数据结构基础复习09市公开课获奖课件省名师优质课赛课一等奖课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,数据结构,考研辅导,基础复习,浙江大学计算机学院,1/115,1,内容提要,考研概述,1,基础内容复习,2,线性表、堆栈、队列、数组,A,树与图,B,查找与排序,C,2/115,2,考研概述,考查目标,了解数据结构基本概念：掌握数据结构逻辑结构、存放结构及其差异，以及各种基本操作实现。,在掌握基本数据处理原理和方法基础上，能够对算法进行设计与分析。,能够选择适当数据结构和方法进行问题求解。,3/115,3,考研概述,考试形式,整卷满分为,150,分，考试时间为,180,分钟,数据结构占,45,分，预计用时,4550,分钟,单项选择题：,40,题,2,分,/,题，预计占,10,题,20,分左右，提议用时不超出,2,分钟,/,题,综合题：,70,分，预计占,2,题共,2025,分，提议用时不超出,10,分钟,/,题,4/115,4,考研概述,复习计划,基础理论复习,例题详解,题目范围：真题,1,套,+,模拟题,9,套,+,补充题,模拟题第,10,套将用于最终一天模拟考试,5/115,5,基础内容复习,数据结构（,C,语言版）,，严蔚敏、吴伟民，清华大学出版社,线性表、堆栈、队列、数组,树与图,查找与排序,6/115,6,线性表、堆栈、队列、数组,线性表,定义：,n,个数据元素有限序列,基本操作：随机访问、插入、删除、前驱、后继、倒序等,实现方式：,次序存放：数组,a,i,a,i,+1,Loc,(,a,i,),Loc,(,a,i,+1,)=,Loc,(,a,i,)+,l,l,Loc,(,a,i,)=,Loc,(,a,1,)+?,(,i,-1)*,l,7/115,7,线性表,实现方式：,次序存放：数组,线性表、堆栈、队列、数组,是一个随机存取存放结构，方便随机存取第,i,个数据元素,插入、删除复杂度为,O,(,n,),，需要移动大量元素,8/115,8,自测题,在,n,个结点次序表中，算法时间复杂度是,O(1),操作是：,访问第,i,个结点,(1in),和求第,i,个结点直接前驱,(2in),在第,i,个结点后插入一个新结点（,1in,）,删除第,i,个结点（,1in,）,将,n,个结点从小到大排序,线性表、堆栈、队列、数组,9/115,9,线性表、堆栈、队列、数组,线性表,实现方式：,链式存放：链表,线性链表,存放地址,数据域,指针域,1,Li,NULL,7,Qian,13,13,Sun,1,19,Zhao,7,头指针,H=19,H,Zhao,Qian,Sun,Li,若,p-data=,a,i,则,p-next-data=,a,i,+1,typedef struct,LNode,ElemType data;,struct,LNode *next;,LNode,*LinkList;,有时附加,头结点,10/115,10,自测题,线性表若采取链式存放结构时，要求内存中可用存放单元地址,:,必须是连续,部分地址必须是连续,一定是不连续,连续或不连续都能够,线性表、堆栈、队列、数组,11/115,11,线性表、堆栈、队列、数组,线性表,实现方式：,链式存放：链表,线性链表,插入、删除复杂度为,O,(1),，仅需修改指针而,不,需要移动元素,是一个,非,随机存取存放结构，,不,方便随机存取第,i,个数据元素,*静态链表（,p.31-35,）,12/115,12,自测题,下面叙述不正确是（）,线性表在链式存放时，查找第,i,个元素时间同,i,值成正比,线性表在链式存放时，查找第,i,个元素时间同,i,值无关,线性表在次序存放时，查找第,i,个元素时间同,i,值成正比,线性表在次序存放时，查找第,i,个元素时间同,i,值无关,线性表、堆栈、队列、数组,13/115,13,自测题,在一个单链表中，若,p,所指结点不是最终结点，在,p,之后插入,s,所指结点，则执行：,s-next=p;p-next=s;,s-next=p-next;p-next=s;,s-next=p-next;p=s;,p-next=s;s-next=p;,线性表、堆栈、队列、数组,p,s,14/115,14,自测题,在单链表中，指针,p,指向元素为,x,结点，实现“删除,x,后继”语句是：,p=p-next;,p-next=p-next-next;,p-next=p;,p=p-next-next;,线性表、堆栈、队列、数组,x,p,15/115,15,线性表、堆栈、队列、数组,线性表,实现方式：,链式存放：链表,循环链表,双向链表,H,H,H,H,有时设,尾指针,可简化一些操作，如两表合并。,16/115,16,自测题,设一个链表最惯用操作是在末尾插入结点和删除尾结点，则选取,(),最节约时间。,单链表,单循环链表,带尾指针单循环链表,带头结点双循环链表,线性表、堆栈、队列、数组,17/115,17,自测题,将线性表,La,和,Lb,头尾连接，要求时间复杂度为,O(1),，且占用辅助空间尽可能小。应该使用哪种结构？,单链表,单循环链表,带尾指针单循环链表,带头结点双循环链表,线性表、堆栈、队列、数组,tmp=La-next;,La-next=Lb-next;,Lb-next=tmp;,La,Lb,18/115,18,线性表、堆栈、队列、数组,线性表,练习,1,：,分别实现数组、单链表、循环链表、双向链表插入和删除操作。,练习,2,：,实现单链表原地逆转。,练习,3,：,分别用一元多项式两种表示实现多项式加法。,3,2,-5,1,-2,3000,-1,1,0,3,200,P,19/115,19,自测题,给定,2,个带有表头结点单链表头指针,L1,和,L2,，结点结构为 。假设这,2,个链表结点已经按,Data,域递增有序，请设计算法把它们合并成一个按,Data,域递增有序链表。注意：算法不能使用额外结点空间。,线性表、堆栈、队列、数组,Data,Next,算法思绪为次序比较,L1,和,L2,当前所指两结点,Data,域，将小那个结点从原链表摘除，贴到合并链表尾部。如此进行到最少其中一个链表为空。若此时另一个链表不为空，则将另一个链表整个贴到合并链表尾部。注意原始,2,个链表有,2,个头结点，合并后只保留一个，需要释放另一个空间。,20/115,20,List MergeSortedLists(List L1,List L2),List L=L1;List Tail=L2;,L1=L1-Next;L2=L2-Next;,free(Tail);Tail=L;,/,释放第二个链表表头，并将新链表表尾指针,Tail,初始化,while(L1&L2),if(L1-Data L2-Data),Tail-Next=L2;L2=L2-Next;,/,第二个链表第一结点值小，将其插入新链表尾,else,Tail-Next=L1;L1=L1-Next;,/,第一个链表第一结点值小，将其插入新链表尾,Tail=Tail-Next;,if(L1)Tail-Next=L1;/,将剩下第一个链表接到新链表表尾,else if(L2)Tail-Next=L2;/,将剩下第二个链表接到新链表表尾,return L;,21/115,21,自测题,给定,2,个带有表头结点单链表头指针,L1,和,L2,，结点结构为 。假设这,2,个链表结点已经按,Data,域递增有序，请设计算法把它们合并成一个按,Data,域,递减,有序链表。注意：算法不能使用额外结点空间。,线性表、堆栈、队列、数组,Data,Next,解题基本思绪不变，只要将原来表尾插入改为表头插入即可。当然，当其中一个链表为空而另一个链表不为空时，不能直接将剩下链表贴到表尾，而必须将剩下结点一个一个插入表头。,22/115,22,自测题,若,L1,和,L2,是有序,数组,，其结点已经按,Data,域递增有序，请设计算法把它们合并成一个按,Data,域递增有序数组。注意：要求将,L2,并入,L1,，而且要求移动元素次数尽可能少。,线性表、堆栈、队列、数组,必须事先算好合并后,L1,长度，然后从,L1,最终尾部向前插入元素。插入过程与前面算法类似，不过是,从尾部开始,比较,L1,和,L2,对应元素大小，将较大元素先插入到后面位置。,23/115,23,void MergeSortedArrays(ElementType L1,int N1,ElementType L2,int N2),int p1,p2,cur;,p1=N1-1;/p1,指向,L1,当前处理元素位置,p2=N2-1;/p2,指向,L2,当前处理元素位置,cur=N1+N2-1;/cur,指向下一个要插入元素在,L1,中最终位置,while(p1=0)&(p2=0),if(L1p1 L2p2),L1cur=L1p1;p1-;,else,L1cur=L2p2;p2-;,cur-;,while(p2=0)/,将,p2,剩下元素插入到,L1,中,L1p2=L2p2;p2-;,24/115,24,堆栈,概念：后进先出，限定仅在表尾进行插入删除线性表。,表示与实现：,次序栈：数组，,top+,，,top-,链栈：链表，,top,即为头指针,应用：括号匹配检验、表示式求值、,n,阶,Hanoi,塔问题（经典递归）、迷宫问题,线性表、堆栈、队列、数组,25/115,25,自测题,判定一个栈,ST(,最多元素为,m0),为空条件是：,ST-top!=0,ST-top,=0,ST-top!=m0,ST-top,=m0,线性表、堆栈、队列、数组,26/115,26,自测题,有六个元素以,6,，,5,，,4,，,3,，,2,，,1,次序进栈，问以下哪一个不是正当出栈序列？,5 4 3 6 1 2,4 5 3 1 2 6,3 4 6 5 2 1,2 3 4 1 5 6,线性表、堆栈、队列、数组,27/115,27,自测题,若一个栈输入序列为,1,，,2,，,3,，,，,n,，输出序列第一个元素是,i,，则第,j,个输出元素是：,i j 1,i j,j i 1,不确定,线性表、堆栈、队列、数组,28/115,28,队列,概念：先进先出，限定仅在队尾进行插入、仅在队头进行删除线性表。,表示与实现：,次序队列：循环数组，,(rear+1)%N,(front+1)%N,链栈：链表，,front,为头指针，,rear,为尾指针,应用：离散事件模拟,线性表、堆栈、队列、数组,29/115,29,自测题,循环队列用数组,A0,N,1,存放其元素值，已知其头尾指针分别是,front,和,rear,，则当前队列中元素个数是：,(rear-front+N)%N,rear-front+1,rear-front-1,rear-front,线性表、堆栈、队列、数组,0,1,.,N-1,front,rear,30/115,30,自测题,栈和队列共同特点是：,都是先进后出,都是先进先出,只允许在同一端点处插入和删除,没有共同点,线性表、堆栈、队列、数组,31/115,31,数组,特殊矩阵压缩存放,对称矩阵：,线性表、堆栈、队列、数组,a,n,1,a,11,a,21,a,22,a,31,a,n,n,SA,k,0,1,2,3,*上（下）三角矩阵同理存放，或许多存放一个常数（若另二分之一矩阵元素是非零常数）。,32/115,32,线性表、堆栈、队列、数组,数组,特殊矩阵压缩存放,m,对角矩阵：,或者,稀疏矩阵：,nrow=3,ncol=5,ntotal=6,(1,3,4),(2,1,7),(2,3,1),(2,5,-3),(3,2,-2),(3,5,5),33/115,33,线性表、堆栈、队列、数组,数组,特殊矩阵压缩存放,稀疏矩阵：,三元组次序表：以行序为主序，次序排列为三元组,1,维数组，并存行数、列数、非,0,元个数。,typedef struct,int,i,j;,ElemTypev;,Triple;,typedef union,TripledataMAXSIZE+1;,int,nrow,ncol,ntotal;,Sparse_Matrix;,i,j,v,1,3,4,2,1,7,2,3,1,2,5,-3,5,5,3,-2,2,3,34/115,34,线性表、堆栈、队列、数组,数组,特殊矩阵压缩存放,稀疏矩阵：,三元组次序表：,快速转置,i,j,v,1,2,7,2,3,-2,3,1,4,3,2,1,5,3,5,-3,2,5,i,j,v,1,3,4,2,1,7,2,3,1,2,5,-3,5,5,3,-2,2,3,对每列扫描整个数组：,O,(ncol,ntotal),怎样一步到位，放入正确位置？,numcol,第,col,列中非,0,元个数；,cpotcol,第,col,列中第,1,个非,0,元在转置矩阵中位置；,cpot1=1;,cpotcol=cpotcol-1+numcol-1;,1,2,3,4,5,col,1,1,2,0,2,num,1,2,3,5,5,cpot,4,2,O,(ncol,+,ntotal),35/115,35,线性表、堆栈、队列、数组,数组,特殊矩阵压缩存放,稀疏矩阵：,行逻辑链接次序表：,矩阵相乘,typedef struct,TripledataMAXSIZE+1;,int,rposMAXRC+1;,int,nrow,ncol,ntotal;,Sparse_Matrix;,各行第,1,个非,0,元在数组中位置,设,M,=,A,B,，则有,关键：,对每个,A.datap,，找全部,B.dataq,，满足,(A.datap.j=B.dataq.i),，将,(A.datap.v,B.dataq.v),累加到对应暂时行向量，最终压缩到,M,中。,O,(Arow,Bcol,+,Atotal,Btotal/Brow,),36/115,36,线性表、堆栈、队列、数组,数组,特殊矩阵压缩存放,稀疏矩阵：,十字链表：,矩阵相加,4,1,3,7,2,1,1,2,3,-3,2,5,-2,3,2,5,3,5,1,2,3,M.rhead,1,2,3,4,5,M.chead,计算,A,+,B,复杂度为,O,(Atotal,+Btotal,),37/115,37,自测题,设稀疏矩阵,A,有,t,个非零元素，用二维数组存放时占用,m*n,个单元。问稀疏矩阵三元组表示法在什么情况下比二维数组存放节约空间？,t m*n,t m*n/3,t m*n/3 1,t m*n 1,线性表、堆栈、队列、数组,38/115,38,树与图,树与二叉树概念,树概念：,度,(degree),；层,(level),注意：根为第,1,层；深度,(depth),结点最大层次。,二叉树概念：左右有序,性质,1,：第,i,层最多有,2,i-1,个结点。,性质,2,：深度为,k,二叉树最多有,2,k,-1,个结点。,性质,3,：若,n,0,为叶子数，,n,2,为度为,2,结点数，则有,n,0,=n,2,+1,。,性质,4,：含有,n,个结点,完全二叉树,深度为,log,2,n+1,。,39/115,39,树与二叉树概念,二叉树概念：,性质,5,：对有,n,个结点且次序编号完全二叉树，其任一结点,i,有,树与图,40/115,40,二叉树存放结构,次序存放结构：数组,仅适合用于完全二叉树,链式存放结构：,在含有,n,个结点二叉链表中有 个空链域。,二叉树遍历,先序、中序、后序、层次,树与图,Lchild,Data,Rchild,Parent,1,2,3,4,5,6,7,n+1,41/115,41,自测题,一棵完全二叉树共有,2435,个结点，则其中度为,0,结点数为？,1218,1217,不确定,812,树与图,前,11,层共有,2,11,-1=2047,个结点,第,12,层共有,2435-2047=388,个结点,388+2,10,388/2 =1218,42/115,42,自测题,在一棵高度为,h(,假定树根结点层号为,0),完全二叉树中，所含结点个数大于,2,h 1,2,h+1,2,h,1,2,h,树与图,43/115,43,自测题,结点中序遍历为,xyz,不一样二叉树，它有几个不一样状态？,3,4,5,6,树与图,y,x,z,z,x,y,z,y,x,x,z,y,x,y,z,44/115,44,自测题,前序遍历和中序遍历结果相同二叉树为,普通二叉树,只有根结点二叉树,全部结点只有左子树二叉树,全部结点只有右子树二叉树,树与图,45/115,45,自测题,前序遍历和后序遍历结果相同二叉树为,普通二叉树,只有根结点二叉树,全部结点只有左子树二叉树,全部结点只有右子树二叉树,树与图,46/115,46,自测题,已知中序遍历和前序遍历结果，给出算法求后序遍历结果。,树与图,（,1,）从前序遍历结果推断该树树根。,（,2,）找出左子树和右子树中序和前序遍历结果。,（,3,）重复上述过程，找出左、右子树根结点，并逐步往下扩展，直到生成一颗完整二叉树。,中序,前序,左,左,右,右,47/115,47,OutPostOrder(PreOrder,InOrder),/,已知前序序列,PreOrder,、中序序列,InOrder,，求后序序列,1,）应用前述方法，从序列,PreOrder,和,InOrder,中推断出：,树根,r;,左子树前序遍历序列,PreOrderLeft,和中序遍历序列,InOrderLeft;,右子树前序遍历序列,PreOrderRight,和中序遍历序列,InOrderRight;,2,）递归,OutPostOrder(PreOrderLeft,InOrderLeft);,3,）递归,OutPostOrder(PreOrderRight,InOrderRight);,4,）输出,r;,48/115,48,自测题,下面是某二叉树三种遍历部分结果，请画出对应二叉树。,前序,:_B_F_ICEH_G,中序,:D_KFIA_EJC_,后序,:_K_FBHJ_G_A,树与图,A,B,C,D,F,K,I,E,H,J,G,A,B,D,K,D,I,H,J,G,E,C,49/115,49,自测题,在任意一颗二叉树中，任何两个叶结点在先序、中序、后序中相对次序怎样？,不变,不一样,不能确定,以上都不是,树与图,50/115,50,线索二叉树,概念：,树与图,Lchild,Data,Rchild,Ltag,Rtag,0:Lchild,指向左孩子,1:Lchild,指向前驱,0:Rchild,指向右孩子,1:Rchild,指向后继,+,A,D,B,C,中序遍历：,A+B,C D,0,0,0,+,0,1,A,1,0,0,0,0,1,D,1,1,B,1,1,C,1,头结点,中序线索二叉树,51/115,51,树与图,线索二叉树,结构：,中序：增加,pre,指针，指向刚访问过结点,后序：须增加,Parent,指针域,优点：,遍历不需要堆栈。若经常需要遍历二叉树或查找结点在遍历序列中前驱和后继，则应采取线索链表作为存放结构。,52/115,52,二叉排序树,定义：左,根,二叉树,B=(R,LB,RB),二叉树,B=(R,LB,RB),-,森林,F=T,1,T,2,.T,m,树与图,if,(!F)B=NULL;,else,R=root(T,1,);,LB=T,11,T,12,.T,1m1,;,RB=T,2,.T,m,;,if,(!B)F=NULL;,else,root(T,1,)=R;,T,11,T,12,.T,1m1,=LB;,T,2,.T,m,=RB;,61/115,61,树和森林,树和森林遍历,树遍历：,先根（次序）遍历,=,二叉树先序遍历,后根（次序）遍历,=,二叉树,中序,遍历,森林遍历：,先序遍历,=,二叉树先序遍历,中序遍历,=,二叉树中序遍历,树与图,62/115,62,自测题,设森林,F,对应二叉树为,B,，它有,m,个结点。,B,根为,p,，,p,右子树结点个数为,n,，森林,F,中第一棵树结点个数是,？,m-n,m-n-1,n+1,无法确定,树与图,m,n,63/115,63,自测题,树最适适用来表示,有序数据元素,无序数据元素,元素之间无联络数据,元素之间有分支层次关系,树与图,64/115,64,树应用,等价类问题：,给定集合,S,n,个元素，以及,m,个形如,(x,y),等价偶对，求,S,等价类划分。,树与图,初始化,n,个只包含,1,个元素子集,;,while,(,读入,x,y),if,(!(,Find,(x)=,Find,(y),Union,两集合,;,10,6,8,7,4,1,9,2,3,5,1,4,2,0,10,0,9,4,8,10,7,10,6,10,5,2,4,0,3,2,S,65/115,65,树应用,等价类问题,Union by size,根统计,(-,结点数,),，小树并入大树,Find+,压缩路径,将,Find,路径上结点都变成根孩子,树与图,10,6,8,7,4,1,9,2,3,5,1,4,2,-3,10,-7,9,4,8,10,7,10,6,10,5,2,4,8,3,2,S,Union(2,10),-10,10,Find(9),10,6,8,7,4,1,9,2,3,5,10,10,*等价划分,n,元集合复杂度为,O,(,n,(,n,),),(,n,)4,对通常见到,n,成立。,66/115,66,哈夫曼,(Huffman),树和哈夫曼编码,哈夫曼树：带权路径长度最小二叉树,树与图,7,5,2,4,7,5,2,4,路径长度,=7,2,+5 2,+2 2,+4 2,=36,7,5,2,4,路径长度,=7,3,+5 3,+2 1,+4 2,=46,路径长度,=7,1,+5 2,+2 3,+4 3,=35,67/115,67,哈夫曼,(Huffman),树和哈夫曼编码,哈夫曼树结构,将,n,个带权结点作为,n,棵只有根二叉树森林；,选,2,棵根权值最小树，作为左右子树结构新树，新根权值,=,左右子树根权值和；,将上述,2,棵树删除，将新树加入森林；,重复第,2,、,3,步，直到只剩,1,棵树，即是哈夫曼树。,树与图,68/115,68,哈夫曼,(Huffman),树和哈夫曼编码,哈夫曼编码,例：,aaa,x,u,a,x,z,普通被存为,8,个字符，占,64,字节。但因只有,4,个不一样字符，故可编码为,a,=00,u,=01,x,=10,z,=11,，只需要占,16,个字节。若采取哈夫曼编码,a,=0,u,=110,x,=10,z,=111,，则得到,000,10,110,0,10,111,，只需要占,14,个字节。,注意：任一字符编码都不是另一字符编码前缀,前缀编码,。,树与图,69/115,69,哈夫曼,(Huffman),树和哈夫曼编码,哈夫曼编码结构：,将字符出现频率作为权重，结构哈夫曼树，并按左,0,右,1,编码。,例：,aaa,x,u,a,x,z,树与图,a,:4,x,:2,u,:1,z,:1,a,:4,x,:2,u,:1,z,:1,2,4,8,0,0,0,1,1,1,a,=0,x,=10,u,=110,z,=111,思索：给定编码，怎样判断是否哈夫曼编码？,70/115,70,自测题,哈夫曼树有,n,个叶结点，则该树共有多少个结点？,2n,2n-1,2n+1,不能确定,树与图,N0=n,N1=0,2*N2=N 1,N=N0+N1+N2,N=?,71/115,71,图概念（,p.156-160,）,图存放及基本操作,邻接矩阵法,无向图顶点度,有向图顶点度,网,树与图,72/115,72,图存放及基本操作,邻接表法,树与图,V,1,V,2,V,3,V,4,V,1,V,2,V,3,V,4,0,1,2,3,i,V,1,data,V,2,V,3,V,4,2,1,3,0,0,1,2,3,i,V,1,data,V,2,V,3,V,4,3,1,2,0,0,3,0,2,0,1,2,3,i,V,1,data,V,2,V,3,V,4,3,0,2,0,逆邻接表,*边稀疏时节约空间，但判断任意两顶点是否有弧相连时，则不如邻接矩阵方便。,73/115,73,自测题,含有,n,个顶点无向图最多有几条边？,n(n-1)/2,n(n+1)/2,n,2,/2,2n,树与图,74/115,74,自测题,在一个图中，全部点度数之和等于全部边数目标,多少倍？,1/2,1,2,4,树与图,75/115,75,自测题,一个无向图采取邻接矩阵存放，该邻接矩阵一定是一个,_,_,对称矩阵,对角矩阵,三角矩阵,稀疏矩阵,树与图,76/115,76,树与图,自测题,从邻接矩阵 能够看出，该图共有（）个顶点；假如是有向图该图共有（）条弧；假如是无向图，则共有（）条边,9,5,5,3,4,2,6,3,3,1,2,2,77/115,77,图遍历,深度优先,(DFS),：类似于树先序遍历。递归，需要堆栈。邻接矩阵,O,(,n,2,),；邻接表,O,(,n+e,),。,广度优先,(BFS),：类似于树层次遍历。需要队列。时间复杂度与,DFS,相同。,树与图,78/115,78,自测题,已知无向图为,G=(V,E),，其中，顶点集合为,V=v1,v2,v3,v4,v5,v6,v7,，边集合为,E=(v1,v2),(v1,v3),(v2,v4),(v2,v6),(v4,v5),(v4,v7),(v5,v6),，请分别给出依据该邻接表从顶点,v1,出发进行深度优先搜索与广度优先搜索后顶点序列。当有各种选择时，按序号先后访问。,深度优先搜索序列：,v1,v2,v4,v5,v6,v7,v3,广度优先搜索序列：,v1,v2,v3,v4,v6,v5,v7,树与图,1,2,3,4,5,6,7,79/115,79,图基本应用及其复杂度分析,最小（代价）生成树,普里姆,(Prim),算法：一棵树生长,树与图,v,1,v,2,v,6,v,7,v,3,v,4,v,5,2,4,2,1,3,10,7,5,8,4,6,1,*复杂度为,O,(,n,2,),，与边数无关，适合于求边稠密网最小生成树。,80/115,80,图基本应用及其复杂度分析,最小（代价）生成树,克鲁斯卡尔,(Kruskal),算法：森林生长,树与图,v,1,v,2,v,6,v,7,v,3,v,4,v,5,2,4,2,1,3,10,7,5,8,4,6,1,*,适合于求边稀疏网最小生成树，,复杂度为,O,(,e,log,e,),。,81/115,81,自测题,已知一个带权连通图,G=(V,E),，其中顶点集合为,V=1,2,3,4,5,，其邻接矩阵如图，求出其全部可能最小生成树。,树与图,7 6 9 ,7 8 4 4,6 8 6 ,9 4 6 2,4 2 ,82/115,82,图基本应用及其复杂度分析,最短路径,单源（带权）最短路：迪杰斯特拉,(Dijkstra),算法,贪心，按长度递增生成，当新顶点使路径更短时，更新路径，,O,(,n,2,),。,多源（带权）最短路：弗洛伊德,(Floyd),算法,O,(,n,3,),，但比重复,Dijkstra,算法简单。,树与图,83/115,83,图基本应用及其复杂度分析,拓扑排序：,有向无环图,(DAG),应用之一,选一个无前驱顶点输出；,删除该顶点以及全部以之为尾弧；,重复第,1,、,2,步，直到全部顶点输出，或不存在无前驱顶点,(,说明有环,),。,注意：,拓扑排序可方便检验有向图中是否存在环；,确定无环时，也可用,DFS,进行拓扑排序，退出,DFS,次序即为逆向拓扑序；,DFS,可方便检验无向图中是否存在环,(,若碰到回边即有环,),。,树与图,84/115,84,图基本应用及其复杂度分析,关键路径：,AOE,网,带权,DAG,树与图,0,1,2,3,4,5,6,7,8,start,finish,a0=6,a1=4,a2=5,a3=1,a4=1,a5=2,a6=9,a7=7,a8=4,a9=2,a10=4,0,6,4,5,7,7,16,14,18,18,16,14,7,10,5,6,6,0,2,3,2,3,85/115,85,自测题,判断有向图是否存在回路，除了能够利用拓扑排序方法外，还能够利用,_,_,求关键路径方法,求最短路径,Dijkstra,方法,深度优先遍历算法,广度优先遍历算法,树与图,86/115,86,自测题,弗洛伊德,(Floyd),算法是求图中每一对结点之间最短路径算法。请描述该算法，而且回答：怎样用该算法判断图是否有回路？请说明理由,。,树与图,检验对角元,D,N 1,ii,，若存在非,对角元，就表明图中有回路。因为若,D,N 1,ii,非,，说明存在某个,k,，使得,D,k,ii,值被更新为,（,D,k 1,ik+D,k 1,ki,），即存在一条从,i,到,k,、再从,k,到,i,路径。,87/115,87,自测题,怎样判断图中有负回路（即回路中边权值之和为负数）？请说明理由,。,树与图,将对角元,Costii,初始化为,0,，当,D,k,ii0,时，图中必存在负回路。,88/115,88,查找与排序,查找,概念：,静态查找,动态查找（随时插入删除）,平均查找长度,=,P,i,C,i,，其中,P,i,为查找第,i,个统计概率，满足,P,i,=1,；,C,i,是找到第,i,个统计需要比较次数。,当查找不成功情况也考虑在内时，,平均查找长度是（成功,+,不成功）平均查找长度。,89/115,89,查找,次序查找法：,逐一比较。,若对,n,个统计做等概率查找（即,P,i,=1,/n,），则平均查找长度为,不成功查找必定进行,n+1,次比较。设成功与不成功概率相同，都是,1/2n,，则平均查找长度为,缺点：效率低,优点：简单、适用面广,对结构无要求，不要求有序，也适合用于链表。,查找与排序,(n+1)/2,。,3(n+1)/4,。,90/115,90,查找,折半查找法：,有序,表查找,成功查找最多比较次数为,等概率成功查找平均查找长度为,优点：效率高,缺点：只适合用于有序表，且不适合用于线性链表,查找与排序,log,2,n+1,。,(1+1/n)log,2,(n+1)-1,。,91/115,91,查找,B,树：平衡多路查找树,查找与排序,1,11,1,27,1,39,3,47,53,64,1,99,1,18,2,43,78,1,35,每个结点至多有,m,棵子树；,若根不是叶子，则最少有,2,棵子树；,除根之外全部非叶子结点最少有,m/2,棵子树；,全部非叶子结点包含,(n,p,0,K,1,p,1,K,2,p,2,.,K,n,p,n,),其中,K,i,为关键字且有序（递增）,p,i,所指子树中所相关键字,K,n,。,全部叶子在同一层，为,NULL,。,47,23,在有,N,个关键字,m,阶,B,树上进行查找，从根结点到关键字所在结点路径上包括结点数不超出,92/115,92,查找,B,树：插入、删除,查找与排序,30,3 12,37,50,61 70,100,24,53 90,45,30,30,37,26,26 30,37,50,61 70,100,53 90,45,3 12,37,24,26,85,61 70,85,45,3 12,37,24,30,26,50,61,100,53,70,90,85,70,50,61,100,85,53,90,7,3,7,12,24,45,70,37,30,26,3,12,7,70,37,30,26,3,12,7,50,61,100,85,53,90,24,45,3 12,37,50,61 70,100,24,53 90,45,最小值,50,最小值,61,53,3,37,53,70,100,24,61 90,50,61,24,50,93/115,93,自测题,下面关于,m,阶,B,树说法正确是,（）,每个结点最少有两棵非空子树,树中每个结点至多有,m,一,1,个关键字,全部叶子在同一层上,当插入一个数据项引发,B,树结点分裂后，树长高一层,查找与排序,94/115,94,自测题,B-,树中叶子结点数,s,与关键字数,n,关系是,s=n/2,s=n-1,s=n+1,无法确定,查找与排序,设,B-,树第,i,个结点子树数为,Ci,，则该结点关键字数,Ni=Ci-1,。,对于有,k,个结点,B-,树：,n=Ni=(Ci-1)=Ci-k,每个结点（除根结点）都是一棵子树：,Ci=(k-1)+s,95/115,95,查找,散列,(Hash),表及其查找,关键问题：,设计哈希函数,处理同义词冲突,哈希函数：（,任一关键字等概率映射到任一地址哈希函数是均匀,(Uniform),）,各种方法（,p.253-256,，其中,key%p,最常见）,冲突处理,开放定址法：线性、二次（,）、伪随机探测再散列,再哈希法（冲突时计算另一个哈希函数地址）,链地址法（同义词链表）,查找与排序,96/115,96,查找,散列,(Hash),表及其查找,查找分析,装填因子,哈希表平均查找长度是,函数，而不是,n,函数,从非链地址处理冲突哈希表中,删除,一个统计，须在该统计位置上填入一个特殊符号，以免找不到在它之后填入同义词,对于预先知道且规模不大关键字集，应尽力设计不发生冲突完美哈希函数,查找与排序,97/115,97,自测题,下面关于哈希查找说法正确是,（）,哈希函数结构越复杂越好，因为这么随机性好，冲突小,除留余数法是全部哈希函数中最好,不存在尤其好与坏哈希函数，要视情况而定,若需在哈希表中删去一个元素，不论用何种方法处理冲突都只要简单将该元素删去即可,查找与排序,98/115,98,自测题,设有一组统计关键字为,19,，,14,，,23,，,1,，,68,，,20,，,84,，,27,，,55,，,11,，,10,，,79,，用链地址法结构散列表，散列函数为,H,（,key,）,=key MOD 13,，散列地址为,1,链中有几个统计？,1,2,3,4,查找与排序,99/115,99,自测题,设哈希表长,m,14,，哈希函数,H,（,key,）,key,11,。表中已经有,4,个结点：,addr(15)=4,，,addr(38)=5,，,addr(61)=6,，,addr(84)=7,，其余地址为空。假如用二次探测再散列处理冲突，关键字为,49,结点地址是,8,3,5,9,查找与排序,100/115,100,内部排序,概念,基本操作：比较,+,移动,存放方式：,数组：必须移动统计,静态链表：表排序，仅修改指针,数组,+,地址：地址排序，然后调整统计位置,稳定,排序法：关键字等值统计在排序前后先后位置不变,查找与排序,101/115,101,内部排序,插入排序,直接插入排序：理扑克牌过程。正序最快,O,(,n,),，逆序最慢,O,(,n,2,),，平均,O,(,n,2,),。,折半,插入排序：查找过程用“折半查找”，降低了比较次数，但移动次数不变，还是,O,(,n,2,),。,气泡排序,(bubble sort),每趟比较相临统计，最大值沉入水底。,复杂度与直接插入排序类似。,查找与排序,102/115,102,自测题,用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少是哪个？,94,32,40,90,80,46,21,69,32,40,21,46,69,94,90,80,21,32,46,40,80,69,90,94,90,69