本文主要是介绍算法笔记读书思考---散列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
散列
所谓散列,就是元素通过一个函数转化为整数,使得该整数可以尽量唯一地代表这个元素。我们可以把这个转化函数记为:H(),把这个元素记为key,那么这个元素转化后的整数为H(key)。
常用的散列函数有直接定址法,平方取中法,除留取余法等方法。今天我想着重讨论的是直接定址法,这是散列函数中我认为最常用,也是最实用,建议大家掌握。
直接定址法其实就是指的数恒等变换即H(key) = key,这个在实际问题中经常会用到,说得直白一点我们在对数组进行处理时,有时会把这个元素(key)当做数组的下标,而这个操作就是我们的直接定址法。
下面有几个很经典的例子来展现我们的直接定址法的作用
1.如果让你输入10以内的10个数,并把它们从小到大进行排序,你会怎么做?
很多人估计会想到冒泡排序,交换排序等很多排序,甚至会直接使用STL里面的sort函数。但是今天我想用的就是以我们直接定址法为核心的排序方法–桶排序(在书上和网站都这么称呼这种排序),直接见代码:
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
int a[15];
int t;
//先数组全部置为0
memset(a,0,sizeof(a));for(int i = 0;i<10;i++){scanf("%d",&t);//这里可以理解为H(t) = t,这个H(t)就是我们数组的下标.a[t]++;
}
//循环遍历0-10这10个下标
for(int i = 0;i<=10;i++){//打印数组中每个元素,如果有相同的元素,就打印多次for(int j = 1;j<=a[i];j++){printf("%d ",i);}
}
return 0;
}
2.求素数的埃氏筛法也用到了散列的思想
当我们要求2-n以内有多少个素数的时候,就可以使用埃氏筛法
#include<bits/stdc++.h>
using namespace std;
const int maxn = 202;
int a[maxn];
bool p[maxn]={false};
int main(){
int n;
while(scanf("%d",&n)!=EOF){int index = 0;for(int i = 2;i<=n;i++){if(p[i]==false){//我们这里直接将下标i当做素数本身存入素数数组中,也是H(key) = key的思想a[index++] = i;}for(int j = i+i;j<=n;j+=i){p[j] = true;}}for(int i = 0;i<index;i++){printf("%d ",a[i]);}
}
return 0;
}
散列对查询类问题也有奇效,我们通过散列可以唯一地标志一些元素,当程序拿到散列值的时候,可以通过散列值来判断该元素出现了几次。
下面有两个小问题:
1.当给你n个数,再给你m个数,让你判断这m个数在n个数中出现了几次。
思路:这是一个很简单的散列查询问题,我们直接使用H(key)= key就可以做出来。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int hashtable[maxn]={0};
int main(){
int n,m,x;
//进行填数
while(scanf("%d %d",&n,&m)!=EOF){for(int i = 0;i<n;i++){scanf("%d",&x);//对x出现了几次进行计数hashtable[x]++;
}
for(int i = 0;i<m;i++){scanf("%d",&x);//直接打印次数printf("%d\n",hashtable[x]);
}
}
return 0;
}
2.当给你n个字符串,它们分别是有四个大写字母所组成,再给你m个查询的字符串,判断这些字符串在n个字符串中出现了几次。
思路:这个题可以两种思路,实际上也就是我们对散列表达式的选择,第一种我们也还是可以选择H(key) = key来算出这道题;第二种我这里引用胡凡算法笔记中的散列表达式H(P) = x*Range + y, 因为这里规定了是大写字母,所以这个Range的值为26(A-Z共有26个大写字母),每个字符串我们可以通过散列表达式得到一个唯一的值来标志它。我们以id来表示散列值,那么id = idx26+(字符串中的每个字母)-‘A’,那么算出的这个id值就是唯一代表这个字符串的散列值。
1.H(key) = key的做法
#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
//二维数组来装n个字符串
char a[maxn][6];
//散列数组来计数
int hashTable[maxn];
int main(){
int n,m;
int index = 0;
//这里我使用了string声明的字符串方便后续进行比较
string s;
cin>>n>>m;
//输入n个字符串
for(int i = 0;i<n;i++){cin>>a[i];
}
//在输入m个查询字符串,边输入边比较
for(int i = 0;i<m;i++){cin>>s;//遍历字符a数组,进行比较for(int j = 0;j<n;j++){if(s==a[j]){hashTable[index]++;}}//计数数组脚标增加,把一种字符串出现的次数记录完毕index++;
}
//输出打印计数数组
for(int i = 0;i<index;i++){cout<<hashTable[i]<<" ";
}return 0;
}
2.H(P) = x*Range + y的做法
我们先写一个函数hashFunc专门来计算并返回我们字符串的散列值, 它有两个参数s[]和len(分别指的是我们要得到字符数组每个字母和字符数组的长度)
该函数代码如下:
nt hashFunc(char s[],int len){int id = 0;for(int i = 0;i<len;i++){id = id * 26+(s[i]-'A');}return id;
}
完整源码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
char s[maxn][5],temp[8];
//因为这里有四个大写字母,所以考虑到4个26连乘,将数组的大小设置为26*26*26*26
int hashTable[26*26*26*26+10];
int hashFunc(char s[],int len){int id = 0;for(int i = 0;i<len;i++){id = id * 26+(s[i]-'A');}return id;
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){for(int i = 0;i<n;i++){scanf("%s",s[i]);int id = hashFunc(s[i],4);//对应的计数为加1hashTable[id]++;}//直接打印输出for(int i = 0;i<m;i++){scanf("%s",temp);int id = hashFunc(temp,4);printf("%d\n",hashTable[id]);}}
return 0;
}
今天的讨论就到这里,感觉最近的动力不是很足。
这篇关于算法笔记读书思考---散列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!