检索查找技术教学讲座PPT.ppt

《检索查找技术教学讲座PPT.ppt》由会员分享，可在线阅读，更多相关《检索查找技术教学讲座PPT.ppt（76页珍藏版）》请在三一文库上搜索。

1、第九章 查找技术,课前思考题： 猜价格游戏：已知主持人手中物品价格为1至31元之间的整数，猜中者可得到该奖品。 1.如果你猜错时主持人只告诉你所猜价格错了让你重新猜，平均要几次才能猜对？ 2.如果你猜错时主持人告诉你所猜价格是高了还是低了再让你重新猜，最少要几次才可以保证对任意一个价格都能猜对？,9.1.1 查找的基本概念,关键码：可以标识一个记录的某个数据项。,键值：关键码的值。 主关键码：可以唯一地标识一个记录的关键码。 次关键码：不能唯一地标识一个记录的关键码。,查找 ：在具有相同类型的记录构成的集合中找出满足给定条件的记录。,查找的结果 ：若在查找集合中找到了与给定值相匹配的记录，则称

2、查找成功；否则，称查找查找失败。,概述,静态查找 ：不涉及插入和删除操作的查找 。,动态查找 ：涉及插入和删除操作的查找。,查找结构 ：面向查找操作的数据结构 。,本章讨论的查找结构 ： 线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。 树表：适用于动态查找，主要采用二叉排序树的查找技术。 散列表：静态查找和动态查找均适用，主要采用散列技术。,概述,9.1.2 查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,算法； 问题规模； 待查关键码在查找集合中的位置。,查找算法的时间复杂度是问题规模n和待查关键码在查找集合中的位置k的函数，记为T(n，k)。,概述,将查找算法进

3、行的关键码的比较次数的数学期望值定义为平均查找长度ASL 。计算公式为：,ASL,其中：n：问题规模，查找集合中的记录个数； pi：查找第i个记录的概率； ci：查找第i个记录所需的关键码的比较次数。,概述,例：某班级30人，按姓名先后次序查找某人， 则其查找成功的平均查找长度为：,查找失败的情况？,概述,线性表,9.2.1 顺序查找 （线性查找）,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,1. 顺序表的顺序查找,20 10 15 24 6 12 35 40

4、98 5,0 1 2 3 4 5 6 7 8 9,查找方向,2. 改进算法 设置“哨兵”。哨兵就是待查值，将它放在查找方向的“尽头”处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,伪代码 1. 设置哨兵k(置于查找方向的“尽头”)； 2. 设置查找的起始下标； 3. 若ri与k相等，则返回当前i的值; 否则，继续比较下一个记录;,线性表,0 1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找64,64,哨兵,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素：

5、 n 查找第i个元素： n+1-i 查找失败： n+1,平均查找长度？ ASL=(1+2+3+n)/n =(n+1)/2=O(n),线性表,/*/ /* 线性表检索用的头文件 文件名:seqlist.h */ /*/ #include #define maxsize 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct datatype datamaxsize; int len; /*线性表长度*/ seqlist; /*预定义的顺序表类型*/,线性表,算法9.1给出了基于顺序查找表的顺序检索方法。 /*

6、顺序检索算法 文件名:s_search.c */ /* 函数名: seqsearch1()、seqsearch2() */ #include “seqlist.h“ /*-顺序查找的非递归实现-*/ int seqsearch1(seqlist l,datatype key) int k=l.len-1; while (k=0 ,线性表,/*-顺序查找的递归实现-*/ int seqsearch2(seqlist l,int n,datatype key) int k=0; if (n=-1) k=-1; else if (l.datan=key) k=n; else k=seqsearch2

7、(l,n-1,key); return(k); 算法9.1 线性表的顺序检索（顺序存储）,线性表,9.2.2 二分法检索,二分法检索又称为折半查找，采用二分法检索可以大大提高查找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用顺序存储结构。,采用二分搜索时，先求位于搜索区间正中的对象的下标 mid，用其关键码与给定值x比较: x = lmid. Key，搜索成功； x lmid. Key，把搜索区间缩小到表的后半部分。,线性表,下面分析在其中二分检索关键字20的过程,线性表,每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。,例

8、：有一组有序的线性表如下： （10，14，20，32，45，50，68，90，100，120）,分析二分检索关键字95的过程:,线性表,例：有一组有序的线性表如下： （10，14，20，32，45，50，68，90，100，120）,下面给出二分检索法的非递归与递归实现算法，算法中使用seqlist.h中定义的顺序查找表。,/*/ /* 二分查找算法 文件名：b_search.c */ /* 函数名：binsearch1()、binsearch2() */ /*/ /*-二分查找的非递归实现-*/ int binsearch1(seqlist l,datatype key) int low=0

9、,high=l.len-1,mid; while (low=high),线性表, mid = (low+high)/2; /*二分*/ if (l.datamid=key) return mid; /*检索成功返回*/ if (l.datamidkey) high=mid-1; /*继续在前半部分进行二分检索*/ else low=mid+1; /*继续在后半部分进行二分检索*/ return -1; /* 当lowhigh时表示查找区间为空，检索失败*/ ,线性表,/*-二分查找的递归实现-*/ int binsearch2(seqlist l,datatype key,int low,in

10、t high) int mid,k; if (lowhigh) return -1; /*检索不成功的出口条件*/ else mid=(low+high)/2; /*二分*/ if (l.datamid=key) return mid; /*检索成功返回*/ if (key l.datamid) return else return ,binsearch2(l,key,low,mid-1);,binsearch2(l,key,mid+1,high);,/递归地在 前半部分检索,/递归地在 后半部分检索,线性表,搜索成功的情形 搜索不成功的情形,从有序表构造出的二叉搜索树(判定树),若设 n =

11、 2h-1，则描述对分搜索的二叉搜索树是高度为 h-1 的满二叉树。2h = n+1, h = log2(n+1)。 第0层结点有1个，搜索第0层结点要比较1次；第1层结点有2个，搜索第1层结点要比较2次；，,一、查找过程可用二叉树描述： 每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。 二、查找某关键字的比较次数： 为该结点在判定树上的层次数。 （1）找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。查找成功时比较的关键字个数最多不超过树的深度 d : d

12、= log2 n + 1 （2）查找不成功的过程就是走了一条从根结点到外部结点的路径。,线性表,ASLbins=,在假定每个结点的查找概率相同的情况下，二分检索的ASL为：,用数学归纳法容易证明：,ASLbins=,=,线性表,课堂练习9-1（任选一题）,1. 已知一个有序表( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a12中： （1）画出二叉搜索树(判定树); （2）根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数; （3）在等概率情况下，求查找成功时的平均查找长度。 2.对

13、有序表 -1, 0, 1, 3, 4, 6, 8, 10, 12 进行折半查找： （1）画出二叉搜索树(判定树); （2）求查找12需要比较的次数； （3）求等概率情况下搜索成功的平均搜索长度。 3. 假设在有序线性表a20上进行折半查找。 （1）画出二叉搜索树(判定树); （2）求平均查找长度。,树表,9.3 二叉排序树（BST）,二叉排序树(二叉查找树、二叉搜索树) 它或者是一棵空的二叉树，或者是具有下列性质的二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。,下列2种图形，是不是二叉排序树 ？,讨论：对左图中序遍历

14、后的结果是什么？,树表,1 2 3 4 5 6 7 8 9 10,/*/ /* 二叉排序树用的头文件 */ /* 文件名：bstree.h */ /*/ #include #include typedef int datatype; typedef struct node /*二叉排序树结点定义*/ datatype key; /*结点值*/ struct node *lchild,*rchild; /*左、右孩子指针*/ bsnode; typedef bsnode *bstree;,二叉排序树 存储结构定义,树表,1. 二叉排序树的查找,在二叉排序树中查找给定值k的过程是：, 若root是

15、空树，则查找失败； 若k rootdata，则查找成功；否则 若k rootdata，则在root的左子树上查找； 否则在root的右子树上查找。 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率就在于只需要查找二个子树之一。,树表,50,50,50,30,40,35,50,50,80,90,在二叉排序树中查找关键字值等于50,35,90,95,树表,/*/ /* 基于二叉排序树的检索算法 文件名：t_search.c */ /* 函数名：bssearch1()、bssearch2() */ /*/ /*-二叉排序树的非递归查找-*/ vo

16、id bssearch1(bstree t,datatype x, bstree *p,bstree *q) /* q返回待查结点x在二叉排序树中的地址， p返回待查结点x的父结点地址 */ *p=NULL; *q=t; while (*q) ,树表,if (x=(*q)-key) return; *p=*q; *q=(xkey)? (*q)-lchild:(*q)-rchild; return; ,/*-二叉排序树的递归查找-*/ bstree bssearch2(bstree t,datatype x) /*在二叉排序树t中查找关键字为x的结点，若找到则返回该结点的地址，否则返回NULL*

17、/ if (t=NULL | x=t-key) return t;,树表,if (xkey) return bssearch2(t-lchild,x); /*递归地在左子树中检索*/ else return bssearch2(t-rchild,x); /*递归地在右子树中检索*/ ,算法分析：,在二叉排序树上进行检索的方法与二分检索相似，和关键字的比较次数不会超过树的深度 。 因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。,树表,在最坏的情况下，含有n个结点的二叉排序树退化成一棵深度为n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序检索相同，即ASL=（n+1）/2。

18、在最好的情况下，二叉排序树形态比较匀称，对于含有n个结点的二叉排序树，其深度不超过log2n，此时的平均查找长度为O（log2n）。,（a） （b） 图9.4 两棵具有不同检索效率的二叉排序树,树表,例如，对于图9.4中的两棵二叉排序树，其深度分别是4和10，在检索失败的情况下，在这两棵树上的最大比较次数分别是4和10；在检索成功的情况下，若检索每个结点的概率相等，则对于图9.4（a）所示的二叉排序树其平均查找长度为： ASLa= = 对于图9.4（b）所示的二叉排序树其平均查找长度为： ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.5,树表,2. 二叉排序树的插入,分析：

19、二叉排序树的插入操作应该是在查找不成功时才进行。 若二叉排序树为空树，则新插入的结点为新的根结点； 否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,问题描述:在已存在的一个二叉排序树新插入一个结点。,树表,例：,插入值为98的结点,树表,/*/ /* 基于二叉排序树的结点插入算法 */ /* 文件名：t_insert.c 函数名：insertbstree() */ /*/ void insertbstree(bstree *t,datatype x) bstree f,p; p=*t; while (p) /*查找插入位置*/ if (x=p-key) return; /若

20、二叉排序树t中已有key，则无需插入 f=p; /* f用于保存新结点的最终插入位置 */ p=(xkey)? p-lchild:p-rchild; ,树表,p=(bstree) malloc(sizeof(bsnode); /*生成待插入的新结点*/ p-key=x; p-lchild=p-rchild=NULL; if (*t=NULL) *t=p; /*原树为空*/ else if (xkey) f-lchild=p; else f-rchild=p; 程序9.5 基于二叉排序树的结点的插入算法,树表,3. 二叉排序树的构造,输入序列：53,78,65,17,87,09,81,45,23

21、 左小右大,输入序列不同，则建立的二叉搜索树不同。,1,2,3、1,3,2、2,1,32,3,1、3,1,2、3,2,1,树表,建立二叉排序树的算法如下： /*/ /* 二叉排序树的建立算法 */ /* 文件名：t_creat.c 函数名：creatbstree() */ /*/ bstree creatbstree(void) /*根据输入的结点序列，建立一棵二叉排序树，并返回根结点的地址*/ bstree t=NULL; datatype key; printf(“n请输入一个以-1为结束标记的结点序列：n“);,树表,scanf(“%d“, /*返回建立的二叉排序树的根指针*/ 算法9.

22、6 生成一棵二叉排序树,树表,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列; 每次插入的新结点都是二叉排序树上新的叶子结点; 找到插入位置后，不必移动其它结点，仅需修改某个结点的指针； 在左子树/右子树的查找过程与在整棵树上查找过程相同； 新插入的结点没有破坏原有结点之间的关系。,二叉排序树小结,树表,课堂练习,4. 依次输入表 30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55 中的元素，生成一棵二叉搜索树。 试画出生成之后的二叉搜索树； 对该二叉搜索树进行中序遍历，试写出遍历序列。 假定每个元素的查找概率相等，试计算该二叉搜索树的平均查

23、找长度。,课堂练习（任选一题）,5. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 6. 画出依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树，并求出查找元素35要进行元素间的比较次数。,例：编制一个将百分制转换成五级分制的程序。 if(a60) b=“不及格”; else if(a70) b=“及格”; else if(a80) b=“中等”; else if(a90) b=“良好”; else b=“优良”;,哈夫曼树,哈夫曼树,9.5 哈夫曼树及哈夫曼编码,1. 哈夫曼

24、树相关概念,叶子结点的权值 对叶子结点赋予的一个有意义的数值量。,二叉树的带权路径长度 设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。,WPL=,Wk：第k个叶子结点的权值 lk：从根结点到第k个叶子结点的路径长度,哈夫曼树,哈夫曼树,哈夫曼树： 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树。,哈夫曼树,哈夫曼编码和译码,报文：abbcddabccdcdddddddd (a)010 011 011 00 1 1 010 011 00 00 1 00 11111111共34码 (b)00 01 01 10

25、11 11 00 01 10 10 11 10 11 11 11 11 11 11 11 11共40码, 初始化 由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn； 选取与合并 在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树根结点的权值为其左、右子树根结点的权值之和； 删除与加入 在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中； 重复、两步 当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,哈夫曼算法基本思想,哈夫曼树的构造过程,1 初始化,2 选取与合并,给出叶子结点的

26、权值集合为W=5,2,9,11, 8,3,7的哈夫曼树的构造过程。,哈夫曼树,3 删除与加入,4 重复2 、3 两步,哈夫曼树,4 重复2 、3 两步,哈夫曼树,4 重复2 、3 两步,哈夫曼树,4 重复2 、3 两步,哈夫曼树,哈夫曼树,散列表,9.7.1 概述,散列的基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。,散列技术:查找时是根据记录的存储位置和它的关键码之间建立的一个确定对应关系H来进行的查找。,散列函数：将关键码映射为散列表中适当存储位置的函数。,散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连

27、续的存储空间称为散列表。,散列地址：所得的存储位置。,散列存储：通过散列函数计算出存储地址。 例如：函数为 Loc(key)=asc(left(key,1) % 8,散列表,冲突： 对于两个不同关键码k1k2，有H(k1)H(k2)，即:两个不同的记录需要存放在同一个存储位置的现象。则:k1和k2相对于H称做同义词。,散列技术的关键问题： 散列函数的设计 如何设计一个简单、均匀、存储利用率高的散列函数。 冲突的处理 如何采取合适的处理冲突方法来解决冲突。,散列表,9.7.2 散列函数的设计,1. 直接定址法,直接定址法的散列函数是关键码的线性函数 。,即：H(key) = a key + b（

28、a，b为常数）,例：关键码集合为10, 30, 50, 70, 80, 90，选取 的散列函数为H(key)=key/10，则散列表为：,0 1 2 3 4 5 6 7 8 9,10,30,50,70,80,90,适用范围:,地址集合的大小=关键码集合的大小,散列表,2. 除留余数法,选择某个适当的正整数p，以关键码除以p的余数作为散列地址。,即：H(key)=key mod p,散列函数的设计成功与否关键在于选取合适 的p，若p选的不好，则容易产生同义词。,散列表,示例：有一个关键字 key = 962148，散列表大小 m = 25，取质数 p= 23。散列函数 hash ( key )

29、= key % p。则散列地址为： hash ( 962148 ) = 962148 % 23 = 12 可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时到达这些地址.,散列表,9.7.3 处理冲突的方法,1. 开放定址法,由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。,用开放定址法处理冲突得到的散列表叫闭散列表。,如何寻找下一个空的散列地址?,散列表,1) 线性探测法,是指当发生冲

30、突时，从冲突位置的下一个位置起，依次寻找空的散列地址。,对于键值key，设H(key)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为： Hi=(H(key)di) % m （di=1，2，m-1）,散列表,例：关键码集合为 47, 7, 29, 11, 16, 92, 22, 8, 3，散列表表长为11，散列函数为H(key)=key mod 11，用线性探测法处理冲突，则闭散列表为：,0 1 2 3 4 5 6 7 8 9,47,7,29,11,16,92,29,22,22,8,8,3,3,3,3,在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象称为堆积 。

31、,散列表,基于线性探测法构造的散列表的查找算法,散列表,基于线性探测法构造的散列表的查找伪代码,计算散列地址j; 2. 若htj为空，则将待查值插入相应位置,返回; 3. 若htj=k，则查找成功，返回记录在散列表中的下标； 否则j指向下一单元，直至htj为空,将待查值插入相应位置或htj=k,查找成功,返回记录在散列表中的下标.,散列表,int HashSearch1(int ht , int m, int k) j=H(k); if (htj=k) return j; /没有发生冲突，比较一次查找成功 i=(j+1) % m; while (hti!=Empty /查找不成功时插入 ,散列

32、表,2) 二次探测法,当发生冲突时，寻找下一个散列地址的公式为： Hi=(H(key)di)% m （di=12，12，22，22，q2，q2且qm/2）,0 1 2 3 4 5 6 7 8 9,47,7,29,11,16,92,29,22,22,8,8,3,3,3,例：关键码集合为 47, 7, 29, 11, 16, 92, 22, 8, 3，散列表表长为11，散列函数为H(key)=key mod 11，用线性探测法处理冲突，则闭散列表为：,散列表,3) 随机探测法,当发生冲突时，下一个散列地址的位移量是一个随机数列，即公式为： Hi=(H(key)+di)% m （di是一个随机数列，

33、i=1，2，m-1）,小结： 1. 开放地址法就是为产生冲突的地址，通过 Hi=( H(key) + di ) MOD m公式，求得一个地址序列： H0, H1, H2, , Hs （1sm-1）； 2. 增量di 应具有“完备性”，即产生的Hi 均不相同，且所产生的s个 Hi 值能覆盖散列表中所有地址； 3. 平方探测时的表长 m 必为形如 4j+3的素数； 4. 随机探测时的 m 和 di 没有公因子。,散列表,9.7.4 散列查找的性能分析,关键码比较取决于产生的冲突,而影响冲突产生的因素： 1)散列函数是否均匀; 2)处理冲突的方法; 3)散列表的装载因子 =表中填入的记录数/表的长度

34、,散列表,查找成功时,查找不成功时,ASL,处理冲突方法,几种不同处理冲突方法的平均查找长度,散列表,9.7.5 开散列表与闭散列表的比较,开散列表是用链接方法存储同义词，不产生堆积现象，且查找、插入和删除操作易于实现，但有结构性存储开销。 闭散列表存储效率较高，但容易产生堆积现象。实现删除操作时不能简单地将待删记录所在单元置空，仅当运行到一定阶段时，经过整体整理，才能真正删除有标记的单元。,散列表,对开散列表来说，需将给定值与同义词子表中各结点的码值进行比较； 对闭散列表来说，则需将给定值与后继散列地址序列中记录的码值进行比较。开散列表不产生堆积，其平均查找长度较短。开散列表中各同义词子表的

35、表长是动态变化的，无需事先确定表的容量；而闭散列表却必须事先估计容量。,课堂练习（任选一题）,7.设散列表为HT13，散列函数为H(key)=key%13，用闭散列法解决冲突，对下列关键码序列12，23，45，57，20，3，78，31，15，36造表。采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下查找成功的平均搜索长度和搜索不成功的平均搜索长度。 8.给定关键码序列( 11, 81, 23, 59,17,19, 68 )，散列表长度为11，散列函数为H(key) = ( 5 * key ) % 11，用二次探查法解决冲突，试画出插入所有关键码后得到的散列表，并计算查找成功与查找不成功时的平均搜索长度。 9.设散列表为HT17, 待插入关键码序列为 Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ，散列函数为H (key) = i 2，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。 (1)试画出相应的散列表； (2)计算等概率下搜索成功的平均搜索长度；,