散列表的设计与实现报告

1、1 / 141 / 14 数据结构课程设计题目：散列表的设计和实现专业：计算机科学和技术指导教师：李竹林姓名：刘朋飞（ 1060309014004 ）何伟（1060309014042 ）2 / 142 / 14 一、需求分析：1. 任务需求：设计散列表实现电话号码查找系统；2. 功能需求：. 设每个记录有下列数据项：电话号码、用户名、地址；. 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；. 采用一定的方法解决冲突；. 查找并显示给定电话号码的记录；. 查找并显示给定用户名的记录；3. 其他功能：. 系统功能的完善；. 设计不同的散列函数，比较冲突率；. 在散列函数确定的前提下，

2、尝试各种不同类型处理冲突的方法，考察平均查找长度的变化；二、总体设计：1. 系统功能设计：定义电话本记录数量（maxsize ） 、表长（ hashsize ） 、姓名长度 (max_size) 以及结构体 typedef struct的内容，构造两个哈希函数hash1 和 hash2。功能示意图：2. 系统功能设计：增加系统功能如下: 添加用户信息 ; 读取所有用户信息; 以姓名建立哈希表;以电话号码建立哈希表; 查找并显示给定用户名的记录; 查找并显示给定电话号码的记录;清屏以及保存功能；处理流程示意图：录入子系统查询子系统姓名地址号码姓名查找号码查询电话号码管理功能示意图3 / 143

3、/ 14 3. 功能模块设计：.运用main 函数输出电话本信息系统的整体界面，在调试运行后如下：开始进入录入系统获得关键字key 用 hash1(key) 计算地址比 较nam_2(d) 的值 是 否 和 关 键 字相等输出记录用探查序列d+i*hash2(key)计算（寻找）散列地址结束比较 nam_ht(d) 的值 是 否 和 关 键 字相等未找到记录处理流程图4 / 144 / 14 . 利用添加功能void getin(record* a) 实现用户信息的录入，在调试运行后如下：.利用哈希函数createhash1.2 来构造哈希表并用status collision 函数的相应功能

4、来查找并解决冲突：5 / 145 / 14 .利用 void searchhash1(hashtable* h,int &c) 在通讯录里查找姓名关键字，若查找成功，显示信息，c 用来记录冲突次数,查找成功时显示冲突次数：三、详细设计和实现部分：定义头文件及基本属性#include #include #include #include #include #define maxsize 20 / 电话薄记录数量#define max_size 20 / 人名的最大长度#define hashsize 53 / 定义表长#define success 1 #define unsuccess

5、 -1 #define len sizeof(hashtable) typedef int status; typedef char namax_size; 定义结构体typedef struct/ 记录na name; na tel; na add; record; typedef struct/ 哈希表6 / 146 / 14 record *elemhashsize; / 数据元素存储基址int count; / 当前数据元素个数int size; / 当前容量hashtable; 关键字比较功能的实现status eq(na x,na y)/ 关键字比较，相等返回success；否则返

6、回unsuccess if(strcmp(x,y)=0) return success; else return unsuccess; 记录个数功能的实现status num_ber; / 记录的个数输入信息功能void getin(record* a)/ 键盘输入各人的信息coutnum_ber; int i; for(i=0;inum_ber;i+) cout 请输入第 i+1; cout 请输入第 i+1ai.tel; cout 请输入第 i+1ai.add; /gets(str2);? 显示输入信息的实现void showinformation(record* a)/显示

7、输入的用户信息 7 / 147 / 14 int i; for( i=0;inum_ber;i+) coutn第 i+1 个 用 户 信 息 :n 姓名 ： n 电 话 号 码 ：ai.teln 联系地址： ai.addn; 清屏功能的实现void cls(record* a) cout*; system(cls); long fold(na s)/ 人名的折叠处理char *p; long sum=0; na ss; strcpy(ss,s);/ 复制字符串，不改变原字符串的大小写strupr(ss);/ 将字符串ss转换为大写形式p=ss; while(*p!=0) sum+

8、=*p+; coutnsum=sum; return sum; 构造哈希函数int hash1(na str)/ 哈希函数long n; int m; n=fold(str);/ 先将用户名进行折叠处理m=n%hashsize; / 折叠处理后的数，用除留余数法构造哈希函数return m; / 并返回模值 int hash2(na str)/ 哈希函数long n; 8 / 148 / 14 int m; n = atoi(str);/ 把字符串转换成整型数. m=n%hashsize; / 用除留余数法构造哈希函数return m; / 并返回模值 冲突处理函数，用于解决冲突status

9、collision(int p,int &c)/冲突处理函数，采用二次探测再散列法解决冲突int i,q; i=c/2+1; while(i=0) return q; else i=c/2+1; else q=(p-i*i)%hashsize; c+; if(q=0) return q; else i=c/2+1; return unsuccess; void bengettime(); void createhash1(hashtable* h,record* a)/ 建表，以人的姓名为关键字，建立相应的散列表bengettime(); int i,p=-1,c,pp; for(i=

10、0;ielempp!=null) pp=collision(p,c); if(pp0) cout 第i+1elempp=&(ai); / 求得哈希地址，将信息存入h-count+; cout 第i+1个记录冲突次数为c.n;/ 需要显示冲突次数时输出 coutn建 表 完 成 !n此 哈 希 表 容 量为 hashsize, 当 前 表内 存 储 的记 录 个 数 为count.n; bengettime(); 查找功能的实现void searchhash1(hashtable* h,int &c)/ 在通讯录里查找姓名关键字，若查找成功， 显示信息bengettime();

11、na str; coutstr; int p,pp; p=hash1(str); pp=p; while(h-elempp!=null)&(eq(str,h-elempp-name)=-1) pp=collision(p,c); if(h-elempp!=null&eq(str,h-elempp-name)=1) coutn 查找成功！ n 查找过程冲突次数为c以下是您需要要查找的信息：nn; cout 姓名：elempp-namen电话号码： elempp-teln联系地址：elempp-addn; else coutn 此人不存在，查找不成功!n; bengettime()

12、; void bengettime() systemtime sys; getlocaltime( &sys ); 10 / 1410 / 14 coutsys.wyearsys.wmonthsys.wdaysys.whoursys.wminutesys.wsecondsys.wmilliseconds; void createhash2(hashtable* h,record* a)/ 建表，以电话号码为关键字，建立相应的散列表bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(pp0

13、) cout 第i+1elempp=&(ai); / 求得哈希地址，将信息存入h-count+; cout 第i+1个记录冲突次数为c。n;/ 需要显示冲突次数时输出 coutn建 表 完 成 !n此 哈 希 表 容 量为 hashsize, 当 前 表内 存 储 的记 录 个 数 为count.n; bengettime(); void searchhash2(hashtable* h,int &c)/ 在通讯录里查找电话号码关键字，若查找成功， 显示信息bengettime(); na tele; couttele; int p,pp; p=hash2(tele); pp=

14、p; while(h-elempp!=null)&(eq(tele,h-elempp-tel)=-1) 11 / 1411 / 14 pp=collision(p,c); if(h-elempp!=null&eq(tele,h-elempp-tel)=1) coutn 查找成功！ n 查找过程冲突次数为c以下是您需要要查找的信息：nn; cout 姓名：elempp-namen电话号码： elempp-teln联系地址：elempp-addn; else coutn 此人不存在，查找不成功!n; bengettime(); 存盘功能的实现：void save() file *f

15、p; if(fp=fopen(c:test.txt, w)=null) printf(nerror opening customet file); fclose(fp); 主界面功能的实现：int main(int argc, char* argv) int c,flag=1; hashtable *h; h=(hashtable*)malloc(len); for(int i=0;ielemi=null; h-size=hashsize; h-count=0; record amaxsize; while (1) coutn ; coutn 欢迎使用电话号码查找系统; coutn ; cou

16、tn 哈希表的设计和实现 ; coutn 【1】. 添加用户信息 ; coutn 【2】. 读取所有用户信息 ; 12 / 1412 / 14 coutn 【3】. 以姓名建立哈希表(再哈希法解决冲突) ; coutn 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ; coutn 【5】. 查找并显示给定用户名的记录 ; coutn 【6】. 查找并显示给定电话号码的记录 ; coutn 【7】. 清屏 ; coutn 【8】. 保存 ; coutn 【9】. 退出程序 ; coutn 温馨提示： ; coutn .进行 5 操作前请先输出3 ; coutn .进行 6 操作前请先输出4

17、 ; coutn ; coutn; cout; coutnum; switch(num) case 1: getin(a); break; case 2: showinformation(a); break; case 3: createhash1(h,a); /* 以姓名建立哈希表*/ break; case 4: createhash2(h,a); /* 以电话号码建立哈希表*/ break; case 5: 13 / 1413 / 14 c=0; searchhash1(h,c); break; case 6: c=0; searchhash2(h,c); break; case 7: cls(a); break; case 8: save(); break; case 9: return 0; break; default: cout你输错