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_ 閱讀(1081)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構