预备知识81静态查找表82动态查找表83哈希表.ppt

《预备知识81静态查找表82动态查找表83哈希表.ppt》由会员分享，可在线阅读，更多相关《预备知识81静态查找表82动态查找表83哈希表.ppt（108页珍藏版）》请在三一办公上搜索。

1、1,预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表,第8章 查找,2,本章重点难点,重点：顺序查找、二分查找、二叉排序树查找以 及散列表查找的基本思想和算法实现。,难点：二叉排序树的删除算法和平衡二叉树的 构造算法。,3,预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表,第8章 查找,4,(1)查找表：,(2)静态查找表：,是由同一类型的数据元素(或记录)构成的集合。,仅作查询和检索操作的查找表。,有关概念,(3)动态查找表：,在查找时包含插入、删除或修改。,预备知识,5,(4)主关键字,(5)次关键字,可以识别唯一的一个记录的数据项（字段）。,关联若干项记录

2、的数据项（字段）。,(6)查找,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。,有关概念,预备知识,6,(7)查找成功,(8)查找不成功,查找表中存在满足条件的记录。,查找表中不存在满足条件的记录。,有关概念,预备知识,7,typedef float Keytype;/Keytype定义为浮点数据类型typedef int Keytype;/Keytype定义为整型数据类型typedef char*Keytype;/Keytype定义为字符指针数据类型,类型定义,预备知识,8,数据元素类型定义为：typedef struct Keytype key;/声明关键字

3、SElemType;/SElemType结构体数据类型,类型定义,预备知识,9,/数值型关键字的比较#define EQ(a,b)(a)=(b)#define LT(a,b)(a)(b)#define LQ(a,b)(a)=(b)/字符型关键字的比较#define EQ(a,b)(!strcmp(a),(b)#define LT(a,b)(strcmp(a),(b)0)#define LQ(a,b)(strcmp(a),(b)=0),宏定义,预备知识,10,为什么要针对各种数据结构进行查找？,在程序设计中，根据实际情况的需要，要将数据存储为一些特定的数据结构，例如数组，队列，堆，数等等。程序的

4、业务逻辑有时候需要确认某项数据是否存在。因此，要进行查找。例如宾馆电梯控制程序，查找Vip楼层是否在队列中国家缉毒部门要查找可疑的毒品走私犯人等等,预备知识,11,预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表,第8章 查找,12,8.1 静态查找表,8.1.1 顺序表的查找 8.1.2 有序表的查找*8.1.3 静态树表的查找/自学 8.1.4 索引顺序表的查找,13,8.1 静态查找表,数据对象D：,数据关系R：,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,数据元素同属一个集合。,ADT StaticSearchTable,基

5、本操作 P：,ADT StaticSearchTable,见下页,静态查找表的抽象数据类型,14,8.1 静态查找表,Create(/建立静态查找表,Destroy(/销毁静态查找表,Search(ST,key);/按关键字字key查找,Traverse(ST,Visit();/遍历查找表,基本操作,15,8.1 静态查找表,8.1.1 顺序表的查找 8.1.2 有序表的查找*8.1.3 静态树表的查找/自学 8.1.4 索引顺序表的查找,16,顺序查找,17,typedef struct/数据元素存储空间基址，建表时/按实际长度分配，0号单元留空 int length;/表的长度 SSTab

6、le;,8.1.1 顺序查找表,ElemType*elem;,顺序查找表存储结构,18,8.1.1 顺序查找表,从查找表的第一个元素向后（或从最后一个 元素向前），比较当前位置数据元素的关键字与查找关键字；若相等，输出当前位置，查找成功，若不相等，走向下一个位置；循环执行a)、b)步，直到查找成功或超出范围，表示查找失败。,顺序查找表的思想,19,8.1.1 顺序查找表,顺序查找表示例演示,55,67,78,76,45,33,99,88,越界了，表示没找到，返回值为0,监视哨,从后向前查找55,查找步骤：,20,33,67,78,76,45,33,99,88,监视哨,从后向前查找33,查找步骤

7、：,查找成功，返回当前位置5,8.1.1 顺序查找表,顺序查找表示例演示,21,8.1.1 顺序查找表,int Search_Seq(SSTable ST,KeyType key)/在顺序表ST中顺序查找其关键字等于/key的数据元素。若找到，则该函数/返回该元素在表中的位置，否则返回/0。ST.elem0.key=key;/“哨兵”for(i=ST.length;(i=0)/若返回值i为0，则表示没有找到/Search_Seq,顺序查找表的算法与实现,22,给定值进行比较的关键字个数的期望值:,8.1.1 顺序查找表,顺序查找表算法分析,n 为表长,Pi 为查找表中第i个记录的概率,Ci为找

8、到记录时，关键字的比较次数,23,在等概率查找的情况下，顺序表查找的平均查找长度为：,8.1.1 顺序查找表,顺序查找表算法分析,24,折半查找,25,8.1.2 有序表的查找,想一想：英文字典的特点及英语单词的查找过程。,折半查找的前提要求,英文字典是有序的，英语单词的查找用的是折半查找。,折半查找的前提要求是顺序存储并且有序。,26,折半查找表的思想,8.1.2 有序表的查找,1)将要查找关键字与查找表的中间的元素 进行比较，若相等，返回当前位值；2)若查找关键字比当前位置关键字大，向 前递归，否则向后递归。,27,low,high,mid=(low+high)/2,查找21,因为2156

9、，所以21不可能落到右面的区间，于是我们仅考虑左边的区间,8.1.2 有序表的查找,折半查找表示例演示,28,对于左边的区间，继续进行折半查找，如下,low,high,mid=(low+high)/2,因为2119，因此，21不可能在左边的区间出现，所以考虑在右端区间查找,8.1.2 有序表的查找,折半查找表示例演示,29,low,high,mid=(low+high)/2,此时，在mid点的值刚好等于21，所以查找成功,对右端的区间继续进行折半查找，如下,8.1.2 有序表的查找,折半查找表示例演示,查找成功，返回当前位置3,30,位置 0 1 2 3 4 5 6 7 8 9 10关键字05

10、 13 19 21 37 56 64 75 80 88 90,low,high,mid=(low+high)/2,high=mid-1,mid,low=mid+1,mid,8.1.2 有序表的查找,折半查找表示例演示,查找21,31,int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值 while(low=high)/语句见下页 return 0;/顺序表中不存在待查元素/Search_Bin,8.1.2 有序表的查找,折半查找表算法与实现,32,while(low=high)mid=(low+high)/2;if（

11、EQ(key,ST.elemmid.key)return mid;/找到待查元素 else if(LT(key,ST.elemmid.key)high=mid-1;/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找,8.1.2 有序表的查找,折半查找表算法与实现,33,0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 75 80 88 90用判定树描述折半查找的过程。,设n=2h-1(h=log2(n+1),平均查找长度,折半查找表算法分析,8.1.2 有序表的查找,5,8,9,10,6,7,4,3,2,0,1,查找速度真快！

12、,34,游戏：猜商品价格,某款IPad的价格在2000元到3000元之间，猜出它的价格。实际价格在下页,折半查找表算法分析,有序表的查找,35,实际价格：2888元,游戏：猜商品价格,折半查找表算法分析,有序表的查找,36,索引顺序表查找,37,8.1.4 索引顺序表的查找,索引顺序表的前提要求,查找表要求顺序存储要求查找表可以分成n块，并且当ij时，第i块中 的最小元素大于第j块中的最大元素。,0 1 2 3 4 5 6 7 8 9 10,按块单调增加,38,8.1.4 索引顺序表的查找,索引顺序表的查找思想,(1)首先确定所要查找关键字在哪一块中。,(2)在所确定的块中用顺序查找查找关键字

13、。,39,8.1.4 索引顺序表的查找,建立索引表,0 1 2 3 4 5 6 7 8 9 10,该块最大关键字该块起始位址,线性表,索引顺序表的示例演示,第1块最大值,第2块最大值,第3块最大值,第1块起始位置,第2块起始位置,第3块起始位置,40,查找示例：假如要查找42，则根据索引表：,整个查找表被分为了三块，按照块单调递增：第1块中的 最大关键字 小于 第2块的 最小关键字；第2块中的 最大关键字 小于 第3块的 最小关键字。因为42 22，所以42 肯定不在第一块中，因为42 48，而第三块的最小值也大于48，所以42肯定不在第三块中，所以决定在第二块中查找。一般情况下使用顺序查找法

14、。,8.1.4 索引顺序表的查找,41,typedef struct keytype key;int addr;indextype;typedef struct indextype indexmaxblock;int block;INtable;INtable IX;,8.1.4 索引顺序表的查找,索引表的存储结构,索引表数据类型,索引表结构,42,int SEARCH(SSTable ST,INtable IX,KeyType key)int I=0,s,e;/s记录在查找表中的开始位置/e记录在查找表中的结束位置 在索引表中查找，确定s和e的值 根据s和e的值在线性表中查找 return-

15、1,8.1.4 索引顺序表的查找,索引顺序表的算法与实现,43,while(keyIX.indexi.key)return-1,8.1.4 索引顺序表的查找,索引顺序表的算法与实现,44,思考题：如果索引表长度为b，每块平均长度 为L，那么平均查找长度是多少？,8.1.4 索引顺序表的查找,索引顺序表的算法分析,答案：(b+1)/2+(L+1)/2。,45,问题1：如果实现知道一个长度为1600位的查找表，被分为40块，按块单调增加，每块中的数据都是按照单调增加排列的，则是否还有必要利用索引顺序表进行查找？,问题2：如果实现知道一个长度为1600位的查找表，被分为40块，按块单调增加，每块都是

16、有序的（有的块为单调增加的，有的块为单调减少的），则是否还有必要利用索引顺序表进行查找？如果是，则在已经确定了的那块中，使用什么方法继续进行查找。,索引顺序表的算法分析,46,预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表,第8章 查找,47,8.2 动态查找表,8.2.1 二叉排序树(平衡二叉树，自己学)8.2.2 B树和B+树(需要者可自己学习),48,ADT DynamicSearchTable,动态查找表的抽象数据类型,数据对象D：数据关系R：,数据元素同属一个集合。,D是具有相同特性的数据元素的集合，每个数据元素含有类型相同的关键字，可唯一标识数据元素。,ADT D

17、ynamicSearchTable,基本操作P：,8.2 动态查找表,见下页,49,InitDSTable(&DT)/初始化表,DestroyDSTable(&DT)/销毁表,SearchDSTable(DT,key);/按关键字查找,InsertDSTable(/插入数据元素,DeleteDSTable(/删除数据元素,TraverseDSTable(DT,Visit();/遍历表,8.2 动态查找表,基本操作,50,二叉排序树的查找,51,二叉排序树(Binary Sort Tree)或者是一棵空树；或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有的结点 的关键字的值均小于它的

18、根结点的值；若它的右子树不空，则右子树上所有的结点 的关键字的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。,二叉排序树的定义,8.2.1 二叉排序树和平衡二叉树,52,45,12,53,3,37,100,24,61,90,78,45,12,37,24,二叉排序树的例子,8.2.1 二叉排序树和平衡二叉树,53,typedef struct BiTNode/结点结构 struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,TElemType data;,二叉排序树的存储结构,8.2.1 二叉排序树和平衡二叉树,54,当二叉排序树

19、不空时，先将给定值和根结点 的关键字比较，若相等，则查找成功；否则：若给定值小于根结点的关键字，则在左子树上继续进行查找；若给定值大于根结点的关键字，则在右子树上继续进行查找;直到找到或查到空结点时为止。,二叉排序树的查找思想,8.2.1 二叉排序树和平衡二叉树,55,在下图中查24,二叉排序树的查找示例演示,45,12,53,3,37,100,24,61,90,78,45,12,37,24,8.2.1 二叉排序树和平衡二叉树,例,查找成功，返回该节点的指针,56,二叉排序树的查找示例演示,45,12,53,3,37,100,24,61,90,78,45,53,100,61,90,8.2.1

20、二叉排序树和平衡二叉树,在下图中查100,例,查找成功，返回该节点的指针,57,二叉排序树的查找示例演示,45,12,53,3,37,100,24,61,90,78,45,53,100,61,90,NULL,8.2.1 二叉排序树和平衡二叉树,在下图中查93,例,查找失败，返回null,58,BiTree SearchBST(BiTree T,keytype k)BiTree p=T;while(p!=NULL)if(p-data.key=k)return p;if(kdata.key)p=p-lchild else p=p-rchild return NULL;,二叉排序树的查找算法,8.2

21、.1 二叉排序树和平衡二叉树,59,45,24,53,12,37,94,12,24,37,45,53,94,树1平均查找长度O(log2n),树2平均查找长度O(n),二叉排序树的查找算法分析,8.2.1 二叉排序树和平衡二叉树,60,二叉排序树的平均查找长度最差情况与顺序表相 同(关键字有序时),为O(n);最好情况与折半查找相同,是O（log2n）数量级的;二叉排序树的平均查找长度仍然是O(log2n)。,二叉排序树的查找算法分析,8.2.1 二叉排序树和平衡二叉树,61,若二叉树为空：则待插入结点*s作为根结点；当二叉排序树非空时：将待插结点关键字与根 结点进行比较，若相等，则说明树中已

22、有此结点，无须插入；若小于根结点，插入左子树；若大于根结点，插入右子树。,二叉排序树的插入算法思想,8.2.1 二叉排序树和平衡二叉树,62,12,45,3,37,53,100,24,61,在如下二叉排序树中插入25过程演示,45,25,二叉排序树的插入过程演示,12,37,24,8.2.1 二叉排序树和平衡二叉树,63,二叉排序树的插入算法,Status InsertBST(BiTree/树中已有关键字相同的结点，不再插入/Insert BST,8.2.1 二叉排序树和平衡二叉树,64,二叉排序树的插入算法分析,二叉排序树的插入算法的时间复杂性与查找 算法的时间复杂性相同;最好情况是O（lo

23、g2n）;最坏情况是O(n);平均情况是O(log2n)。,思考题：如何生成二叉排序树?,答案：从空树开始循环调用插入算法。,8.2.1 二叉排序树和平衡二叉树,65,例：从给定的一列数据出发，构造二叉排序树。给定：56 52 60 43 65 28 80 96 40 39 45,产生了一棵不平衡的二叉排序树,8.2.1 二叉排序树和平衡二叉树,56,66,例：从给定的一列数据出发，构造二叉排序树。给定：52 56 60 43 65 28 80 96 40 39 45,产生另外一棵不平衡的二叉排序树,8.2.1 二叉排序树和平衡二叉树,52,67,在二元查找树上的删除一个结点，要求删除结点后，

24、仍保持二叉排序树的结构特点不变。,二叉排序树的结点删除定义,8.2.1 二叉排序树和平衡二叉树,68,(1)p为叶结点,(2)p只有左子树,(3)p只有右子树,(4)p左右子树都有,设被删结点为p,其双亲结点为f，则p可能有以下4种情况：,二叉排序树的结点删除方法,8.2.1 二叉排序树和平衡二叉树,69,(1)p为叶结点,如右图所示：,删除方法：释放结点p，修改其父结点f的相应指针。,f,p,12,45,3,37,53,100,24,61,51,25,二叉排序树的结点删除方法,8.2.1 二叉排序树和平衡二叉树,70,(2)p只有左子树,如上图 所示：,删除方法：释放结点p，p的左子树顶替p

25、点的位置。,p,12,45,3,37,53,100,24,61,51,25,12,45,3,53,100,24,61,51,25,二叉排序树的结点删除方法,8.2.1 二叉排序树和平衡二叉树,71,(3)p只有右子树,如上图 所示：,删除方法：释放结点p，p的右子树顶替p点的位置。,12,45,3,37,53,100,24,61,25,12,45,3,37,100,24,61,25,二叉排序树的结点删除方法,8.2.1 二叉排序树和平衡二叉树,72,把左子树作为右子树中最小结点的左子树。,或者把右子树作为左子树中最大结点的右子树。,(4)p既有左子树，也有右子树，如上图 所示：,删除方法：,缺

26、点：,增加了树的高度。,12,45,3,37,53,100,24,61,51,25,二叉排序树的结点删除方法,8.2.1 二叉排序树和平衡二叉树,73,(4)p既有左子树，也有右子树,如上图 所示：,12,45,3,37,53,100,24,61,51,25,二叉排序树的结点删除方法,8.2.1 二叉排序树和平衡二叉树,改进删除方法：,找一个结点顶替它的位置。,能够顶替它的结点是左子树中最大的，右子树中最小的。我们用左子树最大的结点来顶替。,74,Status DeleteBST(BiTree/DeleteBST,二叉排序树的结点删除算法,8.2.1 二叉排序树和平衡二叉树,75,Status

27、 Delete(BiTree,二叉排序树的结点删除算法,8.2.1 二叉排序树和平衡二叉树,76,while(s-rchild)q=s;s=s-rchild;p-data=s-data;if(q!=p)q-rchild=s-lchild;else q-lchild=s-lchild;free(s);return TRUE;/Delete,二叉排序树的结点删除算法,8.2.1 二叉排序树和平衡二叉树,77,二叉排序树的删除算法分析,二叉排序树的删除算法的时间复杂性与查找算法的时间复杂性相同;最好情况是O（log2n）;最坏情况是O(n);平均情况是O(log2n),8.2.1 二叉排序树和平衡二

28、叉树,78,预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表,第8章 查找,79,8.3.1 什么是哈希表 8.3.2 哈希函数的构造方法 8.3.3 处理冲突的方法 8.3.4 哈希表的查找及其分析,8.3 哈希表,80,学生名单的顺序存储与查找方式：,哈希表的引入,030530101 张三 男030530103 李四 男030530133 王五 男,030530101 张三 男,030530103 李四 男,030530133 王五 男,0 1,8.3.1 什么是哈希表,例,顺序存储,81,030530101 张三 男,030530103 李四 男,030530133 王五

29、 男,0 1 2 32,H(num)=atoi(substr(num,8,2)-1,num=“030530101”name=“张三”sex=“男”,030530101 张三 男030530103 李四 男030530133 王五 男,substr(num,8,2)=“01”,哈希表的引入,8.3.1 什么是哈希表,不是按照顺序存储；按照函数映射,82,以结点的关键字K为自变量，通过一个确定的函数关系H，计算出对应的函数值H(K),把这个函数值作为结点的存储地址。存储时：把关键字为K的数据元素存储在地址H(K)中;查找时：给定关键字K，直接到地址H(k)中取数据元素。,哈希表的思想,8.3.1

30、什么是哈希表,优点：查找的速度快,83,用散列法存储的线性表叫散列表（Hash table）,又称杂凑表，哈希表，对应的函数称为散列函数、杂凑函数或哈希函数。,哈希表的定义,8.3.1 什么是哈希表,84,(1)装填因子：设散列表空间大小为n，填入表中的结点数为 m,则称=m/n为散列表的装填因子。(2)散列函数的选取原则：运算简单；函数值域不能超过表长；尽可能使关键字不同时，散列函数值也不同。(3)冲突与同义词 若H(k1)=H(k2),则称为冲突，发生冲突的两个关键字k1和k2称为同义词。,哈希表的有关概念,8.3.1 什么是哈希表,85,直接定址法,8.3.2 哈希函数的构造方法,取关键

31、字的某个线性函数值为哈希地址。即:H(key)=a*key+b 其中a、b为常数。又称H(key)为自身函数。优点：没有冲突；缺点：若关键字集合很大，浪费存储空间严重。,86,质数除余法,8.3.2 哈希函数的构造方法,如果表长为n，取小于或等于n的最大质数m作模，关键字通过m取模运算，所得值作为散列地址。,例子：针对以下的数据，使用质数除余法，决定存储地址 56 52 60 43 65 28 80 96 40 39 45H(a)=a%53则得存储地址：3 52 7 43 12 28 27 43 40 39 45,87,平方取中法,int Hash(int key)/假设key是4位整数 ke

32、y*=key；/求平方 key=key/100；/去掉末尾的两位数 key=key%1000;return key；,8.3.2 哈希函数的构造方法,在不知道关键字的全部情况时，可通过求关键字的平方值扩大差别，然后取中间几位作为哈希地址：,88,折叠法（关键字太长，分成几块，相加）数字分析法（预先知道数据结构，例如身份证）基数转换法（例如，10进制转换为8进制）,8.3.2 哈希函数的构造方法,89,又叫开放地址，用于顺序存储；开放地址指地址单元为空，对于数组来说，是指还没存入数据的数组单元，在顺序存储结构中用一定方法进行散列存取的方法称为开放定址法。,开放定址法的定义,8.3.3 处理冲突的

33、方法,90,设散列表的长度为13，散列函数为:H(K)=K%13,给定的关键字序列为:19,14,23,1,68,20,84,27,54,11,10,0 1 2 3 4 5 6 7 8 9 10 11 12,14,23,(1)线性探测再散列法：若H(key)=d的单元发生冲 突，则按下述方法进行探查：hi(k)=(h(k)+i)%n，n是散列表的长度，1in-1,1,68,20,19,27,54,H(K)=6,1,10,1,3,7,6,1,2,11,10,11,10,84,开放定址法示例演示,8.3.3 处理冲突的方法,例,91,二次聚集的概念,8.3.3 处理冲突的方法,两个本来不发生冲突的

34、非同义词，也就是散列地址不同的结点，发生争夺同一个散列地址的现象称为二次聚集或堆积。,92,查找分析：查11，查40。1、利用散列函数计算出关键字为K的数据元素的地址：d=H(K)，如果Fd.key=K,查找成功，返回d;2、如果Fd.key!=K,依次查找F(d+i)%n.key,直到找到某个F(d+j)%n.key=K,返回(d+j)%n,或者找到一个开放地址为止，此时显示没找到。,19,14,23,1,68,20,84,27,54,11,10,0 1 2 3 4 5 6 7 8 9 10 11 12,14,23,1,68,20,19,27,54,H(K)=6,1,10,1,3,7,6,1

35、,2,11,10,11,10,84,开放定址法查找示例演示,8.3.3 处理冲突的方法,93,删除分析：如果删除68，查找27。删除结点时不能简单地将被删结点的地址置空（使用一个特殊标记、值占位），否则将截断它之后填入散列表的同义词的查找路径(如果删除了68，并且使得地址置空，则将无法查找得到27),19,14,23,1,68,20,84,27,54,11,10,0 1 2 3 4 5 6 7 8 9 10 11 12,14,23,1,68,20,19,27,54,H(K)=6,1,10,1,3,7,6,1,2,11,10,11,10,84,开放定址法删除示例演示,8.3.3 处理冲突的方法,

36、94,(1)线性探测再散列法：若H(key)=d的单元发生冲突，则按下述方法进行探查：hi(k)=(h(k)+i)%n,n是散列表的长度，1in-1,(2)二次探测再散列法：若H(key)=d的单元发生冲突，则按下述方法进行探查：hi(k)=(h(k)+di)%n,n是散列表的长度，di=12,-12,22,-22,k2,-k2(k n/2),(3)伪随机探测再散列，取di=伪随机序列（种子一样，随机一样，不会变）,开放定址法处理冲突的方法,8.3.3 处理冲突的方法,95,设置RHi()，i=1,2,k 多个哈希函数，当一个哈希函数产生冲突时，顺序用下一个。,(4)再哈希法（再散列法）,开放

37、定址法处理冲突的方法,8.3.3 处理冲突的方法,96,链地址法（又称拉链法）的示例演示,01234,19,14,23,1,68,20,84,27,54,11,10,79,H(K)=6,1,10,1,3,7,6,1,2,11,10,1,8.3.3 处理冲突的方法,先查找指针，然后按照顺序查找,97,拉链法（外散列表）平均查找长度比开放地质法（内散列法）平均查找长度短。,14,23,1,68,20,19,27,54,11,10,84,79,0 1 2 3 4 5 6 7 8 9 10 11 12,8.3.3 处理冲突的方法,开放定址法与链地址法平均查找长度比较,例子查找79,使用链地址法查找：,

38、98,拉链法的查找算法,01234,8.3.3 处理冲突的方法,根据关键字K找到关键字为K的结点所在单链表的首地址；在所找到的单链表上进行顺序查找，若找到则返回地址值，否则返回空值。,99,拉链法的插入算法：,8.3.3 处理冲突的方法,根据关键字K找到关键字为K的结点所应该存在的单链表的首地址；在单链表中查找结点为K的关键字，若找到，则无须插入；若没找到，利用头插法或尾插法插入单链表中。,100,哈希表存储结构,int hashsize=997,.;typedef struct ElemType*elem;int count;/当前数据元素个数 int sizeindex;/hashsize

39、sizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE-1,8.3.4 哈希表的查找和分析,101,Status SearchHash(HashTable H,KeyType K,int&p,int&c)/SearchHash,p=Hash(K);/求得哈希地址,while(H.elemp.key!=NULLKEY/求得下一探查地址 p,if(EQ(K,H.elemp.key)return SUCCESS;/查找成功，返回待查数据元素位置 p,else return UNSUCCESS;/查找

40、不成功,哈希表的查找算法,8.3.4 哈希表的查找和分析,102,(1)选用的哈希函数；(2)选用的处理冲突的方法；(3)哈希表饱和的程度，装载因子=n/m 值的大小（n记录数，m表的长度）,决定哈希表查找的ASL的因素：,哈希表的插入算法分析,8.3.4 哈希表的查找和分析,103,一般情况下，可以认为选用的哈希函数是“均匀”的，也就是在讨论ASL（平均查找长度）时，认为各个位置被存数据的概率是相等的。,在这种情况下，可认为哈希表的ASL是处理冲突方法和装载因子的函数。,哈希表的插入算法分析,8.3.4 哈希表的查找和分析,104,(1)线性探测再散列平均查找长度,查找成功时有下列结果（经过

41、大量的数据 实验，得出以下的经验公式）：,8.3.4 哈希表的查找和分析,105,(3)链地址法平均查找长度,(2)随机探测再散列平均查找长度,查找成功时有下列结果：,8.3.4 哈希表的查找和分析,106,哈希表的平均查找长度是装填因子 的函数，而不是 n 的函数。,这说明，用哈希表构造查找表时，可以选择一个适当的装填因子，使得平均查找长度限定在某个范围内。,8.3.4 哈希表的查找和分析,107,不同的散列函数构成的散列表平均查找长度是不同的。由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。散列法与其他查找方法的区别:除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。,散列法与其它方法的比较,8.3.4 哈希表的查找和分析,108,本章小结,熟练掌握顺序查找、二分查找、二叉排序 树查找以及散列表查找的基本思想和算法实现。熟练掌握顺序查找、二分查找、二叉排序树查找以及散列表查找的应用条件以及算法优劣。掌握二叉排序树的删除算法和平衡二叉树的构造算法的概要。,