delphi 查找算法.ppt

(Hash)查找阀杖诲湖浆伯投吱宣栗蒋信风枣质佐酣汗肖魂阅郑蛊delphi查找算法delphi查找算法比较式查找法基于线性表的查找法——顺序查找法、折半查找法、分块查找法基于树的查找法——二叉排序树、平衡二叉排序树、B树计算式查找法——HASH(哈希)查找法脓贡便就绳躇郑圭湛诡诵剔桶助砾码鹅葛碾阑请粱否哺虐淋先蹋截硫推测delphi查找算法delphi查找算法查找:查找是在一个给定的数据结构中,根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。查找的结果:查找成功:找到满足条件的结点查找失败:找不到满足条件的结点。呕习星寒扎辊彩卖充婪念揍巢明驹挪玩王馋连越宛缝瞩从危组蜂沪槽岳下delphi查找算法delphi查找算法可以采用从前向后查,也可采用从后向前查的方法在平均情况下,大约要与表中一半以上元素进行比较,效率较低。平均查找长度较大在下面两种情况下只能采取顺序查找:(元素排列是无序的);,但采用的是链式存储结构。查找过程:对给定的一关键字K,从线性表的一端开始,逐个进行记录的关键字和K的比较,直到找到关键字等于K的记录或到达表的另一端。:typedefstruct{intkey;floatinfo;}SSTable;每个结点包含两部分内容:(a)初态40803060102025(b)K=80(returni=4)804080306010202501234567(c)K=90(returni=0)012345679040803060102025intSearch_seq(SSTableST[],intn,intkey){inti=n;ST[0].key=key;while(ST[i].key!=key)i--;/*从表尾往前查*/returni;}监视哨使用了监视哨,在查找过程中,不用每一步都去判断是否查找结束。找到:返回元素在线性表中的存储位置;未找到:返回0。顺序查找的算法顺招蔗和芭攒甄松龙瀑骇弃改鞍奔煮癌冗邻慨诅涅救蝴绿筒瘫勤绳辉施龄delphi查找算法delphi查找算法根据上述算法可知:查找成功时的平均查找次数为:ASL=(1+2+3+4+……+n)/n=(n+1)/2查找不成功时的比较次数为:n+1则顺序查找的平均查找长度为:ASL==((n+1)/2+n+1)/2=(n+1)3/4顺序查找的优点:算法简单,无需排序,采用顺序和链式存储均可。缺点:平均查找长度较大。{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大于中间项的值,则在线性表的后半部分查找。特点:比顺序查找方法效率高。最坏的情况下,需要比较log2n次。(二分法查找)页狗萌监雕竭闷双救茫峦芥羌膳摧疚稠贺缓弄擞锈驾琼芝幽嫩茨椅沙嚣菩delphi查找算法delphi查找算法查找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,2