实习报告
题目：设计一个哈希表，完成相应的建表和查表程序
班级：1503013 姓名：李睿元学号：完成日期：
一、需求分析
1. 假设人名为中国人名的汉语拼音形式；
2. 待填入哈希表的姓名共有30个，去平均查找长度的上限为2；
3. 哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；
4. 取读者周围较熟悉的30个人的姓名。
二、概要设计
1. 抽象数据类型的定义：
（1）人名数据表：
typedef struct Node
{
char name[20];
int key;
}Node,NodeList[MAX];
（2）哈希表：
typedef struct hashtable
{
char* name;
int key;
int conflict_time;
}HashTable[hashlen];
（3）变量：
#define P 61//随机数值
#define MAX 30//人数
#define hashlen 61//哈希表长
2. 主要函数的实现：
（1）哈希函数：
int Hash(int key)
（2）关键字获得：
int GetKey(char str[])
（3）文件流中读取姓名：
void GetName(NodeList &L,int i,FILE* fp)
（4）哈希表的初始化：
void InitialHashTable(HashTable &ht)
（5）伪随机探测序列的生成：
void CreatConfilctArray(int n[])
（6）哈希表的生成：
void CreatHashTable(HashTable &ht,NodeList L,int* n)
（7）哈希表的查询：
void SearchHashTable(HashTable ht,int* n,char get_name[]) 三、详细设计
#include
#include
#include
#define P 61//随机数值
#define MAX 30//人数
#define hashlen 61//哈希表长typedef struct Node
{
char name[20];
int key;
}Node,NodeList[MAX]; typedef struct hashtable {
char* name;
int key;
int conflict_time;
}HashTable[hashlen];
int Hash(int key)
{
return key%P;
}
int GetKey(char str[])
{
int t=0;
char *s=str;
while(*s)
{
t += *s;
s++;
}
return t;
}
void GetName(NodeList &L,int i,FILE* fp)
{
/* printf("请以拼音形式输入第%d个姓名:",i);
scanf("%s",L[i].name);
L[i].key=GetKey(L[i].name); */
fscanf(fp,"%s",L[i].name);
L[i].key=GetKey(L[i].name);
//printf("\n");
}
void InitialHashTable(HashTable &ht)
{
int n=0;
while(n { ht[n].conflict_time=0; ht[n].name=NULL; ht[n].key=0; n++; } } void CreatConfilctArray(int n[]) { // n=(int*)malloc(50*sizeof(int)); int i=0,j=0; while(i<50) { n[i]=rand()%(hashlen+1); for(;j { if(n[i]==n[j]) { j=0; n[i]=rand()%(hashlen+1); continue; } } i++; } } void CreatHashTable(HashTable &ht,NodeList L,int* n) { // CreatConfilctArray(n); int i=0; int t; while(i { t=Hash(L[i].key); if(ht[t].conflict_time==0) { ht[t].name=L[i].name; ht[t].conflict_time++; ht[t].key=L[i].key; printf("姓名：%s key值：%d 表内存储位置：%d\n",L[i].name,L[i].key,t); } else { int m=0; int d=(t+n[m])%hashlen; while(ht[d].conflict_time!=0) { ht[d].conflict_time++; m++; d=(t+n[m])%hashlen; } ht[d].name=L[i].name; ht[d].conflict_time++; ht[d].key=L[i].key; printf("姓名：%s key值：%d 表内存储位置：%d\n",L[i].name,L[i].key,d); } i++; } } void SearchHashTable(HashTable ht,int* n,char get_name[]) { //printf("请输入要查询的姓名："); //char get_name[20]; int p=-1; int s_time=1; // scanf("%s",get_name); int h,k; int t; k=GetKey(get_name); t=h=Hash(k); while(1) { /*if(ht[h].conflict_time==0&&ht[h].key!=k) { printf("表中未找到无此人！\n"); break; } else if(ht[h].key==k) { printf("已找到%s，表内存储位置：%d\n",get_name,h); break; } else p++; h=n[p]; }*/ if(ht[h].name==NULL) { printf("表中未找到无此人！\n"); break; } else if(strcmp(ht[h].name,get_name)==0) { printf("已找到%s，表内存储位置：%d，查找次数:%d\n",get_name,h,s_time); break; } else { p++; h=(t+n[p])%hashlen; s_time++; } } } int main() { // printf("请输入建表所需的三十个人名！\n"); NodeList L; HashTable ht; InitialHashTable(ht); char get_name[20]={0}; int rand_n[50]; CreatConfilctArray(rand_n); FILE* fp; fp=fopen("name.txt","r"); for(i=0;i<30;i++) { GetName(L,i,fp); } fclose(fp); CreatHashTable(ht,L,rand_n); printf("\n"); printf("--------------哈希表建表完成-------------"); printf("\n"); while(1) { get_name[20]={0}; printf("请输入要查找的人名(输入“***”表示结束程序):"); scanf("%s",get_name); printf("关键字：%d ",GetKey(get_name)); if(strcmp(get_name,"***")==0) break; SearchHashTable(ht,rand_n,get_name); } return 0; } 四、调试分析 1. 哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录； 2. 除留余数法对于p的选择很重要，经过分析后的选择是p为小于等于m的最大素数，最终选择了61； 3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。 五、用户手册 1. 本程序的运行环境为Windows操作系统，执行文件为hashtable.exe； 2. 本程序的输入的名字存储在name.txt文件中； 3. 程序进入后已经完成哈希表的构建并进行展示，用户只需进行相应的查找； 六、测试数据 1. 挑选表中已有的十个姓名进行测试 （xiaoli,zhuangshuangshuang,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wangkun） 与上方的哈希表进行对比完全匹配。 2. 选择5个没有在表中的名字进行查表操作： （lovetianqi,tianjiejie,jiwang,beijing,heheda） 一: 需求分析 (2) 三: 详细设计（含代码分析） (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五，总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (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; 附件4： 北京理工大学珠海学院 课程设计任务书 2010 ～2011学年第二学期 学生姓名：专业班级： 指导教师：工作部门： 一、课程设计题目 哈希表应用 二、课程设计内容（含技术指标） 【问题描述】 利用哈希表进行存储。 【任务要求】 任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。 设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。 设计目的：实现哈希表的综合操作 简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。 显示元素：显示已经创建的哈希表。 查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。 退出系统：退出程序。 【测试数据】 自行设定，注意边界等特殊情况。 三、进度安排 1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。 2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。 3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。 4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。 5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。 四、基本要求 1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。 从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 课程负责人签名： 年月日 实验报告 姓名：学号： 1．实验题目 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 2．需求分析 本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 输出形式：地址，关键字，收索长度，H（key），拼音 3.概要设计 typedef struct NAME typedef struct hterm void InitNameList() void CreateHashList() void FindList() void Display() int main() 4．详细设计 #include #define HASH_LEN 50 #define M 47 #define NAME_NO 8 typedef struct NAME { char *py; //名字的拼音 int k; //拼音所对应的整数}NAME; NAME NameList[HASH_LEN]; typedef struct hterm //哈希表{ char *py; //名字的拼音 int k; //拼音所对应的整数int si; //查找长度 }HASH; HASH HashList[HASH_LEN]; void InitNameList() { NameList[0].py="houxinming"; NameList[1].py="abc"; NameList[2].py="defdgf"; NameList[3].py="zhangrji"; NameList[4].py="jiaxin"; NameList[5].py="xiaokai"; NameList[6].py="liupeng"; NameList[7].py="shenyonghai"; 哈希表实现电话号码查询系统 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用 C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ①读取原电话本存储的电话信息。 ②读取系统随机新建电话本存储的电话信息。 2)查找信息 ①根据电话号码查询用户信息。 ②根据姓名查询用户信息。 3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。 3)数据文件“out.txt”存放未查找到的电话信息。 4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存 到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。 3)根据姓名查找时显示给定姓名用户的记录。 4)根据电话号码查找时显示给定电话号码的用户记录。 5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。三概要设计 1、子函数功能 int Collision_Random(int key,int i) //伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address) //以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str) //再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address) //以电话号码为关键字建立哈希表 void Outfile(string name,int key) //在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中void Outhash(int key) //输出哈希表中的记录 void Rafile() //随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n) //建立哈希表 int Search_by_name(string name) //根据姓名查找哈希表中的记录 int Search_by_phone(string phone) //根据电话号码查找哈希表中的记录 数据结构与算法-基础算法篇-哈希算法 1. 哈希算法 如何防止数据库中的用户信息被脱库？ 你会如何存储用户密码这么重要的数据吗？仅仅 MD5 加密一下存储就够了吗？ 在实际开发中，我们应该如何用哈希算法解决问题？ 1. 什么是哈希算法？ 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法？ 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈 希值。 2. 哈希算法的常见应用有哪些？ 7个常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1. 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2. 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 3. 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 4. 散列函数 1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？ 福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++; printf("\nsum====================%d",sum); return sum; } （2）建立哈希表 1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值 }Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{ int i,q; i=c/2+1; while(i 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本（2) 指导教师王昆仑、李贯虹 2010 年5 月 课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一， 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和 数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题，培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）如何定义一个包括电话号码、用户名、地址的节点。 （2）如何以电话号码和用户名为关键字建立哈希表。 （3）用什么方法解决冲突。 （4）如何查找并显示给定电话号码的记录。 （5）如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知，本设计要求分别以电话号码和用户名为关键字建立哈希表，z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题，从而建立一比较合理 的哈希表。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使 用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 根据问题分析，我们可以定义有3个域的节点，这三个域分别为电话号码char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构：散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系，并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想，是以所需存储的结点中的关键词作为自变量，通过某种确定的函 数H（称作散列函数或者哈希函数）进行计算，把求出的函数值作为该结点的存储地址，并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法（简称散列法）通过在结点的存储地址和关键字之间建立某种确定的函数 关系H，使得每个结点（或关键字）都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时，可以很方便地根据待查关键字K计算出对应的“映像”H(K)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。 数据结构实验报告四——哈希表查找名字(字符串） 实验题目:哈希表查找名字（字符串) 实验目标: 输入一组名字(至少50个）,将其保存并利用哈希表查找。输出哈希查找冲突次数,哈希表负载因子、查找命中率。 数据结构： 哈希表与数组（二维）。二维数组用于静态顺序存储名字(字符串),哈希表采用开放定址法,用于存储名字(字符串)对应得关键字并实现对名字（字符串)得查找。 需要得操作有: １、关键字求取(主函数中两次出现，未单独编为函数） 关键字key=abｓ(字符串首位AＳＣII码值-第二位ASCIＩ码值＋第([]+1)位ASCＩI码值-最后一位ASCII码值－倒数第二位ASCII码值)*字符串长度（abｓ为求整数绝对值得函数)。 ２、处理关键字得哈希函数(Hash) 利用平方取中法求关键值key在哈希表中得位置。公式ａdd=(key＊key）%1０00/LENGTH（a ｄd为key在哈希表中得地址)。 int Hａsｈ（ｉｎｔkey) { ?rｅturn((key*key)/1０００%LENＧＴH); } 3、处理哈希表中冲突得函数(Coｌlｉｓiｏn) 利用线性探测再散列处理冲突,利用全局变量counｔ统计冲突次数。 ｉnt Collｉsioｎ（inｔkｅy,int Haｓhtaｂle［］) { ｉｎtｉ; for(i=1;i<=ＬENGTH;ｉ++） { ??iｆ（Ｈashtabｌe[(Hａsｈ（kｅy)+ｉ)％LEＮGＴＨ]==-1） ?returｎ(（Hａsｈ(keｙ）＋i)％LENＧTＨ); ??count+＋; } } 4、哈希表初始化（InitＨaｓh) ｖoid InitHash(int Hａshtaｂlｅ[]) { ｉｎｔi; for(i=0;ｉ＜ＬＥNGTH；i++) ??Hashtable[i]=-1; } 5、向哈希表中插入关键字(InsｅrｔＨaｓh) void InｓertＨash(int kｅy,int Hａshｔablｅ［]) { ｉｎt add; 一、问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 二、基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 三、概要设计 1.构造结构体：typedef struct{}； 2.姓名表的初始化：void InitNameTable()； 3.建立哈希表：void CreateHashTable()； 4.显示姓名表：void DisplayNameTable()； 5.姓名查找：void FindName()； 6.主函数：void main() ； 四、详细设计 1.姓名表的初始化 void InitNameTable() { NameTable[0].py="louyuhong"; NameTable[1].py="shenyinghong"; NameTable[2].py="wangqi"; NameTable[3].py="zhuxiaotong"; NameTable[4].py="zhataotao"; NameTable[5].py="chenbinjie"; NameTable[6].py="chenchaoqun"; NameTable[7].py="chencheng"; NameTable[8].py="chenjie"; NameTable[9].py="chenweida"; NameTable[10].py="shanjianfeng"; NameTable[11].py="fangyixin"; NameTable[12].py="houfeng"; NameTable[13].py="hujiaming"; NameTable[14].py="huangjiaju"; NameTable[15].py="huanqingsong"; NameTable[16].py="jianghe"; NameTable[17].py="jinleicheng"; NameTable[18].py="libiao"; NameTable[19].py="liqi"; NameTable[20].py="lirenhua"; NameTable[21].py="liukai"; NameTable[22].py="louhanglin"; NameTable[23].py="luchaoming"; NameTable[24].py="luqiuwei"; NameTable[25].py="panhaijian"; NameTable[26].py="shuxiang"; NameTable[27].py="suxiaolei"; NameTable[28].py="sunyubo"; NameTable[29].py="wangwei"; for (i=0;i /* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.doczj.com/doc/95951906.html, */ #include 计算与数据结构篇 - 哈希算法 (Hash) 计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 构成哈希算法的条件： 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同； 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小； 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。 哈希算法的应用(上篇) 安全加密 说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。 除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。 前面我讲到的哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。 不过，即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1-2^128。 如果我们拿到一个 MD5 哈希值，希望通过毫无规律的穷举的方法，找到跟这个 MD5 值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资-源下，哈希算法还是被很难破解的。 对于加密知识点的补充，md5这个算法固然安全可靠，但网络上也有针对MD5中出现的彩虹表，最常见的思路是在密码后面添加一组盐码(salt), 比如可以使用md5(1234567.'2019@STARK-%$#-idje-789'),2019@STARK-%$#-idje-789 作为盐码起到了一定的保护和安全的作用。 唯一标识(uuid) 我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。 福建工程学院课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; 录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct //哈希表 { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameT able() 操作结果：初始化姓名表。 CreateHashT able() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashT able() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 云南大学数学与统计学实验教学中心实验报告 课程名称： 数据结构与算法学期： 2011-2012学年第二学期 成绩： 指导教师：xxx学生姓名：xxx学生学号：xxxxx 实验名称：哈希表及其查找实验要求：必做实验学时：4（+2）学时 实验编号：4（及5）实验日期：第6-8周完成日期：2012.5.10 学院：数学与统计学院专业：信息与计算科学年级：2010级 一、实验目的 通过实验掌握散列存储的基本概念，进行哈希问题的处理，同时附带进行字符串的处理的练习。 二、实验内容 为某单位的人名（n=30人）设计一个哈希表，使得平均查找长度<2，要求完成相应的哈希建表和查表。。 三、实验环境 Windows XP 程序设计语言C 四、实验过程 1．实验要求： 1、设人名长度<10个字符，用二维字符数组存储哈希表：char hash[ ][10]; 2、要求哈希函数用除留余数法，并用人名的10个字符代码和作为分子； 用（补偿性）线性探测再散列处理冲突。 3、依题意有：平均查找长度=（1+1/(1-α)）/2< 2，∴取α=0.6， 由此哈希表长m=n/α=30/0.6=50; 所以有char hashlist [ 50][10]； 令：除留余数法中的P取47； （补偿性）线性探测再散列的地址：j=(j+Q)% m中的Q取17。 4、对程序结构的要求： ①要求为哈希建表和哈希查表分别编写和设计相应的函数： createhash( ... ... ); hashsearch(... ...)； ②再设计一个哈希函数表的输出函数printhash( )，对构造的哈希表进行输出，注 意输出格式要在屏幕好看，先输出序号（1~30），再输出该序号 的人名或null，每行输出10项，共输出5行。 ③还应有一个初始化char hashlist [ 50][10]的函数Inithashlist( )， 初始时将50个人名全赋值为null. 5、在主函数中： 调用Inithashlist( )初始化哈希表； 课程设计(论文)任务书 软件学院学院软件工程专业班 一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表 二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止 三、课程设计(论文) 地点: 软件测试中心（北区测试二室） 四、课程设计(论文)内容要求： 1．本课程设计的目的 ⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题； ⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求： ⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求 ⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订； ⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等； ⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分； ⑷回答问题：20分； ⑸论文撰写：30分。 哈希表查找不成功怎么计算？ 解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！ 例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？ 地址：0 1 2 3 4 5 6 7 8 9 10 11 12 数据： 39 1228154244 625－－ 36－ 38 成功次数： 1 3 1 2 2 1 191 1 不成功次数：98 7 65 4 3 2 1 1 2 110 查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54 说明： 第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。至少要查询多少次才能确认没有这个值。 （1）查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失 败。 （2）查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失 败。 （3）查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失 败。 （4）查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失 败。 （5）查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失 败。 （6）查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失 败。 （7）查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失败。 （8）查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。 （9）查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。 （10）查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。 （11）查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。 （12）查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失败。 （13）查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候，才能确认查询失败。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans： (1).首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长度为 L = 7/0.7 = 10；因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。 H(Key) = (keyx3) MOD 7, 例如key=7时， H(7) = (7x3）%7 = 21%7=0，其他关键字同理。哈希表的设计与实现 课程设计报告
哈希表应用
哈希表实验报告完整版
哈希表实现电话号码查询系统
哈 希 常 见 算 法 及 原 理
数据结构课程设计--哈希表实验报告
哈希表的设计与实现-数据结构与算法课程设计报告
哈希表实验报告
数据结构哈希表设计
哈希表查询设计及实现
哈 希 常 见 算 法 及 原 理
数据结构课程设计--哈希表实验报告
哈希表设计-大大数据结构课程设计
数据结构实验四哈希表及其查找
数据结构课设-通讯录系统的设计与实现——哈希表
哈希表查找成功和不成功的算法
相关主题
文本预览