14数据结构复习.ppt

* * * * * * * 附设一个数组，其中每个分量包含两个域，一个域存储vi（属于V-U）到U最小代价的边的权，另一个域存储该边依附的在U中的顶点。 * * 根据设定的哈希函数和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的象作为记录在表中的存储位置,这种表称为哈希表. * 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 * 拓扑排序的方法 在有向图中选一个没有前驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止 基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。 Dijkstra算法 应用举例——最短路径 A B A E D C 10 50 30 10 100 20 60 S={A} A→B:(A, B)10 A→C:(A, C)∞ A→D: (A, D)30 A→E: (A, E)100 应用举例——最短路径 Dijkstra算法 A B A E D C 10 50 30 10 100 20 60 S={A, B, D} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, E)90 应用举例——最短路径 B D Dijkstra算法 A B A E D C 10 50 30 10 100 20 60 S={A, B, D, C} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 应用举例——最短路径 B D C Dijkstra算法 A B A E D C 10 50 30 10 100 20 60 Dijkstra算法 S={A, B, D, C, E} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 应用举例——最短路径 B D C E * 1.基本概念 —若表中存在特定值,称查找成功,应输出该记录; —否则,称查找不成功(也应输出失败标志或失败位置) 表 查 找 查找成功 查找不成功 ——由同一类型的数据元素（或记录）构成的集合。 ——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 是一种数据结构 第八章 查找表 * 查找方法评价 对将给定的K值进行比较的查找次数的期望称为平均查找长度（ASL：average search length）。 其中： n是数据元素的个数； Pi是第i个数据元素为目标值的概率（通常Pi =1/n）; Ci是找到第i个元素时所经历的比较次数。 统计意义上的数学期望值 意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。 * 8.1.2有序表的查找(折半查找) 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法思想: 首先将待查的K值与有序表R[1]到R[n]的中间位置mid上的结点的关键字进行比较，若相等，则查找完成；否则，若R[mid].keyK，则说明待查找的结点只可能在左子表R[1]到R[mid-1]中，只需在左子表中继续查找；否则在右子表中继续查找。这样，经过一次关键字的比较就缩小了一半的查找区间。如此进行下去，直到找到为止（也存在最后找不到的可 能）。 * 8.3 哈希表 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数:在记录的关键字与记录的存储地址之间建立的一种对应关系叫~ 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ai.ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字 关键字 集合 存储地址 集合 hash * 哈希表:应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~ 哈希地址:所得记录的存储位置.又称散列地址. 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~ * 处理冲突的方法