《数据结构复习题.ppt》由会员分享，可在线阅读，更多相关《数据结构复习题.ppt（136页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京化工大学数据北京化工大学数据结构构课程教学程教学课件件江志英江志英信息学院计算机系jiangzy总 复 习数据结构数据结构概论数据结构概论数据结构数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科数据结构是对数据元素之间的逻辑关系、数据的存储方式以及对数据的操作的抽象描述。抽象数据类型(Abstract Data Type 简称ADT)ADT：是指一个数学模型以及定义在此数学模型上的一组操作。数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装：将实体的外部
2、特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。ADT的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D 是数据对象；S 是 D 上的关系集；P 是对 D 的基本操作集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名算法和算法分析算法：是为了解决某类问题而规定的一个有限长的操作序列。复杂度对度量值的阶的评估。设某函数f(x)，若存在另一函数g(x)，满足当x趋近于无穷时，limf(x)/g(x)趋
3、近于一个非的常数，则称f(x)的度为O(g(x)。算法复杂度一般分为时间复杂度和空间复杂度。习题判断题（1）数据项是数据基本单位（）（2）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（）（3）数据的物理结构是指数据在计算机内实际的存储形式（）（1）错误错误（2）对对（3）对对 习题选择题（1）算法的计算量的大小称为计算的 .a)现实性 b)难度 c)复杂性 d)效率（2）数据结构被形式定义为（D，S），其中D 是 的有限集合，S 是D 上的 有限集合。a)算法 b)数据元素 c)数据操作 d)逻辑结构 e)操作f)映象 g)存储 h)关系（3）在数据结构中，从逻辑上可以把
4、数据结构分成 。a)动态结构和静态结构 b)紧凑结构和非紧凑结构 c)线性结构和非线性结构 d)内部结构和非内部结构（4）算法的时间复杂度取决于 .a)问题的规模 b)待处理数据的初态 c)问题的规模和待处理数据的初态 习题选择题（1）算法的计算量的大小称为计算的 c 。a)现实性 b)难度 c)复杂性 d)效率（2）数据结构被形式定义为（D，S），其中D 是 b 的有限集合，S 是D 上的 h 有限集合。a)算法 b)数据元素 c)数据操作 d)逻辑结构 e)操作f)映象 g)存储 h)关系（3）在数据结构中，从逻辑上可以把数据结构分成 c 。a)动态结构和静态结构 b)紧凑结构和非紧凑结构
5、 c)线性结构和非线性结构 d)内部结构和非内部结构（4）算法的时间复杂度取决于 a 。a)问题的规模 b)待处理数据的初态 c)问题的规模和待处理数据的初态线性表线性表线性表n线性表的定义和特点u 定义 n（0）个数据元素的有限序列，记作 （a1,a2,an）ai 是表中数据元素，n 是表长度。v除第一个元素外，其他每一个元素有一个且仅有一除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。个直接前驱。v除最后一个元素外，其他每一个元素有一个且仅有除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。一个直接后继。u 特点特点 顺序表n顺序表的定义和特点u 定义 将线性表中的元素相继
6、存放在一个连续的存储空间中。u 可利用一维数组描述存储结构u 特点 线性表的顺序存储方式u 遍历 顺序访问,可以随机存取 25 34 57 16 48 09 0 1 2 3 4 5 data顺序表的插入int Insert(SeqList&L,ListData x,int i)/在表中第i个位置插入新元素 xif(i L.length|L.length=ListSize)return 0;/插入不成功for(int j=L.length;j i;j-)L.dataj=L.dataj-1;L.datai=x;L.length+;return 1;/插入成功顺序表的删除int Delete(Seq
7、List&L,ListData x)/在表中删除已有元素x inti=Find(L,x);/在表中查找x if(i=0)L.length-;for(int j=i;j L.length;j+)L.dataj=L.dataj+1;return 1;/成功删除 return 0;/表中没有x应用1：集合 并运算void Union(SeqList&A,SeqList&B)intn=Length(A);int m=Length(B);for(int i=0;i m;i+)int x=GetData(B,i);/在B中取一元素intk=Find(A,x);/在A中查找它if(k=-1)/若未找到插入它
8、 Insert(A,x,n);n+;应用2：集合 交运算voidIntersection(SeqList&A,SeqList&B)intn=Length(A);int m=Length(B);inti=0;while(i link=first;first=newnode;u第二种情况：在链表中间插入 newnode-link=p-link;p-link=newnode；u 第三种情况：在链表末尾插入 newnode-link=p-link;p-link=newnode；intInsert(LinkList&first,int x,inti)/在链表第i个结点处插入新元素x ListNode*p
9、=first;intk=0;while(p!=NULL&k link;k+;/找第 i-1个结点if(p=NULL&first!=NULL)printf(“无效的插入位置!n”);return0;ListNode*newnode=/创建新结点 (ListNode*)malloc(sizeof(ListNode);newnode-data=x;if(first=NULL|i=1)/插在表前 newnode-link=first;first=newnode;else/插在表中或末尾 newnode-link=p-link;p-link=newnode;return1;n删除u第一种情况:删除表中第
10、一个元素u第二种情况:删除表中或表尾元素在单链表中删除含在单链表中删除含ai的结点的结点ai-1aiai+1删除前删除前ai-1aiai+1pq删除后删除后int Delete(LinkList&first,int i)/在链表中删除第 i个结点 ListNode*p,*q;if(i=1)/删除表中第1个结点q=first;first=first-link;elsep=first;intk=0;/找第 i-1个结点 while(p!=NULL&k link;k+;if(p=NULL|p-link=NULL)printf(“无效的删除位置!n”);return0;else/删除表中或表尾元素 q
11、=p-link;/重新链接 p-link=q-link;free(q);/删除q return 1;单链表清空void Clear(LinkList first)/删去链表中除表头结点外的所有其他结点 ListNode*q;while(first-link!=NULL)q=first-link;first-link=q-link;/将表头结点后第一个结点从链中摘下 free(q);/释放它 习题习题例例1.已知单链表的结构定义如下：已知单链表的结构定义如下：structListNodeintdata;structListNode*next;typedefListNode*LinkList;请编
12、写算法（写出算法代码），将指定的带头结点的单请编写算法（写出算法代码），将指定的带头结点的单链表转为逆序。链表转为逆序。参考算法代码形式如下：参考算法代码形式如下：intReverseLinkList(LinkListA).参考代码如下：参考代码如下：int ReverseLinkList(LinkList A)if(A=NULL)return 0;ListNode*p=A-next;A-next=NULL;while(p!=NULL)ListNode*q=p;p=p-next;q-next=A-next;A-next=q;return 1;例例2.已知顺序结构线性表的结构定义如下，且表中的元
13、素按已知顺序结构线性表的结构定义如下，且表中的元素按非降序排列：非降序排列：struct SListstruct SList int bufferMAXLENGTH;int bufferMAXLENGTH;int tablelen;int tablelen;请编写高效算法，删除表中的重复元素。如，若原表为请编写高效算法，删除表中的重复元素。如，若原表为(1,1,2,3,3,3,4,5,5)，经过算法处理后，表为，经过算法处理后，表为(1,2,3,4,5)。参考算法代码形式如下：参考算法代码形式如下：int PackSList(SList&L).参考代码如下：参考代码如下：int PackSLi
14、st(SList&L)int i,j;for(i=0;iL.tablelen-1;i+)if(L.bufferi=L.bufferi+1)break;for(j=i+1;jtop=-1;intStackFull(SeqStack*S)/判断栈是否满？满则返回1，否则返回0return S-top=StackSize-1;void InitStack(SeqStack*S)/置空栈S-top=-1;int Push(SeqStack*S,StackDatax)/若栈满返回0,否则新元素 x 进栈并返回1 if(StackFull(S)return0;S-data+S-top=x;/加入新元素re
15、turn1;intGettop(SeqStack*S,StackData&x)/若栈空返回0,否则栈顶元素读到x并返回1if(StackEmpty(S)return0;x=S-dataS-top;return1;int Pop(SeqStack*S,StackData&x)/若栈空返回0,否则栈顶元素退出到x并返回1 if(StackEmpty(S)return 0;x=S-dataS-top-;return 1;栈的链接表示栈的链接表示 链式栈链式栈链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头适合
16、于多栈操作适合于多栈操作toptypedefintStackData;typedefstructnode StackData data;/结点数据 structnode*link;/结点链指针 StackNode;typedefstruct StackNode*top;/栈顶指针 LinkStack;链式栈链式栈(LinkStack)的定义的定义链式栈操作的实现链式栈操作的实现void InitStack(LinkStack*S)S-top=NULL;int Push(LinkStack*S,StackData x)StackNode*p=(StackNode*)malloc (sizeof(
17、StackNode);p-data=x;p-link=S-top;S-top=p;return 1;int StackEmpty(LinkStack*S)return S-top=NULL;intPop(LinkStack*S,StackData&x)if(StackEmpty(S)return 0;StackNode*p=S-top;S-top=p-link;x=p-data;free(p);return 1;intGetTop(LinkStack*S,StackData&x)if(StackEmpty(S)return 0;x=S-top-data;return 1;定义定义队列是只允许在
18、一端删除，在另一端插入的线性表队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做允许删除的一端叫做队头队头(front)，允许插入的一端，允许插入的一端叫做叫做队尾队尾(rear)。特性特性先进先出先进先出(FIFO,First In First Out)a0a1a2 an-1frontrear队列队列(Queue)队列的抽象数据类型ADT Queue/对象对象:由数据类型为由数据类型为QueueData的元素构成的元素构成int EnQueue(Queue*Q,QueueData x);/进队进队 intDeQueue(Queue*Q,QueueData&x);/出队出队 int
19、GetFront(Queue*Q,QueueData&x);/取队头取队头 void InitQueue(Queue*Q);/置空队置空队intQueueEmpty(Queue*Q);/判队空否判队空否 int QueueFull(Queue*Q);/判队满否判队满否顺序队列#defineQueueSize 50;typedefintQueueData;typedefstructQueueData dataQueueSize;intrear,front;SeqQueue;voidInitQueue(SeqQueue*Q)Q-front=Q-rear=-1;队列的进队和出队原则队列的进队和出队原
20、则n进队时队尾指针先进一进队时队尾指针先进一rear=rear+1，再将新，再将新元素按元素按rear指示位置加入。指示位置加入。n出队时队头指针先进一出队时队头指针先进一front=front+1，再将，再将下标为下标为front的元素取出。的元素取出。n 队满时再进队将队满时再进队将溢出出错溢出出错；n队空时再出队将队空时再出队将队空处理队空处理。n解决办法之一：将队列元素存放数组首尾相接，解决办法之一：将队列元素存放数组首尾相接，形成形成循环循环(环形环形)队列队列。队列存放数组被当作首尾相接的表处理。队列存放数组被当作首尾相接的表处理。队头、队尾指针加队头、队尾指针加1时从时从Queu
21、eSize-1直接进到直接进到0，可，可用语言的取模用语言的取模(余数余数)运算实现。运算实现。队头指针进队头指针进1:front=(front+1)%QueueSize;队尾指针进队尾指针进1:rear=(rear+1)%QueueSize;队列初始化：队列初始化：front=rear=0;队空条件：队空条件：front=rear;队满条件：队满条件：(rear+1)%QueueSize=front 循环队列循环队列(Circular Queue)voidInitQueue(SeqQueue*Q)Q-rear=Q-front=0;intQueueEmpty(SeqQueue*Q)return
22、Q-rear=Q-front;intQueueFull(SeqQueue*Q)return(Q-rear+1)%QueueSize=Q-front;循环队列操作的实现循环队列操作的实现intEnQueue(SeqQueue*Q,QueueData x)if(QueueFull(Q)return 0;Q-rear=(Q-rear+1)%QueueSize;Q-dataQ-rear=x;return1;intDeQueue(SeqQueue*Q,QueueData&x)if(QueueEmpty(Q)return 0;Q-front=(Q-front+1)%QueueSize;x=Q-dataQ-
23、front;return 1;intGetFront(SeqQueue*Q,QueueData&x)if(QueueEmpty(Q)return 0;x=Q-data(Q-front+1)%QueueSize;return1;队列的链接表示队列的链接表示链式队列链式队列队头在链头，队尾在链尾。队头在链头，队尾在链尾。链式队列在进队时无队满问题，但链式队列在进队时无队满问题，但有队空问题。有队空问题。队空条件队空条件为为 front=NULLfrontrear 链式队列的定义链式队列的定义typedef int QueueData;typedef struct node QueueData da
24、ta;/队列结点数据队列结点数据 struct node*link;/结点链指针结点链指针 QueueNode;typedef struct QueueNode*rear,*front;LinkQueue;voidInitQueue(LinkQueue*Q)Q-rear=Q-front=NULL;intQueueEmpty(LinkQueue*Q)return Q-front=NULL;intGetFront(LinkQueue*Q,QueueData&x)if(QueueEmpty(Q)return 0;x=Q-front-data;return1;链式队列主要操作的实现链式队列主要操作的实
25、现int EnQueue(LinkQueue*Q,QueueData x)QueueNode*p=(QueueNode*)malloc (sizeof(QueueNode);p-data=x;p-link=NULL;if(Q-front=NULL)/空,创建第一个结点 Q-front=Q-rear=p;else Q-rear=Q-rear-link=p;return1;intDeQueue(LinkQueue*Q,QueueData&x)/删去队头结点，并返回队头元素的值 if(QueueEmpty(Q)return0;/判队空 QueueNode*p=Q-front;x=p-data;/保存
26、队头的值 Q-front=Q-front-link;/新队头 if(Q-front=NULL)Q-rear=NULL;free(p);return 1;队列的应用举例队列的应用举例逐行打印二项展开式逐行打印二项展开式(a+b)i的系数的系数杨辉三角形杨辉三角形 (Pascals triangle)分析第分析第 i 行元素与第行元素与第 i+1行元素的关系行元素的关系从前一行的数据可以计算下一行的数据从前一行的数据可以计算下一行的数据0110ts+ti=3013310si=414641i=201210从第从第 i 行数据计算并存放第行数据计算并存放第 i+1 行数据行数据1 2 1 0 1 3
27、3 1 0 1 4 6s=0t=1t=2t=1t=0t=1t=3t=3t=1t=0t=1s+ts=ts=ts=ts=ts=ts=ts=ts=ts+ts+ts+ts+ts+ts+ts+ts+t#include queue.hvoid YANGVI(int n)Queue q;/队列初始化队列初始化 InitQueue(q);EnQueue(q,1);EnQueue(q,1);int s=0,t;利用队列打印二项展开式系数的程序利用队列打印二项展开式系数的程序for(int i=1;i=n;i+)/逐行计算逐行计算 printf(“n”);EnQueue(q,0);for(int j=1;j lc
28、hild);PreTraverse(T-rchild);return 0;参考非递归算法代码参考非递归算法代码int PreTraverse(BiTree T)Stack S;InitStack(S);if(T=NULL)return 0;Push(S,T);while(!EmptyStack(S)Pop(S,T);Visit(T);if(T-rchild!=NULL)Push(S,T-rchild);if(T-lchild!=NULL)Push(S,T-lchild);return 1;例2.已知入栈序列为1 2 3 4 5 6，能否得到出栈序列3 4 2 1 6 5？若能，请设计操作序列（
29、P表示入栈动作，Q表示出栈动作），若不能，请说明原因。操作序列为：操作序列为：PPPQPQQQPPQQ PPPQPQQQPPQQ 串和数组串和数组例题例题请用改进请用改进KMP算法计算下面两个模式串的算法计算下面两个模式串的nextval值（写出值（写出结果结果nextval值即可）：值即可）：kkmmppkkmmnextvanext解：解：i i0 01 12 23 34 45 56 67 78 89 9T Tk kk km mm mp pp pk kk km mm mK K-1-10 01 10 00 00 00 01 12 23 3-1-1-1-11 10 00 00 0-1-1-1-1
30、1 10 0i i0 01 12 23 34 45 56 67 78 89 9T Tn ne ex xt tv va an ne ex xt tK K-1-10 00 00 00 00 00 01 12 23 3-1-10 00 00 00 00 0-1-10 00 00 0nextnextnextnext特殊矩阵的压缩存储n特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。n特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。u对称矩阵u三对角矩阵树和二叉树树和二叉树二叉树遍历中序遍历结果：a+b*c-d-e/f前序遍历结果：-
31、+a*b-c d/e f后序遍历结果：a b c d-*+e f/-/+*abcdef二叉树的计数 例,前序序列 ABHFDECKG 和中序序列 HBDFAEKCG,求构造的二叉树。由二叉树的前序序列和中序序列可唯一地确定一棵二叉树由二叉树的前序序列和中序序列可唯一地确定一棵二叉树由二叉树的前序序列和中序序列可唯一地确定一棵二叉树由二叉树的前序序列和中序序列可唯一地确定一棵二叉树?由二叉树的后序序列和中序序列可唯一地确定一棵二叉树由二叉树的后序序列和中序序列可唯一地确定一棵二叉树由二叉树的后序序列和中序序列可唯一地确定一棵二叉树由二叉树的后序序列和中序序列可唯一地确定一棵二叉树?由二叉树的前序
32、序列和后序序列可唯一地确定一棵二叉树由二叉树的前序序列和后序序列可唯一地确定一棵二叉树由二叉树的前序序列和后序序列可唯一地确定一棵二叉树由二叉树的前序序列和后序序列可唯一地确定一棵二叉树?由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。由二叉树的后序序列和中序序列可唯一地确定一棵二叉树。由二叉树的后序序列和中序序列可唯一地确定一棵二叉树。由二叉树的由二叉树的前序序列和后序序列不可前序序列和后序序列不可唯一地确定一棵二叉树。唯一地确定一棵二叉树。前序序列 ABHFDECKG 中序序列 HBDFAEKCG EKCGABHDFEKCGABHFD
33、KCGEABHFDEABHFDCKGHBDFEKCGAEKCGABHDFCGEHT1T2T3AFBDIJKAFGHKT1T2T3BCDEIJBACEDKHIJGF3 棵树的森林各棵树的二叉树表示森林的二叉树表示森林与二叉森林与二叉树的的对应关系关系树的遍历n深度优先遍历u 先根次序遍历u 后根次序遍历n广度优先遍历CGABDEFABCEDGF例例.已知二叉树中度为已知二叉树中度为2的结点个数为的结点个数为n2，度为，度为1的结点个数为的结点个数为n1，度为，度为0的结点个数为的结点个数为n0。请证明：。请证明：n2=n0-1。参考证明如下：参考证明如下：设结点数为设结点数为n，则，除根结点外，
34、每个结点有唯一的父结点，则，除根结点外，每个结点有唯一的父结点，因此总分支数为因此总分支数为n-1，因此可得：，因此可得：n=n2+n1+n0n2*2+n1*1+n0*0=n-1综合上述两式，可得综合上述两式，可得n2=n0-1例例.已知一组字符及其权值如下：已知一组字符及其权值如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8请构造相应的哈夫曼树，画出结果哈夫曼树即可。请构造相应的哈夫曼树，画出结果哈夫曼树即可。参考答案如下：参考答案如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25
35、,j:5,k:11,l:8a/35b/9c/19d/27f/14g/21h/12i/25j/5k/11l/8e/811320253341506076110157267给出二叉树，画出对应的中序线索化二叉树。图图图的要点图的存储结构邻接矩阵邻接表结构图的遍历深度优先搜索广度优先搜索最小生成树有向无环图的关键路径最短路径邻接表结构例1：写出右图的的邻接矩阵或邻接表。邻接矩阵解：邻接矩阵如下 顶点表顶点表0 0a a1 1b b2 2c c3 3d d4 4e e5 5f f6 6g g0 01 12 23 34 45 56 60 00 00 00 00 00 01 11 11 10 00 01 1
36、0 00 00 00 02 20 00 00 00 01 10 00 03 30 00 00 00 00 00 00 04 40 00 00 01 10 00 00 05 50 00 00 00 01 10 01 16 60 01 10 01 10 00 00 0邻邻接接矩矩阵阵邻接表结构解：邻接表结构如下解：邻接表结构如下 6543210gfedcba顶点表顶点表652446313图的深度优先搜索例例2 2：写出其深度优先遍历序。：写出其深度优先遍历序。深度优先遍历序：深度优先遍历序：afedgbcafedgbca a a ab b b bf f f fe e e ed d d dc c c
37、 cg g g g1 1 1 14 4 4 41 1 1 12 2 2 22 2 2 23 3 3 3图的广度优先搜索例例3 3：写出其广度优先遍历序。：写出其广度优先遍历序。广度优先遍历序：广度优先遍历序：afgedbcafgedbca ab bf fe ed dc cg g1 11 12 24 43 32 2例例4：已知一个用邻接表存储的有向图如下，请画出图，：已知一个用邻接表存储的有向图如下，请画出图，并写出该图的深度优先遍历序和广度优先遍历序。并写出该图的深度优先遍历序和广度优先遍历序。a ab bc cd de ef fg gh hi ij j01234567823061050679
38、569298958最小生成树例5 MST性质证明设无向图N=(V,E),U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU,vV-U，则必存在一棵包含边(u,v)的最小生成树。MST性质证明：设N的任何一棵最小生成树都不包含(u,v)，T是一棵最小生成树。n将边将边(u,v)(u,v)加入到加入到T T中时，由生成树的定义，中时，由生成树的定义，T T必存必存在一条包含在一条包含(u,v)(u,v)的闭合回路。的闭合回路。nT T上必存在另一条边上必存在另一条边(u(u,v,v)，其中，其中u uU,U,v vV-UV-U，且，且u u和和u u之间，之间，v v和和v v
39、之间均有路径相通。之间均有路径相通。n删去边删去边(u(u,v,v)，可消去回路，同时得到另一棵，可消去回路，同时得到另一棵生成树生成树T T。n由于由于(u,v)(u,v)的代价不高于的代价不高于(u(u,v,v)，则，则T T的代价的代价不高于不高于T T，T T是包含是包含(u,v)(u,v)的一棵最小生成树，与假的一棵最小生成树，与假设矛盾设矛盾最小生成树(Prim算法)E1：任取一个顶点构成U=v0，viV-U；构造向量cost0n-1和adj0n-1，costi表示顶点vi到U的最短边的长度，adji表示顶点vi到U的最短边在U中邻接点的下标；初始时，生成树T为空集。nE2E2：重
40、复：重复n-1n-1次次nE21E21：从：从V-UV-U中选出中选出cost值最小的顶点值最小的顶点v vk k，将边，将边v 加入到生成树加入到生成树T T中，然后将中，然后将v vk k并入并入U U中；中；nE22E22：修正：修正V-UV-U中各顶点的中各顶点的cost值和值和adj值；值；例6：已知连通网如下图所示，请用Prim算法计算出该连通网的最小生成树（写出计算过程）。abecgfhid2015313174239219341523612最小生成树(Kruskal算法)E1：将所有的边按权值排序；E2：设每个顶点为一个独立的点集，生成树T为空集；E3：依序扫描每一条边，直到已输
41、出n-1条边：E31：若vi、vj不在同一点集中，则将该边加入生成树T中，并合并这两个点集；否则舍弃该边；例7：已知连通网如下图所示，请用Kruskal算法计算出该连通网的最小生成树（写出计算过程）。abecgfhid2015313174239219341523612关键路径关键路径的计算E1：依拓扑序计算各顶点的最早发生时间ve；E2：依逆拓扑序计算各顶点的最迟发生时间vl；E3：计算每条弧的最早开始时间e和最迟开始时间l，若e等于l，则输出该弧（关键弧）；例.已知有向无环图如下所示，计算该图的关键路径，并写出计算过程和结果。01234567851912174271510676 参考答案如下
42、：参考答案如下：012345678ve0519172321293844vl0619302328373844边边el选入选入01005185619191926173023312323212829373838拓扑序拓扑序最短路径从指定起点到其他各顶点的最短路径（Dijkstra算法）每一对顶点之间的最短路径（Floyd算法）Dijstra算法E1：初始化辅助向量D和集合S；Di表示从始点v0到终点vi的较短路径的长度。S为最短路径的终点集合。E2：循环n-1次：E21：从V-S中选择最小的Dj；E22：将vj并入S中;E23：对V-S中的各顶点vi的已知较短路径进行修正：Dijstra算法例例10
43、：已知带权邻接矩阵：已知带权邻接矩阵：求求v0到其余各点的最短路径。到其余各点的最短路径。Floyd算法E1：初始化从vi到vj的目前已知较短路径为从vi到vj的直达弧；E2：对每两顶点对(vi,vj)依次计算P(i,k,j)，k=0n-1，计算规则为：P(i,k,j)=min(P(i,k-1,k)+P(k,k-1,j),P(i,k-1,j)例例1010：已知有向网如下图所示，请用：已知有向网如下图所示，请用Floyd算法算法计算各顶点间的最短路径（写出计算过程）。计算各顶点间的最短路径（写出计算过程）。Floyd算法例例1111：已知某带权有向图如下，请用：已知某带权有向图如下，请用Floy
44、dFloyd算法计算算法计算图中各顶点间的最短路径，并写出计算过程。图中各顶点间的最短路径，并写出计算过程。1230112345012300/4/0-1-/0-2-/0-31-/1-00/-/1-21/1-323/2-01/2-10/-/2-332/3-0-/3-15/3-20/P(i,j,0)012300/4/0-1-/0-2-/0-31-/1-00/-/1-21/1-323/2-01/2-10/-/2-332/3-06/3-0-15/3-20/P(i,j,-)P(i,j,1)012300/4/0-1-/0-25/0-1-31-/1-00/-/1-21/1-323/2-01/2-10/2/2
45、-1-332/3-06/3-0-15/3-20/P(i,j,2)012300/4/0-1-/0-25/0-1-31-/1-00/-/1-21/1-323/2-01/2-10/2/2-1-332/3-06/3-0-15/3-20/P(i,j,3)012300/4/0-110/0-1-3-25/0-1-313/1-3-00/6/1-3-21/1-323/2-01/2-10/2/2-1-332/3-06/3-0-15/3-20/结果如下：012300/4/0-110/0-1-3-25/0-1-313/1-3-00/6/1-3-21/1-323/2-01/2-10/2/2-1-332/3-06/3-0
46、-15/3-20/查找和排序查找和排序顺序查找顺序查找（顺序查找（Sequential Search）：又叫线性查找，是最基本的查找技术查找过程：从表中第一个（或最后一个）记录开始，按顺序逐个进行记录的关键字和给定值比较，若某讴歌记录的关键字和给定值相等，则查找成功。如果表中所有记录都比较完后仍未找到，则查找失败顺序表查找优化监视哨ASL分析查找成功：ASL=(n+1)/2查找不成功：ASL=(n+1)顺序查找：ASL=1/2*(n+1)/2+1/2*(n+1)=(n+1)折半查找折半查找（Binary Search）又称为二分查找二分查找，要求线性表：记录的关键码有序关键码有序（通常从小到大
47、）线性表必须采用顺序存储顺序存储基本思想：取中间记录作为比较对象：若给定值与中间记录的关键字相等相等，则查找成功；若给定值小于小于中间记录的关键字，则在中间记录的左半区继续二分查找若给定值大于大于中间记录的关键字，则在中间记录的右半区继续二分查找不断重复上述查找，直到查找成功或所有查找区域无记录，查找失败折半查找算法实现性能分析：时间复杂度：O(logn)ASL=log2(n+1)1二叉搜索（排序）树二叉排序树（二叉排序树（Binary Sort Tree），又称为二叉查找树二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：若左子树不为空，则左子树上所有节点的值均小于它 的根结点的值若
48、右子树不为空，则右子树上所有节点的值均小于它的根节点的值左、右子树也均为二叉排序树n 个结点的二叉搜索树的数目【例】【例】3 个结点的二叉搜索树个结点的二叉搜索树122133132123123123 132 213 231 312 321输入数据输入数据 53,78,65,17,87,09,81,15 创创建二叉搜索树建二叉搜索树53537853786553786517537865178753786517870953786517870981平衡二叉树（AVL）平衡二叉树平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binar
49、y Search Tree）一种二叉排序树每个节点的左子树、右子树的高度差不超过 1平衡因子平衡因子（Balance Factor）节点的左子树深度减去右子树深度的值，简称BFhhhACEBDhh+1BACEDhhh+1CEABDh0 00 00 0-1 1-1 1-2 2失衡：在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到-2，造成不平衡。为使树恢复平衡，从A沿插入路径连续取3 个结点A、B和D，它们处于一条方向为L的直线上，需要做右单旋转。以结点B为旋转轴，将结点A顺时针旋转LL型hhhACEBDhhh+1BACEDhhh+1CEABD+1+1+2+20 0+1+10 00
50、0失衡：在子树E中插入新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。沿插入路径检查三个结点A、C和E。它们处于方向为L的直线上，需做左单旋转。以结点C为旋转轴，让结点A逆时针旋转。RR型LR型插入插入0 00 0-1 1hhACEDh-1h-1BFG-2 2+1+1-1 1hhA h-1hCEDB左单左单左单左单旋转旋转旋转旋转FG0 00 0-2 2hhACED-2 2 h-1hB右单右单右单右单旋转旋转旋转旋转FG0 0 0 00 0+1+1hhA h-1hCEDBFGRL型插入插入插入插入+1+10 00 00 00 0hhACED h-1 h-1BFG0 00 0+2