查找、排序的應(yīng)用實(shí)驗(yàn)(共11頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上淮海工學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告書課程名： 數(shù)據(jù)結(jié)構(gòu) 題 目： 查找、排序的應(yīng)用實(shí)驗(yàn) 班 級(jí)： 軟件112 學(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)行交互操作

2、）和實(shí)用性；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)行折半查找或順序查找；3 實(shí)驗(yàn)步

3、驟與源程序 #include "stdio.h"#include "stdlib.h"#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef structKeyType key;RecordType;typedef structRecordType rLIST_SIZE+1;int length;RecordList;void seqSearch(RecordList *l)KeyType k;int i;printf("請(qǐng)輸出要查詢的元素k:&q

4、uot;); fflush(stdin);scanf("%d",&k);i=l->length;while (i>=0&&l->ri.key!=k) i-;printf("該元素的位置是");printf("%d",i+1);/cout<<"該元素在圖中第"<<i<<"個(gè)位置"<<endl;printf("n");void BinSrch(RecordList *l)KeyType q;

5、int mid;printf("請(qǐng)輸入要查詢的元素k:");fflush(stdin);scanf("%d",&q);int low=1;int high=l->length;while(low<=high)mid=(low+high)/2;if(q=l->rmid.key)printf("該元素的位置為:");printf("%d",mid+1);/注意不能隨便使用&printf("n");break;else if(q<l->rmid.key)

6、high=mid-1;elselow=mid+1;void inputkey(RecordList *l) int i;printf("請(qǐng)輸入線性表長(zhǎng)度:");/遇到錯(cuò)誤：1.print用法scanf("%d",&(l->length);/&將變量的地址賦值，而不是變量的值for(i=1;i<=l->length ;i+)printf("請(qǐng)輸入第%d個(gè)元素的值:",i); fflush(stdin);scanf("%d",&(l->ri.key);void InsSo

7、rt(RecordList *l)for(int i=2;i<=l->length;i+)l->r0.key=l->ri.key;int j=i-1;while(l->r0.key<l->rj.key) l->rj+1.key=l->rj.key;j=j-1;l->rj+1.key=l->r0.key;/直接插入排序void BubbleSort(RecordList *l) int x,i,n,change,j; n=l->length;change=TRUE; for(i=1;i<=n-1&&ch

8、ange;+i) change=FALSE; for(j=1;j<=n-i;+j) if(l->rj.key>l->rj+1.key) x=l->rj.key; l->rj.key=l->rj+1.key ; l->rj+1.key=x; change=TRUE; /冒泡排序法int QKPass(RecordList *l,int left,int right) int x; x=l->rleft.key ;int low=left;int high=right; while(low<high) while(low<high&

9、amp;&l->rhigh.key>=x) high-; if(low<high) l->rlow.key=l->rhigh.key; low+; while(low<high&&l->rlow.key<=x) low+;if(low<high)l->rhigh.key=l->rlow.key;high-; l->rlow.key=x; return(low); void QKSort(RecordList *l,int low,int high) int pos; if(low<high)

10、pos=QKPass(l,low,high); QKSort(l,low,pos-1); QKSort(l,pos+1,high); /快速排序void SelectSort(RecordList *l) int n,i,k,j,x; n=l->length; for(i=1;i<=n-1;+i) k=i; for(j=i+1;j<=n;+j) if(l->rj.key<l->rk.key) k=j; if(k!=i) x=l->ri.key;l->ri.key=l->rk.key;l->rk.key=x; void output(R

11、ecordList *l)for(int i=1;i<=l->length;i+)printf("%d",l->ri.key);printf("n");void main()RecordList *l,*t,*m,*n; l=(RecordList *)malloc(sizeof(RecordList);int low;int high;int flag=1;int xuanze;while(flag!=0)printf("#n");printf("# 請(qǐng)選擇你要進(jìn)行的操作! #n");print

12、f("# 1.直接插入排序; #n");printf("# 2.冒泡排序; #n");printf("# 3.快速排序; #n");printf("# 4.簡(jiǎn)單選擇排序; #n");printf("# 5.順序查找; #n");printf("# 6.折半查找; #n");printf("# 7.退出! #n");printf("#n");scanf("%d",&xuanze);switch(xuanze)c

13、ase 1:inputkey(l);InsSort(l);printf("直接插入排序結(jié)果是:n");output(l);break;case 2:inputkey(l);BubbleSort(l);printf("冒泡排序結(jié)果是:n");output(l);break;case 3:inputkey(l); low=1; high=l->length; QKSort(l,low,high);printf("快速排序結(jié)果是:n");output(l);break;case 4:inputkey(l); SelectSort(l); printf("簡(jiǎn)單選擇排序結(jié)果是:n"); output(l);break;case 5:inputkey(l); InsSort(l); printf("排序結(jié)果是:n"); output(l);seqSear