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

1、實(shí)驗(yàn)十二實(shí)現(xiàn)順序和二分查找算法姓名：張就 班級(jí)：09計(jì)算機(jī)一班學(xué)號(hào)：2009111111一、實(shí)驗(yàn)?zāi)康恼莆枕樞蚝投植檎宜惴ǖ幕舅枷爰捌鋵?shí)現(xiàn)方法。二、實(shí)驗(yàn)內(nèi)容對(duì)給定的任意數(shù)組(設(shè)其長(zhǎng)度為n),分別用順序和二分查找方法 在此數(shù)組中查找與給定值k相等的元素。三、算法思想與算法描述1、 順序查找，在順序表R0.n-1中查找關(guān)鍵字為k的記錄，成功時(shí)返回找到的記錄位置，失敗時(shí)返回-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中進(jìn)行二分查找，成功時(shí)返回記錄 的位置，失敗時(shí)返回-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;)四、實(shí)驗(yàn)步驟與算法實(shí)現(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");五、實(shí)驗(yàn)測(cè)試及結(jié)果153426元素&的位置是5程序完全正確的執(zhí)行結(jié)

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