《数据结构》(C语言版)第九章_查找

1、学习提要：学习提要：1.掌握顺序表和有序表的查找方法及其平均掌握顺序表和有序表的查找方法及其平均查找长度的计算方法。查找长度的计算方法。2.熟练掌握二叉排序树的构造和查找方法。熟练掌握二叉排序树的构造和查找方法。3.掌握平衡二叉树的维护平衡的方法。掌握平衡二叉树的维护平衡的方法。4.理解理解B-和和B+树的特点及它们的建树过程。树的特点及它们的建树过程。5.熟练掌握哈希表的构造方法，深刻理解哈熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。希表与其它结构的表的实质性的差别。6.掌握按定义计算各种查找方法在掌握按定义计算各种查找方法在等等概率情况下查找成功时的平均查找长度概

2、率情况下查找成功时的平均查找长度。重难点内容：重难点内容： 顺序查找和折半查找的实现算法，顺序查找和折半查找的实现算法， 二叉排序树的构造和查找方法，二叉排序树的构造和查找方法， B-树的构造和查找方法，树的构造和查找方法， 哈希表的构造以及解决冲突的方法，哈希表的构造以及解决冲突的方法， 各种查找算法的效率衡量。各种查找算法的效率衡量。何谓查找表何谓查找表 ？ 查找表是由同一类型同一类型的数据元素(或记录)构成的集合集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的对查找表经常进行的操作操作: :1.查询查询某个“特定的”数据元素是否在查

3、找表中；2.检索检索某个“特定的”数据元素的各种属性；3.在查找表中插入插入一个数据元素；4.从查找表中删去删去某个数据元素。仅作查询查询和检索检索操作的查找表。静态查找表静态查找表 有时在查询之后，还需要将“查询”结果为“不在查找表中不在查找表中”的数据元素插插入到入到查找表中；或者，从查找表中删除删除其“查询”结果为“在查找表中在查找表中”的数据元素。动态查找表动态查找表查找表可分为两类查找表可分为两类: :关键字：关键字：是数据元素（或记录）中某个数据项数据项的值，用以标识标识（识别）一个数据元素（或记录）。 若此关键字可以识别唯一的唯一的一个记录，则称之谓“主关键字主关键字”。 若此关

4、键字能识别若干若干记录，则称之谓“次关键字次关键字”。查找：查找：根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元确定一个其关键字等于给定值的数据元素或（记录）。素或（记录）。 查找结果查找结果通常有两种可能：v查找成功查找成功：即找到满足条件的数据对象，这时查找的结果为给出整个记录的信息，或指示该记录在表中的位置。v查找不成功查找不成功：查找的结果可给出一个“空”记录或“空”指针。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表

5、示用另外一种结构来表示查找表查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。关键字和数据元素类型说明：关键字和数据元素类型说明：/关键字类型定义关键字类型定义Typedef float KeyType;Typedef int KeyType;Typedef char* KeyType;Typedef struct/ 数据元素类型定义数据元素类型定义 KeyType key; /关键字域 /其他域ElemType;9.1 静态查找表静态查找表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数每个数据元素含有类型相同的据

6、元素含有类型相同的关键字关键字，可唯一标识数据元素。 数据元素同属一个集合。ADT StaticSearchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P： ADT StaticSearchTable构造一个含n个数据元素的静态查找表ST。Create(&ST, n);操作结果：操作结果：销毁表ST。Destroy(&ST);初始条件：初始条件：操作结果：操作结果：静态查找表ST存在；若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元

7、素的值或在表中的位置，否则为“空”。 Search(ST, key);初始条件：初始条件：操作结果：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。Traverse(ST, Visit();初始条件：初始条件：操作结果：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;假设静态查找表静态查找表的顺序存储

8、结构顺序存储结构为ElemType *elem;数据元素类型数据元素类型的定义为的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;前提：前提：以顺序表或线性链表顺序表或线性链表表示静态查找表。顺序查找的查找过程查找过程： 从表中最后一个最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，否则查找不成功。9.1.1 顺序表的查找顺序表的查找21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.e

9、lem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值 e=64,要求 ST.elemi = e, 问: i = ?iiint location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) i = 1; p = L.elem; while ( i=L.length & !(*compare)(*p+,e) i+; if ( i= L.length) return i; else return 0; /locationi例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21

10、 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：比较次数：查找第n个元素： 1查找第n-1个元素：2.查找第1个元素： n查找第i个元素： n-i+1查找失败： n+1int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0

11、 / Search_Seq 定义：定义：查找算法的平均查找长度平均查找长度ASL 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值进行比较的关键字个数的期望值。 其中: n 为表长，Pi 为查找表中第i个记录的概率，且 ， Ci为找到该记录时，曾和给定值比较过的关键字的个数。顺序查找的时间性能分析：顺序查找的时间性能分析：niiiCPASL111niiP在等概率查找的情况下， 顺序表查找的平均查找长度为：对顺序表顺序表而言，在查找成功查找成功时 Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 +2Pn-1+Pn查找查找不

12、成功不成功时：时：ASLn+1) 1(43) 1(21) 1(211nninnASLssni时间复杂度时间复杂度 O（n） v在不等概率查找不等概率查找的情况下，ASLss 在 PnPn-1 . P2 P1时取极小值。v若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。顺序查找改进顺序查找改进: 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。9.1.2 有序查找表有序查找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。查找过程：查找过程：先确定待查记录所在的范围，然后逐步缩小范

13、围直到找到或找不到该记录为止。适用条件适用条件：采用顺序存储顺序存储结构的有序表。05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid = (low+high)/2int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low 50时

14、，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs9.1.4 索引顺序表查找（分块查找）索引顺序表查找（分块查找）索引顺序表索引表+分块有序表分块有序表：分块有序表：把顺序表分成若干个子表（块），分块有序。查找过程查找过程：1）由索引确定记录所在块；2）在顺序表的块内进行查找。索引表：indexstart最大关键字域指向本块第一个结点的指针1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13

15、 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13例如：例如：查找关键字为38的记录。int Search_Blo(SSTable ST,IndexTable A, KeyType Key) for (i=1;i A.elemi.length; +i) /在索引表A中顺序查找关键字Key所对应的索引项 if (Key=A.elemi.index) break; if(i= = A.elemi.length) / 表明查找失败，返回0 return 0;for(j=ST.elemi.start; jdata.key) ) retur

16、n(T);else if ( LT (key, T-data.key) ) return(SearchBST(T-lchild,key); else return(SearchBST(T-rchild,key); 根据动态查找表的定义,“插入插入”操作在操作在查找不成功查找不成功时才进行时才进行；3. 二叉排序树的插入算法二叉排序树的插入算法 若二叉排序树为空树空树，则新插入的结点为新的根结点新的根结点；否则，新插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程得到。Status SearchBST (BiTree T, KeyType key, BiTree f, Bi

17、Tree &p ) / 在根指针在根指针 T 所指二叉排序树中递归地查找其所指二叉排序树中递归地查找其 / 关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功， / 则指针则指针 p 指向该数据元素结点，并返回函数值指向该数据元素结点，并返回函数值 /为为 TRUE; / SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初始调用值为的结点的双亲，其初

18、始调用值为NULLif (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功 p = T; return TRUE; / 查找成功SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找30201040352523f=nullT设 key = 48fTfT25pTfTTfpStatus Insert BST(BiTree &

19、amp;T, ElemType e ) / 当二叉排序树中不存在关键字等于 e.key 的 / 数据元素时，插入元素值为 e 的结点，并 /返回 TRUE; 否则，不进行插入并返FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST s = (BiTree) malloc (sizeof (BiTNode); / 为新结点分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 为新的根结点else if ( LT(e.ke

20、y, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子else p-rchild = s; / 插入 *s 为 *p 的右孩子return TRUE; / 插入成功例例:设查找的关键字序列 45,24,53,45,12,24,90， 构造其二叉排序树。2445Tp53Tp12TTTTp90中序遍历：12，24，45，53，90（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除在查找成功查找成功之后进行，并且要求在删

21、除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性然保持二叉排序树的特性。50308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 408050308020908540358832（3）被删除的结点既有左子树

22、，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字 = 50Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树 T 中存在其关键字等于 key 的 / 数据元素，则删除该数据元素结点，并返回 / 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; / 不存在关键字等于key的数据元素 else / DeleteBST算法描述如下：算法描述如下： if ( EQ (key, T-data.key) )

23、 / 找到关键字等于key的数据元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找void Delete ( BiTree &p ) / 从二叉排序树中删除结点 p， / 并重接它的左子树或右子树 if (!p-rchild) else if (!p-lchild) else / Delete其中删除操作删除操作过程如下所描述： / 右子树为

24、空树则只需重接它的左子树q = p; p = p-lchild; free(q);ppqq/ 左子树为空树只需重接它的右子树q = p; p = p-rchild; free(q);ppq = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱/ 左右子树均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子树free(s);sqFPCQSSLQLCLPRpfqssqFSCQSLQLCLPR

25、pfqsqFPPRSSLpfFSPRSLpfq5. 查找性能的分析查找性能的分析 在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根从根结点到该结点的路径的过程结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加路径长度加1（或结点所在层数），因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。但二叉排序树平均查找长度和树的形态有关。 122437455393452453123793关键字序列45,24,53,12,37,9312,24,37,45,53,93ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6例

26、如：例如： 下面讨论平均情况下面讨论平均情况: 不失一般性，假设长度为 n 的序列中有i 个关键字小于小于第一个关键字，则必有 n-i-1 个关键字大于大于第一个关键字,由它构造的二叉排序树：n-i-1i其平均查找长度是 n 和 i 的函数：P(n, i) ( 0 i n-1 )在等概率查找等概率查找的情况下，njjnjjjCnCpinP111),(RjLjrootCCCn1) 1) 1()(1() 1)(11inPiniPin 假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度：10),(1)(niinPnnPASL10) 1() 1()(1

27、11niinPiniPinn112)(21niiPin可类似于解差分方程，此递归方程有解：CnnnnPlog12)(最坏情况：最坏情况：单支树，平均查找长度为 （和顺序查找相同）。最好情况：最好情况：二叉排序树的形态和折半查找的判定树相同，平均查找长度和log2n成正比。平均情况：平均情况：在随机的情况下，平均查找长度和logn是等量级的。21n二、平衡二叉树二、平衡二叉树3.平衡二叉树的查找性能分析平衡二叉树的查找性能分析2. 如何构造如何构造“平衡二叉树平衡二叉树”1. 何谓何谓“平衡二叉树平衡二叉树”？ 平衡二叉树平衡二叉树（又称（又称AVL树）树）是二叉排序树的另一种形式，其特点特点为

28、： 树中每个结点的左、右子树深度树中每个结点的左、右子树深度之差的绝对值不大于之差的绝对值不大于1 。1RLhh1. 何谓何谓“平衡二叉树平衡二叉树”？ 结点的结点的平衡因子平衡因子BF：该结点左子树深度和右子树深度之差。例如例如:是平衡树是平衡树不是平衡树不是平衡树548254821构造平衡二叉树的方法是：在插入过程中，采用在插入过程中，采用平衡旋转技术平衡旋转技术。例如例如:依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转2. 如何构造如何构造“平衡二叉树平衡二叉树”426589642895向左旋转一次继续插入关键字 9 一般情况

29、下，假设由于在二叉排序树上插入结点而失去平衡的最小子树失去平衡的最小子树根结点的指针为a，则失去平衡后进行调整的规律可归纳为以下四种情况：（1）单向右旋平衡处理：单向右旋平衡处理：1A0 B AR BL BR C 0B0ABRARBLC（2）单向左旋平衡处理：单向左旋平衡处理：在a的右子树根结点的右子树插入结点而失去平衡。-1AAL 0 B BL BR C 0B0ABLBRALC（3）双向旋转（先左后右）平衡处理双向旋转（先左后右）平衡处理:在*a的左子树根结点的右子树插入结点而失去平衡。1A0B AR 0C CL BL CR D 0C0B -1A CL BL CR D AR 0C1A（4）双

30、向旋转（先右后左）平衡处理双向旋转（先右后左）平衡处理：在*a的右子树根结点的左子树插入结点而失去平衡。 D 0C0A -1B CL AL CR D BR -1A0B AL 0C CL BR CR 0C-1A 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。 问：含 n 个关键字的平衡二叉树可能达到的最大深度最大深度是多少？3.平衡二叉树的查找性能分析平衡二叉树的查找性能分析n = 0空树空树最大深度为最大深度为 0n = 1最大深度为最大深度为 1n = 2最大深度为最大深度为 2n = 4最大深度为最大深度

31、为 3n = 7最大深度为最大深度为 4先看几个具体情况:反过来问，深度为深度为 h 的平衡平衡二叉树树中所含结点的最小值含结点的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情况下一般情况下N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用归纳法可证得利用归纳法可证得Nh = Fh+2 1斐波那契序列 因此，在平衡二叉树平衡二叉树上进行查找时，查找过程中和给定值进行比较的关键字进行比较的关键字的个数和的个数和 logn 相当。 由此推得，深度为深度为 h 的平衡二叉树平衡二叉树中所含结点的最小值含结点的最小值 Nh = h+2/5

32、 - 1。 反之，含有含有 n 个结点的平衡二叉树能个结点的平衡二叉树能达到的最大深度达到的最大深度 hn = log ( 5 (n+1) - 2。 三、三、B - 树和树和B树树（1）定义）定义（2）查找过程）查找过程（3）插入操作）插入操作 （4）删除操作）删除操作（5）查找性能的分析）查找性能的分析1. B - 树树2. B + 树树（1）B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字关键字 Ki（1 in） n

33、m n 个指向记录的指针指向记录的指针 Di（1in） n+1 个指向子树的指针指向子树的指针 Ai（0in）多叉树的特性typedef struct BTNode int keynum; / 结点中关键字个数，结点大小 struct BTNode *parent; / 指向双亲结点的指针 KeyType keym+1; / 关键字（0号单元不用） struct BTNode *ptrm+1; / 子树指针向量 Record *recptrm+1; / 记录指针向量 BTNode, *BTree; / B树结点和B树的类型B-树结构的树结构的C语言描述如下语言描述如下: : 非叶结点中的多个关

34、键字多个关键字均自小至大自小至大有序排列，即：K1 K2 keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的双亲 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功 在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：（3）插入）插入1）插入后，该结点的关

35、键字个数nm， 不修改指针; 例如2）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = m/2， 在原结点中保留 （A0，K1， ， Ks-1，As-1）； 建新结点 （As，Ks+1， ，Kn，An）； 将（Ks，p）插入双亲结点；例如3）若双亲为空，则建新的根结点。 例如例如:下列为 3 阶B-树50 20 40 80 插入关键字 = 60, 60 80 90, 60 80 90 90 50 80 60 30, 40 20 30 50 808030 50 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要

36、从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。（4）删除）删除 在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度树的深度。（5）查找性能的分析）查找性能的分析问：含 N 个关键字的 m 阶 B-树可能达到的最大深度 H 为多少？第第 2 层层 2 个个先推导每一层所含最少结点数：第第 1 层层 1 个个第第 H+1 层层 2 ( m/2 ) H-1 个个第第 4 层层 2 ( m/2 )2 个个第第 3 层层 2m/2 个个反过来问： 深度为H的B-树中， 至少含有多少个结

37、点？ 假设 m 阶 B-树的深度为 H+1，由于第 H+1 层为叶子叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个， N+12( m/2 )H-1 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1由此可推得下列结果： 在含在含 N 个关键字的个关键字的 B-树上树上进行一次查找，需访问的结点进行一次查找，需访问的结点个数不超过个数不超过 log m/2 (N+1)/2)+1结论：结论：（1）B+树的结构特点：树的结构特点： 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子叶子结点彼此相链接链接构成一个有序链表，其头指针指

38、向含最小关键字的结点；2. B+树：树：是是B-树的一种变型树的一种变型 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。（2）查找过程）查找过程 在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； 若在结点内查找时，给定值Ki， 则 应继续在 Ai 所指子树中进行查找。（3）插入和删除的操作）插入和删除的操作 类似于类似于B-树进行，即必要树进行，即必要时，也需要进行结点的时，也需要进行结点的“

39、分裂分裂”或或“归并归并”。 50 96 15 5062 78 96 71 788 4 8 9 96 56 6220 26 43 50 3 8 15sqroot9.3 哈希哈希(Hash)表表9.3.4 以上两节讨论的表示查找表的各种结结构构的共同特点特点：记录在表中的位置位置和它的关键字关键字之间不存在不存在一个确定的关系，查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较，查找的效率查找的效率取取决于和给定值进行比较的关键字个数。决于和给定值进行比较的关键字个数。 用这类方法表示的查找表，其平均查找长度都不为零。 不同的表示方法，其差别仅在于：差别仅在于：关键

40、字和给定值进行比较的顺序不同。 要想ASL0，只有一个办法：预先知道所查关键字在表中的位置。即要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为以下标为000 999 的顺序表的顺序表表示之。例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。但是，对于动态查找表动态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表

41、中的位置，通常称这个函数 f(key) 为哈希函数哈希函数。1) 表长不确定；2) 在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dai 例如：对于如下 9 个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 ChenZhaoQianSunLiWuHanYeDai问题问题: 若添加关键字 Zhou , 怎么办？怎么办？能否找到能否找到另一个哈希函数？1) 哈希函数是一个映

42、象映象，即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活灵活，只要这个地址集地址集合的 大小不超出允许范围不超出允许范围即可；从这个例子可见：从这个例子可见：2) 由于哈希函数是一个压缩映象压缩映象，因此，在一般情况下，很容易产生“冲突冲突”现象，即： key1 key2，而 f(key1) = f(key2)。Key1和 key2互称为同义词同义词。3) 很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；

43、还需要找到一种“处理冲突” 的方法。哈希表的定义： 根据设定的哈希函数哈希函数 H(key) 和所选中的处理冲突的方法处理冲突的方法，将一组关键字映象映象到到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置存储位置，如此构造所得的查找表称之为“哈希表哈希表”。 对数字数字的关键字可有下列构造方法： 若是非数字关键字非数字关键字，则需先需先对其进行进行数字化处理数字化处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法1. 直接定址法直接定址法v构

44、造：构造：取关键字关键字或关键字的某个线线性函数性函数作哈希地址，即 H(key)=key 或 H(key)=akey+bv特点：l地址集合与关键字集合大小相等，不会发生冲突。l实际中能用这种哈希函数的情况很少。v构造：构造：对关键字进行分析，取关键字的若干位若干位或其组合其组合作哈希地址。v适于关键字位数比哈希地址位数大，且能预先估计出预先估计出全体关键字的每一位每一位上上各种数字出现的频度数字出现的频度。2. 数字分析法数字分析法8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3

45、 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.例：例：有80个记录，关键字为8位十进制数，哈希地址为2位十进制数。分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址.v构造：构造：取关键字平方后中间几位平方后中间几位作哈希地址。v此方法适合于此方法适合于: 不知道全部关键字情况,并且关键字中的每一位都有某些数字重复出现频度很高的现象。3. 平方取中法平方取中法4. 折叠法折叠法v构造：构造：将关键字分割成位数相同的分割成位数相同的几部分几部分，然后取这几部分的叠加和叠加和（舍去进位）做哈希地址

46、。v种类：种类：l移位叠加：移位叠加：将分割后的几部分低位对齐相加。l间界叠加间界叠加：从一端沿分割界来回折叠，然后对齐相加。例例 关键字为 ：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加v此方法适合于此方法适合于:关键字位数很多，且每一位上数字分布大致均匀情况。v构造：构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即 H(key)=key MOD p，pmvp 应为不大于 m 的质数或是不含 20 以下的质因子。5.

47、 除留余数法除留余数法例如：例如：给定一组关键字为:12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3为什么要对为什么要对 p 加限制？加限制？ 可见，若 p 中含质因子 3， 则所有含质则所有含质因子因子 3 的关键字均映射到的关键字均映射到“3 的倍数的倍数”的的地址上地址上，从而增加了“冲突”的可能。6. 随机数法随机数法v构造：构造：取关键字的随机函数值作哈希地址，即 H(key) = random(key)v适于关键字长度不等的情况。 实际造表时，选取哈希函数，考虑以下因素因素： （1）计算哈希函数所需时间；

48、（2）关键字长度； （3）哈希表长度（哈希地址范围）； （4）关键字分布情况； （5）记录的查找频率。 总的的原则原则是使产生冲突的可能性降到是使产生冲突的可能性降到尽可能地小。尽可能地小。 “处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址。一、一、 开放定址法开放定址法三、三、 链地址法链地址法二、二、 再哈希法再哈希法一、一、 开放定址法开放定址法为产生冲突的地址 H(key) 求得一个地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, ,

49、s对增量 di 有三种取法：（1）线性探测再散列：线性探测再散列： di = 1,2,3,m-1（2） 平方探测再散列：平方探测再散列： di=1,-1,2,-2,3,k (k m/2)（3） 随机探测再散列随机探测再散列 di 是一组伪随机数列 或者 di = iH2(key) (又称双散列函数探测)即：产生的 Hi 均不相同，且所产生的 s(m-1)个个 Hi 值能覆盖覆盖哈希表中所有 地址。则要求： 注意：注意：增量增量 di 应具有应具有“完备性完备性” 随机探测时的 m 和 di 没有公因子。 二次探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, 等）

50、；例例：表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中。 0 1 2 3 4 5 6 7 8 9 10 60 17 29(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5-1) MOD 11=4 不冲突38(3) H(38)=38 MOD 11=5 冲

51、突 设伪随机数序列为9，则：H1=(5+9) MOD 11=3 不冲突38例例:已知一组关键(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长m=16.(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16

52、=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2

53、)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12 构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即： Hi = RHi(key) i=1,2,k 其中：RHi为不同的哈希函数。特点：特点：不易产生“聚集”，但计算时间增加。二、二、 再哈希法再哈希法 将所有关键字为同义词的记录存储在一个单链表单链表中，并用一维数组存放头指针头指针。 三、三、 链地址法链地址法例例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(

54、key)=key MOD 13, 用链地址法处理冲突。0 1 2 3 4 5 6 7 8 9 10 11 12 11427795568198420102311ASL=(1*6+2*4+3+4)/12=1.75 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为： 对于给定值 K， 计算哈希地址 p = H(K)若若 elemp = NULL 则查找不成功若若 elemp.key = K 则查找成功否则否则 “求下一地址 p” ，直至 elemp = NULL (查找不成功) 或 elemp.key = K (查找成功) 为止。9.3.4 int hashsize = 997, . ; typedef struct ElemType *elem; int count; / 当前数据元素个数 int sizeindex; / hashsizesizeindex为当前容量 HashTable;/- 开放定址哈希表开放定址哈