解决哈希冲突
解决哈希冲突
一、需求分析
1、本程序由用户输入运行命令和数据，运行结果显示在其后。
2、程序执行的命令包括：
1）输入相关信息，构造一个指针型向量；2）输入数据，保存在哈希表中；3）输出用链地址法解决哈希冲突的结果。
2、测试数据
输入：T N M（T 表示hash表空间，N表示Hash函数的模，输入的数据个数）8 6 5
输入的数据：7，13，10，16，22
二、概要设计
#include
using namespace std;
struct Chain
{
int m;
Chain *next;
};
int T,M,N;
int key(int m,int n)
{
return m%n;
}
void create(Chain ChainHash[],int T,int M,int N)
{
Chain *p;
p=new Chain;
cout<<"输入数据：\n";
for(int i=0;i { Chain *q=new Chain;q->next=NULL; cin>>q->m; if(ChainHash[key(q->m,N)].next!=NULL) { p=&ChainHash[key(q->m,N)]; while(p->next!=NULL){p=p->next;} p->next=q; } else{ChainHash[key(q->m,N)].next=q;} } } void out_put(Chain a) { Chain *p=a.next; if(p==NULL) {cout<<"^"< else { while(p!=NULL) { cout<<"->"< p=p->next; } cout< } } void output(Chain a[],int T) { for(int i=0;i { cout< out_put(a[i]); } } void main() { int T=0,M=0,N=0;Chain ChainHash[30]; cout<<"输入Hash表空间:T=";cin>>T; cout<<"输入Hash函数的模:N=";cin>>N; cout<<"输入的数据个数M=";cin>>M; for(int i=0;i { ChainHash[i].next=NULL; } create(ChainHash,T,M,N); output(ChainHash,T); cout<<"ASL＝（1*2+2*2＋3）/M="<<(1*2+2*2+3)/M< } 四、调试分析 在编写时程序时，没有认真考虑链表的连接问题，总是出现链表连不上的情况。经过调试分析后，我终于找到了问题的所在。不但解决了问题，同时还加深了我对链表存储结构的理解。还有，在编写的时候，对于用链地址法解决哈希冲突是第一次，所以刚开始不知该如何下手。之后，经过查资料和认真分析，终于找到了方法。 五、运行结果 六、实验环境 （1）Windows 7系统下 （2）编程环境：VC6.0++ ，TC2.0 附件4： 北京理工大学珠海学院 课程设计任务书 2010 ～2011学年第二学期 学生姓名：专业班级： 指导教师：工作部门： 一、课程设计题目 哈希表应用 二、课程设计内容（含技术指标） 【问题描述】 利用哈希表进行存储。 【任务要求】 任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。 设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。 设计目的：实现哈希表的综合操作 简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。 显示元素：显示已经创建的哈希表。 查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。 退出系统：退出程序。 【测试数据】 自行设定，注意边界等特殊情况。 三、进度安排 1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。 2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。 3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。 4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。 5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。 四、基本要求 1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。 从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 课程负责人签名： 年月日 哈希表概念及构建方法 一、哈希表的概念及作用 一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。 哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条... 如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？ a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 1 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 2 1 2 2 2 3 24 25 26 刘丽刘宏英吴军吴小艳李秋梅陈伟... 姓名中各字拼音首字母ll lhy wj wxy lqm cw ... 用所有首字母编号值相加求 和 24 46 33 72 42 26 ... 最小值可能为3 最大值可能为78 可放75个学生 用上述得到的数值作为对应记录在表中的位置，得到下表： 成绩一成绩二... 3 ... ...... 24 刘丽82 95 25 ... 26 陈伟 ... ... 33 吴军 ... ... 42 李秋梅 ... ... 46 刘宏英 ... ... 72 吴小艳 ... ... 78 ... 上面这张表即哈希表。 如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置： 李秋梅:lqm 12+17+13=42 取表中第42条记录即可。 问题：如果两个同学分别叫刘丽刘兰该如何处理这两条记录？ 这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。 二、哈希表的构造方法 １、直接定址法 一: 需求分析 (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; 一、该程序实现的哈希表：构造哈希函数的方法为除留余数法(函数modhash)，处理哈希冲突的方法为链地址法。 二、对哈希表的操作：插入（函数hash_table_insert）、移除（函数hash_table_remove）、 查找（函数hash_table_lookup）、整个哈希表的释放（函数hash_table_delete）、 整个哈希表的输出（函数hash_table_print）。 三、哈希表的最大长度可以由HASHMAXLEN设置（我设为1000）。 四、输入哈希表的名称拼音字符是长度为10—20（长度可由STR_MAX_LEN和STR_MIN_LEN）的小写字母组成。这些名字字符串是我用函数rand_str随机产生的。 五、名称拼音字符（关键字）到关键字值的转换方法：先把名称的拼音字符转换对应的ASCII，累加后作为关键字值。我是用函数str_to_key实现的。 六、异常情况包括： 1、在对哈希表进行插入操作时，若哈希表的实际长度超过了哈希表的最大长度，我就输出“out of hash table memory!”，然后直接跳出插入子函数，不进行插入操作。 2、在对哈希表进行插入操作时，若插入的元素在哈希表中已经存在，我就输出“******already exists !”，然后直接跳出插入子函数，不进行插入操作。 3、在对哈希表进行查找操作时，若查到则返回其地址，若没查到则返回空地址。 4、在对哈希表进行移除操作时，对同义词元素的删除，分为表头和表中两种情况处理。 七、开发平台：DEV-C++，用c语言实现。 在哈希表程序中我比较注重整个代码风格，希望能形成很好的代码风格！如果有什么可以改进的，希望老师能跟我说说！ 龙源期刊网 https://www.wendangku.net/doc/7613883121.html, 哈希表冲突处理方法浅析 作者：叶军伟 来源：《科技视界》2014年第06期 【摘要】哈希表的理想情况是无需比较一次存取便能找到所查的记录，但是在实际应用中，哈希表通常存在冲突的情况，这就需要反复查找处理冲突。各种处理冲突的方法都有其适用范围及优缺点，需要根据实际情况灵活的选择适当的冲突处理方法。 【关键词】哈希表；冲突；处理方法 0 引言 在哈希表中，哈希函数的设置是非常灵活的，只要能使任一关键字由此所得的哈希地址都分布在哈希表允许的范围内就可以了。因此常常会出现不同的关键字值对应到同一个存储地址的现象，这就叫冲突。即关键字key1≠key2，但H（key1）= H（key2）。 适当的选择分布均匀的哈希函数能有效地减少冲突的发生，但是不能不免冲突。发生冲突后，必须解决，也即必须寻找下一个可用的地址。因此哈希表的建立通常为如下步骤：第一步，取出一个数据元素的关键字key，根据哈希函数计算其在哈希表中的存储地址D，若地址为D的存储空间还没有被占用，则将该数据元素存入，否则发生冲突，执行下一步；第二 步，根据规定的冲突处理方法，计算关键字为key的数据元素的下一个存储地址，若该地址的存储空间没有被占用，则存入，否则继续执行第二步，直到找出一个空闲的存储空间为止。由此可见，如何处理冲突是哈希表不可缺少的部分。 1 开放定址法 这是应用最为广泛的一种冲突处理方法。其公式描述为：Hi=（H（key）+di） MOD L i=1，2，…，k（k 其中：H（key）为哈希函数，L为哈希表的表长，di为增量序列。 根据增量序列取值方法的有三种：（1）线性探测再散列di=1，2，3，…，m-1；（2）二次探测再散列di=12，-12，22，-22，32，...，k2，（k 用线性探测再散列处理冲突可以保证做到，只要哈希表未满，总能找到不发生冲突的地址，但是容易发生二次聚集的情况，即在处理同义词的冲突过程中又添加了非同义词的冲突，效率不高。比如当哈希表中k，k+1，k+2位置上已存放有数据时，下一个哈希地址为k， k+1，k+2和k+3的数据都将填入k+3的位置，这样原本不冲突的哈希地址在经过冲突处理后，反而发生冲突，这种现象对查找不利。 哈希表实现电话号码查询系统 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用 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 前言 (1) 2 需求分析 (1) 2.1 任务和要求 (1) 2.2 运行环境 (1) 2.3 开发工具 (1) 3 分析和设计 (2) 3.1 系统分析及设计思路 (2) 3.2 主要数据结构及算法 (2) 3.3 函数流程图 (2) （1）哈希表的创建及初始化流程图 (2) 5 课程设计总结 (13) 5.1 程序运行结果或预期运行结果 (13) 说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。 (14) 5.2 设计结论 (15) 参考文献 (15) 致谢 (15) 1 前言 从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2 需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或TC编译环境 2.3 开发工具 C语言 3 分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1）用除留余数法构建哈希函数 （2）用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体typedef struct hashtable创建哈希表 定义函数Hash_Init(HashTable ht)来对哈希表初始化 定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址 定义函数Hash_Init(ht)输入30个名字 定义函数Hash_Create(HashTable ht)来求哈希表长度 定义函数hash_output(HashTable h)来输出哈希表 定义函数Hash_Link()构造链表函数 定义函数int hash_search(int h[],int key)查找输入的名字 3.3 函数流程图 （1）哈希表的创建及初始化流程图 /* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.wendangku.net/doc/7613883121.html, */ #include 一,哈希表(Hashtable)简述 在.NET Framework中，Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似key/value的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于key的值。Hashtable中key/value键值对均为object 类型，所以Hashtable可以支持任何类型的key/value键值对. 二,哈希表的简单操作 在哈希表中添加一个key/value键值对：HashtableObject.Add(key,value); 在哈希表中去除某个key/value键值对：HashtableObject.Remove(key); 从哈希表中移除所有元素：HashtableObject.Clear(); 判断哈希表是否包含特定键key：HashtableObject.Contains(key); 下面控制台程序将包含以上所有操作： using System; using System.Collections; //使用Hashtable时，必须引入这个命名空间 class hashtable { public static void Main() { Hashtable ht=new Hashtable(); //创建一个Hashtable实例 ht.Add("E","e");//添加key/value键值对 ht.Add("A","a"); ht.Add("C","c"); ht.Add("B","b"); string s=(string)ht["A"]; if(ht.Contains("E")) //判断哈希表是否包含特定键,其返回值为true或false Console.WriteLine("the E key:exist"); ht.Remove("C");//移除一个key/value键值对 Console.WriteLine(ht["A"]);//此处输出a ht.Clear();//移除所有元素 Console.WriteLine(ht["A"]); //此处将不会有任何输出 } } 三,遍历哈希表 遍历哈希表需要用到DictionaryEntry Object，代码如下： for(DictionaryEntry de in ht) //ht为一个Hashtable实例 { Console.WriteLine(de.Key);//de.Key对应于key/value键值对key Console.WriteLine(de.Value);//de.Key对应于key/value键值对value 1. 引言 哈希表（Hash Table）的应用近两年才在NOI（全国青少年信息学奥林匹克竞赛）中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 哈希表又叫做散列表，分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。 2. 基础操作 2.1 基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 2.2 函数构造 构造函数的常用方法（下面为了叙述简洁，设h(k) 表示关键字为k 的元素所对应的函数值）： a) 除余法： 选择一个适当的正整数p ，令h(k ) = k mod p ，这里，p 如果选取的是比较大 的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。 b) 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S ，则当h(k)已经存储了元素的时候，依次探查(h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 2.4 支持运算 哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(i nsert)、查找元素(member)。设插入的元素的关键字为x ，A 为存储的数组。初始化比较容易，例如： const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： 课程设计(论文)任务书 软件学院学院软件工程专业班 一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表 二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止 三、课程设计(论文) 地点: 软件测试中心（北区测试二室） 四、课程设计(论文)内容要求： 1．本课程设计的目的 ⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题； ⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求： ⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求 ⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订； ⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等； ⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分； ⑷回答问题：20分； ⑸论文撰写：30分。 Delphi 使用哈希表(键值对key) 以往在软件开发中经常需要用哈希表保存一些数据结构，C#下的哈希表可以快速检索数据，其实Delphi也提供了对哈希表的支持，下面我就将我在用Delphi开发中使用Hash表的方法写出来，希望对大家有一定的帮助! 在Borland Delphi中有一个THashedStringlist类，使用这个类可以实现Hash表的操作.使用这个类需要引用IniFiles单元. 例如：我们定义的数据结构是： 以下是引用片段： MyHashTest = record Key:Integer; Name:String[20]; Sex:Boolean; Age:Integer; end; PTest = ^MyHashTest ; 1：创建Hash表. ScHash:=THashedStringlist.Create; 2：将数据结构加入Hash表中. var Index:Integer; p_Test:PTest; Index:=ScHash.IndexOf(IntToStr(p_Test.Key)); if Index=-1 then begin ScHash.AddObject(IntToStr(p_Test.Key),TObject(Integer( p_Test))); end; 在加入Hash表的时候，首先我们检查看这个Key是否在Hash表中，如果Index=-1则说明此Key不在Hash表中，则我们将这个结构指针加入到Hash表中. 3：将数据结构从Hash表中删除. 以下是引用片段： var Index:Integer; t_Object: TObject; Index:=ScHash.IndexOf(IntToStr(p_Test.Key)); if Index -1 then begin t_Object:=ScHash.Objects[Index]; ScHash.Delete(Index); 一．问题描述 1问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2.基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。 二. 需求分析 （1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。 （2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双zhuangshuangshuang)。 （3）假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。 （4）在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。 （5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度 三．程序设计 1 .存储结构设计 typedef struct { char *py; //名字的拼音 int k; //拼音所对应的整数 }NAME; typedef struct //哈希表 { char *py; //名字的拼音 int k; //拼音所对应的整数 int si; //查找长度 }HASH; 2 .主要算法设计 （1）姓名（结构体数组）初始化 名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。 void InitNameList() { char *f; int r,s0,i; NameList[0].py="chenliang";//陈亮 NameList[1].py="chenyuanhao";//陈元浩 NameList[2].py="chengwenliang";//程文亮 NameList[3].py="dinglei";//丁磊 NameList[4].py="fenghanzao";//冯汉枣 NameList[5].py="fuzongkai";//付宗楷 NameList[6].py="hujingbin";//胡劲斌 NameList[7].py="huangjianwu";//黄建武 NameList[8].py="lailaifa";//赖来发 NameList[9].py="lijiahao";//李嘉豪 NameList[10].py="liangxiaocong";//梁晓聪 NameList[11].py="linchunhua";//林春华 NameList[12].py="liujianhui";//刘建辉 NameList[13].py="luzhijian";//卢志健 NameList[14].py="luonan";//罗楠 NameList[15].py="quegaoxiang";//阙高翔 NameList[16].py="sugan";//苏淦 NameList[17].py="suzhiqiang";//苏志强 NameList[18].py="taojiayang";//陶嘉阳 NameList[19].py="wujiawen";//吴嘉文 NameList[20].py="xiaozhuoming";//肖卓明 NameList[21].py="xujinfeng"; //许金峰 NameList[22].py="yanghaichun";//杨海春 NameList[23].py="yeweixiong";//叶维雄 NameList[24].py="zengwei";//曾玮 NameList[25].py="zhengyongbin";//郑雍斌 NameList[26].py="zhongminghua";//钟明华 NameList[27].py="chenliyan";//陈利燕 NameList[28].py="liuxiaohui";//刘晓慧 NameList[29].py="panjinmei";//潘金梅 for(i=0;i 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 一、问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过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哈希表应用
Hash表的构建和冲突解决
哈希表的设计与实现 课程设计报告
该程序实现的哈希表构造哈希函数的方法为除留余数法(
哈希表冲突处理方法浅析
哈希表实现电话号码查询系统
数据结构课程设计哈希表设计问题复习过程
哈希表查询设计及实现
哈希表基本操作
散列表(哈希表)
数据结构课设-通讯录系统的设计与实现——哈希表
Delphi 使用哈希表 (键值对 key)
哈希表
哈希表设计-数据结构课程设计
数据结构哈希表设计