1、顺序查找:(有两种方法)
在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。
①、让关键字与队列中的值从
第一个开始逐个比较,直到找出与给定关键字相同的值为止。
int SeqSearch(Seqlist R,KeyType K)
{
//在顺序表R[1..n]中顺序查找关键字为K的结点,
//成功时返回找到的结点位置,失败时返回-1
int i;
for(i=0;i<R.len;i++)
{
if(R[i].key==K) return i;
}
return -1;
} //SeqSearch②、从表中最后一个记录开始,逐个进行与关键字比较。直至第一个值,elem[0]=key,为设置“哨兵”。找不到返回0
int SeqSearch(Seqlist R,KeyType K)
{
//在顺序表R[1..n]中顺序查找关键字为K的结点,
//成功时返回找到的结点位置,失败时返回0
int i;
R[0].key=K; //设置哨兵
for(i=R.len;R[i].key!=K;i--); //从表后往前找
return i; //若i为0,表示查找失败,否则R[i]是要找的结点
} //SeqSearch比较:
成功时的顺序查找的平均查找长度:
在等概率情况下,pi=1/n(1≤i≤n),故成功的平均查找长度为
(n+…+2+1)/n=(n+1)/2
即查找成功时的平均比较次数约为表长的一半。
若K值不在表中,则须进行n+1次比较之后才能确定查找失败。
2、折半查找:(二分法查找)(必须有序)
①、假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;
②、若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。
int search(int *a,int key,int low,int high)
{
int mid;
mid = (low + high)/2;
while(low<high)
{
if(a[mid] == key) return mid;
else
if (a[mid]>key) high=mid;
else low=mid;
mid = (low + high)/2;
}//while
return -1; //没有找到
}//search
用递归思想:
int search(int *a,int key,int low,int high)
{
int mid;
if(low > high)
return -1;
mid = (low + high)/2;
if(a[mid] == key) return mid;
else if(a[mid] > key) return search(a,key,low,mid -1);
else return search(a,key,mid + 1,high);
}
3、
/////////////////////待续...
posted on 2011-10-03 11:00
Yu_ 阅读(1069)
评论(0) 编辑 收藏 引用 所属分类:
数据结构