-
2017-06-20 13:49:44
将上面的数据利用长度为15的哈希表存储,输出存储后的哈希表。哈希函数采用key%13,用线性探测再散列解决冲突,设计并实现查找运算。
代码:
#include <bits/stdc++.h> using namespace std; const int MAXN=15; typedef struct HashList{ int elem[MAXN],mod; HashList(){ for(int i=0;i<MAXN;i++) elem[i]=-1; mod=13; } public: int Insert(int x){ int pos=x%mod; while(elem[pos]!=-1) pos=(pos+1)%mod; elem[pos]=x; return pos; } void show(){ for(int i=0;i<mod;i++) cout<<elem[i]<<' '; cout<<endl; } int Find(int x){ int pos=x%mod; while(elem[pos]!=x) pos=(pos+1)%mod; elem[pos]=x; return pos; } }HashList; int main() { srand((unsigned long long)time(0)); int a[10]={90 ,92 ,41 ,2 ,4 ,29 ,73 ,87 ,11 ,77}; HashList b; for(int i=0;i<10;i++){ b.Insert(a[i]); b.show(); } cout<<a[3]<<' '<<b.Find(a[3])<<endl; }
更多相关内容 -
哈希表线性探测(功能:查找,删除,插入)
2021-01-08 12:25:40直接看代码: #include <stdio.h> #include <stdlib.h> //宏定义相关常量 #define Max 10 #define Size 10 typedef struct Sqlist{ int *data; int length;...//哈希表 int hash (int key){直接看代码:
#include <stdio.h> #include <stdlib.h> //宏定义相关常量 #define Max 10 #define Size 10 typedef struct Sqlist{ int *data; int length;//长度 }Sqlist;//顺序表 typedef struct HashSqlist{ int *data; int length; }HashSqlist;//哈希表 int hash (int key){ return key%10; } //哈希函数 void InitSqlist(Sqlist &l){ //这里l 还没定义,所以要加 & printf("Please int the length of the hashTable\n"); scanf("%d",&l.length); l.data = (int *)malloc (Max * sizeof(int)); printf("Please int %d numbers\n",l.length); for (int i = 0; i < l.length ; i ++) scanf("%d",&l.data[i]); }//建立一个顺序表,通过顺序表给哈希表赋值 void InitHashSqlist(Sqlist l,HashSqlist &hl){ hl.data = (int *)malloc (Max * sizeof (int )); hl.length = Size; int i,j,key; for (i = 0; i < hl.length; i ++) hl.data[i] = 0; for (i = 0; i < l.length ; i ++){ key = hash(l.data[i]); if (hl.data [key] != NULL){ for (j = 1; hl.data[key] != NULL; j ++) key = hash(l.data[i] + j); } hl.data[key] = l.data[i] ; printf("%d ----%d \n",key,hl.data[key]);//顺便输出,方便检验 } } void OutPut(HashSqlist hl){ int key ; for (key = 0; key < hl.length; key ++){ if (hl.data[key] == 0){ key = key; } else printf("%d----%d \n",key , hl.data[key]); } }//哈希表输出 void Find(HashSqlist hl){ int address; printf("please int an address to find !\n"); scanf("%d",&address); printf("The number is : %d\n",hl.data[address]); }//根据地址查找 void Delete(HashSqlist hl){ int address; printf("please int the address of the element that you want to delete!\n"); scanf("%d",&address); hl.data[address] = 0; printf ("Now, the HashSqlist is :\n"); OutPut(hl); }//删除地址元素 void Insert(HashSqlist hl){ int i; printf("Please int the number that you want to insert!\n"); scanf("%d",&i); int key = i; if (hl.data [key] != NULL){ for (int j = 1; hl.data[key] != NULL; j ++) key = hash(hl.data[key] + j); } hl.data[key] = i; OutPut(hl); }//插入元素 int main (){ Sqlist l; HashSqlist hl; InitSqlist(l); InitHashSqlist(l,hl); Find(hl); Delete(hl); Insert(hl); return 0; }
-
哈希表线性探测再散列
2021-05-23 07:47:52#include#define HashLength 23using namespace std;//哈希函数int HashFuc...}//线性探测再散列int *HashReLineExplor(int A[], int k,int h[],int m)//关键字数组、关键字个数、哈希表、哈希表长度{for (int i = 0...#include
#define HashLength 23
using namespace std;
//哈希函数
int HashFuc(int i,int length)
{
return i%length;
}
//线性探测再散列
int *HashReLineExplor(int A[], int k,int h[],int m)//关键字数组、关键字个数、哈希表、哈希表长度
{
for (int i = 0; i < m; i++)
h[i] = NULL;
for (int j = 0; j < k; j++)
{
int loc = HashFuc(A[j], HashLength);
while (h[loc])
{
loc=loc++%m;//寻找第一个空位置
}
h[loc] = A[j];
}
return h;
}
int main()
{
int Hash[25];//哈希表
int Key[20] = { 23, 26, 14, 22, 24, 38, 32, 120, 29, 93, 83, 21, 11, 23, 43, 123, 94, 93, 92, 91 };//关键字
HashReLineExplor(Key, 20, Hash, 25);
for (int i = 0; i < 25; i++)
{
if (Hash[i])
{
printf("第%2d个元素是:%4d\n", i, Hash[i]);
}
}
return 0;
}
数组中元素:23, 26, 14, 22, 24, 38, 32, 120, 29, 93, 83, 21, 11, 23, 43, 123, 94, 93, 92, 91
哈希表中元素:
第 0个元素是: 23 第 1个元素是: 24 第 2个元素是: 93 第 3个元素是: 26 第 4个元素是: 23 第 5个元素是: 120 第 6个元素是: 29 第 7个元素是: 94 第 8个元素是: 123 第 9个元素是: 32 第10个元素是: 93 第11个元素是: 11 第12个元素是: 92 第14个元素是: 14 第15个元素是: 38 第16个元素是: 83 第20个元素是: 43 第21个元素是: 21 第22个元素是: 22 第23个元素是: 91 请按任意键继续. . .
-
哈希表线性探测再散列(纯数字)
2018-12-22 11:09:22c代码实现哈希表线性探测再散列。关键字均为纯数字。查找时为单次查找,未加入循环 -
哈希表线性探测再散列的方法详解
2020-03-26 16:01:56例:设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法) 解题步骤: 1.将 ...哈希表线性探测再散列的方法详解
例:设哈希表长为m=14,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法)解题步骤:
(1)将关键字序列中的每一个数除以散列函数中的11并取余数。
(2)将关键字对照余数,放入哈希表中。
(3)因为在关键字序列中16排在51前,所以我们先处理关键字16的冲突,也就是先解决关键字16到底应该放在哪一个哈希表值的位置。
(4)关键字16除以11取余数为5,哈希表值为5处已经被关键字5占用,关键字5在关键字序列中排在16的前面,所以,关键字16只能向后移动一位放在哈希表值为6处,但是此时哈希表6的位置处放的是关键字17,我们查看关键字序列可以发现,关键字16在序列中是排在17的前面,所以,可以将16放在哈希表值为6处。此时,17变为冲突的关键字。
(5)此时冲突关键字为17和51,对照关键字序列,关键字51的位置排在关键字17之前,所以我们先处理关键字51的冲突。
(6)关键字51与关键字7冲突,查看关键字序列,关键字7排在关键字51的前面,所以关键字需向后移动一位,在哈希表值8处存储,查看哈希表,值为8处没有其他关键字占用,将关键字51放入8处。
(7)此时只有关键字17处于冲突状态。哈希表值为7、8、9、10处关键字为7、51、31、21,查看关键字序列发现关键字7、51、31、21均排在17的前面,所以关键字17只能放在此时为空的哈希表值11处。
仅仅只是为了考试,我太难了。。。。°(°¯᷄◠¯᷅°)°。
-
133-哈希表-线性探测法代码实现
2022-05-02 19:22:541、哈希表-线性探测法理论 线性探测法的理论我们在上一篇博客已经阐述了。 现在我们来看看线性探测法的增删查的代码思想: 1.1、哈希表的增加元素 注意: 往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然... -
552-哈希表-线性探测法代码实现
2021-09-13 09:28:34哈希表-线性探测法理论 线性探测法的理论我们在上一篇博客已经阐述了。 现在我们来看看线性探测法的增删查的代码思想: 哈希表的增加元素: 注意:往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然访问数组... -
哈希表——线性探测
2018-10-13 19:04:29* 哈希表是根据关键码值来进行访问的数据结构 * 也就是说 他通过关键码值映射到表中的一个位置来访问记录,来加快查找的速度, * 这个映射叫做散列函数,这个存放记录的数组叫做散列表 * 1、哈希表可以快速... -
java哈希表(线性探测哈希表。链式哈希表)
2021-03-14 11:16:39class LinerHashMap>{//散列表数组private Entry[] hashTable;...//哈希表的装载因子private doubleloadFactor;//定义素数表private static int[] primTable;//记录当前使用的素数的下标private intprimIndex;/... -
哈希表实现线性检测(超详细)
2022-04-04 22:11:54哈希表的线性检测: 思路分析: 1.哈希表定义 ----成员定义(private):存储方式(哈希节点的数组)、元素空间的大小、哈希表构造函数 2.哈希表存入的数据类型: 哈希节点:哈希函数需要知道键值,因此键值数据设置成... -
哈希表线性探测&二次探测
2017-06-09 11:00:36在代码中实现了哈希表中任意类型都可以存放,即哈希函数要可扩展以及哈希表动态增容的功能。 贴上代码: #include #include using namespace std; template//特化 class _HashFun { public: size_t operator... -
哈希表(线性存储)+ 线性探测法解决哈希冲突
2021-03-22 23:45:42哈希表(线性存储)+ 线性探测法解决哈希冲突: 将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小... -
搜索结构之哈希表(线性探测法)
2017-06-20 12:01:58散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组... -
C语言-----生成哈希表(线性探测法)
2019-11-30 21:23:13/* / / @哈希表(线性探测法) / */ #include<stdio.h> #include<stdlib.h> #include<windows.h> #define Field -1 #define null -32768 typedef struct hashmap... -
基于C语言实现哈希表(线性探测)
2018-05-28 17:24:26之前在写过的很多的结构...但是如果有一种存储结构,通过某种函数使元素的存储位置与他的关键码之间能够建立一一映射的关系,那么就能够直接地查找到需要地元素,时间复杂度就达到了O(1),那么这种结构就是哈希表。... -
DS哈希查找—线性探测再散列
2021-12-27 21:39:01数据结构实验题目:DS哈希查找—线性探测再散列 及其解答 -
哈希表的线性探测法代码实现
2022-05-23 20:08:26线性探测法理论: 哈希表增加元素 增加元素注意两点: 往后遍历寻找空闲位置是环形遍历,否则访问会数组越界 发生哈希冲突找空闲位置的时候,有两种情况:这个位置一直是空的没放过元素;这个位置是空的,以前放过... -
哈希表线性探测法和二次探测法详细代码
2018-07-28 16:58:14//哈希表中每个元素不仅包含关键字,还有其状态信息 typedef struct Element{ Key key; State state; } Element; //哈希表,包括元素类型,有效数据大小,容量和哈希函数 typedef struct HashTable { Element *... -
15-B. DS哈希查找—线性探测再散列
2021-12-22 12:57:34输入关键字集合,用线性探测再散列构建哈希表,并查找给定关键字。 –程序要求– 若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件,不看代码,作0分... -
哈希表,开放地址法之线性探测代码(JAVA)
2019-04-14 01:32:07NULL 博文链接:https://128kj.iteye.com/blog/1744810 -
哈希表的C++实现(线性探测)
2017-03-14 12:31:26简介哈希表/散列表(HashTable)是一种根据关键字(key)直接进行访问数据存储位置的数据结构。他通过一个关键字的函数把数据映射到表中的储存位置,这个映射函数叫做散列函数或者哈希函数,存放数据的数组就叫做散... -
哈希表之线性探测和二次探测
2020-02-29 17:58:35哈希表又称散列表。 哈希表存储的基本思想是:以数据表中的每个记录的关键字 k为自变量,通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个... -
【数据结构】哈希表(线性探测法)
2018-03-28 22:41:15哈希表是一种搜索结构,当数据量大时,哈希搜索的效率高,平均时间复杂度O(1)。 【哈希查找】: (1)在插入时,根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。 (2)在搜索时,对... -
【数据结构】哈希表的线性探测算法
2016-05-30 17:19:04构造哈希表常用的方法是:除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。HashKey= Key % P。直接定址法--取关键字的某个线性函数为散列地址HashKey= Key 或 HashKey= A*Key + BA、B为... -
DS哈希查找—线性探测再散列(附图文解析)
2020-12-23 17:33:58输入表长(大于、等于11),输入关键字集合,用线性探测再散列构建哈希表,并查找给定关键字。 –程序要求– 若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio 程序中若include多过... -
【数据结构】哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度
2021-04-12 14:08:57一、哈希表 1、概念 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,... -
搜索结构之哈希表--线性探测法
2019-08-14 23:54:41散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组... -
线性探测哈希表
2020-06-22 23:02:075.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并求出等概率查找时查找成功 的 ASL(成功) (1 分),...