數(shù)據(jù)結(jié)構(gòu)試驗(yàn)哈希表

..第10章實(shí)驗(yàn)實(shí)驗(yàn)名稱：考試日程安排與成績統(tǒng)計(jì)實(shí)驗(yàn)類型：綜合性性實(shí)驗(yàn)__20100611__2010061118__郭鑫問題描述=1\*GB3①問題描述現(xiàn)要安排考試的考表〔即考試日程表,假設(shè)共有10個班的學(xué)生,要安排10門必修課程的考試,必修課程是以班級來確定的,每個班各有3門必修課,因此各班的考試科目是不相同的；安排考表的原則是：相同課程采用統(tǒng)一的試卷,因此同一門課程的考試必須在相同時間進(jìn)行,同一個班所修的科目必須安排在不同的時間進(jìn)行考試,以避免考試時間的沖突。并要求全部考試的日程盡可能短。要求對考試結(jié)果做統(tǒng)計(jì)和排序。假設(shè)分別以編號0,1,2,3,4,5,6,7,8,9代表10門要考試的課程,以B1,B2,B3,B4,B5,B6,B7,B8,B9,B10代表10個班,每個人的信息包括學(xué)號、姓名、班級、各門考試課程成績、三門課程總成績,每個班的學(xué)生人數(shù)自行設(shè)定。要求設(shè)計(jì)一個簡單的考試成績的查詢統(tǒng)計(jì)系統(tǒng)實(shí)現(xiàn)以下功能：顯示學(xué)生考試情況-按考試總分從高到底輸出全體學(xué)生的信息。-按照從B1到B10的班級順序,分班級按照考試總分從高到底的順序輸出各班學(xué)生的信息。-輸出指定班的學(xué)生考試成績信息。統(tǒng)計(jì)學(xué)生考試成績-按總成績統(tǒng)計(jì)出90分以上、80~89分、70~79分、60~69分、60分以下各分?jǐn)?shù)段的人數(shù),并按總分從高到低分段輸出。-根據(jù)指定的某們課程的成績,統(tǒng)計(jì)出上述各分?jǐn)?shù)段的人數(shù),并按分?jǐn)?shù)從高到低分段輸出。-統(tǒng)計(jì)并輸出指定班級中總成績或某一門課成績的各分?jǐn)?shù)段人數(shù)和每個人具體的信息。查找學(xué)生成績

-查找總分或某一門課程成績的指定分?jǐn)?shù)段的人數(shù)及學(xué)生的詳細(xì)信息。-查找指定班級中總分或某一門課程成績屬于某分?jǐn)?shù)段的學(xué)生詳細(xì)信息。-查找指定學(xué)生〔例如給定學(xué)號的具體信息,包括：姓名、班級、各科分?jǐn)?shù)、總分?jǐn)?shù)等。=2\*GB3②求解方法說明考試日程安排問題。該問題實(shí)際上是對若干元素進(jìn)行子集劃分的問題,要求所劃分的每個子集中的元素沒有"考試沖突"關(guān)系。假設(shè)各個班的考試課程分別為：<1,4,8>,<1,3,7>,<8,2,4>,<1,0,5>,<2,6,9>,<3,0,8>,<4,5,9>,<2,9,7>,<6,0,3>,<5,6,9>。根據(jù)題中考試安排原則,各個班要進(jìn)行的考試課程可以抽象為"考試沖突關(guān)系",歸納各個班的考試課程可以整理得到考試沖突關(guān)系：R={<1,4>,<1,8>,<4,8>,<1,3>,<1,7>,<3,7>,<8,2>,<2,4>,<1,0>,<1,5>,<0,5>,<2,6>,<2,9>,<6,9>,<3,0>,<0,8>,<3,8>,<4,5>,<5,9>,<4,5>,<2,7>,<9,7>,<6,0>,<6,3>,<5,6>}。顯然,"考試沖突"關(guān)系R的每個有序?qū)χ械膬砷T課程不能安排在同一時間考試,據(jù)此可以將10門課劃分為若干個考試時間沒有沖突的子集,并且使考場的場次盡量少,使得整個考試時間盡可能短。上述子集劃分問題可以用對集合中的元素逐個"篩選"的辦法來解決。首先將集合的第1個元素置為第1個子集,再逐個檢查集合中的其余元素是否和第1個元素有考試沖突,若不存在考試沖突,則將其加入到第1個子集中,繼續(xù)檢查集合中的其余元素,凡是不與第1個子集中的元素沖突的元素都逐個將其加入到其中；接著按同樣的方法"篩選"出若干沒有考試沖突的元素構(gòu)成第2個子集,…,該過程一直到集合中的全部元素都分到某個子集中結(jié)束。得到的每一個子集中的課程就是可以安排在同一時間考試的課程。不同子集的課程則要安排在不沖突的時間考試?？荚嚪?jǐn)?shù)的統(tǒng)計(jì)與排序考試成績輸出每個學(xué)生的信息記錄數(shù)據(jù)項(xiàng)應(yīng)包括：學(xué)號、姓名、班級、課程1、課程2、…、課程10、總成績。按總分高低輸出所有學(xué)生信息時,應(yīng)該以總成績?yōu)殛P(guān)鍵字從高分到低分對所有的學(xué)生記錄進(jìn)行排序,排序方法自行選定,然后依次輸出各個記錄。按照班級順序和總分高低輸出各班學(xué)生信息時,要對學(xué)生記錄進(jìn)行多關(guān)鍵字排序,首先以總成績?yōu)殛P(guān)鍵字從高分到低分對所有的學(xué)生記錄進(jìn)行排序,然后再以班號為關(guān)鍵字對全部學(xué)生記錄排序,再輸出結(jié)果。統(tǒng)計(jì)成績統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù),要求由用戶輸入,具體要求可以有：按照總成績統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù),并輸出各分?jǐn)?shù)段的學(xué)生記錄,即在統(tǒng)計(jì)一個分?jǐn)?shù)段的人數(shù)過程中,要輸出滿足查找條件的學(xué)生記錄,再輸出統(tǒng)計(jì)的結(jié)果。指定某一門課程,統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)并輸出各分?jǐn)?shù)段的學(xué)生記錄。對指定班級中總成績或指定課程成績做各分?jǐn)?shù)段人數(shù)的統(tǒng)計(jì),也要輸出各分?jǐn)?shù)段的學(xué)生記錄。查找成績查找要求由用戶輸入,可以輸入以下條件：查找指定分?jǐn)?shù)項(xiàng)〔總分或某一門課程的某分?jǐn)?shù)段的學(xué)生信息,輸出查找結(jié)果。查找指定班級、指定分?jǐn)?shù)項(xiàng)的某分?jǐn)?shù)段的學(xué)生信息,輸出查找結(jié)果。查找指定學(xué)生〔給定學(xué)號的具體信息,輸出查找結(jié)果。③算法提示考試場次的劃分——"無考試沖突"子集劃分的算法思路。為了把10門課程劃分為時間上不沖突的若干場考試,可以利用一個循環(huán)隊(duì)列來實(shí)現(xiàn)求解方法中說明的"篩選"過程。首先定義一個循環(huán)隊(duì)列,再把10門課程的編號從小到大依次加入到循環(huán)隊(duì)列中,然后重復(fù)下列步驟：隊(duì)頭元素出隊(duì)并作為當(dāng)前子集的第1個元素。隊(duì)頭元素繼續(xù)依次出隊(duì),每出隊(duì)一個隊(duì)頭元素都要檢查與當(dāng)前子集中的元素是否有"考試沖突"；如果沒有沖突,則將其加入到當(dāng)前子集中,否則將其重新加入隊(duì)列中,等待以后加入新子集的機(jī)會。比較剛出隊(duì)元素與前一出隊(duì)元素編號。因?yàn)殛?duì)列中原有的元素是以編號從小到大的順序排列的,重新入隊(duì)的元素編號一定小于它的前一元素,所以一旦發(fā)現(xiàn)目前出隊(duì)的元素編號小于前一個出隊(duì)的元素,就可以斷定當(dāng)前的"考試沖突"子集已經(jīng)構(gòu)建完,隊(duì)列中剩余元素應(yīng)該構(gòu)建新的子集。為此,在當(dāng)前的隊(duì)頭元素出隊(duì)前,要先記下剛剛出隊(duì)的元素,以便判斷當(dāng)前出隊(duì)的元素是否要開始構(gòu)建一個新子集。重復(fù)上述步驟一直到隊(duì)列空,則"無考試沖突"子集劃分完成。由上述算法思路可以知道,"無考試沖突"子集的劃分過程是一個循環(huán)的執(zhí)行過程,循環(huán)中的主要操作是元素出隊(duì)和判斷的操作。判斷操作包括出隊(duì)元素是否可以加入當(dāng)前子集和是否要開始構(gòu)建一個新子集兩個方面,對后一個判斷如前所述,通過比較出隊(duì)元素與前一個出隊(duì)元素編號大小可以確定。為了判斷出隊(duì)元素與當(dāng)前子集中的元素是否有"考試沖突",可以定義一個二維數(shù)組conf[n][n]來表示課程的考試沖突關(guān)系矩陣,矩陣中各元素的值根據(jù)以下規(guī)則確定,若編號為i的課程和編號為j的課程有考試沖突,則置conf[i][j]=1,否則置conf[i][j]=0,考試沖突關(guān)系矩陣如圖1所示。0101011010100111011000001011111100001110011001001111001010011011010001011100000111111000000010111100圖1考試沖突關(guān)系矩陣?yán)?考試沖突"關(guān)系矩陣可以檢查出隊(duì)元素i是否與當(dāng)前子集中的元素有考試沖突,其方法是：當(dāng)課程號為j1,j2,…,jk的元素已經(jīng)在當(dāng)前子集S中,要判斷目前出隊(duì)的元素i是否可以加入子集S,只要檢查"考試沖突"關(guān)系矩陣中第i行的元素conf[i][j1],conf[i][j2],…conf[i][jk]的值是否為0即可。如果這些元素的值都為0,表示課程i與子集中的課程沒有考試沖突,可以加入其中,否則說明表示課程i與子集中的某些課程有考試沖突,它不能加入該子集中。為了減少在二維數(shù)組conf中查找元素的操作,可以定義一個一維數(shù)組clash[n]來方便出隊(duì)元素i是否要加入當(dāng)前子集的判斷,數(shù)組clash[n]用于記錄出隊(duì)元素i與當(dāng)前子集中的元素是否存在考試沖突的信息。每當(dāng)開始構(gòu)建一個新子集時,先將數(shù)組clash[n]的各元素初始化為0,當(dāng)有編號為i的課程加入子集時,將"考試沖突"關(guān)系矩陣中第i行的各列的值與數(shù)組clash的各對應(yīng)元素的值相加,因而使得數(shù)組clash中和編號為i的元素有考試沖突的相應(yīng)元素的值不再是0,當(dāng)下一個隊(duì)頭元素j出隊(duì)時,只要檢查數(shù)組clash中第j個元素的值是否為0,就可以判斷其是否與當(dāng)前子集中的元素有考試沖突；若數(shù)組clash中第j個元素的值不為0,則說明元素j與當(dāng)前子集中元素存在考試沖突,應(yīng)將其重新加入隊(duì)列；若數(shù)組clash中第j各元素的值為0,則說明它與當(dāng)前子集中元素不存在考試沖突,應(yīng)該將它加入當(dāng)前子集中,同時要將"考試沖突"關(guān)系矩陣中第j行的各列的值與數(shù)組clash的各對應(yīng)元素的值相加,這個過程一直到隊(duì)列空,則劃分無考試沖突子集完成。劃分結(jié)果可以用一個二維數(shù)組來記錄各子集中的元素的方式來表示,也可以用一個一維數(shù)組來記錄每個元素其所屬的子集號的方式來表示。上述算法的思路可以描述如下：建立表示課程考試沖突關(guān)系矩陣的二維數(shù)組conf[n][n]；定義用于檢查當(dāng)前子集的課程考試沖突信息的數(shù)組clash[n]；定義用于記錄子集劃分結(jié)果的數(shù)組result[n]；pre=n; //pre用于記錄前一個出隊(duì)元素的編號,初始值置為n以新建第1個子集k=0； //k用于記錄子集序號0~9<課程編號>依次入隊(duì)；while〔隊(duì)列不空{(diào) 隊(duì)頭元素i出隊(duì)； if<i<pre> //剛出隊(duì)元素小于前一個出隊(duì)元素,生成一個新子集 { k++; 數(shù)組clash初始化；}if<i可以加入當(dāng)前子集> //如果剛出隊(duì)元素與當(dāng)前子集中的元素?zé)o考試沖突,將其加入當(dāng)前子集 { 將i加入當(dāng)前子集,記錄i所屬子集的序號； 將conf數(shù)組第i行各列的值與clash數(shù)組對應(yīng)列的值相加并記入clash中；}else//如果剛出隊(duì)元素與當(dāng)前子集中的元素有考試沖突,將其重新入隊(duì) 將i重新加入隊(duì)列；pre=i;}考試成績統(tǒng)計(jì)和排序的實(shí)現(xiàn)按總成績或按某一門課的成績統(tǒng)計(jì)并輸出人數(shù)時,應(yīng)該使各分?jǐn)?shù)段的人數(shù)和每個學(xué)生的信息清晰的分開。對全體學(xué)生或?qū)δ骋粋€班的學(xué)生的成績進(jìn)行排序時,排序方法可以任意選擇。就本實(shí)驗(yàn)問題而言,因表長不大采用簡單的排序方法就可以達(dá)到目的,但為了比較各種常用排序方法性能和適用場合,還可以采用不同的排序方法實(shí)現(xiàn)排序。對多關(guān)鍵字的排序要求,要注意排序方法的穩(wěn)定性問題。例如,在按總成績從高分到低分對全體學(xué)生進(jìn)行排序后,再按班級從高分到低分進(jìn)行排序,此時要求分班級排序時采用的排序方法其動態(tài)性能必須是穩(wěn)定的。同樣地,如果在按總成績從高分到低分排序的基礎(chǔ)上,再要求按某一門課的成績從高分到低分排序,也要求第2層排序一定注意選擇動態(tài)性能穩(wěn)定的排序方法。在實(shí)現(xiàn)查找或排序功能時,其查找或排序的依據(jù)〔指定項(xiàng)和目標(biāo)〔輸出結(jié)果通過提示用戶輸入來確定。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)typedefintKeyType;typedefcharInfoType[10];typedefstruct /*記錄類型*/{ KeyTypekey; /*關(guān)鍵字項(xiàng)*/InfoTypedata; /*其他數(shù)據(jù)項(xiàng),類型為InfoType*/}RecType算法設(shè)計(jì)#include<iostream>usingnamespacestd;#defineMAXE20 /*線性表中最多元素個數(shù)*/typedefintKeyType;typedefcharInfoType[10];typedefstruct /*記錄類型*/{ KeyTypekey; /*關(guān)鍵字項(xiàng)*/InfoTypedata; /*其他數(shù)據(jù)項(xiàng),類型為InfoType*/}RecType;voidSelectSort<RecTypeR[],intn> /*直接選擇排序算法*/{ inti,j,k,l; RecTypetemp; for<i=0;i<n-1;i++> /*做第i趟排序*/ { k=i; for<j=i+1;j<n;j++> /*在當(dāng)前無序區(qū)R[i..n-1]中選key最小的R[k]*/ if<R[j].key<R[k].key> k=j; /*k記下目前找到的最小關(guān)鍵字所在的位置*/ if<k!=i> /*交換R[i]和R[k]*/ { temp=R[i];R[i]=R[k];R[k]=temp; } printf<"i=%d",i>; /*輸出每一趟的排序結(jié)果*/ for<l=0;l<n;l++> printf<"%2d",R[l].key>; printf<"\n">; }}intmain<>{ inti,k,n=10,m=5; KeyTypea[]={6,8,7,9,0,1,3,2,4,5}; RecTypeR[MAXE]; for<i=0;i<n;i++> R[i].key=a[i]; printf<"\n">; printf<"初始關(guān)鍵字">; /*輸出初始關(guān)鍵字序列*/ for<k=0;k<n;k++> printf<"%2d",R[k].key>; printf<"\n">; SelectSort<R,n>; printf<"最后結(jié)果">; /*輸出初始關(guān)鍵字序列*/ f