数据结构与算法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2,数据结构与算法,1,2.1,算法,2.1.1,算法,(algorithm),基本概念,对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。,算法具有,有穷性,、,确定性,、,可行性,、,输入,和,输出,等个重要特性。,2,2.1.2,算法的基本要素,1,、对数据对象的运算和操作,算术运算,逻辑运算,关系运算,数据传输,2,、算法的控制结构,算法中各操作之间的执行顺序,描述算法的工具通常有传统流程图、,N-S,结构化流程图、算法描述语言等,一个算法一般可以用,顺序、选择、循环,三种基本机构组合而成。,3,2.1.3,算法设计基本方法,列举法,归纳法,递推,递归（以简洁的形式设计和描述算法）,减半递推技术,回溯法,4,2.2,算法复杂度,2.2.1,时间复杂度,依据算法算法编制的程序在计算机上运行时所消耗的时间来度量。通常有事后统计法和,事前,分析估算法。,一个算法是由控制结构（顺序、分支和循环）和原操作构成的，算法时间取决于两者的综合效果。,算法中基本操作重复执行次数,n,和算法执行时间同步增长，称作算法的时间复杂度。,5,2.2.2,算法的空间复杂度,一般是指执行这个算法所需要的内存空间,一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间,一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。,6,例题讲解,7,算法的时间复杂度是指（）,A),执行算法程序所需要的时间,B),算法程序的长度,C),算法执行过程中所需要的基本运算次数,D),算法程序中的指令条数,算法的空间复杂度是指（）,A),算法程序的长度,B),算法程序中的指令条数,C),算法程序所占的存储空间,D),执行过程中所需的存储空间,在计算机中，算法是指（）,A),加工方法,B),解题方案的准确而完整的描述,C),排序方法,D),查询方法,8,算法分析的目的是（）,A),找出数据结构的合理性,B),找出算法中输入和输出之间的关系,C),分析算法的易懂性和可靠性,D),分析算法的效率以求改进,下列叙述中正确的是（）,A),算法的效率只与问题的规模有关，而与数据的存储结构无关。,B),算法的时间复杂度是指执行算法所需的计算工作量。,C),数据的逻辑结构与存储结构是一一对应的。,D),算法的时间复杂度与空间复杂度一定相关。,算法的基本特征是可行性、确定性、（）输入、输出。,9,2.2,数据结构,数据结构的定义,数据的逻辑结构和存储结构,数据结构的图形表示,线性结构与非线性结构,10,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构是反映数据元素之间关系的数据元素集合的表示，即,数据的组织形式,。,数据结构定义,11,数据元素,(Data Element),数据元素是数据的基本单位，即数据集合中的个体。,有时一个数据元数可由若干,数据项,(Data Item),组成。数据项是数据的最小单位。,数据元素亦称,节点,或,记录,。,12,数据结构主要研究以下三个方面的问题：,数据的逻辑结构,数据的存储结构,对各种数据结构进行的运算,13,数据的逻辑结构,数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。,两个要素,1,）数据元素集合,2,）数据元素之间的关系,表示形式,B=(D,R),其中,B,表示一个数据结构,D,表示数据元素集合,R,表示数据元素之间的关系,14,数据的存储结构,数据的存储结构也称数据的物理结构，是数据的逻辑结构在计算机存储空间的存放形式。,数据结构的存储方式：,1.,顺序存储方法,2.,链式存储方法,3.,索引存储方法,4.,散列存储方法,15,数据结构的图形表示,数据结构的表示形式,1),二元关系表,2),图形,B=(D,R),D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),1,4,2,3,16,线性结构与非线性结构,根据数据结构中各数据元素之间前后关系的复杂程度，将数据结构分为线性结构与非线性结构。,线性结构定义：,如果一个非空的数据结构满足下列两个条件：,1.,有且只有一个根节点,2.,每个节点最多有一个直接前驱，也最多有一个直接后继。,则称该数据结构为线性结构，又称线性表。,在一个线性结构中插入或删除任何一个节点还应该是线性结构。,17,例题,例,1:,下列叙述正确的是（）（,2007.9,）,A),程序执行的效率与数据的存储结构密切相关,B,）程序执行的效率只取决于程序的控制结构,C,）程序执行的效率只取决于所处理的数据量,D,）以上三种说法都不对,例,2,数据结构分为线性结构和非线性结构，带链的队列属于,_,结构。,(2006.9),18,2.3,线性表,2.3.1,线性表的定义,线性表是,n,个元素的有限序列，它们之间的关系可以排成一个线性序列：,a1,，,a2,，,，,ai,，,，,an,其中,n,称作表的长度，当,n=0,时，称作空表。,19,线性表的特点：,1.,线性表中所有元素的性质相同。,2.,除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继。,3.,数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有：,初始化、求长度、取元素、修改、,前插、删除、检索、排序。,20,线性表及其顺序存储结构,线性表的顺序存储结构,线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。用这种存储形式存储的线性表称其为顺序表。,21,元素,a,n,.,元素,a,i,.,元素,a,2,元素,a,1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存储地址,内存状态,Loc(,元素,i)=b+,（,i-1)*m,顺序存储结构示意图,(,顺序表,),：,首地址,起始地址,基地址,每个元素所占用,的存储单元个数,22,2.3.2,线性表的顺序存储结构,特点：,1,、线性表中数据元素类型一致，只有数据域，存储空间利用率高。,2,、所有元素所占的存储空间是连续的,3,、各数据元素在存储空间中是按逻辑顺序依次存放的,2.,做插入、删除时需移动大量元素。,3.,空间估计不明时，按最大空间分配。,23,元素,a,1,元素,a,2,.,元素,a,i+1,.,0,1,i,线性表的顺序存储结构,可用,C,语言中的一维数组来描述,.,int VM;,/*V,是数组的名字，,M,是数组大小，假设数组中的元素是整型类型*,/,第,i,个元素的,a,i,存储地址：,Loc(a,i,)=Loc(a,1,)+(i-1)*k,V,V,Vi,Vm-1,24,.,a,2,a,1,a,n,.,a,i+1,a,i,0,1,i-1,i,n-1,1-,1,插入运算,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,x,a,i-1,.,a,2,a,1,a,i,a,i+1,a,length,a,length,a,i+1,a,i,x,25,.,a,2,a,1,a,n,.,a,i+1,a,i,0,1,i-1,i,n-1,1-,2,删除,运算,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,x,a,i-1,.,a,2,a,1,a,i,a,length,a,length,a,i,x,26,插入算法的分析,假设线性表中含有,n,个数据元素，在进行插入操作时，若假定在,n+1,个位置上插入元素的可能性均等，则平均移动元素的个数为：,27,删除算法的分析,在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：,分析结论,顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,28,例题讲解,29,链表不具有的特点是,不必事先估计存储空间,可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,数据结构分为逻辑结构与存储结构，线性链表属于,【1】,。,数据的逻辑结构有线性结构和,【1】,两大类。,30,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【2】,的存储单元中。,数据处理的最小单位是,A),数据,B),数据元素,C),数据项,D),数据结构,数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及,A),数据的存储结构,B),计算方法,C),数据映象,D),逻辑存储,线性表的顺序存储结构和线性表的链式存储结构分别是,A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,31,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成,A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,数据结构包括数据的逻辑结构、数据的,【2】,以及对数据的操作运算。,数据的基本单位是,【5】,。,32,下列叙述中，错误的是,A),数据的存储结构与数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,数据的存储结构是指,A,）数据所占的存储空间,B,）数据的逻辑结构在计算机中的表示,C,）数据在计算机中的顺序存储方式,D,）存储在外存中的数据,33,链表不具有的特点是,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【2】,的存储单元中。,长度为,n,的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为,【1】,。,34,线性表,L=(a1,a2,a3,ai,，,an),，下列说法正确的是,A),每个元素都有一个直接前驱和直接后继,B),线性表中至少要有一个元素,C),表中诸元素的排列顺序必须是由小到大或由大到小,D),除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前驱和直接后继,线性表的顺序存储结构和线性表的链式存储结构分别是,A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,35,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成,A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,当线性表采用顺序存储结构实现存储时，其主要特点是,【1】,。,线性表若采用链式存储结构时，要求内存中可用存储单元的地址,A),必须是连续的,B),部分地址必须是连续的,C),一定是不连续的,D),连续不连续都可以,36,下列叙述中，错误的是,A),数据的存储结构与数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,37,2.4,栈和队列,2.4.1,栈和队列的定义,栈和队列,是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为,限定性的数据结构,。,38,2.4.1.1,栈的定义,栈,：,限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为,后进先出,设栈,s=,（,a,1,，,a,2,，,.,a,i,，,.,，,a,n,）,，,其中,a,1,是栈底元素，,a,n,是栈顶元素。,栈顶（,top),：允许插入和删除的一端；,约定,top,始终指向新数据元素将存放的位置。,栈底（,bottom):,不允许插入和删除的一端。,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,39,队列的主要运算,（,1,）设置一个空队列；,（,2,）插入一个新的队尾元素，称为进队；,（,3,）删除队头元素，称为出队；,（,4,）读取队头元素；,2.4.1.2,队列的定义,定义：,一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为,先进先出（,FIFO,）表,。,a,1,a,2,a,3,a,4,a,n-1,a,n,队 列 示 意 图,队头,队尾,40,2.4.2,栈的顺序存储结构及其基本运算,a,2,a,1,a,1,a,2,top,用顺序存储结构表示的栈,。,顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量,top,指示栈顶位置，,称为,栈顶指针,，,它始终指向待插入元素的位置。,基本运算：,压（进）栈：,PUSH,出栈：,POP,41,3 2 1 0,(a),rear=front=-1(,队空）,e,3,e,4,(c),e1,e2,出队，,e4,入队,队 满,rear=4,front,e,1,e,2,e,3,(b),rear,front,(b)e1,e2,e3,入队,队空时，令,rear=front=-1,，,当有新元素入队时，尾指针加,1,，当有元素出队时，头指针加,1,。故在非空队列中，,头指针,始终指向,队头元素前一个位置,，而,尾指针,始终指向,队尾元素的位置,2.4.3,队列的顺序存储结构及其基本运算,42,例题讲解,43,栈和队列的共同特点是,A),都是先进先出,B),都是先进后出,C),只允许在端点处插入和删除元素,D),没有共同点,如果进栈序列为,e1,e2,e3,e4,，则可能的出栈序列是,A)e3,e1,e4,e2 B)e2,e4,e3,e1,C)e3,e4,e1,e2D),任意顺序,一些重要的程序语言,(,如,C,语言和,Pascal,语言,),允许过程的递归调用。而实现递归调用中的存储分配通常用,A),栈,B),堆,C),数组,D),链表,44,栈底至栈顶依次存放元素,A,、,B,、,C,、,D,，在第五个元素,E,入栈前，栈中元素可以出栈，则出栈序列可能是,A)ABCED B)DCBEA C)DBCEA D)CDABE,栈通常采用的两种存储结构是,A),线性存储结构和链表存储结构,B),散列方式和索引方式,C),链表存储结构和数组,D),线性存储结构和非线性存储结构,栈和队列通常采用的存储结构是,【1】,。,下列数据结构中，按先进后出原则组织数据的是,A),线性链表,B),栈,C),循环链表,D),顺序表,45,由两个栈共享一个存储空间的好处是,A),减少存取时间，降低下溢发生的机率,B),节省存储空间，降低上溢发生的机率,C),减少存取时间，降低上溢发生的机率,D),节省存储空间，降低下溢发生的机率,下列关于栈的叙述中正确的是,）在栈中只能插入数据,B,）在栈中只能删除数据,C,）栈是先进先出的线性表,D,）栈是后进先出的线性表,下列关于队列的叙述中正确的是,）在队列中只能插入数据,B,）在队列中只能删除数据,C,）队列是先进先出的线性表,D,）队列是后进先出的线性表,46,2.5,链表,线性单链表,双向链表,循环链表,结构及其基本运算,47,2.5.1,线性表的链式存储结构,将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。,数据域存放数据，指针域存放,后继结点,的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。,48,上图的线性表为,ZHAO,，,QIAN,，,SUN,，,LI,，,ZHOU,，,WU,，,ZHENG,，,WANG,49,线性链表表示法,:,50,链式存储结构的特点,插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。,适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。,链表的查找只能从头指针开始顺序查找。,51,a,1,a,2,a,n,a,3,L,.,线性表的链式存储结构可用,C,语言中的“结构指针”来描述,带头结点的线性链表,data,next,typedef struct LNode,int data;,Struct LNode*next;,JD;,52,b,a,b,a,x,P,P,单链表的插入运算,S,在,P,所指向的结点之后插入新的结点,53,b,a,b,a,x,a,n,a,i,a,1,a,2,P,P,a,i-1,x,L,单链表的插入运算,S,54,a,i-1,a,1,a,i,a,i,+,1,L,p,单链表的删除运算,a,i-1,a,1,a,i,a,i,+,1,L,p,q,删除,p,指针指向结点的后一个结点,q,指向,p,的后继结点,2.,修改,p,结点的指针域,3.,删除并释放结点,a,i-1,a,1,a,i,a,i,+,1,L,p,q,55,void lbsc(JD*p)/*,删除,p,指针指向结点的后一个结点*,/,JD*q;,if(p-next!=NULL),q=p-next,;/*q,指向,p,的后继结点*,/,p-next=q-next,;/*,修改,p,结点的指针域*,/,free(q);,/*,删除并释放结点*,/,单链表的删除运算,56,线性链表的查找操作：,设无表头结点的线性链表的头指针为,h,沿着链表的开始往后找结点,x,，若找到，则返回该结点在链表中的位置，否则返回空地址。,JD*lbcz(JD*h,int x),JD*p;,p=h;,while(p!=NULL,return(p);,57,2.5.2,循环链表,:,首尾相接的链表。,将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,a,1,a,2,a,n,a,3,L,.,带头结点的单链表,a,1,a,2,a,n,a,3,L,.,循环单链表,58,2.5.3,双向链表,在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,data,next,before,59,例题讲解,60,用链表表示线性表的优点是,A),便于随机存取,B),花费的存储空间较顺序存储少,C),便于插入和删除操作,D),数据元素的物理顺序与逻辑顺序相同,在单链表中，增加头结点的目的是,A),方便运算的实现,B),使单链表至少有一个结点,C),标识表结点中首结点的位置,D),说明单链表是线性表的链式存储实现,61,非空的循环单链表,head,的尾结点,(,由,p,所指向,),，满足,A)p-next=NULLB)p=NULL,C)p-next=head D)p=head,循环链表的主要优点是,A),不再需要头指针了,B),从表中任一结点出发都能访问到整个链表,C),在进行插入、删除运算时，能更好的保证链表不断开,D),已知某个结点的位置后，能够容易的找到它的直接前件,62,2.6,树,树的基本概念,二叉树的定义及其存储结构,二叉树的前序、中序和后序遍历,63,2.6.1,树的定义,由一个或多个结点组成的有限集合,。,仅有一个根结点，结点间有明显的层次结构关系。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,现实世界中，能用树的结构表示的例子：,学校的行政关系、书的层次结构、人类的家族血缘关系等。,64,介绍几个概念：,结点（,Node,）：树中的元素，包含数据项及若干指向其子树的分支。,结点的度（,Degree,）：结点拥有的子树数。,结点的层次：从根结点开始算起，根为第一层。,叶子（,Leaf,）：度为零的结点，也称端结点。,孩子（,Child,）：结点子树的根称为该结点的孩子结点。,兄弟（,Sibling,）：,同一双亲的孩子。,双亲（,Parent,）：孩子结点的上层结点，称为这些结点的双亲。,深度（,Depth),：树中结点的最大层次数。,森林（,Forest,）：,M,棵互不相交的树的集合。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,65,2.6.2,二叉树（,Binary Tree,）,1,、二叉树的定义及其性质,(1),二叉树的定义,二叉树的五种基本形态,二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。,空二叉树,仅有,根结点,右子树为空,左子树为空,左右子树均非空,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。,66,二叉数是,n(n,0),个结点的有限集合。它或为空数,(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。,特别要注意：,二叉数不是,树的特殊情况。,a,a,b,b,两棵不同的二叉数,67,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层上,(i=3),，有,2,3-1,=4,个节点。,第四层上,(i=4),，有,2,4-1,=8,个节点。,68,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,B,、,深度为,h,的二叉树中至多含有,2,h,-1,个结点。,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,此树的深度,h=4,，共有,2,4,-1=15,个节点。,69,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,B,、,深度为,h,的二叉树中至多含有,2,h,-1,个结点。,C,、,若在任意一棵二叉树中，有,n,0,个叶子结点，,有,n,2,个度为,2,的结点，则：,n,0,=n,2,+1,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,n,0,=8,n,2,=7,70,（,3,）满二叉树,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,特点：每一层上都含有最大结点数。,71,4,2,3,1,6,7,8,9,10,11,12,5,非完全二叉树,（,4,）完全二叉树,4,2,3,1,6,7,8,9,10,11,12,5,完全二叉树,特点：除最后一层外，每一层都取最大结点数，,最后一层结点都集中在该层最左边的若干位置。,72,（,5,）树与二叉树的区别,A,树中结点的最大度数没有限制，二叉树结点最大度数为,2,。,B,树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。,树,二叉树,73,2,、二叉树的存储结构,(2),链式存储结构,T16,若父结点在数组中,i,下标处，其左孩子在,2*i,处，右孩子在,2*i+1,处。,11,A,B,c,F,E,D,1,2,4,8,9,10,5,6,3,7,12,13,14,15,(1),顺序存储结构,(1),顺序存储结构,2,h,-1=,2,4,-1=15,用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。,0,0,0,0,F,E,0,0,0,D,C,0,B,A,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,0,一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。,74,2.6.3,二叉树的遍历,查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。,（,1,）遍历定义及遍历算法,遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。,按先左后右的原则，一般使用三种遍历：,先序遍历,(D L R):,访问根结点，按先序遍历左子树，按先序遍历右子树。,中序遍历,(L D R):,按中序遍历左子树，访问根结点，按中序遍历右子树。,后序遍历,(L R D):,按后序遍历左子树，按后序遍历右子树，访问根结点。,二叉树为空时，执行空操作，即空二叉树已遍历完。,75,（,2,）遍历算法,先序遍历：,D L R,中序遍历：,L D R,后序遍历：,L R D,A,D,B,C,T,1,T,2,T,3,D L R,A,D L R,D L R,B,D,C,D L R,以先序遍历,D L R,为例演示遍历过程,ABDC,BDAC,DBCA,76,例题讲解,77,在深度为,7,的满二叉树中，叶子结点的个数为（）,(2006.4),A)32 B)31 C)64 D)63,某二叉树有,n,个度为,2,的结点，则该二叉树中的叶子节点数为（）,(2007.4),A)n+1 B)n-1 C)2nD)n/2,具有,3,个结点的二叉树有,A)2,种形态,B)4,种形态,C)7,种形态,D)5,种形态,78,设有下列二叉树：,对此二叉树前序遍历的结果为,A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT,79,设一棵二叉树中有,3,个叶子结点，有,8,个度为,1,的结点，则该二叉树中总的结点数为,(),A)12 B)13 C)14D)15,设有下列二叉树：,对此二叉树的中序遍历的结果为,A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA,80,2.7,查找和排序,顺序查找与二分查找算法,基本排序算法（交换类排序、选择类排序、插入类排序）,81,2.7.1,查找,查找是在一个给定的数据结构中，,根据给定的条件查找满足条件的结点,。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。,查找的结果：,查找成功：,找到满足条件的结点,查找失败：,找不到满足条件的结点。,82,2.7.1.1,顺序查找（线性查找）,查找过程：,对给定,的一关键字,K,，从线性表的一端开始，逐个进行记录的关键字和,K,的比较，直到找到关键字等于,K,的记录或到达表的另一端。,可以采用从前向后查，也可采用从后向前查的方法。,在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。,在下面两种情况下只能采取顺序查找：,a.,线性表为无序表（元素排列是无序的）；,b.,即使是有序线性表，但采用的是链式存储结构。,83,2.7.1.2,折半查找（二分法查找）,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。,前提：必须在,具有顺序存储结构的,有序表中进行,。,分三种情况：,1,）若中间项的值等于,x,则说明已查到。,2,）若,x,小于中间项的值，则在线性表的前半部分查找；,3,）若,x,大于中间项的值，则在线性表的后半部分查找。,特点,：比顺序查找方法效率高。最坏的情况下，需要比较,log2n,次,。,84,查找,23,和,79,的过程如下图：,mid=(low+high)/2,不进位取整,(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),low,high,mid,(08,14,23,37,46,55,68,79,91),low,high=mid-1,mid,(08,14,23,37,46,55,68,79,91),low=mid+1,high,mid,(08,14,23,37,46,55,68,79,91),low,high,mid,(08,14,23,37,46,55,68,79,91),low,high,mid,(08,14,23,37,46,55,68,79,91),low,high,mid,85,2.7.2,排序,2.7.2.1,概述,1,、排序的功能：,将一个数据元素（或记录）的,任意序列,，重新排成一个按关键字,有序,的序列。,2,、排序过程的组成步骤：,首先,比较,两个关键字的大小；,然后将记录从一个位置,移动,到另一个位置。,86,排序方法,插入排序,选择排序,交换排序,归并排序,直接插入排序,折半插入排序,简单选择排序,堆排序,起泡排序,快速排序,87,2.7.2.2,插入排序,直接插入、折半插入,1,、直接插入排序,:,基本思想：,从数组的第,2,号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。,需要,n(n-1)/2,次比较,88,该算法适合于,n,较小的情况，时间复杂度为,O(n,2,).,待排元素序列：,53,27 36 15 69 42,第一次排序：,27 53,36 15 69 42,第二次排序：,27 36 53,15 69 42,第三次排序：,15 27 36 53,69 42,第四次排序：,15 27 36 53 69,42,第五次排序：,15 27 36 42 53 69,直接插入排序示例,对于有,n,个数据元素的待排序列，插入操作要进行,n-1,次,89,2,、折半插入排序,折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。,折半插入排序,的条件：,在有序序列中插入一个关键字。,90,例：有,6,个记录，前,5,个已排序的基础上，对第,6,个记录排序。,15 27 36 53 69,42,low,mid,high,15 27 36 53 69,42,low,high,mid,15 27 36 53 69,42,high,low,15 27 36 42 53 69,(high36),(4253 ),91,1,、简单选择排序,思想：首先从,1n,个元素中选出关键字,最小,的记录交换到,第一个,位置上。然后再从第,2,个到第,n,个元素中选出次小的记录交换到,第二个,位置上，依次类推。,时间复杂度为,O(n,2,),，最坏情况下需要比较,n(n-1)/2,次,适用于,待排序元素较少,的情况。,2.7.2.3,选择排序,简单选择排序、堆排序,92,初态,8,3 9 1 6,8,3 9 1 6,8,3 9 1 6,8,3 9 1 6,i,j,k,i,j,k,i,j,k,i,j,k,1,3,9 8 6,互换,i,j,k,1,3,9 8 6,i,k,j,1,3,9 8 6,i,k,j,第一趟,第二趟,1,3,9,8 6,i,k,j,第三趟,93,2,堆排序,也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：,任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。,(1),堆的示例,89,76,24,33,15,10,11,25,36,49,78,56,(a):,堆顶元素取最大值,(b):,堆顶元素取最小值,(2),实现堆排序需解决两个问题：,（,1,）如何由一个无序序列建成一个堆？,（,2,）输出堆顶元素后，如何将剩余元素调整成一个新的堆？,堆排序需要比较的次数为,O(nlog,2,n),94,2.7.2.4,交 换 排 序,交换排序的特点在于,交换,。有冒泡和快速排序两种。,1,、冒泡排序（起泡排序）,思想：,小的浮起，大的沉底。,从左端开始比较。,第一趟：第,1,个与第,2,个比较，大则交换；第,2,个与第,3,个比较，,大则交换，,关键字最大的记录交换到最后一个位置上；,第二趟：对前,n-1,个记录进行同样的操作，关键字次大的记录交换,到第,n-1,个,位置上；,依次类推，则完成排序。,正序：时间复杂度为,O(n),逆序：时间复杂度为,O(n,2,),适合于数据较少的情况。,排序,n,个记录的文件最多需要,n-1,趟冒泡排序。,95,第,六,趟,排,序,后,第,五,趟,排,序,后,第,四,趟,排,序,后,第,三,趟,排,序,后,第,二,趟,排,序,后,第,一,趟,排,序,后,初,始,关,键,字,思想：小的浮起，大的沉底。,49,36,41,65,11,78,36,65,36,41,56,36,41,65,41,36,41,56,11,78,36,36,41,49,11,56,49,25,25,25,11,49,49,56,11,11,11,25,25,25,25,96,2,、快速排序,(,对冒泡排序的改进）,思想：通过一趟排序将待排序列,分成两部分,，使其中,一部分记录,的关键字均比,另一部分小,，再分别对这两部分排序，以达到整个序列有序。,关键字通常取第一个记录的值为基准值。,做法：,附设两个指针,low,和,high,，初值分别指向,第一个记录,和,最后一个记录,，设关键字为,key,，首先从,high,所指位置起,向前,搜索，找到第一个,小于,基准值的记录与基准记录交换，然后从,low,所指位置起,向后,搜索，找到第一个,大于,基准值的记录与基准记录交换，重复这两步直至,low=high,为止。,时间复杂度：,O(log,2,n),97,快速排序过程示意图：,有序序列,6 18 23 52 67,key,初始序列,23 52 6 67 18,low,high,一次交换,18 52 6 67 23,low,high,二次交换,18,23 6 67 52,high,三次交换,18 6 23 67 52,/,完成一趟排序后分别进行快速排序,low,high,98,2.7.2.5,内部排序方法的选择,各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有,：,待排序的记录个数；记录本身的大小；记录的键值分布情况,等。,若待排序的记录个数,n,较小时，可采用简单排序方法。,若,n,较大时，应采用快速排序或堆排序。,若待排序的记录已基本有序，可采用起泡排序。,99,