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.
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我有话要说：原先一头雾水，看了姥姥在慕课上的习题选讲，总算有了头绪，原来是拓扑排序啊！
首先，咱得把每个数对应的入度（Indegree）求出来，方法是在线性探测的模拟中循环求出，算法详见函数Find()，如此拓扑排序才有依据；其次，就是拓扑排序时，如何查找 数 ，不才的方法是用结构体数组，按照数据输入的顺序，存放 数，查找 数时，直接用下标pos检索,即 Nums[pos].num; 还有就是， 数 入队之后，它的入度得有标记，所以我将Indegree置为 -1， 防止重复入队。好了，就说这么多了，虽然我的代码，不是很完美、简洁，but i have tried and i am on my way to improvement! 谢谢观赏！ 手动狗头！
代码如下：
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 65535
struct NumNode{
int num; // 数值
int Pos; // 位置
int Indegree; //入度
}Nums[1001];
int n;
int res[1001];
int G[1001][1001]={
{0}};
queue<struct NumNode> Q;
int hasNeg=0;
void BuildGraph(){
cin>>n;
//先读取哈希表的元素值
for(int i=0;i<n;i++){
cin>>res[i];
Nums[i].num=res[i];
Nums[i].Pos=i;
Nums[i].Indegree=0;
if(res[i]==-1){
hasNeg++;
}
}
}
int Hash(int Key,int Size){
return Key%Size;
}
void Find(struct NumNode Key,int Size){
// cout<<"start to Find"<<endl;
int NewPos,CurrentPos;
int CNum=0;
NewPos=CurrentPos=Hash(Key.num,Size);
while( NewPos!=Key.Pos ){
NewPos=CurrentPos+CNum; // 线性探测
while(NewPos>=Size){
NewPos-=Size;
}
if( NewPos!=Key.Pos ){
CNum++;
G[NewPos][Key.Pos]=1;
Nums[Key.Pos].Indegree++;
}
}
// cout<<"Find is over"<<endl;
}
void DataComp(){
for(int i=0;i<n;i++){
if(Nums[i].num!=-1)
Find(Nums[i],n);
}
}
void Check(){
for(int i=0;i<n;i++){
if(Nums[i].num!=-1){
cout<<"num: "<<Nums[i].num<<" pos:"<<Nums[i].Pos<<" Indegree:"<<Nums[i].Indegree<<endl;
}
}
}
struct NumNode FindMinZeroIdg(){
int pos=-1;
int thismin=INF;
for(int i=0;i<n;i++){
if(Nums[i].Indegree==0 && Nums[i].num!=-1){ // 找num值最小 且入度为0 的Num结点
if(Nums[i].num<thismin){
thismin=Nums[i].num;
pos=i;
}
}
}
//Nums[pos].Indegree=-1;
return Nums[pos];
}
void TopSort(){
struct NumNode Tmp=FindMinZeroIdg();
Tmp.Indegree=-1;
Q.push( Tmp );
int flag=0;
while(!Q.empty()){
int V=Q.front().Pos;
Q.pop();
Nums[V].Indegree=-1;
if(flag){
cout<<" ";
}
flag++;
cout<<Nums[V].num;
for(int W=0;W<n;W++){
if(G[V][W]==1 ){
--Nums[W].Indegree;
}
}
Tmp=FindMinZeroIdg();
if( Tmp.Indegree==0){
Q.push( Tmp );
Tmp.Indegree=-1;
}
if(flag==n-hasNeg){
break;
}
}
}
int main(int argc, char** argv) {
BuildGraph();
DataComp();
// Check();
TopSort();
return 0;
}