实验七 哈希表查找设计

实验七哈希表查找设计

实验目的：掌握哈希表查找的基本方法和过程，包括建立哈希表、解决冲突和查找元素。实验要求：

[问题描述]

设数序为53，17，12，61，98，70，87，25，63，46，14，59，67，75，哈希表长M=18，哈希函数为：

H（K）=K MOD 17

建立对应的哈希表，采用采用开放地址法中的二次探测再散列解决冲突，并查找值为70的元素位置。

[基本要求]

采用开放地址法中的二次探测再散列解决冲突。

[测试数据]

数序53，17，12，61，98，70，87，25，63，46，14，59，67，75；哈希表长M=18；哈希函数为：H（K）=K MOD 17。

实验时数：2

实验类型：验证性

一: 需求分析 (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;

实验报告 姓名：学号： 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 #include #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";

数据结构课程设计哈希表设计问题

目录 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）哈希表的创建及初始化流程图

课程实验报告 课程名称：数据结构 实验项目名称：散列表 专业班级： 姓名：XXX 学号： 完成时间：2015 年06 月13 日

背景 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。 例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。 例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。 问题描述 我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了...）。通过书名，来查询它是否存在。 为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。 基本要求 （1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 （2）数据的输入输出格式： 输入分为两部分 第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存 在的图书记录。 第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查 询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。 测试数据 输入： 4 a ans and hellocpp

福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：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=0) return q; else i=c/2+1; } else{ q=(p-i*i)%HASHSIZE; c++;

/* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.wendangku.net/doc/e718201874.html, */ #include #include #include #include #include #define szNAME 80 #define HASH_ROOT 47 /*用于计算哈希地址的随机数*/ #define szHASH 50 /*哈希表总长度*/ #define POPULATION 30 /*学生总数*/ /*哈希表结构体*/ struct THash { int key; /*钥匙码*/ char name[10]; /*姓名*/ int depth; /*检索深度*/ }; /*根据钥匙码和哈希根计算哈希地址*/ int GetHashAddress(int key, int root) { return key % root; }/*end GetHashAddress*/ /*冲突地址计算，如果发现地址冲突，则用当前地址和钥匙码、哈希根重新生成一个新地址*/ int GetConflictAddress(int key, int address, int root) { int addr = address + key % 5 + 1; return addr % root; }/*end GetConflictAddress*/ /*根据字符串生成哈希钥匙码，这里的方法是将串内所有字符以数值形式求累加和*/ int CreateKey(char * name) { int key = 0; unsigned char * n = (unsigned char *)name; while(*n) key += *n++; return key; }/*end CreateKey*/ /*输入一个名字，并返回哈希钥匙码*/ int GetName(char * name) { scanf("%s", name); return CreateKey(name); }/*end CreateKey*/ /*根据学生人数、长度和哈希根构造哈希表*/ struct THash * CreateNames(int size, int root, int population) { int i =0, key = 0, addr = 0, depth = 0; char name[10]; struct THash * h = 0, *hash = 0; /*哈希根和长度不能太小*/ if(size < root || root < 2) return 0; /*根据哈希表长度构造一个空的哈希表*/ hash = (struct THash *)malloc(sizeof(struct THash) * size); /*将整个表清空*/ memset(hash, 0, sizeof(struct THash) * size); for(i = 0; i < population; i++) { /*首先产生一个随机的学生姓名，并根据姓名计算哈希钥匙码，再根据钥匙码计算地址*/ key = GetName(name); addr = GetHashAddress(key, root); h = hash + addr; if (h->depth == 0) { /*如果当前哈希地址没有被占用，则存入数据*/ h->key = key; strcpy(h->name , name); h->depth ++; continue; }/*end if*/ /*如果哈希地址已经被占用了，就是说有冲突，则寻找一个新地址，直到没有被占用*/ depth = 0; while(h->depth ) { addr = GetConflictAddress(key, addr, root); h = hash + addr; depth ++; }/*end while*/ /*按照新地址存放数据，同时记录检索深度*/ h->key = key; strcpy(h->name , name); h->depth = depth + 1; }/*next*/ return hash; }/*end CreateNames*/ /*在哈希表中以特定哈希根查找一个学生的记录*/ struct THash * Lookup(struct THash * hash, char * name, int root) { int key = 0, addr = 0; struct THash * h = 0; /*不接受空表和空名称*/ if(!name || !hash) return 0; key = CreateKey(name); addr = GetHashAddress(key, root); h = hash + addr; /*如果结果不正确表示按照冲突规则继续寻找*/ while(strcmp(h->name , name)) { addr = GetConflictAddress(key, addr, root); h = hash + addr; if(h->key == 0) return 0; }/*end while*/ return hash + addr; }/*end Lookup*/ /*根据一条哈希表记录打印该记录的学生信息*/ void Print(struct THash * record) { if (!record) { printf("【查无此人】\n"); return ; }/*end if*/ if(record->depth) printf("【钥匙码】%04d\t【姓名】%s\t【检索深度】%d\n", record->key, record->name, record->depth ); else printf("【空记录】\n"); /*end if*/ }/*end Print*/ /*打印学生花名册*/ void Display(struct THash * hash, int size) { struct THash * h = 0; if (!hash || size < 1) return ; printf("学生花名册：\n"); printf("--------------------\n"); for(h = hash; h < hash + size; h++) { printf("【地址】%d\t", h - hash); Print(h); }/*next*/ printf("--------------------\n"); }/*end Display*/ /*主函数，程序入口*/ int main(void) { /*哈希表变量声明*/ struct THash * hash = 0, * h = 0; int cmd = 0; /*命令*/ char name[10]; /*学生姓名*/ /*生成30个学生用的哈希表*/ hash =

数据结构实验报告四——哈希表查找名字(字符串） 实验题目:哈希表查找名字（字符串) 实验目标: 输入一组名字(至少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;

哈希表查找的设计 一．问题描述： 哈希表查找的设计：设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。二．需求分析： 程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户键入运算命令以实现对应的功能，包含数据的录入、查找、删除、显示等功能。 本程序旨在实现哈希函数的构造与处理存储冲突，因而指定哈希表存储的数据类型为简单的整型数字，在实用性上还有所欠缺。但根据用户需求的变化，可以对程序的基本数据类型进行改造，以实现更为丰富的功能，进而体现哈希表在查找数据时的优越性。 三．算法思想： 在设定哈希表的抽象数据类型时，要有查找数据元素的操作。另外，插入操作和删除操作也要用到查找数据元素操作，以查看该数据元素是否存在，因此可以设计查找元素操作包括插入和删除操作的查找。 因此，查找操作就有两种情况：一种情况是插入操作时寻找空闲单元的查找；另一种情况是在查找和删除操作时寻找该元素是否在哈希表中已存在的查找。插入操作时寻找空闲单元查找的特征是哈希表中不存在该对象，设计此时查找函数返回该空闲单元位置的“正”值；查找和删除操作时寻找该元素是否在哈希表中已存在的特征是哈希表中已存在该数据元素，设计此时查找函数返回该数据单元位置的“负”值。进而执行后续操作。 为了区分哈希表中每一个表元素的当前状态，为每一个表元素设置一个“标志”定为tag。tag=0表示该元素为空；tag=1表示该元素以存放有数据元素；tag=-1表示该元素中存放的数据元素已被删除。判断当tag为0或-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; 录入信息结构体的定义，包含姓名，学号，电话号码。 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：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include #include//time用到的头文件 #include//随机数用到的头文件 #include//toascii()用到的头文件 #include//查找姓名时比较用的头文件 #define HASH_LEN 50//哈希表的长度 #define P 47//小于哈希表长度的P #define NAME_LEN 30//姓名表的长度 typedef struct {//姓名表 char *py; //名字的拼音 int m; //拼音所对应的 }NAME; NAME NameTable[HASH_LEN]; //全局定义姓名表 typedef struct {//哈希表 char *py; //名字的拼音

一、问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过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

云南大学数学与统计学实验教学中心实验报告 课程名称： 数据结构与算法学期： 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( )初始化哈希表；

哈希表设计数据结构课程设计

实习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 #include//time用到的头文件 #include//随机数用到的头文件 #include//toascii()用到的头文件 #include//查找姓名时比较用的头文件#define HASH_LEN 50//哈希表的长度

课程实习报告 一、需求分析： 1.本程序来自于图书馆靠书名来检索想要查找的书问题。 2.本程序要求： （1）根据输入建立图书名称表，采用创建散列表实现。 （2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。 二、哈希表简介 结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。

* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。 * 综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”，作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子(load factor)不超过75%，查找效率最高。* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 程序设计流程 程序思想 (一)哈希函数unsigned int hash_BKDE(char *str)生成映射 地址，成为散列表的编号。 (二)哈希表HashTable::HashTable()通过数组储存元素 (三)插入函数void HashTable::insert(char*c)插入字符串， 先计算要插入字符串生成的映射地址，然后在相应的地址插入，如果没有空位查找空位插入。

《程序设计与算法分析》实验报告 一设计的目的与容 1.设计目的 通过本实验需要掌握构造哈希函数表，需要完成设计构造哈希表的完整算法，并求出平均查找长度。 2 实验容 使用哈希函数：H(K)=3*K MOD 11 并采用开放地址法解决冲突，试在0到10的散列地址空间对关键字序列( 22, 41, 53, 46, 30,13, 01,67)构造哈希函数表，并设计构造哈希表的完整算法，并求出平均查找长度。 二算法的基本思想 1.数据结构的设计 哈希函数H ( key ) =3* key mod 11，哈希表的地址空间为0 ～10，对关键字序列（22, 41, 53, 46, 30,13, 01,67）按线性探测再散列和二次探测再散列的方法分别构造哈希表。 （1 ）线性探测再散列： 3*22％11 = 0；3*41 ％11=2 ；3*53％11 = 5 ；3* 46%11=6；3*30%11=2发生冲突，下一个存储地址（2＋1 ）％11 ＝3 ； 3*13%11=6发生冲突，下一个存储地址（6＋1 ）％11 ＝7 ； 3*01%11=3发生冲突，下一个存储地址（3＋1 ）％11 ＝4 ； 3*67%11=3发生冲突，下一个存储地址是：（3 ＋1 ）％11 ＝4 发生冲突；下一个存储地址（4 + 1 ）%11=5发生冲突；下一个存储地址（5 + 1 ）%11=6发生冲突；下一个存储地址（6+ 1 ）%11=7发生冲突；下一个存储地址（7 +

1 ）%11=8未发生冲突。 2.算法的基本思想 开放地址法这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述： H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ，k ( k ≤ m – 1)) 其中：H ( key ) 为关键字key 的直接哈希地址，m 为哈希表的长度，di 为每次再探测时的地址增量。采用这种方法时，首先计算出元素的直接哈希地址H ( key ) ，如果该存储单元已被其他元素占用，则继续查看地址为H ( key ) + d 2 的存储单元，如此重复直至找到某个存储单元为空时，将关键字为key 的数据元素存放到该单元。增量d 可以有不同的取法，并根据其取法有不同的称呼： （1 ）d i ＝1 ，2 ，3 ，…… 线性探测再散列； （2 ）d i ＝1^2 ，－1^2 ，2^2 ，－2^2 ，k^2，-k^2…… 二次探测再散列； （3 ）d i ＝伪随机序列伪随机再散列； 三源程序代码及测试结果 1.源程序代码 #include #include #define M 11 #define N 8 struct hterm

合肥学院 计算机科学与技术系 课程设计报告 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)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。

HUNAN UNIVERSITY 课程实习报告 题目: 哈希表 学生姓名唐鹏 学生学号 2 专业班级物联2班 指导老师吴帆 完成日期2014年4月2日

一、需求分析: 1.本程序来自于图书馆靠书名来检索想要查找的书问题。 2.本程序要求: (1)根据输入建立图书名称表,采用创建散列表实现。 (2)建散列表后,如果想要查找的数据在散列表中输出yes否则输出no。 二、哈希表简介 结构中存在关键字与K相等的记录,则必定存储在f(K)的位置上。由此,不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function),按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。 * 综上所述,根据散列函数H(key)与处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”, 作为这条记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。这个现象也叫散列桶,在散列桶中,只能通过顺序的方式来查找,一般只需要查找三次就可以找到。科学家计算过,当负载因子(load factor)不超过75%,查找效率最高。 * 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率就是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。 程序设计流程 程序思想 (一)哈希函数unsigned int hash_BKDE(char *str)生成映射地址,成为散列表的编 号。 (二)哈希表HashTable::HashTable()通过数组储存元素 (三)插入函数void HashTable::insert(char*c)插入字符串,先计算要插入字符串生 成的映射地址,然后在相应的地址插入,如果没有空位查找空位插入。(四)查找函数bool HashTable::find(char*c)进行查找,先计算要生成字符串的地 址,再到散列表中进行查找比较。 (五)主函数main() 1)输入:输入散列表内容与要查找的数据个数与数据