delphi 查找算法（精选）.ppt

第七章查找
顺序查找
折半查找
分块查找
基于树的查找法
哈希(Hash)查找
比较式查找法
基于线性表的查找法
——顺序查找法、折半查找法、分块查找法
基于树的查找法
——二叉排序树、平衡二叉排序树、B树
计算式查找法——HASH(哈希)查找法
查找:查找是在一个给定的数据结构中,根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。
查找的结果:
查找成功:找到满足条件的结点
查找失败:找不到满足条件的结点。
可以采用从前向后查,也可采用从后向前查的方法
在平均情况下,大约要与表中一半以上元素进行比较,效率较低。平均查找长度较大
在下面两种情况下只能采取顺序查找:
a. 线性表为无序表(元素排列是无序的);
b. 即使是有序线性表,但采用的是链式存储结构。
查找过程:
对给定的一关键字K,从线性表的一端开始,逐个进行记录的关键字和K的比较,直到找到关键字等于K的记录或到达表的另一端。
顺序查找
线性表在顺序存储结构下的顺序查找
数据结构:
typedef struct{
int key;
float info;
}SSTable;
每个结点包含两部分内容:Key 和info
其他信息
顺序查找
0 1 2 3 4 5 6 7
(a) 初态
40
80
30
60
10
20
25
(b) K=80
(return i=4)
80
40
80
30
60
10
20
25
0 1 2 3 4 5 6 7
(c) K=90
(return i=0 )
0 1 2 3 4 5 6 7
90
40
80
30
60
10
20
25
int Search_seq(SSTable ST[ ], int n, int key)
{ int i=n;
ST[0].key=key;
while(ST[i].key!=key) i- -; /*从表尾往前查*/
return i;
}
监视哨
使用了监视哨,在查找过程中,不用每一步都去判断是否查找结束。
找到:返回元素在线性表中的存储位置;
未找到:返回0。
顺序查找的算法
根据上述算法可知:
查找成功时的平均查找次数为:
ASL=(1+2+3+4+……+n)/n=(n+1)/2
查找不成功时的比较次数为: n+1
则顺序查找的平均查找长度为:
ASL==((n+1)/2+n+1)/2=(n+1)3/4
顺序查找的优点:算法简单,无需排序,采用顺序和链式存储均可。
缺点:平均查找长度较大。
顺序查找
线性表在链式存储结构下的顺序查找
struct node
{ int data;
struct node *next;};
int searlb(struct node *h,int x)
{
struct node *m;
m=h;
while (m->next!=NULL&&m->data!=x) m=m->next;
return(m);
}
顺序查找
思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止。
前提:必须在具有顺序存储结构的有序表中进行。
分三种情况:
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 )
low
high
mid
( 08, 14, 23, 37, 46, 55, 68, 79, 91 )
low
high=mid-1
mid
( 08, 14, 23, 37, 46, 55, 68, 79, 91 )
low=mid+1
high
mid
( 08, 14, 23, 37, 46, 55, 68, 79, 91 )
low
high
mid
( 08, 14, 23, 37, 46, 55, 68, 79, 91 )
low
high
mid
( 08, 14, 23, 37, 46, 55, 68, 79, 91 )
low
high
mid