资源描述:
《【精品数据结构】查找2.ppt》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键,则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构第二章 数据结构与算法(续)2.7查找查找:查找是在一个给定的数据结构中,根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。查找的结果:查找成功:找到满足条件的结点查找失败:找不到满足条件的结点。·可以采用
2、从前向后查,也可采用从后向前查的方法。·在平均情况下,大约要与表中一半以上元素进行比较,效率较低。平均查找长度较大。·在下面两种情况下只能采取顺序查找:a.线性表为无序表(元素排列是无序的);b.即使是有序线性表,但采用的是链式存储结构。2.7.1顺序查找(线性查找)查找过程:对给定的一关键字K,从线性表的一端开始,逐个进行记录的关键字和K的比较,直到找到关键字等于K的记录或到达表的另一端。1.顺序查找(线性表在顺序存储结构下的顺序查找)数据结构:typedefstruct{intkey;floatinfo;}SSTable;每个结点包含两部分内容:Key和info其他信息0
3、1234567(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;}监视哨使用了监视哨,在查找过程中,不用每一步都去判断是否查找结束。找到:返回元素在线性表中的存储位置;未找到:返回0。根据上述算法可知:查
4、找成功时的平均查找次数为:ASL=(1+2+3+4+……+n)/n=(n+1)/2查找不成功时的比较次数为:n+1则顺序查找的平均查找长度为:ASL==((n+1)/2+n+1)/2=(n+1)3/4顺序查找的优点:算法简单,无需排序,采用顺序和链式存储均可。缺点:平均查找长度较大。2.线性表在链式存储结构下的顺序查找structnode{intdata;structnode*next;};intsearlb(structnode*h,intx){structnode*m;m=h;while(m->next!=NULL&&m->data!=x)m=m->next;return
5、(m);}2.7.2折半查找(二分法查找)思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止。前提:必须在具有顺序存储结构的有序表中进行。分三种情况:1)若中间项的值等于x,则说明已查到。2)若x小于中间项的值,则在线性表的前半部分查找;3)若x大于中间项的值,则在线性表的后半部分查找。特点:比顺序查找方法效率高。最坏的情况下,需要比较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)lowhighm
6、id(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)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid折半查找的c语言算法程序:intSearch_Bin(SSTableST[],intn,intkey){intlow,high,mid;low=1;high=n;while(
7、low<=high){mid=(low+high)/2;if(ST[mid].key==key)return(mid);/*查找成功*/elseif(key