實驗四查找docx

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

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

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

4、求將數(shù)據(jù)輸入五、程序代碼#include<stdio.h>#define OK 1#define ERROR 0#define MAXSIZE 100typedef int Status;typedef int KeyType; / 設關鍵字域為整型#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、儲空間基址，建表時按實際長度分配，0號單元留空 int length; / 表長度 SSTable;typedef struct int dataMAXSIZE; / 數(shù)組，存儲數(shù)據(jù)元素 int length; / 線性表當前長度 SqList;Status InitList(SqList *L) L->length=0; return OK;Status ListInsert(SqList *L,int i,int e) int k; if (L->length=MAXSIZE) / 順序線性表已經(jīng)滿 return ERROR; if (i<1 | i>L->l

6、ength+1) / 當i比第一位置小或者比最后一位置后一位置還要大時 return ERROR; if (i<=L->length) / 若插入數(shù)據(jù)位置不在表尾 for(k=L->length-1; k>=i-1; k-) / 將要插入位置之后的數(shù)據(jù)元素向后移動一位 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;/ 將當前下標定義為最小值下標 for (j = i+1; j<=L->length; j+) / 循環(huán)之后的數(shù)據(jù) if (L->datamin>L->dataj)/ 如果有小于當前最小值的關鍵字 min = j;/ 將此關鍵字的下標賦值給min if(i!=min)/ 若min不等于i，說明找

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

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

10、) / 在有序表ST中折半查找其關鍵字等于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ū)間進行查找 else low=mid+1; / 繼續(xù)在后半?yún)^(qū)間進行查找 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("沒找到nn"); return 0;int main() SqList L; SSTable st; int N,j,o; int aMAXSIZE,e; InitList(&L); printf("請輸入元素個數(shù)："); scanf("%d",

12、&N); for(j=1; j<=N; j+) printf("請輸入元素%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("請輸入要查找的數(shù)："); int s,i,p; scanf("%d",&s); printf("順序查找:"); i=Search_Seq(st,s); judge(st,i); printf("折半查找法：");