哈希表课程设计报告

哈希表设计1需求分析1.1针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序.1.2人名为汉语拼音形式，最长不超过18个字符(如：庄双双zhuangshuangshuang).1.3假设待填入哈希表的人名有30个，平均查找长度为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。1.4在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。1.5测试数据: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,zhuangshuangshuang,$%&^&*等等)2)查找输入:zhuangyuan输出:查找成功输入:zhuangshuangshuang输出:查找失败输入:mochengcheng输出:查找成功输入:zhanglei输出:查找失败(在输入时也输入非法数据来检验)2概要设计2.1哈希表的定义如下:classHashList_T{数据对象:D={A(i,j)={不多于18个字符的字符串}0=i18,0=j2};基本操作:voidcreateHashList(void);操作结果:创建一个哈希表boolisLegal(string&s);前置条件:s是非空字符串后置条件:s合法字符串返回true,否则返回falsevoidshow(boollhs)const;前置条件:lhs被初始化后置条件:lhs为真打印查找成功,否则打印查找失败voidfindName(string&s);前置条件:哈希表已经建立,s非空后置条件:查找所输入的人名在不在哈希表中intgetNumber(string&s)前置条件:s被初始化后置条件:返回s索引的值boolisFull(inti)const前置条件:变量i被初始化并且i不超过哈希表的长度后置条件:第i行的链表满了返回true，否则返回falseboolisExistence(inti,string&s)前置条件:参数被初始化后置条件:s存在返回true,否则返回false};2.2主程序voidmain(){初始化；do{接受命令；处理命令；}while(命令!=退出);}2.3本程序的模块只有两个模块:主程序模块和哈希表模块,调用关系为:主程序模块调用哈希表模块.3详细设计3.1哈希表的私有成员为vectorstring的向量组，每一组的数据个数不超过2个3.2哈希表的基本操作设置:HashList_T(intnumbers=1);HashList_T(constHashList_T&rhs);//初始化哈希表~HashList_T(void);//释放资源HashList_T&operator=(constHashList_T&rhs);//赋值函数voidcreateHashList(void);//创建哈希表boolisLegal(string&s);//判断人名是否合法voidshow(boollhs)const;//显示查找结果voidfindName(void);voidfindName(string&s);//查找特定姓名intgetNumber(string&s);//得到索引号boolisExistence(inti,string&s);//第i行是否存在字符串sboolisFull(inti)const;//第i行向量是否满了其中部分操作的算法:HashList_T::HashList_T(intnumbers){m_numbers=numbers;m_name_ptr=newvectorstring[m_numbers];}HashList_T::~HashList_T(void){delete[]m_name_ptr;}intHashList_T::getNumber(string&s){inti=s.size()%m_numbers;boolresult=isFull(i);if(!result)returni;else{intj;if(m_numbers%2==0)j=m_numbers-1;elsej=m_numbers-2;i=(i+j)%m_numbers;result=isFull(i);while(result){i=(i+j)%m_numbers;result=isFull(i);}returni;}}voidHashList_T::createHashList(void){inti=0,numbers;stringname;cout输入要输入的人名总数:endl;cinnumbers;while(inumbers+1){if(1){strings;cout输入人名:endl;cins;name=s;}boolresult=isLegal(name);while(!result){if(1){strings;cout输入非法,输入人名:endl;cins;name=s;}result=isLegal(name);}intj=getNumber(name);m_name_ptr[j].push_back(name);i++;}}voidHashList_T::findName(void){stringname;inti=1;while(i0){cout输入查找人名endl;cinname;boolresult=isLegal(name);while(!result){cout输入非法,再次输入人名endl;cinname;}findName(name);cout继续?yes--1.no--0endl;cini;}}boolHashList_T::isExistence(inti,string&s){if(m_name_ptr[i].empty())returnfalse;vectorstring::iteratorp;intj;if(m_numbers%2==0)j=m_numbers-1;elsej=m_numbers-2;while(!m_name_ptr[i].empty()){p=m_name_ptr[i].begin();while(p!=m_name_ptr[i].end()){if(*p==s)returntrue;p++;}i=(i+j)%m_numbers;}returnfalse;}3.3主程序算法:voidmain(){HashList_Thash(18);hash.createHashList();hash.findName();}4程序调试4.1本次作业比较简单,只有一个核心算法就是构造散列函数的算法,在调试的时候发现string的问题(系统自带的),输入的人名不应该含有空格字符，否则回出现逻辑错误，这是程序的一个问题，如果要修改成char[]型处理方法类似就没改.在调试其他代码时候没有出现问题,比较顺利的调试成功.4.2有些函数不写系统会自己生成,为了避免出错自己写了上去只是声名并没有定义,如果用了编译器会报错.4.3算法改进:伪随机探查法能够消除基本聚集,但是如果两个关键子有相同的基位置,那么他们就有同样的探查序列.采用双散列法能够避免这样,双散列函数使用两个和散列函数,第一个探查序列的起始值,第二个计算下一个位置的探查步长.4.4经验体会:借助DEBUG调试器和数据观察窗口,可以加快找到程序中的错误,采用软件工程的方法将程序划分层次结构使得代码设计时思路清晰,实现时调试顺利,得到了一次良好的程序设计训练.测试结果:输入要输入的人名总数:30输入人名:输入人名:ASDGHmochengcheng输入非法,输入人名:输入人名:#$%^&qwrdgeyuwei输入非法,输入人名:输入人名:zhuangshuangshuangshuangzhouruifengcreateHashListisLegalgetNumberisExistenceisLegalfindName主程序HashList_T输入非法,输入人名:输入人名:Zhuangyunwangqi输入非法,输入人名:输入人名:zhangyunzhangxiuhua输入人名:输入人名:yuanyanxiongliying输入人名:输入人名:mengxiangyinleiyang输入人名:输入人名:wuxudonghanbingfeng输入人名:输入人名:chenghushengyaoboyu输入人名:输入人名:liyingtaolvxiaohu输入人名:输入人名:liutonghuanglei输入人名:输入人名:wangyinglizhouxiong输入人名:输入人名:lixiangzhangxinxin输入人名:输入人名:hexuyangyuman输入人名:输入人名:linyouluzhangyao输入人名:输入人名:zhangxiaozhangchao输入人名:输入人名:chenzhiwangxinyu输入人名:dongchaoxun输入查找人名:zhuangzhuangzhuangfsff输入非法,再次输入人名qwer45465输入非法,再次输入人名$Zhff输入非法,再次输入人名mochengcheng查找成功继续?yes--1.no--01输入查找人名:zhangyun查找成功继续?yes--1.no--01输入查找人名:zhanglei查找失败继续?yes--1.no--01输入查找人名:leiyang查找成功继续?yes--1.no--00附录hashList.h哈希表的声名hashList.cpp哈希表的定义test.cpp主程序hashList.h文件/*************************************************针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R假设待填入哈希表的人名有30个，平均查找长度为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。***************************************************/#ifndefHASHLIST#defineHASHLIST#includeiostream#includestring#includevectorusingnamespacestd;classHashList_T{public:HashList_T(intnumbers=1);HashList_T(constHashList_T&rhs);~HashList_T(void);HashList_T&operator=(constHashList_T&rhs);//创建哈希表voidcreateHashList(void);//非法数据的检验boolisLegal(string&s);voidshow(boollhs)const;//查找特定姓名voidfindName(void);//得到索引号intgetNumber(string&s);//第i行是否存在字符串sboolisExistence(inti,string&s);boolisFull(inti)const;private:voidfindName(string&s);vectorstrin