查找、排序應(yīng)用實(shí)驗(yàn)

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

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

3、制，在一個(gè)主程序下實(shí)現(xiàn)題目要求的排序和查找以及結(jié)果顯示）3 實(shí)驗(yàn)步驟與源程序#include <stdio.h>#include <stdlib.h>/*鏈?zhǔn)交鶖?shù)法排序聲明*/ #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; /* 子關(guān)鍵字?jǐn)?shù)組 */ OtherType other_data; /*

4、其它數(shù)據(jù)項(xiàng) */ int next; /* 靜態(tài)鏈域 */ RecordType1;typedef struct RecordType1 rLIST_SIZE+1;/* r0為頭結(jié)點(diǎn) */int length;int keynum;SLinkList; /* 靜態(tài)鏈表 */typedef int PVectorRADIX;typedef structint next;KeyType key;OtherType other_data;RecordType;void InsSort(RecordType r, int length)/* 對(duì)記錄數(shù)組r做直接插入排序，length為數(shù)組中待排序記錄的

5、數(shù)目*/ int i,j;for (i=2; i<=length; i+) r0=ri; /*將待插入記錄存放到監(jiān)視哨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("該元素在數(shù)組中的位置是%d&qu

6、ot;,i);/冒泡排序void BubbleSort(RecordType r, int length )/*對(duì)記錄數(shù)組r做冒泡排序，length為數(shù)組的長(zhǎng)度*/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)/*對(duì)記錄數(shù)組r 中的rleft至rright部分進(jìn)行一趟排序，并得到基準(zhǔn)的位置，使得排序后的結(jié)果滿足其之后（前）的記錄的關(guān)鍵字均不小于（大于）于基準(zhǔn)記錄*/ RecordType x;int low,high;x= rleft; /* 選擇基準(zhǔn)記錄*/ 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的記錄，則進(jìn)行交換*/while (low<high && rlow.key<x.key ) /* low從左到右找大于x.key的記錄 */low+; if ( low<high ) rhigh= rlow;high-; /* 找到大于x.key的記錄，則交換*/rlow=x; /*將基準(zhǔn)記錄保存到low=high的位置*/return low; /*返回基準(zhǔn)記錄的位置*/ /* QKPass */ void SelectSort(Record

9、Type r,int length)/*對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，length為數(shù)組的長(zhǎng)度*/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 )/*對(duì)記錄數(shù)組rlow.high用快速排序算法進(jìn)行排序*/int pos;if(low<high)pos=QKPass(r, low, high);

10、/*調(diào)用一趟快速排序，將樞軸元素為界劃分兩個(gè)子表*/QKSort(r, low, pos-1); /*對(duì)左部子表快速排序*/QKSort(r, pos+1, high); /*對(duì)右部子表快速排序*/ 堆排序void sift(RecordType r, int k, int m)/* 假設(shè)k.m是以k為根的完全二叉樹，且分別以2k和2k+1為根的左、右子樹為大根堆，調(diào)整rk，使整個(gè)序列rk.m滿足堆的性質(zhì) */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; /* 若存在右子樹，且右子樹根的關(guān)鍵字大，則沿右分支"篩選" */if ( x>= rj.key)finished=TRUE; /* 篩選完畢 */ else ri = rj;i=j;j=2*i; /* 繼續(xù)篩選 */ ri =t; /* rk填入到恰當(dāng)?shù)奈恢?*/ void crt_heap(RecordType r, int length )/*對(duì)記錄數(shù)組r建堆

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

13、(r,1,i-1); /* 進(jìn)行調(diào)整，使r1.i-1變成堆 */ /* HeapSort */鏈?zhǔn)交鶖?shù)排序void Distribute(RecordType1 r, int i, PVector head, PVector tail)/* 記錄數(shù)組r中記錄已按低位關(guān)鍵字keyi+1，keyd進(jìn)行過"低位優(yōu)先"排序。本算法按第i位關(guān)鍵字keyi建立RADIX個(gè)隊(duì)列，同一個(gè)隊(duì)列中記錄的keyi相同。headj和tailj分別指向各隊(duì)列中第一個(gè)和最后一個(gè)記錄（j=0，1，2，RADIX-1）。headj=0表示相應(yīng)隊(duì)列為空隊(duì)列*/ int j;int p;for ( j=0 ;

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

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

16、后一個(gè)結(jié)點(diǎn) */ /* Collect */ void RadixSort (RecordType1 r,int length )/* length個(gè)記錄存放在數(shù)組r中，執(zhí)行本算法進(jìn)行基數(shù)排序后，鏈表中的記錄將按關(guān)鍵字從小到大的順序相鏈接。 */ int i,n;int d;PVector head;PVector tail; n= length;for ( i=0 ; i<= n-1 ; +i) ri.next=i+1; /* 構(gòu)造靜態(tài)鏈表 */rn.next =0;d= 3;for ( i =d-1; i>= 0; -i ) /* 從最低位子關(guān)鍵字開始，進(jìn)行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.簡(jiǎn)單選擇排序;n");printf("5.堆排序; 6.順序查找;n");printf("7.

18、鏈?zhǔn)交鶖?shù)排序; 8.退出;n");printf("請(qǐng)輸入待排序記錄的長(zhǎng)度:");scanf("%d",&len);for(i=1;i<=len;i+)printf("請(qǐng)輸入第%d個(gè)記錄元素:",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("請(qǐng)選擇操作："); scanf("%d",&b);switch(b)case 1:/ 直接插入排序printf("n直接插入排序結(jié)果：n");InsSort(r,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 2:/冒泡排序printf("冒泡排序結(jié)果：n");BubbleSort(r,len);for(i=1;i<=len;i+)prin

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

21、reak;case 5:/ 堆排序printf("堆排序結(jié)果：n");HeapSort(r,len); for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 6:/進(jìn)行順序查找printf("請(qǐng)輸入您要查找的元素：");fflush(stdin);scanf("%d",&k);SeqSearch(r,len,k);printf("n");break; case 7:/鏈?zhǔn)交鶖?shù)排序 RecordType1 a20; in