数据结构与算法-散列表查找操作实验

题目：顺序表的实现一、实验题目顺序表的实现二、实验目的⑴掌握线性表的顺序存储结构；⑵验证顺序表及其基本操作的实现；⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。

三、实验内容与实现⑴建立含有若干个元素的顺序表；⑵对已建立的顺序表实现插入、删除、查找等基本操作。

实验实现#include<stdio.h>#include<memory.h>int a[10000];int arrlong(){int j;for(j=0;j<12;j++)if(a[j]==0)break;return j;}int Insect(int n,int s) ////插入{int j;for(j=0;j<10000;j++)if(a[j]==0)break;printf("要操作的元素\n");for(int i=0;i<j;i++)printf("%d ",a[i]);printf("\n");for(int i=j;i>n-1;i--)a[i+1]=a[i];a[n]=s;for(int k=0;k<j+1;k++)printf("%d ",a[k]);printf("\n");}int Search(int p) //查找{int j,h;for(j=0;j<12;j++){if(a[j]==0)break;}for(h=0;h<j;h++){if(a[h]==p){printf("查找到的数在第%d位\n",h+1);break;}}if(h==j)printf("查无此数\n");}int Delate(int g,int q) //删除{int j;g=g-1;for(int j=g;j<12;j++)a[j]=a[j+1];for(q =0;q<12;q++){if(a[q]==0)break;}for(int i=0;i<q;i++)printf("%d ",a[i]);printf("\n");}int main(){int y,c;printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");while(scanf("%d",&y)!=EOF){int n,x,s;if(y==0){memset(a,0,sizeof(a));printf("请输入元素的个数:\n");scanf("%d",&c);printf("请输入数据:\n");for(int i = 0;i < c;i++)scanf("%d",&a[i]);}else if(y==1){int L;printf("请输入插入的第几位\n");scanf("%d",&n);//输入L=arrlong();if(n<=L){printf("请输入插入的数字\n");scanf("%d",&s);Insect(n,s);}else{printf("输入有误\n");continue;}}else if(y==2){int p;printf("请输入要查找的数字\n");scanf("%d",&p);Search(p);}else if(y==3){int g,q,L;printf("请输入要删除数的位置\n");scanf("%d",&g);L=arrlong();if(L>=g){Delate(g,q);}else{printf("输入有误\n");printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");continue;}}else if(y==4)break;else{printf("输入有误\n");printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");continue;}printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");}}建立顺序表：插入操作：查找操作：删除操作：插入数据超出顺序表范围：查找不到输入数据：删除数据超出顺序表范围：四、实验心得1.掌握了为数组赋值的方法，深刻理解了数组的含义2.掌握了为数组排序的方法。

散列表实验报告(不同装载因子下链表法和放寻址法对比)TOC \o “1-4“ \h \z \u 1 概述22 原理介绍22.1 散列表介绍22.2 直接寻址表32.3 散列函数32.3.1 除法散列42.3.2 乘法散列42.3.3 全域散列42.4 解决碰撞问题52.4.1 链接法52.4.2 开放寻址法52.4.2.1 线性探查62.4.2.2 二次探查62.4.2.3 双重散列73 算法说明73.1 概述73.2 使用链接法解决碰撞问题83.2.1 算法思想83.2.2 伪代码描述93.2.3 算法分析与证明103.3 使用开放寻址法的双重散列解决碰撞问题123.3.1 算法思想123.3.2 伪代码描述123.3.3 算法分析与证明143.4 两个算法的比较144 实验设计与分析165 C++实现与结果分析185.1 C++实现与结果185.2 结果分析266 实验总结和感想27概述该实验报告主要是通过介绍散列表的各种技术，包括散列函数、解决碰撞的机制等技术，并对两种解决碰撞的机制：链接法和开放寻址法进行分析和证明，并通过实验分析两者在不同的规模下的运行时间和空间占用的对比，来证明在“算法说明”一章中的理论分析。

原理介绍散列表介绍散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做散列函数，存放记录的数组叫做散列表。

它实际上是是普通数组概念的推广，因为可以对数组进行直接寻址，故可以而在O(1)时间内访问数组的任意元素。

如果存储空间允许，我们可以提供一个数组，为每个可能的关键字保留一个位置，就可以应用直接寻址技术。

基本概念若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。

由此，不需比较便可直接取得所查记录。

称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

北京物资学院信息学院实验报告
课程名_数据结构与算法
实验名称查找与排序
实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ ________ 学号___
一、实验目的
1.掌握线性表查找的方法；
2.了解树表查找思想；
3.掌握散列表查找的方法.
4.掌握插入排序、交换排序和选择排序的思想和方法；
二、实验内容
查找部分
1.实现顺序查找的两个算法（P307）, 可以完成对顺序表的查找操作, 并根据查到和未查到两种情况输出结果；
2.实现对有序表的二分查找；
3.实现散列查找算法(链接法)，应能够解决冲突；
排序部分
4.分别实现直接插入排序、直接选择排序、冒泡排序和快速排序算法
三、实验地点与环境
3.1 实验地点
3.2实验环境
(操作系统、C语言环境)
四、实验步骤
（描述实验步骤及中间的结果或现象。

在实验中做了什么事情, 怎么做的, 发生的现象和中间结果, 给出关键函数和主函数中的关键段落）
五、实验结果
六、总结
（说明实验过程中遇到的问题及解决办法；个人的收获；未解决的问题等）。

《数据结构》实验报告题目: 散列查找一、实验题目散列查找二、实验目的⑴掌握散列查找的基本思想；⑵掌握闭散列表的构造方法；⑶掌握线性探测处理冲突的方法；⑷验证散列技术的查找性能。

三、实验内容与实现⑴对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表；⑵设计查找算法，验证查找性能。

实验实现：#include <stdio.h>#include <stdlib.h>#define HASHSIZE 10 // 长度#define NULLKEY -32768typedef struct{int *elem; // 数据元素存储地址，动态分配数组int count; // 当前数据元素个数}HashTable;int m = 0;int Init(HashTable *H){int i;m = HASHSIZE;H->elem = (int *)malloc(m * sizeof(int)); //分配内存H->count = m;for (i = 0; i<m; i++){H->elem[i] = NULLKEY;}return 1;}int Hash(int k)//除留余数法{return k % m;}void Insert(HashTable *H, int k)//插入数字如果有冲突用开放定址法{int addr = Hash(k);while (H->elem[addr] != NULLKEY){addr = (addr+1) % m;}H->elem[addr] = k;}int Search(HashTable *H, int k)//求哈希地址开放定址法解决冲突{int addr = Hash(k);while (H->elem[addr] != k){addr = (addr+1) % m;if (H->elem[addr] == NULLKEY || addr == Hash(k)) return -1;}return addr;}void Result(HashTable *H)//散列表元素显示{int i;for (i = 0; i<H->count; i++){if(H->elem[i]!=-32768)printf("%d ", H->elem[i]);}printf("\n");}int main(){int i, j, addr,n;HashTable H;int arr[HASHSIZE] = { NULL };Init(&H);printf("请输入数:");for (i = 0; i<10; i++)scanf("%d", &arr[i]);Insert(&H, arr[i]);}printf("输入的数存入哈希表后：");Result(&H);int b;printf("输入需要查找的数：\n");while(scanf("%d",&j)!=EOF){addr = Search(&H, j);if (addr == -1){printf("元素不存在,程序结束\n");break;}elseprintf("%d元素在表中的位置是:%d\n", j,addr+1); }}四、实验心得。

一、实验目的1. 理解并掌握几种常见查找算法的基本原理和实现方法。

2. 比较不同查找算法的时间复杂度和空间复杂度。

3. 通过实验验证查找算法的效率和适用场景。

二、实验内容本次实验主要涉及以下查找算法：1. 顺序查找法2. 二分查找法3. 散列查找法三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm四、实验步骤1. 实现顺序查找法2. 实现二分查找法3. 实现散列查找法4. 编写测试程序，分别对三种查找算法进行测试5. 比较三种查找算法的性能五、实验结果与分析1. 顺序查找法（1）实现代码```pythondef sequential_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1```（2）测试程序```pythonarr = [5, 3, 8, 6, 2, 7, 4, 9, 1]target = 6print("顺序查找结果：", sequential_search(arr, target))```（3）分析顺序查找法的时间复杂度为O(n)，空间复杂度为O(1)。

当数据量较大时，查找效率较低。

2. 二分查找法（1）实现代码```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1```（2）测试程序```pythonarr = [1, 2, 3, 4, 5, 6, 7, 8, 9]target = 6print("二分查找结果：", binary_search(arr, target))```（3）分析二分查找法的时间复杂度为O(log2n)，空间复杂度为O(1)。

HUNAN UNIVERSITY 课程实习报告题目：散列表问题学生姓名刘乐学生学号20080820208专业班级通信工程2班指导老师朱宁波完成日期2010年6月8日一、需求分析：1.本程序来自于图书馆靠书名来检索想要查找的书问题。

2.本程序要求：（1）根据输入建立图书名称表，采用创建散列表实现。

（2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。

3在dos系统下输入散列表内容和要查找的数据个数和数据。

4测试数据：二、概要设计为实现上述功能需要用到散列表的存储结构。

算法基本思想散列表存储的基本思想是用关键字的值决定数据元素的存储地址，散列表存储中解决碰撞的基本方法：①开放定址法：形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。

根据di取法不同，又分为三种：a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b．di =12，-12，22，-22，… ，±k2（k≤m/2）称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。

c．di =伪随机数序列，称为随机探测再散列。

②再散列法：Hi=RHi（key）i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。

该方法不易产生“聚集”，但增加了计算时间。

③链地址法：将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。

凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。

这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。

这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

数据结构实验散列表实验报告一、实验目的本次实验的主要目的是深入理解和掌握散列表这种数据结构的基本原理、实现方法以及其在实际应用中的性能特点。

通过实际编写代码和进行相关测试，提高对散列表的操作能力，并能够分析和解决在使用散列表过程中可能遇到的问题。

二、实验原理散列表（Hash Table）是一种根据关键码值（Key value）而直接进行访问的数据结构。

通过一个特定的函数（哈希函数）将关键码映射到表中的一个位置来访问记录，以加快查找的速度。

这个映射函数称为哈希函数，存放记录的数组称为哈希表。

哈希函数的设计至关重要，它需要尽可能地将不同的关键码值均匀地分布在哈希表中，以减少冲突的发生。

常见的哈希函数有直接定址法、除留余数法、数字分析法等。

冲突解决方法也是散列表中的重要部分。

当不同的关键码通过哈希函数映射到相同的位置时，就会产生冲突。

常见的冲突解决方法有开放定址法（线性探测、二次探测等）和链地址法。

三、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

四、实验内容1、哈希函数的实现采用除留余数法实现哈希函数。

代码如下：｀｀｀cppint hashFunction(int key, int tableSize) ｛return key ％ tableSize;｝｀｀｀2、散列表的创建与初始化使用动态数组创建散列表，并将所有位置初始化为空。

｀｀｀cppclass HashTable ｛private:int table;int size;public:HashTable(int tableSize) ｛size ＝ tableSize;table ＝ new intsize;for （int i ＝ 0; i ＜ size; i+＋）｛tablei ＝－1; ／／－1 表示为空｝｝～HashTable(）｛delete table;｝｝；｀｀｀3、数据插入操作采用线性探测法解决冲突。

实验十三哈希表（散列表）查找一、实验目的1.进一步理解散列存储原理；2.掌握在散列表中插入数据和查找数据的方法；3.会用不同的处理冲突方法建立散列表；4.了解在散列表中删除数据的方法。

二、实验环境Windows 2000以上版本的操作系统，Visual C++ 6.0版编程环境。

三、实验内容和步骤hash工程文件说明：ArrayHash.h和ArrayHash.cpp分别是采用开放定址法处理冲突的散列表抽象数据类型头文件和实现源代码；LinkHash.h和LinkHash.cpp分别是链地址法处理冲突的散列表抽象数据类型头文件和实现源代码；Hash.h和Hash.cpp分别是散列表长度、特殊标志和哈希函数、处理冲突函数的头文件和实现源代码。

1.已知散列表长11，地址区间为0～10，给定关键字序列（20，30，70，15，8，12，18，63，19）。

设哈希函数为h(k)=k％11，分别采用线性探查法和链地址法处理冲突，构造散列表。

要求写出各自的计算过程并画出对应的散列表。

解题方法及步骤请参考本次实验的PPT第1至第3页。

【重点】（额外参考内容：课本P266 例9.9 与课本P268例9.10。

程序参考：课本P268－P270）2.已知哈希函数为H(k)=k％11，线性探测法解决冲突，根据散列表的状态图，完成下面问题，并写出过程及结果。

1)在上述散列表的状态图中，在空位置上设置空标志NULLFLAG，并查找45；H1 =(H(45)+1)%11=2，占用;H2 =(H(45)+2)%11=3，查找成功。

2)查找5，若5不存在，则将其插入；H(5)=5％11＝5，地址被占用，线性探查下一地址；H1 =(H(5)+1)%11=6，占用;H2 =(H(5)+2)%11=7，占用;3)查找26，若26存在，则将其删除，并在相应位置设置删除标志DELETEFLAG；H(26)=26％11＝4，地址被占用，线性探查下一地址；H1 =(H(26)+1)%11=5，占用;4)查找5，若5存在，则将其删除；H(5)=5％11＝5，地址被占用，线性探查下一地址；H1 =(H(5)+1)%11=6，删除标志，继续探查;H2 =(H(5)+2)%11=7，占用;5)查找10，若10不存在，则将其插入；H(10)=10％11＝10，地址被占用，线性探查下一地址；6)查找27，若27不存在，则将其插入；H(27)=27％11＝5，地址被占用，线性探查下一地址；H1 =(H(27)+1)%11=6，删除标志，继续探查;H2 =(H(27)+2)%11=7，占用;H3 =(H(27)+3)%11=8，删除标志，继续探查;H4 =(H(27)+4)%11=9，占用;H5 =(H(27)+5)%11=10，占用;H6 =(H(27)+6)%11=0，占用;H7 =(H(27)+7)%11=1，占用;H8 =(H(27)+8)%11=2，占用;H9 =(H(27)+9)%11=3，占用;。

课程名称：数据结构实验项目：散列表题目：散列表实验一、需求分析1、实验目标掌握散列表的构造方法以及冲突处理方法，实现散列表的运算算法。

2、程序的输入和输出输入：void insertRec(char x[], char y[])输出：void print() {const char space[] = " ";int i, k;for (i = 0; i < N; i++) {k = H(a[i].key);cout << i << ":\t"<< a[i].key << "\t"<< a[i].value << "\t";if (strlen(a[i].key) > 0)cout << "(" << k << ")";cout << endl;}二、概要设计1、数据结构带头节点的线性链表。

主要的操作：查找节点，插入节点，更新节点，打印链表。

2、程序的模块分为两个程序文件。

主要模块如下：void init();void insertRec(char x[], char y[]);int searchRec(char x[]);int deleteRec(char x[]);void print();三、详细设计1、数据结构#include <cstdlib>#include <iostream>using namespace std;const int N = 17; //散列表长struct record { //记录char key[24];char value[24];int deleted;};record a[N]; //散列表int H(char key[]); //散列函数void init();void insertRec(char x[], char y[]);int searchRec(char x[]);int deleteRec(char x[]);void print();int main(int argc, char *argv[]){int i, k;char x[24], y[24];init();cout << "输入要插入的记录: \n";for (i = 0; i < 14; i++) {cin >> x >> y;insertRec(x, y);print();}system("PAUSE");return EXIT_SUCCESS;}void insertRec(char x[], char y[]) { int i, k;i = H(x);while (strlen(a[i].key) > 0) {i++; //线性探测if (i == N) i = 0; //绕回表头}strcpy(a[i].key, x);strcpy(a[i].value, y);}int deleteRec(char x[]) {}int searchRec(char x[]) {}int H(char key[]) {int i = key[0], j = key[1];return (i*i + j*j) % N;}void print() {const char space[] = " "; int i, k;for (i = 0; i < N; i++) {k = H(a[i].key);cout << i << ":\t"<< a[i].key << "\t"<< a[i].value << "\t";if (strlen(a[i].key) > 0)cout << "(" << k << ")"; cout << endl;}}void init() {int i;for (i = 0; i < N; i++) {strcpy(a[i].key, "");strcpy(a[i].value, "");a[i].deleted = 0;}}四、测试结果1、输入autumn 秋天2、输出0：1：2：3:4:5:6:7:8:9：10：11:12:autumn秋天<12>13:14:15:16:。

散列表的设计实验报告1、题目：散列表的设计:针对某个集体中人名设计一个散列表，使得平均查找长度不超过R,并完成相应的建表和查表程序。

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

待填入哈希表的人名共30个，取平均查找长度上限为2，哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。

人名长度不超过20个字符。

可先对过长的人名作折叠处理。

3、设计思想：a.构造哈希函数的方法很多，常用的有(1)直接定址法(2)数字分析法;(3)平方取中法;(4)折叠法;( 5)除留余数法;(6)随机数法；本实验采用的是除留余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址H(key)=key MOD p,p<=m.b.哈希函数可以减少冲突，但不能避免。

通常用的处理冲突的方法有：（1）开放定址法，这种方法还包含三种形式，一种叫线性探测再散列，一种叫二次探测再散列，另一种叫伪随机探测再散列。

本实验采用的是第三种伪随机探测再散列。

求下一个开放地址的公式为：Hi=(H(k)+di)MOD m (Di=伪随机数序列)c.对哈希表的操作InitNameList() 操作结果：姓名（结构体数组）初始化CreateHashList() 操作结果：建立哈希表FindList() 操作结果：在哈希表中查找Display() 操作结果：显示哈希表4、程序结构图5、流程图6、数据测试7、程序清单#include<iostream>#include<string>using namespace std;#define HASH_LENGTH 50#define M 47#define NAME_NO 30typedef struct{ char *py;int k;}NAME;NAME NameList[HASH_LENGTH]; typedef struct{ char *py;int k;int si;//查找长度}HASH;HASH HashList[HASH_LENGTH]; void InitNameList(){ char *f;int r,s0,i;for (i=0; i<HASH_LENGTH; i++){NameList[i].py = new char[20];NameList[i].py[0] = 0;}strcpy(NameList[0].py, "lintingting"); strcpy(NameList[1].py, "chenxiaoping"); strcpy(NameList[2].py, "jianghaiyan"); strcpy(NameList[3].py, "wangtingting"); strcpy(NameList[4].py, "zhouhuihui"); strcpy(NameList[5].py, "zhuzhenguo"); strcpy(NameList[6].py, "wuqingwen"); strcpy(NameList[7].py, "chenzuopeng"); strcpy(NameList[8].py, "jinlining"); strcpy(NameList[9].py, "zhandakan"); strcpy(NameList[10].py, "linjiajia"); strcpy(NameList[11].py, "huangwenjun"); strcpy(NameList[12].py, "lizhongjing"); strcpy(NameList[13].py, "sushiding"); strcpy(NameList[14].py, "ouyangyaoyao"); strcpy(NameList[15].py, "chenwei");strcpy(NameList[16].py, "linxiaxiao"); strcpy(NameList[17].py, "zhanjie");strcpy(NameList[18].py, "baishujun"); strcpy(NameList[19].py, "gongqiaoqiao"); strcpy(NameList[20].py, "lvhaitao"); strcpy(NameList[21].py, "jiangqingsong"); strcpy(NameList[22].py, "gubaolong"); strcpy(NameList[23].py, "yehuaisong"); strcpy(NameList[24].py, "wangyuqin"); strcpy(NameList[25].py, "xuefeifei"); strcpy(NameList[26].py, "wujianshu"); strcpy(NameList[27].py, "zhanghuajiang"); strcpy(NameList[28].py, "zhengpan"); strcpy(NameList[29].py, "sudongdong");for(i=0;i<NAME_NO;i++){s0=0;f=NameList[i].py;for(r=0;*(f+r)!='\0';r++)s0=*(f+r)+s0;NameList[i].k=s0;}}void CreateHashList(){int i;for(i=0; i<HASH_LENGTH;i++){HashList[i].py=new char[20];HashList[i].py[0] = 0;HashList[i].k=0;HashList[i].si=0;}for(i=0;i<HASH_LENGTH;i++){int sum=0;int adr=(NameList[i].k)%M;int d=adr;if(HashList[adr].si==0) //如果不冲突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else //冲突{while (HashList[d].k!=0){d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突sum=sum+1;};HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}}}void FindList(){string name;int s0=0,r,sum=1,adr,d;cout<<"请输入人名的拼音:"<<endl;cin>>name;for(r=0;r<20;r++)s0+=name[r];adr=s0%M; //使用哈希函数d=adr;if(HashList[adr].k==s0)cout<<"姓名:"<<HashList[d].py<<endl<<"关键字:"<<s0<<endl<<"查找长度为: 1"<<endl;else if (HashList[adr].k==0)cout<<"无此记录!"<<endl;else{int g=0;while(g==0){d=(d+s0%10+1)%M;sum=sum+1;if(HashList[d].k==0){cout<<"无此记录!"<<endl;g=1;}if(HashList[d].k==s0){cout<<"姓名:"<<HashList[d].py<<endl<<"关键字:"<<s0<<endl<<"查找长度为:"<<sum<<endl;g=1;}};}}void Display(){int i;float average=0;cout<<"\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n";for(i=0; i<50; i++){cout<<i<<" ";cout<<"\t"<<HashList[i].k<<" ";cout<<"\t\t"<<HashList[i].si<<" ";cout<<"\t\t"<<(HashList[i].k%M)<<" ";cout<<"\t "<<HashList[i].py<<" ";cout<<"\n";}for(i=0;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;cout<<"平均查找长度：ASL("<<NAME_NO<<")="<<average<<endl; }int main(){char x;InitNameList(); CreateHashList ();cout<<"d. 显示哈希表"<<endl<<"f. 查找"<<endl<<"任意键退出"<<endl<<"请选择："<<endl;while(cin>>x){if(x=='d'){Display();cout<<endl;}else if(x=='f'){FindList();cout<<endl;}else break;}for (int i=0; i<HASH_LENGTH; i++){free(NameList[i].py);free(HashList[i].py);}return 0;}。

计算机科学与技术系之欧侯瑞魂创作哈希表的设计与实现项目陈说专业名称计算机科学与技术项目课程数据结构与算法项目名称哈希表的设计与实现班级项目人员钱海峰,郑秀娟,王传敏,杨青,凌波实验日期 2015.12.9目录一．设计目的 (3)二．问题分析 (3)三．设计环境 (3)四．人员分配 (3)五．详细设计和编码 (4)六．实验分析 (7)1测试分析 (7)2性能分析……………………………………………………11附录 (12)参考书目 (17)一．设计目的（1）掌握散列结构和散列函数的相关概念（2）掌握散列结构的存储结构的相关概念（2）掌握散列抵触的处置方法（3）运用散列解决抵触问题.二．问题分析要完成如下要求：设计哈希表实现整数查询系统.实现本项目需要解决以下问题：（1）如何设计一个哈希表.（2）如何在哈希表中拔出记录.（3）如何删除哈希表中的记录.（4）如何查找并显示记录.（5）如何解决抵触问题.三．设计环境⒈硬件：计算机每人一台.⒉软件：Windows把持系统和Microsoft Visual VC++6.0编译器.四．人员分配五．详细设计和编码1.界说结点结构类型在链地址法中,每个结点对应一个链表结点,由3个域组成,结构如图9-1所示.其中,key为关键字域,寄存结点关键字；data为数据域,寄存结点数据信息；next为链域,寄存指向下一个同义词结点的指针.图9-1 链地址法结点结构链地址数据结构类型如下：#define MAX_LENGTH 50typedef struct node{int data;struct node *next;}ElemNode;typedef struct{ElemNode *first;}ElemHeader,HashTable[MAX_LENGTH];#include <stdio.h>设计一个Hash（）函数,本设计中对散列函数选择的是除留余数法,即对关键字进行模运算,将运算结果所得的余数作为关键字（或结点）的存储地址,即i=ht mod n,本设计n由用户自己输入,然后将计算出来的结果返回.具体设计如下：int Hash(int ht){ int i;i = ht%n;return i;}3.初始化散列链表初始化链地址散列算法只需要把散列表中所有表头结点的指针域置为NULL.初始化散列链表的算法如下：void initHashTable(HashTable ht,int n){int i;for(i =0;i<n;i++){ ht[i].first= NULL;}}在整个设计中,创立哈希表必需是第一步要做的,结点之前应先输入结点的个数,利用链地址法解决抵触.添加结点实际是调用了拔出结点函数insert（）,需要利用哈希函数计算出地址,其次将结点拔出以关键字为地址的链表后.建立结点应包括静态申请内存空间,想地址中输入信息,同时最后一个结点中的next指针即是NULL.具体实现如下：int createHashTable(HashTable ht){HashTable *p=ht;int ad[MAX_LENGTH]={0};int i;printf("请输入拔出个数n:");scanf("%d",&n);printf("\n请输入拔出%d个整数:",n);for(i=0;i<n;i++)scanf("%d",&ad[i]);initHashTable(p,n);for(i=0;i<n;i++)insert(p,ad[i]);return 1;5.散列链表拔出结点算法将一个结点拔出到散列链表中,其算法分为以下几步：（1）根据结点关键字计算散列地址；（2）根据散列地址找到表头结点,并将结点拔出到对应的链表中.链地址法散列表的拔出算法如下：void insert(HashTable ht,int ele){int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode));p->data = ele;p->next = ht[i].first;ht[i].first = p;}6.散列链表查找结点算法在散列链表中查找一个结点,其算法分为以下几步：（1）根据待查找关键字计算散列地址；（2）在散列地址所指向的单链表中顺序查找待查找关键字；（3）如果找到待查关键字,则返回指向该结点的指针；否则返回NULL.散列链表中查找结点的算法如下：ElemNode* search(HashTable ht,int ele){ int i;ElemNode *p;i = Hash(ele);p=ht[i].first;while(p!=NULL && p->data != ele){ p = p->next; }if(p!=NULL){printf("数据%d的位置为%d\n",ele,i);return p;}else{ printf("哈希表中无%d\n",ele);return p;}}7.散列链表删除结点算法在散列表中删除一个结点,其算法分为两步：（1）查找要删除的结点；（2）如果找到则删除,否则显示提示信息.在散列表中删除一个结点的算法如下：void dele(HashTable ht,int ele){//删除指定命据int i;ElemNode *p,*q;i = Hash(ele);p=ht[i].first;if(p == NULL){printf("error occurred! ");}if(p->data == ele){ht[i].first = p->next;}else {q= p->next;while(q!=NULL && q->data != ele){p=q;q = q->next;}if(q == NULL){printf("error occurred! ");}else{p->next = q->next;free(q);}}}六．实验分析1.测试分析（1）建立哈希表（2）拔出一个结点并显示：（3）查找结点：在哈希表中没有3这个数,会输出一行提示信息.（4）删除一个结点并显示：2.性能分析散列法实质上是一种通过关键字直接计算存储地址的方法.在理想情况下,散列函数可以把结点均匀地分布在散列表中,不发生抵触,则查找过程无需比力,其时间复杂度O（1）.但在实际使用过程中,为了将范围广泛的关键字映射到一组连续的存储空间,往往会发生同义词抵触,这时就需要进行关键字比力.能够把关键字尽可能均匀地分布到散列表中的函数是“好”的散列函数.好的散列函数可以有效地降低抵触的的发生,从而提高查找性能.但好的散列函数和关键字的数字特征有关,因此不存在对任何结点都好的散列函数.对同一种散列函数,采纳分歧的抵触处置方法将发生分歧的效果,例如线性探测法容易招致“二次聚集”,而拉链法可以从根本上根绝二次聚集,从而提高查找性能.不外也会“浪费”一部份散列表的空间.附录****************************法式源代码*********************************//头文件#include <stdio.h>#include <stdlib.h>#define MAX_LENGTH 50typedef struct node{int data;struct node *next;}ElemNode;typedef struct{ElemNode *first;}ElemHeader,HashTable[MAX_LENGTH];int n;//存储哈希表长度void initHashTable(HashTable ht,int n);void insert(HashTable ht,int ele);ElemNode* search(HashTable ht,int ele);void dele(HashTable ht,int ele);int Hash(int ht);int createHashTable(HashTable ht);void showHashTable(HashTable ht);void menu(HashTable ht);//菜单//功能函数sanlibiao.c#include"sanlibiao.h"void initHashTable(HashTable ht,int n){//初始化int i;for(i =0;i<n;i++){ht[i].first= NULL;}}void insert(HashTable ht,int ele){//拔出int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode)); // p->key = ele;p->data = ele;p->next = ht[i].first;ht[i].first = p;}ElemNode* search(HashTable ht,int ele){//查找int i;ElemNode *p;i = Hash(ele);p=ht[i].first;while(p!=NULL && p->data != ele){p = p->next;}if(p!=NULL){printf("数据%d的位置为%d\n",ele,i);return p;}else{printf("哈希表中无%d\n",ele);return p;}}void dele(HashTable ht,int ele){//删除指定命据int i;ElemNode *p,*q;i = Hash(ele);p=ht[i].first;if(p == NULL){printf("error occurred! ");}if(p->data == ele){ht[i].first = p->next;}else {q= p->next;while(q!=NULL && q->data != ele){p=q;q = q->next;}if(q == NULL){printf("error occurred! ");}else{p->next = q->next;free(q);}}}int Hash(int ht){//哈希函数int i;i = ht%n;return i;}int createHashTable(HashTable ht)//创立哈希表{HashTable *p=ht;int ad[MAX_LENGTH]={0};int i;printf("请输入拔出个数n:");scanf("%d",&n);printf("\n请输入拔出%d个整数:",n);for(i=0;i<n;i++)scanf("%d",&ad[i]);initHashTable(p,n);for(i=0;i<n;i++)insert(p,ad[i]);return 1;}void showHashTable(HashTable ht)//显示哈希表{int i;ElemNode *p;//i = Hash(ele);for(i=0;i<n;i++){p=ht[i].first;if(p!=NULL)printf("位置%d上的数据：",i);while(p!=NULL){printf("%d ",p->data);p = p->next;}if(ht[i].first!=NULL)printf("\n");}}void menu(HashTable ht){int p,h; //p 菜单选择；do{// system("cls");//清屏printf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");printf("☆★☆★\n");printf("★☆************** 欢迎来到哈希表系统! ***************★☆\n");printf("☆★合肥学院☆★\n");printf("★☆计算机科学与技术★☆\n");printf("☆★钱海峰,郑秀娟,王传敏,杨青,凌波☆★\n");printf("☆★☆★\n");printf("☆★※※※※※※※☆★\n");printf("★☆※菜单※★☆\n");printf("☆★※※※※※※※☆★\n");printf("☆★☆★\n");printf("★☆************** (1)---创立哈希表******************★☆\n");printf("☆★************** (2)---查找******************★☆\n");printf("★☆************** (3)---删除******************★☆\n");printf("☆★************** (4)---拔出******************★☆\n");printf("★☆************** (5)---输出哈希表******************★☆\n");printf("☆★************** (0)---退出******************☆★\n");printf("★☆****************************************************★☆\n");printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★\n");printf("\n请在上述序号中选择一个并输入： ");scanf("%d",&p);switch(p){case 1:createHashTable(ht);break;case 2:printf("请输入要查找的数：\n");scanf("%d",&h);search(ht,h);break;case 3:printf("请输入要删除的数：\n");scanf("%d",&h);dele(ht,h);printf("\n");break;case 4:printf("请输入要拔出的数：\n");scanf("%d",&h);insert(ht,h);printf("\n");break;case5:showHashTable(ht);printf("\n");break;case 0: break; //退出default:printf("输入毛病!请重新输入!\n");break;}//system("pause");//系统暂停,提示按任意键继续....}while(p!=0); //for do}//主函数 mian.c#include "sanlibiao.h"int main(){HashTable ht;menu(ht);//进入菜单循环return 0;参考书目王昆仑,李红,《数据结构与算法》,中国铁道出书社,2007年6月初版.谭浩强,《C语言法式设计》,北京：清华年夜学出书社,2005年7月第三版.。

散列查找（散列表创建及平⽅探测）编译处理时，涉及变量及属性的管理：插⼊（新变量的定义），查找（变量的引⽤）。

顺序查找 O(N) ⼆分查找 O(logN) ⼆叉树查找O(H) 平衡⼆叉树 O（logN）如何快速查找？查找的本质：已知对象找位置有序的安排对象-》全序：顺序查找半序：⼆叉树直接算出位置-》散列查找散列查找:1.计算位置。

2.解决冲突。

⼀、计算位置构造散列函数。

要求：计算简单；地址分布均匀。

数字关键词：1 直接定值。

2 除留余数 h(key)= key mod p,p<tablesize且p为素数。

3 数字分析法。

4 折叠法。

5平⽅取中法。

字符关键字：1 ASII码加和法 2 前3个字符移位法。

3 移位法。

⼆、处理冲突1. 开放地址法。

（换个位置）2.链地址法。

（同⼀位置的冲突对象放在⼀起）开放地址法⼀旦发⽣冲突，就按照某种规则起找另⼀空地址。

若发⽣了第i次冲突，试探性的将地址加di线性探测：di=i 容易产⽣聚集现象平⽅探测：di=+-i*i 有空间，但跳来跳去不⼀定能找到。

有定理显⽰，如果散列表长度是某个4k+3形式的素数时，平⽅探测就可以探查到整个散列空间。

双散列：di=i*h2(key) 对任意key,h2(key)!=0 h2(key )=p-(key mod p)再散列：把散列表扩⼤，散列表扩⼤时，需要重新计算。

代码散列表的创建：1#define MAXTABLESIZE 100000 /* 允许开辟的最⼤散列表长度 */2 typedef int Index;3 typedef Index Position;4 typedef enum { Legitimate, Empty, Deleted}EntryType;56 typedef struct HashEntry cell;// 散列表单元定义7struct HashEntry8 {9 ElementType Data; //散列表单元中的数据10 EntryType Info; // 散列表单元的信息11 };12 typedef struct Tb1Node *HashTable;//散列表定义13struct Tb1Node14 {15int TableSize; //散列表⼤⼩16 cell *cells; //散列表数组，数组是散列表单元的集合17 };18int NextPrime(int X)19 {20int i,P;21 P = (X%2==0) ? X+1:X+2; //PC从x下⼀个数奇数开始22while(P< MAXTABLESIZE) //23 {24for(i=(int) (sqrt(X));i<2;i--)//依次判断从根号x到2中是否有可以整除的25if(P%i==0) break; //说明不是素数，跳出for，26if(i==2)break; //判断是不是全都除了⼀遍，如果全都除了⼀遍，都不整除，说明是素数，跳出while 27else P=P+2; //说明不是素数，继续从下⼀个奇数p+2继续查找。

散列表实验报告doc散列表实验报告篇一：数据结构实验散列表实验报告课程实验报告课程名称：实验项目名称：专业班级：姓名：学号：完成时间：月背景散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做散列函数，存放记录的数组叫做散列表。

在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。

例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。

该符号表常采用散列表。

例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。

LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。

问题描述我们希望在浩瀚的图书中，去发现一本书是否存在。

我们不知道书的编号，只知道它的书名。

（其实这已经不错了...）。

通过书名，来查询它是否存在。

为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。

基本要求（1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。

（2）数据的输入输出格式：输入分为两部分第一部分，第一行是行数n，n 第二部分，第一行是行数m，m 输出：输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。

测试数据输入：4aansandhellocppaban。

散列表查找算法 python3散列表（Hash Table）是一种通过计算某个值（关键字）的散列函数，将这个值映射到一个表中的位置来进行快速查找的数据结构。

在Python中，我们可以使用字典（dictionary）来实现散列表。

下面是一个用Python实现散列表查找算法的例子：```pythondef hash_function(key):return key % 10 # 使用取余操作符作为散列函数def insert(hash_table, key, value):index = hash_function(key)hash_table[index] = valuedef search(hash_table, key):index = hash_function(key)if index in hash_table: # 判断散列表中是否存在该索引return hash_table[index]else:return None# 示例hash_table = {} # 创建一个空散列表# 在散列表中插入键值对insert(hash_table, 23, 'Alice')insert(hash_table, 14, 'Bob')insert(hash_table, 7, 'Charlie')# 查找键值对print(search(hash_table, 23)) # 输出：Aliceprint(search(hash_table, 14)) # 输出：Bobprint(search(hash_table, 7)) # 输出：Charlieprint(search(hash_table, 10)) # 输出：None（散列表中不存在该键）```在上面的例子中，我们使用简单的取余操作符作为散列函数，并且假设散列表的大小为10。

其中，`hash_function()`函数用于计算键的散列值，`insert()`函数用于将键值对插入散列表中，`search()`函数用于搜索相应的键。

详解数据结构之散列（哈希）表1.散列表查找步骤散列表，最有用的基本数据结构之一。

是根据关键码的值直接进行访问的数据结构，散列表的实现常常叫做散列（hasing）。

散列是一种用于以常数平均时间执行插入、删除和查找的技术，下面我们来看一下散列过程。

我们的整个散列过程主要分为两步：1.通过散列函数计算记录的散列地址，并按此散列地址存储该记录。

就好比麻辣鱼，我们就让它在川菜区，糖醋鱼，我们就让它在鲁菜区。

但是我们需要注意的是，无论什么记录我们都需要用同一个散列函数计算地址，然后再存储。

2.当我们查找时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。

因为我们存和取的时候用的都是一个散列函数，因此结果肯定相同。

刚才我们在散列过程中提到了散列函数，那么散列函数是什么呢？我们假设某个函数为f，使得存储位置= f (key) ，那样我们就能通过查找关键字不需要比较就可获得需要的记录的存储位置。

这种存储技术被称为散列技术。

散列技术是在通过记录的存储位置和它的关键字之间建立一个确定的对应关系 f ，使得每个关键字key 都对应一个存储位置f(key)。

见下图这里的 f 就是我们所说的散列函数（哈希）函数。

我们利用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间就是我们本文的主人公------散列(哈希)上图为我们描述了用散列函数将关键字映射到散列表。

但是大家有没有考虑到这种情况，那就是将关键字映射到同一个槽中的情况，即f(k4) = f(k3) 时。

这种情况我们将其称之为冲突，k3 和k4 则被称之为散列函数 f 的同义词，如果产生这种情况，则会让我们查找错误。

幸运的是我们能找到有效的方法解决冲突。

首先我们可以对哈希函数下手，我们可以精心设计哈希函数，让其尽可能少的产生冲突，所以我们创建哈希函数时应遵循以下规则：1.必须是一致的。

假设你输入辣子鸡丁时得到的是在看，那么每次输入辣子鸡丁时，得到的也必须为在看。

6 查找1. 实验题目与环境1.1实验题目及要求（1）折半查找编程实现折半查找的非递归算法。

（2）二叉排序树编程实现一棵二叉排序树，包括插入、删除、查找等功能。

（3）散列表的应用选择合适的散列函数和冲突处理方法，编程实现QQ账户的申请与登录。

2. 问题分析（1）折半查找二分查找，基本思想为：首先将待查的key值与有序数据表中的中间位置mid上的元素进行比较，若相等则查找完成；否则，若R[mid] > key，说明待查元素可能在左子表中，则在左子表中继续进行二分查找，若R[mid] < key，说明待查元素可能在右子表中，则在右子表中继续进行二分查找。

如此进行下去，直到找到关键字为key的元素，或者未找到，则查找失败。

（2）二叉排序树二叉排序树的建立，反复调用插入算法，就可以构造出一棵二叉排序树。

二叉排序树的插入算法，如果二叉排序树为空，新建结点*s，数值域赋值，左右孩子置空；当二叉排序树非空时，将待插入的s的数据域data与树根结点关键字BT->data比较，若BT->data <= data，则将s所指的结点数值域data插入到右子树中，否则插入到左子树中。

二叉排序树创建成功后，中序遍历输出结果，查看是否为有序序列，是则成功，否则失败。

（3）散列表的应用输入首先给出一个正整数N（≤10^5 ），随后给出N行指令。

每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。

其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。

QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。

密码为不小于6位、不超过16位、且不包含空格的字符串。

3. 测试用例（1）折半查找数据：数组1 2 3 4 5 6 7 8 9 10（2）二叉排序树数据：建立二叉树5 1 9 6 3 2 8 7 4 0（3）散列表的应用输入样例：5L 1234567890 myQQ@N 1234567890 myQQ@N 1234567890 myQQ@L 1234567890 myQQ@qqL 1234567890 myQQ@4. 结果展示（1）折半查找图1-1建立数据表（a）查找成功（b）查找失败图1-2查找结果展示（2）二叉排序树（a）无重复数据（b）有重复数据图2二叉排序树建立与中序遍历结果（3）散列表的应用5.实验总结本次实验中学会了折半查找和二叉排序树还有散列表的各个功能和操作，通过实验对栈队列得到了更加深刻的认识和更完善的运用。