查找与排序技术

《查找与排序技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、查找排序查找与排序技术查找查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。查找的结果：查找成功：找到满足条件的结点查找失败：找不到满足条件的结点。查找的基本概念关键字:是数据元素中可以唯一标识一个数据元素的数据项，比如学号、身份证号等。查找:是根据给定的关键值，在一组数据中确定一个其关键字等于给定值的数据元素的过程。确切定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个其关键字等于给定的K值的记录，如找到，则输出记录或记录在文件中的相对位置称查找成功；否则输出查找不

2、成功的信息称查找失败。查找方法1.顺序查找2.二分法查找3.分块查找4.散列（HASH）查找查找方式与特点：可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。在下面两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）；b.即使是有序线性表，但采用的是链式存储结构。顺序查找（线性查找）查找过程：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。1.线性表在顺序存储结构下的顺序查找数据结构：typedefstruct{

3、intkey;floatinfo;}SSTable;每个结点包含两部分内容：Key和info01234567（a）初态40803060102025(b)K=80(returni=4)804080306010202501234567(c)K=90(returni=0)012345679040803060102025顺序查找的算法：intSearch_seq(SSTableST[],intn,intkey){inti=n;ST[0].key=key;while(ST[i].key!=key)i--；/*从表尾往前查*/returni;}监视哨使用了监视哨，在查找过程中

4、，不用每一步都去判断是否查找结束。找到：返回元素在线性表中的存储位置；未找到：返回0。01234567（a）初态40803060102025(c)K=90(returni=0)012345679040803060102025根据上述算法可知：查找成功时的平均查找次数为：ASL=(1+2+3+4+……+n)/n=(n+1)/2查找不成功时的比较次数为：n+1则顺序查找的平均查找长度为：ASL=((n+1)/2+n+1)/2=(n+1)3/4顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。缺点：平均查找长度较大。2.线性表在链式存储结构下的顺序查找stru

5、ctnode{intdata;structnode*next;};intsearlb(structnode*h,intx){structnode*m;m=h;while(m->next!=NULL&&m->data!=x)m=m->next;return(m);}折半查找（二分法查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。查找过程：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找。3）若x大于中间项的值，则在线性表的后半部分查找。特点：比

6、顺序查找方法效率高。最坏的情况下，需要比较log2n次。查找23和79的过程如下图：mid=(low+high)/2（只舍不入）(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)l

7、owhighmid(08,14,23,37,46,55,68,79,91)lowhighmid折半查找的算法程序：intSearch_Bin(SSTableST[],intn,intkey){intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(ST[mid].key==key)return(mid);/*查找成功*/elseif(key

8、*查找不成