《数据结构教程》第八章查找.ppt
数据结构,第一章 绪论第二章 线性表第三章 稀疏矩阵和广义表第四章 栈和队列第五章 树和二叉树第六章 二叉树的应用第七章 图第八章 查找第九章 排序,第八章 查找,8.1 对查找的操作：1）查询(检索)某个“特定的”数 据元素是否在查找表中及各 种属性；2）在查找表中插入一个数据元素；3）从查找表中删去某个数据元素。,1.顺序查找,2.二分查找,3.索引顺序,8.2 静态查找表,顺序搜索的平均搜索长度,设搜索第 i 个元素的概率为 pi，搜索到第 i 个元素所需比较次数为 ci，则搜索成功的平均搜索长度:,在顺序搜索情形，ci=i+1,i=0,1,n-1，因此,在等概率情形，pi=1/n,i=0,1,n-1。,1.顺序查找,顺序查找算法,Struc elemtypeeneytype data;keytype key;Int seqserch(elemtype a,int n,keytype k)an.key=k;for(int i=0;i+)if(ai.key=k)break;If(in)return IElse return-1;,2.二分查找条件：表已排序思想：第一步把表一分为二；判定查找的元素落在哪部分；依据上述步骤重复直到最后找到（或对半结束查找不成功）,算法下一页,Int binserch(elemtype a,int low,int hiht,keytype k)if(low=high)int mid=(low+high)/2;if(k=amid.key)return mid;else if(kamid.key)return binserch(a,low,mid-1,k);else return binserch(a,mid,high-1,k)return-1;,下一页图示,搜索成功的例子 搜索失败的例子,下一页判定树,搜索成功的情形 搜索不成功的情形,从有序表构造出的二叉搜索树(判定树),若设 n=2h-1，2h=n+1,h=log2(n+1)。第0层结点有1个，搜索第0层结点要比较1次；第1层结点有2个，搜索第1层结点要比较2次；，,顺序查找表的查找算法简单，但 平均查找长度较大，特别不适用于 表长较大的查找表。,总结：有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,5.3 索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,索引可以根据查找表的特点来构造。,索引顺序查找的过程也是一个“缩小区间”的查找过程。,一、索引顺序查找的数据结构：Struct indexitemindexkeytype index;int start;int length;,主表,0123,Index start lengh,索引表,二、分块查找：在索引表为稀疏索引,0 1 2,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,IndexStartlengh,索引表,主表,注：同一块中的数据没有排序,8.4 散 列 查 找,动态查找表,一、散列的概念散列：通过对表中的每个元素关健字K为自变量的H()计算出一值作为一连续存储空间的位置,并将该元素存储到这个单元中.此函数称散列函数或哈希函数.()称散列地址或哈希地址,上述的存储空间称散列表或哈希表.,例:A=(18,75,60,43,54,90,46)h(k)=k%m:m为散列表的长度=13,0 1 2 3 4 5 6 7 8 9 10 11 12,54,90,46,同义词冲突:70,下一页冲突,引起冲突的三个原因:一、装填因子:=n/m 二、与散函数有关三、与解决的方法有关,1.直接定址法,3.数字分析法,5.折叠法,4.平方取中法,2.除留余数法,二、对数字的关键字可有下列构造方法：,若是非数字关键字，则需先对其进行数字化处理。,1.直接定址法:h(k)=k+c,3.数字分析法:(92326875,92343634,92774638,92381262,92394220),5.折叠法：k=68242324,散列分三段682，423，240，叠加和：1345，其散列地址为：345,4.平方取中法:322 取中三位1024,2.除留余数法:h(k)=k%m,三、处理冲突的方法,“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。,1.开放定址法,1 2 3 4 5 6 7 8,26,27,非同义词冲突,线性探查法,2.链接法,0 1 2 3 4 5 6 7 8 9 10 11 12,B(18,75,60,43,54,90,46,31,58,73,15,34)H(k)=k%13,8.5 B-树查找,1定义,2查找过程,3插入操作,4查找性能的分析,动态查找表,在 m 阶的B-树上，每个非终端结点 可能含有：n 个关键字 Ki（1 in）nm 或 n 个指向记录的指针 Di（1in）n+1 个指向子树的指针 Ai（0in）,多叉树的特性,a,mt,b,c,d,e,f,g,h,非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn；Ai-1 所指子树上所有关键字均小于Ki；Ai 所指子树上所有关键字均大于Ki；,查找树的特性,平衡树的特性,树中所有叶子结点均不带信息，且在树中的同一层次上；根结点或为叶子结点，或至少含有两棵子树；其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树；,B-树的定义,B-树是一种 平衡 的 多路 查找 树：,root,50,15 71 84,3 8 20 26 43 56 62 78,89 96,
