《哈希表课程设计报告》由会员分享，可在线阅读，更多相关《哈希表课程设计报告（15页珍藏版）》请在金锄头文库上搜索。
1、哈希表设计哈希表设计1 1 需求分析需求分析1.1 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过 R，完成相应的 建立和查表程序.1.2 人名为汉语拼音形式，最长不超过 18 个字符(如：庄双双 zhuangshuangshuang).1.3 假设待填入哈希表的人名有 30 个，平均查找长度为 2。哈希表用除留余数法构造， 用伪随机探测在散列法处理冲突。1.4 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。1.5 测试数据:1)输入数据:zhangyun,mochengcheng,geyuwei,zhouruifeng,yuanyan,mengxian
2、gyin, 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,$%Hash
3、List_T(const HashList_T/初始化哈希表HashList_T(void);/释放资源HashList_T/赋值函数void createHashList(void);/创建哈希表bool isLegal(string/判断人名是否合法void show(bool lhs)const;/显示查找结果void findName(void);void findName(string /查找特定姓名int getNumber(string/得到索引号bool isExistence(int i,string/第 i 行是否存在字符串 sbool isFull(int i)const
4、;/第 i 行向量是否满了其中部分操作的算法:HashList_T:HashList_T(int numbers) m_numbers=numbers; m_name_ptr=new vectorm_numbers;HashList_T:HashList_T(void) delete m_name_ptr;int HashList_T:getNumber(stringbool result=isFull(i);if(!result) return i; else int j; if(m_numbers%2=0) j=m_numbers-1; else j=m_numbers-2;i=(i+j)
5、%m_numbers;result=isFull(i);while(result) i=(i+j)%m_numbers; result=isFull(i); return i; void HashList_T:createHashList(void) int i=0,numbers; string name;coutnumbers;while(is; name=s; bool result=isLegal(name);while(!result) if(1) string s;couts; name=s; result=isLegal(name);int j=getNumber(name);
6、m_name_ptrj.push_back(name); i+; void HashList_T:findName(void) string name;int i=1;while(i0) coutname;bool result=isLegal(name);while(!result) coutname; findName(name);couti; bool HashList_T:isExistence(int i,stringvector:iterator p;int j;if(m_numbers%2=0)j=m_numbers-1;elsej=m_numbers-2;while(!m_na
7、me_ptri.empty()p=m_name_ptri.begin();while(p!=m_name_ptri.end() if(*p=s) return true; p+; i=(i+j)%m_numbers;return false;3.3 主程序算法:void main() HashList_T hash(18);hash.createHashList(); hash.findName();createHashListisLegalgetNumberisExistenceisLegalfindName4 4 程序调试程序调试4.1 本次作业比较简单,只有一个核心算法就是构造散列函数的
8、算法,在调试的时候发现 string 的问题(系统自带的),输入的人名不应该含有空格字符，否则回出现逻辑错误， 这是程序的一个问题，如果要修改成 char型处理方法类似就没改.在调试其他代码时 候没有出现问题,比较顺利的调试成功.4.2 有些函数不写系统会自己生成,为了避免出错自己写了上去只是声名并没有定义,如 果用了编译器会报错.4.3 算法改进:伪随机探查法能够消除基本聚集,但是如果两个关键子有相同的基位置, 那么他们就有同样的探查序列.采用双散列法能够避免这样,双散列函数使用两个和散 列函数,第一个探查序列的起始值,第二个计算下一个位置的探查步长.4.4 经验体会:借助 DEBUG 调试
9、器和数据观察窗口,可以加快找到程序中的错误,采用软 件 工程的方法将程序划分层次结构使得代码设计时思路清晰,实现时调试顺利,得到 了一 次良好的程序设计训练.测试结果:输入要输入的人名总数: 30输入人名: 输入人名: ASDGH mochengcheng输入非法,输入人名: 输入人名:#$%class HashList_T public: HashList_T(int numbers=1); HashList_T(const HashList_T HashList_T(void);HashList_T/创建哈希表 void createHashList(void);/非法数据的检验bool
10、isLegal(stringvoid show(bool lhs)const;/查找特定姓名 void findName(void);/得到索引号 int getNumber(string/第 i 行是否存在字符串 sbool isExistence(int i,stringbool isFull(int i)const;private:void findName(string vector *m_name_ptr; int m_numbers; ;#endifhashList.cpp #include “hashList.h“HashList_T:HashList_T(int numbers
11、) m_numbers=numbers; m_name_ptr=new vectorm_numbers; HashList_T:HashList_T(void) delete m_name_ptr; bool HashList_T:isLegal(stringfor(int i=0;iz) return false; return true; void HashList_T:show(bool lhs)const if(lhs) coutnumbers;while(is; name=s; bool result=isLegal(name);while(!result) if(1) string
12、 s;couts;name=s; result=isLegal(name);int j=getNumber(name); m_name_ptrj.push_back(name); i+; void HashList_T:findName(void) string name;int i=1;while(i0) if(1) string s;couts; name=s; bool result=isLegal(name);while(!result) if(1) string s;couts; name=s; result=isLegal(name); findName(name);couti;
13、void HashList_T:findName(stringbool result=isExistence(i,s);show(result); cout:iterator p;int j;if(m_numbers%2=0)j=m_numbers-1;elsej=m_numbers-2;while(!m_name_ptri.empty()p=m_name_ptri.begin();while(p!=m_name_ptri.end() if(*p=s) return true; p+; i=(i+j)%m_numbers;return false; test.cpp 主程序#include “hashList.h“void main() HashList_T hash(18);hash.createHashList(); hash.findName();
