数据结构第二十讲

1、 第九章本章要点9.1 基本概念9.2 顺序表的静态查找 9.2.1 简单顺序查找 9.2.2 二分查找（折半查找）（重点） 9.2.3 分块查找9.3 树表的动态查找(简单掌握二叉排序树) 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法本章小结9.3.1 二叉排序树 二叉排序树又称为二叉查找树。它或者是空树，或者是满足如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。（2）

2、若它的右子树非空，则右子树上所有结点的值均大于根结点的值。（3）它的左、右子树本身又各是一棵二叉排序树。 下图为一棵二叉排序树思考该排序二叉树有什么特点？中序有序基本思想是：（1）当二叉树为空树时，检索失败。 （2）如果二叉排序树根结点的关键字等于待检索的关键字，则检索成功。 （3）如果二叉排序树根结点的关键字小于待检索的关键字，则在根结点的右子树中用相同的方法继续检索。 （4）如果二叉排序树根结点的关键字大于待检索的关键字，则在根结点的左子树中用相同的方法继续检索。 算法实现BsTree *BstSearch(BsTree *BST,KeyType k) if(BST = NULL) ret

3、urn BST; else if (BST-key = k) return BST; else if(BST-key k) return BstSearch(BST-lchild, k); else return BstSearch(BST-rchild,k);算法性能分析：ASL=?ASL=113 * (1+2+2+3+3+3+3+4+4+4+4+4+4+4)=41 13 课堂练习：ASL=?本章要点9.1 基本概念9.2 顺序表的静态查找 9.2.1 简单顺序查找 9.2.2 二分查找 9.2.3 分块查找9.3 树表的动态查找 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3

4、B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法本章小结9.4.1 散列表的基本概念散列表（HASH）,即哈希表，或杂凑表。通过一个函数直接将记录关键字值映射成一块连续存储空间的地址，这个函数称为Hash(哈希)函数，或散列函数，或杂凑函数。H:K-AH(k)数据表的这种存储方式叫散列存储，或哈希存储。数据表的存储空间称为散列表，或Hash表。哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。学号姓名英语成绩高数成绩34张三687856李四745678王二6

5、68891余六8067Hash 9下标012345678根据关键字直接计算出元素所在位置的函数。例如：设哈希函数为： int(K/3)+1则构造 01、02、05、09、11、13、16、19、21、26、27、31、的散列表(哈希表）为：哈希函数：冲突：两个不同的关键字具有相同的存储位置。3127262119161309110501H(K)=int(K/3)+1121110987654321表项序号02为了有效地使用散列技术，需要解决两方面的问题：构造好的哈希函数，使冲突的现象尽可能的少；设计有效的解决冲突的方法。本章要点9.1 基本概念9.2 顺序表的静态查找 9.2.1 简单顺序查找 9

6、.2.2 二分查找 9.2.3 分块查找9.3 树表的动态查找 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法本章小结9.4.2 散列函数的构造方法(1)（1） 直接定址法取关键字或关键字的某个线性函数值为散列地址，即 H（K）=K 或 H（K）=A*K+B或 H（K）=K+C ；（其中A、B为常数） 直接定址哈希函数示例：某公司一险种投保费交纳表（20年），将年份作关键字，哈希函数取关键字本身，若查找第3

7、年应交纳的保费，只要查找表的第3项即可。地址 01 02 03 20年份 1 2 3. 20保费.9.4.2 散列函数的构造方法(2)（2）平方取中法取关键字平方后的中间几位为哈希函数。 如：K=308，K2=94864，H（K）=486 例如，关键字为3632，则36322=13191424。H(3632)=914。（3） 除后余数法设散列表的地址空间大小为m，取关键 字被不大于m的质数p， 除后所得的余数为哈希函数， 即： H（K）=K MOD p （pm）例：散列表的长度为25，那么散列函数可以为：H(K）key23P取与表长最接近的那个数本章要点9.1 基本概念9.2 顺序表的静态查找

8、 9.2.1 简单顺序查找 9.2.2 二分查找 9.2.3 分块查找9.3 树表的动态查找 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法本章小结假设哈希表的地址范围为0m-l，当对给定的关键字k，由哈希函数H(k)算出的哈希地址为i（0im-1）的位置上已存有记录，这种情况就是冲突现象。处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突，

9、则再求下一个，依次类推。直至新的哈希地址不再发生冲突为止。解决冲突的方法：9.4.3 解决冲突的方法1) 线性探查法基本思想是：将哈希表看成是一个循环表。若地址为d(d=H(K)的单元发生冲突，则依次探查下述地址单元d+1 , d+2 , , m1 , 0 , 1 , , d1 (m为哈希表的长度)直到找到一个空单元或查找到关键字为key的元素为止。若沿着该探查序列查找一遍之后，又回到了地址d，则表示哈希表的存储区已满。9.4.3 解决冲突的方法 设散列函数 H（k）=k m （m为表长, 设m=11) 若发生冲突，设发生冲突的地址为 d , 则沿着一个探查序列逐个探查，那么，探查的地址序列为

10、：d +1, d +2, d +3 , m-1 , 0, 1, , d -1. 29 17 600 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10设散列函数 H(k)=k MOD 11求： 60、17、29、38在散列表中的位置。H(60)= 60 mod 11 = 5 H(17)= 17 mod 11 = 6H(29)= 29 mod 11 = 7H(38)= 38 mod 11 = 560172938【例2】 有一组关键字为：(26，38，73，21，54，35，167，32，7，223，52) 试用线性探查法解决冲突，并构造这组关键字的哈希表。设哈

11、希表的长度为15。 分析：当哈希表的长度为15时，显然P取13比较合理。利用哈希函数H (K) = K %13进行计算，可知上述关键字序列所对应的哈希地址如下： 由此可知不同关键字的哈希地址出现了冲突，依据线性探查解决冲突，最终结果如下表所示：关键字哈希地址0123456789101112131426387321543516732723352关键字26387321543516732722352哈希地址0128829116720ASL=?课堂练习：使用线性探测法将下列元素散列存储在表长为7的表中：3，13，15，14，21，32，42关键字哈希地址01234563131514213242ASL=

12、(1/7)*(1+1+1+1+3+1+6)=2（2）平方探查法 设发生冲突的地址为d，则平方探查法的探查序列为：d+12，d+22，直到找到一个空闲位置为止。平方探查法的数学描述公式为： d0=H(k) di=(d0+i2) % m (1im-1)【例3】 有一组关键字为：（20，30，70，15，8，12，18，63，19）， 试用平方探查法解决冲突，并构造这组关键字的哈希表。设哈希表的长度为11。 分析：当哈希表的长度为11时，P取11比较合理。利用哈希函数H (K) = K %11进行计算，可知上述关键字序列所对应的哈希地址如下：关键字哈希地址01234567891020关键字20307

13、015812186319哈希地址984481788ASL=（1*4+2*2+3+4+6）/9 =21/9307015812186319平方探查法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。例如，若表长m=13，假设在第3个位置发生冲突，则后面探查的位置依次为4、7、12、6、2、0，即可以探查到一半单元。若解决冲突时，探查到一半单元仍找不到一个空闲单元。则表明此哈希表太满，需重新建立哈希表。 课堂练习：使用二次线性探测法将下列元素散列存储在表长为7的表中：3，13，15，14，21，32，42关键字哈希地址012345631

14、31514213242ASL=(1/7)*(1+1+1+1+3+2+4)=13/73）链地址法用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从0到m-1）。这类似于图中的邻接表和树中孩子链表的结构。 关键字20307015812186319哈希地址984481788 由于在各链表中的第一个元素的查找长度为l，第二个元素的查找长度为2，依此类推。因此，在等概率情况下成功的平均查找长度为： ASL=(1*5+2*2+3*l+4*1)9=169 虽然链地址法要多费一些存储空间，但是彻底解决了“堆积”问题，大大

15、提高了查找效率。 本章要点9.1 基本概念9.2 顺序表的静态查找 9.2.1 简单顺序查找 9.2.2 二分查找 9.2.3 分块查找9.3 树表的动态查找 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法本章小结 哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。在哈希表

16、中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关。第一:与装填因子有关 所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即 =n/m。 当 越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。=n/m=9/11第二:与所构造的哈希函数有关 若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生。否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。第三:与解决冲突的方法有关 解决冲突的方法选择的好坏也将减少或增加发生冲突的可能性。 #define NIL -1 #define

17、 M 997 /表长度typedef int KeyType;typedef struct node /哈希表结点类型KeyType key; /关键字域Infodata data；/其他数据域HashType;/用除余法求K的哈希地址的函数h int h(KeyType K) return K%M; /Increment是求增量序列的函数,它依赖于解决冲突的方法int Increment(int i) /用线性探查法求第i个增量di return i; /求在哈希表T0.M-1中第i次探查的哈希地址hi，0iM-1int Hash(KeyType k,int i) return (h(k)+

18、Increment(i)%M; /在哈希表T0.M-1中查找K,成功时返回1。失败有两种情况：找到一个开放址时返回0;表满未找到时返回-1int HashSearch(HashType T,KeyType K,int *pos) int i=0; /记录探查次数 do *pos=Hash(K,i); /求探查地址hi if(T*pos.key=K) return 1; if(T*pos.key=NIL) return 0; /查找到空结点返回 while(+i0) printf(重复的关键字!); else printf(“表满错误,终止程序执行!”); exit(0);根据A0.n-1中结点建立哈希表T0.M-1void CreateHashTable(HashType T,HashType A,int n) if(nM) /用开放定址法处理冲突时，装填因子须不大于1 prin