计算机软件技术基础 第6章 查找和排序.ppt

《计算机软件技术基础 第6章 查找和排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、查找和排序自动化与电气工程学院沈捷查找基本概念查找表:由同一类数据构成的用于查找的集合被称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字等于K的记录，如找到则成功，否则查找失败。静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容

2、。它所对应的查找算法属于动态查找技术。动态查找的例子——词汇统计问题。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。平均查找长度：为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为：n为表长；Pi为查找第i个元素的概率。Ci为找到该记录时，和给定值比较过的数据元素的个数。在等概率条件下（Pi=1/n）这

3、时平均查找长度为：其中：静态查找技术假设静态顺序查找表的存储结构为：structSSTable{ElemType*data;//存储空间地址intlength;//表的长度};顺序查找表的元素存放在data[0]至data[length-1]中。顺序查找的方法是从表的一端开始，逐一比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。1顺序查找ElemTypedata[length];intlength;intSqSearch(ElemTypedata[length],KeyTypekey){i

4、ntk=0;while(k

5、在length号单元停止，这样就不必在每一次循环中都判别是否数组出界。intSqSearch(data[length+1],KeyTypekey){data[length+1]=key;//监视哨intk=0;while(data[k]!=key)k++;if(k

6、。如果顺序查找表的元素按照关键字的值有序存放，那么可利用高效的对分查找来完成查询。假定元素按关键字的值升序排列，折半查找的思路是将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功；若前者小于后者则在中间位置左边的元素中继续查找；若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。2对分查找（折半或二分）对分查找算法的步骤描述如下：①设置查找区间初值，设下界low=0，设上界high=length-1。②若low≤high则计算中间位置mid=(low+high)/2

7、。③若keydata[mid]，则设low=mid+1并继续执行步骤②；若key=data[mid]则查找成功，返回目标元素位置mid+1（位置从1计数）。④若当low>high时，则查找失败，返回0。intBinSearch(data[length-1],KeyTypekey){intlow,high,mid;low=0;high=length-1;//设置查找区间初值while(low<=high){mid=(low+high)/2;if(key==data[mid])returnmi

8、d+1;//查找成功el