課程設計報告-哈希表

1、. 數(shù)據(jù)結(jié)構(gòu)課程設計 （哈希表的設計） 院 系 專 業(yè) 班 級 學 生 姓 名 學 號 課程設計日期：2011年 6月26日至 2011年 7 月 7 日目錄1、 問題描述.32、 需求分析 1、基本要求3 2、測試數(shù)據(jù).33、 概要設計.34、 詳細設計.45、 測試分析.11六、課程設計總結(jié).13七、附錄（源代碼）.141、 問題描述針對自己班級體中的“人名”設計一個哈希表，使得平均查找長度不超過R，完成相應的建表和查表程序。2、 需求分析基本要求： 假設人名為中國姓名的漢語拼音模式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用鏈表法處理沖突。測試數(shù)

2、據(jù)： 輸入30個人的姓名拼音，即30個字符串，然后用除留余數(shù)法構(gòu)建哈希表并用鏈表法處理沖突，最后將結(jié)果輸出，程序自動計算查找長度的總數(shù)和平均查找長度，然后用戶可以根據(jù)需求進行查找操作。3、 概要設計 開始i=0,key i+ N i<Max YHti.key=NULLKEYHti.next=NULLi=0 i+ i<8 N Y輸入em->kry_codeem->next=NULLkey=em->key_code%p Nhtkey.key= NULLKEY NULLKEY NULLKEY NULLKEY Nhtkey.key = key Y htkey.key =

3、key Y htkey.next = em p = htkey.next Np->next!= NULL p->next = em Y p = p->next 結(jié)束4、 詳細設計頭文件#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define P 30 /*除數(shù)余留法中的除數(shù)*/#define NULLKEY 0 #define MAX 30 /*人名個數(shù)*/#define hashlen 30 /*哈希表長度*/int su

4、m=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ù)*/ return mode;void Hash_Init(HashTable ht) /*哈希表初始化*/ int i; for(i = 0; i < MAX; i

5、+) 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(Node); if(htkey.key = NULLKEY) htkey.key = key; htkey.next = node;k+; else if(htkey.

6、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; else if(htp0.key = p0) Node *p = htp0.next; while(p != NULL) if(CharToInt(p->key_

7、code) = key) sum+; return p; p = p->next;sum+; return NULL;int Hash_Create(HashTable ht) /*哈希表長度*/ int i; Node *node; Hash_Init(ht); printf("請輸入姓名："); /*輸入30個姓名*/ for(i=0;i<30;i+) node = (Node *)malloc(sizeof(Node); scanf("%s",node->key_code); node->next = NULL; Hash_

8、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",i);printf("%4d",hi.key);if(hi.next!=0)count2+;j=1;a=hi.next;while(a)pri

9、ntf("->%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("count=%dn",k); /*查找總長度*/printf("ASL=%d/8n",k); /*平均查找長度*/ printf("

10、請輸入要查找的數(shù)據(jù)："); /*輸入查找的姓名*/ scanf("%s",&key); node = Hash_Search(ht, key);printf("查找次數(shù):%dn",sum); if(node != NULL) printf("查找成功！"); else printf("查找不成功！"); void hash_create(int h,int status,int data)int address;int di;address=data%P;if(statusaddress=0)ha

11、ddress=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; if(haddress=key) /*哈希表中元素與查找元素是否相等*/ return 1; else for(di=1;di<=hashlen-1;di+)

12、/*哈希表中元素與查找元素不相等，查找下一元素*/ 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 哈希表設計n"); printf("n"); printf("ttt*n"); printf("n");Hash_Link(); 5、 測試分析測試數(shù)據(jù)：隨機輸入的30個人

13、的姓名拼音測試過程：輸入30個人的姓名拼音，觀察輸出結(jié)果，并進行查找操作測試結(jié)果：主界面：哈希表：6、 課程設計總結(jié) 這次數(shù)據(jù)結(jié)構(gòu)課程設計持續(xù)了兩周，在這兩周中付出了很多，同樣也得到了很多。 這次課程設計鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學知識的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。通過實際編譯系統(tǒng)的分析設計、編程調(diào)試，掌握應用軟件的分析方法和工程設計方法。在本次課程設計中，不得不提的還有合作。雖說課題不是太難，但有時自己想不明白，通過大家的討論可以更快和更有效率的解決問題，而且映象還很深刻。所以以后要多多和同學討論，畢竟自己的不可能想得很全。 通過這次課程設

14、計，讓我學到了很多，讓我知道了認真上好專業(yè)實驗課的重要性，以后多在實踐中鍛煉自己，畢竟說和做還是有很大差距的，而且寫程序的過程中要考慮周到，嚴密。在做設計的時候要有信心，有耐心，切勿浮躁。認真的學習課本知識，掌握課本中的知識點，并在此基礎上學會靈活運用。在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。 7、 附錄（程序源代碼): #include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define P 11#d

15、efine NULLKEY 0#define MAX 20#define hashlen 13int sum=0,k=0;typedef struct employee int key_code; struct employee *next;Employee;typedef struct hashtable int key; struct employee *next;HashTableMAX;int Hash(int key) int mode = key % P; return mode;void logo() printf("ttt*n"); printf("

16、;ttt 哈希表的基本操作n"); printf("n"); printf("ttt n"); printf("ttt*n"); printf("n");void Hash_Init(HashTable ht) int i; for(i = 0; i < MAX; i+) hti.key = NULLKEY; hti.next = NULL; int Hash_Insert(HashTable ht, Employee *em) int key = Hash(em->key_code); Em

17、ployee *p;p=(Employee*)malloc(sizeof(Employee); if(htkey.key = NULLKEY) htkey.key = key; htkey.next = em;k+; else if(htkey.key = key) p = htkey.next;k+; while(p->next!= NULL) p = p->next;k+; p->next = em;k+; return 1;Employee* Hash_Search(HashTable ht, int key)int p0 = Hash(key); if(htp0.ke

18、y = NULLKEY)sum+;return NULL; else if(htp0.key = p0) Employee *p = htp0.next; while(p != NULL) if(p->key_code = key) sum+; return p; p = p->next;sum+; return NULL;int Hash_Create(HashTable ht)int i; Employee *em; Hash_Init(ht); printf("請輸入數(shù)據(jù)："); for(i=0;i<30;i+) em = (Employee *)m

19、alloc(sizeof(Employee);scanf("%d",&em->key_code); em->next = NULL; Hash_Insert(ht, em); printf("nCreate Successfully!n"); return 1;void ConFun() printf("請按任意鍵繼續(xù)."); getch();int hash_output(HashTable h)Employee *a;int i,j,count2=0;a=(Employee*)malloc(sizeof(Emp

20、loyee);j=0;for(i=0;i<hashlen;i+)printf("%4d",i);printf("%4d",hi.key);if(hi.next!=0)count2+;j=1;a=hi.next;while(a)printf("->%d",(*a).key_code);a=(*a).next;j+;count2+=j;printf("n");return count2;void Hash_Link()int key;Employee *em; HashTable ht; Hash_Crea

21、te(ht);hash_output( ht);printf("count=%dn",k);printf("ASL=%d/30n",k); printf("請輸入要查找的數(shù)據(jù)："); scanf("%d",&key); em = Hash_Search(ht, key);printf("查找次數(shù):%dn",sum); if(em != NULL) printf("查找成功！"); else printf("查找不成功！");ConFun();void hash_create(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)%