

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎ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&
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----哈希表設(shè)計(jì)
- 哈希表設(shè)計(jì)-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈希表設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈希表的設(shè)計(jì)與實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈希表和運(yùn)動(dòng)會(huì)
- 數(shù)據(jù)結(jié)構(gòu)哈希表設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)哈希表設(shè)計(jì)
- 哈希表的設(shè)計(jì)與實(shí)現(xiàn)-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(迷宮問(wèn)題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--迷宮問(wèn)題
- 課程設(shè)計(jì)——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(八皇后問(wèn)題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)順序表課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題
評(píng)論
0/150
提交評(píng)論