1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构数据结构期末复习(2)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第六章第六章 图图本章的主要内容是:图的逻辑结构图的存储结构及实现图的连通性最小生成树最短路径AOV网与拓扑排序AOE网与关键路径 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的定义6.1 图的逻辑结构图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数
2、不能为零，但可以没有边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图的基本术语 简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图 非简单
3、图 简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图的基本术语 邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。6.1 图的逻辑
4、结构图的基本术语 顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。6.1 图的逻辑结构图的基本术语 V1V2V3V42785数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则
5、路径也是有方向的，顶点序列满足E。6.1 图的逻辑结构图的基本术语 V1V2V3V4V5v一般情况下，图中的路径不惟一。V1 到V4的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径长度：路径长度：6.1 图的逻辑结构图的基本术语 非带权图路径上边的个数带权图路径上各边的权之和V1V2V3V4V5V1 V4：长度为1V1 V2 V3 V4：长度为3V1 V2 V5V3 V4：长度为4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径长度：路径长度：6.1 图的逻辑结构图的基本术语 非带权图路径上边的个
6、数带权图路径上各边的权之和V1 V4：长度为8V1 V2 V3 V4：长度为7V1 V2 V5V3 V4：长度为15V1V2V3V4V5256328数据结构（数据结构（C版）版）清华大学出版社清华大学出版社连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。6.1 图的逻辑结构图的基本术语 如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社强连通图：在有向图中，对图中
7、任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。6.1 图的逻辑结构图的基本术语 如何求得一个非连通图的连通分量?数据结构（数据结构（C版）版）清华大学出版社清华大学出版社生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如何理解极小连通子图?6.1 图的逻辑结构图的基本术语 多构成回路少不连通含有n-1条边数据结构（数据结构（C版）版）清华大学出版社清华大学出
8、版社V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林6.1 图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的遍历操作图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。6.1 图的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.深度优先遍历 基本思想：访问顶点v；从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。6.1 图的逻辑结构数
9、据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1V2 V2V4 V4V5 V5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1V2 V2V4 V4V5V8 V8数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8
10、 V1遍历序列：V1V2 V2V4 V4V5V8数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：V1 V7V2V4V5V8V3 V3V6 V6V7数据结构（数据结构（C版）版）清华大学出版社清华大学出版社2.广度优先遍历 基本思想：访问顶点v；依次访问v的各个未被访问的邻接点v1,v2,vk；分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。6.
11、1 图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列?入队序列?出队序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列?入队序列?出队序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列?入队序列?出队序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5数据结构（数据结构（C版）版）清华大学出版社清华大
12、学出版社广度优先遍历序列?入队序列?出队序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列?入队序列?出队序列?6.1 图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。6.2 图的存储结构及实现假设图G(V，E)有n个顶点，则
13、邻接矩阵是一个nn的方阵，定义为：arcij1 若(vi,vj)E（或E）0 其它数据结构（数据结构（C版）版）清华大学出版社清华大学出版社无向图的邻接矩阵的特点？无向图的邻接矩阵6.2 图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4主对角线为 0 且一定是对称矩阵。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社网图的邻接矩阵6.2 图的存储结构及实现网图的邻接矩阵可定义为：arcij wij 若(vi,vj)E（或E）0 若i=j 其他V1V2V3
14、V42785 0 2 5 0 0 8 7 0 arc=数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。6.2 图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接表有两种结点结构：顶点表结点和边表结点。vertexfirstedge adjvex next
15、顶点表 边 表 vertex：数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。6.2 图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社10323101 V1 V2 V3 V40123vertex firstedge6.2 图的存储结构及实现V1V3V4V2无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社10323101 V1 V2 V3 V4012
16、3vertex firstedge6.2 图的存储结构及实现V1V3V4V2无向图的邻接表如何求顶点 i 的度？顶点i的边表中结点的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断顶点 i 和顶点 j之间是否存在边?测试顶点 i 的边表中是否存在终点为 j 的结点。6.2 图的存储结构及实现10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2无向图的邻接表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123vertex fir
17、stedge如何求顶点 i 的出度？顶点 i 的出边表中结点的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的入度？各顶点的出边表中以顶点 i 为终点的结点个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点 i 的所有邻接点？遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接
18、点。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现网图的邻接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 0数据结构（数据结构（C版）版）清华大学出版社清华大学出版社十字链表 邻接表6.2 图的存储结构及实现逆邻接表将邻接表与逆邻接表合二为一?为什么要合并？V1V2V3V412 3 0v1v2v3v401231 3 0 2 v1v2v3v4012303 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社十字链表的结点结构vertexfirstinfirstout顶点表结点tailve
19、x headvex headlink taillink边表结点tailvex：弧的起点在顶点表中的下标；headvex：弧的终点在顶点表中的下标；headlink：入边表指针域；taillink：出边表指针域。6.2 图的存储结构及实现vertex：数据域，存放顶点信息；firstin：入边表头指针；firstout：出边表头指针；数据结构（数据结构（C版）版）清华大学出版社清华大学出版社3 03 1 3210V1V2V3V42 3 0 10 2 6.2 图的存储结构及实现十字链表存储有向图 V1V2V3V4v3v4v4v1v1v2v1v3v4v2数据结构（数据结构（C版）版）清华大学出版社清
20、华大学出版社生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。应用举例最小生成树最小生成树最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U=u0（u0V），TE=，重复执行下述操作：在所有uU，vV-U的边
21、中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。关键:是如何找到连接U和V-U的最短边。普里姆（Prim）算法 应用举例最小生成树利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社U=A V-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19 251234192646381725应用举例最小生成树ABEDCFPrim算法 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法 应用举例最小生
22、成树251234192646381725ABEDCFU=A,F V-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法 应用举例最小生成树251234192646381725ABEDCFU=A,F,C V-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)26 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法 应用举例最小生成树251234192646381725ABEDCFU=A,F,C,D V-U=B,Ecost=(A,B)34,(F,E)2
23、6 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法 应用举例最小生成树251234192646381725ABEDCFU=A,F,C,D,E V-U=Bcost=(E,B)12 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法 应用举例最小生成树251234192646381725ABEDCFU=A,F,C,D,E,B V-U=数据结构（数据结构（C版）版）清华大学出版社清华大学出版社克鲁斯卡尔（Kruskal）算法 基本思想：设无向连通网为G(V,E)，令G的最小生成树为T(U,TE)，其初态为UV，TE，然后，按照边的权值由小到大的顺序，考察G
24、的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。应用举例最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF应用举例最小生成树ABEDCF连通分量A,B,C,D,E,F数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF应用举例最小生成树ABED
25、CF连通分量A,B,C,D,E,F12连通分量A,B,E,C,D,F数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF应用举例最小生成树ABEDCF连通分量A,B,E,C,D,F12连通分量A,F,B,C,D,E17数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF应用举例最小生成树ABEDCF连通分量A,B,E,C,D,F12连通分量A,F,B,E,C,D1917数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF应用举例最小生
26、成树ABEDCF连通分量A,F,B,E,C,D12连通分量A,F,C,D,B,E191725数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF应用举例最小生成树ABEDCF连通分量A,F,C,D,B,E12连通分量A,F,C,D,B,E19172526数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在非网图中，最短路径是指两顶点之间经历的边数最少的路径。应用举例最短路径最短路径 BAEDCAE：1ADE：2 ADCE：3ABCE：3数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例最短路径最短路径 在网图中，最短
27、路径是指两顶点之间经历的边上权值之和最短的路径。BAEDC105030101002060AE：100ADE：90 ADCE：60 ABCE：70数据结构（数据结构（C版）版）清华大学出版社清华大学出版社问题描述：给定带权有向图G(V,E)和源点vV，求从v到G中其余各顶点的最短路径。单源点最短路径问题 应用举例最短路径应用实例计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想：设置一个集
28、合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,vk，就将vk加入集合S中，并将路径v,vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。Dijkstra算法应用举例最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 集 合 V-S集合 SvkvviDijkstra算法的基本思想应用举例最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=AAB:(A,B)10AC:(A,C)
29、AD:(A,D)30AE:(A,E)100应用举例最短路径Dijkstra算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=A,BAB:(A,B)10AC:(A,B,C)60AD:(A,D)30AE:(A,E)100应用举例最短路径BDijkstra算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060S=A,B,DAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,E)90应用举例最短路径BDDijkstra算法数据结构（数据结构（C版）版）清华大学出版社清
30、华大学出版社ABAEDC105030101002060S=A,B,D,CAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60应用举例最短路径BDCDijkstra算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABAEDC105030101002060Dijkstra算法S=A,B,D,C,EAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60应用举例最短路径BDCE数据结构（数据结构（C版）版）清华大学出版社清华大学出版社AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系
31、，称这样的有向图为顶点表示活动的网，简称AOV网。应用举例拓扑排序AOV网什么是工程？工程有什么共性？AOV网中出现回路意味着什么？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。应用举例拓扑排序AOV网2.AOV网中不能出现回路。AOV网特点：1.AOV网中的弧表示活动之间存在的某种制约关系。什么是工程？工程有什么共性？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社编号编号课程名称课程名称先修课先修课C1高等数学高等数学无无C2计算机导论计算机
32、导论无无C3离散数学离散数学C1C4程序设计程序设计C1,C2C5数据结构数据结构C3，C4C6计算机原理计算机原理C2，C4C7数据库原理数据库原理C4，C5，C6应用举例拓扑排序C1C2C3C4C6C5C7AOV网数据结构（数据结构（C版）版）清华大学出版社清华大学出版社拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序。应用举例拓扑排序拓扑排序拓扑序列使得AOV网中所有应存在的前驱和后继关系都能
33、得到满足。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想：从AOV网中选择一个没有前驱的顶点并且输出；从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。应用举例拓扑排序拓扑排序拓扑排序的结果？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序C1C2C3C4C6C5C7拓扑序列：C1,C2,C3,C4,C5,C6,C7 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序C1C2C3C4C6C5拓扑序列：C1,C2,C3,说明AOV网中存在
34、回路。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社设计数据结构 1.图的存储结构：采用邻接表存储，在顶点表中增加一个入度域。顶点表结点 in vertexfirstedge2.栈S：存储所有无前驱的顶点。应用举例拓扑排序数据结构（数据结构（C版）版）清华大学出版社清华大学出版社(a)一个AOV网 (b)AOV网的邻接表存储 012345 in vertex firstedge3 A 0 B1 C3 D0 E2 F 0 3 0 0 5 2 3 3 5 ABCDEF应用举例拓扑排序拓扑排序数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序012345
35、in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序012345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE0C21数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序012345 in vertex firstedge 3 A 0 B 0 C 2 D 0 E 1 F 0 3 0 0 5 2 3 3
36、5 ABCDFBC21数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序012345 in vertex firstedge 2 A 0 B 0 C 1 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ABDFB D01数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序012345 in vertex firstedge 1 A 0 B 0 C 0 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ADF00AF数据结构（数据结构（C版）版）清华大学出版社清华大学出版社应用举例拓扑排序拓扑排序012345 in ve
37、rtex firstedge 0 A 0 B 0 C 0 D 0 E 0 F 0 3 0 0 5 2 3 3 5 AFAF数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.栈S初始化；累加器count初始化；2.扫描顶点表，将没有前驱的顶点压栈；3.当栈S非空时循环 3.1 vj=退出栈顶元素；输出vj；累加器加1；3.2 将顶点vj的各个邻接点的入度减1；3.3 将新的入度为0的顶点入栈；4.if(count0&ri!=k)i-;return i;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查
38、找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。7.2 线性表的查找技术改进的顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找k35iii哨兵35查找方向数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。7.2 线性表的查找技术改进的顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找k25ii25查找方向iiii
39、iii数据结构（数据结构（C版）版）清华大学出版社清华大学出版社int SeqSearch2(int r,int n,int k)/数组r1 rn存放查找集合 r0=k;i=n;while(ri!=k)i-;return i;7.2 线性表的查找技术改进的顺序查找ASL=niicp1+-=niiinp1)1(i=(n+1)/2=O(n)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。7.2 线性表的查找技术顺序查找的缺点：算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有
40、要求，无论记录是否按关键码有序均可。顺序查找的优点：数据结构（数据结构（C版）版）清华大学出版社清华大学出版社折半查找使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。7.2 线性表的查找技术数据结构（数据结构（C版）版）清华大学出版社清华大学出版社折半查找的基本思想7.2 线性表的查找技术 r1 rmid-1 r
41、mid rmid+1 rn 如果krmid 查找左半区 查找右半区k（mid=(1+n)/2）数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例：查找值为14的记录的过程：0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 311418147221822low=4mid=4 21high数据结构（数据结构（C版）版）清华大学出版社清华大学出版社具有n个结点的折半查找判定树的深度为 查找成功：在表中查找任一记录的过
42、程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。7.2 线性表的查找技术。1log2+n折半查找性能分析 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉排序树二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左右子树也都是二叉排序树。7.3 树表的查找技术二叉排
43、序树的定义采用的是递归方法。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉排序树 非二叉排序树二叉排序树7.3 树表的查找技术6390554258104567837063605582581045678370中序遍历二叉排序树可以得到一个按关键码有序的序列 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉排序树的插入分析：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。7.3 树表的查找技术void InsertBST(BiNode*root,BiNode*s);数据结构（数据结构（C版）版）清华大学
44、出版社清华大学出版社例：插入值为98的结点7.3 树表的查找技术63559058 70985563root90587098sroot数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉排序树的删除在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。分三种情况讨论：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树。7.3 树表的查找技术数据结构（数据结构（C版）版）清华大学出版社清华大学出版社情况1被删除的结点是叶子结点7.3 树表的查找技术50302080908588403532503020809085403532操作：将双亲结点中相
45、应指针域的值改为空。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社情况2被删除的结点只有左子树或者只有右子树操作：将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。7.3 树表的查找技术50302080908588403532503020908588403532数据结构（数据结构（C版）版）清华大学出版社清华大学出版社情况3被删除的结点既有左子树也有右子树操作：以其前驱（左子树中的最大值）替代之，然后再删除该前驱结点。7.3 树表的查找技术50302080908588403532403020809085883532数据结构（数据结构（C版）版）清华大学出版社清华大学出版
46、社例：在二叉排序树中查找关键字值为35，95的过程：7.3 树表的查找技术50302080908588403532二叉排序树的查找50302080908588403532数据结构（数据结构（C版）版）清华大学出版社清华大学出版社平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：根结点的左子树和右子树的深度最多相差1;根结点的左子树和右子树也都是平衡二叉树。平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。平衡二叉树7.3 树表的查找技术数据结构（数据结构（C版）版）清华大学出版社清华大学出版社最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且
47、平衡因子的绝对值大于1的结点为根的子树。7.3 树表的查找技术542814平衡二叉树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：1.LL型 2.RR型 3.LR型 4.RL型7.3 树表的查找技术平衡二叉树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社插入前 插入后，调整前 调整后7.3 树表的查找技术平衡二叉树LL型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX旋转：扁担原理；冲突：旋转优先数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6
48、12例:LL型 7.3 树表的查找技术108791291012876数据结构（数据结构（C版）版）清华大学出版社清华大学出版社插入后，调整前 先顺时针旋转 再逆时针旋转7.3 树表的查找技术平衡二叉树LR型数据结构（数据结构（C版）版）清华大学出版社清华大学出版社课堂练习：设有关键码序列5,4,2,8,6,9，构造平衡树5427.3 树表的查找技术LL型42586数据结构（数据结构（C版）版）清华大学出版社清华大学出版社864256842585642课堂练习：设有关键码序列5,4,2,8,6,9，构造平衡树7.3 树表的查找技术RL型旋转1次RL型旋转2次数据结构（数据结构（C版）版）清华大学
49、出版社清华大学出版社856429RR型8465297.3 树表的查找技术课堂练习：设有关键码序列5,4,2,8,6,9，构造平衡树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社概 述散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。7.3 散列表的查找技术关键码集合ki riH(ki)H数据结构（数据结构（C版）版）清华大学出版社清华大学出版社散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。概 述7.3 散列表的查找技术关键码集合ki riH(ki)H散列表数组数据结构（
50、数据结构（C版）版）清华大学出版社清华大学出版社散列函数：将关键码映射为散列表中适当存储位置的函数。概 述7.3 散列表的查找技术散列表关键码集合ki riH(ki)H散列函数数组数据结构（数据结构（C版）版）清华大学出版社清华大学出版社散列地址：由散列函数所得的存储位置址。概 述7.3 散列表的查找技术散列表关键码集合ki riH(ki)H散列函数散列地址下标数组数据结构（数据结构（C版）版）清华大学出版社清华大学出版社散列技术的关键问题：散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。冲突的处理。如何采取合适的处理冲突方法来解决冲突。7.3 散列表的查找技术概 述数据结构（
