第十一周：散列查找 & KMP
题目集总目录 学习指路博客 数据结构学习笔记＜9＞ 散列查找
11-散列1 电话聊天狂人 (25分)
一定要做。如果不知道怎么下手，可以看“小白专场”，将详细给出C语言实现的方法
思路
散列查找，插入的时候若键值已存在改改操作就好，直接用之前的模板
代码
#include <iostream>
#include <cmath>
#include <utility>
using namespace std;
const int MaxSize = 100000;
typedef int Index;//散列后的下标
//散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素
typedef enum {Legitimate, Empty, Deleted} EntryType;
struct Person {
string str;
int num;
bool operator!=(const Person& p) {
return str != p.str;
}
} per;
typedef Person DataType;//数据的类型
struct HashNode { //散列表单元类型
DataType data; //存放元素
EntryType flag; //单元状态
};
struct HashTable { //散列表类型
int TableSize; //表长
HashNode *Units; //存放散列单元的数组
};
typedef HashTable *ptrHash;
//返回大于N且不超过MaxSize的最小素数，用于保证散列表的最大长度为素数
int NextPrime(int N) {
int i, p = (N%2) ? N+2 : N+1;//从大于N的下一个奇数p开始
while(p <= MaxSize) {
for(i = (int)sqrt(p); i > 2; i--)
if(!(p %i)) break;//不是素数
if(i == 2) break;//for正常结束，是素数
else p += 2;//试探下一个奇数
}
return p;
}
//创建一个长度大于TableSize的空表。（确保素数）
ptrHash CreateTable(int TableSize) {
ptrHash H;
int i;
H = new HashTable;
H->TableSize = NextPrime(TableSize);
H->Units = new HashNode[H->TableSize];
for(int i = 0; i < H->TableSize; ++i)
H->Units[i].flag = Empty;
return H;
}
//返回经散列函数计算后的下标
Index Hash(DataType Key, int TableSize) {
unsigned int h = 0; //散列函数值，初始化为0
string str = Key.str;
int len = str.length();
for(int i = 0; i < len; ++i)
h = (h << 5) + str[i];
return h % TableSize;
}
//查找Key元素,这里采用平方探测法处理冲突
Index Find(ptrHash H, DataType Key) {
Index nowp, newp;
int Cnum = 0;//记录冲突次数
newp = nowp = Hash(Key, H->TableSize);
//若该位置的单元非空且不是要找的元素时发生冲突
while(H->Units[newp].flag != Empty && H->Units[newp].data != Key) {
++Cnum;//冲突增加一次
if(++Cnum % 2) {
newp = nowp + (Cnum+1)*(Cnum+1)/4;//增量为+i^2,i为(Cnum+1)/2
if(newp >= H->TableSize)
newp = newp % H->TableSize;
} else {
newp = nowp - Cnum*Cnum/4;//增量为-i^2,i为Cnum/2
while(newp < 0)
newp += H->TableSize;
}
}
return newp;//返回位置，该位置若为一个空单元的位置则表示找不到
}
//插入Key到表中
bool Insert(ptrHash H, DataType Key) {
Index p = Find(H, Key);
if(H->Units[p].flag != Legitimate) {
H->Units[p].flag = Legitimate;
Key.num = 1;
H->Units[p].data = Key;
return true;
} else {//该键值已存在
H->Units[p].data.num++;
return false;
}
}
int main() {
int N;
cin >> N;
N *= 2;
ptrHash H = CreateTable(N+1);
for(int i = 0; i < N; ++i) {
cin >> per.str;
Insert(H, per);
}
string minstr;
int maxnum = 0;
int sum = 0;
for(int i = 0; i < H->TableSize; ++i) {
HashNode h = H->Units[i];
if(h.flag != Legitimate) continue;
if(h.data.num > maxnum) {//有更狂的
sum = 1;
minstr = H->Units[i].data.str;
maxnum = H->Units[i].data.num;
} else if(h.data.num == maxnum) {
sum++;
if(h.data.str < minstr) minstr = h.data.str;
}
}
if(sum == 1) {
cout << minstr << ' ' << maxnum << endl;
} else cout << minstr << ' ' << maxnum << ' ' << sum << endl;
return 0;
}测试点
11-散列2 Hashing (25分)
2014年考研上机复试真题，比较直白，一定要做；
思路
有几个坑，1不算素数，如果M为1的话要特判。这题因为没有删除操作直接输出下标，所以只要维护一个数组标记是否存过数。
代码
测试点
11-散列3 QQ帐户的申请与登陆 (25分)
数据结构教材中的练习题，可以用散列，也可以用排序，有兴趣+有时间的，建议两种都试一下。选做；
题目大意
实现QQ新帐户申请和老帐户登陆的简化版功能。主要就是判断账号存在与否以及密码是否对应
思路
一开始用常规散列查找，移位法和平方探测法后两个样例一直错误，于是改成了用STL中map来替代…
代码
用STL中的map做的话，非常简洁
测试点
11-散列4 Hashing - Hard Version (30分)
很好玩的一道题哦，需要思考一下，想通了就很容易 —— 于是有时间就想想吧~ 实在想不通也没关系，下周习题课会讲的。
题目大意
已知散列函数H(x) = x%N 以及用线性探测法解决冲突问题
先给出散列映射的结果，反求输入顺序
当元素x被映射到H(x)位置后，发现这个位置已经有y了，则y一定是在x之前被输入的
思路
拓扑排序！其实是将散列映射和拓扑排序融合在了一起~
代码
注意有个坑，入度都为0即不确定谁先输出时，挑最小的输出，所以这里用优先队列代替小顶堆来存，并用map记录对应下标~
测试点
Kmp 串的模式匹配 (25分)
大家可以把找来的各种模式匹配算法都在这里测试一下，看看效果如何。
思路
没啥好说的，KMP就完事了
代码
测试点
最后更新于
这有帮助吗？