《预备知识81静态查找表82动态查找表83哈希表》由会员分享，可在线阅读，更多相关《预备知识81静态查找表82动态查找表83哈希表（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 索引顺序表的查找,索引顺序表的算法与实现,44,思考题：如果索引表长度为b，每块平均长度 为L，那么平均查找长度是多少？,8.1.4 索引顺序表的查找,索引顺序表的算法分析,答案：(b+1)/2+(L+1)/2。,45,问题1：如果实现知道一个长度为1600位的查找表，被分为40块，按块单调增加，每块中的数据都是按照单调增加排列的，则是否还有必要利用索引顺序表进行查找？,问题2：如果实现知道一个长度为1600位的查找表，被分为40块，按块单调增加，每块都是有序的（有的块为单调增
