课程设计-散列表实现电话号码查找系统.docVIP

华北科技学院

课程设计说明书

学号：

班级:网络B15-1姓名:

设计题目:散列表的设计与实现

设计地点:___________________________

设计时间:2017-2-27至2017-3-10

成绩评定：

1、工作量：A（），B（），C（），D（）,F()

2、难易度：A（），B（），C（），D（）,F()

3、答辩情况：A（），B（），C（），D（）,F()

4、报告规范度：A（），B（），C（），D（）,F()

5、学习态度：A（），B（），C（），D（）,F()

总评成绩:___________________________

指导教师:

一、问题描述与需求分析

1、问题描述

设计散列表实现电话号码查找系统。

2、功能需求分析

1) 每个记录有下列数据项：电话号码、用户名、地址；

2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；

3) 采用一定的方法解决冲突；

4) 查找并显示给定电话号码的记录；

5) 查找并显示给定用户名的记录。

6) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。

二、概要设计

1、总体设计思路

程序的总体实现思路、方法：

本程序使用了链地址法和开放定址法处理冲突，可以实现从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；查找并显示给定电话号码的记录；查找并显示给定用户名的记录；计算使用不同方法处理冲突时的平均查找长度。

当使用链地址法处理冲突，电话号码为关键字建立散列表时，使用除留余数法(t=e-number%n)，确定哈希地址。

当使用链地址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name）的0号位置的字符(name[0])强制转换为int类型(i)，即i=（int）name[0],再使用除留余数法确定哈希地址(i=i%n，n=13)。

当使用开放定址法处理冲突，电话号码为关键字建立散列表时，增量序列取用线性探测再散列法。

当使用开放定址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name2）的0号位置的字符(name2[0])强制转换为int类型(e)，即e=(int)name[0],使用开放定址法取得哈希地址，如果产生冲突增量取用线性探测再散列法。

用户

用

户

名

为关

键字

号码为关键字

添加

查询

用

户

名

为关

键字

号码为关键字

用

户

名

为关

键字

号码为关键字

添加

查询

用

户

名

为关

键字

号码为关键字

链地址法

开放定址法

电话号码查找系统

初始化散列表

记算ASL

2、模块简介

链地址法：

voidhashlistinit(newnode**p)//初始化散列表

voidhashinputname(newnode**p)//添加记录（以用户名为关键字）

voidhashshow2name(newnode**p)//查询记录（以用户名为关键字）

voidhashinput(newnode**p)//添加记录（以号码为关键字）

voidhashshow(newnode**p)//查询记录（以号码为关键字）

voidASL(newnode**p)//计算ASL

开放定址法

voidhashlistinit2(anode3w)//初始化散列表

voidhashinput2(anode3w)//添加记录（以号码为关键字）

voidhashshow2(anode3w)//查询记录（以号码为关键字）

voidhashinputname2(anode3w{//添加记录（以用户名为关键字）

voidhashshow2name2(anode3w)//查询记录（以用户名为关键字）

voidASL2(anode3w)//计算ASL

intscan()//菜单显示函数

intscan2(){//菜单显示函数

三、详细设计

1、数据结构设计

链地址法：

电话号码地址名字指向下一个结点typedefstructnode{

电话号码

地址

名字

指向下一个结点

intnumber;

charaddress[size];

charname[size];

structnode*next;