浙大数据结构Week11
课程地址：https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。
这周是最后一周，内容为散列表，下面回顾下。
Part1:回顾
1.散列表
如果我们有一组数据，这组数据不方便比较大小，那么如何高效地查找其中的元素呢？这就有了散列表。
散列表的基本思想就是构造一个映射h，将需要查找的元素映射到一个值上，这个值就是数组存储的地址。但是不同的关键字可能会映射到同一个地址，这就有了冲突，如何解决冲突是我们需要关心的问题。
从散列函数的定义我们可以看出，散列函数应该构造简单，并且尽量减少冲突，老师的课件中介绍了很多种处理方法，这里不一一列出了。下面着重介绍冲突处理方法。
2.冲突处理方法
这里老师其是就介绍了两种冲突处理方法，第一种是遇到冲突就换一个位置，第二种是把冲突的对象组织在一起。第一种被称为开放地址法，第二种被称为链地址法。
开放地址法
下面分别看下
线性探测法
简单来说线性探测法就是在冲突的时候不停地右移，如果到底则从头开始，直至找到一个空的位置。
我们从下图看下具体的过程。
我们来分析下散列表的性能，这里分别计算成功平均查找长度(ASLs)以及不成功平均查找长度 (ASLu)。这里散列函数为h(key) = key mod 11。
先看下ASLs。对于key=11，H(key)=0，0位置上的元素就是11，因此对于11需要找1次；对于key=30，H(key)=8,8位置上的元素为29，不是30，接着右移，移动6次后发现找到了30。经过这个过程，我们发现查找散列表中元素的次数为元素冲突次数加1。
再来看下ASLu，显然这种情况没法穷举，一般要将关键词分类，这里直接根据H(key)分类即可。对于H(key)为0的不在表内的元素，位置0，不在表内，右移，依旧不在表内，继续右移，这时候结束了，因为这个位置上没有元素。所以H(key)为0的情形需要找3次来确定不在表内，同理可以计算其余情况。
平方探测法
我们知道线性探测法最后一定能填满整个空间，那么平方探测法是否可以呢？事实上有以下结论：
这是个数论的内容，先略过了。
双散列探测法
简单来说就是构造一个复合函数。
再散列
如果一个散列表几乎是满的，那么它大概率有很多次冲突，这时候就需要我们加倍扩大散列表了，这个过程就叫“再散列”。
分离链接法
分离链接法就是把冲突的元素串在一起构成链表，具体过程如下所示。
3.性能分析
这里老师给了期望探测次数关于装填因子的公式，不一一列出了，留个坑，以后抽空补上证明，简单来说装填因子越大，期望探测次数量越多。
最后老师给出以下总结：
Part2:作业
- 作业1
11-散列1 电话聊天狂人（25 分）
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。输入格式:
输入首先给出正整数N（≤100000），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。输入样例:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832输出样例:
13588625832 3
因为我是用python做的，用自带的字典就可以很方便的解决。
# -*- coding: utf-8 -*-
"""
Created on Mon May 21 20:01:38 2018
@author: Administrator
"""
n=int(raw_input())
dic={}
#读入数据
for i in range(n):
a,b=map(int,raw_input().strip().split())
if a in dic:
dic[a]+=1
else:
dic[a]=1
if b in dic:
dic[b]+=1
else:
dic[b]=1
'''
dic={13005711862L: 1,
13088625832L: 1,
13505711862L: 1,
13588625832L: 3,
15005713862L: 1,
18087925832L: 1}
'''
#找到打电话的最多次数
m=max(dic.values())
#记录最小的电话号码
phone=20000000000
num=0
#遍历字典，找到最小的电话号码
for i in dic.keys():
if dic[i]==m:
num+=1
if i<phone:
phone=i
#key=dic.keys()[dic.values().index(m)]
if num>1:
print(str(phone)+" "+str(m)+" "+str(num))
else:
print(str(phone)+" "+str(m))- 作业2
11-散列2 Hashing（25 分）
The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.Input Specification:
Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (≤10000) and N (≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.Output Specification:
For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-“ instead.Sample Input:
4 4
10 6 4 15Sample Output:
0 1 4 -
这题没啥好说的，直接把数据插入散列函数即可。
#include <stdio.h>
int isPrime(int x){
if (x==1){
return 0;
}else if(x==2){
return 1;
}else if(x%2==0){
return 0;
}else{
for(int i=2;i<x;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
}
int main(){
int m,n;
scanf("%d %d",&m,&n);
while(isPrime(m)==0){
m++;
}
int c[m]={0};
//读入数据
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
//开始处理数据
for(int i=0;i<n;i++){
int r=a[i]%m;
//printf("%d %d\t",r,b[r]);
if(c[r]==0){
printf("%d",r);
c[r]=1;
}else{
int tmp=r;
int flag=0;
for(int j=1;j<m;j++){
tmp=(r+j*j)%m;
if(c[tmp]==0){
c[tmp]=1;
flag=1;
printf("%d",tmp);
break;
}
}
if(flag==0){
printf("-");
}
}
if(i<n-1){
printf(" ");
}
}
return 0;
}- 作业3
11-散列3 QQ帐户的申请与登陆（25 分）
实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。输入格式:
输入首先给出一个正整数N（≤100000），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。输出格式:
针对每条指令，给出相应的信息：
1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”；
3）若老帐户登陆成功，则输出“Login: OK”；
4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”；
5）若老帐户密码错误，则输出“ERROR: Wrong PW”。输入样例:
5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com输出样例:
ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK
直接利用python的字典来做，非常的简单，其实如果第一次做还是建议用更底层的语言，那样才能起到学习的效果。
- 作业4
11-散列4 Hashing - Hard Version（30 分）
Given a hash table of size N, we can define a hash function . Suppose that the linear probing is used to solve collisions, we can easily obtain the status of the hash table with a given sequence of input numbers.
However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), which is the size of the hash table. The next line contains N integers, separated by a space. A negative integer represents an empty cell in the hash table. It is guaranteed that all the non-negative integers are distinct in the table.Output Specification:
For each test case, print a line that contains the input sequence, with the numbers separated by a space. Notice that there must be no extra space at the end of each line.Sample Input:
11
33 1 13 12 34 38 27 22 32 -1 21Sample Output:
1 13 12 21 33 34 38 27 22 32
这题一开始没做出来，看了老师的讲解才做出来的。题目是给出散列映射的结果，让我们反求输入的顺序，这里要抓住一个根本特点：如果x被映射到H(x)上，这个位置上一定有y了，那么y一定在x之前输入，实际上假设x最终位置之前一位的元素为z，那么y到z之间的元素都在x之前被输入，这样有明显递进关系的点就可以使用我们之前学过的拓扑排序了，每次抛出入度为0的点，这里的入度为x之前的点的数量，可以通过刚才所说的方式计算，注意这里为了唯一性，如果有多个入度为0的点，直接抛出值最小的点。
# -*- coding: utf-8 -*-
"""
Created on Mon May 21 21:52:59 2018
@author: Administrator
"""
n=int(raw_input().strip())
m=map(int,raw_input().strip().split(" "))
#记录指向每个边的点
l={}
for i in m:
if i>0:
l[i]=[]
#计算入度
count=0
for i in range(n):
x=m[i]
if(x>0):
count+=1
r=x%n
if(i>r):
for j in range(r,i):
if(m[j]>0):
l[x].append(m[j])
elif(i<r):
for j in range(i):
if(m[j]>0):
l[x].append(m[j])
for j in range(r,n):
if(m[j]>0):
l[x].append(m[j])
#记录入度为0的点
s=set()
for i in l:
if(len(l[i]))==0:
s.add(i)
ans=""
for k in range(count):
small=min(s)
ans+=str(small)+" "
s.remove(small)
for i in l:
if small in l[i]:
l[i].remove(small)
if len(l[i])==0:
s.add(i)
print(ans.strip())