數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-學(xué)生成績管理系統(tǒng)

1、石家莊經(jīng)濟(jì)學(xué)院全套設(shè)計加扣 3346389411或3012250582課題名稱：學(xué)生成績管理系統(tǒng)（數(shù)據(jù)結(jié)構(gòu)）學(xué)號：姓名：II目錄目錄1.需求分析11.1.開發(fā)背景11.2.數(shù)據(jù)需求11.3.功能需求12.功能介紹13.概要設(shè)計13.1.功能概要13.1.1.倒排查找23.2.子程序33.3.主界面截圖44.詳細(xì)設(shè)計54.1.數(shù)據(jù)結(jié)構(gòu)設(shè)計54.2.散列文件74.2.1.添加74.2.2.刪除74.2.3.查找74.2.4.插入74.3.B+樹74.3.1.增加74.3.2.刪除74.3.3.查找84.4.倒排表84.5.外部排序85.測試運(yùn)行85.1.輸出85.2.散列查找95.3.外部排序10

2、5.4.散列更改115.5.刪除學(xué)生信息125.6.B+樹查找125.7.倒排表136.總結(jié)與展望137.參考文獻(xiàn)148.使用說明14學(xué)生成績管理系統(tǒng)（數(shù)據(jù)結(jié)構(gòu)）1. 需求分析1.1. 開發(fā)背景學(xué)校在實際運(yùn)營中需要存儲大量的學(xué)生信息，在電子化之前，我們一般采用在紙上存儲學(xué)生信息，費(fèi)時費(fèi)力，所以，在當(dāng)今的社會中，我們運(yùn)用電子計算機(jī)的功能來存儲學(xué)生信息，并對學(xué)生信息進(jìn)行一系列的運(yùn)算，手工處理已經(jīng)退出了歷史的舞臺，如今的社會中，計算機(jī)具有檢索迅速、查找方便、可靠性高、存儲量大、保密性好、壽命長的優(yōu)點(diǎn)，信息的龐大也是我們利用計算機(jī)的超強(qiáng)的運(yùn)算功能的一個原因、成本低等，但更重要的是夠把學(xué)生的信息存儲起來

3、，方便以后的調(diào)用和處理。為了保證學(xué)生信息的規(guī)范化保存，我們有必要設(shè)計一個學(xué)生管理系統(tǒng)來統(tǒng)籌我們的學(xué)生信息。這就會大大減少學(xué)校教務(wù)人員的勞動量，提高工作效率，規(guī)范工作，推動教學(xué)的發(fā)展。1.2. 數(shù)據(jù)需求本程序利用B+樹、散列文件存儲信息，并進(jìn)行一系列的增刪改查。同時利用倒排表進(jìn)行分類管理信息，利用外部排序?qū)W(xué)號進(jìn)行排序。本系統(tǒng)包括學(xué)生的姓名，學(xué)號，出生日期，成績等。這些信息是等待用戶輸入的基本信息，或者是保存在文件中的信息，可以直接對文件進(jìn)行調(diào)用，并進(jìn)行一系列的操作。每次進(jìn)行操作之后，都會保存在相應(yīng)的文件中，方便下一次的操作。1.3. 功能需求利用B+樹、散列文件對學(xué)生信息進(jìn)行增刪改查的操作，利

4、用倒排表對學(xué)生信息進(jìn)行分類整理，利用外部排序?qū)ξ募臄?shù)據(jù)進(jìn)行學(xué)號排序。同時，每次操作之后都會保存在文件中，方便下次的操作。2. 功能介紹本“學(xué)生成績管理系統(tǒng)”能夠?qū)崿F(xiàn)的功能包括以下幾個方面：對學(xué)生信息進(jìn)行B+樹的增刪改查，對學(xué)生信息進(jìn)行散列文件的增刪改查，利用倒排文件對學(xué)生信息進(jìn)行多關(guān)鍵字查找，利用外部排序?qū)W(xué)生文件進(jìn)行排序。對于每一項操作，均是在文件中進(jìn)行的，所以在關(guān)閉之后，已經(jīng)進(jìn)行的操作沒有消失。 3. 概要設(shè)計3.1. 功能概要主菜單界面包括全部對學(xué)生的增、刪、改、查的操作，還包括對文件進(jìn)行多關(guān)鍵字查找，對文件進(jìn)行一系列的操作是在B+樹以及散列文件中進(jìn)行的，運(yùn)行程序首先進(jìn)入主菜單，在主菜

5、單里，分別列有十二項基本功能，等待用戶進(jìn)一步操作，如圖3-1-1所示。其中：倒排表選項有后續(xù)功能。重置輸出散列查找散列更改刪除增加退出外部排序隨機(jī)生成B+查找直接輸出倒排查找主菜單3-1-1一級菜單3.1.1. 倒排查找性別學(xué)號語文退出倒排查找可以對語文，性別，查找具體如圖3-1-1-1所示。3-1-1-1 二級菜單（查找）3.2. 子程序1. void creat1(stu data);/單獨(dú)輸入文件2. void outs();/輸出3. void inputss(BPTree *T);/重新輸入4. void menus();/菜單5. void te();/教師記錄6. int fin

6、ds(int *ip,int *key);/學(xué)號查找7. int find(int dat,char num,int *i);/關(guān)鍵字查找8. void outfindsl(int a,int ip);/查找9. void output(stu a);/輸出10. void change();/更改11. int de(BPTree *T);/刪除12. void clean();/清空13. void add();/增加14. void saveout(int max);/記錄15. void changedat();/更改student中的記錄信息，更新記錄16. void cleanba

7、ck();/清空17. void backgoal(int a256);/語文18. void backsex(int a256);/性別19. void backnum(int a256);/學(xué)號20. void back(stu student);/學(xué)生21. void outback();/輸出測試22. void backouts(int t,char name,int a);/測試倒排表中數(shù)據(jù)23. int outbackfind();/查找到后輸出,返回文件中學(xué)生記錄的個數(shù)24. void outbackss(int saveout,int k);25. void telldate

8、(int choice,int a,int b256);/數(shù)據(jù)檢驗26. void copyint1(int b,int a,int t);/把a(bǔ)中的前t個數(shù)字復(fù)制到b中27. void copyint2(int b256,int a256,int t,int every);/把a(bǔ)中的數(shù)據(jù)復(fù)制到b中，其中，每一維度只是復(fù)制對應(yīng)的every個數(shù)據(jù)28. int compare(int choice1,int choice2,int aa1,int bb1256,int aa2,int bb2256);/二維數(shù)組保存數(shù)據(jù)，一維數(shù)組保存對應(yīng)二維數(shù)組中的個數(shù)29. int sort();/排序30.

9、void sortclassify(int sum,stu student,char name);/個數(shù)，學(xué)生數(shù)組，學(xué)生文件名字31. void createlosertree(int ls,stu student);/初始化32. void K_merge(char name20);/k路歸并33. void adjust(int ls,int s,stu student);/調(diào)整34. void creatb(BPTree *A); /創(chuàng)建樹35. result findb(BPTree T,int K); /查找樹36. void creatb();/清空樹37. int search(

10、BPTree T,int K); /查找分支38. int insertb(BPTree *T,int K,BPTree q,int i,stu student); /總的添加樹39. void insert(BPTree q,int i,int x,stu student,BPTree p); /添加數(shù)據(jù)40. void newroot(BPTree *T,BPTree q1,int x,BPTree p); /新建節(jié)點(diǎn)41. int outb(BPTree T); /輸出樹42. int del_b(BPTree *T,int key1); /刪除樹43. void adjust0(BPT

11、ree q , int k); /調(diào)整樹根44. void adjust1(BPTree q,int k ,BPTree father,int now); /直接刪除的調(diào)整45. void adjust2(BPTree q,int k,BPTree father,int now,int delstu); /與左邊借的調(diào)整46. void adjust3(BPTree q,int k,BPTree father,int now,int delstu); /與右邊借的調(diào)整47. void adjust4(BPTree q,int k,BPTree father,int now,int delstu

12、); /與左右合并的調(diào)整48. void changefather(BPTree q,int now,int key); /查找父親49. void findb1(BPTree T); /查找樹3.3. 主界面截圖當(dāng)運(yùn)行程序時首先進(jìn)入主菜單界面，如圖3-3-1所示。圖3-3-1主菜單4. 詳細(xì)設(shè)計4.1. 數(shù)據(jù)結(jié)構(gòu)設(shè)計本系統(tǒng)運(yùn)用的是文件保存學(xué)生信息的方法，把每一個學(xué)生信息保存在文件中，每次對學(xué)生信息進(jìn)行修改，增加，刪除等操作時，均是對文件中的記錄類型中的數(shù)據(jù)進(jìn)行的更改變化。采用了b+樹，散列文件，倒排表以及外部歸并的方法對文件進(jìn)行一系列的操作。具體的定義數(shù)據(jù)結(jié)構(gòu)如下：typedef struc

13、t dint year;int month;int day;dates;typedef struct scfloat chinese;float math;float english;float average;score;typedef struct studentchar num13;char name20;dates birthday; char sex20;score goal; int sum; int age; int key;stu;typedef struct headsint s;heads;/目錄typedef struct bksint sum;/這個桶中保存的數(shù)據(jù)stu

14、 a3;/學(xué)生信息int t;/下一個桶bks;/散列文件typedef struct BPNode int keynum; /結(jié)點(diǎn)中關(guān)鍵字個數(shù) struct BPNode *parent; /指向雙親結(jié)點(diǎn) int key4;/關(guān)鍵字向量，至多m個關(guān)鍵字 int tag;/標(biāo)記是否是葉子 struct BPNode *ptr4;/非終端結(jié)點(diǎn)至多m棵子樹 struct /葉子節(jié)點(diǎn)信息 stu *student4;/葉子記錄指針向量，0號單元未用 struct BPNode *next;/指向下一個葉子結(jié)點(diǎn) struct BPNode *pre;/指向前一個葉子結(jié)點(diǎn) leaf; /葉子結(jié)點(diǎn)BPNo

15、de,*BPTree;typedef structBPNode *ptr;/返回當(dāng)前的地址，一個葉子節(jié)點(diǎn)地址int i;/并且返回該位置為i，如果不能找到，返回該位置i為第一個大于他數(shù)int tag;result;/作為查找返回值，如果能查找到，就返回自己的位置，不能查找到，就返回插入位置4.2. 散列文件實現(xiàn)散列文件的增刪改查。采用頭插法保存信息。一共使用8個桶，其中最后一個桶保存使用過的溢出桶，并且該溢出桶沒有數(shù)據(jù)。每次添加信息的時候都需要檢測溢出桶是否有數(shù)據(jù)。4.2.1. 添加在添加過程中，取學(xué)生學(xué)號關(guān)鍵字，對7取余，放入相應(yīng)的桶中，在放入之前，先對該桶進(jìn)行查找操作，確定沒有該學(xué)生記錄之

16、后，進(jìn)行插入。在插入過程中，我們要有4種情況：1.在基桶中插入；2.沒有溢出桶，創(chuàng)建溢出桶中插入；3.基桶滿了，最后一個桶存在空間，調(diào)用最后一個桶空間進(jìn)行插入；4.存在溢出桶，直接在溢出桶插入。4.2.2. 刪除先對學(xué)生信息進(jìn)行查找，查找到之后返回學(xué)生 信息的位置，直接對該位置進(jìn)行操作，3種情況：1.在基桶中刪除，存在溢出桶，把溢出桶最后一個數(shù)據(jù)放入待刪除的位置，不存在溢出桶就直接挪動學(xué)生信息；2.在不是最后一個溢出桶中刪除，同上一個操作；3.在最后一個溢出桶中刪除，直接挪動位置。4.2.3. 查找取學(xué)生關(guān)鍵字，對關(guān)鍵字進(jìn)行再的散列文件中查找，先找到對應(yīng)的桶，從最后一個溢出桶遍歷，直到遍歷到學(xué)

17、生信息或者基桶的尾部為止。返回信息。4.2.4. 插入調(diào)用查找，更改學(xué)生信息后，滴啊用插入，把更改好的學(xué)生信息進(jìn)行插入原來的位置。4.3. B+樹4.3.1. 增加調(diào)用查找函數(shù)，返回一個結(jié)構(gòu)體類型，其中包括要插入的信息，如果不能查找到，返回的是要插入的節(jié)點(diǎn)的位置以及對應(yīng)的下標(biāo)。我們在插入之后，判斷是否需要分裂節(jié)點(diǎn)，如果需要分裂節(jié)點(diǎn)，那么就會新建一個節(jié)點(diǎn)保存其中的一半的信息，把原來節(jié)點(diǎn)的最大值更改，往父親添加信息，重復(fù)操作，值得注意的是，如果當(dāng)插入的是一個新的最大值，就需要更改父親中相應(yīng)的節(jié)點(diǎn)。一直進(jìn)行下去，直到進(jìn)行到根節(jié)點(diǎn)，如果根節(jié)點(diǎn)需要分裂，那么就要新建一個根節(jié)點(diǎn)，成為一個新的根節(jié)點(diǎn)的樹。4

18、.3.2. 刪除調(diào)用查找函數(shù)，利用返回的信息進(jìn)行一系列的操作，這里有6種情況需要考慮：1.該節(jié)點(diǎn)信息刪除一個后，仍能獨(dú)立存在，就只是觀察是不是刪除的最大值；2.從左邊接一個信息；3.從右邊借一個信息；4.和左邊合并；5.和右邊合并；6.根節(jié)點(diǎn)只有一個數(shù)據(jù)的時候，刪除該根節(jié)點(diǎn)，根指向它的孩子；值得注意的是，只有合并的時候需要循環(huán)，其余只是調(diào)整。合并相當(dāng)于父親節(jié)點(diǎn)刪除的操作，而其余情況只是對非終端節(jié)點(diǎn)進(jìn)行的操作。4.3.3. 查找利用b+樹的特點(diǎn)，我們利用父親節(jié)點(diǎn)保存孩子的最大值的特性，不斷地往下邊遍歷，直到遍歷到葉子節(jié)點(diǎn)為止，返回葉子節(jié)點(diǎn)地址，下標(biāo)，以及是否找到。4.4. 倒排表把文件中的信息分

19、類到不同的文件中，這些子文件只是保存的學(xué)生的數(shù)量以及學(xué)生信息在文件中的相對位置。使用其進(jìn)行分類的時候，直接對文件中的信息進(jìn)行調(diào)用即可，找出公共部分。4.5. 外部排序先把文件分為幾部分，這里我分了5個部分，一個一個分配到文件中，盡量平均分配。利用冒泡法對每個文件中的學(xué)生信息的學(xué)號進(jìn)行排序，排序成功后，寫入文件。值得注意的是，要寫入一個最大值進(jìn)入文件，用來判斷文件末尾。這時候，我們得到了5個以及排好序的文件，在利用敗者樹的思想進(jìn)行單個排序，首先從每個文件中讀出一個數(shù)據(jù)，進(jìn)行比較，選取最小的放入一個新文件中，找到這個信息所在的子文件的位置，繼續(xù)從這個子文件中讀出數(shù)據(jù)，繼續(xù)比較。重復(fù)上述操作，直到讀

20、出的信息是一個最大值為止。5. 測試運(yùn)行5.1. 輸出選擇輸出。如圖5-1-1(1)、5-1-1(2)所示。輸入：鍵盤輸入2選項。輸出：直接用b+樹輸出關(guān)鍵字，用倒排文件的桶輸出學(xué)生信息效果：輸出對應(yīng)的信息。圖5-1-1(1) 輸出圖5-1-1(2) 輸出5.2. 散列查找散列查找成功。如圖5-2-1所示。效果：顯示要查找的信息。圖5-2-1 散列查找5.3. 外部排序?qū)λ袑W(xué)生信息進(jìn)行外部排序，如圖5-3-1所示 。程序輸出：顯示排好序的信息。圖5-3-1 顯示排序5.4. 散列更改把學(xué)生信息修改。數(shù)據(jù)輸入：修改學(xué)生信息，如圖5-4-1(1)。數(shù)據(jù)輸出:輸出更改后的學(xué)生信息，如圖5-4-1(

21、2)。效果:將學(xué)生信息以一定的格式顯示在屏幕上，發(fā)現(xiàn)修改后的信息正確。圖5-4-1(1) 修改學(xué)生信息圖5-4-1(2) 修改學(xué)生信息成功5.5. 刪除學(xué)生信息刪除最大學(xué)生學(xué)號的學(xué)生信息，具體排序如圖5-5-1所示。效果：進(jìn)行外部排序，對比上邊的排序，沒有了最大值得學(xué)上信息。顯示成績單在屏幕上。圖5-5-1 刪除5.6. B+樹查找B+樹查找功能，如圖5-4-1所示。效果：把學(xué)生各項基本信息顯示在屏幕上。圖5-4-1 查找b+5.7. 倒排表查找語文不及格的女生。 圖5-7-2 倒排表6. 總結(jié)與展望學(xué)習(xí)了這半年的數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)了好多以前不懂得東西，以前好多東西都是一位很簡單的，沒想到最后，他們都有這么多種解