《数据结构教程》第八章查找

《《数据结构教程》第八章查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章绪论第二章线性表第三章稀疏矩阵和广义表第四章栈和队列第五章树和二叉树第六章二叉树的应用第七章图第八章查找第九章排序第八章查找8.1对查找的操作：1）查询(检索)某个“特定的”数据元素是否在查找表中及各种属性；2）在查找表中插入一个数据元素；3）从查找表中删去某个数据元素。1.顺序查找2.二分查找3.索引顺序8.2静态查找表顺序搜索的平均搜索长度设搜索第i个元素的概率为pi，搜索到第i个元素所需比较次数为ci，则搜索成功的平均搜索长度:在顺序搜索情形，ci=i+1,i=0,1,,n-1，因此在等概率情形，pi

2、=1/n,i=0,1,,n-1。1.顺序查找顺序查找算法Strucelemtype{eneytypedata;keytypekey;}Intseqserch(elemtypea[],intn,keytypek){a[n].key=k;for(inti=0;;i++)if(a[i].key==k)break;If(i

3、ch(elemtypea[],intlow,inthiht,keytypek){if(low<=high){intmid=(low+high)/2;if(k==a[mid].key)returnmid;elseif(k

4、h=n+1,h=log2(n+1)。第0层结点有1个，搜索第0层结点要比较1次；第1层结点有2个，搜索第1层结点要比较2次；…，顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。总结：有序查找表若以有序表表示静态查找表，则查找过程可以基于“折半”进行。5.3索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。索引可以根据查找表的特点来构造。索引顺序查找的过程也是一个“缩小区间”的查找过程。一、索引顺序查找的数据结构：Structindexitem{indexkeyt

5、ypeindex;intstart;intlength;}职工号姓名JS001JS002JS003JS004DZ001DZ002DZ003JJ001JJ002HG001HG002HG003主表Js04Dz43Jj72hg930123Indexstartlengh索引表二、分块查找：在索引表为稀疏索引152618343672405743869398347298051045301201234567891011121314IndexStartlengh索引表主表注：同一块中的数据没有排序8.4散列查找动态查找表一、散列的概念散列

6、：通过对表中的每个元素关健字K为自变量的H(Ｋ)计算出一值作为一连续存储空间的位置,并将该元素存储到这个单元中.此Ｈ函数称散列函数或哈希函数.Ｈ(Ｋ)称散列地址或哈希地址,上述的存储空间称散列表或哈希表.例:A=(18,75,60,43,54,90,46)h(k)=k%m:m为散列表的长度=1343186075Ｈ0123456789101112549046同义词冲突:70下一页冲突引起冲突的三个原因:一、装填因子:α=n/m二、与散函数有关三、与解决的方法有关1.直接定址法3.数字分析法5.折叠法4.平方取中法2.除留余数

7、法二、对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进行数字化处理。1.直接定址法:h(k)=k+c3.数字分析法:(92326875,92343634,92774638,92381262,92394220)5.折叠法：k=68242324,散列分三段682，423，240，叠加和：1345，其散列地址为：3454.平方取中法:322取中三位10242.除留余数法:h(k)=k%m三、处理冲突的方法“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法18123456782627非同义词

8、冲突线性探查法2.链接法∧∧∧∧∧0123456789101112B＝(18,75,60,43,54,90,46,31,58,73,15,34)H(k)=k%131554∧43∧3158∧46∧3475∧18∧7360∧90∧8.5B-树查找1．定义2．查找过程3．插入操作4．查找性能的分析动态查找表在