云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)7學(xué)生信息管理系統(tǒng)

1、云南大學(xué)軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 （本實(shí)驗(yàn)項(xiàng)目方案受“教育部人才培養(yǎng)模式創(chuàng)新實(shí)驗(yàn)區(qū)（X3108005）”項(xiàng)目資助） 實(shí)驗(yàn)難度： A B C 序號(hào)學(xué)號(hào)姓名成績(jī)123指導(dǎo)教師 （簽名）學(xué)期：2013秋季學(xué)期 任課教師: 張德海 實(shí)驗(yàn)題目: 學(xué)生信息管理系統(tǒng) 小 組 長(zhǎng): 聯(lián)系電話: 電子郵件: 完成提交時(shí)間：2013年 12月17日數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)成績(jī)考核表 評(píng)分項(xiàng)目評(píng)分指標(biāo)分值得分實(shí)驗(yàn)構(gòu)思（10%）1. 實(shí)驗(yàn)?zāi)康拿鞔_52. 實(shí)驗(yàn)內(nèi)容理解透徹、對(duì)實(shí)驗(yàn)所涉及到的知識(shí)點(diǎn)分析到位5實(shí)驗(yàn)設(shè)計(jì)（15%）1. 有對(duì)基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實(shí)驗(yàn)方案設(shè)計(jì)完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程

2、序功能模塊之間邏輯清晰、有相應(yīng)的流程圖5實(shí)驗(yàn)實(shí)現(xiàn)（25%）1. 代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運(yùn)行正常，測(cè)試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯(cuò)性5實(shí)驗(yàn)報(bào)告撰寫（10%）1. 內(nèi)容詳實(shí)無缺漏，文字流暢、圖表清楚52. 實(shí)驗(yàn)結(jié)果分析客觀、詳細(xì)，實(shí)驗(yàn)體會(huì)真實(shí)可信，對(duì)原實(shí)驗(yàn)方案的改進(jìn)和對(duì)實(shí)驗(yàn)內(nèi)容的發(fā)散性思考5個(gè)人工作量（30%）1. 個(gè)人完成工作量152. 個(gè)人技術(shù)水平103. 團(tuán)隊(duì)合作精神5實(shí)驗(yàn)運(yùn)作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日評(píng)分項(xiàng)目評(píng)分指標(biāo)分值得分實(shí)驗(yàn)構(gòu)思（10%）1. 實(shí)驗(yàn)?zāi)康拿鞔_52.

3、實(shí)驗(yàn)內(nèi)容理解透徹、對(duì)實(shí)驗(yàn)所涉及到的知識(shí)點(diǎn)分析到位5實(shí)驗(yàn)設(shè)計(jì)（15%）1. 有對(duì)基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實(shí)驗(yàn)方案設(shè)計(jì)完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程序功能模塊之間邏輯清晰、有相應(yīng)的流程圖5實(shí)驗(yàn)實(shí)現(xiàn)（25%）1. 代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運(yùn)行正常，測(cè)試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯(cuò)性5實(shí)驗(yàn)報(bào)告撰寫（10%）1. 內(nèi)容詳實(shí)無缺漏，文字流暢、圖表清楚52. 實(shí)驗(yàn)結(jié)果分析客觀、詳細(xì)，實(shí)驗(yàn)體會(huì)真實(shí)可信，對(duì)原實(shí)驗(yàn)方案的改進(jìn)和對(duì)實(shí)驗(yàn)內(nèi)容的發(fā)散性思考5個(gè)人工作量（30%）1. 個(gè)人完成工作量152. 個(gè)人技術(shù)水平103. 團(tuán)隊(duì)合作精神5

4、實(shí)驗(yàn)運(yùn)作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日評(píng)分項(xiàng)目評(píng)分指標(biāo)分值得分實(shí)驗(yàn)構(gòu)思（10%）1. 實(shí)驗(yàn)?zāi)康拿鞔_52. 實(shí)驗(yàn)內(nèi)容理解透徹、對(duì)實(shí)驗(yàn)所涉及到的知識(shí)點(diǎn)分析到位5實(shí)驗(yàn)設(shè)計(jì)（15%）1. 有對(duì)基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義52. 實(shí)驗(yàn)方案設(shè)計(jì)完整，數(shù)據(jù)結(jié)構(gòu)、算法選擇合理 53.算法結(jié)構(gòu)和程序功能模塊之間邏輯清晰、有相應(yīng)的流程圖5實(shí)驗(yàn)實(shí)現(xiàn)（25%）1. 代碼編寫規(guī)范、風(fēng)格統(tǒng)一、注釋清楚易讀 52. 程序運(yùn)行正常，測(cè)試結(jié)果正確153. 界面友好、易于操作、有較強(qiáng)的容錯(cuò)性5實(shí)驗(yàn)報(bào)告撰寫（10%）1. 內(nèi)容詳實(shí)無缺漏，文字流暢、圖表清楚52

5、. 實(shí)驗(yàn)結(jié)果分析客觀、詳細(xì)，實(shí)驗(yàn)體會(huì)真實(shí)可信，對(duì)原實(shí)驗(yàn)方案的改進(jìn)和對(duì)實(shí)驗(yàn)內(nèi)容的發(fā)散性思考5個(gè)人工作量（30%）1. 個(gè)人完成工作量152. 個(gè)人技術(shù)水平103. 團(tuán)隊(duì)合作精神5實(shí)驗(yàn)運(yùn)作（10%）1. 有一定用戶群52. 應(yīng)用前景分析5綜合得分： （滿分100分）指導(dǎo)教師： 年 月 日一、【實(shí)驗(yàn)構(gòu)思（Conceive）】(10%)設(shè)計(jì)主要要求分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表，并實(shí)現(xiàn)查找功能。所以本設(shè)計(jì)的核心問題是如何解決散列的問題，由于結(jié)點(diǎn)的個(gè)數(shù)無法確認(rèn)，并且如果采用線性探測(cè)法散列算法，刪除結(jié)點(diǎn)會(huì)引起“信息丟失”的問題。所以采用鏈地址法散列算法。采用鏈地址法，當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表

6、結(jié)構(gòu)把同義詞鏈接在一起。 首先，解決的是定義鏈表結(jié)點(diǎn)，在鏈接地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成。name8 、num11和address20都是char浮點(diǎn)型采用鏈地址法，其中的所有同義詞構(gòu)成一個(gè)單鏈表，再由一個(gè)表頭結(jié)點(diǎn)指向這個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)。這些表頭結(jié)點(diǎn)組成一個(gè)一維數(shù)組，即哈希表。二、【實(shí)驗(yàn)設(shè)計(jì)(Design)】(20%)設(shè)計(jì)哈希表實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)完成以下要求： （1）設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址； （2）從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希

7、表； （3）采用再哈希法解決沖突； （4）查找并顯示給定電話號(hào)碼的記錄； （5）查找并顯示給定用戶的記錄。 具體思路為： （1）對(duì)于以號(hào)碼為關(guān)鍵字的散列函數(shù)，是將十一個(gè)數(shù)字全部相加，然后對(duì)20求余。得到的數(shù)作為地址。對(duì)于以用戶名為關(guān)鍵字的散列函數(shù)，是將所有字母的ASCLL碼值相加，然后對(duì)20求余。 （2）要添加用戶信息，即要有實(shí)現(xiàn)添加結(jié)點(diǎn)的功能函數(shù)，所以要設(shè)計(jì)一個(gè)必須包括一個(gè)輸入結(jié)點(diǎn)信息、添加結(jié)點(diǎn)的函數(shù)； （3）要實(shí)現(xiàn)查找函數(shù)，則必須包括一個(gè)查找結(jié)點(diǎn)的函數(shù)； 另外還有一個(gè)必不可少的就是運(yùn)行之后要有一個(gè)主菜單，即要設(shè)計(jì)一個(gè)主函數(shù)（4）最后，程序完成后要對(duì)程序進(jìn)行編譯調(diào)試，執(zhí)行后要選擇數(shù)據(jù)進(jìn)行測(cè)試

8、， 三、【實(shí)現(xiàn)描述（Implement）】(30%)1 建立節(jié)點(diǎn) struct node char name8,address20; char num11; node * next; ; typedef node* pnode; /可以為一個(gè)已有的數(shù)據(jù)類型聲明多個(gè)別名 typedef node* mingzi; node *phone; node *nam; node *a; 2 哈希函數(shù)的定義 本程序要設(shè)計(jì)兩個(gè)hash（）函數(shù)，分別對(duì)應(yīng)電話號(hào)碼和用戶名。對(duì)關(guān)鍵字進(jìn)行模運(yùn)算，將運(yùn)算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點(diǎn)）的存儲(chǔ)地址，方法如下：以電話號(hào)碼為關(guān)鍵字建立哈希函數(shù)hash(char num1

9、1)。以用戶名為關(guān)鍵字建立哈希函數(shù)hash2(char name8)。利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù)。將計(jì)算出來的數(shù)作為該結(jié)點(diǎn)的地址賦給key2。 void hash(char num11); /以電話號(hào)碼為關(guān)鍵字建立哈希函數(shù) /哈希函數(shù)的主旨是將電話號(hào)碼的十一位數(shù)字全部加起來 int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; /利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù) void hash2(char nam

10、e8); /哈希函數(shù) 以用戶名為關(guān)鍵字建立哈希函數(shù) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; 3 哈希查找 想要實(shí)現(xiàn)查找功能，同樣需要兩個(gè)查找函數(shù)，無論以用戶名還是以電話號(hào)碼為關(guān)鍵字，首先，都需要利用hash函數(shù)來計(jì)算出地址。再通過比對(duì)，如果是以電話號(hào)碼為關(guān)鍵字，比較其電話號(hào)碼是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息，如果以用戶名為關(guān)鍵字，則比較用戶名是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息。如果找不到與之對(duì)應(yīng)相同的，則輸出“無此記錄”。 void find(char n

11、um11) ; /在以電話號(hào)碼為關(guān)鍵字的哈希表中查找用戶信息 4 流程圖以學(xué)號(hào)為關(guān)鍵字的hash函數(shù)流程圖以姓名為關(guān)鍵字的hash函數(shù)流程圖四、【測(cè)試結(jié)果（Testing）】(10%) 1、添加記錄2、查找記錄3、姓名散列4、學(xué)號(hào)散列5、清空記錄五、【實(shí)驗(yàn)總結(jié)】(10%)盧晨陽(yáng) 20121120205：主要負(fù)責(zé)：程序算法的設(shè)計(jì)和程序?qū)崿F(xiàn)，實(shí)驗(yàn)報(bào)告的部分撰寫經(jīng)驗(yàn)總結(jié)：1、我們定義了兩個(gè)哈希函數(shù)，一個(gè)以學(xué)號(hào)為關(guān)鍵字，另一個(gè)以姓名ASCII之和求模之后的值為關(guān)鍵字。第一種是將學(xué)號(hào)從第二位開始逐一累加并將所得結(jié)果對(duì)30求模得哈希地址。第二種則是將姓名字符進(jìn)行強(qiáng)制類型轉(zhuǎn)換之后得ASCII碼相加對(duì)30求模

12、得哈希地址。2、哈希表問題，在存儲(chǔ)位置和關(guān)鍵字之間建立對(duì)應(yīng)關(guān)系f，根據(jù)對(duì)應(yīng)關(guān)系f找到定值K。若結(jié)構(gòu)中存在關(guān)鍵字和定值K相等的記錄，必定在f（K）的存儲(chǔ)位置上，由此可以省去比較過程，直接找到所查記錄。3、。由于長(zhǎng)度無法確定，并且如果采用線性探測(cè)法散列算法，刪除結(jié)點(diǎn)會(huì)引起“信息丟失”的問題，所以采用鏈地址法散列算法。采用鏈地址法，當(dāng)出現(xiàn)同義詞沖突時(shí)，可以使用鏈表結(jié)構(gòu)把同義詞鏈接在一起即同義詞的存儲(chǔ)地址不是散列表中其他的空地址。毛鈺源 20121120036：主要負(fù)責(zé)：程序算法的部分改進(jìn)和界面設(shè)計(jì)，部分接口的實(shí)現(xiàn)經(jīng)驗(yàn)總結(jié)：1、哈希表的實(shí)現(xiàn)，其主要的精妙之處在于，重載了這個(gè)運(yùn)算符，然后在判斷哈希表是否

13、為空時(shí)，初始化。2、在實(shí)驗(yàn)中雖然使用得仍然是倒插入指針頭的方法，但其始終保持著在散列的地址第一位。且在此次實(shí)驗(yàn)中，主要是要分清nHash與key二者的區(qū)別，前者是由后者通過HashKey()函數(shù)算出來的，但還是有一定的區(qū)別的。3、哈希表其實(shí)不難，考驗(yàn)的是我們的學(xué)習(xí)態(tài)度，獨(dú)立思考問題，和解決問題的能力。把握這次機(jī)會(huì)大有收獲。劉羽 20121120274：主要負(fù)責(zé)：程序部分算法的實(shí)現(xiàn)，數(shù)據(jù)測(cè)試和部分實(shí)驗(yàn)報(bào)告的撰寫經(jīng)驗(yàn)總結(jié)：1、在程序的重載的函數(shù)里，通過GetAssocAt()函數(shù)來判斷KEY是滯相等，如果不等，則新關(guān)聯(lián)一個(gè)到當(dāng)前的哈希表內(nèi)。否則，返回當(dāng)前值。 2、我們定義有3個(gè)域的節(jié)點(diǎn)，這三個(gè)域分

14、別為學(xué)號(hào)char num30，姓名char name30，地址char address30。這種類型的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)鏈表中的每個(gè)節(jié)點(diǎn)，其中電話號(hào)碼和姓名可分別作關(guān)鍵字實(shí)現(xiàn)哈希表的創(chuàng)建。3、“哈希表問題”基本算法老師在課堂上有涉及過，但具體的還要靠自己去鉆研。通過本次課程設(shè)計(jì)對(duì)哈希表問題有了一個(gè)比較全面的認(rèn)識(shí)和了解。 六、【項(xiàng)目運(yùn)作描述（Operate）】(10%)在運(yùn)作部分沒有圖形界面，只能在DOS下面運(yùn)行，雖然成本很低，但推廣的價(jià)值意義不是很大。且此次程序仍然能夠滿足一些要求，比如哈希表的建立以及解決沖突問題，程序中查找也可以正常實(shí)現(xiàn)，是基本達(dá)到了實(shí)驗(yàn)的要求。七、【代碼】(10%)#inclu

15、de<stdio.h> #include<string.h> #define NULL 0 unsigned int key; unsigned int key2; int *p; struct node char name8,address20; char num11; node * next; ; typedef node* pnode; typedef node* mingzi; node *phone; node *nam; node *a; void hash(char num11) int i = 3; key=(int)num2; while(numi!=

16、NULL) key+=(int)numi; i+; key=key%20; void hash2(char name8) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; printf("ndz=%dn",key2); node* input() node *temp; temp = new node; temp->next=NULL; printf("請(qǐng)輸入姓名:"); scanf("%s",temp->n

17、ame); printf("輸入地址："); scanf("%s",temp->address); printf("輸入學(xué)號(hào)："); scanf("%s",temp->num); return temp; int apend() node *newphone; node *newname; newphone=input(); newname=newphone; newphone->next=NULL; newname->next=NULL; hash(newphone->num); h

18、ash2(newname->name); newphone->next = phonekey->next; phonekey->next=newphone; newname->next = namkey2->next; namkey2->next=newname; return 0; void create() int i; phone=new pnode20; for(i=0;i<20;i+) phonei=new node; phonei->next=NULL; void create2() int i; nam=new mingzi2

19、0; for(i=0;i<20;i+) nami=new node; nami->next=NULL; void list() int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) printf("%s_%s_%sn",p->name,p->address,p->num); p=p->next; void list2() int i; node *p; for(i=0;i<20;i+) p=nami->next; while(p) printf(&quo

20、t;%s_%s_%sn",p->name,p->address,p->num); p=p->next; void find(char num11) hash(num); node *q=phonekey->next; while(q!= NULL) if(strcmp(num,q->num)=0) break; q=q->next; if(q) printf("%s_%s_%sn",q->name,q->address,q->num); else printf("無此記錄n"); vo

21、id find2(char name8) hash2(name); node *q=namkey2->next; while(q!= NULL) if(strcmp(name,q->name)=0) break; q=q->next; if(q) printf("%s_%s_%sn",q->name,q->address,q->num); else printf("無此記錄n"); void menu() /菜單 printf("ttt $哈希表實(shí)驗(yàn)$n");printf("ttt 1.添加記錄n"); printf("ttt 2.查找記錄n"); printf("ttt 3.姓名散列n"