1、主要内容：1. 图2.查找、排序,数据结构学位考复习课(3),第七章 图,考核内容及要求：熟练掌握图的相关概念、性质、存储结构熟练掌握遍历：深度优先遍历、广度优先遍历过程；熟练掌握连通分量的求法；熟练掌握最小生成树、最短路径概念与方法；掌握拓扑排序、关键路径的求法及实现方法。,1 图的定义、术语和存储结构,图：图结构中，任意两个结点之间的关系是任意的，图中任意两个数据元素之间都可能相关图的抽象数据类型顶点、弧、边有向图（digraph)有向图G1=(V1,A1)，其中V1=v1,v2,v3,v4,A1=,无向图(undigraph)无向图G2=(V2,E2)V2=v1,v2,v3,v4,v5,
2、 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),有向图,无向图,顶点数n和边(弧)的数目e：无向图：有向图：完全图：有n(n-1)/2条边的无向图;有向完全图：有n(n-1)条弧的有向图;稀疏图、稠密图子图：G=(V,E),G=(V,E)，若V V,且E E,则称G为G的子图邻接点：无向图中，(v,v)E，则v,v互为邻接点；顶点v的度：与v相关联的边的数目，TD(v)有向图中,若A，则顶点v邻接到顶点v，而顶点v邻接自v出度：以v为尾的弧的数目，OD(v)入度：以v为头的弧的数目，ID(v) TD(v)=OD(v)+ID(v),路径：回
3、路（环）简单路径：顶点序列中顶点不重复的路径。连通图、连通分量、强连通图、强连通分量：,一个连通图的生成树：一个极小连通子图，含有图中全部结点，但只有足以构成一棵树的n-1条边。一棵有n个顶点的生成树有且仅有n-1条边但有n-1条边的图不一定是生成树有向图：如果有一个顶点的入度为0，其余顶点的入度都为1，则是一棵有向树。,图的存储结构,数组表示法（邻接矩阵）： 用两个数组分别存放顶点信息和边（弧）信息,G1.VEXS4=V1 V2 V3 V4,G1,G2,图的邻接矩阵 Aij=1 /若存在 Aij=0 /若不存在 无向图：第i行分量的和为结点vi的度 有向图：第i行分量的和为结点vi的出度；
4、第i列分量的和为结点vi的入度 网的邻接矩阵 Aij=无穷大 间无边 =权 间有边 问题：为什么放无穷大而不放0,邻接表：一种链式存储结构为图中的每一个顶点创建一个单链表，其中的结点表示依附于顶点的边(以该顶点为尾的弧),无向图的邻接表中，顶点v的度就是该顶点的单链表中的结点数；有向图中，第i个链表的结点数是该顶点的出度；如何求有向图中顶点的入度？有向图的逆邻接表。,有向图G1的邻接表,有向图G1的逆邻接表,十字链表：有向图的链式存储,邻接多重表：无向图的另一种链式存储结构。,2. 图的遍历,图的遍历目标是解决图的连通性问题、拓扑排序问题、关键路径问题。图的遍历方法：深度优先算法、广度优先算法
5、,深度优先遍历,深度优先搜索遍历：类似于树的先根遍历，是树的先根遍历的推广算法：1.假设图中所有顶点的初始状态为：未访问；2.从图中某个未访问的顶点v出发，访问此结点；3.依次从v的邻接点出发深度优先遍历图，直到图中所有与v有路径的顶点都被访问到；4.若图中还有未访问结点，则另选一个结点作起始点，重复2、3过程。,v1,V2,v6,v4,v5,v8,v3,v7,图解深度优先遍历过程,一个非连同图的深度优先遍历过程图解,H,A,B,L,M,C,D,E,F,G,H,I,J,K,可能的遍历序列：A L M J B F C D E G I H K,注：图的存储结构没有给定的情况下，图的遍历序列不是唯一
6、的。,广度优先遍历,广度优先搜索遍历类似于树的层次遍历算法,v1,V2,v6,v4,v5,v8,v3,v7,一个非连同图的广度优先遍历过程图解,H,A,B,L,M,C,D,E,F,G,H,I,J,K,可能的遍历序列：A L F C B M D E G I H K,3.图的连通性问题掌握连通分量的求法,无向图的连通分量和生成树由图的遍历得出：对于连通图，从图中任一顶点出发，可以访问到图中的所有顶点；对于非连通图，需要从多个顶点出发，搜索到树的各个连通分量中的顶点集。,4 掌握最小生成树的概念和求法,最小生成树构造连通网的最小代价生成树。MST性质：假设N=(V,E)是一个连通网，U是顶点集V上的
7、一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vV-U,则必存在一棵包含边(u,v)的最小生成树。构造最小生成树的算法：Prin算法和Kruskal算法。,Prim算法构造最小生成树的过程：,Kruskal算法构造最小生成树的过程,两种算法的区别：普鲁姆算法：基于连通地选择，避免回路克鲁斯卡儿算法：离散地选择，避免回路,拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，就是拓扑排序。偏序：集合中仅有部分成员之间可以比较；全序：集合中全体成员之间均可比较。AOV网：顶点表示活动，弧表示活动之间的优先关系的有向图称为顶点表示活动的网。,偏序,全序,5 拓扑排序,进行拓扑排序的方
8、法：在有向图中选一个没有前驱的顶点且输出；从图中删除该结点和所有以该结点为尾的弧。重复上述操作。若可以输出全部顶点，则该图中不存在环，否则存在环。例如：算法实现：以邻接表的方法存储有向图；头结点增加信息：顶点入度；增加一个栈：存放入度为0的顶点。,6 最短路径,7.6.1 从某个源点到其余各顶点的最短路径Dijkstra算法：按路径长度递增的次序产生最短路径Di表示当前所找到的从点v到每个终点vi的最短路径的长度。Di初值：v到vi的弧的权值；则：初值最小的路径就是从v出发的最短的一条路径下面按照长度递增多次序产生各个终点的最短路径,Dijkstra算法 求最短路径,查找,考核内容及要求：熟练
9、掌握顺序查找、有序表的查找、索引顺序查找、二分查找法及HASHING查找技术；了解平衡二叉树、B树及B+树的概念；理解查找速度的分析及比较、算法复杂性的级别。,1 顺序表的查找,物理存储： 顺序表方式： typedef struct ElemType *elem; int length; SSTable查找过程：从表中最后一个元素开始，逐个比较，相等则比较成功，否则直到第一个元素。,Int Search_Seq(SSTable ST, KeyType key) /从尾部依次比较key和数据元素的关键字， /当比到0下标才成功则查找不成功，返回0 /否则返回下标i ST.elem0.key =
10、key; for (i=ST.length; !EQ(ST.elemi.key, key); -i); return i; /Search-Seq0下标为监视哨,时间复杂度O(n)平均查找长度： ASL =sum(pici) i=1n,查找成功： pi = 1/n ci= 1,2,3n ASL=1/n1+2+n = (n+1)/2查找不成功：ASL = n+1 , (n, n-11, 0)成功和不成功同概率：1/2 ASL = *1/n1+2+n+1/2(n+1) = (n+1),折半查找：先确定待查记录的范围，逐步缩小范围直到找到或找不到。例：在下列数据元素中查找关键字为21和85的数据元素
11、分析：设置两个指针low ,high指示待查元素所在范围的上界和下界。mid（low+high）/2ST.elemmid.key=key:查找成功ST.elemmid.keykey: high=mid-1 low=high:查找不成功,2 有序表的查找,low,high,mid,int Search_Bin (SSTable ST, KeyTable key) /对有序表的查找采用折半查找，逐步缩小 /查找范围，直到找到或找不到，返回值为 /找到返回下标，找不到返回0 low = 1; high = ST.length; while (low=high) mid = (low+high)/2;
12、 if EQ(key, ST.elemmid.key) return mid; else if LT(key, ST.elemmid.key) high = mid 1; else low = mid +1; return OK; /Search_Bin 时间复杂度：O(log2n), ASL = log2(n+1)+1 (按照满二叉树),分块查找，索引顺序查找分块有序两步查找：确定待查记录所在地子表（块）；在子表中顺序查找,3 索引顺序表的查找,4.动态查找表二叉排序树,例 已知如下长度为8的表，试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率下
13、查找成功的平均查找长度。（Mon, Tiger, Win, Butter, Fish, Fly, Pig,Cat),平衡二叉树平衡因子：左子深度减去右子深度为 1， 0， 1的二叉排序树。二叉平衡树的构造（单项左旋/单项右旋）， （左右旋，右左旋）,右旋,左旋,左右旋,右左旋,9.3 哈希表,确定的对应关系f：记录的存储位置 关键字对应关系f就是哈希函数：f(K)哈希函数是一个映象，构造哈希函数的方法：直接定址法；哈希地址：直接取关键字或者关键字的线性函数H(key)=key; or H(key)=a*key+b数字分析法；分析关键字，取关键字的若干数位组成哈希地址。平方取中法；取关键字平方后
14、的中间几位为哈希地址较为常用的方法折叠法：分割关键字、叠加除留余数法：H(key)=key MOD p p=哈希表长m,冲突现象：当K1K2时f(K1)=f(K2)解决冲突的方法开放定址法；Hi=(H(key)+di) MOD m i=1,2,k (kL.ri+1.key) 交换两个记录时间复杂度：O(n2),49 38 65 97 76 13 27 49,low,high,27 38 65 97 76 13 49,low,high,27 38 13 97 76 65 49,low,high,27 38 97 76 13 65 49,low,high,27 38 13 76 97 65 49,
15、low,high,快速排序的算法,快速排序算法：Int Partition (SqList /平均时间：K为常数因子。就平均时间而言快速排序是目前被认为最好的一种内部排序方法。,4 选择排序,选择排序基本思想：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。简单选择排序：Void SelectSort(SqList ,堆排序堆的定义：n个元素的序列k1,k2,kn当且仅当满足下列关系时，称为堆：思想：每趟选取最小关键字、次小关键字、次次小关键字-。 做法：建立一个完全二叉树，任何非终端结点的值均不大于其左、右孩子结点的值。输出堆顶，将其余的元素建立
16、新的堆。,kik2ikik2i+1,kik2ikik2i+1,49 38 65 97 76 13 27 49,49 38 65 49 76 13 27 97,49 38 13 49 76 65 27 97,49 38 13 49 76 65 27 97,5 归并排序,思想：将两个或两个以上的有序表组合成一个新的有序表。具体做法：以两路归并示例,49 38 65 97 76 13 27,n个记录看成n个有序的序列, 38 49 65 97 13 76 27,第一趟合并, 38 49 65 97 13 27 76, 13 27 38 49 65 76 97,第二趟合并,第三趟合并,外部排序,考核要
17、求：了解外存及分类技术简介 了解缓冲区管理、初始合并串、置换选择分类技术、胜者树及败者树,3. 置换-选择排序目标：减少m(初始归并段的个数)来减少归并趟数。 m=upper(n/l), n为外部文件中记录数， l为每段记录数目。 故增大l, l受内存空间限制 置换-选择排序：在得到所有初始归并段的过程中，选择最小（大）关键字和输入、输出交叉或同时进行。外部排序方法：思想：分段读入内存、排序；分段写入外存、有序段归并。,已知图G的邻接表如下图所示，从其顶点V1出发的深度优先搜索序列和广度优先搜索序列分别写出来，并按图中给出的存储结构给出深度优先生成树和广度优先生成树。,典型例题图、查找、排序,
18、7.5 已知以二维数组表示的图的邻接矩阵如下，分别画出自顶点1出发进行遍历得到的深度优先和广度优先生成树,1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0,给出如图所示的无向图的邻接矩阵和邻接表，并从其顶点V
19、1出发的深度优先搜索序列和广度优先搜索序列分别写出来。,已知图2所示的图，若从顶点A出发按深度优先搜索法进行遍历，则可能得到的遍历序列为：A) A,B,E,C,D,FB)A,C,F,E,B,DC) A,E,B,C,F,DD) A,E,D,F,C,B,7.9 试列出下图中全部可能的拓扑有序序列，并指出7.5.1节中算法Topological Sort求得到是哪一个序列。,9.8 已知含12个关键字的有序表及其相应权值如下，画出对以下有序表进行折半查找的判断树。,10.1 以关键字序列(53, 87, 12, 61,98,17, 97, 75, 53, 26)为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态： (1) 希尔排序(增量d1=5) (2) 快速排序 (3)堆排序,10.2 判别以下序列是否为堆，如果不是，则把它调整为堆。 (1) (100,86,48,73,35,39,42,57,66,21); (2) (12,70,33,65,24,56,48,92,86,33),考试题型,选择题（20题，每题一分，共20分）填空题（10空，每空一分）算法填空题（5空，每空两分）操作题（一般45个大题目，共40分）算法设计题（2题，每题10分）,祝考试顺利！,注意复习的原则：简单为主！,
