第二章数据结构课件

第二章 数据结构李素清李素清.第1节 数据结构的引入度量一个算法的好坏用度量一个算法的好坏用时间复杂度时间复杂度和和空间复杂度空间复杂度算法最终要用程序在计算机上实现算法最终要用程序在计算机上实现程序在运行过程中要用到程序在运行过程中要用到数据数据不同的不同的数据结构数据结构可以采用不同的编程方法可以采用不同的编程方法例如：在下列数据中查找例如：在下列数据中查找67：2132122 3145 56 673145 2122 13267 56顺序查找：顺序查找：二分法：二分法：数据结构的好坏影响算法的效率数据结构的好坏影响算法的效率.1.1 什么是数据结构 数据结构数据结构是指相互有关联的数据元素的集合。是指相互有关联的数据元素的集合。它包括以下两个方面：它包括以下两个方面：表示表示数据元素数据元素的信息的信息表示各表示各数据之间的前后件关系数据之间的前后件关系314521221326756.1.2 数据结构研究的内容 数据结构作为计算机的一门学科，主要研究和讨论以下数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：三个方面：(1)数据集合中各数据元素之间所固有的逻辑关系，即数据数据集合中各数据元素之间所固有的逻辑关系，即数据的的逻辑结构逻辑结构;(2)在对数据元素进行处理时，各数据元素在计算机中的存在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的储关系，即数据的存储结构存储结构;(3)对各种数据结构进行的对各种数据结构进行的运算运算：插入、删除、修改数据元：插入、删除、修改数据元素以及对数据元素的一些运算处理素以及对数据元素的一些运算处理。目的：提高目的：提高数据处理的效率数据处理的效率，即：提高数据处理的速度，尽，即：提高数据处理的速度，尽量节省在数据处理过程中所占用的计算机存储空间量节省在数据处理过程中所占用的计算机存储空间.1.2.1 数据的逻辑结构 反映数据元素之间逻辑关系的数据结构，包含以下两反映数据元素之间逻辑关系的数据结构，包含以下两方面的信息：方面的信息：(1)表示表示数据元素数据元素的信息，记作的信息，记作D;(2)表示各数据元素之间的表示各数据元素之间的前后件关系前后件关系，记作，记作R。如果用如果用B表示数据结构：表示数据结构：l 一个数据的逻辑结构可以用一个数据的逻辑结构可以用二元关系二元关系表示为：表示为：B=(D,R).例例1：一年四季的数据结构可以表示为：一年四季的数据结构可以表示为：B=(D,R)D=春，夏，秋，冬春，夏，秋，冬 R=(春，夏春，夏),(夏，秋夏，秋),(秋，冬秋，冬)例例2：家庭成员的数据结构可以表示为：家庭成员的数据结构可以表示为：B=(D,R)D=父亲，儿子，女儿父亲，儿子，女儿 R=(父亲，儿子父亲，儿子),(父亲，女儿父亲，女儿).l 数据逻辑结构的数据逻辑结构的图形表示图形表示（1）方框表示数据元素值，称为结点；）方框表示数据元素值，称为结点；（2）有向线段（箭头）从前件指向后继结点，表示数据元）有向线段（箭头）从前件指向后继结点，表示数据元素之间的前后关系。素之间的前后关系。（3）没有前驱的结点称为根结点，没有后继结点的称为叶）没有前驱的结点称为根结点，没有后继结点的称为叶子结点（终端结点）。子结点（终端结点）。春春夏夏秋秋冬冬父亲父亲儿子儿子女儿女儿.1.2.2 逻辑结构分类l 线性结构线性结构：满足下面两个条件的非空数据结构：满足下面两个条件的非空数据结构 如：例如：例1 有且只有一个根结点；有且只有一个根结点；每个结点最多有一个前驱，最多只有一个后继每个结点最多有一个前驱，最多只有一个后继 常见的线性结构：常见的线性结构：线性表线性表、栈栈、队列队列 非线性结构非线性结构 集合集合：元素无顺序：元素无顺序 树形结构树形结构：结构中的数据元素之间存在着：结构中的数据元素之间存在着“一对多一对多”的关系。如：例的关系。如：例2 图形结构图形结构：数据元素之间存在：数据元素之间存在“多对多多对多”的关系，每的关系，每个结点都可以有多个直接前驱和多个直接后继。个结点都可以有多个直接前驱和多个直接后继。春春夏夏秋秋冬冬父亲父亲儿子儿子女儿女儿.l 线性结构和非线性结构都具有的一种线性结构和非线性结构都具有的一种特殊特殊情情况。况。空数据结构是属于线性结构还是非线性结构空数据结构是属于线性结构还是非线性结构要看具体情况：要看具体情况：如果按照如果按照线性结构的规则线性结构的规则去处理则属于线性结去处理则属于线性结构构如果按照如果按照非线性结构的规则非线性结构的规则去处理则属于非线去处理则属于非线性结构。性结构。空数据结构.1.2.3 数据的存储结构 数据的逻辑结构在计算机存储空间中的数据的逻辑结构在计算机存储空间中的存放形式存放形式称称为数据的存储结构，或数据的物理结构。为数据的存储结构，或数据的物理结构。数据存储时，不仅要存放数据存储时，不仅要存放数据元素数据元素的信息，而且要的信息，而且要存储数据存储数据元素之间的前后件关系元素之间的前后件关系的信息。的信息。常见的存储结构有：常见的存储结构有：顺序、链接顺序、链接、索引索引 数据的存储结构与逻辑结构的关系数据的存储结构与逻辑结构的关系一一种数据的逻辑结构根据需要可以表示成种数据的逻辑结构根据需要可以表示成多种多种存储结存储结构构一一种存储结构可以表示种存储结构可以表示多种多种逻辑结构。逻辑结构。.第2节 线性表及其顺序存储结构2.1 2.1 线性表的基本概念线性表的基本概念 线性表是由线性表是由n（n0）个数据元素构成的）个数据元素构成的有限有限序列（序列（a1,a2,an）l 当当n=0时，称为空线性表。时，称为空线性表。l n0时，称为非空线性表，具有下面的特征：时，称为非空线性表，具有下面的特征：(1)有且只有一个有且只有一个根结点根结点a1，它无前驱，它无前驱;(2)有且只有一个有且只有一个终端结点终端结点an，它无后继，它无后继;(3)除根结点与终端结点外，其他所有结点有且只有一除根结点与终端结点外，其他所有结点有且只有一个前驱，也有且只有一个后继。个前驱，也有且只有一个后继。l 结点个数结点个数n称为线性表的长度。称为线性表的长度。a1a2a3an.2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储，称为线性表的顺序存储，称为顺序表顺序表用一组用一组地址连续的存储单元地址连续的存储单元依次存储线性表的数据元依次存储线性表的数据元素素 线性表第线性表第1个元素的地址为个元素的地址为adr(a1)每个元素占的字节数为每个元素占的字节数为k 第第i个元素个元素ai的存储地址为：的存储地址为：ADR(ai)=ADR(a1)+(i-1)k 线性表的顺序存储结构是一种线性表的顺序存储结构是一种随机存取随机存取的结构的结构a1a2a3 an-1an.2.3 2.3 线性表顺序存储后的运算线性表顺序存储后的运算查找、查找、插入、删除插入、删除排序排序分解、合并分解、合并复制复制逆转逆转.2.3.1 顺序表的插入运算长度为长度为n的顺序表的顺序表(a1,a2,ai-1,ai,an)在第在第i（1in+1)个位置插入一个新结点个位置插入一个新结点x长度为长度为n的顺序表变为长度为的顺序表变为长度为n+1的顺序表的顺序表 (a1,a2,ai-1,x,ai,an)插入运算的基本步骤是：插入运算的基本步骤是：将结点将结点an，ai各后移一位，腾出第各后移一位，腾出第i个位置；个位置；将将x插入该空位插入该空位 表长加表长加1.顺序表的插入运算举例：顺序表的插入运算举例：.顺序表插入结点算法分析：合法的插入位置共合法的插入位置共n+1个，即第个，即第1个位置到第个位置到第n+1个位个位置置最坏情况是插入到第最坏情况是插入到第1个位置，共需要移动个位置，共需要移动n个元素个元素最好情况是插入到最好情况是插入到n+1个位置，不需要移动元素个位置，不需要移动元素在第在第i个位置上插入需要移动个位置上插入需要移动n-i+1次次在插入位置等概率情况下，平均移动元素的个数是在插入位置等概率情况下，平均移动元素的个数是 (n+(n-1)+(n-2)+2+1+0)/(n+1)=n/2.2.3.2 顺序表的删除运算长度为长度为n指将顺序表指将顺序表 (a1,a2,ai-1,ai,ai+1,an)删除第删除第i(1in)个结点个结点变为长度为变为长度为n-1的顺序表的顺序表 (a1,a2,ai-1,ai+1,an)线性表删除运算的基本步骤是：线性表删除运算的基本步骤是：结点结点ai+1，an依次向依次向前前移动一个位置；移动一个位置；表长减表长减1.在线性表中删除元素举例在线性表中删除元素举例.顺序表删除结点的算法分析合法的删除位置共合法的删除位置共n个，即第个，即第1个位置到第个位置到第n个位置个位置最坏情况是删除第最坏情况是删除第1个位置上的元素，共需要移动个位置上的元素，共需要移动n-1个个元素元素最好情况是删除第最好情况是删除第n个位置上的元素，不需要移动元素个位置上的元素，不需要移动元素删除第删除第i个位置上的元素需要移动个位置上的元素需要移动n-i次次在删除位置等概率情况下，平均移动元素的个数是在删除位置等概率情况下，平均移动元素的个数是 (n-1)+(n-2)+2+1+0)/n=(n-1)/2.2.4 2.4 顺序表的特点顺序表的特点顺序表中所有元素的所占的顺序表中所有元素的所占的存储存储空间是连续的空间是连续的;线性表中线性表中逻辑上相邻的逻辑上相邻的数据元素数据元素在存储空间中是相邻的，即按在存储空间中是相邻的，即按顺顺序依次存放的序依次存放的；可以随机访问元素；可以随机访问元素；对于元素对于元素很多很多的线性表进行插入的线性表进行插入和删除运算不方便。和删除运算不方便。a1a2a3an-1anadr(a1)adr(an).定义：定义：栈和队列是一种栈和队列是一种线性结构线性结构 栈和队列是一种栈和队列是一种特殊特殊的线性表的线性表第3节 栈和队列.3.1.1 3.1.1 什么是栈？什么是栈？例如：进入死胡同的汽车例如：进入死胡同的汽车 栈是限定在一端进行插入与删除的栈是限定在一端进行插入与删除的线性表线性表。允许插入与删除的一端称为允许插入与删除的一端称为栈顶栈顶（用（用top表表示）示）不允许插入与删除的另一端称为不允许插入与删除的另一端称为栈底栈底（用（用bottom表示）。表示）。3.1 栈及其基本运算.a1a2a3an栈顶栈顶栈底栈底栈底元素栈底元素栈顶元素栈顶元素入栈入栈出栈出栈栈的示意图栈的示意图.3.1.2 3.1.2 栈的特点栈的特点l 栈按照栈按照“先进后出先进后出”(FILO)或或“后进先出后进先出”(LIFO)组织数据，栈具有记忆作用。组织数据，栈具有记忆作用。栈顶元素总是栈顶元素总是后被插入后被插入的元素，也是的元素，也是最先最先被删除被删除的元素；的元素；栈低元素总是栈低元素总是最先被插入最先被插入的元素，也是的元素，也是最最后才能被删除后才能被删除的元素。的元素。入栈时，如果栈中已满，称为上溢错误入栈时，如果栈中已满，称为上溢错误出栈时，栈中没有元素，称为下溢错误出栈时，栈中没有元素，称为下溢错误.3.1.3 3.1.3 栈的存储方式栈的存储方式顺序存储顺序存储：用顺序方式实现的栈称为：用顺序方式实现的栈称为顺序顺序栈栈链式存储链式存储：用链式实现的栈称为：用链式实现的栈称为链栈链栈.3.1.4 栈的顺序存储及其运算用用S(1:m)作为栈的顺序存储空间，作为栈的顺序存储空间，m为栈的最大容量。为栈的最大容量。（1）判断栈空判断栈空：top=0时栈为空时栈为空（2）判断栈满判断栈满：top=m时栈满时栈满（3）x进栈进栈：top=top+1;stop=x（4）出栈出栈：x=ssq.top;top=top-1（5）读栈顶元素读栈顶元素：x=stopa1a2a3123mtopbottom.举例：举例：.栈练习一个栈的初始状态为空。一个栈的初始状态为空。首先将元素首先将元素5,4,3,2,1，依次入栈，然，依次入栈，然后退栈一次后退栈一次。再将元素再将元素A,B,C,D依次入栈依次入栈之后将所有元素全部退栈之后将所有元素全部退栈则所有元素退栈（包括中间退栈的元素）的顺序为则所有元素退栈（包括中间退栈的元素）的顺序为_ 1DCBA2345.3.2 队列3.2.1 什么是队列？例如：排队买票例如：排队买票a1a2a3an出队出队入队入队队头队头队尾队尾队列示意图队列示意图.3.2.2 队列的特点：l 队列是指允许在一端队列是指允许在一端(队尾队尾)进行插入，而在另一端进行插入，而在另一端(队头队头)进行删除的进行删除的线性表线性表。队列有两个指针：队列有两个指针：Rear指针指向队尾元素的后一指针指向队尾元素的后一个位置，个位置，front指针指向队头元素。指针指向队头元素。队列是队列是“先进先出先进先出”(FIFO)或或“后进后出后进后出”(LILO)的线性表。的线性表。a1a2a3a4mRearFront.3.2.3 队列的存储方式l顺序存储顺序存储：队列采用了顺序存储结构称为：队列采用了顺序存储结构称为顺顺序队列序队列。链式存储链式存储：队列采用了链式存储结构称为：队列采用了链式存储结构称为链队列链队列。.3.2.4 队列的顺序存储l顺序队列用一片顺序队列用一片连续的存储空间连续的存储空间来存放队列来存放队列中的元素外，还需要设置两个指针中的元素外，还需要设置两个指针Front：队头指针，指向队头元素：队头指针，指向队头元素Rear：队尾指针，指向实际队尾元素的下：队尾指针，指向实际队尾元素的下一个位置，为接受新元素做好准备一个位置，为接受新元素做好准备初始值为初始值为0.l 队列的顺序存储结构举例：队列的顺序存储结构举例：这种队列存在的问题：这种队列存在的问题：假溢出假溢出ABCfrontrearDD元素入队后元素入队后DBCfrontrearA元素出队后元素出队后初始队列初始队列ABCfrontrear.3.2.5 循环队列l 将队列存储空间的最后一个位置绕到第一个位置，形将队列存储空间的最后一个位置绕到第一个位置，形成成逻辑上逻辑上的环状空间。的环状空间。即：当即：当rear=m，下一次入队下一次入队rear=1 为了区分队列满还是队列空，通常增加一个标志为了区分队列满还是队列空，通常增加一个标志S。队列空：队列空：S=0，rear=front 队列满：队列满：S=1,rear=front.3.2.6 循环队列运算（1）入队运算）入队运算 在队尾插入一个元素。在队尾插入一个元素。新元素插入到对尾指针指向新元素插入到对尾指针指向的位置，的位置，rear=rear+1。当当rear=m+1时，时，rear=1。当当S=1，rear=front，说明队列已经满，不能进行，说明队列已经满，不能进行入队运算，称为入队运算，称为“上溢上溢”.（2）退队运算）退队运算从队头删除一个元素并赋给指定的变量，从队头删除一个元素并赋给指定的变量，front=front+1。当当front=m+1时，时，front=1当当rear=front,s=0，循环队列为空，不能，循环队列为空，不能进行退队运算，称为进行退队运算，称为“下溢下溢”.3.2.7 循环队列中元素的数目(考点)：rear=front，且，且 S=0,队列为空，数目为队列为空，数目为0rear=front，且，且S=1，队列满，数目为，队列满，数目为mrearfront,数目为数目为rear-fronta1a2a3a41mRearFront.l当当rearfront，为，为rear-front rear=front，s=0，为，为0 rear=front，s=1，为，为m=15 rearlink=first;first=newnode;xa0a1 newnode在第一个结点前插入插入a0firstfirst.在链表末尾插入(插入前插入前)(插入后插入后).在线性单链表中删除指定元素的结点在线性单链表中删除指定元素的结点aiai-1ai+1 ai*p*q3.删除.删除表中第一个元素.删除表中最后一个元素 an-1p(a)(a)删除前删除前 an an-1p(a)(a)删除后删除后 .链表的头指针就是链栈的栈顶指针链表的头指针就是链栈的栈顶指针插入和删除操作只能插入和删除操作只能在栈顶进行在栈顶进行.anan-1a1 nulltop4.1.3 栈的链式存储.S SS Sa an-1n-1a a1 1a an npe epe e p-data=e;p-next=S;S=p;NULL栈的插入（进栈）运算.pa an-1n-1a a1 1a an nS SNULL栈的删除（出栈）运算 p=S;S=S-next;e=p-data;free(p);S S.栈的链式存储结构举例栈的链式存储结构举例.l带链的队列实际上是一个同时带有头指针和尾的指针带链的队列实际上是一个同时带有头指针和尾的指针的带头结点的单链表的带头结点的单链表头指针头指针front指向链队列的头结点，尾指针指向链队列的头结点，尾指针rear指向链指向链队列的尾结点。队列的尾结点。链队列一般不会出现队满的情况链队列一般不会出现队满的情况a1a2an nullfrontrear4.1.4 队列的链式存储.队列的插入运算（入队）J1J1Q.frontQ.frontQ.rearQ.rear J2 J2 e epp-data=e;p-next=null;Q.rear-next=p;Q.rear=p;Q.rearQ.rear.pp=Q.front;Q.front=p.nextfree(p);队列的删除运算（出队）J1J1Q.frontQ.frontQ.rearQ.rear J2 J2 J3 J3.线性表的顺序存储和链式存储的比较顺序存储：顺序存储：优点优点：空间利用率高；随机存取；：空间利用率高；随机存取；缺点缺点：插入、删除要大量的移动元素，时间性：插入、删除要大量的移动元素，时间性能比较差；申请相应的存储空间，大，浪费，能比较差；申请相应的存储空间，大，浪费，小，不够小，不够链式存储链式存储优点优点：插入、删除不需要移动元素插入、删除不需要移动元素；动态分配；动态分配空间，不会溢出。空间，不会溢出。缺点缺点：存储一个结点需要多余的空间，所以空：存储一个结点需要多余的空间，所以空间利用率低。间利用率低。.树是一类重要的树是一类重要的非线性非线性数据结构，是以数据结构，是以分支分支关系定义的关系定义的层次层次结构结构第5节 树和二叉树A只有一个根结点的树只有一个根结点的树.ABCDEFGHIJKLMA A为为根结点，其余分为三个互不相交的子集根结点，其余分为三个互不相交的子集T1=B,E,F,K,L T2=C,G T3=D,H,I,J,MT1=B,E,F,K,L T2=C,G T3=D,H,I,J,MT1,T2,T3T1,T2,T3都是都是根结点根结点A A的子树，且本身又是一棵树。的子树，且本身又是一棵树。根.5.1 树的定义树是由树是由n个结点组成的有限集合个结点组成的有限集合若若n=0，称为空树，称为空树若若n0有一个特定的称为有一个特定的称为根根（root）的结点。它只有直接后继，）的结点。它只有直接后继，但没有直接前驱；但没有直接前驱；除根结点以外的其它结点可以划分为除根结点以外的其它结点可以划分为m（m0）个互不）个互不相交的有限集合相交的有限集合T0,T1,Tm-1,每个集合每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树）又是一棵树，称为根的子树每棵子树的根结点有且仅有一个直接前驱，但可以有每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。个或多个直接后继。.BCDEFG HIJKL MAl 在树结构中，每一个结点只有一个前驱，称为在树结构中，每一个结点只有一个前驱，称为父结父结点点；l 没有前驱的结点只有一个，称为树的没有前驱的结点只有一个，称为树的根结点根结点，简称，简称树的根；树的根；l 每一个结点可以有多个后继，称为该结点的每一个结点可以有多个后继，称为该结点的子结点；子结点；l 同一父结点下的子结点称为同一父结点下的子结点称为兄弟结点；兄弟结点；l 没有后继的结点称为没有后继的结点称为叶子结点叶子结点。l 一个结点所拥有的后继的个数（子结点的数目）称为该一个结点所拥有的后继的个数（子结点的数目）称为该结点的度结点的度；l 叶子结点的度为叶子结点的度为0l 所有结点中最大的度称为所有结点中最大的度称为树的度树的度；l 层数层数：根结点的层数为：根结点的层数为1，其余结点的层数等于它父结点的层数加，其余结点的层数等于它父结点的层数加1l 树的最大层次称为树的最大层次称为树的深度树的深度。基本术语.1.二叉二叉树的定的定义l 二叉树是由二叉树是由n（n0）个结点的有限集合构成。）个结点的有限集合构成。n=0，称为空二叉树；，称为空二叉树；n=1，只有一个根结点的二叉，只有一个根结点的二叉树树 n1，由一个根结点及，由一个根结点及两棵两棵互不相交的左右子树组成；互不相交的左右子树组成；左右子树都是二叉树。左右子树都是二叉树。根可以有空的左子树或空的右子树。根可以有空的左子树或空的右子树。二叉树是特殊的有序树。二叉树是特殊的有序树。5.2 二叉树.l非空二叉树只有一个根结点；非空二叉树只有一个根结点；每个结点每个结点至多有二棵子树，至多有二棵子树，称为该结点的左子树和右称为该结点的左子树和右子树。子树。即二叉树中不存在度大于即二叉树中不存在度大于2的结点的结点二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒2.二叉树的特点.3.二叉树基本形态AABABABC 空二叉树；只有一个根结点的二叉树；可空二叉树；只有一个根结点的二叉树；可以只有左子树或只有右子树的二叉树；既有以只有左子树或只有右子树的二叉树；既有左子树又有右子树的二叉树。左子树又有右子树的二叉树。.(1)在二叉树的在二叉树的第第k层上层上，最多有，最多有2（k-1）(k1)个结点个结点;4.二叉树的基本性质证明：用归纳法证明证明：用归纳法证明 i=1i=1时时,只有一个根结点只有一个根结点,2 2i-1i-1=2 20 0=1=1 成立成立 假设对所有假设对所有j(j1j(j1)命题成立，即第命题成立，即第j j层上至多有层上至多有2 2j-1j-1个结点个结点 又因为又因为二叉树每个结点的度至多为二叉树每个结点的度至多为2 2，所以，所以第第j+1j+1层至多有层至多有2*2*2 2j-1j-1=2=2j-1+1j-1+1=2=2j j个结点个结点故命题得证故命题得证.(2)深度为深度为k的二叉树最多有的二叉树最多有2k-1个结点个结点;证明：证明：由性质由性质1 1知深度为知深度为k k 的二叉树最大结点数的二叉树最大结点数为为 k kk k (第第i i层上的最大结点数层上的最大结点数)=2)=2i-1i-1 i=1 i=1i=1 i=1 =2=20 0+2+21 1+2+2k-1k-1=(2=(20 0-2-2k-1k-1*2)/(1-2)*2)/(1-2)=2=2k k11.证明：证明：设度为设度为1的结点数目为的结点数目为n1因为：因为：二叉树中所有结点的度均小于或等于二叉树中所有结点的度均小于或等于2所以：二叉树的结点总数为：所以：二叉树的结点总数为：n=n0+n1+n2又又因为因为二叉树中，除根结点外，其余结点都只有一个二叉树中，除根结点外，其余结点都只有一个 分支分支进入进入设设m表示分支数，具有表示分支数，具有n个结点的二叉树的分支总数为个结点的二叉树的分支总数为m=n-1所有这些分支中，每一个度为所有这些分支中，每一个度为1的结点发出一个分支，每个度为的结点发出一个分支，每个度为2的结点的结点发出两个分支，则有：发出两个分支，则有：m=n1+2n2联立上面三个式子：联立上面三个式子：n-1=n1+2n2n=n1+2n2+1=n0+n1+n2得：得：n0=n2+1 (3)度为度为0的结点的结点(即叶子结点即叶子结点)n0总是比度为总是比度为2的结点的结点n2多一个，则多一个，则n0=n2+1.(4)具有具有n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为log2n+1,其中其中log2n表示取表示取log2n的整数部分的整数部分;例：具有例：具有65个结点的二叉树的深度至少为个结点的二叉树的深度至少为_,最多为最多为_至少为：至少为：log265+1=log2（64+1）+1=7最多为：最多为：65（糖葫芦）（糖葫芦）.三、满二叉树和完全二叉树三、满二叉树和完全二叉树1.满二叉树满二叉树定义：定义：若二叉树中的结点，或者度为若二叉树中的结点，或者度为2，或者度为，或者度为0，并且度，并且度为为0的结点（叶子结点）都集中在最下面一层，具有的结点（叶子结点）都集中在最下面一层，具有这种特点的二叉树称为满二叉树。这种特点的二叉树称为满二叉树。深度为深度为m的满二叉树有的满二叉树有2m-1个结点，总结点数为奇数个结点，总结点数为奇数第第k层上有层上有2(k-1)个结点。个结点。.BCDEFLMAGNOHIJK例题例题：求具有：求具有n个结点的满二个结点的满二叉树叶子结点数叉树叶子结点数n0和度为和度为2的的结点数结点数n2分别是多少？分别是多少？解：由于满二叉树中没有度为解：由于满二叉树中没有度为1的结点，则有：的结点，则有：n=n0+n2根据二叉树的性质根据二叉树的性质3：n0=n2+1联立两式：联立两式：n0=(n+1)/2n2=(n-1)/2.2.完全二叉树完全二叉树定义：若二叉树中只有最下面两层的结点的度可以小定义：若二叉树中只有最下面两层的结点的度可以小于于2，并且最下面那一层结点（叶结点）从左到右依次，并且最下面那一层结点（叶结点）从左到右依次紧密排列，这样的二叉树称为完全二叉树。紧密排列，这样的二叉树称为完全二叉树。满二叉树是完全二叉树的特例，但完全二叉树不一定满二叉树是完全二叉树的特例，但完全二叉树不一定是满二叉树。是满二叉树。完全二叉树总结点数为完全二叉树总结点数为n，若，若n为奇数，则叶子结点数为奇数，则叶子结点数为为(n+1)/2;若若n为偶数，则叶子结点数为为偶数，则叶子结点数为n/2 n1=1或或0BCDEFLAGHIJK.性质（重点）性质（重点）(1)具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1;(2)设完全二叉树共有设完全二叉树共有n个结点。如果从根结点开始，按个结点。如果从根结点开始，按层序层序(每一层从左到右每一层从左到右)用自然数用自然数1，2，.n给结点进行给结点进行编号编号(k=1,2.n)，有以下结论：，有以下结论：若若k=1，则该结点为根结点，它没有父结点，则该结点为根结点，它没有父结点;若若k1，则该结点的父结点编号为则该结点的父结点编号为int(k/2);若若2kn，则编号为，则编号为k的结点的左子结点编号为的结点的左子结点编号为2k；否则，该结点无左子结点否则，该结点无左子结点(也无右子结点也无右子结点);若若2k+1n，则编号为，则编号为k的结点的右子结点编号为的结点的右子结点编号为2k+1;否则，该结点无右子结点。否则，该结点无右子结点。.四、二叉树的存储结构（二叉链表）四、二叉树的存储结构（二叉链表）BCFDAEGHA0 B 0C 0 D 0 E 0F0 G 00 H 0二叉树的链表中的结点至少包含三二叉树的链表中的结点至少包含三个域：数据域、左指针、右指针个域：数据域、左指针、右指针.五、二叉树的遍历（必考）：五、二叉树的遍历（必考）：(1)前序遍历前序遍历(根根左右左右)，首先访问根结点，然后遍历左子，首先访问根结点，然后遍历左子树，最后遍历右子树树，最后遍历右子树;在遍历左右子树时，仍然先访问在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。根结点，然后遍历左子树，最后遍历右子树。(2)中序遍历中序遍历(左左根根右右)，首先遍历左子树，然后访问根结，首先遍历左子树，然后访问根结点，最后遍历右子树点，最后遍历右子树;并且，在遍历左右子树时，仍然并且，在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。先遍历左子树，然后访问根结点，最后遍历右子树。(3)后序遍历后序遍历(左右左右根根)，首先遍历左子树，然后访问遍历，首先遍历左子树，然后访问遍历右子树，最后访问根结点。并且，在遍历左右子树时，右子树，最后访问根结点。并且，在遍历左右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结仍然先遍历左子树，然后遍历右子树，最后访问根结点。点。.CEADFGHPBBCFDAEGH先序遍历：先序遍历：FCADBEGHP中序遍历：中序遍历：ACBDFEHGP后序遍历：后序遍历：ABDCHPGEF先序遍历：先序遍历：ABCDFGHE中序遍历：中序遍历：BADGFHCE后序遍历：后序遍历：BGHFDECA.第六节 查找一、顺序查找一、顺序查找 顺序表查找算法：从顺序表查找算法：从线性表线性表的第一个元素开始，依次的第一个元素开始，依次将线性表中的元素与被查找元素比较，若相等表示查将线性表中的元素与被查找元素比较，若相等表示查找成功，若表中所有元素与被查找元素都不相等，则找成功，若表中所有元素与被查找元素都不相等，则查找失败。查找失败。在查找成功时，最好的情况，查找长度为在查找成功时，最好的情况，查找长度为1；最坏情况，；最坏情况，查找长度为查找长度为n；平均查找长度为；平均查找长度为 (1+2+3+n)=(n+1)/2在两种情况下只能用顺序查找：为无序的线性表，链在两种情况下只能用顺序查找：为无序的线性表，链式存储结构的表式存储结构的表.二、二分法查找二、二分法查找在长度为在长度为n的的有序表有序表中查找中查找x的过程的过程将将x与中间项进行比较与中间项进行比较若若x等于中间项的值，查找成功，查找结束。等于中间项的值，查找成功，查找结束。若若x小于中间项的值，则在中间项以前的部分以相同的方小于中间项的值，则在中间项以前的部分以相同的方法进行查找；法进行查找；若若x大于中间项的值，则在中间项以后的部分以相同的方大于中间项的值，则在中间项以后的部分以相同的方法进行查找。法进行查找。这个过程一直进行到查找成功或子表长度为这个过程一直进行到查找成功或子表长度为0（说明线性（说明线性表中没有这个元素）为止表中没有这个元素）为止二分法查找只适用于二分法查找只适用于顺序存储的有序线性表顺序存储的有序线性表对于长度为对于长度为n的有序线性表，最坏情况只需比较的有序线性表，最坏情况只需比较log2n次。次。.例：例：有序表（有序表（18，20，25，34，48，62，74，85）用二分查找法查找用二分查找法查找74，所需要的比较次数为（），所需要的比较次数为（）A.1 B.2 C.3 D.4.第七节 排序技术 排序是指将一个无序序列整理成按值排序是指将一个无序序列整理成按值非递非递减顺序减顺序排列的有序序列。排列的有序序列。主要掌握排序的主要掌握排序的过程过程 重点掌握重点掌握排序的特点排序的特点 讲三类六种排序方法讲三类六种排序方法 交换类排序法交换类排序法 插入类排序法插入类排序法 选择类排序法选择类排序法.一、交换类排序方法(1)冒泡排序法：需要比较的次数为冒泡排序法：需要比较的次数为n(n-1)/2;(2)快速排序法：最坏情况快速排序法：最坏情况n(n-1)/2；最好情况最好情况nlog2n.（1）冒泡排序法基本过程：基本过程：首先从表头开始往后扫描线性表，在扫描过程中逐次首先从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若前面的元素大于后面的比较相邻两个元素的大小。若前面的元素大于后面的元素，则将它们交换。显然，在扫描过程中，不断地元素，则将它们交换。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到表的最后，这也是线性表中最大元素应的最大者换到表的最后，这也是线性表中最大元素应有的位置。有的位置。对剩下的线性表重复上述过程，直到第一个元素为止，对剩下的线性表重复上述过程，直到第一个元素为止，此时的线性表已经变为有序。此时的线性表已经变为有序。.举例：一个数组中的数据进行排序举例：一个数组中的数据进行排序原始数据：原始数据：5 1 7 3 1 6 9 4 2 8 6 第第1次：次：1 5 3 1 6 7 4 2 8 6 9第第2次：次：1 3 1 5 6 4 2 7 6 8 9 第第3次：次：1 1 3 5 4 2 6 6 7 8 9第第4次：次：1 1 3 4 2 5 6 6 7 8 9第第5次：次：1 1 3 2 4 5 6 6 7 8 9 第第6次：次：1 1 2 3 4 5 6 6 7 8 9总的比较次数总的比较次数:(n-1)+(n-2)+2+1 =(1+n-1)(n-1)/2 =n(n-1)/2总的时间复杂度总的时间复杂度O(n2).(2)快速排序基本思想：基本思想：从线性表中选取一个元素从线性表中选取一个元素T,将线性表后面小于将线性表后面小于T的元的元素移动到素移动到T的前面，而前面大于的前面，而前面大于T的元素移动到的元素移动到T的后的后面。这样，以面。这样，以T为分界线，将线性表分成了前后两个为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均小于子表，且前面子表中的所有元素均小于T，而后面子，而后面子表中的所有元素均大于表中的所有元素均大于T。如果对分割后的各子表再按上述原则进行分割，一直如果对分割后的各子表再按上述原则进行分割，一直继续下去，直到所有子表均为空，则此时的线性表变继续下去，直到所有子表均为空，则此时的线性表变成了有序表成了有序表.具体做法：具体做法：待排序列的下界为待排序列的下界为low，上界为，上界为high，枢轴元素，枢轴元素Rlow；变量；变量p=Rlow,i=low,high=j（1）从）从j所指的元素起，从右向左将元素与所指的元素起，从右向左将元素与p中的值比较，找第中的值比较，找第一个一个小于小于p的元素。如果没找到，的元素。如果没找到，j向先前移动；找到后，将该向先前移动；找到后，将该元素复制到元素复制到i所指的位置，所指的位置，i移动到移动到i+1（2）从）从i+1所指的元素起自左向右将元素与所指的元素起自左向右将元素与p比较，找第一个比较，找第一个大大于于p的元素。如果没有找到，的元素。如果没有找到，i继续向前移动；找到后，将该元继续向前移动；找到后，将该元素复制到素复制到j所指的位置。所指的位置。j向前移动到向前移动到j-1，重复，重复(1)（3）重复（）重复（2）（）（1）步，直到）步，直到i=j，找到了，找到了p的元素所在的正确的元素所在的正确位置，放入。完成了一次快速排序位置，放入。完成了一次快速排序（4）继续对枢轴元素按上述步骤操作。直到每次待排序元素只）继续对枢轴元素按上述步骤操作。直到每次待排序元素只有一个为止。有一个为止。.举例：对数据序列进行排序（第一个数作为枢轴元素）举例：对数据序列进行排序（第一个数作为枢轴元素）原始数据：原始数据：70 75 69 32 88 18 16 58 1:p=70 58 16 69 32 18 70 88 752:p=58 18 16 32 58 69 70 88 753:p=18 16 18 32 58 69 70 88 754:p=88 16 18 32 58 69 70 75 88快速排序在最坏情况下时间复杂性：快速排序在最坏情况下时间复杂性：n(n-1)/2最好情况为：最好情况为：nlog2n.二、插入类排序法(1)简单插入排序法：最坏情况需要简单插入排序法：最坏情况需要n(n-1)/2次比较次比较;(2)希尔排序法：最坏情况需要希尔排序法：最坏情况需要O(n1.5)次比较。次比较。.（1）简单插入排序基本思想：基本思想：假设第假设第1个是有序的个是有序的第第2个跟第个跟第1个比较，排到合适的位置个比较，排到合适的位置第第3个跟前两个比，排到合适的位置个跟前两个比，排到合适的位置第第i个跟前面的个跟前面的i-1个比较，排到合适的位置。直到第个比较，排到合适的位置。直到第n个个对于对于n个数据元素的序列而言，插入排序法的总的个数据元素的序列而言，插入排序法的总的排序趟数排序趟数为为n-1最坏情况下，元素之间的最坏情况下，元素之间的比较比较次数为次数为n(n-1)/2最好情况下（已经从小到大有序），元素直接的最好情况下（已经从小到大有序），元素直接的比较次数比较次数为为n-1.举例：对序列按插入法排序：举例：对序列按插入法排序：初始初始:(5)1 7 3 1 6 9 4 2 8 61：(1 5)7 3 1 6 9 4 2 8 62:(1 5 7)3 1 6 9 4 2 8 63:(1 3 5 7)1 6 9 4 2 8 64:(1 1 3 5 7)6 9 4 2 8 65:(1 1 3 5 6 7)9 4 2 8 66:(1 1 3 5 6 7 9)4 2 8 67:(1 1 3 4 5 6 7 9)2 8 68:(1 1 2 3 4 5 6 7 9)8 69:(1 1 2 3 4 5 6 7 8 9)610:(1 1 2 3 4 5 6 6 7 8 9)从从后后向向前前比比较较，找找到到小小于于等等于于的的数数.（2）希尔排序基本思想：基本思想：将整个无序序列分割成若干小的子序列分别进行插入将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：排序。子序列的分割方法如下：将相隔增量为将相隔增量为h=n/2k的元素构成一个子序列。在排序的元素构成一个子序列。在排序过程中，逐渐减小这个增量，最后当过程中，逐渐减小这个增量，最后当h=1时，进行一时，进行一次插入排序，完成排序。次插入排序，完成排序。.举例：下面举例：下面12个数的希尔排序的过程个数的希尔排序的过程k=1,h=6:7 19 24 13 31 8 82 18 44 63 5 29 7 18 24 13 5 8 82 19 44 63 31 29 h=37 18 24 13 5 8 82 19 44 63 31 297 5 8 13 18 24 63 19 29 82 31 44h=1结果：结果：5 7 8 13 18 19 24 29 31 44 63 82.三、选择排序法(1)简单选择排序法简单选择排序法,最坏情况：需要最坏情况：需要n(n-1)/2次比较次比较;(2)堆排序法，最坏情况：需要堆排序法，最坏情况：需要O(nlog2n)次次比较。比较。.（1）选择排序基本思想：基本思想：从第从第1个元素开始，扫描整个线性表，从中选出最小的个元素开始，扫描整个线性表，从中选出最小的元素，将它与第元素，将它与第1个元素交换（这是它应有的位置）；个元素交换（这是它应有的位置）；从第从第2个元素开始，向后扫描整个线性表，再选出最个元素开始，向后扫描整个线性表，再选出最小的元素与第小的元素与第2个交换个交换 对剩下的子表采用同样的方法，直到子表为空为止。对剩下的子表采用同样的方法，直到子表为空为止。.举例，用选择法排序下面的序列举例，用选择法排序下面的序列原始：原始：89 21 56 48 85 16 19 471：16 21 56 48 85 89 19 472：16 19 56 48 85 89 21 473：16 19 21 48 85 89 56 474：16 19 21 47 85 89 56 485：16 19 21 47 48 89 56 856：16 19 21 47 48 56 89 857：16 19 21 47 48 56 85 89对于对于n个元素的序列，选择排序的总的排序趟数是个元素的序列，选择排序的总的排序趟数是n-1.无论原始序列中的数据元素的排列如何，选择排序方法在无论原始序列中的数据元素的排列如何，选择排序方法在整个排序过程中所进行的比较次数都为整个排序过程中所进行的比较次数都为n*n-1)/2.(2)堆排序堆排序的特征：堆排序的特征：堆是一棵完全二叉树堆是一棵完全二叉树堆中的每一个非叶子结点的值均大于或等于它的两个堆中的每一个非叶子结点的值均大于或等于它的两个子结点子结点树根是堆树中的最大值树根是堆树中的最大值8553364730912412.堆排序的步骤堆排序的步骤1）初始建堆初始建堆：将参加排序的原始序列转换为一个堆：将参加排序的原始序列转换为一个堆 从根开始调整从根开始调整 找出此父结点的两个子结点的较大者与父结点比较，找出此父结点的两个子结点的较大者与父结点比较，若父结点小，则交换若父结点小，则交换 以交换后的子结点作为新的父结点，重复此步骤以交换后的子结点作为新的父结点，重复此步骤，直到没有子结点。，直到没有子结点。把原来的父结点的位置往前推一个位置，作为新的把原来的父结点的位置往前推一个位置，作为新的父结点，重新执行父结点，重新执行直到根为止直到根为止.排序序列为：排序序列为：80 13 6 88 27 75 42 69887569276804213136882775804269887513276804269807569276884213.2）实现堆排序）实现堆排序将堆的第一个元素（最大值）与堆的最后那个元素交将堆的第一个元素（最大值）与堆的最后那个元素交换位置。换位置。除最后一个元素外的其他元素重新调整为一个堆除最后一个元素外的其他元素重新调整为一个堆重复上面的两步，直到剩下根结点，排序结束重复上面的两步，直到剩下根结点，排序结束807569276134288697513276804288697513276428088.697513276428088694213276758088694213277568088642132775698088274213675698088274213697568088276136975428088276426975138088136426975278088.136426975278088132742697568088627426975138088132742697568088132742697568088.各种排序方法的比较分分 类类排序方法排序方法最坏所需要时间最坏所需要时间平均所需要时间平均所需要时间交换排序交换排序冒泡排序冒泡排序n*(n-1)/2O(n2)快速排序快速排序n*(n-1)/2O(nlog2n)插入排序插入排序简单插入简单插入n*(n-1)/2O(n2)希尔排序希尔排序O(n1.5)选择排序选择排序简单选择简单选择n*(n-1)/2O(n2)堆排序堆排序O(nlog2n).总 结总 结数据逻辑结构数据逻辑结构线性结构线性结构非线性结构非线性结构线性表线性表栈栈队列队列集合集合树树图图二叉树二叉树完全二叉树完全二叉树满二叉树满二叉树数据存储结构数据存储结构顺序顺序链式链式索引索引运算运算插入插入删除删除查找查找数数据据结结构构.1.数据的存储结构是指数据的存储结构是指A）数据所占的存储空间量）数据所占的存储空间量B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据评析评析：数据的逻辑结构是反映数据元素之间的逻辑关系；：数据的逻辑结构是反映数据元素之间的逻辑关系；数据的存储结构是指数据的逻辑结构在计算机存储空数据的存储结构是指数据的逻辑结构在计算机存储空间的存放形式。常用的存储结构有顺序、链式、索引间的存放形式。常用的存储结构有顺序、链式、索引等。等。答案答案：B习 题.2下列叙述中正确的是下列叙述中正确的是A）线性表是线性结构）线性表是线性结构B）栈与队列是非线性结构）栈与队列是非线性结构C）线性链表是非线性结构）线性链表是非线性结构D）二叉树是线性结构）二叉树是线性结构评析评析：线性表、栈和队列都是线性结构，树、二叉树、：线性表、栈和队列都是线性结构，树、二叉树、图是非线性结构图是非线性结构答案答案：A.3.下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是A）在队列中只能插入数据）在队列中只能插入数据B）在队列中只能删除数据）在队列中只能删除数据C）队列是先进先出的线性表）队列是先进先出的线性表D）队列是先进后出的线性表）队列是先进后出的线性表评析评析：队列是允许在一端（队尾）进行插入，而在另一：队列是允许在一端（队尾）进行插入，而在另一端（队头）进行删除的线性表。队列是端（队头）进行删除的线性表。队列是“先进先出先进先出（FIFO）”或或“后进后出（后进后出（LILO）”的线性表。的线性表。答案答案：C.4.下列关于栈的叙述中正确的是下列关于栈的叙述中正确的是A）在栈中只能插入数据）在栈中只能插入数据B）在栈中只能删除数据）在栈中只能删除数据C）栈是先进先出的线性表）栈是先进先出的线性表D）栈是先进后出的线性表）栈是先进后出的线性表评析评析：栈是限定在一端进行插入与删除的线性表，允许：栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶（插入与删除的一端称为栈顶（top），不允许插入与删），不允许插入与删除的另一端称为栈低（除的另一端称为栈低（bottom）。栈按照）。栈按照“先进后出先进后出（FILO）”或或“后进先出后进先出(LIFO)”组织数据，栈具有记组织数据，栈具有记忆作用。忆作用。答案答案：D.5.设有下列二叉树：设有下列二叉树：对此二叉树中序遍历的结果为对此二叉树中序遍历的结果为A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCA 评析评析：中序遍历是左根右；并且在遍历左右子树时，仍：中序遍历是左根右；并且在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。然先遍历左子树，然后访问根结点，最后遍历右子树。答案答案：B.6.对下列二叉树进行中序遍历的结果对下列二叉树进行中序遍历的结果 _ABCDEXFYZDBXEAYFZC.7.在深度为在深度为5 的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为A)32B)31C)16D)15 评析评析：在深度为：在深度为5的满二叉树中，叶子结点都位于第的满二叉树中，叶子结点都位于第5层，层，共有共有2(5-1)=16答案答案：C.8.对长度为对长度为n 的线性表进行顺序查找，在最坏情况下所的线性表进行顺序查找，在最坏情况下所需要的比较次数为需要的比较次数为A)n+1B)nC)(n+1)/2D)n/2 评析评析：对线性表进行顺序查找，最坏情况是指找的是最：对线性表进行顺序查找，最坏情况是指找的是最后一个元素或查找失败，此时需要和线性表中的所有元后一个元素或查找失败，此时需要和线性表中的所有元素都比较一次。素都比较一次。答案答案：B.9.设树设树 T 的度为的度为4，其中度为，其中度为1,2,3,4 的结点个数分别为的结点个数分别为4,2,1,1。则。则 T 中的叶子结点数为中的叶子结点数为A)8B)7C)6D)5 评析：评析：n0=n2+2n3+3n4+1=2+2*1+3*1+1=8总结点数：总结点数：x+4+2+1+1=x+8总结点数总结点数=总的子结点数总的子结点数+1=1*4+2*2+3*1+4*1+1=16 X+8=16;x=8答案答案：A.二、填空题1.对长度为对长度为n的有序线性表进行二分查找，需要的比较的有序线性表进行二分查找，需要的比较次数为（）次数为（）评析：对于长度为评析：对于长度为n的有序线性表，在最坏情况下，的有序线性表，在最坏情况下，二分查找只需要比较二分查找只需要比较log2n答案：答案：log2n.2.设一棵完全二叉树共有设一棵完全二叉树共有700个结点，则在该二叉树中个结点，则在该二叉树中有（）个叶子结点。有（）个叶子结点。评析：具有偶数个结点的完全二叉树有评析：具有偶数个结