1、精選優質文檔-傾情為你奉上淮海工學院計算機科學系實驗報告書課程名： 數據結構 題 目： 查找、排序的應用實驗 班 級： 學 號： 姓 名： 評語：成績： 指導教師： 批閱時間： 年 月 日專心-專注-專業排序、查找的應用實驗報告要求1目的與要求:1）查找、排序是日常數據處理過程中經常要進行的操作和運算，掌握其算法與應用對于提高學生數據處理能力和綜合應用能力顯得十分重要。2）本次實驗前，要求同學完整理解有關排序和查找的相關算法和基本思想以及種算法使用的數據存儲結構；3）利用C或C+語言獨立完成本次實驗內容或題目，程序具有良好的交互性（以菜單形式列出實驗排序和顯示命令，并可進行交互操作）和實用性；

2、4）本次實驗為實驗成績評定主要驗收內容之一，希望同學們認真對待，并按時完成實驗任務；5）本次實驗為綜合性實驗，請于2012年12月23日按時提交實驗報告（紙質報告每班10份）；6）下周開始數據結構課程設計，務必按時提交實驗報告，任何同學不得拖延。2 實驗內容或題目題目：對記錄序列（查找表）：287，109，063，930，589，184，505，269,008，083分別實現如下操作：1) 分別使用直接插入排序、冒泡排序、快速排序、簡單選擇排序、堆排序（可選）、鏈式基數排序算法對紀錄序列進行排序，并顯示排序結果；2) 對上述紀錄列表排好序，然后對其進行折半查找或順序查找；（特別要求：使用菜單機

3、制，在一個主程序下實現題目要求的排序和查找以及結果顯示）3 實驗步驟與源程序#include <stdio.h>#include <stdlib.h>/*鏈式基數法排序聲明*/ #define RADIX 10#define KEY_SIZE 6#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef int OtherType;typedef struct KeyType keyKEY_SIZE; /* 子關鍵字數組 */ OtherType other_data; /*

4、其它數據項 */ int next; /* 靜態鏈域 */ RecordType1;typedef struct RecordType1 rLIST_SIZE+1;/* r0為頭結點 */int length;int keynum;SLinkList; /* 靜態鏈表 */typedef int PVectorRADIX;typedef structint next;KeyType key;OtherType other_data;RecordType;void InsSort(RecordType r, int length)/* 對記錄數組r做直接插入排序，length為數組中待排序記錄的

5、數目*/ int i,j;for (i=2; i<=length; i+) r0=ri; /*將待插入記錄存放到監視哨r0中*/j=i-1; while (r0.key< rj.key ) /* 尋找插入位置 */rj+1= rj; j=j-1;rj+1=r0; /*將待插入記錄插入到已排序的序列中*/ /* InsSort */ /順序查找void SeqSearch(RecordType r,int length,KeyType k)int i;r0.key=k;i=length;while(ri.key!=k) i-;printf("該元素在數組中的位置是%d&qu

6、ot;,i);/冒泡排序void BubbleSort(RecordType r, int length )/*對記錄數組r做冒泡排序，length為數組的長度*/int n,i,j;int change;RecordType x;n=length; change=TRUE;for ( i=1 ; i<= n-1 && change ;+i ) change=FALSE;for ( j=1 ; j<= n-i ; +j) if (rj.key > rj+1.key ) x= rj;rj= rj+1;rj+1= x;change=TRUE; /* BubbleS

7、ort */ 快速排序int QKPass(RecordType r,int left,int right)/*對記錄數組r 中的rleft至rright部分進行一趟排序，并得到基準的位置，使得排序后的結果滿足其之后（前）的記錄的關鍵字均不小于（大于）于基準記錄*/ RecordType x;int low,high;x= rleft; /* 選擇基準記錄*/ low=left; high=right;while ( low<high )while (low< high && rhigh.key>=x.key ) /* high從右到左找小于x.key的記錄

8、*/high-;if ( low <high ) rlow= rhigh;low+; /* 找到小于x.key的記錄，則進行交換*/while (low<high && rlow.key<x.key ) /* low從左到右找大于x.key的記錄 */low+; if ( low<high ) rhigh= rlow;high-; /* 找到大于x.key的記錄，則交換*/rlow=x; /*將基準記錄保存到low=high的位置*/return low; /*返回基準記錄的位置*/ /* QKPass */ void SelectSort(Record

9、Type r,int length)/*對記錄數組r做簡單選擇排序，length為數組的長度*/int i,j,k,n; RecordType x;n=length;for(i=1;i<=n-1;+i)k=i;for(j=i+1;j<=n;+j)if(rj.key<rk.key) k=j;if(k!=i)x=ri;ri=rk;rk=x;void QKSort(RecordType r,int low, int high )/*對記錄數組rlow.high用快速排序算法進行排序*/int pos;if(low<high)pos=QKPass(r, low, high);

10、/*調用一趟快速排序，將樞軸元素為界劃分兩個子表*/QKSort(r, low, pos-1); /*對左部子表快速排序*/QKSort(r, pos+1, high); /*對右部子表快速排序*/ 堆排序void sift(RecordType r, int k, int m)/* 假設k.m是以k為根的完全二叉樹，且分別以2k和2k+1為根的左、右子樹為大根堆，調整rk，使整個序列rk.m滿足堆的性質 */RecordType t;int i,j;int x;int finished;t= rk; /* 暫存"根"記錄rk */ x=rk.key;i=k;j=2*i;f

11、inished=FALSE;while( j<=m && !finished ) if (j<m && rj.key< rj+1.key ) j=j+1; /* 若存在右子樹，且右子樹根的關鍵字大，則沿右分支"篩選" */if ( x>= rj.key)finished=TRUE; /* 篩選完畢 */ else ri = rj;i=j;j=2*i; /* 繼續篩選 */ ri =t; /* rk填入到恰當的位置 */ void crt_heap(RecordType r, int length )/*對記錄數組r建堆

12、，length為數組的長度*/int i,n; n= length;for ( i=n/2; i >= 1; -i) /* 自第n/2個記錄開始進行篩選建堆 */ sift(r,i,n);void HeapSort(RecordType r,int length)/* 對r1.n進行堆排序，執行本算法后，r中記錄按關鍵字由大到小有序排列 */ int i,n;RecordType b;crt_heap(r, length);n= length;for ( i=n ; i>= 2; -i) b=r1; /* 將堆頂記錄和堆中的最后一個記錄互換 */ r1= ri;ri=b; sift

13、(r,1,i-1); /* 進行調整，使r1.i-1變成堆 */ /* HeapSort */鏈式基數排序void Distribute(RecordType1 r, int i, PVector head, PVector tail)/* 記錄數組r中記錄已按低位關鍵字keyi+1，keyd進行過"低位優先"排序。本算法按第i位關鍵字keyi建立RADIX個隊列，同一個隊列中記錄的keyi相同。headj和tailj分別指向各隊列中第一個和最后一個記錄（j=0，1，2，RADIX-1）。headj=0表示相應隊列為空隊列*/ int j;int p;for ( j=0 ;

14、 j<=RADIX-1 ; +j)headj=0; /* 將RADIX個隊列初始化為空隊列 */ p= r0.next; /* p指向鏈表中的第一個記錄 */ while( p!=0 ) j=rp.keyi; /* 用記錄中第i位關鍵字求相應隊列號 */if ( headj=0 ) headj=p; /* 將p所指向的結點加入第j個隊列中 */ elsertailj.next=p;tailj=p;p= rp.next; /* Distribute */ void Collect(RecordType1 r, PVector head, PVector tail)/* 本算法從0到RADI

15、X-1 掃描各隊列，將所有非空隊列首尾相接，重新鏈接成一個鏈表 */ int j;int t;j=0;while (headj=0 ) /* 找第一個非空隊列 */ +j;r0.next =headj;t=tailj;while ( j<RADIX-1 ) /* 尋找并串接所有非空隊列 */+j;while ( (j<RADIX-1 ) && (headj=0 ) ) /* 找下一個非空隊列 */ +j;if ( headj!=0 ) /* 鏈接非空隊列 */ rt.next =headj;t=tailj; rt.next =0; /* t指向最后一個非空隊列中的最

16、后一個結點 */ /* Collect */ void RadixSort (RecordType1 r,int length )/* length個記錄存放在數組r中，執行本算法進行基數排序后，鏈表中的記錄將按關鍵字從小到大的順序相鏈接。 */ int i,n;int d;PVector head;PVector tail; n= length;for ( i=0 ; i<= n-1 ; +i) ri.next=i+1; /* 構造靜態鏈表 */rn.next =0;d= 3;for ( i =d-1; i>= 0; -i ) /* 從最低位子關鍵字開始，進行d趟分配 和 收集*

17、/ Distribute(r,i,head,tail); /* 第i趟分配 */ Collect(r,head,tail); /* 第i趟收集 */ /* RadixSort */void main()int flag=1,i,j,k,b;RecordType r20;int len;printf("*功能菜單*n");printf("1.直接插入排序; 2.冒泡排序;n");printf("3.快速排序; 4.簡單選擇排序;n");printf("5.堆排序; 6.順序查找;n");printf("7.

18、鏈式基數排序; 8.退出;n");printf("請輸入待排序記錄的長度:");scanf("%d",&len);for(i=1;i<=len;i+)printf("請輸入第%d個記錄元素:",i);fflush(stdin);scanf("%d",&j);ri.key = j;printf("原記錄序列：");for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");whi

19、le(flag)printf("請選擇操作："); scanf("%d",&b);switch(b)case 1:/ 直接插入排序printf("n直接插入排序結果：n");InsSort(r,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 2:/冒泡排序printf("冒泡排序結果：n");BubbleSort(r,len);for(i=1;i<=len;i+)prin

20、tf("%d ",ri.key);printf("n");break;case 3:/ 快速排序printf("快速排序結果：n");QKSort(r,1,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 4:/簡單選擇排序SelectSort(r,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");b

21、reak;case 5:/ 堆排序printf("堆排序結果：n");HeapSort(r,len); for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 6:/進行順序查找printf("請輸入您要查找的元素：");fflush(stdin);scanf("%d",&k);SeqSearch(r,len,k);printf("n");break; case 7:/鏈式基數排序 RecordType1 a20; in