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

1、第10章實驗實驗名稱：考試日程安排與成績統(tǒng)計實驗類型：綜合性性實驗班級：20100611學(xué)號：2010061118姓名：郭鑫1. 問題描述問題描述l 現(xiàn)要安排考試的考表（即考試日程表），假設(shè)共有10個班的學(xué)生，要安排10門必修課程的考試，必修課程是以班級來確定的，每個班各有3門必修課，因此各班的考試科目是不相同的；安排考表的原則是：相同課程采用統(tǒng)一的試卷，因此同一門課程的考試必須在相同時間進(jìn)行，同一個班所修的科目必須安排在不同的時間進(jìn)行考試，以避免考試時間的沖突。并要求全部考試的日程盡可能短。l 要求對考試結(jié)果做統(tǒng)計和排序。假設(shè)分別以編號0,1,2,3,4,5,6,7,8,9代表10門要考試的

2、課程，以B1，B2，B3，B4，B5，B6，B7，B8，B9，B10代表10個班，每個人的信息包括學(xué)號、姓名、班級、各門考試課程成績、三門課程總成績，每個班的學(xué)生人數(shù)自行設(shè)定。要求設(shè)計一個簡單的考試成績的查詢統(tǒng)計系統(tǒng)實現(xiàn)以下功能：² 顯示學(xué)生考試情況-按考試總分從高到底輸出全體學(xué)生的信息。-按照從B1到B10的班級順序，分班級按照考試總分從高到底的順序輸出各班學(xué)生的信息。-輸出指定班的學(xué)生考試成績信息。² 統(tǒng)計學(xué)生考試成績-按總成績統(tǒng)計出90分以上、8089分、7079分、6069分、60分以下各分?jǐn)?shù)段的人數(shù)，并按總分從高到低分段輸出。-根據(jù)指定的某們課程的成績，統(tǒng)計出上述

3、各分?jǐn)?shù)段的人數(shù)，并按分?jǐn)?shù)從高到低分段輸出。-統(tǒng)計并輸出指定班級中總成績或某一門課成績的各分?jǐn)?shù)段人數(shù)和每個人具體的信息。² 查找學(xué)生成績-查找總分或某一門課程成績的指定分?jǐn)?shù)段的人數(shù)及學(xué)生的詳細(xì)信息。-查找指定班級中總分或某一門課程成績屬于某分?jǐn)?shù)段的學(xué)生詳細(xì)信息。-查找指定學(xué)生（例如給定學(xué)號）的具體信息，包括：姓名、班級、各科分?jǐn)?shù)、總分?jǐn)?shù)等。求解方法說明l 考試日程安排問題。² 該問題實際上是對若干元素進(jìn)行子集劃分的問題，要求所劃分的每個子集中的元素沒有“考試沖突”關(guān)系。² 假設(shè)各個班的考試課程分別為：(1,4,8),(1,3,7),(8,2,4),(1,0,5),(

4、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ù)此可以將1

5、0門課劃分為若干個考試時間沒有沖突的子集，并且使考場的場次盡量少，使得整個考試時間盡可能短。² 上述子集劃分問題可以用對集合中的元素逐個“篩選”的辦法來解決。首先將集合的第1個元素置為第1個子集，再逐個檢查集合中的其余元素是否和第1個元素有考試沖突，若不存在考試沖突，則將其加入到第1個子集中，繼續(xù)檢查集合中的其余元素，凡是不與第1個子集中的元素沖突的元素都逐個將其加入到其中；接著按同樣的方法“篩選”出若干沒有考試沖突的元素構(gòu)成第2個子集，該過程一直到集合中的全部元素都分到某個子集中結(jié)束。得到的每一個子集中的課程就是可以安排在同一時間考試的課程。不同子集的課程則要安排在不沖突的時間考試

6、。l 考試分?jǐn)?shù)的統(tǒng)計與排序² 考試成績輸出ü 每個學(xué)生的信息記錄數(shù)據(jù)項應(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)計成績統(tǒng)計各分?jǐn)?shù)段的人數(shù)，要求由用戶輸入，具體要求可以有：ü 按照總成績統(tǒng)計各分?jǐn)?shù)段的

7、人數(shù)，并輸出各分?jǐn)?shù)段的學(xué)生記錄，即在統(tǒng)計一個分?jǐn)?shù)段的人數(shù)過程中，要輸出滿足查找條件的學(xué)生記錄，再輸出統(tǒng)計的結(jié)果。ü 指定某一門課程，統(tǒng)計各分?jǐn)?shù)段的人數(shù)并輸出各分?jǐn)?shù)段的學(xué)生記錄。ü 對指定班級中總成績或指定課程成績做各分?jǐn)?shù)段人數(shù)的統(tǒng)計，也要輸出各分?jǐn)?shù)段的學(xué)生記錄。² 查找成績查找要求由用戶輸入，可以輸入以下條件：ü 查找指定分?jǐn)?shù)項（總分或某一門課程）的某分?jǐn)?shù)段的學(xué)生信息，輸出查找結(jié)果。ü 查找指定班級、指定分?jǐn)?shù)項的某分?jǐn)?shù)段的學(xué)生信息，輸出查找結(jié)果。ü 查找指定學(xué)生（給定學(xué)號）的具體信息，輸出查找結(jié)果。算法提示l 考試場次的劃分“無考試沖

8、突”子集劃分的算法思路。 為了把10門課程劃分為時間上不沖突的若干場考試，可以利用一個循環(huán)隊列來實現(xiàn)求解方法中說明的“篩選”過程。 首先定義一個循環(huán)隊列，再把10門課程的編號從小到大依次加入到循環(huán)隊列中，然后重復(fù)下列步驟：ü 隊頭元素出隊并作為當(dāng)前子集的第1個元素。ü 隊頭元素繼續(xù)依次出隊，每出隊一個隊頭元素都要檢查與當(dāng)前子集中的元素是否有“考試沖突”；如果沒有沖突，則將其加入到當(dāng)前子集中，否則將其重新加入隊列中，等待以后加入新子集的機(jī)會。ü 比較剛出隊元素與前一出隊元素編號。因為隊列中原有的元素是以編號從小到大的順序排列的，重新入隊的元素編號一定小于它的前一元素

9、，所以一旦發(fā)現(xiàn)目前出隊的元素編號小于前一個出隊的元素，就可以斷定當(dāng)前的“考試沖突”子集已經(jīng)構(gòu)建完，隊列中剩余元素應(yīng)該構(gòu)建新的子集。為此，在當(dāng)前的隊頭元素出隊前，要先記下剛剛出隊的元素，以便判斷當(dāng)前出隊的元素是否要開始構(gòu)建一個新子集。重復(fù)上述步驟一直到隊列空，則“無考試沖突”子集劃分完成。由上述算法思路可以知道，“無考試沖突”子集的劃分過程是一個循環(huán)的執(zhí)行過程，循環(huán)中的主要操作是元素出隊和判斷的操作。判斷操作包括出隊元素是否可以加入當(dāng)前子集和是否要開始構(gòu)建一個新子集兩個方面，對后一個判斷如前所述，通過比較出隊元素與前一個出隊元素編號大小可以確定。為了判斷出隊元素與當(dāng)前子集中的元素是否有“考試沖突

10、”，可以定義一個二維數(shù)組confnn來表示課程的考試沖突關(guān)系矩陣，矩陣中各元素的值根據(jù)以下規(guī)則確定，若編號為i的課程和編號為j的課程有考試沖突，則置confij=1，否則置confij=0，考試沖突關(guān)系矩陣如圖1所示。0101011010100111011000001011111100001110011001001111001010011011010001011100000111111000000010111100圖1 考試沖突關(guān)系矩陣?yán)谩翱荚嚊_突”關(guān)系矩陣可以檢查出隊元素i是否與當(dāng)前子集中的元素有考試沖突，其方法是：當(dāng)課程號為j1，j2，jk的元素已經(jīng)在當(dāng)前子集S中，要判斷目前出隊的元素i

11、是否可以加入子集S，只要檢查“考試沖突”關(guān)系矩陣中第i行的元素confi j1，confi j2，confi jk的值是否為0即可。如果這些元素的值都為0，表示課程i與子集中的課程沒有考試沖突，可以加入其中，否則說明表示課程i與子集中的某些課程有考試沖突，它不能加入該子集中。為了減少在二維數(shù)組conf中查找元素的操作，可以定義一個一維數(shù)組clashn來方便出隊元素i是否要加入當(dāng)前子集的判斷，數(shù)組clashn用于記錄出隊元素i與當(dāng)前子集中的元素是否存在考試沖突的信息。每當(dāng)開始構(gòu)建一個新子集時，先將數(shù)組clashn的各元素初始化為0，當(dāng)有編號為i的課程加入子集時，將“考試沖突”關(guān)系矩陣中第i行的各

12、列的值與數(shù)組clash的各對應(yīng)元素的值相加，因而使得數(shù)組clash中和編號為i的元素有考試沖突的相應(yīng)元素的值不再是0，當(dāng)下一個隊頭元素j出隊時，只要檢查數(shù)組clash中第j個元素的值是否為0，就可以判斷其是否與當(dāng)前子集中的元素有考試沖突；若數(shù)組clash中第j個元素的值不為0，則說明元素j與當(dāng)前子集中元素存在考試沖突，應(yīng)將其重新加入隊列；若數(shù)組clash中第j各元素的值為0，則說明它與當(dāng)前子集中元素不存在考試沖突，應(yīng)該將它加入當(dāng)前子集中，同時要將“考試沖突”關(guān)系矩陣中第j行的各列的值與數(shù)組clash的各對應(yīng)元素的值相加，這個過程一直到隊列空，則劃分無考試沖突子集完成。劃分結(jié)果可以用一個二維數(shù)組

13、來記錄各子集中的元素的方式來表示，也可以用一個一維數(shù)組來記錄每個元素其所屬的子集號的方式來表示。上述算法的思路可以描述如下：建立表示課程考試沖突關(guān)系矩陣的二維數(shù)組confnn；定義用于檢查當(dāng)前子集的課程考試沖突信息的數(shù)組clashn；定義用于記錄子集劃分結(jié)果的數(shù)組resultn；pre=n;/pre用于記錄前一個出隊元素的編號，初始值置為n以新建第1個子集k=0； /k用于記錄子集序號09(課程編號)依次入隊；while（隊列不空）隊頭元素i出隊；if(i<pre)/剛出隊元素小于前一個出隊元素，生成一個新子集k+;數(shù)組clash初始化；if(i可以加入當(dāng)前子集)/如果剛出隊元素與當(dāng)前子

14、集中的元素?zé)o考試沖突，將其加入當(dāng)前子集將i加入當(dāng)前子集，記錄i所屬子集的序號；將conf數(shù)組第i行各列的值與clash數(shù)組對應(yīng)列的值相加并記入clash中；else /如果剛出隊元素與當(dāng)前子集中的元素有考試沖突，將其重新入隊將i重新加入隊列；pre=i;l 考試成績統(tǒng)計和排序的實現(xiàn)ü 按總成績或按某一門課的成績統(tǒng)計并輸出人數(shù)時，應(yīng)該使各分?jǐn)?shù)段的人數(shù)和每個學(xué)生的信息清晰的分開。ü 對全體學(xué)生或?qū)δ骋粋€班的學(xué)生的成績進(jìn)行排序時，排序方法可以任意選擇。就本實驗問題而言，因表長不大采用簡單的排序方法就可以達(dá)到目的，但為了比較各種常用排序方法性能和適用場合，還可以采用不同的排序方法實

15、現(xiàn)排序。ü 對多關(guān)鍵字的排序要求，要注意排序方法的穩(wěn)定性問題。例如，在按總成績從高分到低分對全體學(xué)生進(jìn)行排序后，再按班級從高分到低分進(jìn)行排序，此時要求分班級排序時采用的排序方法其動態(tài)性能必須是穩(wěn)定的。同樣地，如果在按總成績從高分到低分排序的基礎(chǔ)上，再要求按某一門課的成績從高分到低分排序，也要求第2層排序一定注意選擇動態(tài)性能穩(wěn)定的排序方法。ü 在實現(xiàn)查找或排序功能時，其查找或排序的依據(jù)（指定項）和目標(biāo)（輸出結(jié)果）通過提示用戶輸入來確定。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計 typedef int KeyType;typedef char InfoType10;typedef struct /*

16、記錄類型*/KeyType key; /*關(guān)鍵字項*/ InfoType data; /*其他數(shù)據(jù)項,類型為InfoType*/ RecType3. 算法設(shè)計#include<iostream>using namespace std;#define MAXE 20/*線性表中最多元素個數(shù)*/typedef int KeyType;typedef char InfoType10;typedef struct /*記錄類型*/KeyType key; /*關(guān)鍵字項*/ InfoType data; /*其他數(shù)據(jù)項,類型為InfoType*/ RecType;void SelectSor

17、t(RecType R,int n)/*直接選擇排序算法*/int i,j,k,l;RecType temp;for (i=0;i<n-1;i+) /*做第i趟排序*/k=i;for (j=i+1;j<n;j+) /*在當(dāng)前無序區(qū)Ri.n-1中選key最小的Rk */if (Rj.key<Rk.key)k=j; /*k記下目前找到的最小關(guān)鍵字所在的位置*/if (k!=i) /*交換Ri和Rk */temp=Ri;Ri=Rk;Rk=temp; printf(" i=%d ",i);/*輸出每一趟的排序結(jié)果*/for (l=0;l<n;l+)print

18、f("%2d",Rl.key);printf("n");int main()int i,k,n=10,m=5;KeyType a=6,8,7,9,0,1,3,2,4,5;RecType RMAXE;for (i=0;i<n;i+)Ri.key=ai;printf("n");printf(" 初始關(guān)鍵字 ");/*輸出初始關(guān)鍵字序列*/for (k=0;k<n;k+)printf("%2d",Rk.key);printf("n");SelectSort(R,n);printf(" 最后結(jié)果 ");/*輸出初始關(guān)鍵字序列*/for (k=0;k<n;k+)printf("