《数据结构与算法》第10章.ppt

1、南京邮电大学计算机学院 2006年9月,数据结构与算法,Data Structures in C,南京邮电大学计算机学院 2006年9月,第二部分 数据结构,南京邮电大学计算机学院 2006年9月,第10章 跳表和散列表,10.1 字典 10.2 跳表 10.3 散列表,南京邮电大学计算机学院 2006年9月,10.1 字典,10.1 字典 10.2 跳表 10.3 散列表,南京邮电大学计算机学院 2006年9月,字典（dictionary）是记录的集合。字典的每个词条是一个记录，有关单词是该记录的关键字（key），词条中还包含其它信息，不同记录的关键字值各不相同。对字典的存取通过关键字进行。

2、可以认为字典是一种特殊的集合。字典上的基本运算与ADT 8-1的集合抽象数据类型所定义的相同，主要包括搜索、插入和删除。 可以扩充字典的定义使之允许包括重复记录。有重复记录的字典(dictionary with duplicates)，允许字典中有多个相同关键字值的记录，在实现搜索、插入和删除操作时需要一个规则来消除歧义。也就是说，如果要搜索（或删除）关键字值为k的记录，在多个具有相同关键字值的记录中究竟返回哪一个,南京邮电大学计算机学院 2006年9月,10.3 散 列 表,10.1 字典 10.2 跳表 10.3 散列表,南京邮电大学计算机学院 2006年9月,10.3.1 散列技术,散列

3、表是表示集合和字典的另一种有效方法。它提供了一种完全不同的存储和搜索方式：通过将关键字值映射到表中某个位置上来存储元素，而后根据关键字值直接访问。 Loc(key)=h(key) 其中，Loc(key)表示关键字值为key的元素的存储位置。 （1）这个把关键字值映射到位置的函数h称为散列函数； （2）这样建立的表称为散列表,南京邮电大学计算机学院 2006年9月,冲突和同义词 建立全国省、市、自治区的人口统计简表。 h(Hebei)=h(Henan)=h(Hubei)=h(Hunan)=8 h(Shandong)= h(Shanxi)= h(Shanghai)= h(Sichuan)=19 所

4、谓冲突，是指对于关键字集合中的两个关键字值Ki和Kj，当KiKj时，有h(Ki)=h(Kj)，h是散列函数。具有相同散列函数值的关键字值，对该散列函数而言称为同义词,南京邮电大学计算机学院 2006年9月,冲突是不可避免的。 例一：关键字值集合有31个元素，如果我们选择一个有40个元素的记录数组的散列表，也就是说散列地址的范围从0到39。 C4031.31！=40！/9！1042 40314*1049,南京邮电大学计算机学院 2006年9月,10.3.2 散列函数,构造一个散列函数的方法很多，但究竟什么是“好”的散列函数？一个理想的散列函数h应当满足下列条件：（1）能快速计算；（2）具有均匀性

5、。 假定散列表长度为M，那么，散列函数h将关键字值转换成0,M-1中的整数，即0h(key)M。一个均匀的散列函数应当是：如果key是从关键字值集合中随机选取的一个值，则h(key)以同等概率取区间0，M-1中的每一个值,南京邮电大学计算机学院 2006年9月,目前比较通用的散列函数有下列几种： 除留余数法（Division） 除留余数法的散列函数的形式如下： h(key)=key mod M 其中，key是关键字，M是散列表的大小。 M的选择十分重要，如果M选择不当，在某些选择关键字值的方式下，会造成严重冲突。例如，若M=2k，则h(key)=key mod M 的值仅依赖于最后k个比特。如

6、果key是十进制数，则M应避免取10的幂次。多数情况下，选择一个不超过M的素数P，令散列函数为h(key)=key mod P，会收到好的效果,南京邮电大学计算机学院 2006年9月,平方取中法 设关键字用内部码表示，w=18，k=9。内码采用八进制表示。 关键字值内码 内码的平方散列地址 0100 0010000 010 1100 1210000 210 1200 1440000 440,南京邮电大学计算机学院 2006年9月,折叠法 key=12320324111220 若散列地址取3位，则key被划分为5段： 123 203 241 112 20 a)移位法 b)分界法,南京邮电大学计算

7、机学院 2006年9月,数字分析法,南京邮电大学计算机学院 2006年9月,10.3.3 拉链法,解决冲突也称为“溢出”处理技术。有两种常用的解决冲突的方法：拉链的方法和开地址法。拉链的方法也称开散列法，而开地址法又称闭散列法。 采用拉链的方法建立散列表，在极端情况下，散列表中全部为同义词，所以，最坏情况下，为了搜索一个关键字值，需检查全部n个元素。一般情况下有n个元素的散列表的链表的平均长度为n/M,南京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2006年9月,10.3.4 开地址法,地址h(key)被称为基位置 探查表中空闲位置的探查序列形如： h(key),(h(key

8、)+p(1)mod M, (h(key)+p(i)mod M, 根据生成探查序列的规则不同，可以有线性探查法、伪随机探查法、二次探查法和双散列法,南京邮电大学计算机学院 2006年9月,10.3.5 线性探查法,线性探查法是一种最简单的开地址法。它使用下列循环探查序列： h(key),h(key)+1,M-1,0,h(key)-1 从基位置h(key)开始，探查该位置是否被占用，即是否为空位置，如果被占用，则继续检查位置h(key）+1，若该位置也已占用，再检查由探查序列规定的下一个位置，。 可以将线性探查法的探查序列记为： hi=(h(key)+i) mod M 对i=0,1,2,M-1,南

9、京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2006年9月,程序107】 散列表类 template class HashTable:public DynamicSet public: HashTable(int divisor=11); HashTable()deleteht;delete empty; ResultCode Search(T,南京邮电大学计算机学院 2006年9月,private: ResultCode Find(T 后置条件： 若散列表中存在与x的关键字值相同的元素，则将其值赋给x，pos指示该位置，函数返回Success；否则函数返回NotPresen

10、t,南京邮电大学计算机学院 2006年9月,template HashTable:HashTable(int divitor) M=divitor; ht=new TM; empty=new boolM; for (int i=0;iM;i+) emptyi=true; for (i=0;iM;i+) hti=NeverUsed;,南京邮电大学计算机学院 2006年9月,程序108】线性探查散列表的搜索 template ResultCode HashTable:Find(T /基地址,南京邮电大学计算机学院 2006年9月,do if(emptypos) return NotPresent;

11、 if (htpos=x) x=htpos; return Success; pos=(pos+1) % M; while (pos!=i); return NotPresent;,南京邮电大学计算机学院 2006年9月,template ResultCode HashTable: Search(T,南京邮电大学计算机学院 2006年9月,程序109】线性探查散列表的插入 template ResultCode HashTable: Insert(T,南京邮电大学计算机学院 2006年9月,do if (htpos=x) x=htpos;return Duplicate; if (htpos=

12、NeverUsed) htpos=x;emptypos=false; return Success; pos=(pos+1) % M; while(pos!=i); return Overflow;,南京邮电大学计算机学院 2006年9月,程序1010】线性探查散列表的删除 template ResultCode HashTable: Remove(T,南京邮电大学计算机学院 2006年9月,10.3.6 其它开地址法,基本聚集：许多元素在散列表中连成一片， 理想的探查序列应当是散列表位置的一个随机排列。以后搜索关键字时，须再生同样的探查序列,南京邮电大学计算机学院 2006年9月,伪随机探查

13、法 探查序列： 一个简单的伪随机发生器，其计算公式如下： y0h(key) yi+1(yi+p) mod M (i=0,1,2,) 式中，y0为伪随机数发生器的初值，M为散列表的长度，p为与M接近的素数,南京邮电大学计算机学院 2006年9月,二次探查法 探查序列： h(key),h1(key),h2(key),h2i-1(key),h2i(key), h2i-1(key)=(h(key)+i2)mod M，i=1,2,3,(M-1)/2 h2i(key)=(h(key)-i2)mod M，i=1,2,3,(M-1)/2 式中，M是表的大小，它是一个值为4k+3的素数，k是整数，如503,1019等,南京邮电大学计算机学院 2006年9月,南京邮电大学计算机学院 2