交大学位考辅导课件3

1、1 图的定义、术语和存储结构图的定义、术语和存储结构n顶点数顶点数n和边和边(弧弧)的数目的数目e：q无向图：无向图：q有向图：有向图：n完全图：有完全图：有n(n-1)/2条边的无向图条边的无向图;有向完全图：有有向完全图：有n(n-1)条弧的有向图条弧的有向图;稀疏图、稠密图稀疏图、稠密图n子图：子图：G=(V,E),G=(V,E)，若，若V V,且且E E,则称则称G为为G的子图的子图n邻接点：无向图中，邻接点：无向图中，(v,v)E，则，则v,v互为邻接点；互为邻接点；顶点顶点v的度：与的度：与v相关联的边的数目，相关联的边的数目，TD(v)n有向图中有向图中,若若AA，则顶点，则顶点

2、v v邻接到顶点邻接到顶点vv，而顶点，而顶点vv邻邻接自接自v vq出度：以出度：以v为尾的弧的数目，为尾的弧的数目，OD(v)q入度：以入度：以v为头的弧的数目，为头的弧的数目，ID(v) qTD(v)=OD(v)+ID(v) 1(210nne) 1(0nnen路径：路径：q回路（环）回路（环）q简单路径：顶点序列中顶点不重复的路径。简单路径：顶点序列中顶点不重复的路径。 图的存储结构图的存储结构G1.arcs=G2.arcs=表结点表结点头结点头结点V1V2V3V4V5012340121410323242. 图的遍历图的遍历图的遍历目标是解决图的连通性问题、拓扑排序图的遍历目标是解决图的

3、连通性问题、拓扑排序问题、关键路径问题。问题、关键路径问题。图的遍历方法：深度优先算法、广度优先算法图的遍历方法：深度优先算法、广度优先算法深度优先遍历深度优先遍历广度优先遍历广度优先遍历n广度优先搜索遍历类似于树的层次遍历广度优先搜索遍历类似于树的层次遍历n算法算法 3.图的连通性问题图的连通性问题掌握连通分量的求法掌握连通分量的求法651255664365125566435 拓扑排序拓扑排序6 最短路径最短路径10050602010301051005060201030105查找成功：查找成功： pi = 1/n ci= 1,2,3n ASL=1/n1+2+n = (n+1)/2查找不成功：

4、查找不成功：ASL = n+1 , (n, n-11, 0)成功和不成功同概率：成功和不成功同概率：1/2 ASL = *1/n1+2+n+1/2(n+1) = (n+1)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 5348 861 7 13n平衡二叉树q平衡因子：左子深度减去右子深度为 1， 0， 1的二叉排序树。q二叉平衡树的构造（单项

5、左旋/单项右旋）， （左右旋，右左旋）2222右旋右旋左旋左旋左右旋左右旋右左旋右左旋n确定的对应关系f：记录的存储位置 关键字n对应关系f就是哈希函数：f(K)n哈希函数是一个映象，构造哈希函数的方法：q直接定址法；哈希地址：直接取关键字或者关键字的线性函数H(key)=key; or H(key)=a*key+bq数字分析法；分析关键字，取关键字的若干数位组成哈希地址。q平方取中法；取关键字平方后的中间几位为哈希地址较为常用的方法q折叠法：分割关键字、叠加q除留余数法：H(key)=key MOD p p=哈希表长mn冲突现象：当K1K2时f(K1)=f(K2)n解决冲突的方法q开放定址法

6、；Hi=(H(key)+di) MOD m i=1,2,k (k=m-1)m为哈希表长度；di为增量,di的取法：(1)线性探测再散列；di=1,2,3,(2)二次探测再散列；di=k2(3)伪随机探测再散列 ：di=伪随机数序列q再哈希：Hi=RHi(key)q链地址：所有关键字为同义词的记录存储在同一线性链表中q公共溢出区：发生冲突时填入溢出表。 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49先将整个待排序记录分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次全体记录的插入排序。49 38 65 97 76 13

7、 27 49 55 0449 1338 2765 4976 0413 27 49 55 04 49 38 65 97 76 13 55 38 7627 04 6549 49 97第一次第一次分组分组这就是第一趟这就是第一趟排序结果排序结果第二趟的第二趟的“增量增量”就要缩小就要缩小了！了！n冒泡排序：冒泡排序：q具体做法：依次比较第i个关键字和第i+1个关键字，大者排后，一趟得到最大值。（i=1,2,3,4,-n-1)49 38 65 97 76 13 27 4938 49 65 97 76 13 27 4938 49 65 76 97 13 27 4938 49 65 76 13 97 27

8、 4938 49 65 76 13 27 97 4938 49 65 76 13 27 49 9749 38 65 97 76 13 27 49lowhigh27 38 65 97 76 13 49lowhigh27 38 13 97 76 65 49lowhigh27 38 97 76 13 65 49lowhigh27 38 13 76 97 65 49lowhighnknTavglnkik2ikik2i+1kik2ikik2i+149 38 65 97 76 13 27 499749386527137649494938652713769749 38 65 49 76 13 27 9749 38 13 49 76 65 27 9749 38 13 49 76 65 27 9749493813276576974913382765769749 38 65 97 76 13 27 n n个记录看个记录看成成n n个有序个有序的序列的序列 38 49 65 97 13 76 27 第