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_ 阅读(1044)
评论(0) 编辑 收藏 引用 所属分类:
数据结构