實驗五查找及排序

1、實驗五 查找及排序?qū)嶒炚n程名： 數(shù)據(jù)結(jié)構(gòu)與算法一、實驗?zāi)康募耙?、掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法。2、熟練掌握順序表的查找方法和有序順序表的折半查找算法。3、掌握常用的排序方法，并能用高級語言實現(xiàn)排序算法。4、深刻理解排序的定義和各種排序方法的特點，并能加以靈活運用。5、了解各種方法的排序過程及依據(jù)的原則，并掌握各種排序方法的時間復(fù)雜度的分析方法。二、實驗內(nèi)容任務(wù)一：順序表的順序查找。 有序表的折半查找。完成下列程序，該程序?qū)崿F(xiàn)高考成績表（如下表所示）的順序查找，在輸出結(jié)果中顯示查找成功與查找不成功信息。準(zhǔn)考證號姓名各科成績總分政治語文外語數(shù)學(xué)物理化學(xué)生物179328何芳芳8

2、58998100938047592179325陳紅858688100929045586179326陸華78759080958837543179327張平82807898849640558179324趙小怡76859457776944502解答：（1）源代碼：#include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.

3、h> / exit() #include<iostream.h> / cout,cin / 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean; / Boolean是布爾類型,其值是TRUE或FALS

4、E#define MAX_LENGTH 100#include<string.h> #include<ctype.h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #inc

5、lude<process.h> / exit() #include<iostream.h> / cout,cin / 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean; / Boolean是布

6、爾類型,其值是TRUE或FALSE #define N 5 / 數(shù)據(jù)元素個數(shù)#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#define LQ(a,b) (a)<=(b)typedef long KeyType; / 設(shè)關(guān)鍵字域為長整型 #define key number / 定義關(guān)鍵字為準(zhǔn)考證號 struct ElemType / 數(shù)據(jù)元素類型(以教科書圖9.1高考成績?yōu)槔? long number; / 準(zhǔn)考證號，與關(guān)鍵字類型同 char name9; / 姓名(4個漢字加1個串結(jié)束標(biāo)志) int politics; / 政治 i

7、nt Chinese; / 語文 int English; / 英語 int math; / 數(shù)學(xué) int physics; / 物理 int chemistry; / 化學(xué) int biology; / 生物 int total; / 總分 ;typedef struct ElemType *elem; / 數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，0號單元留空 int length; / 表長度 SSTable;void Creat_Seq(SSTable &ST,ElemType r,int n) / 操作結(jié)果：由含n個數(shù)據(jù)元素的數(shù)組r構(gòu)造靜態(tài)順序查找表ST int i; ST

8、.elem=(ElemType*)calloc(n+1,sizeof(ElemType); / 動態(tài)生成n+1個數(shù)據(jù)元素空間(0號單元不用) if(!ST.elem) exit(ERROR); for(i=1;i<=n;i+) ST.elemi=ri-1; / 將數(shù)組r的值依次賦給ST ST.length=n; void Ascend(SSTable &ST) / 重建靜態(tài)查找表為按關(guān)鍵字非降序排序 int i,j,k; for(i=1;i<ST.length;i+) k=i; ST.elem0=ST.elemi; / 待比較值存0單元 for(j=i+1;j<=ST

9、.length;j+) if LT(ST.elemj.key,ST.elem0.key) k=j; ST.elem0=ST.elemj; if(k!=i) / 有更小的值則交換 ST.elemk=ST.elemi; ST.elemi=ST.elem0; void Creat_Ord(SSTable &ST,ElemType r,int n) / 操作結(jié)果：由含n個數(shù)據(jù)元素的數(shù)組r構(gòu)造按關(guān)鍵字非降序查找表ST Creat_Seq(ST,r,n); / 建立無序的查找表ST Ascend(ST); / 將無序的查找表ST重建為按關(guān)鍵字非降序查找表 Status Destroy(SSTabl

10、e &ST) / 初始條件：靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST free(ST.elem); ST.elem=NULL; ST.length=0; return OK; int Search_Seq(SSTable ST,KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則返回 / 該元素在表中的位置，否則返回0。算法9.1 int i; ST.elem0.key=key; / 哨兵 for(i=ST.length;!EQ(ST.elemi.key,key);-i); / 從后往前找 return i; / 找不到時，i為0 void Tr

11、averse(SSTable ST,void(*Visit)(ElemType) / 初始條件：靜態(tài)查找表ST存在，Visit()是對元素操作的應(yīng)用函數(shù) / 操作結(jié)果：按順序?qū)T的每個元素調(diào)用函數(shù)Visit()一次且僅一次 ElemType *p; int i; p=+ST.elem; / p指向第一個元素 for(i=1;i<=ST.length;i+) Visit(*p+); void print(ElemType c) / Traverse()調(diào)用的函數(shù) printf("%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5dn",c.number,

12、,c.politics, c.Chinese,c.English,c.math,c.physics,c.chemistry,c.biology,c.total); int main() ElemType rN=179328,"何芳芳",85,89,98,100,93,80,47, 179325,"陳紅",85,86,88,100,92,90,45,179326,"陸華",78,75,90,80,95,88,37,179327,"張平",82,80,78,98,84,96,40,179324,"

13、趙小怡",76,85,94,57,77,69,44; / 數(shù)組不按關(guān)鍵字有序 SSTable st; int i; long s; for(i=0;i<N;i+) / 計算總分 ri.total=ri.politics+ri.Chinese+ri.English+ri.math+ri.physics+ ri.chemistry+ri.biology; Creat_Seq(st,r,N); / 由數(shù)組r產(chǎn)生順序靜態(tài)查找表st printf("準(zhǔn)考證號 姓名 政治 語文 外語 數(shù)學(xué) 物理 化學(xué) 生物 總分n"); Traverse(st,print); / 按順

14、序輸出靜態(tài)查找表st printf("請輸入待查找人的考號: "); scanf("%ld",&s); i=Search_Seq(st,s); / 順序查找 if(i) print(st.elemi); else printf("沒找到n"); Destroy(st); return 0; （2）運行結(jié)果：（3） 運行結(jié)果分析：運用順序結(jié)構(gòu)完成查詢。任務(wù)二：哈希表的開放定址法算法。在輸出結(jié)果中顯示查找成功與查找不成功信息。解答：（1）源代碼：#include<string.h> #include<ctype.

15、h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,c

16、in / 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean; / Boolean是布爾類型,其值是TRUE或FALSE#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)

17、#define LQ(a,b) (a)<=(b)#define N 11 / 數(shù)據(jù)元素個數(shù)#define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 #define NULL_KEY 0 / 0為無記錄標(biāo)志 #define N 10 / 數(shù)據(jù)元素個數(shù) typedef int KeyType; / 設(shè)關(guān)鍵字域為整型 struct ElemType / 數(shù)據(jù)元素類型 KeyType key; int ord; ;int hashsize=11,19,29,37; / 哈希表容量遞增表，一個合適的素數(shù)序列 int m=0; / 哈希表表

18、長，全局變量 struct HashTable ElemType *elem; / 數(shù)據(jù)元素存儲基址，動態(tài)分配數(shù)組 int count; / 當(dāng)前數(shù)據(jù)元素個數(shù) int sizeindex; / hashsizesizeindex為當(dāng)前容量 ;void InitHashTable(HashTable &H) / 操作結(jié)果：構(gòu)造一個空的哈希表 int i; H.count=0; / 當(dāng)前元素個數(shù)為0 H.sizeindex=0; / 初始存儲容量為hashsize0 m=hashsize0; H.elem=(ElemType*)malloc(m*sizeof(ElemType); if(!

19、H.elem) exit(OVERFLOW); / 存儲分配失敗 for(i=0;i<m;i+) H.elemi.key=NULL_KEY; / 未填記錄的標(biāo)志 void DestroyHashTable(HashTable &H) / 初始條件：哈希表H存在。操作結(jié)果：銷毀哈希表H free(H.elem); H.elem=NULL; H.count=0; H.sizeindex=0; unsigned Hash(KeyType K) / 一個簡單的哈希函數(shù)(m為表長，全局變量) return K%m; void collision(int &p,int d) / 線性

20、探測再散列 / 開放定址法處理沖突 p=(p+d)%m; Status SearchHash(HashTable H,KeyType K,int &p,int &c) / 在開放定址哈希表H中查找關(guān)鍵碼為K的元素，若查找成功，以p指示待查數(shù)據(jù) / 元素在表中位置，并返回SUCCESS；否則，以p指示插入位置，并返回UNSUCCESS / c用以計沖突次數(shù)，其初值置零，供建表插入時參考。算法9.17 p=Hash(K); / 求得哈希地址 while(H.elemp.key!=NULL_KEY&&!EQ(K,H.elemp.key) / 該位置中填有記錄并且關(guān)鍵字

21、不相等 c+; if(c<m) collision(p,c); / 求得下一探查地址p else break; if EQ(K,H.elemp.key) return SUCCESS; / 查找成功，p返回待查數(shù)據(jù)元素位置 else return UNSUCCESS; / 查找不成功(H.elemp.key=NULL_KEY)，p返回的是插入位置 Status InsertHash(HashTable &,ElemType); / 對函數(shù)的聲明 void RecreateHashTable(HashTable &H) / 重建哈希表 int i,count=H.count

22、; ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType); p=elem; printf("重建哈希表n"); for(i=0;i<m;i+) / 保存原有的數(shù)據(jù)到elem中 if(H.elem+i)->key!=NULL_KEY) / 該單元有數(shù)據(jù) *p+=*(H.elem+i); H.count=0; H.sizeindex+; / 增大存儲容量 m=hashsizeH.sizeindex; p=(ElemType*)realloc(H.elem,m*sizeof(ElemType); if(!

23、p) exit(OVERFLOW); / 存儲分配失敗 H.elem=p; for(i=0;i<m;i+) H.elemi.key=NULL_KEY; / 未填記錄的標(biāo)志(初始化) for(p=elem;p<elem+count;p+) / 將原有的數(shù)據(jù)按照新的表長插入到重建的哈希表中 InsertHash(H,*p); Status InsertHash(HashTable &H,ElemType e) / 查找不成功時插入數(shù)據(jù)元素e到開放定址哈希表H中，并返回OK； / 若沖突次數(shù)過大，則重建哈希表，算法9.18 int c,p; c=0; if(SearchHash(

24、H,e.key,p,c) / 表中已有與e有相同關(guān)鍵字的元素 return DUPLICATE; else if(c<hashsizeH.sizeindex/2) / 沖突次數(shù)c未達(dá)到上限，(c的閥值可調(diào)) / 插入e H.elemp=e; +H.count; return OK; else RecreateHashTable(H); / 重建哈希表 return UNSUCCESS; void TraverseHash(HashTable H,void(*Vi)(int,ElemType) / 按哈希地址的順序遍歷哈希表 printf("哈希地址0%dn",m-1)

25、; for(int i=0;i<m;i+) if(H.elemi.key!=NULL_KEY) / 有數(shù)據(jù) Vi(i,H.elemi); Status Find(HashTable H,KeyType K,int &p) / 在開放定址哈希表H中查找關(guān)鍵碼為K的元素，若查找成功，以p指示待查數(shù)據(jù) / 元素在表中位置，并返回SUCCESS；否則，返回UNSUCCESS int c=0; p=Hash(K); / 求得哈希地址 while(H.elemp.key!=NULL_KEY&&!EQ(K,H.elemp.key) / 該位置中填有記錄并且關(guān)鍵字不相等 c+;

26、if(c<m) collision(p,c); / 求得下一探查地址p else return UNSUCCESS; / 查找不成功(H.elemp.key=NULL_KEY) if EQ(K,H.elemp.key) return SUCCESS; / 查找成功，p返回待查數(shù)據(jù)元素位置 else return UNSUCCESS; / 查找不成功(H.elemp.key=NULL_KEY) void print(int p,ElemType r) printf("address=%d (%d,%d)n",p,r.key,r.ord); int main() Elem

27、Type rN=17,1,60,2,29,3,38,4,1,5,2,6,3,7,4,8,60,9,13,10; HashTable h; int i,p; Status j; KeyType k; InitHashTable(h); for(i=0;i<N-1;i+) / 插入前N-1個記錄 j=InsertHash(h,ri); if(j=DUPLICATE) printf("表中已有關(guān)鍵字為%d的記錄，無法再插入記錄(%d,%d)n",ri.key,ri.key,ri.ord); printf("按哈希地址的順序遍歷哈希表:n"); Trave

28、rseHash(h,print); printf("請輸入待查找記錄的關(guān)鍵字: "); scanf("%d",&k); j=Find(h,k,p); if(j=SUCCESS) print(p,h.elemp); else printf("沒找到n"); j=InsertHash(h,ri); / 插入第N個記錄 if(j=ERROR) / 重建哈希表 j=InsertHash(h,ri); / 重建哈希表后重新插入 printf("按哈希地址的順序遍歷重建后的哈希表:n"); TraverseHash(h

29、,print); printf("請輸入待查找記錄的關(guān)鍵字: "); scanf("%d",&k); j=Find(h,k,p); if(j=SUCCESS) print(p,h.elemp); else printf("沒找到n"); DestroyHashTable(h); return 0; （2）運行結(jié)果：（3） 運行結(jié)果分析：運用哈希表開放定地址算法實現(xiàn)。任務(wù)三：各種插入排序算法的實現(xiàn)。解答：（1）源代碼：#include<string.h> #include<ctype.h> #includ

30、e<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,cin / 函數(shù)結(jié)果狀態(tài)代碼

31、 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean; / Boolean是布爾類型,其值是TRUE或FALSE typedef int InfoType; / 定義其它數(shù)據(jù)項的類型 #define EQ(a,b) (a)=(b) #d

32、efine LT(a,b) (a)<(b) #define LQ(a,b) (a)<=(b) #define MAX_SIZE 20 / 一個用作示例的小順序表的最大長度 typedef int KeyType; / 定義關(guān)鍵字類型為整型 struct RedType / 記錄類型 KeyType key; / 關(guān)鍵字項 InfoType otherinfo; / 其它數(shù)據(jù)項，具體類型在主程中定義 ; struct SqList / 順序表類型 RedType rMAX_SIZE+1; / r0閑置或用作哨兵單元 int length; / 順序表長度 ; void InsertS

33、ort(SqList &L) / 對順序表L作直接插入排序。 int i,j; for(i=2;i<=L.length;+i) if LT(L.ri.key,L.ri-1.key) / "<",需將L.ri插入有序子表 L.r0=L.ri; / 復(fù)制為哨兵 for(j=i-1;LT(L.r0.key,L.rj.key);-j) L.rj+1=L.rj; / 記錄后移 L.rj+1=L.r0; / 插入到正確位置 void BInsertSort(SqList &L) / 對順序表L作折半插入排序。 int i,j,m,low,high; for(

34、i=2;i<=L.length;+i) L.r0=L.ri; / 將L.ri暫存到L.r0 low=1; high=i-1; while(low<=high) / 在rlow.high中折半查找有序插入的位置 m=(low+high)/2; / 折半 if LT(L.r0.key,L.rm.key) high=m-1; / 插入點在低半?yún)^(qū) else low=m+1; / 插入點在高半?yún)^(qū) for(j=i-1;j>=high+1;-j) L.rj+1=L.rj; / 記錄后移 L.rhigh+1=L.r0; / 插入 void P2_InsertSort(SqList &L) / 2_路插入排序 int i,j,first,final; RedType *d; d=(RedType*)malloc(L.length*sizeof(RedType); / 生成L.length個記錄的臨時空間 d0=L.r1; / 設(shè)L的第1個記錄為d中排好序的記錄(在位置0) first=final=0; / first、final分別指示d中排好序的記錄的第1個和最后1個記錄的位置 for(i=2;i&