數據結構試驗哈希表

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

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

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

4、2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,9),(2,9,7),(6,0,3),(5,6,9)。根據題中考試安排原則，各個班要進行的考試課程可以抽象為“考試沖突關系”，歸納各個班的考試課程可以整理得到考試沖突關系：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)。顯然，“考試沖突”關系R的每個有序對中的兩門課程不能安排

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

6、程則要安排在不沖突的時間考試。l 考試分數的統(tǒng)計與排序² 考試成績輸出ü 每個學生的信息記錄數據項應包括：學號、姓名、班級、課程1、課程2、課程10、總成績。ü 按總分高低輸出所有學生信息時，應該以總成績?yōu)殛P鍵字從高分到低分對所有的學生記錄進行排序，排序方法自行選定，然后依次輸出各個記錄。ü 按照班級順序和總分高低輸出各班學生信息時，要對學生記錄進行多關鍵字排序，首先以總成績?yōu)殛P鍵字從高分到低分對所有的學生記錄進行排序，然后再以班號為關鍵字對全部學生記錄排序，再輸出結果。² 統(tǒng)計成績統(tǒng)計各分數段的人數，要求由用戶輸入，具體要求可以有：ü

7、; 按照總成績統(tǒng)計各分數段的人數，并輸出各分數段的學生記錄，即在統(tǒng)計一個分數段的人數過程中，要輸出滿足查找條件的學生記錄，再輸出統(tǒng)計的結果。ü 指定某一門課程，統(tǒng)計各分數段的人數并輸出各分數段的學生記錄。ü 對指定班級中總成績或指定課程成績做各分數段人數的統(tǒng)計，也要輸出各分數段的學生記錄。² 查找成績查找要求由用戶輸入，可以輸入以下條件：ü 查找指定分數項（總分或某一門課程）的某分數段的學生信息，輸出查找結果。ü 查找指定班級、指定分數項的某分數段的學生信息，輸出查找結果。ü 查找指定學生（給定學號）的具體信息，輸出查找結果。算法提示

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

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

10、子集中的元素是否有“考試沖突”，可以定義一個二維數組confnn來表示課程的考試沖突關系矩陣，矩陣中各元素的值根據以下規(guī)則確定，若編號為i的課程和編號為j的課程有考試沖突，則置confij=1，否則置confij=0，考試沖突關系矩陣如圖1所示。0101011010100111011000001011111100001110011001001111001010011011010001011100000111111000000010111100圖1 考試沖突關系矩陣利用“考試沖突”關系矩陣可以檢查出隊元素i是否與當前子集中的元素有考試沖突，其方法是：當課程號為j1，j2，jk的元素已經在當前子集

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

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

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

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

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

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

17、void SelectSort(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+) /*在當前無序區(qū)Ri.n-1中選key最小的Rk */if (Rj.key<Rk.key)k=j; /*k記下目前找到的最小關鍵字所在的位置*/if (k!=i) /*交換Ri和Rk */temp=Ri;Ri=Rk;Rk=temp; printf(" i=%d ",i);/*輸出每一趟的排序結果*/for (l=0;l

18、<n;l+)printf("%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(" 初始關鍵字 ");/*輸出初始關鍵字序列*/for (k=0;k<n;k+)printf("%2d",Rk.key);printf("n");SelectSort(R,n);printf(" 最后結果 ");/*輸出初始關鍵字序列*/for (k=0;k<n;k+)printf("