實(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、掌握運(yùn)用常用的排序與選擇算法的思想來解決一般問題的方法和技巧。二、實(shí)驗(yàn)內(nèi)容［問題描述］對(duì)學(xué)生的基本信息進(jìn)行管理。［基本規(guī)定］設(shè)計(jì)一個(gè)學(xué)生信息管理系統(tǒng)，學(xué)生對(duì)象至少要包含：學(xué)號(hào)、姓名、性別、成績(jī)1、成績(jī)2、總成績(jī)等信息。規(guī)定實(shí)現(xiàn)以下功能：.總成績(jī)規(guī)定自動(dòng)計(jì)算；.查詢：分別給定學(xué)生學(xué)號(hào)、姓名、性別，可以查找到學(xué)生的基本信息（規(guī)定至少用兩種查找算法實(shí)現(xiàn)）；.排序:分別按學(xué)生的學(xué)號(hào)、成績(jī)1、成績(jī)2、總成績(jī)進(jìn)行排序（規(guī)定至少用兩種排序算法實(shí)現(xiàn)）。［測(cè)試數(shù)據(jù)］由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己擬定。voidCreatList(SqList&ST)〃創(chuàng)建學(xué)生的相關(guān)信息coutV<〃輸入學(xué)生個(gè)數(shù)"<<endl;。cin>>ST.length;ofor(inti=0;i<ST.length;i++)(coutV<"輸入第"<<i+1<<〃學(xué)生的信息”<<endl；cout<<〃學(xué)號(hào)”d1;cin?ST.r[i].xuehao;cou〃姓名〃《endl；??cin>>ST.r[i].xingming;acout<<"性別"V<endl；ocin>>ST.r[i].xingbei；coutV<"成績(jī)r(jià)\<end1；cin?ST.r[i].chengji1;cout?成績(jī)2z，<<endl；cin>>ST.r[i].chengji2；)ocout<<〃輸入完畢"?endl；)voidzong(SqList&ST)〃計(jì)算總分

for(inti=0；i<ST.length；i++)。ST.r[i].zong=ST.r[i].chengjil+ST.r[i].chengji2;。})voidshuchu(SqList&ST)//輸出{0cout<〈〃學(xué)生的信息如下?end1；cout?"學(xué)號(hào)姓名性別成績(jī)1成績(jī)2總分“VVendl;for(inti=0;i<ST.1ength;i++)(cout<<ST.r[i].xuehao<<?，”<<ST.r[i].xingming<<"/Z?ST.r[i].xingbei<<，z"?ST.r[i].chengjilV<〃Z，Z，<<ST.r[i].Z，<<ST.r[i].chengji2?Z，<<ST.r[i].chengji2?/z“K〈ST.r[i].zong<<zz/z<<end1;voidchaxunvoidchaxunvoidchaxun(SqList&ST)//voidchaxun(SqList&ST)//查詢信息11：acout?end1；cout久〃（1）根據(jù)學(xué)號(hào)查詢”“endl;coutvv(2)根據(jù)姓名查詢”<<end1;ocout?z，(3)根據(jù)性別查詢〃。end1;cout?，z(4)退出"<<endl；intn,m；stringname;stringxb；cin>>m；?if(m=二1)//折半查找6{oRecordTypeLI;〃使學(xué)號(hào)變?yōu)橛行蚪黲Minti=1；i<ST.length；i++)?for(intj=i；j>=l;j)。if(ST.r[j].xuehao<ST.r[j-1].xuehao)(gLI=ST.r[j];。ST.r[j]=ST.r[j-l];ooST.r[j-1]=LI;o}12:inta=0;cout?"輸入要查找的學(xué)號(hào)?endl;cin?n;。int1ow,high,mid;//置區(qū)間初值ow=0;//置區(qū)間初值while(1ow<=high)(oomid=(low+high)/2;。if(n==ST.r[mid].xuehao)g{cout<<ST.r[mid].xuehao?""<<ST.r[mid].xingming<<z/Z，?ST.r[mid].xingbei<</zZ，<<ST.r[mid].chengji1<<Z,z，<<ST.r[mid].chengji2<<"”<XST.r[mid].zong<<endl;°a=1;obreak;0)oelseif(n<ST.r[mid].xuehao)ohigh=mid-l;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找e1se。low=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找。}oif(!a)(coutV〈〃所查信息不存在！〃VVendl;cout<〈"請(qǐng)重新輸入Vend1；goto12;if(m==2)//順序查找(13:inta=0;cout。〃輸入耍查找的姓名〃<Vendl;cin?name;for(inti=0;i<ST.length；i++)0{if(name==ST.r[i].xingming)?(cout<<ST.r[i].xuehao?z/"<<ST.r[i].xingming<<"Z，?ST.r[i].xingbei?z/，Z<<ST.r[i].chengjil?z，Z/<<ST.r.chengji2<<z，，Z<<ST.r[i].zong<<endl;°a=1;00}}。if(!a)°{8cout<<〃所查信息不存在!"?end1；cout?"請(qǐng)重新輸入"v<end1；goto13;。｝goto11；}if(m==3)//順序查找(14：ointa=0；coutV<〃輸入要查找性別”〈Vendl;cin>>xb;。for(inti=0；i<ST.length;i++)°(oif(xb==ST.r[i].xingbei)?(cout<<ST.r[i].xuehao<<"/z?ST.r[i].xingming<<?/"<<ST.r[i].xingbei<</z，Z<<ST.r[i].chengjil?/，"V<ST.r[i].chengji2<<z，，，<<ST.r[i].zong<<end1；a=l;)}f(!a)coutvv〃所查信息不存在!〃<Xendl;。cout?”請(qǐng)重新輸入〃V<endl;ggoto14;0)0goto11；)if(m==4){?caidan(ST);})voidpaixu(SqList&ST)//排序(:intn;cout?end1；ocout<V〃(l)根據(jù)學(xué)號(hào)排序〃<<end1；cout<V〃(2)根據(jù)成績(jī)l排序"<<endl;ocout?，z(3)根據(jù)成績(jī)2排序〃<<endl;Cout<<〃⑷根據(jù)總成績(jī)排序“<<end1;coutVV"(5)退出”;cout?end1;cin>>n;if(n==l)〃按學(xué)號(hào)排序，使用插入排序。RecordTypeLI；//定義存儲(chǔ)學(xué)號(hào)向量for(inti=l；i<ST.1ength;i++)g「or(intj=i;j>=l;j)if(ST.r[j].xuehao<ST.r[j-l].xuehao)。(oLI=ST.r[j];。ST.r[j]=ST.r[j-1];gST.r[j-l]=LI；力shuchu(ST);ocout排序完畢〃V〈endl;0t011;oif(n==2)//按成績(jī)1排序,用選擇排序3.oRecordTypeLI;gfor(inti=0;i<ST.1ength；i++)for(intj=i+1;j<ST.1ength；j++)

dOOif(ST.r[i].chengjil>ST.r[j].chengjil)dOO000{-LI=ST.r[j];°ST.r[j]=ST.r[i];8aST.r[i]=LI;a010shuchu(ST);outV〈"排序完畢”<Xendl;。goto11;。}，if(n=3)//根據(jù)成績(jī)2排序，使用選擇法排序(oRecordTypeLI;&for(inti=0;i<ST.length;i++)ofor(intj=i+l;j<ST.Iength;j++)00I/if(ST.r[i].chengji2>ST.r[j].chengji2)000j0wLI=ST.r[j];-ST.r[j]=ST.r[i];ooST.rEi]=LI;oshuchu(ST);。cout<V〃排序完畢〃<Vendl;goto11;。}if(n=4)〃根據(jù)總成績(jī)排序，使用選擇法排序{gRecordTypeLI;。for(inti=0;i<ST.length；i++)oofor(intj=i+l；j<ST.1ength;j++)8(0if(ST.r[i].zong>ST.r[j].zong)。(。。LI=ST.rLj];。ST.rEJ]=ST.r[i];qST.r[i]=LI;°}3shuchu(ST);三、實(shí)驗(yàn)前的準(zhǔn)備工作1、掌握哈希表的定義，哈希函數(shù)的構(gòu)造方法。2、掌握一些常用的查找方法。1、掌握幾種常用的排序方法。2、掌握直接排序方法。四、實(shí)驗(yàn)報(bào)告規(guī)定1、實(shí)驗(yàn)報(bào)告要按照實(shí)驗(yàn)報(bào)告格式規(guī)范書寫。2、實(shí)驗(yàn)上要寫出多批測(cè)試數(shù)據(jù)的運(yùn)營(yíng)結(jié)果。3、結(jié)合運(yùn)營(yíng)結(jié)果，對(duì)程序進(jìn)行分析。五、算法設(shè)計(jì)a、折半查找設(shè)表長(zhǎng)為n,1ow、high和mid分別指向待查元素所在區(qū)間的下界、上界和中點(diǎn)，key為給定值。初始時(shí)，令low=1,high=n,inid=(low+high)/2,讓key與mid指向的記錄比較，若key二二r[mid].key,查找成功若key〈r[mid].key,則high=mid-1若key>r[mid].key,則low=mid+1反復(fù)上述操作，直至1ow>high時(shí)，查找失敗b、順序查找youtX〈〃排序完畢“〈〈end1；?goto11;°!oif(n==5)//退出°{ocaidan(ST);。})voidcaidan(SqList&ST)//選擇菜單{?cout?"請(qǐng)選擇要進(jìn)入的模塊"<<endl；?cout?”(l)查詢"?endl;cout?z，(2)排序“<<endl;cout?/，(3)退出〃<<endl;intc;cin?c;if(c==l)?>chaxun(ST);°}4f(c==2)paixu(ST)；)if(c==3)(o?exit(0);))voidmain()(SqListST;oCreatList(ST);zong(ST);oshuchu(ST);caidan(ST);從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。在這里從表尾開始并把下標(biāo)為0的作為哨兵。voidchaxun(SqList&ST)//查詢信息cout〈〈〃\n************************〃VVendl;cout?(1)根據(jù)學(xué)號(hào)查詢?〃VVendl;笛o(2)根據(jù)姓名查詢?〃<Vend1;，cout*”?(3)根據(jù)性別查詢~〃*endl；0cout<〈八(4)退出^z，<<endl;cout<<"************************”<<endl；if(m==l)折半查找算法：for(inti=l;i<ST.length;i++)〃使學(xué)號(hào)變?yōu)橛行騠or(intj=i;j>=l;j—)if(ST.rLj].xuehao<ST.r[j-1].xuehao)ooLI=ST.r[j];6T.rLj]=ST.r[j-l];3ST.r[j-1]=LI;°)ointa=0；ocoutv〈〃輸入要查找的學(xué)號(hào)〃。endl；cin>>n;int1ow,high,mid;ow=0;high=ST.1ength-1；//置區(qū)間初值owhile(1ow<=high)amid=(1ow+high)/2；if(n==ST.r[mid].xuehao)6(cout?ST.r[mid].xuehao<<z，Z，<<ST.r[mid].xingming?M"?ST.r[mid].xingbei<<n〃<VST.r[mid].chengjil<<，z"，<<ST.r[mid].chengji2<<"〃<VST.r[mid].zong<<end1;小1=1;ebreak;g}elseif(n<ST.r[mid].xuehao)。high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找1se//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找順序查找算法：cout<V”輸入要查找的姓名〃<<end1；。cin>>name;for(inti=0;i<ST.1ength;i++){°if(name==ST.r[i].xingming)b{cout<<ST.r[i].xuehao?z，"<<ST.r[i].xingming?，/n?ST.r[i].xingbei?n〃V<ST.r[i].chengjil<<z，"<<ST.r[i].chengji2?''*<<ST.r[i].zong<<endl;°a=l；a}1、插入排序每步將一個(gè)待排序的記錄,按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組記錄的適當(dāng)位置上，直到記錄所有插入為止。//按學(xué)號(hào)排序,使用插入排序-RecordTypeLI;〃定義存儲(chǔ)學(xué)號(hào)向量or(inti=l；i<ST.length;i++)for(intj=i;j>=l;j—)(ST.r[j].xuehao<ST.r[j-1].xuehao)l-LI=ST.r[j];-ST.r[j]=ST.r[j-1];oST.r[j-l]=LI;}2、選擇排序一方面通過n—1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄互換再通過n-2次比較,從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄互換反復(fù)上述操作，共進(jìn)行n—1趟排序后，排序結(jié)束。//按成績(jī)1排序，用選擇排序?>RecordTypeLI;for(inti=0;i<ST.1ength;i++)for(intj=i+1;j<ST.length;j++)?{if(ST.rEi],chengjil>ST.r[j].chengjil)a。{LI=ST.r[j];3ST.r[j]=ST.r[i];00六、運(yùn)營(yíng)測(cè)試結(jié)果輸入學(xué)生信息a超樓心第1學(xué)生的信息學(xué)號(hào)3名zed性別成績(jī)1褊2學(xué)車的宿息如下季號(hào)姓名,性別成績(jī)1成績(jī)2總分1zed99991982eue女89961853noc.■*a■■aaa、■■,男9095185請(qǐng)選擇要進(jìn)入的模塊〈1）查詢<2〉喈亭<3）退出以多種方式進(jìn)行查找〈2〉根據(jù)姓名查詢〈3地囑性剌查詢<4〉退出3輸入要查找性別男1zed男99991983noc男9095185

詢?cè)冊(cè)兤障阆?姓性詢?cè)冊(cè)兤障阆?姓性根〔根〔根封〔_>>>>1234<<<<2詢?cè)冊(cè)兒孟惴?hào)俞