數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈希表設(shè)計(jì)問(wèn)題

1、<p><b>　　目 錄</b></p><p><b>　　1 前言1</b></p><p><b>　　2 需求分析1</b></p><p>　　2.1 任務(wù)和要求1</p><p>　　2.2 運(yùn)行環(huán)境1</p><p>　

2、　2.3 開(kāi)發(fā)工具2</p><p><b>　　3 分析和設(shè)計(jì)2</b></p><p>　　3.1 系統(tǒng)分析及設(shè)計(jì)思路2</p><p>　　3.2 主要數(shù)據(jù)結(jié)構(gòu)及算法2</p><p>　　3.3 函數(shù)流程圖3</p><p>　　4 具體代碼實(shí)現(xiàn)6</p><

3、;p>　　5 課程設(shè)計(jì)總結(jié)15</p><p>　　5.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果15</p><p>　　5.2 設(shè)計(jì)結(jié)論17</p><p><b>　　參考文獻(xiàn)17</b></p><p><b>　　致 謝17</b></p><p><b

4、>　　1 前言</b></p><p>　　從C語(yǔ)言產(chǎn)生到現(xiàn)在，它已經(jīng)成為最重要和最流行的編程語(yǔ)言之一。在各種流行編程語(yǔ)言中，都能看到C語(yǔ)言的影子，如Java的語(yǔ)法與C語(yǔ)言基本相同。學(xué)習(xí)、掌握C語(yǔ)言是每一個(gè)計(jì)算機(jī)技術(shù)人員的基本功之一。 </p><p>　　根據(jù)本次課程設(shè)計(jì)的要求，我設(shè)計(jì)小組將編寫一個(gè)C語(yǔ)言程序來(lái)處理哈希表問(wèn)題，通過(guò)這個(gè)程序，將針對(duì)自己的班集體中的“人名

5、”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。</p><p><b>　　2 需求分析</b></p><p><b>　　2.1 任務(wù)和要求</b></p><p>　　針對(duì)自己的班集體中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。</p><

6、;p>　　要求：假設(shè)人名為中國(guó)姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用鏈表法處理沖突。</p><p><b>　　2.2 運(yùn)行環(huán)境</b></p><p>　?。?）WINDOWS2000/XP系統(tǒng)</p><p>　?。?）Visual C++ 6.0編譯環(huán)境或TC編譯環(huán)

7、境</p><p><b>　　2.3 開(kāi)發(fā)工具</b></p><p><b>　　C語(yǔ)言</b></p><p><b>　　3 分析和設(shè)計(jì)</b></p><p>　　3.1 系統(tǒng)分析及設(shè)計(jì)思路</p><p><b>　?。?）創(chuàng)建哈希

8、表</b></p><p>　?。?）姓名（結(jié)構(gòu)體數(shù)組）初始化 </p><p>　?。?） 用除留余數(shù)法構(gòu)建哈希函數(shù)</p><p>　?。?） 用鏈表法處理沖突</p><p><b>　　(3)查找哈希表</b></p><p>　　在哈希表中進(jìn)行查找，輸出查找的結(jié)果和關(guān)鍵字，并

9、計(jì)算和輸出查找成功的平均查找長(zhǎng)度</p><p><b>　　(4) 顯示哈希表</b></p><p>　　顯示哈希表的的格式：</p><p>　　3.2 主要數(shù)據(jù)結(jié)構(gòu)及算法</p><p>　　定義結(jié)構(gòu)體typedef struct hashtable創(chuàng)建哈希表</p><p>　　定義函數(shù)

10、Hash_Init(HashTable ht)來(lái)對(duì)哈希表初始化</p><p>　　定義函數(shù)Hash_Insert(HashTable ht, Node *node)來(lái)為哈希表分配地址</p><p>　　定義函數(shù)Hash_Init(ht)輸入30個(gè)名字</p><p>　　定義函數(shù)Hash_Create(HashTable ht)來(lái)求哈希表長(zhǎng)度</p>

11、<p>　　定義函數(shù)hash_output(HashTable h)來(lái)輸出哈希表</p><p>　　定義函數(shù)Hash_Link()構(gòu)造鏈表函數(shù)</p><p>　　定義函數(shù)int hash_search(int h[],int key)查找輸入的名字</p><p><b>　　3.3 函數(shù)流程圖</b></p>

12、<p>　?。?）哈希表的創(chuàng)建及初始化流程圖 </p><p>　　圖3.1 哈希表的創(chuàng)造及初始化流程圖</p><p>　?。?）創(chuàng)建哈希表鏈表的流程圖</p><p>　　圖3.2 創(chuàng)造哈希表鏈表的流程圖</p><p>　?。?）查找輸入數(shù)據(jù)的流程圖</p><p&g

13、t;　　圖3.3 查找輸入數(shù)據(jù)的流程圖</p><p><b>　　4 具體代碼實(shí)現(xiàn)</b></p><p>　　#include <stdio.h></p><p>　　#include <string.h></p><p>　　#include <stdlib.h></p&

14、gt;<p>　　#include <conio.h></p><p>　　#define P 30 /*除數(shù)余留法中的除數(shù)*/</p><p>　　#define NULLKEY 0 </p><p>　　#define MAX 30 /*人名個(gè)數(shù)*/</p><p>　　#de

15、fine hashlen 30 /*哈希表長(zhǎng)度*/</p><p>　　int sum=0,k=0;</p><p>　　typedef struct Node /*哈希表結(jié)構(gòu)體*/</p><p><b>　　{</b></p><p>　　char key_code[10]; /*哈希表地址*/</p&g

16、t;<p>　　struct Node *next;</p><p><b>　　}Node;</b></p><p>　　typedef struct hashtable /*創(chuàng)建哈希表*/ </p><p><b>　　{</b></p><p><b>　　

17、int key;</b></p><p>　　struct Node *next;</p><p>　　}HashTable[MAX];</p><p>　　int Hash(int key) </p><p><b>　　{</b></p><p>　　

18、int mode = key % P; /*除留余數(shù)法得到的余數(shù)*/</p><p>　　return mode;</p><p><b>　　}</b></p><p>　　void Hash_Init(HashTable ht) /*哈希表初始化*/ </p><p><b>　　{<

19、/b></p><p><b>　　int i;</b></p><p>　　for(i = 0; i < MAX; i++)</p><p><b>　　{</b></p><p>　　ht[i].key = NULLKEY;</p><p>　　ht[i].n

20、ext = NULL;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int CharToInt(char str[]){</p><p>　　return str[0]+str[1]+str[2];</p><p>&

21、lt;b>　　}</b></p><p>　　int Hash_Insert(HashTable ht, Node *node) /*為哈希表分配地址*/</p><p><b>　　{</b></p><p>　　int key = Hash(CharToInt(node->key_code));</p>

22、<p><b>　　Node *p;</b></p><p>　　p=(Node*)malloc(sizeof(Node));</p><p>　　if(ht[key].key == NULLKEY)</p><p><b>　　{</b></p><p>　　ht[key].key =

23、 key;</p><p>　　ht[key].next = node;</p><p><b>　　k++;</b></p><p><b>　　}</b></p><p>　　else if(ht[key].key == key) </p><p><

24、b>　　{</b></p><p>　　p = ht[key].next;</p><p><b>　　k++;</b></p><p>　　while(p->next!= NULL) </p><p><b>　　{</b></p><

25、;p>　　p = p->next;</p><p><b>　　k++;</b></p><p><b>　　}</b></p><p>　　p->next = node;</p><p><b>　　k++;</b></p><p>

26、<b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　Node* Hash_Search(HashTable ht, int key) /*查找函數(shù)*/</p><p><b>　　

27、{</b></p><p>　　int p0 = Hash(key);</p><p>　　if(ht[p0].key == NULLKEY) </p><p>　　{sum++;return NULL;} </p><p>　　else if(ht[p0].key == p0) </p>

28、<p><b>　　{</b></p><p>　　Node *p = ht[p0].next;</p><p>　　while(p != NULL)</p><p><b>　　{</b></p><p>　　if(CharToInt(p->key_code) == key)&

29、lt;/p><p>　　{ sum++;</p><p><b>　　return p;</b></p><p><b>　　}</b></p><p>　　p = p->next;</p><p><b>　　sum++;</b></p&

30、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　return NULL;</p><p><b>　　}</b></p><p>　　int Hash_Create(HashTable ht) /*哈希表長(zhǎng)度*/&

31、lt;/p><p><b>　　{ </b></p><p><b>　　int i;</b></p><p>　　Node *node;</p><p>　　Hash_Init(ht);</p><p>　　printf("請(qǐng)輸入姓名："); /*輸入30個(gè)

32、姓名*/</p><p>　　for(i=0;i<30;i++)</p><p><b>　　{</b></p><p>　　node = (Node *)malloc(sizeof(Node));</p><p>　　scanf("%s",node->key_code);</p&g

33、t;<p>　　node->next = NULL;</p><p>　　Hash_Insert(ht, node);</p><p><b>　　} </b></p><p>　　printf("\nCreate Successfully!\n");</p><p><b&

34、gt;　　return 1;</b></p><p><b>　　}</b></p><p>　　int hash_output(HashTable h) /*哈希表的輸出部分*/</p><p><b>　　{ </b></p><p><b>　　Node *a;<

35、/b></p><p>　　int i,j,count2=0;</p><p>　　a=(Node*)malloc(sizeof(Node));</p><p><b>　　j=0;</b></p><p>　　for(i=0;i<hashlen;i++)</p><p><b&

36、gt;　　{ </b></p><p>　　printf("%4d",i);</p><p>　　printf("%4d",h[i].key);</p><p>　　if(h[i].next!=0)</p><p><b>　　count2++;</b></p&

37、gt;<p><b>　　j=1;</b></p><p>　　a=h[i].next;</p><p><b>　　while(a)</b></p><p><b>　　{</b></p><p>　　printf("->%s",(*a

38、).key_code);</p><p>　　a=(*a).next;</p><p><b>　　j++;</b></p><p>　　count2+=j;</p><p><b>　　}</b></p><p>　　printf("\n");</

39、p><p><b>　　}</b></p><p>　　return count2;</p><p><b>　　}</b></p><p>　　void Hash_Link() /*鏈表法構(gòu)造函數(shù)*/</p><p><b>　　{&

40、lt;/b></p><p><b>　　int key;</b></p><p><b>　　int i;</b></p><p>　　Node *node;</p><p>　　HashTable ht;</p><p>　　Hash_Create(ht);<

41、/p><p>　　hash_output( ht);</p><p>　　printf("count=%d\n",k); /*查找總長(zhǎng)度*/</p><p>　　printf("ASL=%d/8\n",k); /*平均查找長(zhǎng)度*/</p><p>　　printf("請(qǐng)輸入要

42、查找的數(shù)據(jù)："); /*輸入查找的姓名*/</p><p>　　scanf("%s",&key);</p><p>　　node = Hash_Search(ht, key);</p><p>　　printf("查找次數(shù):%d\n",sum);</p><p>　　if(node !

43、= NULL)</p><p>　　printf("查找成功！");</p><p><b>　　else</b></p><p>　　printf("查找不成功！");</p><p><b>　　}</b></p><p>　　vo

44、id hash_create(int h[],int status[],int data)</p><p><b>　　{</b></p><p>　　int address;</p><p><b>　　int di;</b></p><p>　　address=data%P;</p>

45、<p>　　if(status[address]==0)</p><p><b>　　{</b></p><p>　　h[address]=data;</p><p>　　status[address]=1;</p><p><b>　　}</b></p><p&g

46、t;<b>　　else</b></p><p><b>　　{</b></p><p>　　for(di=1;di<=hashlen-1;di++)</p><p><b>　　{</b></p><p>　　address=((data%P)+di)%hashlen;

47、</p><p>　　if(status[address]==0)</p><p><b>　　{</b></p><p>　　h[address]=data;</p><p>　　status[address]=1;</p><p><b>　　break;</b><

48、/p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return ;</b></p><p><b>　　}</b>&l

49、t;/p><p>　　int hash_search(int h[],int key)</p><p>　　{int address, di;</p><p>　　address=key % P;</p><p>　　if(h[address]==key) /*哈希表中元素與查找元素是否相等*/</p><p&g

50、t;<b>　　return 1;</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　for(di=1;di<=hashlen-1;di++)/*哈希表中元素與查找元素不相等，查找下一元素*/</p><p&g

51、t;<b>　　{</b></p><p>　　address=((key%P)+di)%hashlen;</p><p>　　if(h[address]==key)</p><p><b>　　{</b></p><p>　　return di+1;</p><p>&l

52、t;b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(di>=hashlen)</p><p><

53、b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int main() /*主函數(shù)*/</p><p><b>　　{ </b></p><p>　　printf("\t\t\t***

54、*********************\n");</p><p>　　printf("\t\t\t 哈希表設(shè)計(jì)\n");</p><p>　　printf("\n");</p><p>　　printf("\t\t\t************************\n");</p&

55、gt;<p>　　printf("\n");</p><p>　　Hash_Link();</p><p><b>　　}</b></p><p><b>　　5 課程設(shè)計(jì)總結(jié)</b></p><p>　　5.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果</p>&

56、lt;p>　　圖5.1程序運(yùn)行結(jié)果1</p><p>　　圖5.2程序運(yùn)行結(jié)果2</p><p>　　說(shuō)明：輸入的數(shù)為30個(gè)姓的拼音，查找的為“pan”，輸出的如上圖所示。</p><p><b>　　5.2 設(shè)計(jì)結(jié)論</b></p><p>　　通過(guò)這次課程設(shè)計(jì)，我了解到了許多自身的不足，有很多學(xué)習(xí)過(guò)的知識(shí)，在學(xué)

57、過(guò)之后并沒(méi)有反復(fù)的操作和復(fù)習(xí)，以為課堂上聽(tīng)懂就行了，在這課程設(shè)計(jì)中，這些不足就顯現(xiàn)了出來(lái)，導(dǎo)致經(jīng)常要翻書，查找一些以為弄懂的問(wèn)題，這次我了解到了，學(xué)習(xí)不僅僅是課堂上聽(tīng)講，還要課后復(fù)習(xí)和操作。</p><p>　　課程設(shè)計(jì)是對(duì)我們這學(xué)期的學(xué)習(xí)成果的試金石，對(duì)我們來(lái)說(shuō)是一個(gè)不小的考驗(yàn)，它是我們專業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練?！白约簞?dòng)手，豐衣足食”，通過(guò)這次課程設(shè)計(jì)，我深深體會(huì)到這句千古名言的真正含義，只有理論知識(shí)是遠(yuǎn)

58、遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。</p><p>　　實(shí)驗(yàn)過(guò)程中，也對(duì)團(tuán)隊(duì)精神的進(jìn)行了考察，讓我們?cè)诤献髌饋?lái)更加默契，在成功后一起體會(huì)喜悅的心情。果然是團(tuán)結(jié)就是力量，只有互相之間默契融洽的配合才能換來(lái)最終完美的結(jié)果。</p><p><b>　　參考文獻(xiàn)</b></

59、p><p>　　[1]張福祥. C語(yǔ)言程序設(shè)計(jì)[M]. 遼寧大學(xué)出版社，2008.1</p><p>　　[2] 張福祥，王萌．C語(yǔ)言程序設(shè)計(jì)習(xí)題解答與實(shí)驗(yàn)實(shí)訓(xùn)[M]．沈陽(yáng)：遼寧大學(xué)出版社，2008．</p><p>　　[3] 牛莉，劉遠(yuǎn)軍等．計(jì)算機(jī)等級(jí)考試輔導(dǎo)教程[M]．北京：中國(guó)鐵道出版社，2008．</p><p><b>　　

60、致 謝</b></p><p>　　本次課程設(shè)計(jì)在選題及進(jìn)行過(guò)程中得到xx老師的悉心指導(dǎo)，xx老師嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度，熱情洋溢的工作激情，將使我終生受益，在老師的影響下我學(xué)到了很多在書本上學(xué)不到的東西，我非常感謝她。謹(jǐn)再一次向xx老師致以誠(chéng)摯的謝意和崇高的敬意。此外我還要感謝組內(nèi)的成員們，因?yàn)樗麄円矌臀医鉀Q了不少難題，正是在大家的共同努力下，本次課程設(shè)計(jì)將隨著論文的完成劃上圓滿的句號(hào)!</p&