 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
数据结构的课程设计--哈希表设计
下载积分：900
内容提示：数据结构的课程设计--哈希表设计
文档格式：DOC|
浏览次数：17|
上传日期： 23:28:29|
文档星级：
该用户还上传了这些文档
数据结构的课程设计--哈希表设计
官方公共微信哈希查找 数据结构实验报告_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
哈希查找 数据结构实验报告
上传于||文档简介
&&哈​希​查​找​ ​数​据​结​构​实​验​报​告
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢数据结构和算法（16）
哈希表也叫散列表，散列存储结构主要是面向查找的。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。
散列地址/存储位置&=
f（关键字）
哈希表/散列表的构造主要依赖两个问题的解决：
1、散列函数的构造方法；
2、散列冲突的处理方法。
构造散列函数的两个原则：
1、计算简单；
2、散列地址/存储位置/f()函数值均匀分布。
散列函数的构造方法：
直接定址法
f（key）= a * key +b （a、b为常数）
适合于知道关键字分布，且查找表较小且连续的情况。
数字分析法
抽取部分数字进行诸如：反转、左环位移、右环位移、前两数与后两数相加
适合于知道关键字分布，且关键字位数较多，关键字的若干位分布比较均匀的情况。
平方取中法
数字平方后取中间的几位
适合于不知道关键字分布，且关键字位数不多的情况。
将数字串平均分几个部分后求和
适合于不知道关键字分布，且关键字位数较多的情况。
除留余数法（最常用）
f（key）= key mod p（p &= m）
f（key）= random（key）
适合于关键字长度不等的情况。
散列冲突的处理方法：
开放定址法（线性探测）
fi（key）= （f（key）+ di） MOD m
di = 1, 2, 3, ...., m-1
开放定址法（二次探测）
fi（key）= （f（key）+ di） MOD m
di = 1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2, q&=m/2
开放定址法（随机探测）
fi（key）= （f（key）+ di） MOD m
di是一个伪随机数列，即：用同样的随机种子，每次得到的数列是相同的。
再散列函数法
fi（key）= RHi（key）
i = 1, 2, ..., k & & RHi是不同散列函数，可以使用不同的散列函数构造方法构造。
散列表中只存储指针，指针指向同义词子表。
公共区溢出法
散列表中只存储一个记录，其他同义词存储在公共溢出区。
散列表查找性能的分析角度：
1、散列函数是否均匀；
2、处理冲突的方法；
3、散列表的装填因子：装填因子 = 填入表中的记录个数 / 散列表的长度。装填因子越大，冲突的可能性越大。通常做法是将散列表的长度设置得比查找集合大，以空间换时间，提高查找效率。
// Filename: hash.h
#ifndef HASH_H_INCLUDED
#define HASH_H_INCLUDED
#define HASH_TABLE_SIZE 10
// Hash表大小，根据实际情况修改
typedef int HElemT // Hash表中存储的元素类型，根据实际情况修改
#define HASH_ELEM_INVALID_VALUE 0x7FFFFFFF // 无效的元素值，假设为最大正整数
typedef struct HashTable
HElemType *pE
// Hash表，数组形式，动态分配, 每个元素初始值为HASH_ELEM_INVALID_VALUE
// Hash表中能够存储的元素，Hash表申请后固定不变
// Hash表中已经存储的元素，初始为0，每插入一个加一
#define HASH_ERROR_INIT
#define HASH_ERROR_MALLOC
#define HASH_ERROR_KEY
#define HASH_ERROR_FULL
#define HASH_ERROR_NOT_FOUND
int hash_main();
#endif // HASH_H_INCLUDED
// Filename: hash.c
#include &stdio.h&
#include &stdlib.h&
#include &public.h&
#include &hash.h&
// 哈希表初始化，哈希表长度为size
int InitHashTable(HashTable *pH, int size)
int i = 0;
if ((!pH) || (size &= 0))
return HASH_ERROR_INIT;
pH-&pElem =
malloc(sizeof(HElemType) * size);
if (!pH-&pElem)
return HASH_ERROR_MALLOC;
for (i = 0; i & i++)
pH-&pElem[i] = HASH_ELEM_INVALID_VALUE;
pH-&totalnum =
pH-&existnum = 0;
return OK;
// 散列函数：计算散列地址
int Hash(int key)
return key % HASH_TABLE_SIZE;
// 查找关键字，返回散列地址
int SearchHash(HashTable *pH, int key, int *pAddr)
if ((!pH) || (!pAddr)) return ERROR;
// key值不能和Hash表元素的初始默认值相同，否则就会被后面的元素覆盖
if (HASH_ELEM_INVALID_VALUE == key) return HASH_ERROR_KEY;
// 进行查找操作
*pAddr = Hash(key);
while (pH-&pElem[*pAddr] != key)
*pAddr = (*pAddr + 1) % HASH_TABLE_SIZE;
if ((HASH_ELEM_INVALID_VALUE == pH-&pElem[*pAddr]) || (*pAddr == Hash(key)))
return HASH_ERROR_NOT_FOUND;
return OK;
// 插入元素，冲突处理方法：开放定址法线性探测
int InsertHash(HashTable *pH, int key)
if (!pH) return ERROR;
// key值不能和Hash表元素的初始默认值相同，否则就会被后面的元素覆盖
if (HASH_ELEM_INVALID_VALUE == key) return HASH_ERROR_KEY;
// 表满则无法插入，返回错误
if (pH-&existnum &= pH-&totalnum) return HASH_ERROR_FULL;
// 已经插入的元素，不能重复插入
if (OK == SearchHash(pH, key, &addr))
printf(&该元素已经在哈希表中，无需重复插入\n&);
return OK;
// 进行插入操作
addr = Hash(key);
while (HASH_ELEM_INVALID_VALUE != pH-&pElem[addr])
addr = (addr + 1) % HASH_TABLE_SIZE;
pH-&pElem[addr] =
pH-&existnum++;
return OK;
// 删除关键字，有则删除，没有不做操作
int DeleteHash(HashTable *pH, int key)
if (!pH) return ERROR;
// key值不能和Hash表元素的初始默认值相同，否则就会被后面的元素覆盖
if (HASH_ELEM_INVALID_VALUE == key) return HASH_ERROR_KEY;
if (OK == SearchHash(pH, key, &addr))
if (pH-&existnum &= 0) pH-&existnum = 1; // 此处应提示异常，说明程序实现有问题;
pH-&pElem[addr] = HASH_ELEM_INVALID_VALUE;
pH-&existnum--;
//printf(&DeleteHash(): 未找到待删除元素%d.&, key);
return OK;
// 打印哈希表
void PrintHash(HashTable *pH)
printf(&哈希表: 空间大小: %d, 元素数量: %d.\n&, pH-&totalnum, pH-&existnum);
printf(&-----------------------------------\n&);
printf(&下标
元素值\n&);
printf(&-----------------------------------\n&);
for (i = 0; i & pH-& i++)
printf(&%-8d%-6d\n&, i, pH-&pElem[i]);
printf(&-----------------------------------\n&);
int hash_main()
HashTable H;
printf(&----------------------------------\n&);
printf(&哈希表基本操作\n&);
printf(&----------------------------------\n&);
printf(&0.创建/初始化哈希表\n&);
printf(&1.插入元素\n&);
printf(&2.删除元素\n&);
printf(&3.查找元素\n&);
printf(&4.打印哈希表\n&);
printf(&9.退出系统\n&);
printf(&----------------------------------\n&);
printf(&请选择:&);
scanf(&%d&, &input);
getchar();
switch (input)
retCode = InitHashTable(&H, HASH_TABLE_SIZE);
if (OK == retCode)
printf(&创建/初始化哈希表成功!\n&);
printf(&创建/初始化哈希表失败!!!\n&);
printf(&请输入待插入元素: --& &);
scanf(&%d&, &key);
retCode = InsertHash(&H, key);
if (OK == retCode)
printf(&插入元素成功!\n&);
printf(&插入元素失败!!!\n&);
printf(&请输入待删除元素: --& &);
scanf(&%d&, &key);
retCode = DeleteHash(&H, key);
if (OK == retCode)
printf(&删除元素成功!\n&);
printf(&删除元素失败!!!\n&);
printf(&请输入待查找元素: --& &);
scanf(&%d&, &key);
retCode = SearchHash(&H, key, &addr);
if (OK == retCode)
printf(&查找元素成功, 所在位置为: %d.\n&, addr);
printf(&查找元素失败!!!\n&);
PrintHash(&H);
printf(&系统已退出！\n&);
printf(&无效，请重新选择操作！\n&);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：13865次
排名：千里之外
原创：76篇
(5)(5)(7)(11)(28)(18)(2)福建工程学院；课程设计；课程：算法与数据结构；题目：哈希表；专业：网络工程；班级：xxxxxx班座号：xxxxxxxxxxx；姓名：xxxxxxx；日；实验题目：哈希表；一、要解决的问题；针对同班同学信息设计一个通讯录，学生信息有姓名，；基本要求：姓名以汉语拼音形式，待填入哈希表的人名；运行的环境：MicrosoftVisualC++；二
课 程 设 计
算法与数据结构
xxxxxxxxxxxx
实验题目：哈希表
一、 要解决的问题
针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。
基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。
运行的环境：Microsoft Visual C++ 6.0
二、算法基本思想描述
设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。
1、数据结构的设计和说明
（1）结构体的定义
typedef struct
录入信息结构体的定义，包含姓名，学号，电话号码。
typedef struct
Record *elem[HASHSIZE];
//数据元素存储基址
//当前数据元素个数
//当前容量
哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。
2、关键算法的设计
（1）姓名的折叠处理
long fold(NA s)
//人名的折叠处理
long sum=0;
strcpy(ss,s);
//复制字符串，不改变原字符串的大小写
strupr(ss);
//将字符串ss转换为大写形式
while(*p!='\0')
sum+=*p++;
printf(&\nsum====================%d&,sum);
（2）建立哈希表
1、用除留余数法构建哈希函数
2、用线性探测再散列法处理冲突
int Hash1(NA str)
//哈希函数
n=fold(str);
//先将用户名进行折叠处理
m=n%HASHSIZE;
//折叠处理后的数，用除留余数法构造哈希函数
//并返回模值
}Status collision(int p,int c)
//冲突处理函数，采用二次探测再散列法解决冲突
while(i&HASHSIZE){
if(c%2==0){
q=(p+i*i)%HASHSIZE;
else i=c/2+1;
q=(p-i*i)%HASHSIZE;
else i=c/2+1;
return UNSUCCESS;
void benGetTime();
void CreateHash1(HashTable* H,Record* a)
//建表，以人的姓名为关键字，建立相应的散列表 { int i,p=-1,c,
system(&cls&);
//若哈希地址冲突，进行冲突处理
benGetTime();
for(i=0;i&NUM_BER;i++){
p=Hash1(a[i].name);
while(H-&elem[pp]!=NULL) {
pp=collision(p,c);
printf(&第%d记录无法解决冲突&,i+1);
//需要显示冲突次数时输出
//无法解决冲突，跳入下一循环
H-&elem[pp]=&(a[i]);
//求得哈希地址，将信息存入
H-&count++;
printf(&第%d个记录冲突次数为%d。\n&,i+1,c);
//需要显示冲突次数时输出
printf(&\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n&,HASHSIZE,H-&count);
benGetTime();
（3）查找哈希表
void SearchHash1(HashTable* H,int c)
//在通讯录里查找姓名关键字，若查找成功，显示信息
system(&cls&);
//c用来记录冲突次数,查找成功时显示冲突次数
benGetTime();
printf(&\n请输入要查找记录的姓名：\n&);
scanf(&%s&,str);
p=Hash1(str);
while((H-&elem[pp]!=NULL)&&(eq(str,H-&elem[pp]-&name)==-1))
pp=collision(p,c);
if(H-&elem[pp]!=NULL&&eq(str,H-&elem[pp]-&name)==1){
printf(&\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n&,c);
printf(&姓
名：%s\n学号：%s\n电话号码：%s\n&,H-&elem[pp]-&name,H-&elem[pp]-&xuehao,H-&elem[pp]-&tel);
else printf(&\n此人不存在，查找不成功!\n&);
benGetTime();
（4）显示哈希表
void ShowInformation(Record* a)
//显示输入的用户信息
system(&cls&);
for( i=0;i&NUM_BER;i++)
printf(&\n
（5）主函数的设计
void main(int argc, char* argv[])
{Record a[MAXSIZE];
int c,flag=1,i=0;
HashTable *H;
H=(HashTable*)malloc(LEN);
for(i=0;i&HASHSIZE;i++){
H-&elem[i]=NULL;
H-&size=HASHSIZE;
H-&count=0;
printf(&\n
printf(&\n
欢迎使用同学通讯录录入查找系统
printf(&\n
哈希表的设计与实现&);
printf(&\n
添加用户信息
printf(&\n
读取所有用户信息
printf(&\n
以姓名建立哈希表(再哈希法解决冲突)
printf(&\n
以电话号码建立哈希表(再哈希法解决冲突) &);
printf(&\n
查找并显示给定用户名的记录
printf(&\n
查找并显示给定电话号码的记录
printf(&\n
printf(&\n
printf(&\n
printf(&\n
温馨提示：
printf(&\n
Ⅰ.进行5操作前 请先输出3
printf(&\n
Ⅱ.进行6操作前 请先输出4
&); 第%d个用户信息:\n 姓
名：%s\n 学号：%s\n 电话号码：%s\n&,i+1,a[i].name,a[i].xuehao,a[i].tel);
包含各类专业文献、幼儿教育、小学教育、中学教育、高等教育、生活休闲娱乐、专业论文、数据结构课程设计--哈希表实验报告95等内容。　
　哈希表设计 专业班级:XXX 学姓号:XXX 名:XXX 指导教师:XXX 课程设计时间:XXX 计算机 专业 数据结构 课程设计任务书学生姓名 题目 XXX 专业班级 哈希表设计 工程... 　数据结构课程设计实验报告_工学_高等教育_教育专区。停车场系统设计 ...以姓名建立哈希表的主要函数: void CreateHash1(HashTable* H,Record* a){ ... 　数据结构哈希表实验报告_计算机软件及应用_IT/计算机...C++,哈希表,实验报告HUNAN UNIVERSITY 课程实习报告 ...程序设计流程程序思想 (一) 哈希函数 unsigned int ... 　数据结构课程设计实验报告_工学_高等教育_教育专区。华南农业大学课程论文 ( 设计...在管理线程方面用了静态哈希表, 使服务端很好地去接收各个客户端发来的各种... 　数据结构课程设计报告哈希表设计 姓名: 学号: 院系 :班级 : 二一三年七月 一、需求分析 1.实验内容和实验目的 (1)针对某个集体中的人名设计一个哈希表,使... 　数据结构课程设计实验报告_工学_高等教育_教育专区。数据结构,课设课程...3.程序执行的命令包括: (1)构造哈希表; (2)查找单词出现的次数; (3)找出... 　} cout&&&不存在该学生&&& return 0;} 2、 哈希查找 //哈希表 int...数据结构 课程设计报告 班级:网络工程 112 学号: 姓名:史国凤 ... 　哈希表的设计与实现-数据结构与算法课程设计报告_计算机软件及应用_IT/计算机_专业资料。数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试... 　数据结构 课程设计报告设计题目: 哈希表的设计与实现专 班学学业 通信工程 级___ 生___ 号___ 指导 教师 ___ 起止 时间 XXXXXX 学院 2011 年上 学期 ...}