课程设计报告哈希表.docx
《课程设计报告哈希表.docx》由会员分享，可在线阅读，更多相关《课程设计报告哈希表.docx（18页珍藏版）》请在冰点文库上搜索。
课程设计报告哈希表
数据结构课程设计
（哈希表的设计）
院系
专业
班级
学生姓名
学号
课程设计日期：
2011年6月26日至2011年7月7日
目录
1、问题描述......................................................3
2、需求分析
1、基本要求……………………………………………3
2、测试数据.......................................................3
3、概要设计......................................................3
4、详细设计......................................................4
5、测试分析.....................................................11
六、课程设计总结.............................................13
七、附录（源代码）.........................................14
1、问题描述
针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
2、需求分析
基本要求：
假设人名为中国姓名的汉语拼音模式。
待填入哈希表的人名共有30个，取平均查找长度的上限为2。
哈希函数用除留余数法构造，用链表法处理冲突。
测试数据：
输入30个人的姓名拼音，即30个字符串，然后用除留余数法构建哈希表并用链表法处理冲突，最后将结果输出，程序自动计算查找长度的总数和平均查找长度，然后用户可以根据需求进行查找操作。
3、概要设计
4、详细设计
头文件
#include
#include
#include
#include
#defineP30/*除数余留法中的除数*/
#defineNULLKEY0
#defineMAX30/*人名个数*/
#definehashlen30/*哈希表长度*/
intsum=0,k=0;
typedefstructNode/*哈希表结构体*/
{
charkey_code[10];/*哈希表地址*/
structNode*next;
}Node;
typedefstructhashtable/*创建哈希表*/
{
intkey;
structNode*next;
}HashTable[MAX];
intHash（intkey）
{
intmode=key%P;/*除留余数法得到的余数*/
returnmode;
}
voidHash_Init（HashTableht）/*哈希表初始化*/
{
inti;
for（i=0;i{
ht[i].key=NULLKEY;
ht[i].next=NULL;
}
}
intCharToInt（charstr[]）{
returnstr[0]+str[1]+str[2];
}
intHash_Insert（HashTableht,Node*node）/*为哈希表分配地址*/
{
intkey=Hash（CharToInt（node->key_code））;
Node*p;
p=（Node*）malloc（sizeof（Node））;
if（ht[key].key==NULLKEY）
{
ht[key].key=key;
ht[key].next=node;
k++;
}
elseif（ht[key].key==key）
{
p=ht[key].next;
k++;
while（p->next!
=NULL）
{
p=p->next;
k++;
}
p->next=node;
k++;
}
return1;
}
Node*Hash_Search（HashTableht,intkey）/*查找函数*/
{
intp0=Hash（key）;
if（ht[p0].key==NULLKEY）
{sum++;returnNULL;}
elseif（ht[p0].key==p0）
{
Node*p=ht[p0].next;
while（p!
=NULL）
{
if（CharToInt（p->key_code）==key）
{sum++;
returnp;
}
p=p->next;
sum++;
}
}
returnNULL;
}
intHash_Create（HashTableht）/*哈希表长度*/
{
inti;
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_Insert（ht,node）;
}
printf（"\nCreateSuccessfully!
\n"）;
return1;
}
inthash_output（HashTableh）/*哈希表的输出部分*/
{
Node*a;
inti,j,count2=0;
a=（Node*）malloc（sizeof（Node））;
j=0;
for（i=0;i{
printf（"%4d",i）;
printf（"%4d",h[i].key）;
if（h[i].next!
=0）
count2++;
j=1;
a=h[i].next;
while（a）
{
printf（"->%s",（*a）.key_code）;
a=（*a）.next;
j++;
count2+=j;
}
printf（"\n"）;
}
returncount2;
}
voidHash_Link（）/*链表法构造函数*/
{
intkey;
inti;
Node*node;
HashTableht;
Hash_Create（ht）;
hash_output（ht）;
printf（"count=%d\n",k）;/*查找总长度*/
printf（"ASL=%d/8\n",k）;/*平均查找长度*/
printf（"请输入要查找的数据：
"）;/*输入查找的姓名*/
scanf（"%s",&key）;
node=Hash_Search（ht,key）;
printf（"查找次数:
%d\n",sum）;
if（node!
=NULL）
printf（"查找成功！
"）;
else
printf（"查找不成功！
"）;
}
voidhash_create（inth[],intstatus[],intdata）
{
intaddress;
intdi;
address=data%P;
if（status[address]==0）
{
h[address]=data;
status[address]=1;
}
else
{
for（di=1;di<=hashlen-1;di++）
{
address=（（data%P）+di）%hashlen;
if（status[address]==0）
{
h[address]=data;
status[address]=1;
break;
}
}
}
return;
}
inthash_search（inth[],intkey）
{intaddress,di;
address=key%P;
if（h[address]==key）/*哈希表中元素与查找元素是否相等*/
return1;
else
{
for（di=1;di<=hashlen-1;di++）/*哈希表中元素与查找元素不相等，查找下一元素*/
{
address=（（key%P）+di）%hashlen;
if（h[address]==key）
{
returndi+1;
break;
}
}
}
if（di>=hashlen）
return0;
}
intmain（）/*主函数*/
{
printf（"\t\t\t************************\n"）;
printf（"\t\t\t哈希表设计\n"）;
printf（"\n"）;
printf（"\t\t\t************************\n"）;
printf（"\n"）;
Hash_Link（）;
}
5、测试分析
测试数据：
随机输入的30个人的姓名拼音
测试过程：
输入30个人的姓名拼音，观察输出结果，并进行查找操作
测试结果：
主界面：
哈希表：
6、课程设计总结
这次数据结构课程设计持续了两周，在这两周中付出了很多，同样也得到了很多。
这次课程设计巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
培养独立思考，深入研究，分析问题、解决问题的能力。
通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。
在本次课程设计中，不得不提的还有合作。
虽说课题不是太难，但有时自己想不明白，通过大家的讨论可以更快和更有效率的解决问题，而且映象还很深刻。
所以以后要多多和同学讨论，毕竟自己的不可能想得很全。
通过这次课程设计，让我学到了很多，让我知道了认真上好专业实验课的重要性，以后多在实践中锻炼自己，毕竟说和做还是有很大差距的，而且写程序的过程中要考虑周到，严密。
在做设计的时候要有信心，有耐心，切勿浮躁。
认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
7、附录（程序源代码）:
#include
#include
#include
#include
#defineP11
#defineNULLKEY0
#defineMAX20
#definehashlen13
intsum=0,k=0;
typedefstructemployee
{
intkey_code;
structemployee*next;
}Employee;
typedefstructhashtable
{
intkey;
structemployee*next;
}HashTable[MAX];
intHash（intkey）
{
intmode=key%P;
returnmode;
}
voidlogo（）
{
printf（"\t\t\t************************\n"）;
printf（"\t\t\t哈希表的基本操作\n"）;
printf（"\n"）;
printf（"\t\t\t\n"）;
printf（"\t\t\t************************\n"）;
printf（"\n"）;
}
voidHash_Init（HashTableht）
{
inti;
for（i=0;i{
ht[i].key=NULLKEY;
ht[i].next=NULL;
}
}
intHash_Insert（HashTableht,Employee*em）
{
intkey=Hash（em->key_code）;
Employee*p;
p=（Employee*）malloc（sizeof（Employee））;
if（ht[key].key==NULLKEY）
{
ht[key].key=key;
ht[key].next=em;
k++;
}
elseif（ht[key].key==key）
{
p=ht[key].next;
k++;
while（p->next!
=NULL）
{
p=p->next;
k++;
}
p->next=em;
k++;
}
return1;
}
Employee*Hash_Search（HashTableht,intkey）
{
intp0=Hash（key）;
if（ht[p0].key==NULLKEY）
{sum++;returnNULL;}
elseif（ht[p0].key==p0）
{
Employee*p=ht[p0].next;
while（p!
=NULL）
{
if（p->key_code==key）
{sum++;
returnp;
}
p=p->next;
sum++;
}
}
returnNULL;
}
intHash_Create（HashTableht）
{
inti;
Employee*em;
Hash_Init（ht）;
printf（"请输入数据：
"）;
for（i=0;i<30;i++）
{
em=（Employee*）malloc（sizeof（Employee））;
scanf（"%d",&em->key_code）;
em->next=NULL;
Hash_Insert（ht,em）;
}
printf（"\nCreateSuccessfully!
\n"）;
return1;
}
voidConFun（）
{
printf（"请按任意键继续...."）;
getch（）;
}
inthash_output（HashTableh）
{
Employee*a;
inti,j,count2=0;
a=（Employee*）malloc（sizeof（Employee））;
j=0;
for（i=0;i{
printf（"%4d",i）;
printf（"%4d",h[i].key）;
if（h[i].next!
=0）
count2++;
j=1;
a=h[i].next;
while（a）
{
printf（"->%d",（*a）.key_code）;
a=（*a）.next;
j++;
count2+=j;
}
printf（"\n"）;
}
returncount2;
}
voidHash_Link（）
{
intkey;
Employee*em;
HashTableht;
Hash_Create（ht）;
hash_output（ht）;
printf（"count=%d\n",k）;
printf（"ASL=%d/30\n",k）;
printf（"请输入要查找的数据：
"）;
scanf（"%d",&key）;
em=Hash_Search（ht,key）;
printf（"查找次数:
%d\n",sum）;
if（em!
=NULL）
printf（"查找成功！
"）;
else
printf（"查找不成功！
"）;
ConFun（）;
}
voidhash_create（inth[],intstatus[],intdata）
{
intaddress;
intdi;
address=data%P;
if（status[address]==0）
{
h[address]=data;
status[address]=1;
}
else
{
for（di=1;di<=hashlen-1;di++）
{
address=（（data%P）+di）%hashlen;
if（status[address]==0）
{
h[address]=data;
status[address]=1;
break;
}
}
}
return;
}
inthash_search（inth[],intkey）{
intaddress,di;
address=key%P;
if（h[address]==key）
return1;
else
{
for（di=1;di<=hashlen-1;di++）
{
address=（（key%P）+di）%hashlen;
if（h[address]==key）
{
returndi+1;
break;
}
}
}
if（di>=hashlen）
return0;
}
voidSelectModel（）
{
inti;
do
{
system（"cls"）;
logo（）;
fflush（stdin）;
printf（"\t
（1）:
除数余留法创建哈希表\n"）;
printf（"\n"）;
printf（"\t
（2）:
退出系统\n"）;
printf（"\n"）;
printf（"\t请选择序号:
"）;
scanf（"%d",&i）;
switch（i）
{
case1:
Hash_Link（）;break;
case2:
{
printf（"感谢您的使用，欢迎下次再来\n"）;
exit（0）;
}
default:
printf（"\t请输入1-6\n"）;
ConFun（）;
break;
}
}while
（1）;
}
intmain（）
{
SelectModel（）;
}
升级会员 