数据结构期末重点复习题课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1,作业：,1,、简述逻辑结构和存储结构的联系？,2,、数据结构和数据类型有什么区别？,3,、分析以下算法的时间复杂度,void func(int n),int i=0,s=0;,while (sL.listsize),p24,while (i=L.elemi) i+;,for (j=L.length-1;j=i; j-) L.elemj+1=L.elemj;,L.elemi=x;,L.length+;,32023/9/8参考算法：Void insert (Sql,4,2024/9/2,顺序表算法设计练习：,试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表。（,a,1,a,2,a,n,）逆置为（,a,n,a,n-1,a,1,）。,42023/9/8顺序表算法设计练习：试写一个算法，实现顺序,5,2024/9/2,参考算法：,Void reverse (Sqlist &L),int i=0, j=L.length-1;,while (ij),L.elemi L.elemj;,i+;,j-;,52023/9/8参考算法：Void reverse (Sq,6,2024/9/2,顺序表算法设计练习：,试设计一个高效的算法，删除线性表,L,中所有值为,x,的元素。,62023/9/8顺序表算法设计练习：试设计一个高效的算法，,7,2024/9/2,参考算法：,Void deletelist (Sqlist &L, ElemType x),int count=0;,for (i=0;inext, r;,If (q!=Null) r=q-next;,Else return 0;,While (r!=Null & r-data!=x),p=q;,q=r;,r=r-next;,if (r!=Null),p-next=q-next;,free(q);,else return 0;,return 1;,92023/9/8参考算法：Int delx(Linklis,10,2024/9/2,链表算法设计练习：,设计一个算法，在带头结点的单链表,head,中删除一个,data,域值最小的结点，假设该结点唯一。,102023/9/8链表算法设计练习：设计一个算法，在带头结,11,2024/9/2,参考算法：,Void DelMinNode (Linklist head),Linklist p=head-next, pre=head;,Linklist minp, minpre;,Elemtype min=p-data;,minp=p;minpre=pre;,While (p!=NULL),I f (p-datadata),min=p-data;,minp=p;,minpre=pre;,pre=p;,p=p-next;,minpre-next=minp-next;,Free(minp); ,112023/9/8参考算法：Void DelMinNode,12,2024/9/2,1,、假设表达式中允许包含,3,种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。,Int match (char exp, int n),char stMaxsize;,int top=-1;,int i=0,tag=1;,while (idata=x;,if (rear=NULL),s-next=s;,rear=s;,else,s-next=rear-next;,rear-next=s;,rear=s ,132023/9/82、假设用一个循环单链表表示队列，并且只,14,2024/9/2,作业：,1,、设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。,2,、设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。,142023/9/8作业：,15,例：,设树,T,的度为,4,，其中度为,1,，,2,，,3,和,4,的结点个数分别为,4,，,2,，,1,，,1,则,T,中的叶子数为（ ）,A,5 B,6 C,7 D,8,提示：,因为每个结点都有一条枝指向它，分支数为,1*4+2*2+3*1+4*1,所有结点数为分支数,+1,，所以,1*4+2*2+3*1+4*1=4+2+1+1+x x=8,例：,若一棵二叉树具有,10,个度为,2,的结点，,5,个度为,1,的结点，则度为,0,的结点个数是（ ）,A,9 B,11 C,15 D,不确定,提示：,n,0,=n,2,+1,15例：设树T的度为4，其中度为1，2，3和4的结点个数分别,16,例,3,：已知某二叉树先序序列, ABHFDECKG ,和中序序列, HBDFAEKCG ,画出该二叉树。,HBDF,EKCG,A,EKCG,A,B,H,DF,EKCG,A,B,H,F,D,E,A,B,H,F,D,C,K,G,A,KCG,E,B,H,F,D,A,16例3：已知某二叉树先序序列 ABHFDECKG ,17,例,1,：统计二叉树中叶子结点的个数,Status CountLeaf (BiTree T, int & count) ,if ( T ) ,if ( (T-lchild =NULL) & (T-rchild =NULL), count + +; return OK; ,CountLeaf( T - lchild, count);,/,统计左子树中叶子结点个数,CountLeaf( T - rchild, count);,/,统计右子树中叶子结点个数,else return ERROR;,17例1：统计二叉树中叶子结点的个数Status Count,18,例,2,：求二叉树的深度,int Depth (BiTree T ) ,if ( !T ) depthval = 0;,else ,depthLeft = Depth( T-lchild );,depthRight= Depth( T-rchild );,depthval = 1 + max(depthLeft,depthRight);,return depthval;,18例2：求二叉树的深度int Depth (BiTree,19,例,3,：按先序序列建立二叉树的二叉链表,已知先序序列：,A B C 0 0 D E 0 G 0 0 F 0 0 0,（其中,0,表示空格字符,空指针）建立相应的二叉链表,A,B,C,D,E,F,G,19例3：按先序序列建立二叉树的二叉链表已知先序序列：A B,20,例：,对于前序遍历与中序遍历结果相同的二叉树（ ）,;,对于前序遍历和后序遍历结果相同的二叉树为（ ）。,A,一般二叉树,B,只有根结点的二叉树,C,根结点无左孩子的二叉树,D,根结点无右孩子的二叉树,E,所有结点只有左子数的二叉树,F,所有结点只有右子树的二叉树,例：,某二叉树的前序序列和后序序列正好相反，则该二叉树,一定是（）的二叉树。,A,空或只有一个结点,B,任一结点无左子树,C,高度等于其结点数,D,任一结点无右子树,F,B,20例：对于前序遍历与中序遍历结果相同的二叉树（ ）;FB,21,例： 一棵左子树为空的二叉树在先序线索化后，其中空的链,域的个数是：,( ),A,不确定,B. 0 C. 1 D. 2,例： 一棵左右子树均不空的二叉树在先序线索化后，其中空,的链域的个数是：,( ),。,A. 0 B. 1 C. 2 D.,不确定,左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共,2,个空链域,只有最后一个叶结点没有后继,21例： 一棵左子树为空的二叉树在先序线索化后，其中空的链,22,例： 线索二叉树是一种（ ）结构。,A, 逻辑,B, 逻辑和存储,C, 物理,D,线性,例：,n,个结点的线索二叉树上含有的线索数为（ ）,A,2n B,n,1 C,n,1 D,n,N,个结点共有,2n,个指针域，二叉链表用了,n-1,个，剩下,n+1,个,22N个结点共有2n个指针域，二叉链表用了n-1个，剩下,23,练习：写出下图所示树的先序和后序遍历序列并将之转换成一棵二叉树,A,B,C,D,E,F,H,G,I,先根遍历：,ABDEGHICF,后根遍历：,DGHIEBFCA,A,B,G,D,C,F,H,E,I,23练习：写出下图所示树的先序和后序遍历序列并将之转换成一棵,24,6.4.2,森林和二叉树的转换规则,设森林,F=T,1,T,2,T,m,，二叉树,B=,（,root,，,LB,，,RB,）,(1),森林转化成二叉树的规则,若,F,为空,(m = 0),，,B,为空,;,若,F,不空,(m0),，,B,的根,root(B),是,F,中第一棵树,T,1,的根,root (T,1,),；,左子树,LB,从,T,1,根结点的子树森林,(T,11, T,12, , T,1m,),转换来；,右子树,RB,是从森林,F=T,2, T,3, , T,m,转换而来。,(2),二叉树转换为森林的规则,若,B,为空，,F,为空；,若,B,非空，则,F,中第一棵树,T,1,的根为二叉树的根,root(B),；,T,1,根的子树森林,F,1,由,B,的左子树,LB,转换而来；,F,中除,T,1,外其余树组成的森林,F= T,2, T,3, , T,n,由,B,的右子树,RB,转换而来。,246.4.2 森林和二叉树的转换规则设森林F=T1,T,25,森林转换成二叉树,步骤,1,：转换将各棵树分别转换成二叉树,步骤,2,：加线将每棵树的根结点用线相连,步骤,3,：旋转,以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树,A,B,C,D,E,F,G,H,I,J,森林,F,A,B,C,D,E,F,G,H,I,J,F,中每棵树对应的二叉树,25森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树A,26,森林转换成二叉树,步骤,1,：转换将各棵树分别转换成二叉树,步骤,2,：加线将每棵树的根结点用线相连,步骤,3,：旋转,以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,森林,F,26森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树A,27,森林转换成二叉树,步骤,1,：转换将各棵树分别转换成二叉树,步骤,2,：加线将每棵树的根结点用线相连,步骤,3,：旋转,以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,森林,F,F,转换的二叉树,B,A,B,C,D,E,F,G,H,I,J,27森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树A,28,二叉树转换成森林,步骤,1,：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树,步骤,2,：还原将孤立的二叉树还原成树,二叉树,B,A,B,C,D,E,F,G,H,I,J,28二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连,29,二叉树转换成森林,步骤,1,：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树,步骤,2,：还原将孤立的二叉树还原成树,二叉树,B,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,29二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连,30,二叉树转换成森林,步骤,1,：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树,步骤,2,：还原将孤立的二叉树还原成树,A,B,C,D,E,F,G,H,I,J,二叉树,B,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,30二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连,31,二叉树转换成森林,步骤,1,：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树,步骤,2,：还原将孤立的二叉树还原成树,B,转换成的森林,F,二叉树,B,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,31二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连,32,练习：写出下图所示森林的先序和中序遍历序列并将之转换成一棵二叉树,E,A,B,C,D,F,I,J,H,G,K,先序遍历：,中序遍历：,ABCDEFIKJGH,BEFDCIAJGHK,32练习：写出下图所示森林的先序和中序遍历序列并将之转换成一,33,例：设,F,是一个森林，,B,是由,F,变换得的二叉树。若,中有,n,个非终端结点，则,B,中右指针域为空的结点有,（ ）个。,A,n-1 B,n C,n+1 D,n+2,每一个非终端结点的孩子中都会贡献出一个空的右指针,例：设,F,是由,T1,T2,T3,三棵树组成的森林,与,F,对应的二叉树为,B,已知,T1,T2,T3,的结点数分别为,n1,n2,和,n3,则二叉树,B,的左子树中有,个结点，右子树中有,个结点。,n1-1,n2+n3,33例：设F是一个森林，B是由F变换得的二叉树。若每一个非终,34,构造最优二叉树的说明,1,在选取两棵根结点权值为最小和次小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中任选一棵。,2,当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时，谁是左子树谁是右子树没有特殊规定。,3,在最优二叉树中没有度为,1,的结点，根据二叉树的性质,3,可知有,n,个叶子结点的二叉树,有,n-1,个非终端结点共有,2*n-1,个结点。,a,7,b,5,c,2,d,4,6,11,18,a,7,b,5,d,4,c,2,6,11,18,34构造最优二叉树的说明1 在选取两棵根结点权值为最小和次小,35,如何得到最短的二进制前缀码（赫夫曼编码）？,为了设计电文总长最短的二进制前缀编码，以,n,种字符出现的频率作权，设计一棵赫夫曼树，从根节点至即所有叶子节点，按左分支为,0,，右分支为,1,的原则即可得到最短二进制前缀编码即赫夫曼编码。,例：已知某系统在通信联络中只可能出现,8,种字符，其概率为,0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,设计赫夫曼编码。,解：设权,w=(5,，,29,，,7,，,8,，,14,，,23,，,3,，,11),35如何得到最短的二进制前缀码（赫夫曼编码）？,36,0,23,14,11,5,29,3,7,8,0,0,0,0,0,0,1,1,1,1,1,1,1,100,58,42,8,29,15,19,编码：,3,（,0111,）,5,（,0110,）,7,（,1110,）,8,（,1111,）,11,（,010,）,14,（,110,）,23,（,00,）,29,（,10,）,360231411529378000000111111110,37,练习：,用于通信的电文由,8,个字母,c1, c2, c3, c4, c5, c6, c7, c8,组成,各字母在电文中出现的频率分别为,5, 25, 3, 6, 10, 11, 36, 4,。试,设计不等长,Huffman,编码,并给出该电文的总码数。,0000 0001 001 0100 0101,011 10 11,电文总码数,=4*5+2*25+4*3+4*6+ 3*10+3*11+2*36+4*4= 257,37练习：0000 0001 001,38,2024/9/2,练习,（,1,）设无向图的顶点个数为,n,，则该图最多有（ ）条边。,（,2,）一个有,n,个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。,（,3,）在一个无向图中，所有顶点的度数之和等于所有边数的,_,倍。,（,4,）要连通具有,n,个顶点的有向图，至少需要（ ）条边。,（,5,）若无向图,G=,（,V,，,E,）中含,7,个顶点，则保证图,G,在任何情况下都是连通的，则需要的边数最少是（ ）。,382023/9/8练习,39,2024/9/2,无向图,邻接表表示,V,1,V,2,V,4,V,5,V,3,顶点的度：该顶点所在单链表中表结点个数,V,1,V,2,V,3,V,4,V,5,0,1,2,3,4,1,3,0,4,2,0,2,1,2,1,4,3,与顶点,V,1,相邻接的顶点在数组中的下标,392023/9/8无向图邻接表表示V1V2 V4 V5 V,40,2024/9/2,V,1,V,2,V,4,V,5,V,3,2,5,4,3,1,1,邻接表表示,V,1,V,2,V,3,V,4,V,5,0,1,2,3,4,1,2,3,4,0,2,4,5,2,1,1,1,4,1,3,3,0,4,2,3,1,5,2,1,权值,无向网,402023/9/8V1V2 V4 V5 V3 254311,41,2024/9/2,V,1,V,2,V,3,V,4,邻接表表示,1,2,V,1,V,2,V,3,V,4,0,1,2,3,3,0,以顶点,V,1,为始点的弧的终点顶点在数组中的下标,顶点的出度,该顶点所在单链表中表结点个数,顶点的入度,查询整个邻接表中的表结点，与该顶点的序号（数组,下标）一致的表结点个数,有向图,412023/9/8V1V2 V3 V4 邻接表表示12V,42,2024/9/2,图的邻接表表示,问题：具有,n,个顶点,e,条边的无向图的邻接表中有多少个表头结点？有多个表结点（边结点）？,有向图呢？,422023/9/8图的邻接表表示问题：具有n个顶点e条边的,43,2024/9/2,练习,:,请画出下图的邻接矩阵和邻接表,432023/9/8练习: 请画出下图的邻接矩阵和邻接表,44,2024/9/2,7.3.1,深度优先搜索,-,举例,1,2,3,4,V,1,V,3,V,4,V,2,data,firstarc,2,7,8,3,adjvex,nextarc,5,V,5,6,4,1,5,1,2,8,2,V,6,V,7,V,8,6,7,8,7,3,6,3,5,4,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,深度遍历：,V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,给定存储结构，图的遍历序列唯一,442023/9/87.3.1 深度优先搜索-举例1234V,45,2024/9/2,7.3.2,广度优先搜索,-,举例,广度遍历：,V,1, V,3,V,2, V,7,V,6,V,5,V,4,V,8,1,2,3,4,V,1,V,3,V,4,V,2,data,firstarc,2,7,8,3,adjvex,nextarc,5,V,5,6,4,1,5,1,2,8,2,V,6,V,7,V,8,6,7,8,7,3,6,3,5,4,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,给定存储结构，图的遍历序列唯一,452023/9/87.3.2 广度优先搜索-举例广度遍历：,46,2024/9/2,下列有关图遍历的说法中不正确的是（）,A,连通图的深度优先搜索是一个递归过程,B,图的广度优先搜索中邻接点的寻找具有“先进先出”的特征,C.,图的遍历要求每一顶点仅被访问一次,D,对图进行一次深度优先遍历可以访问图中所有顶点,462023/9/8下列有关图遍历的说法中不正确的是（）,47,2024/9/2,给定有向图如下：,给出其邻接表存储结构,基于邻接表，给出,DFS,序列和,BFS,序列,472023/9/8给定有向图如下： 给出其邻接表存储结构,48,2024/9/2,练习：,已知一个图的顶点集,V,和边集,E,分别为：,V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;,用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。,【,答,】,用克鲁斯卡尔算法得到的最小生成树为：,(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20,482023/9/8练习：已知一个图的顶点集V和边集E分别为,49,2024/9/2,练习：,设有无向图,G,，要求给出用普里姆算法构造最小生成树所走过的边的集合。,【,答,】E=(1,，,3),，,(1,，,2),，,(3,，,5),，,(5,，,6),，,(6,，,4),492023/9/8练习：设有无向图G，要求给出用普里姆算法,50,2024/9/2,7.5.1,拓扑排序,-,实现步骤,C,1,C,3,C,2,C,7,C,5,C,6,C,4,C,1,C,3,C,2,C,7,C,5,C,6,C,4,拓扑有序序列：,C,1,=,C,3,=,C,2,=,C,4,=,C,6,=,C,5,=,C,7,逻辑结构上：拓扑序列不唯一,502023/9/87.5.1 拓扑排序-实现步骤C1C3,51,2024/9/2,7.5.2,关键路径,AOE-,网,(Active On Edge),：,在带权的有向无环图中，顶点表示事件，弧表示工程的一个活动，弧上权值表示活动持续的时间。用来估算工程完成时间。,源点：入度为,0,的顶点。汇点：出度为,0,的顶点。,路径长度：,AOE,网中路径上各活动持续时间之和。,关键路径：路径长度最长的路径。,V,1,V,3,V,4,V,6,V,5,V,8,V,2,V,7,V,9,a,1,=6,a,7,=9,a,5,=1,a,2,=4,a,4,=1,a,10,=2,a,3,=5,a,6,=2,a,9,=4,a,11,=4,a,8,=7,说明：,（,1,）完成工程的最短时间是从开始点到完成点的最长路径的长度。,（,2,）关键路径的改变会影响整个工期。,512023/9/87.5.2 关键路径 AOE-网(,52,2024/9/2,设活动,a,i,在有向无环图,G,的有向边,上：,事件,v,j,的最早发生时间,ve(j):,从源点,v,0,到,v,j,的最长路径长度。,ve(0)=0;,ve(j)=,从源点到顶点,j,的最长的路径长度。,ve(k)=Maxve(j)+dut(),事件,v,j,的最迟开始时间,vl(j),：保证汇点,v,n-1,在,ve(n-1),时刻完成的前提下，事件,v,j,最迟允许开始的时间。,vl(n-1) = ve(n-1),从源点到汇点的最长路径长度,;,vl(k)=,从汇点到顶点,k,的最短的路径长度。,vl(j)=Minvl(k)-dut(),k,j,dut(),a,i,7.5.2,关键路径,定义和术语,522023/9/8设活动ai在有向无环图G的有向边lchild=NULL,45,53,90,24,12,p,f,45,53,90,24,f,例：删除叶子结点,12,612023/9/89.2.1 二叉排序树-删除1） 被删除,62,2024/9/2,9.2.1,二叉排序树,-,删除,2,） 被删除的结点,p,只有左子树或者只有右子树：令,P,L,或,P,R,直接为其双亲结点,f,的左子树即可，,f-lchild=p-lchild|p-rchild,。,45,53,90,24,12,p,f,45,53,90,12,f,例：删除结点,24,622023/9/89.2.1 二叉排序树-删除2） 被删除,63,2024/9/2,9.2.1,二叉排序树,-,删除,3,）被删除的结点既有左子树，也有右子树。在删去,p,结点前，中序遍历该二叉树得到的序列为,C,L,CQ,L,QS,L,SPP,R,F,，即,S,是中序遍历序列中被删结点,p,的直接前驱结点。,方法一：令,P,的左子树为,F,的左子树，,P,的右子树为,S,的右子树,F,P,P,L,P,R,F,P,C,Q,S,P,R,C,L,Q,L,S,L,F,C,Q,S,P,R,C,L,Q,L,S,L,632023/9/89.2.1 二叉排序树-删除3）被删除的,64,2024/9/2,9.2.1,二叉排序树,-,删除,3,）被删除的结点既有左子树，也有右子树。在删去,p,结点前，中序遍历该二叉树得到的序列为,C,L,CQ,L,QS,L,SPP,R,F,，即,S,是中序遍历序列中被删结点,p,的直接前驱结点。,方法二：令,p,的直接前驱,S,替代,p,，再从二叉排序树中删去,S,。,F,P,P,L,P,R,F,P,C,Q,S,P,R,C,L,Q,L,S,L,F,S,C,Q,P,R,C,L,Q,L,S,L,642023/9/89.2.1 二叉排序树-删除3）被删除的,65,2024/9/2,9.2.1,二叉排序树,-,删除举例,删除,45,45,53,12,37,3,24,100,61,90,78,45,12,37,3,24,53,100,61,90,78,652023/9/89.2.1 二叉排序树-删除举例删除45,66,2024/9/2,9.2.1,二叉排序树,-,删除举例,删除,45,45,12,3,37,24,53,100,61,90,78,37,45,53,12,37,3,24,100,61,90,78,662023/9/89.2.1 二叉排序树-删除举例删除45,67,2024/9/2,练习：,假定一棵二叉排序树采用二叉链表存储结构，其根结点指针为,T,设计一个算法输出该二叉排序树中最大的键值和最小的键值。,672023/9/8练习：,68,2024/9/2,status maxmindata(),if (!T ) return error;,p=q=T;,while (p-lchild!=NULL),p=p-lchild;,printf(“The minimum data is:%d”, p-data);,while (q-rchild!=NULL),q=q-rchild;,printf(“The minimum data is:%d”, q-data);,682023/9/8status maxmindata(),69,2024/9/2,9.3,哈希表,查找表的特点：,记录的关键字和在结构中的位置之间无确定关系,查找过程是给定值依次和关键字集合中各个关键字的比较,查找效率取决于和给定值进行比较的关键字个数。,希望不经比较，直接可以找到所查记录,哈希函数：在记录的关键字和其在表中位置之间建立一种,函数关系，即以,f(key),作为关键字为,key,的记录在表中的位,置。,692023/9/89.3 哈希表查找表的特点：,70,2024/9/2,9.3,哈希表定义和术语,冲突：不同关键字得到同一哈希地址，,key1,key2,，,f(key1)=f(key2),同义词：在一个哈希函数中具有相同函数值的不同关键字。,哈希表：根据设定的哈希函数,H(key),和所选中的处理冲突的方,法，将一组关键字映象到一个有限的、地址连续的地址集,(,区,间,),上，并以关键字在地址集中的,“,象,”,作为相应记录在表中的存,储位置，这种表被称为哈希表。,哈希造表或散列：映象过程。,哈希地址或散列地址：所得的存储位置。,构造哈希表要注意的问题：,考虑选择一个,“,好,”,的哈希函数,;,选择一种处理冲突的方法。,702023/9/89.3 哈希表定义和术语冲突：不同关键字,71,2024/9/2,9.3.3,处理冲突的方法,1,开放定址法：,H,i,=(H(key)+d,i,) MOD m i=1,2,k (km-1),，,H(key),为哈希函数；,m,：哈希表长，,d,i,是增量序列， 有三种取法,d,i,=1,2,m-1,，称为线性探测再散列,d,i,=1,2,-1,2,2,2,-2,2,k,2,(km/2),称为二次探测再散列,d,i,=,伪随机数列，称为随机探测再散列,712023/9/89.3.3 处理冲突的方法1 开放定址法,72,2024/9/2,处理冲突方法举例,例：一组关键字,19,14,23,01,68,20,84,27,55,11,10,79,；按,H(key)=key mod 13,和线性探测再散列方法处理冲突构造表长,为,16,的哈希表。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,3,1,1,9,3,1,1,3,4,1,2,1,比较次数,2,0,0,8,2,0,0,2,3,0,1,0,冲突次数,ASLss=1/12,（,1*6+2+3*3+4+9,）,=2.5,14,01,68,27,55,19,20,84,79,23,11,10,722023/9/8处理冲突方法举例例：一组关键字19,14,73,2024/9/2,9.3.3,处理冲突的方法,例：,用哈希函数,H(key)=key MOD 13,和链地址法处理冲突求一组关键字,19,14,23,01,68,20,84,27,55,11,10,79,的哈希表：,0,1,2,3,4,5,6,7,8,9,10,11,12,01,14,27,79,55,68,19,84,10,23,11,20,ASL,ss,=1/12(1*6+2*4+3+4)=1.75,732023/9/89.3.3 处理冲突的方法例：用哈希函数,74,2024/9/2,练习：,已知关键字序列为：（,75,33,52,41,12,88,66,27,），哈希表长为,10,，哈希函数为：,H(k),k%9,，解决冲突用线性探测法，请：,（,1,）构造出哈希表；,（,2,）计算等概率下查找成功的平均查找长度。,742023/9/8练习：已知关键字序列为：（75,33,5,75,2024/9/2,Typedef struct LNode ,ElemType data; /,数据域,struct,Lnode,*,next; /,指针域,LNode,*LinkList,;,二、结点和单链表的,C,语言描述,LinkList L,；,/ L,为单链表的头指针,752023/9/8 Typedef struct,76,2024/9/2,Typedef struct LNode ,ElemType data; /,数据域,struct,Lnode,*,next; /,指针域,LNode,*LinkList,;,二、结点和单链表的,C,语言描述,LinkList L,；,/ L,为单链表的头指针,762023/9/8 Typedef struct,77,2024/9/2,三、单链表操作的实现,GetElem(L, i, &e) /,取第,i,个数据元素,ListInsert(&L, i, e) /,插入,数据元素,ListDelete(&L, i, e) /,删除,数据元素,ClearList(&L) /,重置线性表为空表,CreateList(&L, n) /,生成含,n,个数据元素的链表,772023/9/8三、单链表操作的实现GetElem(L,78,2024/9/2,L,线性表的操作,GetElem(L, i, &e),在单链表中的实现,:,21,18,30,75,42,56,p,p,p,j,1,2,3,782023/9/8L 线性表的操作 211830,79,2024/9/2,因此，查找第,i,个数据元素的基本操作为：移动指针，比较,j,和,i,。,单链表是一种顺序存取的结构，为找第,i,个数据元素，必须先找到第,i-1,个数据元素。,令指针,p,始终指向线性表中第,j,个数据元素。,792023/9/8 因此，查找第 i 个数据元素的基本操,80,2024/9/2,Status,GetElem_L(LinkList L,int,i, ElemType,&,e),/ L,是带头结点的链表的头指针，以,e,返回第,i,个元素,/ GetElem_L,算法时间复杂度为,:,O(ListLength(L),p = L-next; j = 1; /,p,指向第一个结点，,j,为计数器,while (p ,/,顺指针向后查找，直到,p,指向第,i,个元素,/,或,p,为空,if,(,!,p | ji ),return,ERROR; /,第,i,个元素不存在,e = p-data; /,取得第,i,个元素,return,OK;,802023/9/8 Status GetElem_L(Li,81,2024/9/2,a,i-1,线性表的操作,ListInsert(&L, i, e),在单链表中的实现,：,有序对,改变为,和,e,a,i,a,i-1,812023/9/8ai-1 线性表的操作 ListInse,82,2024/9/2,因此，在单链表中第,i,个结点之前进行插入的基本操作为,:,找到线性表中第,i-1,个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但同时，若要在第,i,个结点之前插入元素，修改的是第,i-1,个结点的指针。,822023/9/8 因此，在单链表中第 i 个结点之,83,2024/9/2,Status,ListInsert_L(LinkList L,int,i, ElemType e),/,L,为带头结点的单链表的头指针，本算法,/,在链表中第,i,个结点之前插入新的元素,e,/ LinstInsert_L,算法的时间复杂度,为,:,O(ListLength(L),p = L; j = 0;,while,(p,&,j next; +j;,/,寻找第,i-1,个结点,if,(,!,p,|,j i-1),return,ERROR; /,i,大于表长或者小于,1,832023/9/8 Status ListInsert_,84,2024/9/2,s = (LinkList),malloc,(,sizeof,(LNode);,/,生成新结点,s,-,data = e;,s-next = p-next; p,-,next = s; /,插入,return,OK;,e,a,i-1,a,i,a,i-1,s,p,842023/9/8s = (LinkList) mallo,85,2024/9/2,线性表的操作,ListDelete (&L, i, &e),在链表中的实现,:,有序对,和,改变为,a,i-1,a,i,a,i+1,a,i-1,852023/9/8线性表的操作ListDelete (&L,86,2024/9/2,在单链表中,删除第,i,个结点,的,基本操作,为,:,找到线性表中第,i-1,个结点，修改其指向后继的指针。,a,i-1,a,i,a,i+1,a,i-1,q = p-next; p-next = q-next;,e = q-data;,free(q);,p,q,862023/9/8 在单链表中删除第 i 个结点的基本,87,2024/9/2,Status,ListDelete_L(LinkList L,int,i, ElemType,&,e),/,删除以,L,为头指针,(,带头结点,),的单链表中第,i,个结点,/ ListDelete_L,算法的时间复杂度,为,:,O(ListLength(L),p = L; j = 0;,while,(p-next,&,j next; +j;,/,寻找第,i,个结点，并令,p,指向其前趋,if,(,!,(p-next) | j i-1),return,ERROR; /,删除位置不合理,q = p-next; p-next = q-next;,/,删除并释放结点,e = q-data;,free(q);,return,OK;,872023/9/8 Status ListDelete_L,88,2024/9/2,操