1、實(shí)驗(yàn)七 查找、排序的應(yīng)用一、 實(shí)驗(yàn)?zāi)康?、本實(shí)驗(yàn)可以使學(xué)生更進(jìn)一步鞏固各種查找和排序的基本知識(shí)。2、學(xué)會(huì)比較各種排序與查找算法的優(yōu)劣。3、學(xué)會(huì)針對(duì)所給問(wèn)題選用最適合的算法。4、掌握利用常用的排序與選擇算法的思想來(lái)解決一般問(wèn)題的方法和技巧。二、實(shí)驗(yàn)內(nèi)容問(wèn)題描述對(duì)學(xué)生的基本信息進(jìn)行管理。 基本要求設(shè)計(jì)一個(gè)學(xué)生信息管理系統(tǒng)，學(xué)生對(duì)象至少要包含：學(xué)號(hào)、姓名、性別、成績(jī)1、成績(jī)2、總成績(jī)等信息。要求實(shí)現(xiàn)以下功能：1總成績(jī)要求自動(dòng)計(jì)算；2查詢：分別給定學(xué)生學(xué)號(hào)、姓名、性別，能夠查找到學(xué)生的基本信息（要求至少用兩種查找算法實(shí)現(xiàn)）；3 排序：分別按學(xué)生的學(xué)號(hào)、成績(jī)1、成績(jī)2、總成績(jī)進(jìn)行排序（要求至少用兩種排序

2、算法實(shí)現(xiàn)）。測(cè)試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握哈希表的定義，哈希函數(shù)的構(gòu)造方法。2、掌握一些常用的查找方法。1、掌握幾種常用的排序方法。2、掌握直接排序方法。四、實(shí)驗(yàn)報(bào)告要求1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。五、算法設(shè)計(jì)a、 折半查找設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的下界、上界和中點(diǎn),key為給定值。初始時(shí)，令low=1,high=n,mid=(low+high)/2，讓key與mid指向的記錄比較， 若key=rmid.key，查找成功 若key

3、rmid.key，則low=mid+1重復(fù)上述操作，直至lowhigh時(shí)，查找失敗b、順序查找從表的一端開(kāi)始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。在這里從表尾開(kāi)始并把下標(biāo)為0的作為哨兵。void chaxun(SqList &ST) /查詢信息 coutn*endl;cout (1)根據(jù)學(xué)號(hào)查詢 endl;cout (2)根據(jù)姓名查詢 endl;cout (3)根據(jù)性別查詢 endl;cout (4)退出 endl;cout*endl;if(m=1)折半查找算法： for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.xuehao)LI=ST.rj;ST.rj=ST

4、.rj-1;ST.rj-1=LI;int a=0;cout輸入要查找的學(xué)號(hào)n;int low,high,mid;low=0;high=ST.length-1; / 置區(qū)間初值while (low=high) mid=(low+high)/2;if(n=ST.rmid.xuehao) coutST.rmid.xuehao ST.rmid.xingming ST.rmid.xingbei ST.rmid.chengji1 ST.rmid.chengji2 ST.rmid.zongendl;a=1;break;else if(nST.rmid.xuehao )high=mid-1; / 繼續(xù)在前半?yún)^(qū)

5、間進(jìn)行查找else low=mid+1; / 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 順序查找算法: cout輸入要查找的姓名name; for(int i=0;iST.length;i+) if(name=ST.ri.xingming) coutST.ri.xuehao ST.ri.xingming ST.ri.xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zongendl; a=1; 1、 插入排序 每步將一個(gè)待排序的記錄，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組記錄的適當(dāng)位置上，直到記錄全部插入為止。 /按學(xué)號(hào)排序，使用插入排序RecordType LI; /

6、定義存儲(chǔ)學(xué)號(hào)向量for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;2、選擇排序首先通過(guò)n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換再通過(guò)n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束。 /按成績(jī)1排序,用選擇排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.chengji1)LI=ST.rj;S

7、T.rj=ST.ri;ST.ri=LI; 六、運(yùn)行測(cè)試結(jié)果輸入學(xué)生信息以多種方式進(jìn)行查找按總成績(jī)進(jìn)行排序六、實(shí)驗(yàn)總結(jié) 通過(guò)本次實(shí)驗(yàn)我對(duì)查找排序的應(yīng)用有了一定得了解，知道了各種查找排序的基本知識(shí)。 同時(shí)，通過(guò)自己數(shù)次的調(diào)試、修改也搞懂了許多以前比較模糊的知識(shí)點(diǎn)，比如這次的界面是復(fù)制過(guò)來(lái)的，其中很多語(yǔ)句經(jīng)過(guò)同學(xué)的講解都理解了。但這次實(shí)驗(yàn)也有很多不盡人意的地方，我將在以后多學(xué)習(xí)同學(xué)優(yōu)秀的地方也會(huì)在以后的學(xué)習(xí)過(guò)程中要盡量考慮周全，使程序更有實(shí)用價(jià)值，提高編程能力。七、源代碼#include using namespace std;#include #define MAXSIZE 100 /設(shè)記錄不超過(guò)

8、20個(gè)typedef struct /定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu) string xingming; /姓名 string xingbei; /性別 float xuehao; /學(xué)號(hào) float chengji1,chengji2; /成績(jī)1，成績(jī)2 float zong; /總分RecordType;typedef struct /定義順序表的結(jié)構(gòu) RecordType r MAXSIZE +1 ; /存儲(chǔ)順序表的向量 int length; /順序表的長(zhǎng)度SqList;void caidan(SqList &ST);void CreatList(SqList &ST)/創(chuàng)建學(xué)生的相關(guān)信

9、息cout輸入學(xué)生個(gè)數(shù)ST.length;for(int i=0;iST.length;i+) cout輸入第i+1學(xué)生的信息endl;cout學(xué)號(hào)ST.ri.xuehao;cout姓名ST.ri.xingming;cout性別ST.ri.xingbei;cout成績(jī)1ST.ri.chengji1;cout成績(jī)2ST.ri.chengji2;cout輸入完畢endl;void zong(SqList &ST) /計(jì)算總分 for(int i=0;iST.length;i+)ST.ri.zong=ST.ri.chengji1+ST.ri.chengji2;void shuchu(SqList &

10、ST)/輸出cout學(xué)生的信息如下endl;cout學(xué)號(hào) 姓名 性別 成績(jī)1 成績(jī)2 總分 endl;for(int i=0;iST.length;i+)coutST.ri.xuehao ST.ri.xingming ST.ri.xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zong endl;void chaxun(SqList &ST) /查詢信息l1:coutendl;cout(1)根據(jù)學(xué)號(hào)查詢endl;cout(2)根據(jù)姓名查詢endl;cout(3)根據(jù)性別查詢endl;cout(4)退出m;if(m=1) /折半查找RecordType L

11、I; /使學(xué)號(hào)變?yōu)橛行騠or(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;l2:int a=0;cout輸入要查找的學(xué)號(hào)n;int low,high,mid;low=0;high=ST.length-1; / 置區(qū)間初值while (low=high) mid=(low+high)/2;if(n=ST.rmid.xuehao) coutST.rmid.xuehao ST.rmid.xingming ST.rmid.xingbei ST.rmid.chengji1 ST.rmid.c

12、hengji2 ST.rmid.zongendl;a=1;break;else if(nST.rmid.xuehao )high=mid-1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找else low=mid+1; / 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找if(!a)cout所查信息不存在!endl;cout請(qǐng)重新輸入endl;goto l2; goto l1;if(m=2) /順序查找l3:int a=0; cout輸入要查找的姓名name; for(int i=0;iST.length;i+) if(name=ST.ri.xingming) coutST.ri.xuehao ST.ri.xingming ST.ri.

13、xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zongendl; a=1; if(!a) cout所查信息不存在!endl; cout請(qǐng)重新輸入endl; goto l3; goto l1;if(m=3) /順序查找 l4:int a=0; cout輸入要查找性別xb; for(int i=0;iST.length;i+) if(xb=ST.ri.xingbei) coutST.ri.xuehao ST.ri.xingming ST.ri.xingbei ST.ri.chengji1 ST.ri.chengji2 ST.ri.zongendl; a=1

14、; if(!a) cout所查信息不存在!endl; cout請(qǐng)重新輸入endl; goto l4; goto l1;if(m=4) caidan(ST);void paixu(SqList &ST) /排序l1:int n;coutendl;cout(1)根據(jù)學(xué)號(hào)排序endl;cout(2)根據(jù)成績(jī)1排序endl;cout(3)根據(jù)成績(jī)2排序endl;cout(4)根據(jù)總成績(jī)排序endl;cout(5)退出;coutn;if(n=1) /按學(xué)號(hào)排序，使用插入排序RecordType LI; /定義存儲(chǔ)學(xué)號(hào)向量for(int i=1;i=1;j-)if(ST.rj.xuehaoST.rj-1.

15、xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI; shuchu(ST);cout排序完畢endl;goto l1;if(n=2) /按成績(jī)1排序,用選擇排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.chengji1)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;shuchu(ST);cout排序完畢endl;goto l1;if(n=3) / 根據(jù)成績(jī)2排序,使用選擇法排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.chengji2)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;shuchu(ST);cout排序完畢endl;goto l1;if(n=4) /根據(jù)總成績(jī)排序,使用選擇法排序RecordType LI; for(int i=0; iST.length;i+)for (int j=i+1;jST.rj.zong)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;shuchu(