ch4_1查找2中国石油大学 {华东} 软件设计基础

《ch4_1查找2中国石油大学 {华东} 软件设计基础》由会员分享，可在线阅读，更多相关《ch4_1查找2中国石油大学 {华东} 软件设计基础（53页珍藏版）》请在金锄头文库上搜索。

1、1,4.1 查找,4.1.1 查找的基本概念 4.1.2 线性表的查找 4.1.3 二叉排序树查找 4.1.4 哈希表及其查找 4.1.5 查找小结,表中一行为一条记录，即一个数据元素,数据项,组合项,主关键字,次关键字,3,4.1.1 查找的基本概念, 数据项 具有独立含义的标识单位，是数据不可分割的最小单位。如“学号” “姓名”。 也称为字段或项。 组合项 由若干项组合构成，表中“出生日期”就是组合项，它由“年”、“月”、“日”三项组成。 关键字 关键字是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。 1)主关键字：能唯一标识一个记录的关键字。如“学号” 2)次关

2、键字：不能唯一标识一个记录的关键字。如“姓名”,4,查找表 是由具有同一类型的记录组成的集合。 分为静态查找表和动态查找表两类。 1)静态查找表：仅对查找表进行查找操作，而不能改变的表； 2)动态查找表： 除可进行查找操作外，还可进行向表中插入，或删除记录的表。 查找 给定一个值K，在查找表中进行搜索，寻找关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。也称为检索。,4.1.1 查找的基本概念,5,查找方法评价 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需进行的关键字比较次数的期望值叫查找算法的,4.1.1 查找的基本概念,

3、其中：n是表中记录的个数； Pi是查找第i个记录的查找概率，通常我们认为每个记录的查找概率相等，即 Pi=1/n； Ci是找到第i个记录时所经历的比较次数。,6,4.1.2 线性表的查找,1. 顺序查找 2. 折半查找 3. 分块查找,7,线性表查找的存储结构：顺序存储结构 数据结构： typedef struct int key; float info; SSTable;,每个结点包含两部分内容：Key 和info,其他信息,8,1、 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方

4、法。 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。,9,int Search_seq(SSTable ST , int n, int key) int i=n; while( i=1 ,需要不断判断查找是否结束,顺序查找的算法：,10,改进的顺序查找的算法：,int Search_seq(SSTable ST , int n, int key) int i=n; ST0.key=key; while( STi.key!=key ) i- -; /从表尾往前查 return i; ,监视哨,使用了监视哨，在查找过

5、程中，不用每一步都去判断是否查找结束。 找到：返回元素在线性表中的存储位置； 未找到：返回0。,(return i=4),11,1、 顺序查找 算法描述,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第i个元素： n-i+1 查找第1个元素： n 查找失败： n+1,12,顺序查找方法的ASL,顺序查找 优点：算法简单,无需排序,线性表采用顺序和链式存储均可。 缺点：平均查找长度较大。,在平均情况下，大约要与表中一半以上元素进行比较,13,2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长

6、为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值 初始时，令low=1, high=n, mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key，查找成功 若krmid.key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败,14,折半查找 算法描述,15,int Search_Bin( SSTable ST , int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if( STmid.key=

7、= key ) return mid; /*查找成功*/ else if( key STmid.key) high=mid-1; /*在前半区间继续查找*/ else low=mid+1; /*在后半区间继续查找*/ return (0); /*查找不成功*/ ,折半查找的C程序,16,折半查找,17,二叉判定树,从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表, 对定位到的子表继续这种操作。所以对表中每个数据元素的查找过程可用二叉树来描述，称这个描述查找过程的二叉树为判定树,lowhigh 查找失败,18,算法评价 有n个结点的判定树的深度为log2n+1 折半查找法在查找

8、过程中进行的比较次数最多不超过其判定树的深度 折半查找的ASL,折半查找,时间复杂度T(n)=O(log2n),19,3 分块查找（索引顺序查找） 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 算法描述,20,查找38,分块查找,分块查找方法评价,当s取n1/2时，ASLbs最小，为n1/2+1,(b = n / s),22,分块查找,块的大小 在实际应用中，分块查找不一定要将线性表分成大小相等的若干块，可根据

9、表的特征进行分块。 结点的存储结构 各块可放在不同的向量中，也可将每一块存放在一个单链表中。 分块查找的优点 在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。 因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。 分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。,线性查找方法比较,24,二叉判定树,从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表, 对定位到的子表继续这种操作。所以对表中每个数据元素的查找过程可用二叉树来描述，称这个描述查找过程的二叉树为判定树,25,二叉排序树 定义：二叉排序树或是一棵

10、空树，或是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树,4.1.3 利用二叉排序树进行查找,26,二叉排序树的概念,一棵二叉排序树,在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列，即 2，3，3，7，8，10，12，18 ,27,二叉排序树的查找：,1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于或等于根结点的关键字，则继续在右子树上进行查找。,否则，,若二叉排序树为空，

11、则查找不成功；,28,二叉排序树的构造,二叉排序树生成： 二叉排序树是一种动态树表。树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。 新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。 从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。,29, 10、18、3、8、12、2、7、3 ,10,10,18,3,8,12,2,7,3,二叉排序树的插入算法,Crstbitr.c,30,50,30,80,20,90,85,40,35,88,32,二叉排序树查找,查找关键字,= 50 ,

12、50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,31,从上述二叉排序树的查找过程可见，,在查找过程中，生成了一条查找路径：,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,32,在指针t 所指向的二叉排序树中查找关键字值为K的结点 #define M 100 typedef struct node int key; struct node L, R;JD JD pxscz(JD t, int K) JD p; if(t!=NULL) p=t; w

13、hile(p!=NULL) printf(“key= %dn”,p-key); if(p-key=k) return (p); else if(p-keyk) p=p-L; else p=p-R; return(NULL); ,利用二叉排序树查找,Pixusucz.c,33,二叉排序树查找性能的分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值 显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。,34,由关键字序列 1，2，3，4，5构造而得的二叉排序树，,例如：,ASL =（1+2+3+4+5）/ 5

14、= 3,最差的情况，二叉排序树退化为单支树， 平均查找长度为(n+1)/2,由关键字序列 3，1，2，5，4构造而得的二叉排序树，,ASL =（1+2+3+2+3）/ 5 = 2.2,35,二叉判定树,最好的情况是二叉排序树的形态和折半查找的判定树 相同，其平均查找长度和log2n成正比。,36,二叉排序树查找性能的分析,可以证明，平均情况下，二叉排序树的平均查找长度和logn是等数量级的。 当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作； 若有序表里动态查找表，则应选择二叉排序树作为其存储结构。,37,哈希函数可写成：addr(ai)=H(ki) ai是表中的一

15、个元素 addr(ai)是ai的存储地址 ki是ai的关键字,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫 哈希查找又叫散列查找，利用哈希函数进行查找的过程叫,4.1.4 哈希查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。 定义 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象,38,以编号作关键字，构造哈希函数：H(key)=key H(1)=1 H(2)=2,以地区别作关键字，取地区 名称第一

16、个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,从上例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫 同义词：具有相同函数值的两个关键字，叫该哈希函数的 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法。,39, 有关问题： 哈希查找是对给定的关键字按哈希函数直接求得记录位置的，不需进行比较关键字。 为提高查找效率，哈希表的空间m要比记录个数n大，定义 =n