数据结构期末重点复习题.pptx

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

1、12023/3/16顺序表算法设计练习：已知一个顺序表L，其中的元素递增有序排列，设计一个算法插入一个元素x后保持该顺序表仍递增有序排列。第1页/共105页22023/3/16参考算法：Voidinsert(Sqlist&L,ElemTypex)inti=0,j;if(L.length+1L.listsize)p24while(i=L.elemi)i+;for(j=L.length-1;j=i;j-)L.elemj+1=L.elemj;L.elemi=x;L.length+;第2页/共105页32023/3/16顺序表算法设计练习：试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性

2、表。（a1,a2,an）逆置为（an,an-1,a1）。第3页/共105页42023/3/16参考算法：Voidreverse(Sqlist&L)inti=0,j=L.length-1;while(ij)L.elemiL.elemj;i+;j-;第4页/共105页52023/3/16顺序表算法设计练习：试设计一个高效的算法，删除线性表L中所有值为x的元素。第5页/共105页62023/3/16参考算法：Voiddeletelist(Sqlist&L,ElemTypex)intcount=0;for(i=0;inext,r;If(q!=Null)r=q-next;Elsereturn0;Whil

3、e(r!=Null&r-data!=x)p=q;q=r;r=r-next;if(r!=Null)p-next=q-next;free(q);elsereturn0;return1;第8页/共105页92023/3/16链表算法设计练习：设计一个算法，在带头结点的单链表head中删除一个data域值最小的结点，假设该结点唯一。第9页/共105页102023/3/16参考算法：VoidDelMinNode(Linklisthead)Linklistp=head-next,pre=head;Linklistminp,minpre;Elemtypemin=p-data;minp=p;minpre=pr

4、e;While(p!=NULL)If(p-datadata)min=p-data;minp=p;minpre=pre;pre=p;p=p-next;minpre-next=minp-next;Free(minp);第10页/共105页112023/3/161、假设表达式中允许包含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;elses-ne

5、xt=rear-next;rear-next=s;rear=s第12页/共105页132023/3/16作业：作业：1、设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。2、设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。第13页/共105页14例：例：设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A5 B6 C7 D8提示：提示：因为每个结点都有一条枝指向它，分支数为1*4+2*2+3*1+4*1所有结点数为分支数+1，所以1*4+2*2

6、+3*1+4*1=4+2+1+1+x x=8例：例：若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A9 B11 C15 D不确定提示：提示：n0=n2+1第14页/共105页15例3：已知某二叉树先序序列 ABHFDECKG 和中序序列 HBDFAEKCG,画出该二叉树。HBDFEKCGAEKCGABHDFEKCGABHFDEABHFDCKGAKCGEBHFDA第15页/共105页16例1：统计二叉树中叶子结点的个数Status CountLeaf(BiTree T,int&count)if(T)if(T-lchild=NULL)&(T-rchild=NULL)

7、count+;return OK;CountLeaf(T-lchild,count);/统计左子树中叶子结点个数 CountLeaf(T-rchild,count);/统计右子树中叶子结点个数 else return ERROR;第16页/共105页17例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;第17页/共105页18例3：按

8、先序序列建立二叉树的二叉链表已知先序序列：A B C 0 0 D E 0 G 0 0 F 0 0 0（其中0表示空格字符,空指针）建立相应的二叉链表ABCDEFG第18页/共105页19例：例：对于前序遍历与中序遍历结果相同的二叉树（）;对于前序遍历和后序遍历结果相同的二叉树为（）。A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树例：例：某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树FB第19页/共

9、105页20例：一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：()A不确定 B.0 C.1 D.2 例：一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：()。A.0 B.1 C.2 D.不确定 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域只有最后一个叶结点没有后继第20页/共105页21例：线索二叉树是一种（）结构。A 逻辑 B 逻辑和存储 C 物理 D线性例：n个结点的线索二叉树上含有的线索数为（）A2n Bn1 Cn1 Dn N个结点共有2n个指针域，二叉链表用了n-1个，剩下n+1个第21页/共10

10、5页22练习：写出下图所示树的先序和后序遍历序列并将之转换成一棵二叉树ABCDEFHGI先根遍历：先根遍历：ABDEGHICF后根遍历：后根遍历：DGHIEBFCAABGDCFHEI第22页/共105页236.4.2 6.4.2 森林和二叉树的转换规则设森林F=T1,T2,Tm，二叉树B=（root，LB，RB）(1)森林转化成二叉树的规则 若F为空(m=0)，B为空;若F不空(m0)，B的根root(B)是F中第一棵树T1的根root(T1)；左子树LB从T1根结点的子树森林(T11,T12,T1m)转换来；右子树RB是从森林F=T2,T3,Tm 转换而来。(2)二叉树转换为森林的规则 若B

11、为空，F为空；若B非空，则F中第一棵树T1的根为二叉树的根root(B)；T1根的子树森林F1由B的左子树LB转换而来；F 中除 T1 外其余树组成的森林F=T2,T3,Tn 由B 的右子树 RB 转换而来。第23页/共105页24森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树步骤2：加线将每棵树的根结点用线相连步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJ森林森林F FABCDEFGHIJF F中每棵树对应的二叉树中每棵树对应的二叉树第24页/共105页25森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树步骤2：加线将每棵树的

12、根结点用线相连步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林森林F F第25页/共105页26森林转换成二叉树步骤1：转换将各棵树分别转换成二叉树步骤2：加线将每棵树的根结点用线相连步骤3：旋转以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林森林F FF F转换的二叉树转换的二叉树B BABCDEFGHIJ第26页/共105页27二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤

13、2：还原将孤立的二叉树还原成树二叉树二叉树B BABCDEFGHIJ第27页/共105页28二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树二叉树二叉树B BABCDEFGHIJABCDEFGHIJ第28页/共105页29二叉树转换成森林步骤1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树ABCDEFGHIJ二叉树二叉树B BABCDEFGHIJABCDEFGHIJ第29页/共105页30二叉树转换成森林步骤

14、1：抹线将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原将孤立的二叉树还原成树B B转换成的森林转换成的森林F F二叉树二叉树B BABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第30页/共105页31练习：写出下图所示森林的先序和中序遍历序列并将之转换成一棵二叉树EABCDFIJHGK先序遍历：先序遍历：中序遍历：中序遍历：ABCDEFIKJGHBEFDCIAJGHK第31页/共105页32例：设F是一个森林，B是由F变换得的二叉树。若中有n个非终端结点，则B中右指针域为空的结点有（）个。A n-1 Bn

15、 C n+1 D n+2 每一个非终端结点的孩子中都会贡献出一个空的右指针例：设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有个结点，右子树中有个结点。n1-1n2+n3第32页/共105页33构造最优二叉树的说明1 在选取两棵根结点权值为最小和次小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中任选一棵。2 当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时，谁是左子树谁是右子树没有特殊规定。3 在最优二叉树中没有度为1的结点，根据二叉树的性质3可知有n个叶子结点的二叉树有n-1个

16、非终端结点共有2*n-1个结点。a7b5c2d461118a7b5d4c261118第33页/共105页34如何得到最短的二进制前缀码（赫夫曼编码）？如何得到最短的二进制前缀码（赫夫曼编码）？为了设计电文总长最短的二进制前缀编码，以n种字符出现的频率作权，设计一棵赫夫曼树，从根节点至即所有叶子节点，按左分支为0，右分支为1的原则即可得到最短二进制前缀编码即赫夫曼编码。例：已知某系统在通信联络中只可能出现例：已知某系统在通信联络中只可能出现8种字符，其概率为种字符，其概率为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,设计赫夫曼编码。设计赫夫曼编码。解：设权解：

17、设权w=(5，29，7，8，14，23，3，11)第34页/共105页350231411529378000000111111110058428291519编码：编码：3（0111）5（0110）7（1110）8（1111）11（010）14（110）23（00）29（10）第35页/共105页36练习：用于通信的电文由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试设计不等长Huffman编码,并给出该电文的总码数。000000010010100010100000001001010001010111011011

18、1011电文总码数电文总码数=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257第36页/共105页372023/3/16练习练习（1）设无向图的顶点个数为n，则该图最多有（）条边。（2）一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。（3）在一个无向图中，所有顶点的度数之和等于所有边数的_倍。（4）要连通具有n个顶点的有向图，至少需要（）条边。（5）若无向图G=（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。第37页/共105页382023/3/16无向图邻接表表示V1V2V4V5V3顶点的度：该顶点所在单链表中表

19、结点个数V1V2V3V4V501234130420212143与顶点V1相邻接的顶点在数组中的下标第38页/共105页392023/3/16V1V2V4V5V3254311邻接表表示V1V2V3V4V501234123402452111413304231521权值无向网第39页/共105页402023/3/16V1V2V3V4邻接表表示12V1V2V3V4012330以顶点V1为始点的弧的终点顶点在数组中的下标顶点的出度该顶点所在单链表中表结点个数顶点的入度查询整个邻接表中的表结点，与该顶点的序号（数组下标）一致的表结点个数有向图第40页/共105页412023/3/16图的邻接表表示问题：具

20、有n个顶点e条边的无向图的邻接表中有多少个表头结点？有多个表结点（边结点）？有向图呢？第41页/共105页422023/3/16练习:请画出下图的邻接矩阵和邻接表第42页/共105页432023/3/167.3.1 7.3.1 深度优先搜索-举例1234V1V3V4V2data firstarc2783adjvexnextarc5V564151282V6V7V8678736354V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1V3 V7 V6 V2 V5 V8 V4给定存储结构，图的遍历序列唯一第43页/共105页442023/3/167.3.2 广度优先搜索-举例广度遍历：广度遍历：

21、V1 V3 V2 V7 V6 V5 V4 V81234V1V3V4V2data firstarc2783adjvexnextarc5V564151282V6V7V8678736354V1V2V4V5V3V7V6V8给定存储结构，图的遍历序列唯一第44页/共105页452023/3/16下列有关图遍历的说法中不正确的是（）A连通图的深度优先搜索是一个递归过程B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.图的遍历要求每一顶点仅被访问一次D对图进行一次深度优先遍历可以访问图中所有顶点第45页/共105页462023/3/16给定有向图如下：给出其邻接表存储结构 基于邻接表，给出DFS序列

22、和BFS序列第46页/共105页472023/3/16练习：已知一个图的顶点集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第47页/共105页482023/3/16练习：设有无向图G，要求给出用普里姆算法构造最小

23、生成树所走过的边的集合。【答】E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4)第48页/共105页492023/3/167.5.1 7.5.1 拓扑排序-实现步骤C1C3C2C7C5C6C4编号课程名称C1数学C2程序设计C3离散数学C4汇编程序设计C5数据结构C6结构程序设计C7编译原理C1C3C2C7C5C6C4拓扑有序序列：C1=C3=C2=C4=C6=C5=C7逻辑结构上：拓扑序列不唯一第49页/共105页502023/3/167.5.2 7.5.2 关键路径 AOE-网(Active On Edge)：在带权的有向无环图中，顶点表示事件，弧表示工程的一个活动，弧上权值表

24、示活动持续的时间。用来估算工程完成时间。源点：入度为0的顶点。汇点：出度为0的顶点。路径长度：AOE网中路径上各活动持续时间之和。关键路径：路径长度最长的路径。V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7说明：（1）完成工程的最短时间是从开始点到完成点的最长路径的长度。（2）关键路径的改变会影响整个工期。第50页/共105页512023/3/16设活动ai在有向无环图G的有向边上：事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。ve(0)=0;ve(j)=从源点到顶点j的最长的路径长度。ve(

25、k)=Maxve(j)+dut()事件vj的最迟开始时间vl(j)：保证汇点vn-1在ve(n-1)时刻完成的前提下，事件vj最迟允许开始的时间。vl(n-1)=ve(n-1)从源点到汇点的最长路径长度;vl(k)=从汇点到顶点k的最短的路径长度。vl(j)=Minvl(k)-dut()kj dut()ai7.5.2 7.5.2 关键路径定义和术语第51页/共105页522023/3/167.5.2 7.5.2 关键路径定义和术语设活动ai在有向边上,有：活动ai的最早开始时间e(i)：从源点v0到vj的最长路径长度。e(i)=ve(j);活动ai的最迟开始时间l(i)：是不推迟工程完成的前提

26、下，该活动允许的最迟开始时间。l(i)=vl(k)-dut()活动ai时间余量：l(i)-e(i)关键活动：满足l(i)=e(i)的活动。关键路径上的活动都是关键活动。kj dut()ai第52页/共105页532023/3/167.5.2 7.5.2 关键路径求关键活动关键活动关键活动e(i)=l(i)e(i)=ve(j)l(i)=vl(k)-dut()ve(j)、vl(j)求顶点（事件）vk的最早开始时间：从ve(0)=0向汇点方向递推求顶点（事件）vj的最迟开始时间：从vl(n-1)=ve(n-1)向源点递推V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a1

27、0=2a3=5a6=2a9=4a11=4a8=7ve(k)=Maxve(j)+dut()vl(j)=Minvl(k)-dut()在拓扑有序的前提下进行在逆拓扑有序前提下进行第53页/共105页542023/3/16由汇点至源点由汇点至源点由源点至汇点由源点至汇点1814161078660vl(i)181416775460ve(i)V9V8V7V6V5V4V3V2V1iV1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7关键路径是关键路径是V1,V2,V5,V7,V9和和V1,V2,V5,V8,V9ve(k)=Maxve

28、(j)+dut()vl(j)=Minvl(k)-dut()e(i)=ve(j);l(i)=vl(k)dut()14161077866320l(i)000000差1416777546000e(i)a11a10a9a8a7a6a5a4a3a2a1注意：关键路径可有多条。缩短工期必须缩短关键活动所需的时间第54页/共105页552023/3/16如何求关键路径？(算法思想)（1）输入e条弧，建立AOE网的存储结构；（2）从源点v0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei(1in-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止，

29、否则执行步骤（3）；（3）从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求余各顶点的最迟发生时间vli(n-2i2)（4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s).若某条弧满足条件e(s)=l(s),则为关键活动。第55页/共105页562023/3/16下列关于AOE网的叙述中，不正确的是（）A.关键活动不按期完成就会影响整个工程的完成时间B.某些关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.任何一个关键活动提前完成，那么整个工程将会提前完成第56页/共105页572023/3/169.2.1

30、 9.2.1 二叉排序树二叉排序树(二叉查找树）(Binary Sort Tree,BST)：空树或具有下列性质的二叉树:根的左子树若非空，则左子树上的所有结点的关键字值均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键字值均大于根结点的值。它的左右子树同样是二叉排序树。中序遍历二叉排序树可得到一个关键字的有序序列第57页/共105页582023/3/169.2.1 9.2.1 二叉排序树的插入例：序列45、24、53、12、90构成一棵二叉排序树建BST树过程：一个无序序列可以构造二叉排序树前提：查找失败插入的结点是一个叶子结点，且是查找失败时查找路径上访问的最后一个结点的左孩子

31、或右孩子。插入算法：二叉排序树的存储结构使用链表 首先执行查找算法，找出被插入结点的父亲结点。若二叉树为空。则首先单独生成根结点。判断被插结点是其父亲结点的左、右孩子。将结点插入4553902412第58页/共105页592023/3/169.2.1 9.2.1 二叉排序树-删除设二叉排序树上被删除结点是p，PL是p的左子树，PR是p的右子树，p的双亲结点是f，不失一般性，设p是f的左孩子。有三种情况：1)被删除的结点p是叶子结点；2)被删除的结点p只有左子树或者只有右子树；3)被删除的结点既有左子树，也有右子树。对二叉排序树，删去一个结点相当于删去有序序列中的一个记录。第59页/共105页6

32、02023/3/169.2.1 9.2.1 二叉排序树-删除1）被删除的结点p是叶子结点：修改双亲结点的指针，令 f-lchild=NULL4553902412pf45539024f例：删除叶子结点12第60页/共105页612023/3/169.2.1 9.2.1 二叉排序树-删除2）被删除的结点p只有左子树或者只有右子树：令PL或PR直接为其双亲结点f的左子树即可，f-lchild=p-lchild|p-rchild。4553902412pf45539012f例：删除结点24第61页/共105页622023/3/169.2.1 二叉排序树-删除3）被删除的结点既有左子树，也有右子树。在删去

33、p结点前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，即S是中序遍历序列中被删结点p的直接前驱结点。方法一：令P的左子树为F的左子树，P的右子树为S的右子树FPPLPRFPCQSPRCLQLSLFCQSPRCLQLSL第62页/共105页632023/3/169.2.1 二叉排序树-删除3）被删除的结点既有左子树，也有右子树。在删去p结点前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF，即S是中序遍历序列中被删结点p的直接前驱结点。方法二：令p的直接前驱S替代p，再从二叉排序树中删去S。FPPLPRFPCQSPRCLQLSLFSCQPRCLQLSL第63页/共105页64

34、2023/3/169.2.1 9.2.1 二叉排序树-删除举例删除454553123732410061907845123732453100619078第64页/共105页652023/3/169.2.1 9.2.1 二叉排序树-删除举例删除45451233724531006190783745531237324100619078第65页/共105页662023/3/16练习：假定一棵二叉排序树采用二叉链表存储结构，其根结点指针为T,设计一个算法输出该二叉排序树中最大的键值和最小的键值。第66页/共105页672023/3/16statusmaxmindata()if(!T)returnerror

35、;p=q=T;while(p-lchild!=NULL)p=p-lchild;printf(“Theminimumdatais:%d”,p-data);while(q-rchild!=NULL)q=q-rchild;printf(“Theminimumdatais:%d”,q-data);第67页/共105页682023/3/169.3 9.3 哈希表查找表的特点：记录的关键字和在结构中的位置之间无确定关系查找过程是给定值依次和关键字集合中各个关键字的比较查找效率取决于和给定值进行比较的关键字个数。希望不经比较，直接可以找到所查记录哈希函数：在记录的关键字和其在表中位置之间建立一种函数关系，即

36、以f(key)作为关键字为key的记录在表中的位置。第68页/共105页692023/3/169.3 9.3 哈希表定义和术语冲突：不同关键字得到同一哈希地址，key1key2，f(key1)=f(key2)同义词：在一个哈希函数中具有相同函数值的不同关键字。哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。哈希造表或散列：映象过程。哈希地址或散列地址：所得的存储位置。构造哈希表要注意的问题：考虑选择一个“好”的哈希函数;选择一种处理冲突的方法。

37、第69页/共105页702023/3/169.3.3 9.3.3 处理冲突的方法1开放定址法：Hi=(H(key)+di)MODmi=1,2,k(km-1)，H(key)为哈希函数；m：哈希表长，di是增量序列，有三种取法di=1,2,m-1，称为线性探测再散列di=12,-12,22,-22,k2(km/2)称为二次探测再散列di=伪随机数列，称为随机探测再散列第70页/共105页712023/3/16处理冲突方法举例例：一组关键字19,14,23,01,68,20,84,27,55,11,10,79；按H(key)=key mod 13和线性探测再散列方法处理冲突构造表长为16的哈希表。0

38、 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15311931134121比较次数200820023010冲突次数ASLss=1/12（1*6+2+3*3+4+9）=2.5 14 0168 27551920847923 11 10第71页/共105页722023/3/169.3.3 9.3.3 处理冲突的方法例：用哈希函数H(key)=keyMOD13和链地址法处理冲突求一组关键字19,14,23,01,68,20,84,27,55,11,10,79的哈希表：0123456789101112 01142779 5568 1984 1023 11 20 ASLss=1/12

39、(1*6+2*4+3+4)=1.75第72页/共105页732023/3/16练习：已知关键字序列为：（75,33,52,41,12,88,66,27），哈希表长为10，哈希函数为：H(k)k%9，解决冲突用线性探测法，请：（1）构造出哈希表；（2）计算等概率下查找成功的平均查找长度。第73页/共105页742023/3/16 Typedef struct LNode ElemType data;/数据域 struct Lnode *next;/指针域 LNode,*LinkList;二、结点和单链表的二、结点和单链表的 C C 语言描述语言描述LinkList L；/L 为单链表的头指针为单

40、链表的头指针第74页/共105页752023/3/16 Typedef struct LNode ElemType data;/数据域 struct Lnode *next;/指针域 LNode,*LinkList;二、结点和单链表的二、结点和单链表的 C C 语言描述语言描述LinkList L；/L 为单链表的头指针为单链表的头指针第75页/共105页762023/3/16三、单链表操作的实现三、单链表操作的实现GetElem(L,i,&e)/取第i个数据元素ListInsert(&L,i,e)/插入数据元素ListDelete(&L,i,e)/删除数据元素ClearList(&L)/重置

41、线性表为空表CreateList(&L,n)/生成含 n 个数据元素的链表第76页/共105页772023/3/16L 线性表的操作 GetElem(L,i,&e)在单链表中的实现:211830754256pppj1 2 3第77页/共105页782023/3/16 因此，查找第因此，查找第 i 个数据元素的基本操作为：个数据元素的基本操作为：移动指移动指针，比较针，比较 j 和和 i。单链表是一种顺序存取的结构，为找第单链表是一种顺序存取的结构，为找第 i 个数据元个数据元素，必须先找到第素，必须先找到第 i-1 个数据元素。个数据元素。令指针 p 始终指向线性表中第 j 个数据元素。第78

42、页/共105页792023/3/16 Status GetElem_L(LinkList L,int i,ElemType&e)/L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素/GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p=L-next;j=1;/p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)returnERROR;/第 i 个元素

43、不存在e=p-data;/取得第 i 个元素returnOK;第79页/共105页802023/3/16ai-1 线性表的操作 ListInsert(&L,i,e)在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-1第80页/共105页812023/3/16 因此，在单链表中第因此，在单链表中第 i 个结点之前进行插入的基个结点之前进行插入的基本操作为本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同可见，在链表中插入结点只需要修改指针。但同时，若要在第时，若要在第 i 个结点之前插入元素，修改的是第个结点之前插入元素，修改

44、的是第 i-1 个结点的指针。个结点的指针。第81页/共105页822023/3/16 Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 /在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e /LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p&jnext;+j;/寻找第 i-1 个结点if(!p|ji-1)returnERROR;/i 大于表长或者小于1 第82页/共105页83

45、2023/3/16s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入returnOK;eai-1aiai-1sp第83页/共105页842023/3/16线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1第84页/共105页852023/3/16 在单链表中删除第删除第 i i 个结点个结点的基本操作基本操作为:找到找到线性表中第线性表中第i-1i-1个结点，修改其指向后继的指针。个结点，修改其指向后继的指针。ai-1a

46、iai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq第85页/共105页862023/3/16 Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点 /ListDelete_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p-next&jnext;+j;/寻找第i个结点，并令p指向其前趋if(!(p-next)|ji-1)return ERROR;/删除位置不合理q=p-next;p-next=q

47、-next;/删除并释放结点e=q-data;free(q);returnOK;第86页/共105页872023/3/16操作ClearList(&L)在链表中的实现:void ClearList(&L)/将单链表重新置为一个空表 while(L-next)p=L-next;L-next=p-next;/ClearListfree(p);算法时间复杂度：O(ListLength(L)第87页/共105页882023/3/16逆位序输入逆位序输入 n 个数据元素的值，建立带头结点的单链表。个数据元素的值，建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据

48、元素二、输入数据元素an，建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a1为止。为止。第88页/共105页892023/3/16void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i 0

49、;-i)p=(LinkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入第89页/共105页902023/3/16时间复杂度为O（La.length+Lb.length）。两个有序线性表合并为一个有序线性表的算法：voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc

50、-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);第90页/共105页912023/3/165.3.2 5.3.2 稀疏矩阵稀稀 疏疏 矩矩 阵阵：设设 m行行 n列列 的的 矩矩 阵阵 含含 t个个 非非 零零 元元 素素，则则=t/(m*n)称称为为稀稀疏疏因因子子，通通常常认认为为 0.05 的的矩矩阵阵为为稀稀疏矩阵。疏矩阵。抽象数据类型稀疏矩阵的定义：书抽象数据类型稀疏矩阵的定义：书96页页稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵中非零元素位置无规律稀疏矩阵中非零元素位置无规律记住非零元素的行记住非零元素的行i，列，列j，值，