1、.;數據結構學生成績管理系統課程設計報告數據結構課程設計 PAGE 13需求分析構建學生成績管理系統，每個學生的信息為：基本信息（學號、姓名、年齡、性別），課程1（課程1、成績、教師），課程2（課程2、成績、教師）。采用Hash表加課程鏈表的結構：Hash表存放每個學生的基本信息，課程指針指向課程鏈表。程序應有如下功能：（1）建立哈希表：輸入十個人的信息，哈希函數為H=（學號后三位）MOD11，用線性探測再散列的方法處理沖突（2）查詢：顯示全部信息，可以實現按學號、姓名、性別、某年級全部課程、聽某教師課的學生、選擇某門課程的學生查找（3）排序：按學號從小到大、按年齡從大到小、按學生總成績從大到

2、小排序（4）統計：可以實現統計：男女生人數、個人平均成績和總成績、各年級平均年齡、各門課程的平均成績（5）系統維護：可以實現插入、刪除、修改一個記錄的功能。演示程序以用戶和計算機的對話方式執行，即在計算機上顯示提示信息，由用戶進行操作，顯示各種指標值。測試數據見附錄。二、概要設計抽象數據定義：課程結構體的定義：typedef struct Classchar name20;int score;char teacher20;Class *next;Class,*ClassList;課程結構體的定義學生信息結構體的定義：typedef struct char number10;char name2

3、0;int age;char sex10;struct Class *classes;Student;數據類型的定義：struct ElemType int key; Student student;哈希結構體的定義：typedef struct ElemType *elem;int count;int sizeindex;HashTable;用于排序的結構體的定義：typedef struct ElemType rMAXSIZE+1;int length;SqList;基本操作：InitHashTable(HashTable &H)操作結果：初始化一個哈希表Hash(int K)操作結果：哈

4、希函數，返回計算得的結果collision(int &p,int c)操作結果：處理沖突，返回計算得的結果SearchHash(HashTable H,int K,int &p,int &c)操作結果：查找哈希表，返回查找到的結果RecreateHashTable(HashTable &H)操作結果：開辟更大空間，重新構造一個哈希表InsertHash(HashTable &H,ElemType e)操作結果：哈希表的插入，插入一個數據SeInsertHash(HashTable &H,ElemType e,fstream dataFile)操作結果：初始哈希表插入，從文件中將數據拷貝到哈希表

5、中ListTraverse(ClassList L)操作結果：遍歷線性鏈表，打印輸出TraverseHash(HashTable H)操作結果：遍歷哈希表，打印輸出Partition(SqList &L,int low,int high)操作結果：一趟快速排序，并返回樞軸所在位置QSort(SqList &L,int low,int high)操作結果：對順序表L中的子序列L.rlowhigh作快速排序QuickSort(SqList &L)操作結果：對順序表L作快速排序HeapAdjust(SqList &H,int s,int m)操作結果：調整H.rs的關鍵字，使H.rsm成為一個小頂堆

6、HeapSort(SqList &H)操作結果：對順序表H進行堆排序Merge(ElemType SR,ElemType TR,int i,int m,int n)操作結果：將有序的SRim和SRm+1n歸并為有序的TRinMSort(ElemType SR,ElemType TR1,int s,int t)操作結果：將SRst歸并為TR1stMergeSort(SqList &L)操作結果：對順序表L作歸并排序CreateList(ClassList &L,fstream dataFile,int n)操作結果：初始從文件中讀數據創建課程鏈表Pricreat(HashTable &peopl

7、e)操作結果：初始化從文件讀入構造哈希表print(ElemType e)操作結果：打印輸出單個學生信息Isvalue(char a,int n)操作結果：判斷數組a的前n個字符是否為數字NumSearch(HashTable H)操作結果：按學號查找，打印輸出NameSearch(HashTable H)操作結果：按姓名查找，打印輸出SexSearch(HashTable H)操作結果：按性別查找，打印輸出GradeSearch(HashTable H)操作結果：按年級查找，打印輸出TeacherSearch(HashTable H)操作結果：按教師查找，打印輸出ClassSearch(Ha

8、shTable H)操作結果：按課程查找，打印輸出ShowQSort(SqList people1,HashTable people)操作結果：顯示快速排序后的結果ShowHSort(SqList people1,HashTable people)操作結果：顯示堆排序后的結果ShowMSort(SqList people1,HashTable people)操作結果：顯示歸并排序后的結果AddSex(HashTable H)操作結果：統計男/女生人數PerAverage(HashTable H)操作結果：計算個人平均成績、總成績GradeAverage(HashTable H)操作結果：計算某

9、年級平均年齡ClassAverage(HashTable H)操作結果：計算某課程平均成績AddCreateList(ClassList &L,int n)操作結果：添加數據時創建課程鏈表AddHash(HashTable &H)操作結果：添加一個數據ClearList(ClassList &L)操作結果：刪除數據時清空課程鏈表DeleteHash(HashTable &H)操作結果：刪除一個記錄EditHash(HashTable &H)操作結果：修改一個記錄headshow(void)操作結果：顯示主菜單show1(void)操作結果：顯示子菜單1Show2(void)操作結果：顯示子菜單

10、2Show3(void)操作結果：顯示子菜單3Show4(void)操作結果：顯示子菜單4三、調試分析1.初始化采用文件操作，且選取的數據需要作沖突處理，測試數據具有較好的典型性，通過運行對哈希表有了具體的認識和實踐。2.查找時按學號、性別查找對用戶的輸入有查錯處理，另外根據實際情況將個人平均成績強制轉換為了整數（采用四舍五入）。3.排序時分別采用了快速排序、堆排序和歸并排序，其中歸并排序是穩定的，選取的數據也基本是無序的，且排序后不影響原來數據的結構。4.插入、刪除、修改數據在程序未關閉時是會表現出來的，但并不改變測試數據文件中的內容，這三個操作只是起一個演示作用。5.在讀文件中的數據的時候

11、，起初我是將數據從文件中讀到一個結構體數組中，然后再將結構體中的數據用哈希表的形式存下來，但這樣明顯浪費了空間，所以我寫了兩個哈希表的插入函數，一個用來作初始化的插入，另一個用來添加數據時的哈希插入，同樣的理由我也寫了兩個建立課程鏈表的函數。這樣無需過渡，直接從文件中將記錄讀入了哈希表中。6.為了區別哈希表中的一個單位有無數據，在初始化哈希表時我將關鍵字全部賦為了NULLKEY即為0，另外為了凸顯關鍵字，我新定義了一個數據類型：ElemType作為哈希表中的數據類型，事實上這種做法在使我在后來的編程中方便了不少。7.在處理哈希表的容量的問題時，我定義了一個整型數組hashsize用來表示哈希表

12、的容量的遞增，另外定義了一個全局變量m來記錄當前哈希表的最大容量。8.在處理沖突時采用的是線性探測再散列的方法，當沖突次數過多時就重建哈希表，重建哈希表時，我先將原來哈希表中的數據用數組記錄下來，在為哈希表開辟了更大的空間后，再調用InsertHash函數將原有數據插入到新的哈希表中。9.我所遇到的最大問題是空間分配出錯的問題，在創建課程鏈表時由于沒有處理好空間分配的問題，沒有對課程鏈表的頭結點分配空間，導致遍歷時學生課程數據讀不出來，在處理好空間分配的問題后，以后的編程就順暢多了。10.在排序階段由于我寫的排序是將數組的1號位作為數據存放的首位置，而哈希表中是將0號位作為數據存放的首位置，這

13、樣在調用的時候就出問題了，為此在排序時我多分配了一個空間，將哈希表中的數據按順序連續的賦到一個新的結構體數組中（從1號位開始賦值）。四、用戶手冊1.本程序的運行環境為DOS操作系統。2.進入演示程序后，即顯示用戶界面（如圖1），有五種操作可選擇，選擇這五種操作中的前四個的任何一個即進入相關子菜單（如圖2，3，4，5所示），有另外的具體操作供選擇。3.如前面的調試分析所述，插入、刪除、修改數據在程序未關閉時是會表現出來的，但并不改變測試數據文件中的內容，這三個操作只是起一個演示作用。圖1圖2圖3圖4圖5五、測試結果對初始數據進行了測試，程序運行正常，基本實現了預先所要求的各種操作。1.查詢部分：

14、測試數據的全部顯示如圖1-1所示，按學號查找的顯示結果如圖1-2所示。其他排序顯示結果也正常，篇幅有限就不顯示截圖了。2.排序部分：按學號排序的結果如圖2-1所示，按年齡排序的結果如圖2-2所示，按總成績排序的結果如圖2-3所示。3.統計部分：按男女生統計的結果如圖3-1所示。其他統計結果經檢驗也是正確的。4.系統維護：插入刪除一個數據的結果分別如圖4-1和4-2所示。執行插入刪除后關于查詢、排序和統計的部分顯示如圖4-3，4-4，4-5所示。5.退出：選擇退出后的顯示如圖5-1所示。圖1-1圖1-2圖2-1圖2-2圖2-3圖3-1圖4-1圖4-2圖4-3圖4-4圖4-5圖5-1六、附錄源程序文件名：student.cpp存放初始數據的文件名：students.txt 其內容為：080710308 朱嘯天 23 男 數據結構 99 葉延風 數學分析 97 陳芳啟080810310 徐若寒 21 女 綜合英語 89 王素敏 數學分析 90 王澤軍080810313 何展風 20 男 綜合英語 90 王素敏 數學分析 95 王澤軍080710314 劉伊藍 22 女 數據結構 87 葉延風 數學分析 91 陳芳啟080710320 郎雨箏 24 女