《数据结构学位考学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构学位考学习教案.pptx（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)学位考学位考第一页，共63页。第七章第七章 图图n n考核内容及要求：考核内容及要求：n n熟练掌握图的相关熟练掌握图的相关(xinggun)概概念、性质、存储结构念、性质、存储结构n n熟练掌握遍历：深度优先遍历、熟练掌握遍历：深度优先遍历、广度优先遍历过程；广度优先遍历过程；n n熟练掌握连通分量的求法；熟练掌握连通分量的求法；n n熟练掌握最小生成树、最短路径熟练掌握最小生成树、最短路径概念与方法；概念与方法；n n掌握拓扑排序、关键路径的求法掌握拓扑排序、关键路径的求法及实现方法。及实现方法。第1页/共63页第二页，共63页。1 图的定义图
2、的定义(dngy)、术、术语和存储结构语和存储结构n n图：图结构中，任意两个结点之间的关图：图结构中，任意两个结点之间的关图：图结构中，任意两个结点之间的关图：图结构中，任意两个结点之间的关系是任意的，图中任意两个数据元素之系是任意的，图中任意两个数据元素之系是任意的，图中任意两个数据元素之系是任意的，图中任意两个数据元素之间都可能相关间都可能相关间都可能相关间都可能相关n n图的抽象数据类型图的抽象数据类型图的抽象数据类型图的抽象数据类型n n顶点顶点顶点顶点(d(d ngdingdi n)n)、弧、边、弧、边、弧、边、弧、边n n有向图（有向图（有向图（有向图（digraph)digra
3、ph)n n有向图有向图有向图有向图G1=(V1,A1)G1=(V1,A1)，其中，其中，其中，其中V1=v1,v2,v3,v4,A1=,vV1=v1,v2,v3,v4,A1=,3,v4,n n无向图无向图无向图无向图(undigraph)(undigraph)n n无向图无向图无向图无向图G2=(V2,E2)G2=(V2,E2)n nV2=v1,v2,v3,v4,v5,V2=v1,v2,v3,v4,v5,E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)(v
4、3,v5)VV11VV22VV33VV44VV11VV22VV44VV55VV33有向图有向图有向图有向图无向无向无向无向(w(w xinxin )图图图图第2页/共63页第三页，共63页。n n顶点顶点顶点顶点(dngdin)(dngdin)数数数数n n和边和边和边和边(弧弧弧弧)的数目的数目的数目的数目e e：n n无向图：无向图：无向图：无向图：n n有向图：有向图：有向图：有向图：n n n n完全图：有完全图：有完全图：有完全图：有n(n-1)/2n(n-1)/2条边的无向图条边的无向图条边的无向图条边的无向图;n n有向完全图：有有向完全图：有有向完全图：有有向完全图：有n(n-
5、1)n(n-1)条弧的有向图条弧的有向图条弧的有向图条弧的有向图;n n稀疏图、稠密图稀疏图、稠密图稀疏图、稠密图稀疏图、稠密图n n子图：子图：子图：子图：G=(V,E),G=(V,E)G=(V,E),G=(V,E)，若，若，若，若V V,V V,且且且且E E,E E,则称则称则称则称GG为为为为GG的子的子的子的子图图图图n n邻接点：无向图中，邻接点：无向图中，邻接点：无向图中，邻接点：无向图中，(v,v)(v,v)E E，则，则，则，则v,vv,v互为邻接点；互为邻接点；互为邻接点；互为邻接点；n n顶点顶点顶点顶点(dngdin)v(dngdin)v的度：与的度：与的度：与的度：与
6、v v相关联的边的数目，相关联的边的数目，相关联的边的数目，相关联的边的数目，TD(v)TD(v)n n有向图中有向图中有向图中有向图中,若若若若A A，则顶点，则顶点，则顶点，则顶点(dngdin)v(dngdin)v邻接到顶点邻接到顶点邻接到顶点邻接到顶点(dngdin)v(dngdin)v，而顶点，而顶点，而顶点，而顶点(dngdin)v(dngdin)v邻接自邻接自邻接自邻接自v vn n出度：以出度：以出度：以出度：以v v为尾的弧的数目，为尾的弧的数目，为尾的弧的数目，为尾的弧的数目，OD(v)OD(v)n n入度：以入度：以入度：以入度：以v v为头的弧的数目，为头的弧的数目，为
7、头的弧的数目，为头的弧的数目，ID(v)ID(v)n nTD(v)=OD(v)+ID(v)TD(v)=OD(v)+ID(v)第3页/共63页第四页，共63页。n n路径：路径：路径：路径：n n回路（环）回路（环）回路（环）回路（环）n n简单路径：顶点序列中顶点不重复的路径。简单路径：顶点序列中顶点不重复的路径。简单路径：顶点序列中顶点不重复的路径。简单路径：顶点序列中顶点不重复的路径。n n连通连通连通连通(lintng)(lintng)图、连通图、连通图、连通图、连通(lintng)(lintng)分量、强连通分量、强连通分量、强连通分量、强连通(lintng)(lintng)图、强连通
8、图、强连通图、强连通图、强连通(lintng)(lintng)分量：分量：分量：分量：AAB BL LMMCCDDE EF FGGHH HHI IJ JKKAAB BL LMMCCF FJ JDDE EGGHH HHI IKK第4页/共63页第五页，共63页。n n一个一个一个一个(y)(y)连通图的生成树：一个连通图的生成树：一个连通图的生成树：一个连通图的生成树：一个(y)(y)极小连通子极小连通子极小连通子极小连通子图，含有图中全部结点，但只有足以构成一棵树的图，含有图中全部结点，但只有足以构成一棵树的图，含有图中全部结点，但只有足以构成一棵树的图，含有图中全部结点，但只有足以构成一棵树
9、的n-1n-1条边。条边。条边。条边。n n一棵有一棵有一棵有一棵有n n个顶点的生成树有且仅有个顶点的生成树有且仅有个顶点的生成树有且仅有个顶点的生成树有且仅有n-1n-1条边条边条边条边n n但有但有但有但有n-1n-1条边的图不一定是生成树条边的图不一定是生成树条边的图不一定是生成树条边的图不一定是生成树n n有向图：如果有一个有向图：如果有一个有向图：如果有一个有向图：如果有一个(y)(y)顶点的入度为顶点的入度为顶点的入度为顶点的入度为0 0，其余顶点，其余顶点，其余顶点，其余顶点的入度都为的入度都为的入度都为的入度都为1 1，则是一棵有向树。，则是一棵有向树。，则是一棵有向树。，则
10、是一棵有向树。AAB BL LMMCCF FJ J第5页/共63页第六页，共63页。图的存储图的存储(cn ch)结构结构n n 数组表示法（邻接矩阵）：数组表示法（邻接矩阵）：数组表示法（邻接矩阵）：数组表示法（邻接矩阵）：用两个数组分别存放顶点用两个数组分别存放顶点用两个数组分别存放顶点用两个数组分别存放顶点(dngdin)(dngdin)信信信信息和边（弧）信息息和边（弧）信息息和边（弧）信息息和边（弧）信息G1.VEXS4=V1 V2 V3 V4G1.VEXS4=V1 V2 V3 V4G1.arcs=0 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11
11、 0 0 01 0 0 0VV11VV22VV33VV44G1G1VV11VV22VV44VV55VV33G2G2G2.arcs=0 1 0 1 00 1 0 1 01 0 1 0 11 0 1 0 10 1 0 1 0 1 0 1 1 1 1 0 1 0 01 0 1 0 00 1 1 0 00 1 1 0 0第6页/共63页第七页，共63页。图的邻接矩阵 Aij=1/若存在 Aij=0/若不存在 无向图：第i行分量(fn ling)的和为结点vi的度 有向图：第i行分量(fn ling)的和为结点vi的出度；第i列分量(fn ling)的和为结点vi的入度 网的邻接矩阵 Aij=无穷大 间
12、无边 =权 间有边 问题：为什么放无穷大而不放0第7页/共63页第八页，共63页。n n 邻接表：一种链式存储结构邻接表：一种链式存储结构邻接表：一种链式存储结构邻接表：一种链式存储结构n n为图中的每一个顶点创建一个单链表，其中的结点为图中的每一个顶点创建一个单链表，其中的结点为图中的每一个顶点创建一个单链表，其中的结点为图中的每一个顶点创建一个单链表，其中的结点(ji din)(ji din)表示依附于表示依附于表示依附于表示依附于顶点的边顶点的边顶点的边顶点的边(以该顶点为尾的弧以该顶点为尾的弧以该顶点为尾的弧以该顶点为尾的弧)adjvexadjvexnextarcnextarcinfo
13、info表结点表结点datadatafirstarcfirstarc头结点头结点VV11VV22VV33VV44v v1 1v v2 2v v3 3v v4 40 01 12 23 32 21 1 3 3 0 0 第8页/共63页第九页，共63页。n n无向图的邻接表中，顶点无向图的邻接表中，顶点无向图的邻接表中，顶点无向图的邻接表中，顶点(dngdin)v(dngdin)v的度就是该顶点的度就是该顶点的度就是该顶点的度就是该顶点(dngdin)(dngdin)的单链表中的结点数；的单链表中的结点数；的单链表中的结点数；的单链表中的结点数；n n有向图中，第有向图中，第有向图中，第有向图中，第
14、i i个链表的结点数是该顶点个链表的结点数是该顶点个链表的结点数是该顶点个链表的结点数是该顶点(dngdin)(dngdin)的的的的出度；出度；出度；出度；n n如何求有向图中顶点如何求有向图中顶点如何求有向图中顶点如何求有向图中顶点(dngdin)(dngdin)的入度？的入度？的入度？的入度？有向图的有向图的有向图的有向图的逆邻接表。逆邻接表。逆邻接表。逆邻接表。v v1 1v v2 2v v3 3v v4 40 01 12 23 32 21 1 3 3 0 0 v v1 1v v2 2v v3 3v v4 40 01 12 23 33 30 0 0 0 2 2 有向图有向图有向图有向图
15、G1G1的邻接的邻接的邻接的邻接(ln(ln ji)ji)表表表表有向图有向图有向图有向图G1G1的逆邻接的逆邻接的逆邻接的逆邻接(ln(ln ji)ji)表表表表第9页/共63页第十页，共63页。VV11VV22VV33VV44v v1 1v v2 2v v3 3v v4 40 01 12 23 31 1 0 02 20 02 22 20 02 23 33 30 03 3 1 12 23 32 2 十字十字十字十字(sh z)(sh z)链表：有向图的链式存储链表：有向图的链式存储链表：有向图的链式存储链表：有向图的链式存储datadatafirstinfirstinfirstoutfirs
16、tout顶点结点顶点结点顶点结点顶点结点tailvextailvexheadveheadvex xhlinkhlinktlinktlinkinfoinfo弧结点弧结点弧结点弧结点第10页/共63页第十一页，共63页。n n邻接多重表：无向图的另一种邻接多重表：无向图的另一种(y zhn)链式存储结构。链式存储结构。VV11VV22VV44VV55VV33V1V2V3V4V501234012141032324第11页/共63页第十二页，共63页。2.图的遍历图的遍历(bin l)图的遍历图的遍历(bin l)(bin l)目标是解决图目标是解决图的连通性问题、拓扑排序问题、的连通性问题、拓扑排序
17、问题、关键路径问题。关键路径问题。图的遍历图的遍历(bin l)(bin l)方法：深度优方法：深度优先算法、广度优先算法先算法、广度优先算法第12页/共63页第十三页，共63页。深度优先深度优先深度优先深度优先(yuxin)(yuxin)遍历遍历遍历遍历n n深度优先搜索遍历：类似于树的先根遍历，是树的先根遍历深度优先搜索遍历：类似于树的先根遍历，是树的先根遍历的推广的推广n n算法：算法：n n1.1.假设图中所有顶点的初始状态为：未访问；假设图中所有顶点的初始状态为：未访问；n n2.2.从图中某个未访问的顶点从图中某个未访问的顶点v v出发出发(chf)(chf)，访问此结点；，访问此
18、结点；n n3.3.依次从依次从v v的邻接点出发的邻接点出发(chf)(chf)深度优先遍历图，直到深度优先遍历图，直到图中所有与图中所有与v v有路径的顶点都被访问到；有路径的顶点都被访问到；n n4.4.若图中还有未访问结点，则另选一个结点作起始点，若图中还有未访问结点，则另选一个结点作起始点，重复重复2 2、3 3过程。过程。第13页/共63页第十四页，共63页。v v1 1V V2 2v v6 6v v4 4v v5 5v v8 8v v3 3v v7 7v v1 1V V2 2v v6 6v v4 4v v5 5v v8 8v v3 3v v7 7图解深度图解深度图解深度图解深度(
19、shnd)(shnd)优先遍历过程优先遍历过程优先遍历过程优先遍历过程第14页/共63页第十五页，共63页。一个非连同图的深度优先一个非连同图的深度优先一个非连同图的深度优先一个非连同图的深度优先(yuxin)(yuxin)遍历过程图解遍历过程图解遍历过程图解遍历过程图解AAB BL LMMCCDDE EF FGGHH HHI IJ JKKHHAAB BL LMMCCDDE EF FGGHHI IJ JKK可能可能可能可能(knng)(knng)的遍历序列：的遍历序列：的遍历序列：的遍历序列：A L M J B F C D E G I H K A L M J B F C D E G I H K
20、 注：图的存储结构没有给定的情况注：图的存储结构没有给定的情况注：图的存储结构没有给定的情况注：图的存储结构没有给定的情况(qngkung)(qngkung)下，图的遍历序列不是唯一的。下，图的遍历序列不是唯一的。下，图的遍历序列不是唯一的。下，图的遍历序列不是唯一的。第15页/共63页第十六页，共63页。广度广度(gungd)优先遍历优先遍历n n广度优先搜索遍历广度优先搜索遍历(bin l)类似于树的层次类似于树的层次遍历遍历(bin l)n n算法算法v v1 1V V2 2v v6 6v v4 4v v5 5v v8 8v v3 3v v7 7v v1 1V V2 2v v6 6v v
21、4 4v v5 5v v8 8v v3 3v v7 7第16页/共63页第十七页，共63页。一个非连同图的广度优先遍历一个非连同图的广度优先遍历一个非连同图的广度优先遍历一个非连同图的广度优先遍历(bin l)(bin l)过程图解过程图解过程图解过程图解AAB BL LMMCCDDE EF FGGHH HHI IJ JKKHHAAB BL LMMCCDDE EF FGGHHI IJ JKK可能可能可能可能(knng)(knng)的遍历序列：的遍历序列：的遍历序列：的遍历序列：A L F C B M D E G I H K A L F C B M D E G I H K 第17页/共63页第十
22、八页，共63页。3.图的连通性问题图的连通性问题(wnt)掌握连通分掌握连通分量的求法量的求法n n无向图的连通分量和生成树无向图的连通分量和生成树无向图的连通分量和生成树无向图的连通分量和生成树n n由图的遍历得出：由图的遍历得出：由图的遍历得出：由图的遍历得出：n n对于连通图，从图中任一顶点对于连通图，从图中任一顶点对于连通图，从图中任一顶点对于连通图，从图中任一顶点(dngdin)(dngdin)出发，可以访问到图中的所有顶点出发，可以访问到图中的所有顶点出发，可以访问到图中的所有顶点出发，可以访问到图中的所有顶点(dngdin)(dngdin)；n n对于非连通图，需要从多个顶点对于
23、非连通图，需要从多个顶点对于非连通图，需要从多个顶点对于非连通图，需要从多个顶点(dngdin)(dngdin)出发，搜索到树的各个连通分量中出发，搜索到树的各个连通分量中出发，搜索到树的各个连通分量中出发，搜索到树的各个连通分量中的顶点的顶点的顶点的顶点(dngdin)(dngdin)集。集。集。集。AAB BL LMMCCDDE EF FGGHH HHI IJ JKKHHAAB BL LMMCCDDE EF FGGHHI IJ JKK第18页/共63页第十九页，共63页。4 掌握最小生成掌握最小生成(shn chn)树树的概念和求法的概念和求法n n最小生成树最小生成树最小生成树最小生成树
24、n n构造连通网的最小代价生成树。构造连通网的最小代价生成树。构造连通网的最小代价生成树。构造连通网的最小代价生成树。n nMSTMST性质：假设性质：假设性质：假设性质：假设N=(V,E)N=(V,E)是一个连通网，是一个连通网，是一个连通网，是一个连通网，U U是顶点集是顶点集是顶点集是顶点集V V上的一个非空子集。若上的一个非空子集。若上的一个非空子集。若上的一个非空子集。若(u,v)(u,v)是一条是一条是一条是一条(y tio)(y tio)具有最小具有最小具有最小具有最小权值的边，其中权值的边，其中权值的边，其中权值的边，其中u uU U，v vV-U,V-U,则必存在一棵包含边则
25、必存在一棵包含边则必存在一棵包含边则必存在一棵包含边(u,v)(u,v)的最小生成树。的最小生成树。的最小生成树。的最小生成树。n n构造最小生成树的算法：构造最小生成树的算法：构造最小生成树的算法：构造最小生成树的算法：PrinPrin算法和算法和算法和算法和KruskalKruskal算法。算法。算法。算法。第19页/共63页第二十页，共63页。n nPrimPrim算法构造最小生成算法构造最小生成算法构造最小生成算法构造最小生成(shn chn)(shn chn)树的过程：树的过程：树的过程：树的过程：VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV5
26、5VV666512556643VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV55VV66第20页/共63页第二十一页，共63页。n nKruskalKruskal算法算法算法算法(sun f)(sun f)构造最小生成树的过程构造最小生成树的过程构造最小生成树的过程构造最小生成树的过程VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV
27、55VV66VV11VV22VV33VV44VV55VV66VV11VV22VV33VV44VV55VV666512556643两种算法的区别：两种算法的区别：两种算法的区别：两种算法的区别：普鲁姆算法：基于连通地选择普鲁姆算法：基于连通地选择普鲁姆算法：基于连通地选择普鲁姆算法：基于连通地选择(xunz)(xunz)，避免回路，避免回路，避免回路，避免回路克鲁斯卡儿算法：离散地选择克鲁斯卡儿算法：离散地选择克鲁斯卡儿算法：离散地选择克鲁斯卡儿算法：离散地选择(xunz)(xunz)，避免回路，避免回路，避免回路，避免回路第21页/共63页第二十二页，共63页。拓扑排序：由某个拓扑排序：由某个
28、拓扑排序：由某个拓扑排序：由某个(mu)(mu)集合上的一个偏序得集合上的一个偏序得集合上的一个偏序得集合上的一个偏序得到该集合上的一个全序，就是拓扑排序。到该集合上的一个全序，就是拓扑排序。到该集合上的一个全序，就是拓扑排序。到该集合上的一个全序，就是拓扑排序。偏序：集合中仅有部分成员之间可以比较；偏序：集合中仅有部分成员之间可以比较；偏序：集合中仅有部分成员之间可以比较；偏序：集合中仅有部分成员之间可以比较；全序：集合中全体成员之间均可比较。全序：集合中全体成员之间均可比较。全序：集合中全体成员之间均可比较。全序：集合中全体成员之间均可比较。AOVAOV网：顶点表示活动，弧表示活动之间的优
29、先网：顶点表示活动，弧表示活动之间的优先网：顶点表示活动，弧表示活动之间的优先网：顶点表示活动，弧表示活动之间的优先关系的有向图称为顶点表示活动的网。关系的有向图称为顶点表示活动的网。关系的有向图称为顶点表示活动的网。关系的有向图称为顶点表示活动的网。v v1 1v v2 2v v3 3v v4 4v v1 1v v2 2v v3 3v v4 4偏序偏序偏序偏序全序全序全序全序5 拓扑拓扑(tu p)排序排序第22页/共63页第二十三页，共63页。n n进行拓扑排序的方法：进行拓扑排序的方法：进行拓扑排序的方法：进行拓扑排序的方法：n n在有向图中选一个没有前驱的顶点且输出；在有向图中选一个没
30、有前驱的顶点且输出；在有向图中选一个没有前驱的顶点且输出；在有向图中选一个没有前驱的顶点且输出；n n从图中删除该结点和所有以该结点为尾的弧。从图中删除该结点和所有以该结点为尾的弧。从图中删除该结点和所有以该结点为尾的弧。从图中删除该结点和所有以该结点为尾的弧。n n重复上述操作。若可以输出全部顶点，则该图中不存在环，重复上述操作。若可以输出全部顶点，则该图中不存在环，重复上述操作。若可以输出全部顶点，则该图中不存在环，重复上述操作。若可以输出全部顶点，则该图中不存在环，否则存在环。否则存在环。否则存在环。否则存在环。n n例如例如例如例如(lr)(lr)：n n算法实现：算法实现：算法实现：
31、算法实现：n n以邻接表的方法存储有向图；以邻接表的方法存储有向图；以邻接表的方法存储有向图；以邻接表的方法存储有向图；n n头结点增加信息：顶点入度；头结点增加信息：顶点入度；头结点增加信息：顶点入度；头结点增加信息：顶点入度；n n增加一个栈：存放入度为增加一个栈：存放入度为增加一个栈：存放入度为增加一个栈：存放入度为0 0的顶点。的顶点。的顶点。的顶点。v v1 1v v2 2v v3 3v v4 4第23页/共63页第二十四页，共63页。6 最短路径最短路径(ljng)n n从某个源点到其余各顶点从某个源点到其余各顶点从某个源点到其余各顶点从某个源点到其余各顶点(dngdin)(dng
32、din)的最短路径的最短路径的最短路径的最短路径n nDijkstraDijkstra算法：按路径长度递增的次序产生最短路径算法：按路径长度递增的次序产生最短路径算法：按路径长度递增的次序产生最短路径算法：按路径长度递增的次序产生最短路径n nDiDi表示当前所找到的从点表示当前所找到的从点表示当前所找到的从点表示当前所找到的从点v v到每个终点到每个终点到每个终点到每个终点vivi的最短路径的长度。的最短路径的长度。的最短路径的长度。的最短路径的长度。n nDiDi初值：初值：初值：初值：v v到到到到vivi的弧的权值；则：的弧的权值；则：的弧的权值；则：的弧的权值；则：n n初值最小的路
33、径就是从初值最小的路径就是从初值最小的路径就是从初值最小的路径就是从v v出发的最短的一条路径出发的最短的一条路径出发的最短的一条路径出发的最短的一条路径n n下面按照长度递增多次序产生各个终点的最短路径下面按照长度递增多次序产生各个终点的最短路径下面按照长度递增多次序产生各个终点的最短路径下面按照长度递增多次序产生各个终点的最短路径v v1 1v v2 2v v3 3v v4 4v v0 0v v5 51005060201030105第24页/共63页第二十五页，共63页。DijkstraDijkstra算法算法算法算法(sun f)(sun f)求最短路径求最短路径求最短路径求最短路径终点
34、终点终点终点从从从从v v0 0到各终点的到各终点的到各终点的到各终点的D D值和最短路径的求解过程值和最短路径的求解过程值和最短路径的求解过程值和最短路径的求解过程i=1i=1i=2i=2i=3i=3i=4i=4i=5i=5v v1 1 无无无无v v2 21010(v(v0 0,v,v2 2)v v3 3 6060(v(v0 0,v,v2 2,v,v3 3)5050(v(v0 0,v,v4 4,v,v3 3)v v4 43030(v(v0 0,v,v4 4)3030(v(v0 0,v,v4 4)v v5 5100100(v(v0 0,v,v5 5)100100(v(v0 0,v,v5 5)
35、9090(v(v0 0,v,v4 4,v,v5 5)6060(v(v0 0,v,v4 4,v,v3 3,v,v5 5)v vj jv v2 2v v4 4v v3 3S Svv0 0,v,v2 2 v v1 1v v2 2v v3 3v v4 4v v0 0v v5 51005060201030105第25页/共63页第二十六页，共63页。查找查找(ch zho)n n考核内容及要求：考核内容及要求：n n熟练掌握顺序查找、有序表的查找、索引熟练掌握顺序查找、有序表的查找、索引(suyn)(suyn)顺序查找、二分查找法及顺序查找、二分查找法及HASHINGHASHING查找技术；查找技术；n
36、 n了解平衡二叉树、了解平衡二叉树、B B树及树及B+B+树的概念；树的概念；n n理解查找速度的分析及比较、算法复杂性的理解查找速度的分析及比较、算法复杂性的级别。级别。第26页/共63页第二十七页，共63页。1 顺序顺序(shnx)表的查找表的查找n n物理物理(wl)存储：存储：n n 顺序表方式：顺序表方式：n n typedef struct n n ElemType*elem;n n int length;SSTablen n查找过程：从表中最后一个元素查找过程：从表中最后一个元素开始，逐个比较，相等则比较成开始，逐个比较，相等则比较成功，否则直到第一个元素。功，否则直到第一个元素
37、。第27页/共63页第二十八页，共63页。Int Search_Seq(SSTable ST,KeyType key)Int Search_Seq(SSTable ST,KeyType key)/从尾部依次比较从尾部依次比较从尾部依次比较从尾部依次比较keykey和数据元素和数据元素和数据元素和数据元素(yun s)(yun s)的关键字，的关键字，的关键字，的关键字，/当比到当比到当比到当比到0 0下标才成功则查找不成功，返回下标才成功则查找不成功，返回下标才成功则查找不成功，返回下标才成功则查找不成功，返回0 0 /否则返回下标否则返回下标否则返回下标否则返回下标i i ST.elem0.
38、key=key;ST.elem0.key=key;for(i=ST.length;!EQ(ST.elemi.key,key);-i);for(i=ST.length;!EQ(ST.elemi.key,key);-i);return i;return i;/Search-Seq /Search-Seq0 0下标为监视哨下标为监视哨下标为监视哨下标为监视哨,时间复杂度时间复杂度时间复杂度时间复杂度O(n)O(n)平均查找长度：平均查找长度：平均查找长度：平均查找长度：ASL=sum(pici)i=1n ASL=sum(pici)i=1n第28页/共63页第二十九页，共63页。查找查找(ch zho
39、)成功：成功：pi=1/n ci=1,2,3n ASL=1/n1+2+n=(n+1)/2查找查找(ch zho)不成功：不成功：ASL=n+1,(n,n-11,0)成功和不成功同概率：成功和不成功同概率：1/2 ASL=*1/n1+2+n+1/2(n+1)=(n+1)第29页/共63页第三十页，共63页。n n折半折半折半折半(zhbn)(zhbn)查找：先确定待查记录的范围，逐步缩小范围直到找到查找：先确定待查记录的范围，逐步缩小范围直到找到查找：先确定待查记录的范围，逐步缩小范围直到找到查找：先确定待查记录的范围，逐步缩小范围直到找到或找不到。或找不到。或找不到。或找不到。n n例：在下列
40、数据元素中查找关键字为例：在下列数据元素中查找关键字为例：在下列数据元素中查找关键字为例：在下列数据元素中查找关键字为2121和和和和8585的数据元素的数据元素的数据元素的数据元素n n分析：设置两个指针分析：设置两个指针分析：设置两个指针分析：设置两个指针low,highlow,high指示待查元素所在范围的上界和下界。指示待查元素所在范围的上界和下界。指示待查元素所在范围的上界和下界。指示待查元素所在范围的上界和下界。midmid（low+highlow+high）/2/2n nST.elemmid.key=key:ST.elemmid.key=key:查找成功查找成功查找成功查找成功n
41、 nST.elemmid.keykeyST.elemmid.keykey:high=mid-1ST.elemmid.keykey:high=mid-1n n low=high:low=high:查找不成功查找不成功查找不成功查找不成功2 有序表的查找有序表的查找(ch zho)5 13 19 21 37 56 64 75 80 88 935 13 19 21 37 56 64 75 80 88 93lowlowhighhighmimid d第30页/共63页第三十一页，共63页。int Search_Bin(SSTable ST,KeyTable key)int Search_Bin(SSTa
42、ble ST,KeyTable key)/对有序表的查找采用折半查找，逐步缩小对有序表的查找采用折半查找，逐步缩小对有序表的查找采用折半查找，逐步缩小对有序表的查找采用折半查找，逐步缩小 /查找范围，直到找到或找不到，返回值为查找范围，直到找到或找不到，返回值为查找范围，直到找到或找不到，返回值为查找范围，直到找到或找不到，返回值为 /找到返回下标，找不到返回找到返回下标，找不到返回找到返回下标，找不到返回找到返回下标，找不到返回0 0 low=1;high=ST.length;low=1;high=ST.length;while(low=high)while(low=high)mid=(lo
43、w+high)/2;mid=(low+high)/2;if EQ(key,ST.elemmid.key)return mid;if EQ(key,ST.elemmid.key)return mid;else if LT(key,ST.elemmid.key)else if LT(key,ST.elemmid.key)high=mid 1;high=mid 1;else low=mid+1;else low=mid+1;return OK;return OK;/Search_Bin /Search_Bin 时间时间时间时间(shjin)(shjin)复杂度：复杂度：复杂度：复杂度：O(log2n
44、),O(log2n),ASL=log2(n+1)+1(ASL=log2(n+1)+1(按照满二叉树按照满二叉树按照满二叉树按照满二叉树)第31页/共63页第三十二页，共63页。n n分块查找，索引顺序分块查找，索引顺序分块查找，索引顺序分块查找，索引顺序(shnx)(shnx)查找查找查找查找n n分块有序分块有序分块有序分块有序n n两步查找：确定待查记录所在地子表（块）；在子表两步查找：确定待查记录所在地子表（块）；在子表两步查找：确定待查记录所在地子表（块）；在子表两步查找：确定待查记录所在地子表（块）；在子表中顺序中顺序中顺序中顺序(shnx)(shnx)查找查找查找查找3 3 索引顺
45、序索引顺序索引顺序索引顺序(shnx)(shnx)表的查找表的查找表的查找表的查找22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 5322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 5322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 532248 861 7 13第32页/共63页第三十三页，共63页。4.4.动态动态(dngti)(dngti)查找表查找表二叉排序树二叉排序树n n例例例例 已知如下长度为已知如下长度为已知如下长度为已知如下长度
46、为8 8的表，试按表中元素的顺序的表，试按表中元素的顺序的表，试按表中元素的顺序的表，试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入依次插入一棵初始为空的二叉排序树，画出插入依次插入一棵初始为空的二叉排序树，画出插入依次插入一棵初始为空的二叉排序树，画出插入完成完成完成完成(wn chng)(wn chng)后的二叉排序树，并求其在等概后的二叉排序树，并求其在等概后的二叉排序树，并求其在等概后的二叉排序树，并求其在等概率下查找成功的平均查找长度。率下查找成功的平均查找长度。率下查找成功的平均查找长度。率下查找成功的平均查找长度。n n（Mon,Tiger,Win,Butter,F
47、ish,Fly,Pig,Cat)Mon,Tiger,Win,Butter,Fish,Fly,Pig,Cat)第33页/共63页第三十四页，共63页。n n平衡二叉树平衡二叉树n n平衡因子：左子深度减去右子深度为平衡因子：左子深度减去右子深度为 1 1，0 0，1 1的二叉排序树。的二叉排序树。n n二叉平衡树的构造二叉平衡树的构造(guzo)(guzo)（单项左旋（单项左旋/单项右旋），单项右旋），n n （左右旋，右左旋）（左右旋，右左旋）2222右旋右旋左旋左旋(zu xun)左右左右(zuyu)旋旋右左旋右左旋第34页/共63页第三十五页，共63页。9.3 哈希表哈希表n n确定的对应
48、关系确定的对应关系f f：记录的存储位置：记录的存储位置 关键字关键字n n对应关系对应关系f f就是哈希函数：就是哈希函数：f(K)f(K)n n哈希函数是一个映象哈希函数是一个映象(yn xin)(yn xin)，构造哈希函数的方法：，构造哈希函数的方法：n n直接定址法；直接定址法；n n哈希地址：直接取关键字或者关键字的线性函数哈希地址：直接取关键字或者关键字的线性函数n nH(key)=key;or H(key)=a*key+bH(key)=key;or H(key)=a*key+bn n数字分析法；数字分析法；n n分析关键字，取关键字的若干数位组成哈希地址。分析关键字，取关键字的
49、若干数位组成哈希地址。n n平方取中法；平方取中法；n n取关键字平方后的中间几位为哈希地址取关键字平方后的中间几位为哈希地址较为常用的较为常用的方法方法n n折叠法：分割关键字、叠加折叠法：分割关键字、叠加n n除留余数法：除留余数法：H(key)=key MOD p p=H(key)=key MOD p p=哈希表长哈希表长mm第35页/共63页第三十六页，共63页。n n冲突现象：当冲突现象：当K1K2K1K2时时f(K1)=f(K2)f(K1)=f(K2)n n解决冲突的方法解决冲突的方法n n开放开放(kifng)(kifng)定址法；定址法；n nHi=(H(key)+di)MOD
50、 m i=1,2,k (k=m-1)Hi=(H(key)+di)MOD m i=1,2,k (k=m-1)n nmm为哈希表长度；为哈希表长度；di di为增量为增量,di,di的取法：的取法：n n(1)(1)线性探测再散列；线性探测再散列；di=1,2,3,di=1,2,3,n n(2)(2)二次探测再散列；二次探测再散列；di=k2di=k2n n(3)(3)伪随机探测再散列伪随机探测再散列 ：di=di=伪随机数序列伪随机数序列n n再哈希：再哈希：Hi=RHi(key)Hi=RHi(key)n n链地址：所有关键字为同义词的记录存储在同一线性链表中链地址：所有关键字为同义词的记录存储