数据的组织结构与算法解析ppt课件

单击此处编辑母版文本样式,第二级,第三级,*,单击此处编辑母版标题样式,第六章,数据的组织结构与算法,6.1,数据结构的基本概念,6.2,常用的几种数据结构,6.3,算法,6.4,程序设计方法,1,6.1,数据结构的基本概念,6.1.1,数值计算与非数值计算,数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，,数据对客观事物采用计算机能够识别、存贮和处理形式所进行的描述,。简言之，,数据就是计算机化的信息,。,数学模型有定量模型和定性模型两类之分，定量模型指的是可以用数值方程表示的一类计算模型，而定性模型则是指非数值性的数据结构,如表、树和图等及其运算。,2,数据结构（,Data Structure,）问题起源于程序设计的发展。,第一个,8008,芯片只有,4K,的内存，微软的最初成立就是为这个芯片的机器编写,BASIC,语言，优化在每一处都非常重要。逐渐地，人们注意了数据表示与操作的结构化，把一些确实能够有效解决问题的数据表示和算法总结出来，如表、栈、队、树、图（稍后会介绍这些术语）等被单独抽出研究，而这些方法便形成一门学问，这就是,“,数据结构,”,这门学科的来源。,6.1.2,数据结构的起源,3,数据结构有逻辑上的数据结构和物理上的数据结构之分。,逻辑上的数据结构反映成分数据之间的逻辑关系。,物理上的数据结构反映成分数据在计算机内部的存储安排。,6.1.3,对数据结构的理解,4,1.,表示,对象,/,实体及其关系在计算机中的表示。只有对象及其相互关系已存储（表示）在计算机中，才能被进一步处理；,2.,操作：对对象,/,实体进行处理、访问。,数据结构,的一般,定义,：相互之间存在着一定关系的数据元素的集合及定义在其上的操作（运算）称为,数据结构。,5,1.,插入,：在数据结构中的指定位置增添新的数据元素,2.,删除,：删去数据结构中指定的数据元素。,3.,查找,：在数据结构中寻找某个特定要求的数据元素。,4.,排序,：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按某个关键字值由小到大或由大到小的次序排列。,5.,遍历,：按某一次序访问数据结构中的每一个数据元素。,6.1.4,对数据结构中数据元素的操作,6,例,6.1,解一元二次方程,ax,2,+bx+c=0.,利用计算机解此方程，第一个问题就是,如何在计算机中表示该方程,。分析该方程，可知决定方程的是方程的三个系数值：,a,、,b,、,c,，而它们的次序表示它们分别属于那一项，其他符号是为增加可读性而引入的，因此，可用这三个系数的线性排列在计算机中表示该方程。例如：,3x,2,-x+1=0,表示为（,3,-1,1,）,x,2,-3=0,表示为,(1,0,-3),在数据结构中，,将若干个数线性排列的数（元素）称为线性表，,因此，一元二次方程,ax,2,+bx+c=0,就在计算机中表示为线性表（,a,b,c,）。解方程实质上是,对线性表,(a,b,c),进行操作。,6.1.5,数据结构能解决什么问题,7,定义变量,X,和一个线性表，如数组,int,S3;S2,，,S1,，,S0,可以分别存放三个系数值,输入,S2,，,S1,，,S0,三个系数值,输入任意一个值,X,开始,S2*X*X+S1*X+S00,，从编号为,1,的人开始，按顺时针方向,1,开始顺序报数，报到,m,时停止。报,m,的人出圈，同时留下他的密码作为新的,m,值，从他在顺时针方向上的下一个人开始，重新从,1,开始报数，如此下去，直至所有的人出列为止。,17,当,n,和,m,较大时，用人工求解约瑟夫环问题是相当繁琐的。,采用单循环链表就容易解决。,其基本思路是：,人围成一圈，把一人看成一个结点，,人之间的关系采用链接方式，即每一结点有一个前趋结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当,人出列时，将,结点的前趋结点指针指向,结点的后继结点指针，即把,结点驱出循环链。,18,1,树的定义,树是由一个或多个结点组成的有限集合，如图,6-12,所示。,6.2.2,树结构,19,必有一个特定的称为,根,（,ROOT,）的结点，根的每个分支称为,子树,（,sub-tree,），子树也是一棵树,树中的每一个结点都可以不止一个直接后继，结点的后继结点称为该结点的“子结点”（,Children,）,除根结点外的所有结点有且只有一个直接前趋,结点的前趋结点称为该结点的“父结点”（,Parent,）,同一父结点的子结点称为“兄弟”（,Sibling,）,结点下不再有分支的称为树叶（,leaf,），或者叶子结点,树结构的特点,20,二叉树的特点：树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于。,二叉树的子树有左右之分，称为左子树和右子树。而且子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清楚。例如图,6-13,是两棵不同的二叉树。,2,二叉树,21,所谓遍历二叉树，就是,按一定的规则和顺序走遍二叉树的所有结点,，使每一个结点都被访问一次，而且只被访问一次。,二叉树的遍历可分为,先序遍历,中序遍历,后序遍历,3,二叉树的遍历,22,1,先序遍历递归算法定义：,若二叉树非空，则依次执行操作：,(1),访问根结点；,(2),遍历左子树；,(3),遍历右子树。,A,B,D,G,E,C,F,2.,中序遍历递归算法定义：,若二叉树非空，则依次执行操作：,(1),遍历左子树；,(2),访问根结点；,(3),遍历右子树。,G,DBEA,C,F,3,后序遍历递归算法定义：,若二叉树非空，则依次执行操作：,(1),遍历左子树；,(2),遍历右子树；,(3),访问根结点。,G,DEBF,C,A,23,一个图由有限的顶点（,Vertices,）和边（,Edge,）组成，所以可形式化地用,G,（,V,，,E,）,代表一个图。图中的结点称为顶点，顶点之间的连线代表边。,6.2.3,图结构,24,图,(Graph),是由非空的顶点集合和一个描述顶点之间关系,边（或者弧）的集合组成。,其形式化定义为：,G,（,V,，,E,）,V,vi|,vidataobject,E,(,vi,vj,)|vi,vj,V,P(vi,vj,),其中，,G,表示一个图，,V,是图,G,中顶点的集合，,E,是图,G,中边的集合，集合,E,中,P(vi,vj,),表示顶点,vi,和顶点,vj,之间有一条直接连线，即偶对,(,vi,vj,),表示一条边,。,6.2.3,图结构,25,下图（无向图,G1,）给出了一个图的示例，在该图中：,集合,V,v1,v2,v3,v4,；,集合,E,(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4),6.2.3,图结构,26,如果数据结构中，数据元素之间不考虑关系问题（无前趋,/,后继之分），则称这种结构为,集合,。在集合中，各元素是,“,平等,”,的，它们的共同关系是：都属于同一个集合。,6.2.4,集合,27,6.3,算法,6.3.1,算法的特性,算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。,1.,有穷性,2.,确定性,3.,可行性,4.,有输入,5.,有输出,28,算法的五个特性,（,1,）,有穷性：,对任何合法的输入值，一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成；,（,2,）,确定性：,算法中每一条指令必须有确切的含义，不会产生二义性，对于相同的输入只能得出相同的输出。,（,3,）,可行性：,即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现的,。,（,4,）,输入：,一个算法有,0,个或多个输入，这些输入取自于某个特定的数据对象的集合，它可以使用,输入语句,从外部提供，也可以在算法内通过,赋初值,给定。,（,5,）,输出：,一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量,。,29,在设计算法时，通常应考虑以下原则：,首先设计的算法必须是“,正确的,”,其次应有很好的“,可读性,”，还必须具有“,健壮性,”,最后还应考虑所设计算法的复杂性，即有“,高效率与低存储量,”。,6.3.2,什么是“好”的算法,30,算法的正确性,所谓算法的,正确性,，也称可靠性或有效性，是指：,程序不含语法错误。,程序对于几组输入的数据能够得出满足规格说明要求的结果。,程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。,程序对于一切合法的输入数据都能产生满足规格说明要求的结果。,31,在算法是正确的前提下，算法的,可读性,是摆在第一位的。可读性好有助于人们对算法的理解，难懂的程序易隐藏较多错误，难以调试和修改。,算法的,效率,指的是算法执行时计算机资源的消耗，它包括运行时间代价和存储空间代价。,算法的,健壮性,指的是，算法应对非法输入的数据做出恰当反映或进行相应处理。它强调的是，如果输入非法数据时，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。,32,算法的复杂性是算法运行所需要的计算机资源的量。算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。,算法的复杂性有,时间复杂性,和,空间复杂性,之分。,需要的时间资源的量，即算法的运行速度，称作,时间复杂性,。,需要的空间（即存储器）资源的量称作,空间复杂性,。,6.3.3,算法复杂性,33,1,自然语言,自然语言是人们日常所用的语言，如汉语、英语、德语等。,例如，求,3,个数中最大者的问题，可以描述为：,比较前两个数。,将中较大的数与第三个数进行比较。,步骤中较大的数即为所求。,6.3.4,算法的表示,34,2,流程图,流程图是描述算法的常用工具。它采用美国国家标准化协会,ANSI,（,American National Standard Institute,）规定的一组图形符号来表示算法,起止框,判断框,处理框,输入,/,输出框,注释框,流向线,连接点,35,3,伪代码,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便格式紧凑，易于理解，便于向计算机程序设计语言过渡。,例：求两个数的较大者，用伪代码描述算法如下：,Find the bigger,Input:two number s:a,b,1.if(the first number a is greater than or equal to the second number b),then,1.1 return a,else,1.2 return b,end if,end,36,4,计算机程序设计语言,一般而言，计算机程序设计语言描述的算法是清晰的、简明的，最终也能由计算机处理的，然而也不是完善无缺。它需要设计者用特定程序设计语言编写的算法，限制了与他人的交流；容易陷入描述计算步骤的细节而忽视算法的本质。,37,6.4,程序设计方法,6.4.1,计算机程序的性质,计算机程序包含两方面的内容：,对象及对象之间关系,(,数据结构,),；,描述对这些对象进行处理的加工规则,(,算法,),。,38,目的性,程序有明确的目的，程序运行时能完成赋予它的功能。,分步性,程序为完成其复杂的功能，由一系列计算机可执行的步骤组成。,有序性,程序的执行步骤是有序的，不可随意改变程序步骤的执行顺序。,有限性,程序是有限的指令序列，程序所包含的步骤是有限的。,操作性,有意义的程序总是对某些对象进行操作，使其改变状态，完成其功能。,计算机程序具有以下性质：,39,数据结构是数据构造的逻辑表示形式，算法是处理问题的方法和步骤，最后问题的解由计算机程序给出。这是程序员在程序设计时应考虑的主要问题。,6.4.2,程序设计与数据结构、算法之间的关系,40,1.,程序的控制结构,一个可以用,顺序、选择、循环和跳转,(,如,goto,语句,),四种程序结构解决的问题，也一定能用顺序、选择、循环三种程序结构解决。,但确实存在这样的问题，它