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

1、目 錄1 前言12 需求分析12.1 任務(wù)和要求12.2 運(yùn)行環(huán)境12.3 開(kāi)發(fā)工具23 分析和設(shè)計(jì)23.1 系統(tǒng)分析及設(shè)計(jì)思路23.2 主要數(shù)據(jù)結(jié)構(gòu)及算法23.3 函數(shù)流程圖34 具體代碼實(shí)現(xiàn)65 課程設(shè)計(jì)總結(jié)155.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果155.2 設(shè)計(jì)結(jié)論17參考文獻(xiàn)17致 謝171 前言從C語(yǔ)言產(chǎn)生到現(xiàn)在，它已經(jīng)成為最重要和最流行的編程語(yǔ)言之一。在各種流行編程語(yǔ)言中，都能看到C語(yǔ)言的影子，如Java的語(yǔ)法與C語(yǔ)言基本相同。學(xué)習(xí)、掌握C語(yǔ)言是每一個(gè)計(jì)算機(jī)技術(shù)人員的基本功之一。 根據(jù)本次課程設(shè)計(jì)的要求，我設(shè)計(jì)小組將編寫(xiě)一個(gè)C語(yǔ)言程序來(lái)處理哈希表問(wèn)題，通過(guò)這個(gè)程序，將針對(duì)自己的班集體

2、中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。2 需求分析2.1 任務(wù)和要求 針對(duì)自己的班集體中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。要求：假設(shè)人名為中國(guó)姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用鏈表法處理沖突。2.2 運(yùn)行環(huán)境（1）WINDOWS2000/XP系統(tǒng)（2）Visual C+ 6.0編譯環(huán)境或TC編譯環(huán)境2.3 開(kāi)發(fā)工具C語(yǔ)言3 分析和設(shè)計(jì)3.1 系統(tǒng)分析及設(shè)計(jì)思路（1）創(chuàng)建哈希表（2）姓名（結(jié)構(gòu)體數(shù)組）初始化 （1） 用除留余數(shù)法構(gòu)建哈希函數(shù)

3、（2） 用鏈表法處理沖突 (3)查找哈希表 在哈希表中進(jìn)行查找，輸出查找的結(jié)果和關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長(zhǎng)度 (4) 顯示哈希表 顯示哈希表的的格式：3.2 主要數(shù)據(jù)結(jié)構(gòu)及算法定義結(jié)構(gòu)體typedef struct hashtable創(chuàng)建哈希表定義函數(shù)Hash_Init(HashTable ht)來(lái)對(duì)哈希表初始化定義函數(shù)Hash_Insert(HashTable ht, Node *node)來(lái)為哈希表分配地址定義函數(shù)Hash_Init(ht)輸入30個(gè)名字定義函數(shù)Hash_Create(HashTable ht)來(lái)求哈希表長(zhǎng)度定義函數(shù)hash_output(HashTable

4、h)來(lái)輸出哈希表定義函數(shù)Hash_Link()構(gòu)造鏈表函數(shù)定義函數(shù)int hash_search(int h,int key)查找輸入的名字3.3 函數(shù)流程圖 （1）哈希表的創(chuàng)建及初始化流程圖 圖3.1 哈希表的創(chuàng)造及初始化流程圖（2）創(chuàng)建哈希表鏈表的流程圖 圖3.2 創(chuàng)造哈希表鏈表的流程圖（3）查找輸入數(shù)據(jù)的流程圖 圖3.3 查找輸入數(shù)據(jù)的流程圖4 具體代碼實(shí)現(xiàn) #include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define P 30 /*除數(shù)余

5、留法中的除數(shù)*/#define NULLKEY 0 #define MAX 30 /*人名個(gè)數(shù)*/#define hashlen 30 /*哈希表長(zhǎng)度*/int sum=0,k=0;typedef struct Node /*哈希表結(jié)構(gòu)體*/ char key_code10; /*哈希表地址*/ struct Node *next;Node;typedef struct hashtable /*創(chuàng)建哈希表*/ int key; struct Node *next;HashTableMAX;int Hash(int key) int mode = key % P; /*除留余數(shù)法得到的余數(shù)*/

6、return mode;void Hash_Init(HashTable ht) /*哈希表初始化*/ int i; for(i = 0; i < MAX; i+) hti.key = NULLKEY; hti.next = NULL; int CharToInt(char str) return str0+str1+str2;int Hash_Insert(HashTable ht, Node *node) /*為哈希表分配地址*/ int key = Hash(CharToInt(node->key_code); Node *p;p=(Node*)malloc(sizeof(N

7、ode); if(htkey.key = NULLKEY) htkey.key = key; htkey.next = node;k+; else if(htkey.key = key) p = htkey.next;k+; while(p->next!= NULL) p = p->next;k+; p->next = node;k+; return 1;Node* Hash_Search(HashTable ht, int key) /*查找函數(shù)*/ int p0 = Hash(key); if(htp0.key = NULLKEY) sum+;return NULL; e

8、lse if(htp0.key = p0) Node *p = htp0.next; while(p != NULL) if(CharToInt(p->key_code) = key) sum+; return p; p = p->next;sum+; return NULL;int Hash_Create(HashTable ht) /*哈希表長(zhǎng)度*/ int i; Node *node; Hash_Init(ht); printf("請(qǐng)輸入姓名："); /*輸入30個(gè)姓名*/ for(i=0;i<30;i+) node = (Node *)malloc

9、(sizeof(Node); scanf("%s",node->key_code); node->next = NULL; Hash_Insert(ht, node); printf("nCreate Successfully!n"); return 1;int hash_output(HashTable h) /*哈希表的輸出部分*/ Node *a;int i,j,count2=0;a=(Node*)malloc(sizeof(Node);j=0;for(i=0;i<hashlen;i+) printf("%4d"

10、;,i);printf("%4d",hi.key);if(hi.next!=0)count2+;j=1;a=hi.next;while(a)printf("->%s",(*a).key_code);a=(*a).next;j+;count2+=j;printf("n");return count2;void Hash_Link() /*鏈表法構(gòu)造函數(shù)*/int key;int i;Node *node; HashTable ht; Hash_Create(ht);hash_output( ht);printf("cou

11、nt=%dn",k); /*查找總長(zhǎng)度*/printf("ASL=%d/8n",k); /*平均查找長(zhǎng)度*/ printf("請(qǐng)輸入要查找的數(shù)據(jù)："); /*輸入查找的姓名*/ scanf("%s",&key); node = Hash_Search(ht, key);printf("查找次數(shù):%dn",sum); if(node != NULL) printf("查找成功！"); else printf("查找不成功！"); void hash_creat

12、e(int h,int status,int data)int address;int di;address=data%P;if(statusaddress=0)haddress=data;statusaddress=1;elsefor(di=1;di<=hashlen-1;di+)address=(data%P)+di)%hashlen;if(statusaddress=0)haddress=data;statusaddress=1;break;return ;int hash_search(int h,int key)int address, di; address=key % P;

13、 if(haddress=key) /*哈希表中元素與查找元素是否相等*/ return 1; else for(di=1;di<=hashlen-1;di+)/*哈希表中元素與查找元素不相等，查找下一元素*/ address=(key%P)+di)%hashlen;if(haddress=key)return di+1;break; if(di>=hashlen)return 0;int main() /*主函數(shù)*/ printf("ttt*n"); printf("ttt 哈希表設(shè)計(jì)n"); printf("n");

14、printf("ttt*n"); printf("n");Hash_Link();5 課程設(shè)計(jì)總結(jié)5.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果 圖5.1程序運(yùn)行結(jié)果1 圖5.2程序運(yùn)行結(jié)果2說(shuō)明：輸入的數(shù)為30個(gè)姓的拼音，查找的為“pan”，輸出的如上圖所示。5.2 設(shè)計(jì)結(jié)論通過(guò)這次課程設(shè)計(jì)，我了解到了許多自身的不足，有很多學(xué)習(xí)過(guò)的知識(shí)，在學(xué)過(guò)之后并沒(méi)有反復(fù)的操作和復(fù)習(xí)，以為課堂上聽(tīng)懂就行了，在這課程設(shè)計(jì)中，這些不足就顯現(xiàn)了出來(lái)，導(dǎo)致經(jīng)常要翻書(shū)，查找一些以為弄懂的問(wèn)題，這次我了解到了，學(xué)習(xí)不僅僅是課堂上聽(tīng)講，還要課后復(fù)習(xí)和操作。課程設(shè)計(jì)是對(duì)我們這學(xué)期的學(xué)習(xí)成果的試金石，對(duì)我們來(lái)說(shuō)是一個(gè)不小的考驗(yàn)，它是我們專(zhuān)業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練?！白约簞?dòng)手，豐衣足食”，通過(guò)這次課程設(shè)計(jì)，我深深體會(huì)到這句千古名言的真正含義，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。實(shí)驗(yàn)過(guò)程中，也對(duì)團(tuán)隊(duì)精神的進(jìn)行了考察，讓我們?cè)诤献髌饋?lái)更加默契，在成功后一起體會(huì)喜悅的心情。果然是團(tuán)結(jié)就是力量，只有互相之間默契融洽的配合才能換來(lái)最終完美的結(jié)果。參考文獻(xiàn)1張福祥. C語(yǔ)言程序設(shè)計(jì)M. 遼寧大學(xué)出版社，2008.12 張福祥，王萌C語(yǔ)言程序設(shè)計(jì)習(xí)題解