文档介绍：哈希表设计
1 需求分析
针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序.
人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang).
假设待填入哈希表的人名有30个,平均查找长度为2。哈希表用除留余数法构造,用伪随机探测在散列法处理冲突。
在输入人名过程中能自动识别非法输入,并给与非法输入的反馈信息要求重新输入。
测试数据:
1)输入数据:zhangyun,mochengcheng,geyuwei,zhouruifeng,yuanyan,mengxiangyin, wuxudong,chenghusheng,wangqi,zhangxiuhua,xiongliying,leiyang,hanbingfeng, zhangchao,yaoboyu,liyingtao,liutong,wangyingli,lixiang,lvxiaohu,huanglei, zhouxiong,zhangxinxin,hexuyang,linyoulu,zhangxiao,chenzhi,dongchaoxun, wangxinyu,yuman,zhangyao.(在输入是可以输入非法数据来检验如:12345,
zhuang shuangshuang,$%&^&*等等)
2)查找输入:zhuangyuan 输出:查找成功
输入:zhuangshuangshuang 输出:查找失败
输入:mochengcheng 输出:查找成功
输入:zhanglei 输出:查找失败
(在输入时也输入非法数据来检验)
2 概要设计
哈希表的定义如下:
class HashList_T
{
数据对象:D={A(i,j)={不多于18个字符的字符串}0=<i<18,0=<j<2};
基本操作:
void createHashList(void);
操作结果:创建一个哈希表
bool isLegal(string&s);
前置条件:s是非空字符串
后置条件:s合法字符串返回true,否则返回false
void show(bool lhs)const;
前置条件:lhs被初始化
后置条件:lhs为真打印查找成功,否则打印查找失败
void findName(string&s);
前置条件:哈希表已经建立,s非空
后置条件:查找所输入的人名在不在哈希表中
int getNumber(string&s)
前置条件:s被初始化
后置条件:返回s索引的值
bool isFull(int i)const
前置条件:变量i被初始化并且i不超过哈希表的长度
后置条件:第i行的链表满了返回true,否则返回false
bool isExistence(int i,string&s)
前置条件:参数被初始化
后置条件:s存在返回true,否则返回false
};
主程序
void main()
{
初始化;
do
{
接受命令;
处理命令;
}while("命令"!="退出");
}
:主程序模块和哈希表模块,调用关系为:主程序模块调用哈希表模块.
3 详细设计
<string>的向量组,每一组的数据个数不超过2个
:
HashList_T(int numbers=1);
HashList_T(const HashList_T&rhs);
//初始化哈希表
~HashList_T(void);
//释放资源
HashList_T& operator=(const HashList_T&rhs);
//赋值函数
void createHashList(void);
//创建哈希表
bool isLegal(string&s);
//判断人名是否合法
void show(bool lhs)const;
//显示查找结果
void findName(void);
void findName(string&s);
//查找特定姓名
int getNumber(string&s);
//得到索引号
bool isExistence(int i,string&s);
//第i行是否存在字符串s
bool isFull(int i)const;
//第i行向量是否满了
其中部分