# Part2:作业

• 作业1

11-散列1 电话聊天狂人（25 分）

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

13588625832 3

# -*- coding: utf-8 -*-
"""
Created on Mon May 21 20:01:38 2018

"""

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 15

Sample 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 分）

1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”；
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

• 作业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 21

Sample Output:
1 13 12 21 33 34 38 27 22 32

# -*- coding: utf-8 -*-
"""
Created on Mon May 21 21:52:59 2018

"""

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:

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:
print(ans.strip())