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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：16 大?。?61.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩15頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

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

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

7、境　　2.3 開發(fā)工具　　C語言　　3 分析和設(shè)計　　3.1 系統(tǒng)分析及設(shè)計思路　?。?）創(chuàng)建哈希

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

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

10、Hash_Init(HashTable ht)來對哈希表初始化　　定義函數(shù)Hash_Insert(HashTable ht, Node *node)來為哈希表分配地址　　定義函數(shù)Hash_Init(ht)輸入30個名字　　定義函數(shù)Hash_Create(HashTable ht)來求哈希表長度

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

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

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

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

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

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

17、int key;　　struct Node *next;　　}HashTable[MAX];　　int Hash(int key) 　　{

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

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

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

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

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

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

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

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

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

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

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

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

30、gt;　　}　　}　　return NULL;　　}　　int Hash_Create(HashTable ht) /*哈希表長度*/&

31、lt;/p>　　{ 　　int i;　　Node *node;　　Hash_Init(ht);　　printf("請輸入姓名："); /*輸入30個

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

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

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

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

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

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

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

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

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

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

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

43、= NULL)　　printf("查找成功！");　　else　　printf("查找不成功！");　　}　　vo

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58、遠不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。　　實驗過程中，也對團隊精神的進行了考察，讓我們在合作起來更加默契，在成功后一起體會喜悅的心情。果然是團結(jié)就是力量，只有互相之間默契融洽的配合才能換來最終完美的結(jié)果。　　參考文獻</

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載