查找、排序的應(yīng)用實(shí)驗(yàn)報(bào)告

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ì)所給問題選用最適合的算法。4、掌握利用常用的排序與選擇算法的思想來解決一般問題的方法和技巧。二、實(shí)驗(yàn)內(nèi)容 問題描述 對(duì)學(xué)生的基本信息進(jìn)行管理。 基本要求 設(shè)計(jì)一個(gè)學(xué)生信息管理系統(tǒng)，學(xué)生對(duì)象至少要包含： 學(xué)號(hào)、姓名、性別、成績1、成績 2、總成績等信息。要求實(shí)現(xiàn)以下功能：1總成績要求自動(dòng)計(jì)算；2查詢：分別給定學(xué)生學(xué)號(hào)、姓名、性別，能夠查找到學(xué)生的基本信息（要求至少用兩種查找算法實(shí)現(xiàn)） ；3排序：分別按學(xué)生的學(xué)號(hào)、成績1、成績 2、總成績進(jìn)行排序（要求至少

2、用兩種排序算法實(shí)現(xiàn)） 。 測試數(shù)據(jù) 由學(xué)生依據(jù)軟件工程的測試技術(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)上要寫出多批測試數(shù)據(jù)的運(yùn)行結(jié)果。3、結(jié)合運(yùn)行結(jié)果，對(duì)程序進(jìn)行分析。五、算法設(shè)計(jì)a、折半查找設(shè)表長為n， low 、 high 和 mid 分別指向待查元素所在區(qū)間的下界、上界和中點(diǎn) ,key 為給定值。初始時(shí)，令low=1,high=n,mid=(low+high)/2，讓key 與 mid 指向的記錄比較，若

3、key=rmid.key，查找成功若 key<rmid.key，則 high=mid-1若 key>rmid.key，則 low=mid+1重復(fù)上述操作，直至low>high時(shí)，查找失敗b、順序查找從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。 在這里從表尾開始并把下標(biāo)為 0 的作為哨兵。void chaxun(SqList &ST) /查詢信息 cout<<"n*"<<endl; cout<<" (1) 根據(jù)學(xué)號(hào)查詢 "<<endl;cout<<"(2)

4、根據(jù)姓名查詢"<<endl;cout<<"(3)根據(jù)性別查詢"<<endl;cout<<"(4)退出"<<endl;cout<<"*"<<endl;if(m=1)折半查找算法 ：for(int i=1;i<ST.length;i+)/使學(xué)號(hào)變?yōu)橛行騠or(int j=i;j>=1;j-)if(ST.rj.xuehao<ST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;-2精選文

5、庫int a=0;cout<<" 輸入要查找的學(xué)號(hào) "<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1; / 置區(qū)間初值 while (low<=high)mid=(low+high)/2;if(n=ST.rmid.xuehao)cout<<ST.rmid.xuehao<<""<<ST.rmid.xingming<<""<<ST.rmid.xingbei<<&quo

6、t;"<<ST.rmid.chengji1<<""<<ST.rmid.chengji2<<""<<ST.rmid.zong<<endl;a=1;break;else if(n<ST.rmid.xuehao )high=mid-1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 elselow=mid+1;/繼續(xù)在后半?yún)^(qū)間進(jìn)行查找順序查找算法 :cout<<" 輸入要查找的姓名 "<<endl;cin>>name;for(int i

7、=0;i<ST.length;i+)if(name=ST.ri.xingming)cout<<ST.ri.xuehao<<""<<ST.ri.xingming<<""<<ST.ri.xingbei<<""<<ST.ri.chengji1<<"-3精選文庫"<<ST.ri.chengji2<<""<<ST.ri.zong<<endl;a=1;1、插入

8、排序每步將一個(gè)待排序的記錄， 按其關(guān)鍵碼大小， 插入到前面已經(jīng)排好序的一組記錄的適當(dāng)位置上，直到記錄全部插入為止。/按學(xué)號(hào)排序，使用插入排序RecordType LI;/定義存儲(chǔ)學(xué)號(hào)向量for(int i=1;i<ST.length;i+)for(int j=i;j>=1;j-)if(ST.rj.xuehao<ST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;2、選擇排序首先通過 n-1 次關(guān)鍵字比較，從 n 個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換再通過 n-2 次比較，從剩余的 n-1 個(gè)記錄中找出關(guān)鍵字次小的記錄

9、，將它與第二個(gè)記錄交換重復(fù)上述操作，共進(jìn)行n-1 趟排序后，排序結(jié)束。/ 按成績 1 排序 , 用選擇排序RecordType LI;for(int i=0; i<ST.length;i+)for (int j=i+1;j<ST.length;j+) if(ST.ri.chengji1>ST.rj.chengji1)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;-4精選文庫六、運(yùn)行測試結(jié)果輸入學(xué)生信息以多種方式進(jìn)行查找-5精選文庫按總成績進(jìn)行排序六、實(shí)驗(yàn)總結(jié)通過本次實(shí)驗(yàn)我對(duì)查找排序的應(yīng)用有了一定得了解，知道了各種查找排序的基本知識(shí)。 同時(shí)，通過自己數(shù)次的調(diào)試、修

10、改也搞懂了許多以前比較模糊的知識(shí)點(diǎn)，比如這次的界面是復(fù)制過來的，其中很多語句經(jīng)過同學(xué)的講解都理解了。 但這次實(shí)驗(yàn)也有很多不盡人意的地方， 我將在以后多學(xué)習(xí)同學(xué)優(yōu)秀的地方 也會(huì)在以后的學(xué)習(xí)過程中要盡量考慮周全， 使程序更有實(shí)用價(jià)值， 提高編程能力。-6精選文庫七、源代碼#include <iostream>using namespace std;#include <string>#define MAXSIZE 100 /設(shè)記錄不超過20 個(gè)typedef struct /定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)string xingming;/姓名string xingbei;/性

11、別float xuehao;/學(xué)號(hào)float chengji1,chengji2;/成績 1，成績 2float zong;/總分RecordType;typedef struct /定義順序表的結(jié)構(gòu)RecordType r MAXSIZE +1 ; /存儲(chǔ)順序表的向量int length; /順序表的長度SqList;void caidan(SqList &ST);void CreatList(SqList &ST)/創(chuàng)建學(xué)生的相關(guān)信息cout<<" 輸入學(xué)生個(gè)數(shù)"<<endl;cin>>ST.length;for(in

12、t i=0;i<ST.length;i+)cout<<" 輸入第 "<<i+1<<" 學(xué)生的信息 "<<endl; cout<<" 學(xué)號(hào) "<<endl;cin>>ST.ri.xuehao;cout<<" 姓名 "<<endl;cin>>ST.ri.xingming;cout<<" 性別 "<<endl;cin>>ST.ri.xingb

13、ei;cout<<" 成績 1"<<endl;cin>>ST.ri.chengji1;cout<<" 成績 2"<<endl;cin>>ST.ri.chengji2;-7精選文庫cout<<" 輸入完畢 "<<endl;void zong(SqList &ST) /計(jì)算總分for(int i=0;i<ST.length;i+)ST.ri.zong=ST.ri.chengji1+ST.ri.chengji2;void shuch

14、u(SqList &ST)/輸出cout<<" 學(xué)生的信息如下"<<endl;cout<<" 學(xué)號(hào)姓名性別成績 1成績 2總分 "<<endl;for(int i=0;i<ST.length;i+)cout<<ST.ri.xuehao<<""<<ST.ri.xingming<<""<<ST.ri.xingbei<<""<<ST.ri.chengji1&

15、lt;<""<<ST.ri.chengji2<<"" <<ST.ri.zong<<""<<endl;void chaxun(SqList &ST) /查詢信息l1: cout<<endl;cout<<"(1)根據(jù)學(xué)號(hào)查詢 "<<endl;cout<<"(2)根據(jù)姓名查詢 "<<endl;cout<<"(3)根據(jù)性別查詢 "<&

16、lt;endl;cout<<"(4)退出 "<<endl;int n,m;string name;string xb;cin>>m;if(m=1)/折半查找RecordType LI;/使學(xué)號(hào)變?yōu)橛行騠or(int i=1;i<ST.length;i+)for(int j=i;j>=1;j-)-8精選文庫if(ST.rj.xuehao<ST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;l2: int a=0;cout<<" 輸入要查找的學(xué)號(hào)"

17、<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1;/置區(qū)間初值while (low<=high)mid=(low+high)/2;if(n=ST.rmid.xuehao)cout<<ST.rmid.xuehao<<""<<ST.rmid.xingming<<""<<ST.rmid.xingbei<<""<<ST.rmid.chengji1<<"

18、"<<ST.rmid.chengji2<<" "<<ST.rmid.zong<<endl;a=1;break;else if(n<ST.rmid.xuehao )high=mid-1;/繼續(xù)在前半?yún)^(qū)間進(jìn)行查找elselow=mid+1;/繼續(xù)在后半?yún)^(qū)間進(jìn)行查找if(!a)cout<<" 所查信息不存在!"<<endl;cout<<" 請(qǐng)重新輸入 "<<endl;goto l2;goto l1;if(m=2)/順序查找-9精選

19、文庫l3: int a=0;cout<<"輸入要查找的姓名"<<endl;cin>>name;for(int i=0;i<ST.length;i+)if(name=ST.ri.xingming)cout<<ST.ri.xuehao<<""<<ST.ri.xingming<<""<<ST.ri.xingbei<<""<<ST.ri.chengji1<<""<

20、;<ST.ri.chengji2<<" "<<ST.ri.zong<<endl;a=1;if(!a)cout<<"所查信息不存在!"<<endl;cout<<"請(qǐng)重新輸入 "<<endl;goto l3;goto l1;if(m=3)/順序查找l4: int a=0;cout<<"輸入要查找性別"<<endl;cin>>xb;for(int i=0;i<ST.length;i+)if(

21、xb=ST.ri.xingbei)cout<<ST.ri.xuehao<<""<<ST.ri.xingming<<""<<ST.ri.xingbei<<""<<ST.ri.chengji1<<""<<ST.ri.chengji2<<" "<<ST.ri.zong<<endl;a=1;if(!a)-10精選文庫cout<<"所查信息不

22、存在!"<<endl;cout<<"請(qǐng)重新輸入 "<<endl;goto l4;goto l1;if(m=4)caidan(ST);void paixu(SqList &ST)/排序l1: int n;cout<<endl;cout<<"(1)根據(jù)學(xué)號(hào)排序 "<<endl;cout<<"(2)根據(jù)成績1 排序 "<<endl;cout<<"(3)根據(jù)成績2 排序 "<<endl;

23、cout<<"(4)根據(jù)總成績排序"<<endl;cout<<"(5)退出 "cout<<endl;cin>>n;if(n=1)/按學(xué)號(hào)排序，使用插入排序RecordType LI;/定義存儲(chǔ)學(xué)號(hào)向量for(int i=1;i<ST.length;i+)for(int j=i;j>=1;j-)if(ST.rj.xuehao<ST.rj-1.xuehao)LI=ST.rj;ST.rj=ST.rj-1;ST.rj-1=LI;shuchu(ST);-11精選文庫cout<<

24、;" 排序完畢 "<<endl;goto l1;if(n=2)/按成績 1 排序 , 用選擇排序RecordType LI;for(int i=0; i<ST.length;i+)for (int j=i+1;j<ST.length;j+)if(ST.ri.chengji1>ST.rj.chengji1)LI=ST.rj;ST.rj=ST.ri;ST.ri=LI;shuchu(ST);cout<<" 排序完畢 "<<endl;goto l1;if(n=3)/根據(jù)成績2 排序 , 使用選擇法排序RecordType