數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 二分查找

1、課程題目：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 學(xué)院： 班級(jí)： 姓名： 學(xué)號(hào)：實(shí)驗(yàn)題目：查找的應(yīng)用實(shí)驗(yàn)內(nèi)容：二分查找實(shí)驗(yàn)?zāi)康模赫莆詹檎曳ǖ墓ぷ髟砑皯?yīng)用過(guò)程，利用其工作原理完成上述實(shí)驗(yàn)題目中的內(nèi)容。實(shí)驗(yàn)要求：為了使學(xué)生更好的掌握與理解課堂上老師所講的概念與原理，實(shí)驗(yàn)前每個(gè)學(xué)生要認(rèn)真預(yù)習(xí)所做的實(shí)驗(yàn)內(nèi)容及編寫(xiě)源程序偽碼(寫(xiě)在紙上及盤(pán)中均可) 以便在實(shí)驗(yàn)課中完成老師所布置的實(shí)驗(yàn)內(nèi)容。實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)設(shè)計(jì)原理：二分查找（Binary Search) 又稱(chēng)折半查找，它是一種效率比較高的查找方法。但是，這種查找方法的前提是： “已經(jīng)排序好的線(xiàn)性表”。我們的一維數(shù)組就是線(xiàn)性表。一位數(shù)組中的成員數(shù)據(jù)必須已經(jīng)排序好了，才能用二分法來(lái)進(jìn)

2、行查找操作。排序可以是升序，也可是降序。二分查找法也是一種通過(guò)關(guān)鍵字比較的查找方法。他的原理就是用關(guān)鍵字與被查找數(shù)據(jù)集（如一維數(shù)組）的中間位置（以下均是指下標(biāo)）的數(shù)據(jù)比較。我們假設(shè)有一個(gè)20個(gè)數(shù)據(jù)的一位數(shù)組，升序。a1,a2,a3,.,a20 我們要查找的數(shù)據(jù)值為Key 。中間位置的計(jì)算方法為：mid（首+尾）/2的底。“首”是指第一個(gè)數(shù)組成員的下標(biāo)數(shù)組成員的下標(biāo)值，“尾”在易語(yǔ)言自然是 命令“取數(shù)組成員數(shù) (數(shù)組)”的值?！暗住毕喈?dāng)于易語(yǔ)言中的“取整”命令 如本例 mid（1+20）/210.5 取底 mid10 則首先 Key與數(shù)組的第10個(gè)成員進(jìn)行比較。如果Key>a10,那么我們

3、要找的數(shù)據(jù)就可能在數(shù)組的第11到20成員之間，反之，Key<a10，我們要找的數(shù)據(jù)就可能在數(shù)組的1到9之間。這樣就確定了定了新的尋找范圍。重復(fù)以上步驟，直到尋找結(jié)束。最后的結(jié)果是：找到 | 未找到。詳細(xì)程序清單及注釋說(shuō)明：#include <stdio.h>#include <conio.h>#include <malloc.h>#include <stdlib.h>#define LIST_INIT_SIZE100 /線(xiàn)性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT10 /線(xiàn)性表存儲(chǔ)空間的分配增量typedefstru

4、ctint *elem; /存儲(chǔ)空間基址intlength; /當(dāng)前長(zhǎng)度intlistsize; /當(dāng)前分配的存儲(chǔ)空間(以sizeof(ElemType)為單位)Sqlist;void initlist_sq(Sqlist &l)l.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); l.length=0; /空表長(zhǎng)度為0l.listsize=LIST_INIT_SIZE; /初始存儲(chǔ)容量void amount(Sqlist &l)/輸入數(shù)組長(zhǎng)度以及每個(gè)數(shù)組元素的值int a,b,c;loop:printf("請(qǐng)輸入數(shù)字的個(gè)數(shù)

5、：");scanf("%d",&b);if(b<=0)printf("輸入錯(cuò)誤!請(qǐng)重新輸入!n");goto loop;printf("n");l.length=l.length+b; /確定表長(zhǎng)printf("請(qǐng)輸入數(shù)組元素!n");for(a=1;a<=l.length;a+)printf("輸入第%d個(gè)數(shù):",a);printf("n");scanf("%d",&c);l.elema=c;void order(S

6、qlist &l) /按照冒泡排序法為數(shù)組中的元素排序(升序)int i,j,k; for(i=1;i<=l.length;i+) for(j=1;j<=l.length-i;j+)if(l.elemj>l.elemj+1)k=l.elemj;l.elemj=l.elemj+1;l.elemj+1=k;void output(Sqlist &l)/將排序后的數(shù)組元素輸出printf("經(jīng)排序后的數(shù)組元素:");for(int i=1;i<=l.length;i+)printf("%d",l.elemi);print

7、f(" ");printf("n");int Search_Bin(Sqlist l,intkey)int low=1; /置區(qū)間初值int high=l.length; /置區(qū)間初值int mid;while(low<=high)mid=(low+high)/2;if(key=l.elemmid) return mid; /找到待查元素else if(key<l.elemmid) high=mid-1; / Key<l.elemmid,繼續(xù)在前半?yún)^(qū)間進(jìn)行查找else low=mid+1; /Key>l.elemmid,繼續(xù)在后半

8、區(qū)間進(jìn)行查找return 0; /順序表中不存在待查元素main()int m,n,v;Sqlist l; initlist_sq(l);amount(l);order(l);output(l);loop1:printf("請(qǐng)輸入要查找的元素:"); scanf("%d",&m);printf("n");n=Search_Bin(l,m);if(n=0)printf("數(shù)組中沒(méi)有此元素!");printf("n");printf("是否繼續(xù)?(輸入1繼續(xù)/輸入0結(jié)束)");scanf("%d",&v);if(v=0) return 0;else if(v=1) goto loop1;elseprintf("數(shù)組中找到此元素!");printf("n");printf("是否繼續(xù)?(輸入1繼續(xù)/輸入0結(jié)束)");scanf("%d",&v);if(v=0) return 0;else if(v=1) goto l