哈希表及其应用-课程设计

附件4：北京理工大学珠海学院课程设计任务书2010 ～2011学年第二学期学生姓名：专业班级：指导教师：工作部门：一、课程设计题目哈希表应用二、课程设计内容（含技术指标）【问题描述】利用哈希表进行存储。

【任务要求】任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。

设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。

设计目的：实现哈希表的综合操作简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。

显示元素：显示已经创建的哈希表。

查找元素：查找哈希表中的元素，分为查找成功和查找不成功。

插入元素：在哈希表中，插入一个元素，分为插入成功和失败。

删除元素：在已有的数据中，删除一个元素。

退出系统：退出程序。

【测试数据】自行设定，注意边界等特殊情况。

三、进度安排1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。

2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。

编译分析调试错误。

3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。

4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。

5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。

四、基本要求1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。

若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。

2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。

3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。

设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。

从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。

哈希表设计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,zhuang shuangshuang,$%&^&*等等)2)查找输入:zhuangyuan 输出:查找成功输入:zhuangshuangshuang 输出:查找失败输入:mochengcheng 输出:查找成功输入:zhanglei 输出:查找失败(在输入时也输入非法数据来检验)2 概要设计2.1 哈希表的定义如下:class HashList_T{数据对象:D={A(i,j)={不多于18个字符的字符串}0=<i<18,0=<j<2};基本操作:void createHashList(void);操作结果:创建一个哈希表bool isLegal(string&s);前置条件:s是非空字符串后置条件:s合法字符串返回true,否则返回falsevoid 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，否则返回falsebool isExistence(int i,string&s)前置条件:参数被初始化后置条件:s存在返回true,否则返回false};2.2 主程序void main(){初始化；do{接受命令；处理命令；}while("命令"!="退出");}2.3本程序的模块只有两个模块:主程序模块和哈希表模块,调用关系为:主程序模块调用哈希表模块.3 详细设计3.1哈希表的私有成员为vector<string>的向量组，每一组的数据个数不超过2个3.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行是否存在字符串sbool isFull(int i)const;//第i行向量是否满了其中部分操作的算法:HashList_T::HashList_T(int numbers){m_numbers=numbers;m_name_ptr=new vector<string>[m_numbers]; }HashList_T::~HashList_T(void){delete []m_name_ptr;}int HashList_T::getNumber(string&s){int i=s.size()%m_numbers;bool result=isFull(i);if(!result)return i;else{int j;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);}return i;}}void HashList_T::createHashList(void) {int i=0,numbers;string name;cout<<"输入要输入的人名总数:"<<endl;cin>>numbers;while(i<numbers+1){if(1){string s;cout<<"输入人名:"<<endl;cin>>s;name=s;}bool result=isLegal(name);while(!result){if(1){string s;cout<<"输入非法,输入人名:"<<endl;cin>>s;name=s;}result=isLegal(name);}int j=getNumber(name);m_name_ptr[j].push_back(name);i++;}}void HashList_T::findName(void){string name;int i=1;while(i>0){cout<<"输入查找人名"<<endl;cin>>name;bool result=isLegal(name);while(!result){cout<<"输入非法,再次输入人名"<<endl;cin>>name;}findName(name);cout<<"继续?yes--1.no--0"<<endl;cin>>i;}}bool HashList_T::isExistence(int i,string&s) {if(m_name_ptr[i].empty())return false;vector<string>::iterator p;int j;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)return true;p++;}i=(i+j)%m_numbers;}return false;}3.3主程序算法:void main(){HashList_T hash(18);hash.createHashList();hash.findName();}4 程序调试4.1本次作业比较简单,只有一个核心算法就是构造散列函数的算法,在调试的时候发现string的问题(系统自带的),输入的人名不应该含有空格字符，否则回出现逻辑错误，这是程序的一个问题，如果要修改成char[]型处理方法类似就没改.在调试其他代码时候没有出现问题,比较顺利的调试成功.4.2有些函数不写系统会自己生成,为了避免出错自己写了上去只是声名并没有定义,如果用了编译器会报错.4.3算法改进:伪随机探查法能够消除基本聚集,但是如果两个关键子有相同的基位置, 那么他们就有同样的探查序列.采用双散列法能够避免这样,双散列函数使用两个和散列函数,第一个探查序列的起始值,第二个计算下一个位置的探查步长.4.4经验体会:借助DEBUG调试器和数据观察窗口,可以加快找到程序中的错误,采用软件工程的方法将程序划分层次结构使得代码设计时思路清晰,实现时调试顺利,得到了一次良好的程序设计训练.测试结果:输入要输入的人名总数:30输入人名: 输入人名:ASDGH mochengcheng输入非法,输入人名: 输入人名:#$%^&qwrd geyuwei输入非法,输入人名: 输入人名:zhuangshuangshuangshuang zhouruifeng输入非法,输入人名: 输入人名:Zhuangyun wangqi输入非法,输入人名: 输入人名:zhangyun zhangxiuhua输入人名: 输入人名:yuanyan xiongliying输入人名: 输入人名:mengxiangyin leiyang输入人名: 输入人名:wuxudong hanbingfeng 输入人名: 输入人名:chenghusheng yaoboyu输入人名: 输入人名:liyingtao lvxiaohu输入人名: 输入人名:liutong huanglei输入人名: 输入人名:wangyingli zhouxiong输入人名: 输入人名:lixiang zhangxinxin输入人名: 输入人名:hexuyang yuman输入人名: 输入人名:linyoulu zhangyao输入人名: 输入人名:zhangxiao zhangchao输入人名: 输入人名:chenzhi wangxinyu输入人名:dongchaoxun输入查找人名:zhuangzhuangzhuangfsff输入非法,再次输入人名qwer45465输入非法,再次输入人名$Zhff输入非法,再次输入人名mochengcheng查找成功继续?yes--1.no--01输入查找人名:zhangyun查找成功继续?yes--1.no--01输入查找人名:zhanglei查找失败继续?yes--1.no--01输入查找人名:leiyang查找成功继续?yes--1.no--0附录hashList.h 哈希表的声名hashList.cpp 哈希表的定义test.cpp 主程序hashList.h文件/*************************************************针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R 假设待填入哈希表的人名有30个，平均查找长度为2。

设计题目哈希表查找的设计任务：设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。

功能要求：编程实现哈希表查找、插入和建立算法需求分析用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法概要设计typedef struct{int shuzhi;}hashtable;int hash_function(int shuzhi,int Prime);void CreateHashTable(hashtable ht[],int Prime);int InsertHashTable(hashtable ht[], int shuzhi,int Prime);int SearchHash(hashtable ht[], int shuzhi,int Prime);程序调用关系如下：CreateHashTable SearchHashInsertHashTableSearchHashhash_function详细设计#include <stdio.h>#define Length 20#define SUCCESS 1#define UNSUCCESS 0typedef struct{int shuzhi;}hashtable;int hash_function(int shuzhi,int Prime);void CreateHashTable(hashtable ht[],int Prime);int InsertHashTable(hashtable ht[], int shuzhi,int Prime);int SearchHash(hashtable ht[], int shuzhi,int Prime);int hash_function(int shuzhi,int Prime){return(shuzhi % Prime);}void CreateHashTable(hashtable ht[],int Prime){int hash_table_number = 0;int shuzhi = 0;printf("请输入哈希表中关键字个数，不要超过%d\n", Length);scanf("%d", &hash_table_number);for (int i = 0; i < hash_table_number; i++){printf("请输入哈系表的关键字:\n");scanf("%d", &shuzhi);InsertHashTable(ht, shuzhi,Prime);}}int InsertHashTable(hashtable ht[], int shuzhi,int Prime){int result = 0;result = SearchHash(ht, shuzhi,Prime);if (ht[result].shuzhi == 0){ht[result].shuzhi = shuzhi;printf("插入数据成功!\n");return SUCCESS;}else{printf("插入数据失败\n");return UNSUCCESS;}}int SearchHash(hashtable ht[], int shuzhi,int Prime){int hash_address = 0;int i = 0;hash_address = hash_function(shuzhi,Prime); //求hash地址while ((shuzhi != ht[hash_address].shuzhi) && (ht[hash_address].shuzhi!=NULL) && (i < Length)){i++;hash_address = (hash_address + 1) % Prime; //线性探查记录的插入位置}if (i >= Length){printf("哈希表已满\n");return UNSUCCESS;else{return hash_address;}}void Print(hashtable ht[]){printf("哈希表地址存储数值\n");for(int i=0;i<Length;i++){if(ht[i].shuzhi!=NULL)printf("%8d%8d\n",i,ht[i].shuzhi);else continue;}}int main(){hashtable ht[Length];int shuzhi = 0;int Prime;printf("-------------欢迎哈希表系统-----------\n");printf("输入哈希函数除留余数法中的除数：");scanf("%d",&Prime);for (int i = 0; i < Length; i++){ht[i].shuzhi = NULL;}CreateHashTable(ht,Prime);printf("输入要查找元素的关键字:\n");scanf("%d", &shuzhi);i = SearchHash(ht, shuzhi,Prime);if (ht[i].shuzhi == shuzhi){printf("表中存关键字为%d的元素的地址是%d：\n", shuzhi,i); }else{printf("没找到\n");}printf("输出哈希表:\n");Print(ht);return 0;}调试分析1、hash_address = (hash_address + 1) % Prime; //线性探查记录的插入位置一开始写成了hash_address = (hash_address + i) % Prime; //线性探查记录的插入位置，我用笔在纸上算了2遍，才发现了错误2、printf("%8d%8d\n",i,ht[i].shuzhi);一开始没想到这个方法，弄得输出界面很难看，后来才想到的用户手册（1）演示程序的运行环境为Windows Xp系统，Microsoft Visual Studio 6.0中的Microsoft Visual C++ 6.0中运行。

课程设计报告--数据哈希表应用兰州商学院陇桥学院工学系课程设计报告设计题目：数据哈希表应用系别：工学系专业 (方向)：网络工程班年级、班：2012级计算机科学与技术学生姓名：李妮学生学号：20120661116指导教师：王万玉2013年12 月24 日目录二、需求分析： 0三、算法思想： 0四、概要设计： (1)五．系统的设计与实现 (1)六、总结 (3)七、附件（代码、部分图表） (4)哈希表应用一、问题描述哈希表应用设计：设哈希表长为13，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表的查找、插入、删除、显示和退出系统的算法。

二、需求分析：1、功能需求①．用户能够自定义输入数据，存入哈希表里；②．用户能够对当前哈希表进行管理。

操作内容包括：显示当前哈希表、查询某个数据、插入某个数据、删除表中某个数据、退出该系统。

③．程序有良好的交互界面，有操作提示和出错提示，方便用户使用和进出入程序。

2、程序约束①．哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。

②．使用C/C++语言编写，程序模块化设计。

程序可实现用户与计算机的交互过程。

在计算机显示提示信息后，可由用户键入运算命令以实现对应的功能，包含表的建立、数据的查找、插入、删除、显示、退出等功能。

本程序旨在实现哈希函数的构造与处理存储冲突，因而指定哈希表存储的数据类型为简单的整型数字，在实用性上还有所欠缺。

但根据用户需求的变化，可以对程序的基本数据类型进行改造，以实现更为丰富的功能，进而体现哈希表在查找数据时的优越性。

三、算法思想：在设定哈希表的抽象数据类型时，要有查找数据元素的操作。

另外，插入操作和删除操作也要用到查找数据元素操作，以查看该数据元素是否存在，因此可以设计查找元素操作包括插入和删除操作的查找。

因此，查找操作就有两种情况：一种情况是插入操作时寻找空闲单元的查找；另一种情况是在查找和删除操作时寻找该元素是否在哈希表中已存在的查找。

洛阳理工学院课程设计说明书课程名称数据结构设计课题哈希表的设计与实现专业班级学号姓名完成日期 2课程设计任务书设计题目：哈希表的设计与实现设计内容与要求：设计哈希表实现电话号码查询系统。

[基本要求]1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，考察平均查找长度的变化。

指导教师：2014 年课程设计评语成绩：指导教师：年月日【问题描述】如何设计一个结构体数组使该数组中每个元素包含电话号码、用户名、地址。

如何分别以电话号码和用户名为关键字建立哈希表。

如何利用线性探测再散列法解决冲突。

如何实现用哈希法查找并显示给定电话号码的记录。

如何查找并显示给定用户的记录。

手工计算查找不成功的平均查找长度。

【基本要求】设计哈希表实现电话号码查询系统。

设计程序完成以下要求：（1）、设每个记录有下列数据项：电话号码、用户名、地址；（2）、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）、采用再哈希法解决冲突（4）、查找并显示给定电话号码的记录；（5）、查找并显示给定用户的记录。

（6）、在哈希函数确定的前提下，考察平均查找长度的变化。

【测试数据】1.用户名：weiguo，号码：123，地址：gansu2.用户名：zhangkui，号码：321，地址：shanxi【算法思想】进入主函数,用户输入1:输入哈希表元素，然后再选择2或者3按照用户名或者电话号码散列，在这下面又有分支语句选择解决冲突的办法，用线性探测再散列还是再哈希法。

生成哈希表之后，选择查找操作3分别以用户名和电话号码为关键字进行查找。

最后，输出查找不成功的平均查找长度。

在本程序当中用了两种解决冲突的办法，分别是线性探测再散列和再哈希法。

哈希函数构造方法是，除留余数法。

成绩南京工程学院课程设计说明书(论文)题目哈希表的设计与性能分析课程名称数据结构院（系、部、中心）通信工程学院专业信息工程班级 K信息091学生姓名翟珂学号 240092610设计地点信息楼C213指导教师吴海涛设计起止时间：2011年8月29日至2011年9 月9 日目录1．功能描述（或设计目标）2．总体设计（或概要设计）2．1数据结构描述与定义2．2模块设计3．测试结果与分析 (8)4．课程设计总结 (9)参考文献: (10)附录： (11)1．功能描述（或设计目标）哈希表的设计与性能分析要求：（1）数据结构的定义（2）哈希表中，哈希函数构造方法多种多样，同时对于同一哈希函数解决冲突的方法也可以不同。

两者是影响查询算法性能的关键因素。

对于几种典型的哈希函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响(平均查找长度).　处理冲突的实际含义是：为产生冲突的地址寻找下一个哈希地址。

（1）开放定址法 为产生冲突的地址H(key)求得一个地址序列： H0, H1, H2, …, Hs 1≤s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …,s（2）链地址法 将所有哈希地址相同的记录都链接在同一链表中。

线性探测容易产生二次聚集，链地址肯定不会产生二次聚集。

一次聚集的产生主要取决于哈希函数，在哈希函数均匀的前提下，可以认为没有一次聚集。

　2．总体设计（或概要设计）第 3 页共18 页2．1数据结构描述与定义除数余留法#define hashlen 11 //哈希表长Int h[hashlen]={0}; //初始哈希表int status[hashlen]={0}; //状态数组用链地址法数据结构定义：typedef struct employee{int key_code;struct employee *next;}Employee;typedef struct hashtable{int key;struct employee *next;}HashTable[MAX];2．2模块设计系统共分几个模块，每个模块的算法描述及流程图（核心模块）除数余留法：Hash_Create:第 5 页共18 页Hash_Serach:链地址法：Hash_Create::Hash_Serach:3．测试结果与分析：第9 页共18 页4．课程设计总结为期4天的数据结构课程设计结束了，时间真的很快，觉得自己这次真的获得了很多。

《哈希表》课程设计报告数据结构散列表(哈希表)课程设计报告及源代码《哈希表的操作》设计报告一目的通过此次课程设计，让学生充分掌握对哈希表的有关操作，例如除留余数法的运用，处理冲突的三个办法：线性探测再散列，二次探测再散列，连地址法等。

加深学生对于哈希表这种独特存储方式（区别于线性存储和链式存储）的理解，和几种算法之间的优越性的体会。

二需求分析1、功能需求①．用户能够自定义输入单词，存入哈希表里；②．用户能够对当前哈希表进行管理。

操作内容包括：查看当前哈希表、搜索某个单词、插入任意单词、删除表中某个单词、查看当前表的平均搜索长度、置空当前哈希表。

③．程序有良好的交互界面，有操作提示和出错提示，方便用户使用和进出入程序。

2、程序约束①．哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。

②．使用C/C++语言编写，程序模块化设计。

三概要设计1、模块设计程序分为主程序模块和哈希表类定义模块，主程序存放在main.app中，哈希表类存放在HashTable.h头文件中。

①．主程序模块用于数据和DOS用户界面的初始化，主函数mai()内部定义子函数function()，调用哈希表类中的各个功能函数。

②．哈希表类定义Calculate(string s) 单词key值计算函数，类友元形参s传送输入的单词。

由于单词为string型，不方便直接拿来参与取余数计算，故用计算函数求出一个key来，同时可以减少冲突（字母相同的单词key有可能不同）。

FindPos(int key,string value) 地址查找函数，类成员key传送计算出的单词的关键值，value传送输入的单词，下同。

此函数为查找、插入、删除等函数提供地址搜索服务。

Search(int key,string value) 查找函数，类成员 Insert(string value) 插入函数，类成员 Remove(int key,string value) 删除函数，类成员 makeEmpty() 置空哈希表函数，类成员感谢您的阅读，祝您生活愉快。

一: 需求分析 (2)三: 详细设计（含代码分析） (4)1. 程序描述: (4)2 具体步骤 (4)四调试分析和测试结果 (7)五，总结 (10)六. 参考文献; (11)七. 致谢 (11)八.附录 (11): 需求分析问题描述：设计哈希表实现电话号码查询系统。

基本要求1、设每个记录有下列数据项：电话号码、用户名、地址2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。

概要设计进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表, 选2: 以再哈希的方法建立哈希表, 然后用户输入用户信息, 分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,. 当添加一定量的用户信息后, 用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息. 程序用链表的方式存储信息以及构造哈希表。

具体流程图如下所示程序结束详细设计（含代码分析）1. 程序描述 :本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号 码、用户名、地址；用结构体存储struct node{ string phone; //string name; //string address;//node *next; //};2具体步骤1. 要求主要用在哈希法解决冲突， 并且至少尝试用两种方法解决冲突， 定义两 个指针数组存储信息 node *infor_phone[MAX]; node *infor_name[MAX]; 前者以电话号码为关键字检索哈希表中的信息， 后者以姓名为关键字检索哈希表中的 信息 用链式法和再哈希法解决冲突：int hash(string key) //{ //int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1;else i=4;for(;i>=0;i--){ cur=key[i]-'0'; result=result*9+cur;}result%=(MOD); return result;}2. 得到输入信息的哈希码以后， 将相应的信息插入对应的地址， 若产生冲突， 则 循环到这个地址的最后一个节点， 然后再将节点插入到这个位置， 电话号码 姓名 地址 链接下一个地址的指以姓名或者电话号码的前四位运算结果作为哈 希码这样就避免了冲突, 在查找的时候便可直接找到这个地址然后快速的查找到信息:void add_infor_phone(string phone,string name,string address){int value=hash(phone);node *infor=build_infor(phone,name,address);if(infor_phone[value]==NULL)infor_phone[value]=infor;else{node *cur=infor_phone[value];while(cur->next)cur=cur->next;cur->next=infor;}}3. 再哈希法也是解决冲突的常见方法，当同义词产生地址冲突时计算另一个哈希函数地址，知道冲突不再发生，这种方法不易产生聚义，但是增加了计算时间：int hash_agin(int numble,int key) // 将关键字的前四位数经过计算的结果{ // 模上一个定义的数然后返回的数字为return numble%key; // 哈希码}int create(string key){int result=1,cur=0,i;if(key.size()<=4)i=key.size()-1;elsei=4;for(;i>=0;i--){ cur=key[i]-'0';result=result*9+cur;}return result;}4. 同样用链表为储存信息的数据结构，当产生冲突时，将模数减去一然后再寻找地址直到不再产生冲突：void add_infors(string phone,string name,string address){int numble_phone=create(phone),key=MOD,pos_phone,pos_name;while(infor_phone[pos_phone=hash_agin(numble_phone,key)]!=NULL) key--; key=MOD;int numble_name=create(name);while(infor_name[pos_name=hash_agin(numble_name,key)]!=NULL) key--; node *inforphone=new node;node *inforname=new node; inforphone->name=inforname->name=name; inforphone->phone=inforname->phone=phone;inforphone->address=inforname->address=address;inforphone->next=inforname->next=NULL; infor_phone[pos_phone]=inforphone; infor_name[pos_name]=inforname;5 . 帮主函数bool usersayyes() ，返回一个bool 值，要求用户输入一个正确的选项，减少程序因错误输入而出现的问题:bool usersayyes(){string sig;bool continu=true;cout<<" 请输入(N/n) 或(Y/y),(N/n) 代表退出,(Y/y) 代表继续:";while(cin>>sig&&(sig!="Y"&&sig!="y")&&(sig!="N"&&sig!="n")) cout<<" 输入错误, 请重新输入!"<<endl;return sig=="Y"||sig=="y";}四调试分析和测试结果1. 用链式法将用户信息添加到哈希表：2. 以姓名为关键字检索用户信息3. 当哈希表中不存在此项记录时4．再哈希法将用户信息添加到哈希表：5．以姓名为检索在哈希表中查找用户信息6. 以电话为检索在哈希表中查询信息使用哈希表能在较短的时间内查找出数据，程序的结果基本和理论相符合。

学号：0121010340132课程设计题目哈希表查找算法的实现学院计算机科学与技术学院专业计算机科学与技术专业班级计算机1001班姓名指导教师2012 年 6 月27 日课程设计任务书题目: 哈希表查找算法的实现初始条件：理论：完成了《汇编语言程序设计》课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。

实践：完成了《汇编语言程序设计》的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好用户界面的设计。

具体的设计任务及要求：1）输入一些整数，采用哈希表结构存储；2）实现对哈希表的查找；3）程序采用子程序结构，结构清晰；4）友好清晰的用户界面，能识别输入错误并控制错误的修改。

在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。

阅读资料：1）《IBM—PC汇编语言程序设计实验教程》实验2.42）《IBM—PC汇编语言程序设计（第2版）》例6.11时间安排：设计安排一周：周1、周2：完成系统分析及设计。

周3、周4：完成程序调试，和验收。

周5：撰写课程设计报告。

指导教师签名：年月日系主任（或责任教师）签名：年月日目录⒈设计目的与任务 (4)⒈1问题描述 (4)⒈2设计目的 (4)⒈3测试用例 (5)⒉设计分析 (5)⒉1存储结构 (5)⒉2主要算法 (5)⒊设计步骤 (6)⒊1概要设计 (6)⒊2代码设计 (7)⒋调试分析和测试结果 (15)⒋1 编码分析 (15)⒋2 调试运行 (16)⒋3调试结果 (16)⒌心得体会 (17)⒍参考文献 (18)⒈设计目的与任务⒈1问题描述⒈⒈1题目：哈希表查找算法的实现⒈⒈2任务与要求：⑴输入一些整数，采用哈希表结构存储；⑵实现对哈希表的查找；⑶程序采用子程序结构，结构清晰；⑷友好清晰的用户界面，能识别输入错误并控制错误的修改。

哈希表的设计与实现摘要哈希表的设计与实现是用Visual C++ 6.0编写的能够实现数据的存储，更新与查找的程序。

它可以方便的进行基本数据信息的输入（如:、电话、地址等），查询（按查询.按电话号查询），删除（运用删除），添加新的数据等。

易于管理员进行管理。

本设计使用Visual C++ 6.0开发工具利用其提供的各种面向对象的开发工具将数据信息定义在结构体中，运用类实现了对数据不同信息的操作功能。

关键字：哈希表; Visual C++ 6.0; 地址目录1、题目分析 .............................................................2、设计思路 .............................................................2.1问题描述......................................................2.2基本要求......................................................2.3数据结构......................................................3、设计思路 .............................................................4、测试的实验结果和测试过程..............................................4.1详细设计......................................................4.2屏幕截图......................................................4.3问题分析：....................................................5、课程设计体会及问题分析................................................6、参考文献 .............................................................7、源程序清单 ...........................................................1、题目分析在21世纪信息时代里，各个机构企业都需要处理一些庞大的重要的数据，而这些数据既需要随时查找还需要随时纪录新的数据。

一、【问题描述】a)题目内容针对某个单位电话号码簿，设计一个哈希表，并完成相应的建表和查表程序。

b)基本要求1)假定每个记录有下列数据项：电话号码、用户名、地址。

2)以用户名和电话号码为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。

3)可以插入、查找、删除并显示给定用户名的记录，并计算查找长度。

哈希表保存到文件中。

4)哈希表保存到文件中。

二、【需求分析】a)软件的基本功能根据用户的选择，分别以姓名和电话号码做为关键字生成哈希表。

生成哈希表后用户可以根据相应关键字进行数据的查找，若查找到对应的数据则将数据输出到屏幕，在用户选择显示哈希表时，显示完整的哈希表。

b)输入/输出形式输入：自己打入姓名、电话号码、住址；数据的格式为：姓名、电话号码、住址或电话号码、姓名、地址。

输出：在用户需要时，将哈希表显示在屏幕上。

c)测试数据要求测试数据为字符串。

三、【概要设计】a)数据类型定义结构体类型存储每条记录。

struct fen //联系人信息结构体{string name;string add;string num;string phone;}st1,st2,b[100],b1[100];b)主程序流程及模块调用关系。

c)各函数功能void gotoxy(int x, int y)//控制坐标void Menu()//菜单void Menu1()//菜单void Create() //创建名字哈希表void Create1() //创建电话哈希表V oid allplay（）//输出全部联系人V oid allplay1（）//输出全部联系人void chazhao()//查找函数void chazhao1()//查找函数void choice()//选择函数void choice()1//选择函数void clean() //清空电话簿void clean()1 //清空电话簿void del()//删除单个联系人void del()1//删除单个联系人void fan()//泛查找函数void fan()1//泛查找函数void filename(int g)//向文件导入数据void filename1(int g)//向文件导入数据int H1(string k)//哈希取模函数int H1(string k)1//哈希取模函数void hash()//哈希查找函数（精确查找）void hash1()//哈希查找函数（精确查找）void jude()//判断是否有重复数据void jude()1//判断是否有重复数据int main()//主函数void putfile()//从文件读入数据void putfile1()//从文件读入数据四、【编码与调试分析】a)编码与调试过程中遇到的问题及解决的办法(1)在数据冲突的时候，不是向后在探查一位，而是直接覆盖了原有数据，这主要的问题出现在当时没有彻底理解线性探测算法，代码的先后有些问题使得后面的代码根本没有运行。

哈希表课程设计绪论一、教学目标本课程的目标是让学生掌握哈希表的基本原理和应用。

通过本课程的学习，学生将能够理解哈希表的概念、特点和优缺点，掌握哈希表的实现方法和相关算法，并能够运用哈希表解决实际问题。

具体来说，知识目标包括：1.了解哈希表的定义、原理和特点。

2.掌握哈希表的常见实现方法，如数组、链表等。

3.理解哈希表的应用场景和优缺点。

技能目标包括：1.能够使用编程语言实现简单的哈希表。

2.能够运用哈希表解决常见的数据存储和查找问题。

3.能够分析哈希表的性能和优化方法。

情感态度价值观目标包括：1.培养学生的逻辑思维能力和问题解决能力。

2.培养学生对数据结构和算法的兴趣和好奇心。

3.培养学生团队合作和自主学习的习惯。

二、教学内容本课程的教学内容主要包括哈希表的基本原理、实现方法和应用。

具体的教学大纲如下：1.哈希表的定义和原理：介绍哈希表的概念、工作原理和特点。

2.哈希表的实现方法：讲解常见的哈希表实现方法，如数组、链表等，并通过编程实践让学生掌握实现技巧。

3.哈希表的应用场景：介绍哈希表在实际问题中的应用，如字典、排序等。

4.哈希表的优缺点：分析哈希表的优缺点和性能评估方法。

三、教学方法为了激发学生的学习兴趣和主动性，本课程将采用多种教学方法相结合的方式。

包括：1.讲授法：通过讲解哈希表的基本原理和概念，帮助学生建立知识框架。

2.讨论法：学生进行小组讨论，鼓励学生提出问题、分享观点，促进学生的思考和交流。

3.案例分析法：通过分析实际案例，让学生了解哈希表的应用场景和解决方法。

4.实验法：安排编程实验，让学生动手实现哈希表，培养学生的实际操作能力和问题解决能力。

四、教学资源为了支持教学内容和教学方法的实施，本课程将准备以下教学资源：1.教材：选择一本与哈希表相关的教材，提供理论知识的学习参考。

2.参考书：提供一些与哈希表相关的参考书籍，供学生深入学习和拓展知识。

3.多媒体资料：制作课件、教案等多媒体教学资料，以图文并茂的形式呈现教学内容。

哈希函数课程设计一、教学目标本节课的教学目标是让学生了解哈希函数的基本概念、特点和应用，掌握哈希函数的计算方法和原理，培养学生的逻辑思维能力和问题解决能力。

1.了解哈希函数的定义和特点。

2.掌握哈希函数的计算方法和原理。

3.了解哈希函数在计算机科学中的应用。

4.能够使用常用的哈希函数进行数据的哈希计算。

5.能够分析哈希函数的性能和优缺点。

情感态度价值观目标：1.培养学生对计算机科学的好奇心和探索精神。

2.培养学生对哈希函数在信息安全领域的责任感和使命感。

二、教学内容本节课的教学内容主要包括哈希函数的定义、特点、计算方法和应用。

1.哈希函数的定义和特点：介绍哈希函数的定义，解释其将输入数据映射到固定大小的输出值的特点。

2.哈希函数的计算方法：介绍常见的哈希函数计算方法，如MD5、SHA-1等，并解释其计算过程。

3.哈希函数的应用：介绍哈希函数在计算机科学中的应用，如数据存储、密码学等。

三、教学方法为了激发学生的学习兴趣和主动性，本节课将采用多种教学方法相结合的方式。

1.讲授法：教师通过讲解哈希函数的定义、特点和计算方法，引导学生了解和掌握相关知识。

2.案例分析法：教师通过分析实际案例，让学生了解哈希函数在计算机科学中的应用。

3.实验法：学生通过实验，亲自进行哈希函数的计算，加深对哈希函数的理解。

四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，我们将准备以下教学资源。

1.教材：选用权威的计算机科学教材，为学生提供系统的学习资料。

2.参考书：提供相关的参考书籍，供学生深入了解哈希函数的更多内容。

3.多媒体资料：制作精美的PPT和教学视频，帮助学生形象地理解哈希函数的概念和原理。

4.实验设备：准备计算机实验室，让学生能够进行哈希函数的计算和实验。

五、教学评估本节课的评估方式将包括平时表现、作业和考试三个部分，以全面客观地评价学生的学习成果。

1.平时表现：通过观察学生在课堂上的参与程度、提问和回答问题的表现，评估学生的学习态度和理解程度。