预备知识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 Key

3、type key; /声明关键字 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是具有相同特性的数据元素的集合。每个数

5、据元素含有类型相同的关键字，可唯一标识数据元素。,数据元素同属一个集合。,ADT StaticSearchTable ,基本操作 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,顺序查找,

6、17,typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;,8.1.1 顺序查找表,ElemType *elem;,顺序查找表存储结构,18,8.1.1 顺序查找表,从查找表的第一个元素向后（或从最后一个 元素向前），比较当前位置数据元素的关键字与查找关键字； 若相等，输出当前位置，查找成功，若不相等，走向下一个位置； 循环执行a)、b)步，直到查找成功或超出范围，表示查找失败。,顺序查找表的思想,19,8.1.1 顺序查找表,顺序查找表示例演示,55,67,78,76,45,33,99,88,

7、越界了，表示没找到，返回值为0,监视哨,从后向前查找55,查找步骤：,20,33,67,78,76,45,33,99,88,监视哨,从后向前查找33,查找步骤：,查找成功，返 回当前位置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，则表示没

8、有找到 / Search_Seq,顺序查找表的算法与实现,22,给定值进行比较的关键字个数的期望值:,8.1.1 顺序查找表,顺序查找表算法分析,n 为表长,Pi 为查找表中第i个记录的概率,Ci为找到记录时，关键字的比较次数,23,在等概率查找的情况下， 顺序表查找的平均查找长度为：,8.1.1 顺序查找表,顺序查找表算法分析,24,折半查找,25,8.1.2 有序表的查找,想一想：英文字典的特点及英语单词的查找过程。,折半查找的前提要求,英文字典是有序的，英语单词的查找用的是折半查找。,折半查找的前提要求是顺序存储并且有序。,26,折半查找表的思想,8.1.2 有序表的查找,1)将要查找关

9、键字与查找表的中间的元素 进行比较，若相等，返回当前位值； 2)若查找关键字比当前位置关键字大，向 前递归，否则向后递归。,27,low,high,mid= (low+high)/2,查找21,因为2156，所以21不可能落到右面的区间，于是我们仅考虑左边的区间,8.1.2 有序表的查找,折半查找表示例演示,28,对于左边的区间，继续进行折半查找，如下,low,high,mid= (low+high)/2,因为2119，因此，21不可能在左边的区间出现，所以考虑在右端区间查找,8.1.2 有序表的查找,折半查找表示例演示,29,low,high,mid= (low+high)/2,此时，在mi

10、d点的值刚好等于21，所以查找成功,对右端的区间继续进行折半查找，如下,8.1.2 有序表的查找,折半查找表示例演示,查找成功，返 回当前位置3,30,位置 0 1 2 3 4 5 6 7 8 9 10 关键字05 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; / 置区间

11、初值 while (low = high) /语句见下页 return 0; / 顺序表中不存在待查元素 / Search_Bin,8.1.2 有序表的查找,折半查找表算法与实现,32,while (low = high) mid = (low + high) / 2; if （EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 ,8.1.2 有序

12、表的查找,折半查找表算法与实现,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,查找速度真快！,34,游戏：猜商品价格,某款IPad的价格在2000元到3000元之间，猜出它的价格。实际价格在下页,折半查找表算法分析,8.1.2 有序表的查找,35,实际价格：2888元,游戏：猜商品价格,折半查找表算法分析,8.1.2 有序表的查找,36,索引

13、顺序表查找,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) 在所确定的块中用顺序查找查找关键字。,39,8.1.4 索引顺序表的查找,建立索引表,0 1 2 3 4 5 6 7 8 9 10,该块最大关键字该块起始位址,线性表,索引顺序表的示例演示,第1块最大值,第2块最大值,第3块最大值,第1块起 始位置,第2块

14、起 始位置,第3块起 始位置,40,查找示例：假如要查找42，则根据索引表：,整个查找表被分为了三块，按照块单调递增： 第1块中的 最大关键字 小于 第2块的 最小关键字； 第2块中的 最大关键字 小于 第3块的 最小关键字。 因为42 22，所以42 肯定不在第一块中， 因为42 48，而第三块的最小值也大于48，所以42肯定不在第三块中， 所以决定在第二块中查找。一般情况下使用顺序查找法。,8.1.4 索引顺序表的查找,41,typedef struct keytype key; int addr; indextype; typedef struct indextype indexmaxb

15、lock; 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 -1 ,8.1.4 索引顺序表的查找,索引顺序表的算法与实现,43,while (keyIX.indexi.key) return -1 ,8.1.4 索引顺序表的查找,索引顺

16、序表的算法与实现,44,思考题：如果索引表长度为b，每块平均长度 为L，那么平均查找长度是多少？,8.1.4 索引顺序表的查找,索引顺序表的算法分析,答案：(b+1)/2+(L+1)/2。,45,问题1：如果实现知道一个长度为1600位的查找表，被分为40块，按块单调增加，每块中的数据都是按照单调增加排列的，则是否还有必要利用索引顺序表进行查找？,问题2：如果实现知道一个长度为1600位的查找表，被分为40块，按块单调增加，每块都是有序的（有的块为单调增加的，有的块为单调减少的），则是否还有必要利用索引顺序表进行查找？如果是，则在已经确定了的那块中，使用什么方法继续进行查找。,索引顺序表的算法

17、分析,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 DynamicSearchTable,基本操作P：,8.2 动态查找表,见下页,49,InitDSTable(&DT) /初始化表,DestroyDSTab

18、le(&DT) /销毁表,SearchDSTable(DT, key); /按关键字查找,InsertDSTable( /插入数据元素,DeleteDSTable( /删除数据元素,TraverseDSTable(DT, Visit(); /遍历表,8.2 动态查找表,基本操作,50,二叉排序树的查找,51,二叉排序树(Binary Sort Tree)或者是一棵空树；或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有的结点 的关键字的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有的结点 的关键字的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。,二叉排序树

19、的定义,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,当二叉排序树不空时，先将给定值和根结点 的关键字比较，若相等，则查找成功；否则： 若给定值小于根结点的关键字，则在左子树上继续进行

20、查找； 若给定值大于根结点的关键字，则在右子树上继续进行查找; 直到找到或查到空结点时为止。,二叉排序树的查找思想,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 二叉排序树和平衡二叉树,在下图中查100,例,查找成功，返回 该节点的指针,57,二叉排序树的查找示例演示,45

21、,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.1 二叉排序树和平衡二叉树,59,45,24,53,12,37,94,12,24,

22、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作为根结点； 当二叉排序树非空时：将待插结点关键字与根 结点进行比较，若相等，则说明树中已有此结点，无须插入； 若小于根结点，插入左子树； 若大于根结点，插入右子树

23、。,二叉排序树的插入算法思想,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（log2n）;最坏情况是O(n);平均情况是O(log2n)。,

24、思考题：如何生成二叉排序树?,答案：从空树开始循环调用插入算法。,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,在二元查找树上的删除一个结点，要求删除结点后，仍保持二叉排序树的结构特点不变。,二叉排序树的结点删除

25、定义,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点的位置。,p,12,45,3,37,53

26、,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既有左子树，也有右子树， 如上图 所示：,删除方法：,缺点：,增加了树的高度。,12,45

27、,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 Delete(BiTr

28、ee ,二叉排序树的结点删除算法,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)

29、,8.2.1 二叉排序树和平衡二叉树,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 张三 男,03053010

30、3 李四 男,030530133 王五 男,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，直接到地

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

32、3.1 什么是哈希表,85,直接定址法,8.3.2 哈希函数的构造方法,取关键字的某个线性函数值为哈希地址。即: 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 45 H(a) = a%53 则得存储地址： 3 52 7 43 12 28 27 4

33、3 40 39 45,87,平方取中法,int Hash(int key) /假设key是4位整数 key*=key； /求平方 key=key/100； /去掉末尾的两位数 key=key%1000; return key； ,8.3.2 哈希函数的构造方法,在不知道关键字的全部情况时，可通过求关键字的平方值扩大差别，然后取中间几位作为哈希地址：,88,折叠法（关键字太长，分成几块，相加） 数字分析法（预先知道数据结构，例如身份证） 基数转换法（例如，10进制转换为8进制）,8.3.2 哈希函数的构造方法,89,又叫开放地址，用于顺序存储； 开放地址指地址单元为空，对于数组来说，是指还没存入

34、数据的数组单元，在顺序存储结构中用一定方法进行散列存取的方法称为开放定址法。,开放定址法的定义,8.3.3 处理冲突的方法,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

35、, 1, 2, 11, 10,11,10,84,开放定址法示例演示,8.3.3 处理冲突的方法,例,91,二次聚集的概念,8.3.3 处理冲突的方法,两个本来不发生冲突的非同义词，也就是散列地址不同的结点，发生争夺同一个散列地址的现象称为二次聚集或堆积。,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, 6

36、8, 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 处理冲突的方法,93,删除分析：如果删除68，查找27。 删除结点时不能简单地将被删结点的地址置空（使用一个特殊标记、值占位），否则将截断它之后填入散列表的同义词的查找路径(如果删除了68，并且使得地址置空，则将无法查找得到27),19, 14, 23, 1, 68, 20, 84, 27, 54, 11,

37、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 处理冲突的方法,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, -1

38、2, 22, -22, k2, -k2 (k n/2),(3) 伪随机探测再散列，取di=伪随机序列（种子一样，随机一样，不会变）,开放定址法处理冲突的方法,8.3.3 处理冲突的方法,95,设置RHi()，i=1, 2, k 多个哈希函数，当一个哈希函数产生冲突时，顺序用下一个。,(4) 再哈希法（再散列法）,开放定址法处理冲突的方法,8.3.3 处理冲突的方法,96,链地址法（又称拉链法）的示例演示,0 1 2 3 4 ,19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10, 79,H(K) = 6, 1, 10, 1, 3, 7, 6, 1, 2, 11,

39、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,使用链地址法查找：,98,拉链法的查找算法,0 1 2 3 4,8.3.3 处理冲突的方法,根据关键字K找到关键字为K的结点所在单链表的首地址； 在所找到的单链表上进行顺序查找，若找到则返回地址值，否则返回空值。,99,拉链法的插入算法：,8

40、.3.3 处理冲突的方法,根据关键字K找到关键字为K的结点所应该存在的单链表的首地址； 在单链表中查找结点为K的关键字，若找到，则无须插入； 若没找到，利用头插法或尾插法插入单链表中。,100,哈希表存储结构,int hashsize = 997, . ; typedef struct ElemType *elem; int count; / 当前数据元素个数 int sizeindex; / hashsizesizeindex为当前容量 HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1,8.3.4 哈希

41、表的查找和分析,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; / 查找不成功,哈希表的查找算法,8.3.4 哈希表的查找和分析,102,(1) 选用的哈希函数； (2) 选用的处理冲突的方法； (3

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

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