哈希表的设计与实现数据结构与算法课程设计报告.doc

合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程 数据结构与算法 课程设计名称 哈希表的设计与实现 学生姓名 王东东 学号 0804012030 专业班级 08计本（2) 指导教师 王昆仑、李贯虹 2010 年 5 月 课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一，是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并用软件解决问题，培养良好的程序设计技能。 一、 问题分析和任务定义 1、 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1） （2） （3） （4） 查找并显示给定电话号码的记录（5） 查找并显示给定用户名的记录{ char name[30]; char address[30]; char num[30]; node * next; }; ElemNode; （2）、哈希地址的计算 以姓名为关键字的哈希地址计算：从取得的姓名第二个字母开始，取ASCII码累加，对30求余得所求哈希地址 以电话号码为关键字的哈希地址计算：从号码第二位开始，将所有号码累加之后对30求模得哈希地址 （3）、拉链法 链地址法：在散表结构存放在指针指向的单元中。链地址法在解决冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 采用C语言定义如下： #define Max_length 100 Typedef struct{ int key; ElemType data; ElemNode *next; }ElemNode; Typedef struct{ ElemNode *first; }ElemHeader,HashTable[Max_length]; 所有的同义词构成一个单链表，再由一个表头节点指向这个单链表的第一个节点。这些镖头节点组成一个一维数组，即散列表。数组元素的下标对应由散列函数求出的散列地址。 拉链法处理冲突的散列表结构 1 2 5 8 （4）链地址法查找结点的算法思想 a、根据查找节点的关键字算出哈希地址b、在散列地址所指向的单链表中依次寻找节点 c、如果找到，输出节点的信息；否则提示没有找到 三、 详细设计和编码 主流程图。  以号码为关键字的Hash()函数流程图 以姓名为关键字的Hash()函数流程图 添加结点信息流程图: 申请专利开始 按姓名查找流程图: 按号码查找流程图: 编码 1、建立节点 struct node //定义 姓名 地址 电话号码 { char name[30]; char address[30]; char num[30]; node * next; }; typedef node* pnode; //声明了已有数据类型的两个指针变量 typedef node* mingzi; node **phone; node **nam; 2、定义哈希函数 这里我们需要定义两个哈希函数，一个以电话号码为关键字，另一个以姓名ASCII之和求模之后的值为关键字。主要方法为将电话号码从第二位开始逐一累加并将所得结果对30求模得哈希地址；第二种则是将姓名字符进行强制类型转换之后得ASCII码相加对30求模得哈希地址。 =============================求哈希地址源代码========================== void hash(char num[30]) //哈希函数 //将运算的结果所得的余数作为节点的存储地址 { int i = 1; key=(int)num[0]; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%30; } void hash2(char name[30]) //哈希函数 //将运算的结果所得的余数作为节点的存储地址 { int i = 1; key2=(int)name[0]; while(name[i]!=NULL) { key2+=(int)name[i