算法思想：
这道题也是做到哭:。
方法一：先是用数组A记录冲突数，①扫描一遍散列表，将冲突数为0的数放入数组B中，每输出B中一个最小数后将其H(key)相同的数的冲突数减1，然后重复①，这个方法是在手工模拟了大半个小时后摸出来的规律。然后测试点4最大N死活过不去，超时（全程暴力破解，不超时才怪）。
方法二：然后实在不行了，看了姥姥的解说，用拓扑排序，然而又不是普通的拓扑排序，按要求要从小到大的原则输入，②要在输出一个目前入度为0数组中最小值，然后将剩下所有入度为0的数再排序一次，再重复②，直至输出数等于输入中不是负数的个数。
题目和代码段在下方（仅供参考）：
中国大学MOOC-陈越、何钦铭-数据结构-2019春
11-散列4 Hashing - Hard Version (30 分)
Given a hash table of size N, we can define a hash function H(x)=x%N. 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.
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.
11
33 1 13 12 34 38 27 22 32 -1 21
Sample Output:
1 13 12 21 33 34 38 27 22 32
代码段1：
/***************2019.5.21-09:20-12:00**************/
//11-散列4 Hashing - Hard Version V1.0(最大N超时) 目测是暴力法超时
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct HashNode *Hash;
struct HashNode{
int key;
int H_key;
int Coll;//collision
};
int main(){
int i,j;
int N;
scanf("%d",&N);
Hash H=(Hash)malloc(N*sizeof(struct HashNode));
for(i=0;i<N;i++){
scanf("%d",&H[i].key);
H[i].H_key=H[i].key%N;
if(H[i].key>=0){
H[i].Coll=i-H[i].H_key;
if(H[i].Coll<0) H[i].Coll+=N;
}
else H[i].Coll=-1;
}
int k=0,In[N],Mark[N];
memset(Mark,0,sizeof(Mark));
for(j=0;j<N;j++){ //遍历散列表，将coll==0的加入In数组
if(H[j].Coll==0){
In[k]=H[j].key;
H[j].Coll=-1;
k++;
}
}
// printf("k=%d\n",k);
// for(i=0;i<k;i++) printf("k[%d]=%d\n",i,In[i]);
int l=0,cnt=0;
for(i=0;;i++){
if(k>l){
sort(In+l,In+k);
Mark[In[l]%N]=1;
l++;
}
cnt=0;
for(j=0;j<N;j++){ // 遍历散列表，将coll==0的加入In数组
if(Mark[H[j].H_key]==1){
H[j].Coll--;
if(H[j].Coll==0) {
In[k++]=H[j].key;
}
}
if(H[j].Coll<0) cnt++;
}
if(cnt==N) break;
}
for(i=0;i<k;i++){
printf("%d",In[i]);
if(i<k-1) printf(" ");
else printf("\n");
}
return 0;
}
代码段2：
/***************2019.5.21-09:20-12:00**************/
/***************2019.5.22-08:30-12:10 (V2.0)**************/
//11-散列4 Hashing - Hard Version V1.0(最大N超时) 目测是暴力法超时 V2.0改用拓扑排序，ok 共6h
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct LNode *List;
struct LNode{
int Index;
List Next;
};
struct GNode{
int Data;
int InD;
List First;
}G[1008];
bool cmp(int a,int b){
if(G[a].Data>G[b].Data) return 0;
else return 1;
}
int main(){
int i,j;
int N;
scanf("%d",&N);
int key,H_key,cnt=0;
for(i=0;i<N;i++) G[i].First=NULL;
for(i=0;i<N;i++){
scanf("%d",&key);
G[i].Data=key;
if(key>=0){
cnt++;
H_key=key%N;
G[i].InD=(i-H_key+N)%N;
if(G[i].InD>0){
for(j=H_key;j!=i;j=(j+1)%N){
List X=(List)malloc(sizeof(struct LNode));
X->Index=i;
X->Next=G[j].First;
G[j].First=X;
}
}
}
else G[i].InD=-1;
}
// for(i=0;i<N;i++){
// printf("%d->",G[i].Data);
// List X=G[i].First;
// while(X){
// printf("%d->",G[X->Index].Data);
// X=X->Next;
// }
// printf("\n");
// }
// printf("cnt=%d\n",cnt);
int In[cnt],k=0,l=0;
for(i=0;i<N;i++){
if(G[i].InD==0) In[k++]=i;
}
sort(In,In+k,cmp);//以防全部InD都是0的情况
int Pre_k=0;
while(k<cnt){
List X=G[In[l]].First;
l++;
while(X){
G[X->Index].InD--;
if(G[X->Index].InD==0) In[k++]=X->Index;
X=X->Next;
}
if(k>Pre_k){
sort(In+l,In+k,cmp);
Pre_k=k;
}
// printf("k=%d:",k);
// for(i=0;i<k;i++) printf("In[%d]=%d ",i,In[i]);
// printf("\n");
}
for(i=0;i<cnt;i++){
printf("%d",G[In[i]].Data);
if(i<cnt-1) printf(" ");
else printf("\n");
}
return 0;
}
