【文章內(nèi)容簡介】 開 始i， s r a n d ( t i m e ( 0 ) )i = L l e n g t hL r [ i ] . k e y = r a n d ( ) % 1 0 0 0 。 L r [ i ] . o t h e r = r a n d ( ) % 2 6 + 6 5 。結(jié) 束 . 數(shù)據(jù)結(jié)構(gòu)： （ 給出所使用的基本抽象數(shù)據(jù)類型 ,所定義的具體問題的數(shù)據(jù) 類型 ,以及新定義的抽象數(shù)據(jù)類型。 ） define MAXSIZE 200 define GET_ARRAY_LEN(array,len){len = (sizeof(array) / sizeof(array[0]))。} //定義一個帶參數(shù)的 宏，將數(shù)組長度存儲在變量 len 中 typedef int KeyType。 typedef struct //定義存儲記錄關(guān)鍵字及其他信息的結(jié)構(gòu)體 { KeyType key。 char other。 }RedType。 //記錄類型 typedef struct //定義存儲所有記錄的結(jié)構(gòu)體 { RedType r[MAXSIZE+1]。 //r[0]閑置或用作哨兵單元 int length。 //順序表長度 }SqList。 //順序表類型 typedef struct{ int move。 /*記錄數(shù)據(jù)移動次數(shù) */ int p。 /*記錄數(shù)據(jù)比較次數(shù) */ 第 19 頁 共 38 頁 int pex。 /*記錄空間復(fù)雜度 */ }Recode。 typedef SqList HeapType。 //堆采用順序表存儲表示 . 源程序： （ 給出所有源程序清單，要求程序有充分的注釋語句，至少要注釋每個函數(shù)參數(shù)的含義和函數(shù)返回值的含義。 ） include include include include iostream includealgorithm using namespace std。 define MAXSIZE 200 define GET_ARRAY_LEN(array,len){len = (sizeof(array) / sizeof(array[0]))。} //定義一個帶參數(shù)的 宏，將數(shù)組長度存儲在變量 len 中 typedef int KeyType。 typedef struct //定義存儲記錄關(guān)鍵字及其他信息的結(jié)構(gòu)體 { KeyType key。 char other。 }RedType。 //記錄類型 typedef struct //定義存儲所有記錄的結(jié)構(gòu)體 { RedType r[MAXSIZE+1]。 //r[0]閑置或用作哨兵單元 int length。 //順序表長度 }SqList。 //順序表類型 typedef struct{ int move。 /*記錄數(shù)據(jù)移動次數(shù) */ int p。 /*記錄數(shù)據(jù)比較次數(shù) */ int pex。 /*記錄空間復(fù)雜度 */ }Recode。 typedef SqList HeapType。 //堆采用順序表存儲表示 int dlta[5]={31,15,7,3,1}。 //初始化希爾排序的增量序列 int num[20]={0}。 //記錄每個排序方法的 移動次數(shù)和比較次數(shù) int flag=0。 //入的數(shù)據(jù) void create(SqList *L,int length) //創(chuàng)造一個初始排序數(shù)列 { int i。 srand(time(0))。 //srand函數(shù)是隨機數(shù)發(fā)生器的初始化函數(shù) Llength=length。 for(i=1。i=Llength。i++) 第 20 頁 共 38 頁 { Lr[i].key=rand()%1000。 Lr[i].other=rand()%26+65。 } } /*輸出元素 */ void visit(SqList L) {int i。 printf(\n)。 for(i=1。i=。i++) printf(%4d%2c,[i].key,[i].other)。 printf(\n)。 } /*簡單選擇排序 */ void select_sort(SqList L) { Recode r。 =0。 =0。 =1。 int i,j,k。 RedType t。 for (i=1。i。i++) { j=i。 for (k=i+1。k=。k++) { if ([j].key[k].key) { ++。 j=k。 }//把無序區(qū)最小的挑出來 } if (i!=j) {/*交換順序 */ //++。 t=[j]。 [j]=[i]。 [i]=t。 = +3。 } 第 21 頁 共 38 頁 } if(!flag) { printf(本次隨機數(shù)據(jù)排序的移動次數(shù)為 :)。 printf(%d\n,)。 printf(本次隨機數(shù)據(jù)排序的比較次數(shù)為 :)。 printf(%d\n,)。 printf(簡單選擇排序后的結(jié)果： )。 visit(L)。 } else{num[0]=。num[1]=。} } //直接插入排序 void Zhijie(SqList L) { Recode r。 =0。 =0。 // =0。 int j。 // ++。 for(int i=2。i=。++i) { // ++。 if([i].key[i1].key) { [0]=[i]。 //復(fù)制為哨兵 [i]=[i1]。 = +2。 for(j=i2。[0].key [j].key。j) { [j+1]=[j]。 //記錄后移 ++。 ++。 } [j+1]=[0]。 //插入到正確位置 ++。 } } if(!flag) 第 22 頁 共 38 頁 { printf(本次隨機數(shù)據(jù)排序的移動次數(shù)為 :)。 printf(%d\n,)。 printf(本次隨機數(shù)據(jù)排序的比較次數(shù)為 :)。 printf(%d\n,)。 printf(直接插入排序后的結(jié)果 ： )。 visit(L)。 } else{num[2]=。num[3]=。} } //希爾排序 void ShellInsert(SqList *L,int dk,Recode *r) { int i,j。 for(i=dk+1。i=Llength 。++i) { rp ++。 if(Lr[i].keyLr[i1].key) { Lr[0]=Lr[i]。 //暫存 rmove ++。 for(j=idk。j0amp。amp。(Lr[0].key Lr[j].key)。j=dk) { Lr[j+dk]=Lr[j]。 //記錄后移 rmove ++。 rp ++。 } Lr[j+dk]=Lr[0]。 //插入到正確位置 rmove ++。 } } } void ShellSort(SqList L,int dlta[],int t) { //按增量序列 dlta[0..t1]對順序表 L作希爾排序。 Recode r。 =0。 =0。 int k。 for(k=0。kt。++k) ShellInsert(amp。L,dlta[k],amp。r)。//一趟增量為 dlta[k]的插入排序 if(!flag) { printf(本次隨機數(shù)據(jù)排序的移動次數(shù)為 :)。 printf(%d\n,)。 printf(本次隨機數(shù)據(jù)排序的比較次數(shù)為 :)。 第 23 頁 共 38 頁 printf(%d\n,)。 printf(希爾排序后的結(jié)果 ： )。 visit(L)。 } else{num[4]=。num[5]=。} } //冒泡排序法 void Maopao(SqList L) { Recode r。 =0。 =0。 int i,j。 RedType t。 for(i=1。i。i++) for(j=1。j=。j++) { ++。 if([j].key[j+1].key) { = +3。 t=[j]。 [j]=[j+1]。 [j+1]=t。 } } if(!flag) { printf(本次隨機數(shù)據(jù)排序的移動次數(shù)為 :)。 printf(%d\n,)。 printf(本次隨機數(shù)據(jù)排序的比較次數(shù)為 :)。 printf(%d\n,)。 printf(冒泡排序后的結(jié)果 ： )。 visit(L)。 } else{num[6]=。num[7]=。} } //快速排序法 int Partition(SqList *L,int low,int high