實驗九,查找、排序算法

1、數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實驗報告實驗九 查找、排序 班 級：13級計本2班 姓 名： 楊宴強(qiáng) 學(xué) 號：201392130129實驗九 查找、排序一、實驗?zāi)康模赫莆枕樞虿檎液驼郯氩檎业乃悸氛莆枕樞虿檎液驼郯氩檎宜惴ǖ某绦驅(qū)崿F(xiàn)3.掌握冒泡排序和選擇排序的思路4.掌握冒泡排序和選擇排序算法的程序?qū)崿F(xiàn)。二、實驗內(nèi)容：順序查找 折半查找3冒泡排序4.選擇排序三、實驗步驟及結(jié)果：161 順序查找#includestdio.h#define MAXSIZE 30typedef structint key;/int為關(guān)鍵字key的數(shù)據(jù)類型char data;/其他數(shù)據(jù)SeqList;/順序表元素類型int SeqSe

2、arch(SeqList R,int n,int k)/順序查找int i=n;R0.key=k;/R0.key為查找不成功的監(jiān)視哨while(Ri.key!=k)/由表尾向表頭方向查找i-;return i;/查找成功返回找到的位置值否則返回0值void main()int i=0,j,x;SeqList RMAXSIZE;/建立存放順序表元素的數(shù)組Rprintf(Intput data of list(-1 stop):n);/生成順序表中的數(shù)據(jù)(-1結(jié)束)scanf(%d,&x);while(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(Intput dat

3、a of list(-1 stop):n);/輸出順序表中的數(shù)據(jù)for(j=0;j0)printf(Position of %d in Seqlist!:n,x,i+1);/找到輸出在順序表中的位置elseprintf(NO found %d in Seqlist!:n,x);/輸出未找到信息printf(nSearch data in Seqlist,Intput data(-1 stop):n);scanf(%d,&x);16.2 折半查找#include#define MAXSIZE 30typedef structint key;char data;SeqList;int BinSea

4、rch(SeqList R,int n,int k)int low=0,high=n-1,mid;while(lowk)high=mid-1;elselow=mid+1;return -1;void main()int i;SeqList RMAXSIZE;for(i=1;i=12;i+)Ri.key=i*2;printf(Search 20 in Seqlist:n);i=BinSearch(R,12,20);if(i!=-1)printf(Position of 20 in Seqlist is %dn,i);elseprintf(NO found 20 in Seqlist!:n);pr

5、intf(Search 21 in Seqlist:n);i=BinSearch(R,12,21);if(i!=-1)printf(Position of 21 in Seqlist is %dn,i);elseprintf(NO found 21 in Seqlist!n);17.4 冒泡排序#include stdio.h#define MAXSIZE 30typedef structint key; /關(guān)鍵字項char data; /其他數(shù)據(jù)項RecordType; /記錄類型void BubbleSort(RecordType R,int n) /對R1Rn這n個記錄進(jìn)行冒泡排序int

6、 i,j,swap;for(i=1;in;i+) /進(jìn)行n-1趟排序swap=0; /設(shè)置未發(fā)生交換標(biāo)志for(j=1;jRj+1.key) /如果R1大于Rj+i.key則交換Rj和Rj+1R0=Rj;Rj=Rj+1;Rj+1=R0;swap=1; /有交換發(fā)生if(swap=0)break; /本趟比較中未出現(xiàn)交換則結(jié)束排序（已排好） void main()int i=1,j,x;RecordType RMAXSIZE; /定義記錄類型數(shù)組Rprintf(Input data of list (-1 stop):n); /給每一記錄輸入關(guān)鍵字直至-1結(jié)束scanf(%d,&x);while

7、(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(Output data in list:n); /輸出表中各記錄的關(guān)鍵字for(j=1;ji;j+)printf(%4d,Rj.key);BubbleSort(R,i-1); /進(jìn)行冒泡排序printf(nOutput data in list after Sort:n); /輸出冒泡排序后的結(jié)果for(j=1;ji;j+)printf(%4d,Rj.key);printf(n);17.7 選擇排序#includestdio.h#define MAXSIZE 30typedef structint key;/關(guān)鍵字項

8、char data;/其它數(shù)據(jù)項RecordType;/記錄類型void SelectSort(RecordType R,int n)/對R1-Rn這n個記錄進(jìn)行選擇排序int i,j,k;for(i=1;in;i+)/進(jìn)行n-1趟選擇k=i;/假設(shè)關(guān)鍵字最小的記錄為第i個記錄for(j=i+1;j=n;j+)/從第i個記錄開始的n-i+1個無序記錄中選出關(guān)鍵字最小的記錄if(Rj.keyRk.key)k=j;/保存最小關(guān)鍵字記錄的存放位置if(i!=k)/將找到的關(guān)鍵字最小的記錄與第i個記錄交換R0=Rk;Rk=Ri;Ri=R0;void main()int i=1,j,x;RecordTy

9、pe RMAXSIZE;/定義記錄類型數(shù)組Rprintf(Input data of list(-1 stop);n);/給每一個記錄輸入關(guān)鍵字直至-1結(jié)scanf(%d,&x);while(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(Output data in list:n);/輸出表中各記錄的關(guān)鍵字for(j=1;ji;j+)printf(%4d,Rj.key);printf(nSort:n);SelectSort(R,i-1);/進(jìn)行選擇排序printf(nOutput data in list after Sore:n);/輸出選擇排序后的結(jié)果for(j=1;ji;j+)printf(%4d,Rj.key);printf(n);四、實驗總結(jié)： 查找又稱檢索，它也是數(shù)據(jù)處理中經(jīng)常使用的一種重要的運算，在線性表上的查找方法有順序查找，二分查找和分塊查找。順序查找是一種最簡單的查找方法。它的基本思