試驗十二實現(xiàn)順序和二分查找算法

1、實驗十二實現(xiàn)順序和二分查找算法姓名：張就 班級：09計算機一班學號：2009111111一、實驗目的掌握順序和二分查找算法的基本思想及其實現(xiàn)方法。二、實驗內(nèi)容對給定的任意數(shù)組(設其長度為n),分別用順序和二分查找方法 在此數(shù)組中查找與給定值k相等的元素。三、算法思想與算法描述1、 順序查找，在順序表R0.n-1中查找關鍵字為k的記錄，成功時返回找到的記錄位置，失敗時返回-1 ,具體的算法如下所示：int SeqSearch(SeqList R, int n,KeyType k)(int i=0;while (i<n&&Ri.key!=k)(printf( "%d

2、”,Ri.key);i+;if (i>=n)return -1;else(printf( "%d”,Ri.key);return i;2、 二分查找，在有序表R0.n-1中進行二分查找，成功時返回記錄 的位置，失敗時返回-1 ,具體的算法如下：int BinSearch(SeqList R, int n,KeyType k)(int low=0,high=n-1,mid,count=0;while (low<=high)(mid=(low+high)/2;printf("第欷查找：在%d ,%d中找到元素 R%d:%dn "，+count,low,hi

3、gh,mid,Rmid.key);if (Rmid.key=k)return mid;if (Rmid.key>k)high=mid-1;elselow=mid+1;)return -1;)四、實驗步驟與算法實現(xiàn)#include <stdio.h>#define MAXL 100typedef int KeyType;typedef char InforType10;typedef struct(KeyType key;InforType data;)NodeType;typedef NodeType SeqListMAXL;int SeqSearch(SeqList R,

4、int n,KeyType k)(int i=0;while (i<n&&Ri.key!=k)(printf( "%d”,Ri.key);i+;)if (i>=n) return -1;else(printf( "%d”,Ri.key);return i;)int BinSearch(SeqList R, int n,KeyType k)(int low=0,high=n-1,mid,count=0;while (low<=high)(mid=(low+high)/2;printf("第欷查找：在%d ,%d中找到元素 R%d:%

5、dn "，+count,low,high,mid,Rmid.key);if (Rmid.key=k)return mid;if (Rmid.key>k)high=mid-1;elselow=mid+1;)return -1;)int BinSearch1(SeqList R,KeyType k, int low, int high)(int mid;if (low>high)return -1;mid=(low+high)/2;if (k=Rmid.key)return mid;else if (k<Rmid.key)return BinSearch1(R,k,lo

6、w,mid-1);elsereturn BinSearch1(R,k,mid+1,high);)void main()(SeqList R;int n=10;KeyType k=7;int a=1,5,3,4,2,6,7,11,9,10,i;for (i=0;i<n;i+)Ri.key=ai;printf( "n" );if (i=SeqSearch(R,n,k)!=-1)printf( "n 元素由勺位置是 %dn",k,i);elseprintf( "n元素由勺位置不在表中n” ,k);printf( "n" );

7、if (i=BinSearch(R,n,k)!=-1)printf( "n 元素由勺位置是 %dn",k,i);elseprintf( "n元素由勺位置不在表中n" ,k);printf( "n");if (i=BinSearch1(R,k,0,7)!=-1)printf( "n 元素由勺位置是 %dn",k,i);elseprintf( "n元素由勺位置不在表中n" ,k);printf( "n");五、實驗測試及結果153426元素&的位置是5程序完全正確的執(zhí)行結

8、果，如圖所示:在0 ,9】中找到元素I在5中找到I在5中找到元素Rrsnfi元素6的位置是5元素6的位置是S請按任意鍵繼續(xù)六、總結與體會通過這次在實現(xiàn)順序和二分查找算法 的過程中，讓我對順序和二分查找算法有了更多的了解。查找根據(jù)給定的某個值，在查找表中確 定一個其關鍵字等于給定值的數(shù)據(jù)元素或（記錄）的操作，應用十分廣彳之。順序查找是一種最簡單的查找方法。它的基本思路是：從表的一端開始，順序掃描線性表，依次將掃描到的關鍵字和給定值 k相比較, 若當前掃描到的關鍵字與 k相等，則查找成功；若掃描結束后，仍未找 到關鍵字等于k的記錄，則查找失敗。二分查找也稱為折半查找要求它首先用線性表中的結點必須己按關鍵字值的遞增或遞減順序排列 要查找的關鍵字k與中間位置的結點的關鍵字相比較