图结构和查找习题复习省公共课一等奖全国赛课获奖课件.pptx

例题例题1 1对于给定关键序列，若哈希函数无冲突，则称其为完备对于给定关键序列，若哈希函数无冲突，则称其为完备(perfect)(perfect)。设哈希表长度为。设哈希表长度为7 7，试为，试为BretBret，JaneJane，MichelleMichelle，HeattherHeatther设计一个完备哈希函数设计一个完备哈希函数H H（提醒：考（提醒：考虑每个字串第虑每个字串第3 3个字符），并写出其个字符），并写出其CC代码。代码。解：解：设计哈希函数设计哈希函数H H以下：以下：H H（keykey）=key=key（第（第3 3个字母个字母ASCIIASCII码码MOD 7MOD 7），则：），则：H H（BertBert）=101 MOD 7=3=101 MOD 7=3H H（JaneJane）=110 MOD 7=5=110 MOD 7=5H H（ShirleyShirley）=105 MOD 7=105 MOD 7H H（BryceBryce）=121 MOD 7=2=121 MOD 7=2H H（MichelleMichelle）=99 MOD 7=1=99 MOD 7=1H H（HeatherHeather）=97 MOD 7=6=97 MOD 7=6第1页例题例题2 2：试述次序查找法、二分查找法和分块查找法对被查找表中元素：试述次序查找法、二分查找法和分块查找法对被查找表中元素要求。对长度为要求。对长度为n n表来说，表来说，3 3种查找法在查找成功时平均查找长度各种查找法在查找成功时平均查找长度各是多少？是多少？解：解：3 3种方法对查找要求分别以下：种方法对查找要求分别以下：1 1）次序查找法：表中元素能够任意次序存入。）次序查找法：表中元素能够任意次序存入。2 2）二分查找法：表中元素必须以关键字大小递增或递减次序有序列且）二分查找法：表中元素必须以关键字大小递增或递减次序有序列且次序表存放。次序表存放。3 3）分块查找法：表中元素块内元素能够任意次序存放，但块与块之间）分块查找法：表中元素块内元素能够任意次序存放，但块与块之间必须以关键字大小递增（或递减）存放，即前一块内全部元素关键必须以关键字大小递增（或递减）存放，即前一块内全部元素关键字都不能大（或小）于后一块内任何元素关键字。字都不能大（或小）于后一块内任何元素关键字。第2页3 3种方法平均查找长度分别以下：种方法平均查找长度分别以下：次序查找法：查找成功平均查找长度为次序查找法：查找成功平均查找长度为n+1/2n+1/2。二分查找法：查找成功平均长度为二分查找法：查找成功平均长度为loglog2 2（n+1n+1）-1-1。分块查找法：若用次序查找确定所在块，平均查找长度为：分块查找法：若用次序查找确定所在块，平均查找长度为：1/21/2（n/1+sn/1+s）+1+1；若用二分查找确定所在块，平均查找长度为；若用二分查找确定所在块，平均查找长度为loglog2 2（n/s+1n/s+1）+s/2+s/2。其中，。其中，s s为每块含有元素个数。为每块含有元素个数。例题例题3 3：设有一组关键字设有一组关键字1919，1 1，2323，1414，5555，2020，8484，2727，6868，1111，1010，7777采取哈希函数：采取哈希函数：H H（keykey）=key%13=key%13采取开放定址法二次采取开放定址法二次探测再哈希方法处理冲突，试在探测再哈希方法处理冲突，试在0 01818哈希地址空间中对该关键字序哈希地址空间中对该关键字序列结构哈希表。列结构哈希表。第3页【解】【解】依题意，依题意，m=19m=19，二次探测再哈希下一地址计算公式为：，二次探测再哈希下一地址计算公式为：d d1 1=H=H（keykey）；）；d d2j 2j=（d d1 1+j*j+j*j）%m%m；d d2j+12j+1（d d1 1-j*j-j*j）%m%m；j=1j=1，2 2，其计算函数以下：其计算函数以下：H H（1919）=19%13=6=19%13=6H H（1 1）=1%13=1=1%13=1H H（2323）=23%13=10=23%13=10H H（1414）=14%13=1=14%13=1（发生冲突）（发生冲突）H H（1414）=（1+1*11+1*1）%19=2%19=2H H（5555）=55%13=3=55%13=3H H（2020）=20%13=7=20%13=7H H（8484）=84%13=6=84%13=6（发生冲突）（发生冲突）H H（8484）=（6+1*16+1*1）%19=7%19=7（仍发生冲突）（仍发生冲突）第4页H（84）=（6-1*1）%19=5H（27）=27%13=1（发生冲突）（发生冲突）H（27）=（1+1*1）%19=2（发生冲突）（发生冲突）H（27）=（1-1）%19=0H（68）=68%13=3（发生冲突）（发生冲突）H（68）=（3+1*1）%19=4H（11）=11%13=11H（10）=10%13=10（发生冲突）（发生冲突）H（10）=（10+1*1）%19=11（仍发生冲突）（仍发生冲突）H（10）=（10-1*1）%19=9H（77）=11%13=12所以，各关键字统计对应地址分配以下：所以，各关键字统计对应地址分配以下：addr（27）=0addr（1）=1第5页addr（14）=2addr（55）=3addr（68）=4addr（84）=5addr（19）=6addr（20）=7addr（10）=9addr（23）=10addr（11）=11addr（77）=12其它地址为空。其它地址为空。第6页例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：哈希函数为：H(key)=key MOD 13,哈希表长为哈希表长为m=16，设每个统计查找概率相等设每个统计查找概率相等(1)用线性探测再散列处理冲突，即用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD mH(55)=3 冲突，冲突，H1=(3+1)MOD16=4 冲突，冲突，H2=(3+2)MOD16=5H(79)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4 冲突，冲突，H4=(1+4)MOD16=5 冲突，冲突，H5=(1+5)MOD16=6 冲突，冲突，H6=(1+6)MOD16=7 冲突，冲突，H7=(1+7)MOD16=8 冲突，冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6 冲突，冲突，H1=(6+1)MOD16=7 冲突，冲突，H2=(6+2)MOD16=8H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，冲突，H1=(10+1)MOD16=11 冲突，冲突，H2=(10+2)MOD16=12第7页(2)用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(19,14,23,1,68,20,84,27,55,11,10,79)第8页lowhighmid 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例例5 5：在下例中，画出折半查找：在下例中，画出折半查找2121过程示意图。在画出有序过程示意图。在画出有序序列查找判定树，计算查找成功序列查找判定树，计算查找成功ASLASL（自己做）。（自己做）。第9页927537138864215801956判定树：判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92ASL=ASL=（1X1+2X2+4X3+4X41X1+2X2+4X3+4X4）/11=/11=第10页1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例例7 7：折半查找举例：折半查找举例第11页1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh因为因为lowhigh，则查找表中不存在要查找统计，查，则查找表中不存在要查找统计，查找失败，返回查找失败信息结束查找。找失败，返回查找失败信息结束查找。第12页例题例题8 8试给出一棵树关键字序列，使试给出一棵树关键字序列，使AVLAVL树树4 4种调整平衡操作（种调整平衡操作（LLLL，LRLR，RRRR，RLRL）各最少执行一次，并画出其结构过程。）各最少执行一次，并画出其结构过程。【解】【解】设关键字输入序列为：设关键字输入序列为：4 4、5 5、7 7、2 2、1 1、3 3、6 6，则，则AVLAVL树结构过程树结构过程以下列图所表示。以下列图所表示。第13页 输入结点输入结点 插入后插入后 调整平衡后调整平衡后 4 4 无需调整无需调整 4454575472547547215274134253671527144175362413725RRRR型型无需调整无需调整无需调整无需调整LLLL型型LRLR型型RLRL型型572163图图8.5 AVL树结构过程树结构过程第14页例题例题9 9给定序列给定序列33，5 5，7 7，9 9，1111，1313，1515，1717：按表中元素次序依次插入一棵初始为空二叉排序树，画出插入完成后二叉按表中元素次序依次插入一棵初始为空二叉排序树，画出插入完成后二叉排序树，并求在等概率情况下查找成功平均查找长度。排序树，并求在等概率情况下查找成功平均查找长度。按表中元素次序结构一棵二叉平衡树，并求其在等概率情况下查找成功平按表中元素次序结构一棵二叉平衡树，并求其在等概率情况下查找成功平均查找长度，与均查找长度，与比较，可得出什么结论？比较，可得出什么结论？【解】【解】按输入次序进行插入后二充满排序树以下左图所表示，其在等概率下查找按输入次序进行插入后二充满排序树以下左图所表示，其在等概率下查找成功平均查找长度为：成功平均查找长度为：ASLASL成功成功=（1+2+2+3+4+5+6+7+81+2+2+3+4+5+6+7+8）/8=9/2/8=9/2。结构一棵平衡二叉树以下右图所表示，其在等概率下查找成功平均查找长结构一棵平衡二叉树以下右图所表示，其在等概率下查找成功平均查找长度为：度为：ASLASL成功成功=1/8=1/8（1+2*2+3*4+51+2*2+3*4+5）=11/4=11/4。与与相比，可见在一样序列查找中，二叉平衡排序树比二叉排序树平均查找相比，可见在一样序列查找中，二叉平衡排序树比二叉排序树平均查找长度要小且查找效率高。长度要小且查找效率高。第15页35 57 79 911111313151517179 953 313131515171711117 7图图8.6 二叉排序树二叉排序树图图8.7 二叉平衡树二叉平衡树第16页例题例题1010：线性表关键字集合：线性表关键字集合8787，2525，310310，0808，2727，132132，6868，9595，187187，123123，7070，6363，4747，共有，共有1313个元素，已知哈希函数为：个元素，已知哈希函数为：H H（k k）=k%13=k%13采取链地址法处理冲突。设计出这种链表结构，并计算该表成功查找平采取链地址法处理冲突。设计出这种链表结构，并计算该表成功查找平均长度。（练习题）均长度。（练习题）【解】【解】依题意知：依题意知：H H（8787）=87%13=9=87%13=9H H（2525）=25%13=12=25%13=12H H（310310）=310%13=11=310%13=11H H（0808）=08%13=8=08%13=8H H（2727）=27%13=1=27%13=1H H（132132）=132%13=2=132%13=2H H（6868）=68%13=3=68%13=3第17页H（95）=95%13=4H（187）=187%13=5H（123）=123%13=6H（70）=70%13=5H（63）=63%13=11H（47）=47%13=8采取拉链法处理冲突链表（学生做）。成功查找平均查找长度：采取拉链法处理冲突链表（学生做）。成功查找平均查找长度：ASL=第18页例题例题1111对如图对如图7.8(a)7.8(a)和和(b)(b)所表示图，试画出其深度优先生成树和广度优先生成所表示图，试画出其深度优先生成树和广度优先生成树。树。(a)(b)图图7.8 7.8 两棵树图两棵树图v1v2v8v4v5v6v3v8v1v6v2v5v4v3v7v1第19页【解】【解】由连通图定义知：这两个图都是连通图。由连通图定义知：这两个图都是连通图。连通图深度优先搜索方法是：连通图深度优先搜索方法是：假定图中某个顶点假定图中某个顶点v v1 1为出发点。搜索方法是：首先访问出发点，然后任为出发点。搜索方法是：首先访问出发点，然后任选未访问过邻接点，再以该邻接点为新出发点继续进行深度优先搜索，选未访问过邻接点，再以该邻接点为新出发点继续进行深度优先搜索，直至全部顶点都被访问过。连通图广度优先搜索方法是：直至全部顶点都被访问过。连通图广度优先搜索方法是：从图中某个顶点从图中某个顶点v vii出发，在访问了出发，在访问了v vi i 之后依次访问之后依次访问v vi i全部邻接点，然后分全部邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图其它顶点。重复这一过程，别从这些邻接点出发按广度优先搜索遍历图其它顶点。重复这一过程，直至全部顶点都被访问到。直至全部顶点都被访问到。由此得到如图由此得到如图7.97.9和图和图7.107.10所表示对应深度优先生成树和广度优先生成树。所表示对应深度优先生成树和广度优先生成树。第20页v1v2v4v5v8v6v3v7v1v2v6v5v3v4v7 (a)(a)顶点顶点v v1 1遍历深度优先生成树遍历深度优先生成树 (b)(b)顶点顶点v v1 1遍历深度优先生成树遍历深度优先生成树 图图7.97.9v1v2v4v5v3v8v7v6v7v4v3v5v2v1v6 (a)(a)顶点顶点v1v1遍历广度优先生成树遍历广度优先生成树 (b)(b)顶点顶点v1v1遍历广度优先生成树遍历广度优先生成树 图图7.107.10第21页例题例题12对如图对如图7.14所表示有向图所表示有向图,试给出：试给出：邻接矩阵邻接矩阵 邻接表邻接表 逆邻接表逆邻接表 强连通分量强连通分量 从从出发深度优先出发深度优先遍历序列遍历序列 从从出发广度优先遍历序列。出发广度优先遍历序列。653241图图7.14 7.14 有向图有向图【解】【解】邻接矩阵以下：邻接矩阵以下：第22页12345644652532141邻接表如图邻接表如图7.157.15所表示。所表示。图图7.15 邻接表邻接表第23页首先改变图首先改变图7.147.14中有向边方向得到如图中有向边方向得到如图7.167.16所表示有向图，然后依据所表示有向图，然后依据图图7.167.16画出邻接表画出邻接表(即图即图7.147.14逆邻接表逆邻接表)，如图，如图7.177.17所表示所表示.653241图图7.16 7.16 有向图有向图第24页12345625636533251图图7.17 图图7.14逆邻接表逆邻接表第25页在有向图在有向图G中中,假如对于每一对假如对于每一对vi,vjV(顶点集顶点集),且且vivj，从，从vi 到到vi 和从和从vi vi 都存在路径，则称都存在路径，则称G是强连通图。有向图中极大强连通子图是强连通图。有向图中极大强连通子图称作有向图强连通分量。由此得图称作有向图强连通分量。由此得图7.14强连通分量如图强连通分量如图7.18所表示。所表示。图图7.18 图图7.14强连通分量强连通分量从从出发深度优先遍历序列为出发深度优先遍历序列为:。从从出发广度优先遍历序列为出发广度优先遍历序列为:。145623第26页例题例题13有一带权无向图顶点集合为有一带权无向图顶点集合为v1，v2，v3，v4，v5，v6，v7，v8，已知其，已知其邻接矩阵三元组表如图邻接矩阵三元组表如图7.19所表示。所表示。画出该无向图邻接表。画出该无向图邻接表。画出全部可能最小生成树。画出全部可能最小生成树。依据你给邻接表分别写出从依据你给邻接表分别写出从v1出发进行深度优先遍历和广度优先遍历出发进行深度优先遍历和广度优先遍历顶点序列。顶点序列。写出从写出从v1到到v2最短路径。最短路径。【解】【解】首先依据邻接矩阵三元组表画出带权无向图，如图首先依据邻接矩阵三元组表画出带权无向图，如图7.20所表示所表示。图图7.20邻接表如图邻接表如图7.21所表示。所表示。第27页 图图7.20 7.20 带权无向图带权无向图882012121522112263285348352364438451047851253254106236346777487678257.19 三元组表三元组表v1v5v3v6v2v8v4v722847351210第28页图图7.21 7.21 邻接表邻接表0123456745215636115422417030第29页因为存在权值相同边因为存在权值相同边,则最小生成树可能不止一个则最小生成树可能不止一个,此题可能最小生成树此题可能最小生成树如图如图7.22所表示所表示.（a）（b）图图7.22 可能最小生成树可能最小生成树v1v5v3v6v2v8v4v72284735v1v5v3v4v7v2v6v82284735第30页依据图依据图7.21邻接表得到深度优先遍历序列为邻接表得到深度优先遍历序列为:v1,v5,v4,v7,v6,v3,v2,v8;广广度优先遍历序列为度优先遍历序列为:v1,v5,v2,v4,v3,v8,v6,v7。从从v1到到v2最短路径为最短路径为v1,v5,v3,v6,v2。例题例题20试列出图试列出图7.23中全部可能拓扑排序序列。中全部可能拓扑排序序列。图图7.23 有向图有向图【解】【解】拓扑排序算法步骤为拓扑排序算法步骤为:在有向图中选择一个没有前驱顶点在有向图中选择一个没有前驱顶点(入度为入度为0)且输出之且输出之;在有向图中删除该顶点和全部以该顶点为尾弧在有向图中删除该顶点和全部以该顶点为尾弧;v1v2v6v5v4v3第31页重复重复和和,直至图中没有前驱顶点直至图中没有前驱顶点(不存在有弧相连顶点不存在有弧相连顶点)时为止。时为止。由此得到图由此得到图7.23全部可能拓扑排序序列以下全部可能拓扑排序序列以下:1 5 2 3 6 4 1 5 2 6 3 4 1 5 6 2 3 4 5 6 1 2 3 4 5 1 6 2 3 4 5 1 2 6 3 4 5 1 2 3 6 4第32页例题例题23设设G为有为有n个顶点无向连通图个顶点无向连通图,证实全部含有证实全部含有n-1条边并有条边并有n个顶点无向连个顶点无向连通图是树图。通图是树图。【证实】【证实】必要性：因为含有必要性：因为含有n个顶点无向连通图最少有个顶点无向连通图最少有n-1条边，因为此处无向条边，因为此处无向连通图为树图，所以它只有连通图为树图，所以它只有n-1条边，假如多于条边，假如多于n-1条边就会形成环，条边就会形成环，少于少于n-1条边则不连通。条边则不连通。充分性：若充分性：若G是连通图且只有是连通图且只有n-1条边，则条边，则G必为树图。设必为树图。设G是连通但是连通但不是树图，则不是树图，则G中必定存在回路，所以我们能够从回路中去掉一条边中必定存在回路，所以我们能够从回路中去掉一条边且仍使得且仍使得G是连通；这时，是连通；这时，G则成为则成为n个顶点但只有个顶点但只有n-2条边连通图，条边连通图，这显然是错误，故这显然是错误，故G一定是树图。一定是树图。证毕。证毕。第33页V1V2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418v9v8v7v6v4v5v3v2v1a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e*00002266046258377077071031616014140033例例14：关键路径计算：关键路径计算第34页