任务书-哈希表设计问题

哈希表数据结构例题哈希表（HashTables）是一种用于存储数据的结构，它根据键（key）计算出一个值（value），从而将数据存储到对应的位置上。

它是一种用空间换取时间的算法，通过哈希函数将键值转化为整数，并将其映射到一个“桶”中，快速定位查找所需的数据，从而大大减少搜索时间。

哈希表也常用于排序、缓存、验证数据的完整性等方面。

哈希表的原理哈希表的主要原理就是使用一种称为哈希函数（hash function）的算法来将键值转化为整数，然后将其映射到一个“桶”中，也就是一个包含要存储的值的有序数组。

哈希函数是把任意字符串或其他数据类型，转换为一个固定长度的整数，也就是所谓的“哈希值”。

这个哈希值可以根据“哈希函数”的设计，映射到0到桶的大小减一之间的某一个整数。

这样，哈希表就可以把原来的数据，通过哈希值转换为一个范围较小的数，把数据存储到一个有序的桶中，从而大大缩短搜索时间。

哈希表的实现哈希表是使用数组和链表实现的。

数组存放键值对，链表可以解决键值重复的情况，其中每个节点存放着该键值对应的值。

为了更有效的利用存储空间，哈希表有时会采取扩容的方式，即把原来的数组容量翻倍，当存储满的时候就重新分配内存空间，并把原来的数据重新哈希映射到新的桶中。

哈希表的用途哈希表除了作为存储数据的结构，也可以用于排序、缓存、验证数据的完整性等问题。

哈希表常被用来实现快速查找和插入功能，而且它的查找时间复杂度主要取决于所使用的哈希函数，一般在O(1)时间内就可以完成查找。

哈希表也可以快速统计某一个键出现的次数，实现计数排序（Counting Sort）等功能。

哈希表的例题例子1：设计一个哈希表，能够把一个字符串（String）转换为一个哈希值，并且能够用这个哈希值搜索相应的字符串。

解题思路：首先，需要设计一种哈希函数，把一个任意长度的字符串，转换为一个固定长度的哈希值，这里可以采用把字符串中每个字符的ASCII码值相加，再除以字符串长度，取余数的方法。

void find(char num[11]) //在以电话号码为关键字的哈希表中查找用户信息 { hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("无此记录\n"); } b)、void find2(char name[8]) // 在以用户名为关键字的哈希表中查找用户信息 { hash2(name); node *q=nam[key2]->next; while(q!= NULL) { if(strcmp(name,q->name)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("无此记录\n"); }
中� 选择号码散列和姓名散列,由此查看程序运行结果。
至此�就解决了哈希表的设计与实现算法可能出现的各种问题�那么根据以上思路以及对问 题的分析和对出现情况的解决则可以写出源程序。
五、测试结果
程序主菜单:
添加记录: 分别按电话号码和姓名查找:
分别输出按姓名和号码散列的结果:
清空记录:
源代码
#include<stdio.h> #include<string.h> #define NULL 0 unsigned int key; //定义两个关键字 unsigned int key2;

课程设计题目哈希表及其应用教学院计算机学院专业班级姓名指导教师年月日课程设计任务书2010 ～2010 学年第 1 学期一、课程设计题目哈希表及其应用二、课程设计内容建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。

要求：1.使用哈希查找表存储信息；2.实现查找、插入、删除、统计、输出等功能；三、进度安排1．初步完成总体设计，搭好框架；2．完成最低要求：尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价四、基本要求1．界面友好，函数功能要划分好2．程序要加必要的注释3．要提供程序测试方案教研室主任签名：年月日1 概述 (4)2 设计目的 (4)3 设计功能说明 (4)4 详细设计说明 (5)5 流程图 (5)6 程序代码 (6)7 程序运行结果 (15)8 总结 (19)参考文献 (19)成绩评定表 (20)数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁，只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。

通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实际动手能力。

为学生后继课程的学习打下良好的基础。

2 设计目的《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。

因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。

通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。

促使学生养成良好的编程习惯。

1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。

2.培养学生综合运用所学知识独立完成程序课题的能力。

3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。

哈希表设计题目哈希表设计[问题描述]针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

[基本要求]假设人名为中国姓名的汉语拼音形式。

待填入哈希表的人名共有30个，取平均查找长度的上限为2。

构造哈希函数，用链表法处理冲突。

[测试数据]读取熟悉的30个人的姓名作测试。

一．需求分析：1. 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

2. 人名为中国姓名的汉语拼音形式。

待填入哈希表的人名共有30个，取平均查找长度的上限为2。

3. 用每个名字各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字，用除余法构造哈希函数，用拉链法处理冲突。

4.输入数据：zhaoxuening ，muchunyang ，lvzhihui，jiangbiwen，zhangye ，libaoling，yulin，wangjie，huangzheng，xiahaiyun，tanyongli，yangjiaqi，liufengbin，wangfeng，huangweilun，chenliang，hezhicong，yaochengzhong，chaozhihao，wangshipeng，ganyongze，luyang，baichongliang，zhurui，chenyiming，pengxuan，equanming，lishiwei，baitian，wuliao。

5.测试数据：lishiwei，zhurui，abcdefg，wangshipeng二．概要设计1.程序流程图2.存储结构：名字表：struct Name{ //名字表char *name; //名字int key; //关键码}哈希表：struct Node;typedef struct Node * PNode;struct Node{ //每条单链表结点结构定义char *name;PNode link;};struct HashDic{ //哈希表结构定义PNode llist[P]; //哈希表所包含的单链表，P为基本区域长度float search; //总查找长度float total; //哈希表中名字数int m; //哈希表长度};};typedef struct HashDic *PHashDic; //哈希表类型3.主要算法: (1). int h(char *py){ }//除余法，返回名字在哈希表中的相应地址(2) PHashDic create_EmptyDic(){ } //创建空哈希表(3)void insert_node(PHashDic phash,char *py) { } //插入算法(4)void search_node(PHashDic phash){ } //查找算法(5)void delete_node(PHashDic phash){ } //删除算法(6)void output_name(){ } //输出姓名表(7)void output_hash(PHashDic phd){ } //输出哈希表(8)void InitNameTable(){ } //姓名表的初始化(9)void print(){ } //打印操作菜单(10)void main(){ } //主函数三．详细设计1. 除余法，返回名字在哈希表中的相应地址int h(char *py){int key;for (int i=0;i<NAME_LEN;i++) //将字符串的各个字符所对应的ASCII码相加，所得的整数做为名字的关键字{int s=0;char *p=py;for (int j=0;*(p+j)!='\0';j++)s+=int(*(p+j));key=s;}return key%P;}2. 创建空哈希表PHashDic create_EmptyDic(){PHashDic phash=(PHashDic)malloc(sizeof(struct HashDic));int i;phash->search=0;phash->total=0;phash->m=P;for(i=0;i<phash->m;i++){phash->llist[i]=NULL;}return phash;}3. 插入算法void insert_node(PHashDic phash,char *py){PNode p,q;int r=1; //查找长度大于2的py的查找长度nt adr=h(py);if(phash->llist[adr]==NULL){ //如果单链表为空，向单链表插入第一个元素p=(PNode)malloc(sizeof(struct Node)); //创建新结点p->name=py;p->link=NULL;phash->llist[adr]=p;phash->total++;phash->search+=1;return;}q=phash->llist[adr];if (strcmp(q->name,py)==0) //如果已有此元素则不再插入{cout<<"名字已经存在"<<endl;return;}while (q->link!=NULL){if(strcmp(q->link->name,py==0{cout<<"名字已经存在"<<endl;return;}q=q->link;r++;}p=(PNode)malloc(sizeof(struct Node)); //否则就插入单链表最后p->name=py;p->link=NULL;q->link=p;r++;phash->search+=r;phash->total++;}4. 查找算法void search_node(PHashDic phash){PNode p;int adr,r; //哈希表地址和查找长度char py[20];cout<<"请输入要查找的名字:\n";cin>>py;adr=h(py);if(phash->llist[adr]==NULL) cout<<"查找结果:\n"<<"没有想要查找的人!!\n";//如果相应单链表为空，则没有所要查找的名字else {p=phash->llist[adr];while(strcmp(p->name,py)!=0 && p->link!=NULL)//否则对比单链表内容直到查找到名字或对比完单链表中数据{p=p->link;r++;}if(strcmp(p->name,py)==0)cout<<"查找结果:\n"<<"名字:"<<py<<" 地址"<<adr<<" 查找长度"<<r<<endl;//查找到名字else cout<<"查找结果:\n"<<"没有想要查找的人\n"; //对比完单链表中数据,没有该名字}}5. 删除算法void delete_node(PHashDic phash){PNode p,q;int r=1; //查找长度char py[20]={0};cout<<"请输入要删除的名字:\n";cin>>py;int adr=h(py);if(phash->llist[adr]==NULL) //如果相应单链表为空，则没有所要删除的名字{cout<<"没有想要删除的名字!!\n";return;}p=phash->llist[adr];if(strcmp(p->name,py)==0) //如果要删除的是单链表第一个元素{phash->llist[adr]=p->link;free(p);cout<<"删除完成!!\n";phash->total--;phash->search-=1;return;}while(p->link!=NULL && strcmp(p->link->name,py)!=0 )//否则对比单链表内容直到查找到名字或对比完单链表中数据{p=p->link;}if(strcmp(p->link->name,py)==0) //查找到名字{q=p->link;p->link=q->link;free(q);cout<<"删除完成!!\n";r++;phash->search-=r;phash->total--;return;}else //对比完单链表中数据,没有该名字{cout<<"没有想要删除的名字!!\n";return;}}6. //输出姓名表void output_name(){ //输出姓名表int i;printf("序号\t\t 姓名\t\t 关键字\n");for (i=0;i<NAME_LEN;i++)printf("%2d %18s \t\t %d \n",i,NameTable[i].name,NameTable[i].key); }7.输出哈希表void output_hash(PHashDic phd){ //输出哈希表PNode p;float ASL; //平均查找长度nt i;cout<<"地址名字\n";for (i=0;i<P;i++){p=phd->llist[i];cout<<i;while(p!=NULL){cout<<" 一> "<<p->name;p=p->link;}cout<<endl;}ASL=phd->search/phd->total;cout<<"平均查找长度："<<ASL<<endl;}8. 姓名表的初始化void InitNameTable(){NameTable[0].name="zhaoxuening";NameTable[1].name="muchunyang";NameTable[2].name="lvzhihui";NameTable[3].name="jiangbiwen";NameTable[4].name="zhangye";NameTable[5].name="libaoling";NameTable[6].name="yulin";NameTable[7].name="wangjie";NameTable[8].name="huangzheng";NameTable[9].name="xiahaiyun";NameTable[10].name="tanyongli";NameTable[11].name="yangjiaqi";NameTable[12].name="liufengbin";NameTable[13].name="wangfeng";NameTable[14].name="huangweilun";NameTable[15].name="chenliang";NameTable[16].name="hezhicong";NameTable[17].name="yaochengzhong";NameTable[18].name="chaozhihao";NameTable[19].name="wangshipeng";NameTable[20].name="ganyongze";NameTable[21].name="luyang";NameTable[22].name="baichongliang";NameTable[23].name="zhurui";NameTable[24].name="chenyiming";NameTable[25].name="pengxuan";NameTable[26].name="equanming";NameTable[27].name="lishiwei";NameTable[28].name="baitian";NameTable[29].name="wuliao";for (int i=0;i<NAME_LEN;i++)//将字符串的各个字符所对应的ASCII码相加，所得的整数做为名字的关键字{int s=0;for (int j=0;NameTable[i].name[j]!='\0';j++)s+=int(NameTable[i].name[j]);NameTable[i].key=s;}}9. 打印操作菜单void print(){cout<<" ********************************************************\n";cout<<" 操作菜单\n";cout<<" 1.输出姓名表\n";cout<<" 2.输出哈希表\n";cout<<" 3.查找\n";cout<<" 4.删除\n";cout<<" 5.插入\n";cout<<" 6.退出\n";cout<<" ********************************************************\n"; }10.主函数void main(){int i,c,k=0;PHashDic phash=create_EmptyDic(); //创建空哈希表phashInitNameTable();for (i=0;i<NAME_LEN;i++) //将名字表中的名字存入哈希表insert_node(phash,NameTable[i].name);print(); //打印操作菜单cout<<"请选择操作:";cin>>c;while(c!=1&&c!=2&&c!=3&&c!=4&&c!=5&&c!=6) {cout<<"请重新选择操作:";cin>>c;}do{//当选择6时结束算法,选择1，2，3，4，5则执行相应操作直到结束switch(c){case 1:output_name();print();break; //输出姓名表case 2: output_hash(phash);print();break; //输出哈希表case 3:search_node(phash);print();break; //查找case 4:delete_node(phash);print();break; //删除case 5:{char py[20]; //插入cout<<"请输入要插入的名字:\n";cin>>py;insert_node(phash,py);}print();break;case 6:cout<<"已退出\n";break;default:cout<<"\n请输入正确的选择!\n:";}if(c!=6){cout<<"请选择操作:";cin>>c;while(c!=1&&c!=2&&c!=3&&c!=4&&c!=5&&c!=6){cout<<"请重新选择操作:";cin>>c;}}}while (c==1||c==2||c==3||c==4||c==5); }四．调试分析1.输出姓名表2.输出哈希表3.查找：lishiwei和abcdefg4.删除：lishiwei,zhurui,abcdefg5.插入：abcdefg和wangshipeng6.退出五．课程设计总结算法分析及改进：1. 由于要对哈希表进行插入，删除等操作字典元素处于动态，而且名字出现无规律可言，因此采用除余法构造哈希函数h(x) = x mod P 。