哈希表的设计版

《哈希表的设计版》由会员分享，可在线阅读，更多相关《哈希表的设计版（5页珍藏版）》请在装配图网上搜索。

1、哈希表的设计doc版哈希表的设计doc版哈尔滨理工大学课程设 计（数据结构）题目：哈希表设计班级：姓名：指导教师：系主任：2013年03月08日目录1、问题描述3 2、需求分析1、 基本要求2、测试数据,3 3、 概要设计3 4、详细设计4 5、 测试分析,11六、课程设计总结,13七、附录（源代码）,13 1、 问题描述 针对自己班级体中的 大名”设计一个哈希表，使得 平均查找长度不超过 R,完成相应的建表和查表程序。2、需求分析基本要求：假设人名为中国姓名的汉语拼音模式。待填入哈希表的人名共有 30个，取平均查找长度的上限 为2。哈希函数用除留余数法构造，用链表法处理冲突。测试数据：输入3

2、0个人的姓名拼音，即 30个字符串，然后用除留余 数法构建哈希表并用链表法处理冲突，最后将结果输由，程 序自动计算查找长度的总数和平均查找长度，然后用户可以 根据需求进行查找操作。3、 概要设计 开始 i=0,key i+ N ikry_code em-next=NULL key=em-key_code%p N htkey.key= NULLKEY NULLKEY NULLKEY NULLKEY N htkey.key = key Y htkey.key = key Y htkey.next = em p = htkey.next N p-next!= NULL p-next = em Y p

3、 = p-next 结束 4、 详细设计 头文件 #include #include #include #include #define P 30 /* 除数余留法 中的除数*/ #define NULLKEY 0 #define MAX 30 /*人名个数 */ #define hashlen 30 /* 哈希表长度 */ int sum=0,k=0; typedef struct Node /* 哈希 表结构体 */ char key_code10; /* 哈希表地址 */ struct Node *next; Node; typedef struct hashtable /* 创建哈希表

4、 */ int key; struct Node *next; HashTableMAX; int Hash(int key) int mode = key % P; /*除留余数法得到的余数 */ return mode; void Hash_Init(HashTable ht) /* 哈希表初始化 */ int i; for(i = 0; i key_code); Node *p; p=(Node*)malloc(sizeof(Node); if(htkey.key = NULLKEY) htkey.key = key; htkey.next =node; k+; else if(htke

5、y.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) /* 查找函数 */ 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_code) =

6、key) sum+; return p; p = p-next; sum+; return NULL; intHash_Create(HashTable ht) /* 哈希表长度 */ int i; Node *node; Hash_Init(ht); printf(请输入姓名：“)；/输入 30 个姓名 */ for(i=0;ikey_code); node-next = NULL; Hash_Insert(ht, node); printf( nCreaten “);return 1; int hash_output(HashTable h) /* 哈希表的输由部分 */ Node *a;

7、 int i,j,count2=0; a=(Node*)malloc(sizeof(Node); j=0; for(i=0;i%s “ey_code); a=(*a).next; j+; count2+=j; printf( n ); return count2; void Hash_Link() /* 链表法构造 函数*/ int key; int i; Node *node; HashTable ht; Hash_Create(ht); hash_output( ht); printf( count=%d ,k);/* 查找总长度 */ printf(ASL=%d/8 ,k);/*平均查找

8、长度*/print f(请输入要查找的数据：“)7* 输入查找的姓名 */ scanf(snod e = Hash_Search(ht,key); printf(查“找次数n ” ,sum); if(node != NULL)printf(查找成功！“);else printf(查找不成功！“); voidhash_create(int h,int status,int data) int address; int di; address=data%P; if(statusaddress=0) haddress=data; statusaddress=1; else for(di=1;di=h

9、ashlen) return 0; int main()/*主函数*/ printf( n );printf( ttf 哈希 表 设 计 n )；printf( n“)；printf( n ”)； printf( n “);Hash_Link(); 5、测试分析 测试数据： 随机输入的30个人的姓名拼音测试过程：输入30个人的姓名拼音，观察输生结果，并进行查找操作 测 试结果：主界面：哈希表：查找界面：6、课程设计总结 在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个 完整的程序。在上机实验之前，最好将

10、程序编写好在草稿纸上，这样在 编译的时候也比较有效率。这段时间的课程设计，我也认识到数据结构是一门比较 难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。7、附录(程序源代码):#include #include #include #include #define P 30 #define NULLKEY 0 #define MAX 30 #define hashlen 30 int sum=0,k=0; typedef struct Node

11、 char key_code10; struct Node *next; Node; typedef struct hashtable int key; struct Node *next; HashTableMAX; int Hash(int key) int mode = key % P; return mode; void Hash_Init(HashTable ht) int i; for(i = 0; i key_code); Node *p; p=(Node*)malloc(sizeof(Node); if(htkey.key = NULLKEY) htkey.key = key;

12、 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) int p0 = Hash(key); if(htp0.key = NULLKEY) sum+;return NULL; else if(htp0.key = p0) Node *p = htp0.next; while(p != NULL) if

13、(CharToInt(p-key_code) = key) sum+; return p; p = p-next; sum+; return NULL; intHash_Create(HashTable ht) int i; Node *node; Hash_Init(ht); printf(请输入姓名：“);for(i=0;ikey_code); node-next = NULL; Hash_Insert(ht, node); printf( nCreaten a); return 1; inthash_output(HashTable h) Node *a; int i,j,count2=

14、0; a=(Node*)malloc(sizeof(Node);j=0;for(i=0;i%s ” ,(*a).key_coda=(*a).next; j+; count2+=j; printf( n )； return count2; void Hash_Link() int key; int i; Node *node; HashTable ht; Hash_Create(ht); hash_output( ht); printf( count=%d,k);printf(ASL=%d/8 ,k);printf(请输入要查找的姓名：“);scanf(snod e = Hash_Search(

15、ht, key); printf(查找次数 n 二sum);if(node != NULL) printf(查找成功！);elseprintf(查找不成功！)； void hash_creae(int h,int status,intdata) int address; int di; address=data%P; if(statusaddress=0) haddress=data; statusaddress=1; else for(di=1;di=hashlen) return 0; int main() printf( n ”)； printf( n “);printf( ttt 哈 希 表 设 计 n “)； printf( n “); printf( n ”)； printf( n “);Hash_Link(); 第 20 页共 20 页