自考数据结构-串讲笔记.ppt

(2)二次探测再散列 d2i-1 = (d + i2) mod m 　d2i = (d - i2) mod m 1=i=(m-1)/2 特点： 将同义词来回散列在第一次产生冲突时的Hash地址的两端 探测序列是跳跃似的 减少堆积（二次聚集）的发生 缺点：不易探测到整个Hash表空间 * (3)伪随机探测再散列 di = (d + Ri) mod m m为Hash表长 d为冲突产生时的Hash地址 Ri：R1, R2, … , Rm-1是一个伪随机数序列 * 2、再哈希法 　　当冲突产生时，通过再计算另一个哈希函数地址解决冲突。即为构造不同的哈希函数。 　　di = RHi(K) 　　i=1,2,…,k 　　其中： RHi(K) ? RHj(K) ,即RHi均是不同的Hash函数。 　　优点：不易产生堆积或聚集。 　　缺点：计算量大。 * 3、链地址法 　　将所有关键字为同义词的记录存储在同一单链表中。 　　假设Hash函数产生的哈希地址在区间0~m-1上，则将Hash表定义为一个由m个头指针组成的指针数组chainHash[m]，凡Hash地址为 i 的记录都插入到以数组元素chainHash[i]为头指针的链表中，并保持同义词在同一线性链表中按关键字有序。 　　优缺点 　　优点：不会产生堆积；空间是动态申请的，适用于造表前无法确定表长的情况。 　　缺点：空间开销大。 * 三、哈希表的算法分析 哈希表的装填因子 ?体现哈希表的装满程度 哈希表的查找效率的决定因素 哈希函数 解决冲突的方法 哈希表的装填因子 表中填入的记录数 哈希表的长度 ?= = n m * 　　假设Hash函数均匀的前提下，不同的解决冲突的方法得到的Hash表的ASL不同，且不是表中关键字个数n的函数，而是装填因子?的函数。如下表所示： 解决冲突的方法 平均查找长度ASL 线性探测法 二次探测、随机探测 、再哈希法 链地址法 (1+1/(1-?))/2 (1+1/(1 -?)2)/2 -ln(1-?)/? 1/(1-?) 1+ ? /2 ? + exp(-? ) 成功查找 不成功查找 * 　　?越小，发生冲突的可能性越小。 　　?越大，发生冲突的可能性越大。 　　因此只要?选择合适，不管n多大，哈希表的平均查找长度就会限定在一个范围之内。 ? ASL 链 线性 随机 （本章结束） * 第十章　文件 　　基本概念 　　文件：是性质相同的记录的集合 　　1.文件的逻辑结构及操作 　　2.文件的存储结构：顺序文件、索引文件、散列文件和多关键字文件 * 顺序文件 顺序文件的顺序存取 顺序文件的随机存取 顺序文件按关键字存取 优点：顺序存取速度快 * 一、多关键字排序 　　设n个记录{R1,R2,…,Rn}，Ri的关键字为（K ,K ,…,K ），d个关键字对任意记录Ri和Rj，若他们的关键字满足（ K ,K ,…,K ）（ K ,K ,…,K 　 ），则称该记录序列有序。 * 　　举例 　　扑克牌按面值、花色排序。 　　多关键字排序方法 　　最高位优先法（MSD）：先按主关键字排序，再按次关键字排序。 　　最低位优先法（LSD）：先按次关键字排序，再按主关键字排序。 　　结论 　　无论MSD和LSD，都是采用若干次的“分配”与“收集”。 　　基数排序就是对单逻辑关键字采用“分配”与“收集”实现排序的方法。 * 二、基数排序 　　基数排序是借助 “分配”与“收集”两种操作对单逻辑关键字采用进行排序的一种内部排序方法 　　单逻辑关键字：可以看成由若干分关键字复合而成 　　设关键字Keyi= K K K …K …K ，其中 　　K 称为分关键字；C0≤ K ≤ Crd-1(1≤i≤n,1≤l≤d) 　　d: 关键字的最大位数 　　rd: 基（分关键字可取值范围） （本章结束） * 第九章　查找 §１．基本概念 一、对查找表的操作 1、查询 2、检索 3、插入 4、删除 1类 2类 * 二、查找表的分类 　　1、称只包含1类操作的查找为静态查找，对应的表叫静态查找表； 　　2、称既包含1类操作，又包含2类操作的查找为动态查找，对应的表叫动态查找表。 * 三、查找结果 查找成功：若表中存在要查找的记录。 查找失败：若表中不存在关键字等于给定值的记录。 * 四、衡量查找算法效率的标准——平均查找长度 平均查找长度 对于含有n个记录的查找表，查找成功时的平均查找长度为： 　　ASL=?PiCi Pi：查找第i个元素（记录）的概率。 Ci：查找第i个元素（记录）所需进行的比较次数。 * §2．静态查找表一、顺序表的查找　　　　　　——顺序查找 　　静态查找表的组织方式。 　　顺序表，即采用线性表的顺序存