查找的基本概念(2).ppt课件

1、第八章 查找1查找的基本概念备注2概念查找表查找操作针对的数据集，由同一类型的数据元素组成关键字(key)数据元素中某个数据项的值，可唯一标识该数据元素关键字和数据元素的类型说明，如typedef float KeyType; /实型typedef int KeyType; /整型typedef char *KeyType; /字符串型typedef struct KeyType key; /关键字域 /其它域ElemType;3概念查找在查找表中根据关键字找出特定的数据元素的操作查找成功关键字找到，返回对应数据元素在查询表中的位置查找失败关键字没有找到，返回空记录或空指针关键字比较的宏定义/

2、对数值类型关键字#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)4概念查找算法取决于查找表的数据结构静态查找表查找表事先已确定对查询表除了创建和销毁操作外，只有查找或遍历操作动态查找表查找表本身在查找过程中动态生成，即若没有找到，则插入该元素对查询表除了创建、销毁、查找、遍历操

3、作外，还能进行插入和删除操作5一些约定典型的关键字类型说明：typedef float KeyType;/实型typedef int KeyType;/整型typedef char *KeyType;/字符串型数据元素类型定义为：typedef structKeyType key; / 关键字域.ElemType; 6对两个关键字的比较约定为如下的宏定义：对数值型关键字#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

4、 LT(a,b) (strcmp(a),(b)0)#define LQ(a,b) (strcmp(a),(b)=0)79.1静态表查找顺序表的查找有序表的查找索引顺序表的查找8静态查找表的类型定义：ADT StaticSearchTable数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：9Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST);初始条件：静态查找表ST存在。操作结果：销毁表ST。Search(ST,key);初始条件：静态查找表ST

5、存在，key为和关键字类型相同的给定值。操作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit();初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。ADT StaticSearchTable109.1.1顺序表的查找顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。11静态查找表的顺序存储结构

6、typedef struct ElemType *elem;int length;SSTable;int Search_Seq(SSTable ST,KeyType key)ST.elme0.key=key;for(i=ST.length; !EQ(ST.elemi.key,key); -i);return i;查找算法12查找操作的性能分析：查找算法中的基本操作是将记录的关键字和给定值进行比较，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。平均查找长度 Average Search Length：为确定记录在查找表中的位置，需用和给定值进行比较的关键字个数的期望值称为查

7、找算法在查找成功时的平均查找长度。13 其中：Pi为查找表中第i个记录的概率，且 ；Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。 等概率条件下有： 假设查找成功与不成功的概率相同： 149.1.2静态查找表（二）有序表的查找折半查找的查找过程以有序表表示静态查找表时，Search函数可用折半查找来实现。先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。 15折半查找的查找实现int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;while(lowdata.key)

8、 return (T); else if (LT(key, T-data.key) return (SearchBST(T-lchild, key); elsereturn (SearchBST(T-rchild, key);29二叉排序树二叉排序树的查找算法二(考虑查找失败后将插入记录，插入的记录将成为一个新的叶子结点，故需在查找过程中预留插入位置)Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) /在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，/若查找成功则p指向该数据元素结点，并返回TRUE，否则

9、指针p指向查/找路径上访问的最后一个结点(一定是一个叶子结点)并返回FALSE，/指针f指向T的双亲，其初始调用值为NULL if (!T) p = f; return FALSE; else if (EQ(key, T-data.key) p = T; return TRUE; else if (LT(key, T-data.key) SearchBST(T-lchild, key, T, p); else SearchBST(T-rchild, key, T, p);30二叉排序树的插入(创建)算法Status InsertBST(BiTree &T, ElemType e) /当二叉排序

10、树T中不存在关键字等于e.key的数据元素时，/插入e并返回TRUE，否则返回FALSE if (!SearchBST(T, e.key, NULL, p) /查找不成功 s = (BiTree)malloc(sizeof(BiNode); s-data = e; s-lchild = s-rchild = NULL; /新的叶子结点 if (!p) T = s; else if (LT(e.key, p-data.key) p-lchild = s; else p-rchild = s; return TRUE; else return FALSE; 从空树开始，经过一系列查找插入操作后，可

11、生成一棵二叉排序树31例一：假设查找的关键序列为45,24,53,45,12,24,90，则生成二叉排序树的过程如下图所示：454524452453452453124524531290abcde32例二：假设查找的关键序列为27,32,16,27,14,16,27，则生成二叉排序树的过程如下图所示：abcd2727322716322716321433二叉排序树二叉排序树的特点中序遍历二叉排序树可得到一个关键字的有序序列（即：可以通过输入一个无序序列，而通过构造二叉排序树后进行遍历的方法实现排序）二叉排序树的插入过程不需要移动其他记录具有相同n个结点的二叉排序树会因为构造的时候关键字插入的顺序不

12、同而不同(下页说明)二叉排序树的查找算法具有折半查找的特性，同时又采用了链式存储结构，因此是动态查找表的适宜表示34如：查找的关键序列分别为27,32,16,14、16,14,27,32和14,16,27, 32, 生成二叉排序树分别如下：27163214161427321416273235例 找 1004036在二叉排序树中删除一个节点的算法Status DeleteBST(BiTree &T,KeyType key)if(!T) return FALSE;elseif EQ(key,T-data.key) Delete(T);else if LT(key,T-data.key) Delet

13、eBST(T-lchild,key);else DeleteBST(T-rchild,key);return TRUE;37void Delete(BiTree &p)if(!p-rchild)q=p; p=p-lchild; free(q);else if(!p-lchild)q=p;p=p-rchild; free(q);else/左右子树都不空/方法一：如图示q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild/转左，然后向右到尽头p-data=s-data; /s指向被删结点的前驱if(q!=p)q-rchild=s-lchild; /重接*q的右子

14、树else q-lchild=s-lchild;/重接*q的左子树 （方法一结束）38q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild/转左，然后向右到尽头p-data=s-data; /s指向被删结点的前驱if(q!=p)q-rchild=s-lchild; /重接*q的右子树else q-lchild=s-lchild;/重接*q的左子树 （方法一结束）39/或可用方法二：/q=s=(*p)-lchild; /while(s-rchild) s=s-rchild; /s-rchild=(*p)-rchild; /free(*p); /(*p)=q;

15、40二叉排序树的查找分析最差情况最好情况平均性能419.3 哈希(Hash)表一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的，使每个关键字和结构中一个唯一的存储位置相对应。称对应关系f就是哈希函数42哈希表最常见的例子是以学生学号为关键字的成绩表，号学生的记录位置在第一条，号学生的记录位置在第条.如果我们以学生姓名为关键字，如何建

16、立查找表，使得根据姓名可以直接找到相应记录呢？abcdefghijklmnopqrstuvwxyz1234567891011121314151617181920212223242526刘丽刘宏英吴军吴小艳李秋梅陈伟.姓名中各字拼音首字母lllhywjwxylqmcw.用所有首字母编号值相加求和244633724226.最小值可能为3 最大值可能为78 可放75个学生用上述得到的数值作为对应记录在表中的位置，得到下表：用上述得到的数值作为对应记录在表中的位置，得到下表：43：成绩一成绩二.3.24刘丽829525.26陈伟.33吴军.42李秋梅.46刘宏英.72吴小艳.78.上面这张表即哈希表。

17、如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：李秋梅:lqm 12+17+13=42 取表中第42条记录即可。问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。44Hash表又称散列表Hash函数建立关键字值集合到存储地址集合的映射关系即：记录的存储位置loc = h(key)Hash表所有记录按Hash思想组成而成的表优点：根据key值，查找时不必经过多次key值比较就可以一次定位，直接找到所查找的记录问题：hash函数的选择非常重要，如果不同的key值可能得到相同的loc，那末就存在存储位置

18、冲突的问题Hash函数顺序表下标值等45哈希(Hash)表如：hash函数h(key) = key mod 10, 记录集合为No. Name Class Zhang c1 Liu c2 Wang c1 Li c3则Hash表为10 Li c312 Liu c24 Wang c15 Zhang c301234567lockey46哈希(Hash)表冲突问题不同key值对应的hash函数值(地址值)相同冲突产生的原因通常hash表的大小小于key值集合的大小Hash函数构造不合理建立hash表时需要重要考虑的是设定好的hash函数，使hash值尽可能均匀分布建立相应的冲突处理方法(冲突不可避免，

19、力求尽量减少)47二、哈希表的构造方法直接定址法 数字分析法平方取中法折叠法除留余数法 随机数法 48例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。地址0102.252627.100年龄12.252627.人数30002000.1050.、直接定址法49、数字分析法有学生的生日数据如下：年.月.日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15.经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。50、平方取中法取关键字平方后的中间几位为哈希地址。

20、Fig.9.2351将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：5864586442200224+)04+)04-100886092H(key)=0088H(key)=6092(a)移位叠加(b)间界叠加、折叠法52、除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(

21、key)=key MOD p (p=m)53、随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。54二、处理冲突的方法成绩一成绩二.3.24刘丽829525.26陈伟.33吴军.42李秋梅.46刘宏英.72吴小艳.78.如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：55选择其它位置的方法有：开放定址法再哈希法链地址法建立一个公共溢出

22、区56、开放定址法Hi=(H(key)+di) MOD m i=1,2,.,k(k=m-1)其中m为表长，di为增量序列如果di值可能为1,2,3,.m-1，称线性探测再散列。如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,.k*k,-k*k(k=m/2)称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。Hi = (H(key)+di)mod m di =伪随机数序列57例：在长度为11的哈希表中已填有关键字分别为17, 60, 29的记录， H(key) = key MOD 11现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散

23、列，如下：012345678910601729(a)插入前01234567891060172938(b)线性探测再散列58012345678910601729(a)插入前01234567891038601729(c)二次探测再散列01234567891038601729(d)伪随机探测再散列伪随机数列为9,5,3,8,1.59、再哈希法当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。60、链地址法将所有关键字为同义词的记录存储在同一线性链表中012345678910111201 14 27 79 55 68 19 84 10 23 20 11 已知一组关键

24、字为19,14,23,01,68,20,84,27,55,11,10,79，则按hash函数H(key) = key mod 13和链地址法处理冲突构造所得的hash表为：61、建立一个公共溢出区假设哈希函数的值域为0,m-1,则设向量HashTable0.m-1为基本表，另外设立存储空间向量OverTable0.v用以存储发生冲突的记录。62三、哈希表的查找/开放定址哈希表的存储结构int hashsize=997,.;typedef structElemType *elem;int count;int sizeindex;HashTable;63#define SUCCESS 1#defi

25、ne UNSUCCESS 0#define DUPLICATE -1Status SearchHash(HashTable H,KeyType K,int &p,int &c)p=Hash(K);while(H.elemp.key!=NULLKEY & !EQ(K,H.elemp.key)collision(p,+c);if(EQ(K,H.elemp.key)return SUCCESS;else return UNSUCCESS;64Status InsertHash(HashTable &H,EleType e)c=0;if(SearchHash(H,e.key,p,c)return DUPLICATE;else if(chashsizeH.sizeindex/2)H.elemp=e; +H.count; return OK;else RecreateHashTable(H);65Example 9.3Key: