数据结构复习资料.ppt

《数据结构复习资料.ppt》由会员分享，可在线阅读，更多相关《数据结构复习资料.ppt（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构教材教材 李春葆李春葆 数据结构教程数据结构教程 清华大学出版社清华大学出版社 严蔚敏严蔚敏 数据结构数据结构 清华大学出版社清华大学出版社参考书参考书 李春葆李春葆数据结构习题与解析数据结构习题与解析(第第2版或第版或第3版版)清华大学出版社清华大学出版社概述概述模块模块1：线性表：线性表模块模块2：树型结构：树型结构模块模块3：图型结构：图型结构模块模块4：其他：其他1.1.数据结构的定义数据结构的定义 数据数据数据元素数据元素数据项数据项数据结构是指数据结构是指数据数据以及相互之间的以及相互之间的联系（或联系（或关系）关系）。包括：。包括：（1）数据的逻辑结构。）数据的逻

2、辑结构。（2）数据的存储结构（物理结构）。）数据的存储结构（物理结构）。（3）施加在该数据上的运算。）施加在该数据上的运算。概述概述 数数据据的的逻逻辑辑结结构构是是从从逻逻辑辑关关系系上上描描述述数数据据，它它与数据的存储无关，是与数据的存储无关，是独立于计算机独立于计算机的。的。数数据据的的存存储储结结构构是是逻逻辑辑结结构构用用计计算算机机语语言言的的实实现（亦称为映象），它是现（亦称为映象），它是依赖于计算机语言依赖于计算机语言的。的。数数据据的的运运算算是是定定义义在在数数据据的的逻逻辑辑结结构构上上的的，每每种种逻逻辑辑结结构构都都有有一一组组相相应应的的运运算算。但但运运算算的的

3、实实现现与与数据的存储结构有关。数据的存储结构有关。程序数据结构算法程序数据结构算法概述概述（1）线性结构）线性结构（2）树形结构）树形结构（3）图形结构）图形结构概述概述逻辑结构主要有三大类：逻辑结构主要有三大类：存储结构分为如下四种：存储结构分为如下四种：（1）顺序存储方法）顺序存储方法（2）链式存储方法）链式存储方法（3）索引存储方法）索引存储方法（4）散列存储方法）散列存储方法概述概述2.算法算法 算法是对特定问题求解步骤的一种描算法是对特定问题求解步骤的一种描述，它是指令的述，它是指令的有限序列有限序列。概述概述算法的五个重要的特性算法的五个重要的特性：（1）有穷性）有穷性（2）确定

4、性）确定性（3）可行性）可行性（4）有输入）有输入（5）有输出）有输出概述概述算算法法的的时时间间复复杂杂度度：是是指指其其基基本本运运算算在在算算法中重复执行的次数。法中重复执行的次数。算算法法中中基基本本运运算算次次数数T(n)是是问问题题规规模模n的的某某个函数个函数f(n)，记作：记作：T(n)=O(f(n)记号记号“O”读作读作“大大O”，它表示随问题规它表示随问题规模模n的增大算法执行时间的增长率和的增大算法执行时间的增长率和f(n)的增长的增长率相同。率相同。概述概述例例分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1;while(ilchild)+f(b-rchi

5、ld)+1bNULL概述概述递归算法设计递归算法设计对对原原问问题题f(s)进进行行分分析析，假假设设出出合合理理的的“较小问题较小问题”f(s);假假设设f(s)是是可可解解的的，在在此此基基础础上上确确定定f(s)的解，即给出的解，即给出f(s)与与f(s)之间的关系；之间的关系；确定一个特定情况（如确定一个特定情况（如f(1)或或f(0)）的解，的解，由此作为递归出口由此作为递归出口.概述概述bb-rchildb-lchild假设出合理的假设出合理的“较小问题较小问题”：假设左右子树的结点个数可求假设左右子树的结点个数可求求出求出f(s)与与f(s)之间的关系：之间的关系：f(b)=f(

6、b-lchild)+f(b-rchild)+1确定递归出口：确定递归出口：f(NULL)=0概述概述intf(BTNode*b)if(b=NULL)return(0);elsereturn(f(b-lchild)+f(b-rchild)+1);求解算法：求解算法：概述概述例例设计求设计求f(n)=1+2+.+n的递归算法的递归算法解：解：f(n)为前为前n项之和，则项之和，则f(n-1)=1+2+.+(n-1)假设假设f(n-1)可求，则可求，则f(n)=f(n-1)+n，所以：所以：f(n)=1当当n=1f(n)=f(n-1)+n当当n1对应的递归算法如下：对应的递归算法如下：intf(in

7、tn)if(n=1)return(1);elsereturn(f(n-1)+n);1.1.一般线性表一般线性表 线性表：具有线性表：具有相同特性相同特性的数据元素的一个的数据元素的一个有限序列有限序列。不是集合。不是集合。模块模块1 1：线性结构：线性结构逻辑结构逻辑结构（1）顺序表）顺序表typedefstructElemTypeelemMaxSize;/*存放顺序表元素存放顺序表元素*/intlength;/*存放顺序表的长度存放顺序表的长度*/SqList;存储结构之一存储结构之一模块模块1 1：线性：线性结构结构顺序表基本运算的实现顺序表基本运算的实现 插入数据元素算法：元素移动的次数

8、不仅与表插入数据元素算法：元素移动的次数不仅与表长长n有关有关；插入一个元素时所需移动元素的平均次数；插入一个元素时所需移动元素的平均次数n2。平均时间复杂度为平均时间复杂度为O(n)。模块模块1 1：线性：线性结构结构删除数据元素算法删除数据元素算法:元素移动的次数也与元素移动的次数也与表长表长n有关有关。删除一个元素时所需移动元素的。删除一个元素时所需移动元素的平均次数为平均次数为(n-1)/2。删除算法的平均时间复杂删除算法的平均时间复杂度为度为O(n)。模块模块1 1：线性结构：线性结构（2）链表）链表定义单链表结点类型定义单链表结点类型:typedefstructLNodeElemT

9、ypedata;structLNode*next;/*指向后继结点指向后继结点*/LinkList;存储结构之二存储结构之二模块模块1 1：线性结构：线性结构定义双链表结点类型定义双链表结点类型:typedefstructDNodeElemTypedata;structDNode*prior;/*指向前驱结点指向前驱结点*/structDNode*next;/*指向后继结点指向后继结点*/DLinkList;模块模块1 1：线性结构：线性结构单链表基本运算的实现单链表基本运算的实现 重点：（重点：（1 1）头插法建表和尾插法建表算法，头插法建表和尾插法建表算法，它是很多算法设计的基础；（它是很

10、多算法设计的基础；（2 2）查找、插入）查找、插入和删除操作。和删除操作。模块模块1 1：线性结构：线性结构 头插法建表头插法建表该方法从一个空表开始该方法从一个空表开始,读取字符数组读取字符数组a中的字中的字符符,生成新结点生成新结点,将读取的数据存放到新结点的数将读取的数据存放到新结点的数据域中据域中,然后将新结点插入到当前链表的表头上然后将新结点插入到当前链表的表头上,直到结束为止。直到结束为止。采用头插法建表的算法如下采用头插法建表的算法如下:模块模块1 1：线性结构：线性结构voidCreateListF(LinkList*&L,ElemTypea,intn)LinkList*s;i

11、nti;L=(LinkList*)malloc(sizeof(LinkList);/*创创建建头头结点结点*/L-next=NULL;for(i=0;idata=ai;s-next=L-next;/*将将*s插在原开始结点之前插在原开始结点之前,头结点之后头结点之后*/L-next=s;模块模块1 1：线性结构：线性结构adc bi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步:建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点,插入到头结点之后插入到头结点之后第第3

12、3步步:i:i1,1,新建新建d d结点结点,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点,插入到头结点之后插入到头结点之后 尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单,但生成的链表但生成的链表中结点的次序和原数组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上,为此必须增加一为此必须增加一

13、个尾指针个尾指针r,r,使其始终指向当前链表的尾结点。使其始终指向当前链表的尾结点。采用尾插法建表的算法如下采用尾插法建表的算法如下:模块模块1 1：线性结构：线性结构voidCreateListR(LinkList*&L,ElemTypea,intn)LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList);/*创建头结点创建头结点*/L-next=NULL;r=L;/*r始终指向终端结点始终指向终端结点,开始时指向头结点开始时指向头结点*/for(i=0;idata=ai;r-next=s;/*将将*s插入插入*r之后之后*/r=s;r

14、-next=NULL;/*终端结点终端结点next域置为域置为NULL*/adc bi=0 i=1 i=2 i=3head头头结点结点adcb b采用尾插法建立单链表的过程采用尾插法建立单链表的过程模块模块1 1：线性结构：线性结构例例设设C=a1,b1,a2,b2,an,bn为为一一线线性性表表,采采用用带带头头结结点点的的hc单单链链表表存存放放,编编写写一一个个算算法法,将其拆分为两个线性表将其拆分为两个线性表,使得使得:A=a1,a2,an,B=b1,b2,bn模块模块1 1：线性结构：线性结构解解:设设拆拆分分后后的的两两个个线线性性表表都都用用带带头头结结点点的的单单链链表表存放。

15、存放。先先建建立立两两个个头头结结点点*ha和和*hb,它它们们用用于于存存放放拆拆分分后后的的线线性性表表A和和B,ra和和rb分分别别指指向向这这两两个个单单链链表表的的表表尾尾,用用p指指针针扫扫描描单单链链表表hc,将将当当前前结结点点*p链链到到ha未未尾尾,p沿沿next域域下下移移一一个个结结点点,若若不不为为空空,则则当当前前结结点点*p链链到到hb未未尾尾,p沿沿next域域下下移移一一个个结结点点,如如此此这这样样,直直到到p为为空空。最后将两个尾结点的最后将两个尾结点的next域置空。域置空。对应算法如下对应算法如下:模块模块1 1：线性结构：线性结构voidfun(Li

16、nkList*hc,LinkList*&ha,LinkList*&hb)LinkList*p=hc-next,*ra,*rb;ha=hc;/*ha的头结点利用的头结点利用hc的头结点的头结点*/ra=ha;/*ra始终指向始终指向ha的末尾结点的末尾结点*/hb=(LinkList*)malloc(sizeof(LinkList);/*创创建建hb头头结结点点*/rb=hb;/*rb始终指向始终指向hb的末尾结点的末尾结点*/模块模块1 1：线性结构：线性结构while(p!=NULL)ra-next=p;ra=p;/*将将*p链到链到ha单链表未尾单链表未尾*/p=p-next;rb-nex

17、t=p;rb=p;/*将将*p链到链到hb单链表未尾单链表未尾*/p=p-next;ra-next=rb-next=NULL;/*两个尾结点的两个尾结点的next域置空域置空*/模块模块1 1：线性结构：线性结构例例已已知知线线性性表表元元素素递递增增有有序序，并并以以带带头头结结点点的的单单链链表表作作存存储储结结构构，设设计计一一个个高高效效算算法法，删删除除表表中中所所有有值值大大于于mink且且小小于于maxk的的元元素素（若若表表中中存存在这样的元素）。并分析所写算法的时间复杂度。在这样的元素）。并分析所写算法的时间复杂度。模块模块1 1：线性结构：线性结构解解：先先在在单单链链表表

18、中中找找到到其其data值值则则好好大大于于mink的的结结点点*p，其其前前驱驱结结点点为为*pre。继继续续沿沿next链链查查找找其其值值大大于于maxk的的结结点点，在在这这个个过过程程中中删删除除*p结结点。算法如下：点。算法如下：voiddelnode(SNode*h,ElemTypemaxk,ElemTypemink)SNode*p,*pre;if(maxk=mink)pre=h;p=pre-next;模块模块1 1：线性结构：线性结构while(p!=NULL&p-datanext;while(p!=NULL&p-datanext=p-next;free(p);p=pre-ne

19、xt;模块模块1 1：线性结构：线性结构双链表基本运算的实现双链表基本运算的实现 重点：插入和删除结点的算法。重点：插入和删除结点的算法。模块模块1 1：线性结构：线性结构循环链表基本运算的实现循环链表基本运算的实现 重点：判断最后一个结点。重点：判断最后一个结点。模块模块1 1：线性结构：线性结构例例某某线线性性表表最最常常用用的的操操作作是是在在最最后后一一个个结结点点之之后后插插入入一一个个结结点点或或删删除除第第一一个个结结点点，故故采采用用存存储方式最节省运算时间。储方式最节省运算时间。A.单链表单链表B.仅有头结点的单循环链表仅有头结点的单循环链表C.双链表双链表D.仅有尾指针的单

20、循环链表仅有尾指针的单循环链表模块模块1 1：线性结构：线性结构例例设计一个算法在单链表中查找元素值为设计一个算法在单链表中查找元素值为e的的结点序号的算法结点序号的算法LocateElem(L,e)。思路：在单链表思路：在单链表L中从头开始找第中从头开始找第1个值域与个值域与e相等的结点相等的结点,若存在这样的结点若存在这样的结点,则返回位置则返回位置,否则否则返回返回0。intLocateElem(LinkList*L,ElemTypee)LinkList*p=L-next;intn=1;while(p!=NULL&p-data!=e)p=p-next;n+;if(p=NULL)retur

21、n(0);elsereturn(n);解：解：本题答案为本题答案为D。在有尾指针在有尾指针r的单循环链表中的单循环链表中在在最最后后一一个个结结点点之之后后插插入入结结点点*s的的操操作作是是：s-next=r-next;r-next=s;r=s。删删除除第第一一个个结结点点的的操操作作是是：p=r-next;r-next=p-next;free(p)。其时间复杂度均为其时间复杂度均为O(1)。模块模块1 1：线性结构：线性结构2.2.栈栈(1)栈的定义栈的定义栈是一种栈是一种先进后出先进后出表表栈的基本运算栈的基本运算:进栈，出栈。进栈，出栈。逻辑结构逻辑结构模块模块1 1：线性结构：线性结

22、构例例已已知知一一个个栈栈的的进进栈栈序序列列是是1,2,3,n,其其输输出出序序列列是是p1,p2,pn,若若p1=n,则则pi的值的值。(A)i(B)n-i(C)n-i+1(D)不确定不确定答答:当当p1=n时时,输出序列必是输出序列必是n,n-1,3,2,1,则有则有:p2=n-1,p3=n-2,pn=1推断出推断出pi=n-i+1,所以本题答案为所以本题答案为C。例例设设n个个元元素素进进栈栈序序列列是是1,2,3,n,其其输输出出序序列列是是p1,p2,pn,若若p1=3,则则p2的值的值。(A)一定是一定是2(B)一定是一定是1(C)不可能是不可能是1(D)以上都不对以上都不对答答

23、:当当p1=3时时,说说明明1,2,3先先进进栈栈,立立即即出出栈栈3,然然后后可可能能出出栈栈,即即为为2,也也可可能能4或或后后面面的的元元素素进进栈栈,再再出出栈栈。因因此此,p2可可能能是是2,也也可可能能是是4,n,但但一一定定不不能能是是1。所所以本题答案为以本题答案为C。模块模块1 1：线性结构：线性结构（2）顺序栈）顺序栈typedefstructElemTypeelemMaxSize;inttop;/*栈指针栈指针*/SqStack;存储结构之一存储结构之一模块模块1 1：线性结构：线性结构栈栈空空条件条件:s.top=-1栈满条件栈满条件:s.top=MaxSize-1进栈

24、进栈:top+;s.datas.top=e;出栈出栈:e=s.datas.top;s.top;顺序栈的顺序栈的4要素要素:模块模块1 1：线性结构：线性结构（3）链栈）链栈 typedefstructlinknodeElemTypedata;/*数据域数据域*/structlinknode*next;/*指针域指针域*/LiStack;存储结构之二存储结构之二模块模块1 1：线性结构：线性结构带头结点的单链表来实现带头结点的单链表来实现(也可不带头结点也可不带头结点)栈空栈空条件条件:s-next=NULL栈满条件栈满条件:?模块模块1 1：线性结构：线性结构3.3.队列队列 (1)队列的定义

25、队列的定义队列是一种队列是一种先进先出先进先出表。表。队列的基本运算队列的基本运算:进队进队,出队出队逻辑结构逻辑结构模块模块1 1：线性结构：线性结构（2）顺序队顺序队typedefstructElemTypeelemMaxSize；intfront,rear；/*队首和队尾指针队首和队尾指针*/SqQueue；存储结构之一存储结构之一模块模块1 1：线性结构：线性结构队空队空:q.front=q.rear队满队满:(q.rear+1)%MaxSize=q.front进队进队:q.rear=(q.rear+1)MaxSize;q.dataq.rear=e;出出队队:q.front=(q.fr

26、ont+1)MaxSize;e=q.dataq.front;环形队列的环形队列的4要素要素:模块模块1 1：线性结构：线性结构（3）链队）链队structqnode/*数据数据结结点点*/ElemTypedata;structqnode*next;QNode;typedefstruct/*头结头结点点*/QNode*front;QNode*rear;LiQueue;存储结构之二存储结构之二模块模块1 1：线性结构：线性结构（2）顺序串）顺序串 （3）链串）链串 （4）串串的模式匹配算法（的模式匹配算法（不作要求不作要求）4.4.串串（1）串的定义）串的定义 串、子串、串相等、空串、空格串串、子

27、串、串相等、空串、空格串模块模块1 1：线性结构：线性结构5.5.数组和稀疏矩阵数组和稀疏矩阵(1)数组的定义数组的定义相同类型数据元素、有限序列相同类型数据元素、有限序列模块模块1 1：线性结构：线性结构(2)数组的存储结构数组的存储结构 以行序为主序以行序为主序:LOC(ai,j)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*k以列序为主序以列序为主序LOC(ai,j)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k以数组以数组Ac1.d1,c2.d2为为例例模块模块1 1：线性结构：线性结构（3）特殊矩阵的压缩存储）特殊矩阵的压缩存

28、储对称矩阵对称矩阵若一个若一个n阶方阵阶方阵Ann中的元素满足中的元素满足ai,j=aj,i（0i，jn-1），），则称其为则称其为n阶对称矩阵。阶对称矩阵。A0.n-10.n-1B0.n(n+1)/2i(i+1)/2+j当当ij时时k=j(j+1)/2+i当当ij时时模块模块1 1：线性结构：线性结构三角矩阵三角矩阵 采用类似的压缩方法采用类似的压缩方法.模块模块1 1：线性结构：线性结构（4）稀疏矩阵）稀疏矩阵存储结构：存储结构：三元组表示三元组表示十字链表表示十字链表表示各种表示的基本思路。各种表示的基本思路。非零非零元素远小于元素总数。元素远小于元素总数。模块模块1 1：线性结构：线性

29、结构一个广义表中所含元素的个数称为它的长度一个广义表中所含元素的个数称为它的长度.6.广义表广义表GL=(a,(a),(a,b,c,d),()长度为长度为4。模块模块1 1：线性结构：线性结构一个广义表中括号嵌套的最大次数为它一个广义表中括号嵌套的最大次数为它的深度的深度.GL=(a,(a),(a,b,c,d),()深度为深度为2。模块模块1 1：线性结构：线性结构表的第一个元素表的第一个元素a1为广义表为广义表GL的表头，的表头，其余部分其余部分(a2，ai，ai+1，an)为为GL的表的表尾尾.GL=(a,(a),(a,b,c,d),()表头为表头为a，表尾为表尾为(a),(a,b,c,d

30、),()模块模块1 1：线性结构：线性结构模块模块2：树形结构：树形结构 （1）树的定义）树的定义递归定义递归定义适合于表示层次结构的数据适合于表示层次结构的数据1.1.树树（2）树的表示法）树的表示法(逻辑表示方法逻辑表示方法)树形表示法树形表示法文氏图表示法文氏图表示法凹入表示法凹入表示法括号表示法括号表示法模块模块2：树形结构：树形结构 （3）树的遍历）树的遍历先根遍历算法先根遍历算法后根遍历算法后根遍历算法模块模块2：树形结构：树形结构 （4）树和二叉树的相互转换）树和二叉树的相互转换树树二叉树二叉树二叉二叉树树树树模块模块2：树形结构：树形结构 2.二叉树二叉树 （1）二叉树的定义）

31、二叉树的定义根、左子树、右子树根、左子树、右子树完全二叉树完全二叉树,满二叉树的定义满二叉树的定义模块模块2：树形结构：树形结构 性性质质1非非空空二二叉叉树树上上叶叶结结点点数数等等于于双双分分支支结结点点数数加加1。即。即n0=n2+1.性性质质2非非空空二二叉叉树树上上第第i层层上上至至多多有有2i-1个个结结点点（i1）。）。（2）二叉树性质）二叉树性质模块模块2：树形结构：树形结构 性质性质3高度为高度为h的二叉树至多有的二叉树至多有2h-1个结点个结点（h1）。性质性质4完全二叉树的性质完全二叉树的性质。性性质质5具具有有n个个（n0）结结点点的的完完全全二二叉叉树树的高度为的高度

32、为 log2n+1 或或 log2n+1。（2）二叉树性质）二叉树性质模块模块2：树形结构：树形结构 例例将将一一棵棵有有99个个结结点点的的完完全全二二叉叉树树从从根根这这一一层层开开始始，每每一一层层从从左左到到右右依依次次对对结结点点进进行行编编号号，根根结结点点的的编编号号为为1，则则编编号号为为49的的结结点点的的右右孩孩子子编编号号为为。A.98B.99C.50D.不存在不存在答：答：D模块模块2：树形结构：树形结构 例例深度为深度为5的二叉树至多有的二叉树至多有个结点。个结点。A.16B.32C.31D.10答：相同满度时满二叉树结点最多，答：相同满度时满二叉树结点最多，h=5的

33、满二叉树结点个数的满二叉树结点个数=25-1=31。C。模块模块2：树形结构：树形结构 （3）二叉树存储结构）二叉树存储结构 二叉树的顺序存储结构二叉树的顺序存储结构模块模块2：树形结构：树形结构 ABCDEF1234567891011121314ABCDEFi2i2i+1左左孩子孩子右孩子右孩子二叉链存储结构二叉链存储结构typedefstructnodeElemTypedata;/*数据元素数据元素*/structnode*lchild;/*指向左孩子指向左孩子*/structnode*rchild;/*指向右孩子指向右孩子*/BTNode;ABC左左孩子孩子右孩子右孩子（4）二叉树的遍历

34、）二叉树的遍历 先序遍历先序遍历中序遍历中序遍历后序遍历后序遍历层次遍历层次遍历通常用递归算法实现通常用递归算法实现通常用队列来实现通常用队列来实现模块模块2：树形结构：树形结构 例例假假设设二二叉叉树树采采用用二二叉叉链链存存储储结结构构存存储储,试试设设计计一一个算法个算法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。解解：输输出出一一棵棵二二叉叉树树的的所所有有叶叶子子结结点点的的递递归归模模型型f()如下：如下：f(b)：不做任何事件不做任何事件若若b=NULLf(b)：输出输出*b结点的结点的data域域若若*b为叶子结点为叶子结点f(b)：f(b-lchil

35、d);f(b-rchild)其他情况其他情况模块模块2：树形结构：树形结构 voidDispLeaf(BTNode*b)if(b!=NULL)if(b-lchild=NULL&b-rchild=NULL)printf(%c,b-data);DispLeaf(b-lchild);DispLeaf(b-rchild);模块模块2：树形结构：树形结构 先序遍历先序遍历思想思想例例试试设设计计判判断断两两棵棵二二叉叉树树是是否否相相似似的的算算法法，所所谓谓二二叉叉树树t1和和t2是是相相似似的的指指的的是是t1和和t2都都是是空空的的二二叉叉树树；或或者者t1和和t2的的根根结结点点是是相相似似的的

36、，t1的的左左子子树树和和t2的的左左子子树树是是相相似似的的且且t1的的右右子子树树与与t2的右子树是相似的。的右子树是相似的。模块模块2：树形结构：树形结构 解解 本题的递归模型如下：本题的递归模型如下：true若若t1=t2=NULLf(t1,t2)=false若若t1、t2之一为之一为NULL,另一不为另一不为NULLf(t1-lchild,t2-lchild)&f(t1-rchild,t2-rchild)其他情况其他情况对应的算法如下：对应的算法如下：模块模块2：树形结构：树形结构 intlike(BTNode*b1,BTNode*b2)intlike1,like2;if(b1=NU

37、LL&b2=NULL)return1;elseif(b1=NULL|b2=NULL)return0;elselike1=like(b1-lchild,b2-lchild);like2=like(b1-rchild,b2-rchild);return(like1&like2);模块模块2：树形结构：树形结构 后序遍历后序遍历思想思想例例 设计一个算法求二叉树的所有结点个数。设计一个算法求二叉树的所有结点个数。解：解：对应的算法如下：对应的算法如下：intnodenum(BTNode*bt)if(bt!=NULL)return(nodenum(bt-lchild)+nodenum(bt-lchil

38、d)+1);elsereturn(0);模块模块2：树形结构：树形结构 后序遍历后序遍历思想思想例例设计一个算法释放一棵二叉树设计一个算法释放一棵二叉树bt的的所有结点。所有结点。解：算法如下：解：算法如下：voidrelease(BSTNode*&bt)if(bt!=NULL)release(bt-lchild);release(bt-rchild);free(bt);模块模块2：树形结构：树形结构 后序遍历后序遍历思想思想（5）线索二叉树）线索二叉树 共有共有2n-(n-1)=n+1个空链域个空链域线索化线索化模块模块2：树形结构：树形结构 线索化与某种遍历方式有关线索化与某种遍历方式有关

39、3.哈夫曼树哈夫曼树（1）哈夫曼树的定义哈夫曼树的定义WPL最小，没有单分支结点即最小，没有单分支结点即n1=0模块模块2：树形结构：树形结构 （2）哈夫曼树的构造过程）哈夫曼树的构造过程（3）哈夫曼编码的构造过程）哈夫曼编码的构造过程模块模块2：树形结构：树形结构 顶点的度、入度和出度顶点的度、入度和出度完全图完全图子图子图路径和路径长度路径和路径长度连通、连通图和连通分量连通、连通图和连通分量强连通图和强连通分量强连通图和强连通分量权和网权和网 模块模块3：图形结构：图形结构（1）图的基本概念）图的基本概念（2）图的存储结构）图的存储结构邻接矩阵存储方法邻接矩阵存储方法 掌握两种存储方法的

40、优缺点，同一种功掌握两种存储方法的优缺点，同一种功能在不同存储结构上的实现算法。能在不同存储结构上的实现算法。邻接表存储方法邻接表存储方法模块模块3：图形结构：图形结构（3）图的遍历）图的遍历深度优先搜索遍历深度优先搜索遍历 离离初始点越远越优先访问。初始点越远越优先访问。1267354访问序列：访问序列：1，2，3，4，5，6，7模块模块3：图形结构：图形结构voidDFS(ALGraph*G,intv)ArcNode*p;Visitedv=1;/*置已访问标记置已访问标记*/printf(%d,v);/*输出被访问顶点的编号输出被访问顶点的编号*/p=G-adjlistv.firstarc

41、;while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);p=p-nextarc;模块模块3：图形结构：图形结构1267354广度优先搜索遍历广度优先搜索遍历 离离初始点越近越优先访问。初始点越近越优先访问。访问序列：访问序列：1，2，6，7，3，5，4模块模块3：图形结构：图形结构voidBFS(ALGraph*G,intv)ArcNode*p;intqueueMAXV,front=0,rear=0;intvisitedMAXV;intw,i;for(i=0;in;i+)visitedi=0;printf(%2d,v);visitedv=1;/*

42、置已访问标记置已访问标记*/rear=(rear+1)%MAXV;queuerear=v;/*v进队进队*/模块模块3：图形结构：图形结构while(front!=rear)/*若队列不空时循环若队列不空时循环*/front=(front+1)%MAXV;w=queuefront;/*出队并赋给出队并赋给w*/p=G-adjlistw.firstarc;while(p!=NULL)if(visitedp-adjvex=0)printf(%2d,p-adjvex);visitedp-adjvex=1;rear=(rear+1)%MAXV;queuerear=p-adjvex;p=p-nextar

43、c;模块模块3：图形结构：图形结构例例试以邻接表为存储结构，分别写出基于试以邻接表为存储结构，分别写出基于DFS和和BPS遍历的算法来判别顶点遍历的算法来判别顶点i和顶点和顶点j(ij)之间是否之间是否有路径。有路径。解：先置全局变量解：先置全局变量visited为为0，然后从顶点，然后从顶点i开开始进行某种遍历，遍历之后，若始进行某种遍历，遍历之后，若visitedj=0，说明说明顶点顶点i与顶点与顶点j之间没有路径；否则说明它们之间存之间没有路径；否则说明它们之间存在路径。在路径。模块模块3：图形结构：图形结构基于基于DFS遍历的算法如下：遍历的算法如下：intvisitedMaxVert

44、exNum;intDFSTrave(ALGraph*G，inti，intj)intk;for(k=0;kn;k+)visitedk=0;DFS(G，i);/从顶点从顶点i开始进行深度优先遍历开始进行深度优先遍历if(visitedj=0)return0;elsereturn1;模块模块3：图形结构：图形结构基于基于BFS遍历的算法如下：遍历的算法如下：intvisitedMaxVertexNum;intDFSTrave(ALGraph*G，inti，intj)intk;for(k=0;kn;k+)visitedk=0;BFS(G，i);/从顶点从顶点i开始进行广度优先遍历开始进行广度优先遍历i

45、f(visitedj=0)return0;elsereturn1;模块模块3：图形结构：图形结构（4）最小生成树）最小生成树普里姆算法普里姆算法给定起始点；给定起始点；算法过程；算法过程；O(n2)模块模块3：图形结构：图形结构克鲁斯卡尔算法克鲁斯卡尔算法不给定起始点；不给定起始点；算法过程；算法过程；O(elog2e)模块模块3：图形结构：图形结构（5）最短路径）最短路径狄克斯特拉算法过程狄克斯特拉算法过程弗洛伊德算法过程弗洛伊德算法过程模块模块3：图形结构：图形结构（6）拓扑排序和关键路径）拓扑排序和关键路径拓扑排序算法拓扑排序算法求关键路径的过程求关键路径的过程模块模块3：图形结构：图形

46、结构源源点点-汇点汇点源点的入度为源点的入度为0 0，汇点的出度为，汇点的出度为（1）线性表的查找）线性表的查找模块模块4：其他：其他1.1.查找查找在顺序表上进行。方法有：在顺序表上进行。方法有：顺序查找顺序查找（过程和算法）（过程和算法）二分查找二分查找（过程和算法）（过程和算法）分块查找分块查找(过程过程)（2）树表的查找树表的查找二叉排序树二叉排序树定义定义查找（过程和算法）查找（过程和算法）插入和删除（过程）插入和删除（过程）与与堆的堆的区别区别模块模块4：其他：其他性质：二叉排序树的中序序列是一个有序序列性质：二叉排序树的中序序列是一个有序序列平衡二叉树平衡二叉树定义定义查找（过程

47、和算法）查找（过程和算法）调整（过程）调整（过程）模块模块4：其他：其他（3）哈希表查找哈希表查找哈希函数哈希函数主要有除留余数法。主要有除留余数法。哈希冲突解决方法哈希冲突解决方法主要有线性探查法、拉链法主要有线性探查法、拉链法模块模块4：其他：其他2.2.内排序内排序内排序内排序 插入排序插入排序（1）直接插入排序）直接插入排序（2）希尔排序）希尔排序模块模块4：其他：其他交换排序交换排序（1）冒泡排序）冒泡排序（2）快速排序）快速排序选择排序选择排序（1）直接选择排序）直接选择排序（2）堆排序）堆排序归并排序归并排序基数排序基数排序例例在在待待排排序序的的元元素素序序列列基基本本有有序序

48、的的前前提提下下，效率最高的排序方法是效率最高的排序方法是。A.插入排序插入排序B.选择排序选择排序C.快速排序快速排序D.归并排序归并排序解解插插入入排排序序是是将将待待排排序序的的记记录录插插入入到到前前面面已已排排好好序序的的子子区区间间中中，即即考考虑虑已已排排好好序序的的子子区区间间。本题答案为本题答案为A。例例快快速速排排序序在在最最坏坏情情况况下下时时间间复复杂杂度度是是O(n2)，比比的性能差。的性能差。A.堆排序堆排序B.冒泡排序冒泡排序C.直接选择排序直接选择排序D.直接插入排序直接插入排序解解A。强调各种排序方法的比较强调各种排序方法的比较是否需要比较是否需要比较排序方法的区别排序方法的区别时间复杂度时间复杂度空间复杂度空间复杂度3.外排序外排序（1 1）外排序的基本步骤）外排序的基本步骤产生初始归并段产生初始归并段归并归并模块模块4：其他：其他（2）磁盘排序）磁盘排序利用选择置换算法产生初始归并段利用选择置换算法产生初始归并段利用最佳归并树进行归并，其中用败者利用最佳归并树进行归并，其中用败者树产生最小记录树产生最小记录模块模块4：其他：其他4.文件文件文件的特点文件的特点各种类型的文件组织结构各种类型的文件组织结构模块模块4：其他：其他考试题型考试题型总分总分75分分单项选择题单项选择题20分分问答题问答题30分分算法设计题算法设计题25分分