《数据结构第9章课件》由会员分享，可在线阅读，更多相关《数据结构第9章课件（68页珍藏版）》请在金锄头文库上搜索。
1、 基本概念基本概念 顺序查找顺序查找 二分查找二分查找 分块索引查找分块索引查找 二叉排序树的查找二叉排序树的查找 B树与树与B+树的查找树的查找 Hash(散列散列)查找查找9.1 基本概念基本概念查找表查找表: :由具有同一类型的数据元素（或由具有同一类型的数据元素（或记录）组成的集合称为查找表。记录）组成的集合称为查找表。 关键字关键字: : 关键字是记录中某个项或组合项关键字是记录中某个项或组合项的值，用它可以标识一个记录。能唯一确的值，用它可以标识一个记录。能唯一确定一个记录的关键字，称定一个记录的关键字，称为主关键字为主关键字；而；而不能唯一确定一个记录的关键字，称为不能唯一确定一
2、个记录的关键字，称为次次关键字关键字. .查找查找是指按给定的某个值是指按给定的某个值k k，在查找表中，在查找表中查找关键字为给定值查找关键字为给定值k k的记录。的记录。查找是计算机中经常遇到的操作。特别是查找是计算机中经常遇到的操作。特别是当问题所涉及到的数据量相当大时，当问题所涉及到的数据量相当大时，查找查找的效率的效率就显得格外重要。就显得格外重要。 查找运算的主要操作是关键字的比较，所以，通查找运算的主要操作是关键字的比较，所以，通查找运算的主要操作是关键字的比较，所以，通查找运算的主要操作是关键字的比较，所以，通常把查找过程中对关键字需要执行的平均比较次常把查找过程中对关键字需要
3、执行的平均比较次常把查找过程中对关键字需要执行的平均比较次常把查找过程中对关键字需要执行的平均比较次数（也称为数（也称为数（也称为数（也称为平均查找长度平均查找长度平均查找长度平均查找长度）作为衡量一个查找算）作为衡量一个查找算）作为衡量一个查找算）作为衡量一个查找算法效率优劣的标准。法效率优劣的标准。法效率优劣的标准。法效率优劣的标准。* 查找结果：查找结果： 成功、失败成功、失败* 查找算法的性能指标查找算法的性能指标 时间复杂性时间复杂性 平均查找长度平均查找长度: : 平均比较次数平均比较次数平均查找长度定义为：平均查找长度定义为：其中，其中，n是元素的个数；是元素的个数；pi 是查找
4、第是查找第i个元个元素的概率，素的概率，p1=p2=.=pn=1/n；ci 是是找到第找到第i个元素所需要的比较次数个元素所需要的比较次数* *常用的查找算法常用的查找算法顺序查找顺序查找 二分查找二分查找(折半查找折半查找) 分块索引查找分块索引查找 二叉排序树的查找二叉排序树的查找 B树与树与B+树的查找树的查找 Hash(散列散列)查找查找9.2 顺序查找顺序查找struct Record int key; ;Record rn;无监视哨的顺序查找无监视哨的顺序查找: int SeqSearch(Record r, int n, int k) int i=0;while (in&ri.k
5、ey!=k) i+;if (in) return i;else return -1;有监视哨的顺序查找有监视哨的顺序查找int SeqSearch2(Record r, int n, int k)int i=0;rn.key=k;while (ri.key!=k) i+;if (iK，则，则说明待查找的结点只可能在左说明待查找的结点只可能在左 子表子表R0到到Rmid-1中，只需在左子表中继续查中，只需在左子表中继续查 找找；否否则则在在右右子子表表Rmid+1到到Rn-1中中继继续续查查找找。这这样样，经经过过一一次次关关键键字字的的比比较较就就缩缩小小了了一一半半的的查查找找区区间间。如如
6、此此进进行行下下去去，直直到到找找到到为为止止（当当然然也也存存在在最后找不到的可能）。最后找不到的可能）。例例:05 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=21K=21的过程（查找成功）的过程（查找成功）05 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=85K=85的过程（查找失败）
7、的过程（查找失败）05 13 19 21 37 56 64 75 80 88 92 二分查找算法二分查找算法(非递归非递归)int BiSearch(Record r , int n, int k)low=0,high=n-1;while (low=high)mid=(low+high)/2;if (rmid.key=k) return mid;else if (rmid.keyhigh)return -1;elsemid=(low+high)/2;if (rmid.key=k) return mid;else if (rmid.keyk) return BiSearch2(r,mid+1,h
8、igh,k);else return BiSearch2(r,low,mid-1,k);算法分析算法分析 如果把当前查找位置上的结点作为根，左子表和如果把当前查找位置上的结点作为根，左子表和右子表的结点分别作为根的左子树和右子树，由此得右子表的结点分别作为根的左子树和右子树，由此得到的二叉树称为描述二分查找的判定树。到的二叉树称为描述二分查找的判定树。 借助于判定树很容易求得二分查找的平均查找长借助于判定树很容易求得二分查找的平均查找长度。查找数据的比较次数最多为该判定树的树高度。查找数据的比较次数最多为该判定树的树高. 二分查找的算法复杂度为：二分查找的算法复杂度为：O(log n)即在最坏
9、情况下，二分查找方法查找成功的比较即在最坏情况下，二分查找方法查找成功的比较次数不超过判定树的高度。次数不超过判定树的高度。 虽然二分查找的效率较高，但它要求被查找虽然二分查找的效率较高，但它要求被查找序列序列事先按关键字排好序事先按关键字排好序，而排序本身是一种很，而排序本身是一种很费时的运算；另外，二分查找只适用于顺序存储费时的运算；另外，二分查找只适用于顺序存储结构，因此，二分查找特别适用于那种一经建立结构，因此，二分查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。就很少改动、而又需要经常查找的线性表。平均长度的计算平均长度的计算平均长度的计算平均长度的计算例如例如例如例
10、如: : 长度为长度为长度为长度为13131313的有序表进行折半查找的平均查找长度的有序表进行折半查找的平均查找长度的有序表进行折半查找的平均查找长度的有序表进行折半查找的平均查找长度ASL=(11+22+34+46)/13=41/13ASL=(11+22+34+46)/13=41/13ASL=(11+22+34+46)/13=41/13ASL=(11+22+34+46)/13=41/13。9.4 分块查找分块查找 分块查找又称为索引查找，它是一种性能介于顺分块查找又称为索引查找，它是一种性能介于顺 序查找和二分查找之间的查找算法。序查找和二分查找之间的查找算法。 分块查找要求将被查找表分成
11、块，建立块索引。分块查找要求将被查找表分成块，建立块索引。 每一块中的关键字不一定有序，但前一块中的最每一块中的关键字不一定有序，但前一块中的最 大关键字必须小于后一块中的最小关键字，即要大关键字必须小于后一块中的最小关键字，即要 “分块有序分块有序”。 抽取各块中的最大关键字及其起始位置构成一个抽取各块中的最大关键字及其起始位置构成一个 索引表。由于被查找表是分块有序的，所以索引索引表。由于被查找表是分块有序的，所以索引表是一个递增有序表。表是一个递增有序表。例如：例如：133920334244386080744986532212061222488624480 1 2 3 4 5 6 7 8
12、 9 10 11 12 13 14 15 16 17 分块查找的基本思想：首先，查找索引表，因分块查找的基本思想：首先，查找索引表，因为索引表是有序表，故可采用二分查找，也可以采为索引表是有序表，故可采用二分查找，也可以采用顺序查找，以确定待查的结点在哪一块；然后在用顺序查找，以确定待查的结点在哪一块；然后在以确定的那一块中顺序查找。以确定的那一块中顺序查找。算法分析算法分析 由于分块查找实际上是两次查找过程，故整个算由于分块查找实际上是两次查找过程，故整个算法的平均查找长度应该是两次查找的平均查找长度之法的平均查找长度应该是两次查找的平均查找长度之和。若以二分查找来确定块，则分块查找的平均查
13、找和。若以二分查找来确定块，则分块查找的平均查找长度约为：长度约为：若以顺序查找来确定块，则分块查找的平均查找长度若以顺序查找来确定块，则分块查找的平均查找长度约为：约为：对于后一种情况，当对于后一种情况，当 时，平均查找长时，平均查找长度为极小值。在实用中，可根据表的具体情况进行分度为极小值。在实用中，可根据表的具体情况进行分块。块。 分块查找的性能介于顺序查找和二分查找之分块查找的性能介于顺序查找和二分查找之间的，例如，对长度为间的，例如，对长度为10000的线性表，它们的平的线性表，它们的平均查找长度分别是：均查找长度分别是：顺序查找：约顺序查找：约5000分块查找：约分块查找：约100
14、二分查找：约二分查找：约149.5 二叉排序树的查找二叉排序树的查找1.二叉排序树的概念二叉排序树的概念2.二叉排序树的建立二叉排序树的建立3.二叉排序树的插入二叉排序树的插入4.二叉排序树的删除二叉排序树的删除5.二叉排序树的查找二叉排序树的查找6.查找性能分析查找性能分析1. 二叉排序树的概念二叉排序树的概念 也称为二叉查找树也称为二叉查找树.(1)左子树的所有结点的值左子树的所有结点的值根结点的值根结点的值(3)左子树、右子树都是二叉排序树。左子树、右子树都是二叉排序树。举例：举例：性质：性质：中序遍历二叉排序树得到的是有序序列。中序遍历二叉排序树得到的是有序序列。class BiSor
15、tTreeBiNode *root;void Insert(BiNode *&ptr, int k); /供插入函数调用供插入函数调用BiNode* Search(BiNode *ptr, int k); /供查找函数调用供查找函数调用void Delete (BiNode *&ptr, int k); /供删除函数调用供删除函数调用 void Free(BiNode *ptr); /供析构函数调用供析构函数调用public:BiSortTree(int a , int n); /建立二叉排序树建立二叉排序树BiSortTree(); /析构函数析构函数void Insert(int k);
16、/插入插入bool Search(int k); /查找查找void Delete (int k); /删除删除;2 2二叉排序树的插入和建立二叉排序树的插入和建立在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为k的结点，步骤如的结点，步骤如下：下： 若二叉排序树为空，则生成值为若二叉排序树为空，则生成值为k的新结点的新结点s，同时将新结点，同时将新结点s作为根结点插入。作为根结点插入。 若若k小于根结点的值，则在根的左子树中插入小于根结点的值，则在根的左子树中插入值为值为k的结点。的结点。 若若k大于根结点的值，则在根的右子树中插入大于根结点的值，则在根的右子树中插入值为值为k的结点。的
17、结点。 若若k等于根结点的值，表明二叉排序树中已有等于根结点的值，表明二叉排序树中已有此关键字，则无须插入。此关键字，则无须插入。 void BiSortTree:Insert(BiNode *&ptr, int k) /在以在以ptr为根的二叉排序树中插入值为为根的二叉排序树中插入值为k的结点的结点if (ptr=NULL) ptr=new BiNode;ptr-key=k;ptr-lchild=ptr-rchild=NULL;elseif (kkey) Insert(ptr-lchild, k);else if(kptr-key) Insert(ptr-rchild, k); void B
18、iSortTree:Insert(int k) Insert(root,k); 二叉排序树的建立算法二叉排序树的建立算法 BiSortTree:BiSortTree(int a , int n) root = NULL; for (int i = 0; i key=k) return ptr; else if (kkey)return Search (ptr-lchild, k); elsereturn Search(ptr-rchild, k); bool BiSortTree:Search(int k) /查找查找 return Search(root, k)!=NULL; 非递归算法非递
19、归算法: 循环实现循环实现BiNode* BiSortTree:Search2(BiNode *ptr, int k) /在以在以ptr为根的二叉排序树中查找值为为根的二叉排序树中查找值为k的结点的结点 while (ptr) if (k=ptr-key) return ptr; else if (kkey) ptr=ptr-lchild; else ptr=ptr-rchild;return NULL;bool BiSortTree:Search2(int k) /查找查找 return Search2(root,k)!=NULL; 4 4二叉排序树的删除操作二叉排序树的删除操作分三种情况分
20、三种情况 :（1）删除叶子结点）删除叶子结点（2）删除单支结点）删除单支结点（3）删除双支结点）删除双支结点递归删除算法的步骤如下：递归删除算法的步骤如下： 若二叉排序树为空，则表明不存在删若二叉排序树为空，则表明不存在删除的结点，不进行删除操作。除的结点，不进行删除操作。 若给定值若给定值k小于根结点的值，则继续在小于根结点的值，则继续在根的左子树中删除。根的左子树中删除。 若给定值若给定值k大于根结点的值，则继续在大于根结点的值，则继续在根的右子树中删除。根的右子树中删除。 若给定值若给定值k等于根结点的值，则根结点等于根结点的值，则根结点即为要删除的结点，此时需要根据上述即为要删除的结点
21、，此时需要根据上述分析的三种结点情况：叶子结点、单支分析的三种结点情况：叶子结点、单支结点或双支结点，执行相应的删除操作。结点或双支结点，执行相应的删除操作。void BiSortTree:Delete(BiNode *&ptr, int k)/在以在以ptr为根的二叉排序树中删除值为为根的二叉排序树中删除值为k的结的结点点if (ptr!=NULL)if (kkey) Delete(ptr-lchild,k); /在左子树进行删除在左子树进行删除else if (kptr-key) Delete(ptr-rchild,k); /在右子树进行删除在右子树进行删除 else /ptr指向的结点就
22、是要删除的结点指向的结点就是要删除的结点 if (ptr-lchild!=NULL&ptr-rchild!=NULL) /双支结点双支结点 temp=ptr-lchild;while (temp-rchild!=NULL) temp=temp-rchild; /寻找左子树中具有最大值的结点寻找左子树中具有最大值的结点 ptr-key=temp-key; Delete(ptr-lchild, temp-key); else temp=ptr; if (ptr-lchild=NULL) /单支结点，左子树为空单支结点，左子树为空 ptr=ptr-rchild;else if (ptr-rchild
23、=NULL) /单支结点，右子树为空单支结点，右子树为空 ptr=ptr-lchild; delete temp; /删除删除 void BiSortTree:Delete(int k) /删除删除Delete(root,k);9.6 9.6 平衡二叉树平衡二叉树问题的提出问题的提出什么是平衡二叉树什么是平衡二叉树平衡二叉树的建立平衡二叉树的建立平衡二叉树平衡二叉树或者是一棵空树，或者是具或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过右子树高度之差的绝对
24、值不超过1. 1. 左子树与右子树高度之差称为结点的左子树与右子树高度之差称为结点的平平衡因子衡因子。由平衡二叉树定义可知，平衡二叉由平衡二叉树定义可知，平衡二叉树所有结点的平衡因子只能取树所有结点的平衡因子只能取 1 1，0 0，1 1三个三个值之一值之一。如何使建立的一棵二叉排序树是平衡的呢如何使建立的一棵二叉排序树是平衡的呢？这就要求当新结点插入二叉排序树时，必这就要求当新结点插入二叉排序树时，必须保持所有结点的平衡因子满足平衡二叉须保持所有结点的平衡因子满足平衡二叉树的要求，一旦不满足要求，就必须进行树的要求，一旦不满足要求，就必须进行调整调整。调整有调整有4 4种情况种情况（1）LL
25、型（2）RR型（3）LR型（4）RL型9.7 B9.7 B树与树与B+B+树树什么是什么是B B树树? ? B B树的查找树的查找什么是什么是B+B+树树? ? B+B+树的查找树的查找9.8 Hash查找查找1. 基本概念基本概念 Hash, 哈希哈希,也称为也称为散列散列. Hash是一种重要的存储方法，也是一种常见是一种重要的存储方法，也是一种常见的查找方法。的查找方法。 它的基本思想是：以数据元素的关键字它的基本思想是：以数据元素的关键字K为自为自变量，通过一个确定的函数关系，计算出对应的变量，通过一个确定的函数关系，计算出对应的函数值函数值f(K)，把这个值作为数据元素的存储地址。把
26、这个值作为数据元素的存储地址。查找时也是根据这个函数计算其存储位置。查找时也是根据这个函数计算其存储位置。 【例例】 假设一组记录的关键字分别为假设一组记录的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关。选取关键字与记录位置间的函数为键字与记录位置间的函数为f(key)=key %11。Hash函数函数-关键字与记录位置间的函数关键字与记录位置间的函数.Hash地址地址-据据HashHash函数计算出的存储位置函数计算出的存储位置. .Hash表表-存储记录的查找表存储记录的查找表, ,该表中根据该表中根据HashHash函数计算出的存储位置函数计算出的存储
27、位置. .基于基于Hash表的查找称为表的查找称为Hash查找。查找。在建立在建立Hash表时，若表时，若Hash函数是一个一对一的函数，函数是一个一对一的函数， 则在查找时，只需根据散列函数对给定值进行某种运则在查找时，只需根据散列函数对给定值进行某种运 算，即可得到待查数据的存储位置。算，即可得到待查数据的存储位置。在一般情况下，在一般情况下， Hash表的空间必须比数据的集合大，表的空间必须比数据的集合大， 此时虽然浪费了一定的空间，但换取的是查找效率。此时虽然浪费了一定的空间，但换取的是查找效率。 设散列表的空间大小为设散列表的空间大小为m，填入表中的数据个数为填入表中的数据个数为n，
28、则称则称=n/m为散列表的为散列表的装填因子装填因子。Hash函数的选取原则是：运算尽可能简单；函数的值函数的选取原则是：运算尽可能简单；函数的值 域必须在表长的范围内；尽可能使得关键字不同时，域必须在表长的范围内；尽可能使得关键字不同时， 其散列函数值亦不相同。其散列函数值亦不相同。若某个若某个Hash函数对于不相等的关键字计算出了相同的函数对于不相等的关键字计算出了相同的 Hash地址，则称该现象为地址，则称该现象为hash冲突冲突，发生冲突的两个，发生冲突的两个关键字该关键字该Hash函数的函数的同义词同义词。在实际应用中，不产生冲。在实际应用中，不产生冲突的突的Hash函数极少存在。函
29、数极少存在。2. Hash函数的构造方法函数的构造方法直接定址法直接定址法除留余数法除留余数法数字分析法数字分析法平方取中法平方取中法折叠法折叠法直接定址法直接定址法 HashHash函数是关键字的线性函数。即：函数是关键字的线性函数。即： H(key) = H(key) = a akeykeyb例例1：已知一个含有：已知一个含有70个数据的线性表，其关个数据的线性表，其关键字是两位十进制数字组成，则可将线性表存键字是两位十进制数字组成，则可将线性表存储在如下说明的散列表中：储在如下说明的散列表中： int HT100;其中，其中，HTi存放关键字为存放关键字为i的结点，即散列函的结点，即散列
30、函数为：数为： H(key)=key除留余数法除留余数法 选择一个适当的正整数选择一个适当的正整数P，用，用P去除关键字，取去除关键字，取所得得余数作为散列地址，即：所得得余数作为散列地址，即： H(key) = key%P这个方法的关键是选取适当的这个方法的关键是选取适当的P。选择选择P最好不要是最好不要是偶数，也不要是基数的幂。一般地选偶数，也不要是基数的幂。一般地选P为小于或等于为小于或等于散列表长度散列表长度m的某个最大的某个最大质数质数比较好。例如：比较好。例如： m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1
31、019除余法的地址计算公式简单，而且在很多情况下效果除余法的地址计算公式简单，而且在很多情况下效果较好，因此是一种常用的构造散列函数的方法。较好，因此是一种常用的构造散列函数的方法。数字分析法数字分析法 若事先知道关键字集合，且关键字的位数比散列表若事先知道关键字集合，且关键字的位数比散列表的地址位数多，则可选取数字分布比较均匀的若干位作的地址位数多，则可选取数字分布比较均匀的若干位作为散列地址。例如，有一组为散列地址。例如，有一组8位数字组成的关键字：位数字组成的关键字： 经过分析可知，前三位和第五位分布不均匀，所以，经过分析可知，前三位和第五位分布不均匀，所以，若表长为若表长为1000，则
32、可取，则可取4、6、7位的数字作为散列地址，位的数字作为散列地址，若表长为若表长为100，则可取，则可取4、6与与7、8位之和并舍去进位作为位之和并舍去进位作为散列地址。散列地址。关键字关键字散列地址散列地址1散列地址散列地址287142653 87172232 8718274587107136 87127281 87137394465723874013228339990432370327平方取中法平方取中法 通常，要预先估计关键字的数字分布并不容易，通常，要预先估计关键字的数字分布并不容易，要找数字均匀分布的位数更难。此时可采用平方取中要找数字均匀分布的位数更难。此时可采用平方取中法：即先通
33、过求关键字的平方来扩大差别，再取其中法：即先通过求关键字的平方来扩大差别，再取其中的几位或其组合作为散列地址。的几位或其组合作为散列地址。 例如：一组关键字：例如：一组关键字： (0100，0110，1010，1001，0111)平方结果为：平方结果为：(0010000，0012100，1020100，1002001，0012321)若表长为若表长为3位，则可取中间三位作为散列地址集：位，则可取中间三位作为散列地址集： (100，121，201，020，123)折叠法折叠法 若关键字位数较多，可将关键字分割成位数相同若关键字位数较多，可将关键字分割成位数相同的几段（最后一段的位数可以不同），段
34、的长度取决的几段（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然后将各段的迭加和（舍去进于散列表的地址位数，然后将各段的迭加和（舍去进位）作为散列地址。位）作为散列地址。 例如，对于例如，对于key=58242324169 582 423 241 + 69 1315H(key)=315移移位位迭迭加加 582 324 241 + 96 1243H(key)=243边边界界迭迭加加3. 处理处理hash冲突的方法冲突的方法(1)(1)开放地址法开放地址法 线性探察法线性探察法 二次探察法二次探察法 双散列函数法双散列函数法(2)(2)链地址法链地址法 用开放地址法解决冲突的基本思想
35、是：用开放地址法解决冲突的基本思想是：当冲突发生时，使用某种方法在散列表中当冲突发生时，使用某种方法在散列表中形成一个探查序列，按此序列逐个单元的形成一个探查序列，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。插入一个开放的地址（单元为空）为止。插入时碰到开放的地址，即可将待插入新结点时碰到开放的地址，即可将待插入新结点放到该地址单元中；查找时碰到开放的地放到该地址单元中；查找时碰到开放的地址，则说明表中没有待查的关键字。址，则说明表中没有待查的关键字。 形成探测的方法不同，所得到的解决形成探测的方法不同，所得到的解决
36、冲突的方法也不同。冲突的方法也不同。线性探测法线性探测法 将散列表看成是一个环形表。若地址为将散列表看成是一个环形表。若地址为d（即（即H(key)=d）的单元发生冲突，则依次探查下述地址的单元发生冲突，则依次探查下述地址单元：单元： d+1，d+2，.，m-1，0，1，.，d-1直到找到一个空单元或查找到关键字为直到找到一个空单元或查找到关键字为key的结点为的结点为止。当然，若沿着该探查序列查找一遍之后，又回到止。当然，若沿着该探查序列查找一遍之后，又回到了地址了地址d，则无论是做插入操作还是做查找操作，都则无论是做插入操作还是做查找操作，都意味着失败。意味着失败。 例例: 有关键字序列为
37、有关键字序列为36，7，40，11，16，81，22，8，14，Hash表表长为表表长为11，Hash(key)=key % 11，用线性探测法处理冲突，建立的，用线性探测法处理冲突，建立的Hash表。表。 板书板书二次探查法二次探查法 二次探查法的探查序列依次为：二次探查法的探查序列依次为：12，-12，22，-22，.，等，也就是说，发生冲突时，将同，等，也就是说，发生冲突时，将同义词来回散列在第一个地址的两端。求下一个开义词来回散列在第一个地址的两端。求下一个开放地址的公式为：放地址的公式为： d2i-1 = (d + i2)%m d2i = (d i2)%m 链地址链地址法法: 基本思
38、想是：将所有关键字为同义词的结点链接在基本思想是：将所有关键字为同义词的结点链接在同一个单链表中。例同一个单链表中。例: Hash(key)=key % 1101234567891011122641681506443638125125若一组关键字为（若一组关键字为（26，36，41，38，44，15，68，12，06，51，25），散列函数定），散列函数定义为：义为：H(key) = key%13。用用链地址链地址法建立散列表法建立散列表4. Hash4. Hash查找算法及分析查找算法及分析 以线性探测法解决冲突建立的以线性探测法解决冲突建立的Hash表的查找算法表的查找算法int Hash
39、Search_1(int hash , int m, int k) pos=k%m; /计算计算Hash地址地址t=pos; while (hashpos!=EMPTY) /当当Hash地址中的记录不为空时循环地址中的记录不为空时循环if (hashpos=k)return pos; /查找成功，返回下标查找成功，返回下标elsepos=(pos+1)%m;if (pos=t) return -1; /查找失败，返回查找失败，返回-1return -1; /查找失败，返回查找失败，返回-1 以链地址法解决冲突建立的以链地址法解决冲突建立的以链地址法解决冲突建立的以链地址法解决冲突建立的Hash
40、Hash表的查找算法表的查找算法表的查找算法表的查找算法Node *HashSearch_2(Node *hash , int m, int k) pos=k%m; /计算计算Hash地址地址 p=hashpos; /p指向对应单链表的表头指向对应单链表的表头 while (p&p-data!=k) /在对应单链表中顺序查找在对应单链表中顺序查找 p=p-next; if (p) return p; /查找成功，返回地址查找成功，返回地址 else return NULL; /查找失败，返回空指针查找失败，返回空指针本章总结本章总结各种查找算法的基本思想各种查找算法的基本思想各种查找算法性能的比较各种查找算法性能的比较查找算法的实现查找算法的实现
