《数据结构》11-散列4 Hashing - Hard Version

旧城等待， 2022-04-14 06:58 255阅读 0赞

# 题目 #

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

# 分析 #

题目大意：从已经确定的散列表中（解决冲突的方法是“线性探测”），找出输入序列

大体思路是把数与数的关系抽象成一张有向图，再用拓扑排序输出

由例子可以看出，比如 1%11 = 1，12%11 = 1，但是 12 排在 1 的后面存储，说明肯定 1 比 12 先输入，而根据线性探测，12 就该存在第二个位置，而现在第二个位置是 13，说明 13 也肯定比 12 先输入，即**只有 1 和 13 输入后 12 才能输入**，…， 由此可以建立一张有向图，只有前面的结点输入后，后面的结点才能被输入

再进行拓扑排序，要求按从小到大输出，所以用到了STL的最小堆，但是最小堆存的只是值，还要根据值找回下标，又用到了STL的map

#include<queue>
    #include<iostream>
    #include<vector>
    #include<map>
    #define INF -100000
    #define MaxVertex 1005
    int G[MaxVertex][MaxVertex];
    int Indegree[MaxVertex];  // 入度 
    int value[MaxVertex];  // 存值 
    int N;  // 总值
    using namespace std;
    priority_queue<int,vector<int>,greater<int> > q;   // 定义最小堆 
    map<int,int> m;
    
    // 插入边 
    void Insert(){
        
    	for(int i=0;i<N;i++){
         
    		if(0 <= value[i]){
        
    			m.insert(pair<int,int>(value[i],i));   // 存下标与值的映射关系 
    			int remainder = value[i]%N;  // 余数 
    			if(remainder==i)
    				Indegree[i] = 0;
    			else if(remainder != i){
        
    				Indegree[i] = (i - remainder < 0)?(i - remainder + N):(i - remainder);
    				for(int j=remainder;j!=i;j=(j+1)%N)
    					G[j][i] = 1;
    			}
    		}
    	}
    }
    
    // 初始化图 
    void build(){
        
    	for(int i=0;i<N;i++)
    		for(int j=0;j<N;j++)
    			G[i][j] = INF;
    	Insert();
    }
    
    // 拓扑排序 
    void TopSort(){
        
    	for(int i=0;i<N;i++)
    		if(!Indegree[i] && 0 < value[i])
    			q.push(value[i]);
    	bool flag = true;
    	while(!q.empty()){
        
    		int tmpValue = q.top(); 
    		int v = m[tmpValue];  // 找回下标 
    		q.pop();
    		if(flag)
    			flag = false;
    		else
    			cout<<" ";
    		cout<<tmpValue;
    		for(int w=0;w<N;w++)
    			if(G[v][w]!=INF){
          // 如果连通 
    				if(--Indegree[w]==0)
    					q.push(value[w]);
    			}
    	}
    }
    
    
    int main(){
        
    	cin>>N;
    	int i=0;
    	for(int i=0;i<N;i++)
    		cin>>value[i];
    	build();
    
    	TopSort();
    	return 0;
    }