数据结构第九章

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

1、第九章查找9.1基本概念查找(search)：又称检索，是数据处理中经常使用的一种重要运算。查找定义：在含有几个结点的表R1,R2,……Rn中，给定一个K值，查找关键字K的结点，若找到则查找成功，给出其在表中的位置，否则失败，给出失败信息。相关问题：1.数据的存储形式（存储结构）。2.内查找——查找过程在内存进行。外查找——查找过程访问外存。3.衡量一个查找算法优劣标准——平均查找长度。平均查找长度：ASL=∑PiCi(i=1…n)n-----结点个数（记录数）Pi----第i个结点查找概率(平均1/n)Ci----第i个结点比较次数9.2线性表的

2、查找1.顺序查找基本思想：从表的一端，顺序扫描，依次和K比较，相等即找到，否则失败。该方法即适合顺序存储结构也适于链式存储结构。存储结构：typedefstruct{keytypekey;datatypeother;}table;算法:intSEQSEARCH(tableR[],keytypeK){inti=0;R[n].key=K;while(R[i].key!=K)i++;if(i==n)return-1;elsereturni}监视哨：R[n]的设置，省去判定条件中i<n，节省时间，若改为：for(i=0;i<n;

3、i++)if(R[i].key==K)returni;return(-1);则此算法效率低于设置监视哨。算法分析：ASL=∑PiCi=1/n(1+2+……+n)=(n+1)/2ASL’=∑PiCi=P1+2P2+……nPn若Pn<=Pn-1<=……<=p1则ASL’最小。若预先知道概率分布情况，应按概率大小存放以提高查找效率，一般情况概率并不清楚，可在每次查找成功，就将找到的结点和前趋交换使得经常查找的结点不断前移，便于在后续的查找过程中减少比较次数。优缺点：算法简单，对存贮结构无特别要求，但查找效率较低，

4、n较大时不宜采用。-13-2.二分查找（折半查找）二分查找效率较高，但要求向量存储结构并预先有序。基本思想：R[0]……R[n-1],每次用K与R[mind]比较相等则成功，否则若R[mind]key>K则在R[0]……R[mind-1]中找若R[mind]key<K则在R[mind-1]……R[n-1]中找如此进行下去……算法：intBINSEARCH(tableR[],keytypeK){intlow,mid,high;low=0;high=n-1;while(low<=high){mid=(low+h

5、igh)/2;if(K==R[mid].key)returnmid;if(K<R[mid].key)high=mid-1;elselow=mid+1;}return-1;}例图：查找K=21，K=85二叉判定树：将R[mind]作根，左子表右子表作为左子树右子树。例图：算法分析：设n=2h-1，h=log2(n+1)是满二叉树，nk=2k-1ASL=∑PiCi=1/n∑Ci=∑k*2k-1/n=((n+1)*log2(n+1)-1)/n≈log2(n+1)-1优缺点：效率较高，但要求有序且需数组作存储结构，二分查找特别适用于那种一经建

6、立就很少改动，而又经常查找的线性表，对那些查找少又经常改动的线性表，可采用链式存储结构进行顺序查找。3.分块查找（索引查找）将R[n]分成b块，前b-1块中结点个数S=n/b，最后