實(shí)驗(yàn)四查找docx

1、成績(jī)：實(shí) 驗(yàn) 報(bào) 告課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目：查找表的操作練習(xí)姓 名：李翠超專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：計(jì)算機(jī)16-6班學(xué) 號(hào)：1609040307計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí)驗(yàn)教學(xué)中心2017年12月11日實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 查找表的操作練習(xí) 一、實(shí)驗(yàn)?zāi)康?.學(xué)習(xí)掌握查找的含義2.學(xué)習(xí)掌握基本查找的操作算法與實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容1.實(shí)現(xiàn)順序查找，在輸入的數(shù)組紀(jì)錄中順序查找所需的紀(jì)錄。2.用二分查找，也稱(chēng)折半查找方法，對(duì)已知的有序序列進(jìn)行查找。3.考慮輸入無(wú)序數(shù)時(shí)如何實(shí)現(xiàn)折半查找。 三、實(shí)驗(yàn)步驟1.順序查找建立一個(gè)線(xiàn)性表，對(duì)表中數(shù)據(jù)元素存放的先后次序沒(méi)有任何要求。輸入待查數(shù)據(jù)元素的關(guān)鍵字進(jìn)行查找

2、。為了簡(jiǎn)化算法，數(shù)據(jù)元素只含一個(gè)整型量關(guān)鍵字字段，數(shù)據(jù)元素的其余數(shù)據(jù)部分忽略不考慮。從表的一端開(kāi)始，順序掃描線(xiàn)性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值相比較，若相等，則查找成功，若整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于的元素，則查找失敗。順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無(wú)序的。2.二分查找表的存儲(chǔ)結(jié)構(gòu)為有序表，即表中記錄按關(guān)鍵字大小排序存放。輸入待查數(shù)據(jù)元素的 關(guān)鍵字進(jìn)行查找。為了簡(jiǎn)化算法，記錄只含一個(gè)整型量關(guān)鍵字字段，記錄的其余數(shù)據(jù)部分忽略不考慮。此程序中要求對(duì)整型量關(guān)鍵字?jǐn)?shù)

3、據(jù)的輸入按從小到大排序輸入。二分查找是一種高效率的查找方法。但二分查找有條件限制：要求表必須用向量作存貯結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序(升序或降序均可)?；舅枷胧牵菏紫葘⒋橹礙與有序表R1到Rn的中點(diǎn)mid上的關(guān)鍵字Rmid.key進(jìn)行比較，若相等，則查找成功；否則，若Rmid.key>k ， 則在R1到Rmid-1中繼續(xù)查找，若有Rmid.key<k ， 則在Rmid+1到Rn中繼續(xù)查找。每通過(guò)一次關(guān)鍵字的比較，區(qū)間的長(zhǎng)度就縮小一半，區(qū)間的個(gè)數(shù)就增加一倍，如此不斷進(jìn)行下去，直到找到關(guān)鍵字為K的元素；若當(dāng)前的查找區(qū)間為空(表示查找失敗)。 四、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果如圖所示，按照要

4、求將數(shù)據(jù)輸入五、程序代碼#include<stdio.h>#define OK 1#define ERROR 0#define MAXSIZE 100typedef int Status;typedef int KeyType; / 設(shè)關(guān)鍵字域?yàn)檎?define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#define LQ(a,b) (a)<=(b)typedef struct KeyType key; ElemType;ElemType aMAXSIZE;typedef struct ElemType *elem; / 數(shù)據(jù)元素存

5、儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空 int length; / 表長(zhǎng)度 SSTable;typedef struct int dataMAXSIZE; / 數(shù)組，存儲(chǔ)數(shù)據(jù)元素 int length; / 線(xiàn)性表當(dāng)前長(zhǎng)度 SqList;Status InitList(SqList *L) L->length=0; return OK;Status ListInsert(SqList *L,int i,int e) int k; if (L->length=MAXSIZE) / 順序線(xiàn)性表已經(jīng)滿(mǎn) return ERROR; if (i<1 | i>L->l

6、ength+1) / 當(dāng)i比第一位置小或者比最后一位置后一位置還要大時(shí) return ERROR; if (i<=L->length) / 若插入數(shù)據(jù)位置不在表尾 for(k=L->length-1; k>=i-1; k-) / 將要插入位置之后的數(shù)據(jù)元素向后移動(dòng)一位 L->datak+1=L->datak; L->datai-1=e; / 將新元素插入 L->length+; return OK;Status GetElem(SqList L,int i,int *e) if(L.length=0 | i<1 | i>L.lengt

7、h) return ERROR; *e=L.datai-1; return OK;/L.datai-1;void SelectSort(SqList *L) int i,j,min,temp; for(i=1; i<L->length; i+) min = i;/ 將當(dāng)前下標(biāo)定義為最小值下標(biāo) for (j = i+1; j<=L->length; j+) / 循環(huán)之后的數(shù)據(jù) if (L->datamin>L->dataj)/ 如果有小于當(dāng)前最小值的關(guān)鍵字 min = j;/ 將此關(guān)鍵字的下標(biāo)賦值給min if(i!=min)/ 若min不等于i，說(shuō)明找

8、到最小值，交換 temp=L->datai; L->datai=L->datamin; L->datamin=temp; / 交換L->datai與L->datamin的Status Creat_Seq(SSTable *ST,ElemType a,int n) / 操作結(jié)果: 構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)順序查找表ST int i; (*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType); / 動(dòng)態(tài)生成n個(gè)數(shù)據(jù)元素空間 if(!(*ST).elem) return ERROR; for(i=1; i<=n

9、; i+) *(*ST).elem+i)=ai-1; / 將全局?jǐn)?shù)組r的值依次賦給 (*ST).length=n; return OK;int Search_Seq(SSTable ST,KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置;否則為0。 int i; ST.elem0.key=key; / 哨兵 for(i=ST.length; !EQ(ST.elemi.key,key); -i); / 從后往前找 return i; / 找不到時(shí)，i為0int Search_Bin(SSTable ST,KeyType key

10、) / 在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 int low,high,mid; low=1; / 置區(qū)間初值 high=ST.length; while(low<=high) mid=(low+high)/2; if EQ(key,ST.elemmid.key) / 找到待查元素 return mid; else if LT(key,ST.elemmid.key) high=mid-1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low=mid+1; / 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 return 0; / 順序表中不存在待查

11、元素void print(ElemType c) / Traverse()調(diào)用的函數(shù) printf("%d",c);int judge(SSTable ST,int i) /判斷是否找到 if(i) print(*(ST.elem+i); else printf("沒(méi)找到nn"); return 0;int main() SqList L; SSTable st; int N,j,o; int aMAXSIZE,e; InitList(&L); printf("請(qǐng)輸入元素個(gè)數(shù)："); scanf("%d",

12、&N); for(j=1; j<=N; j+) printf("請(qǐng)輸入元素%d =:",j); scanf("%d",&o); ListInsert(&L,j,o); SelectSort(&L); for(j=1; j<=N; j+) aj-1=GetElem(L,j,&e); Creat_Seq(&st,a,N); printf("請(qǐng)輸入要查找的數(shù)："); int s,i,p; scanf("%d",&s); printf("順序查找:"); i=Search_Seq(st,s); judge(st,i); printf("折半查找法：");