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 (≤), 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
#include<stdlib.h>
#include<stdio.h>
typedef struct Nodes {
int number;
struct Nodes *next;
}*QNode,Node;
typedef struct N {
int count;
struct Nodes *next;
}*Ns, Nd;
int main()
{
int number;
scanf("%d", &number);
Ns n = (Ns)malloc(sizeof(Nd)*number);
//Nd n[11];
for (int i = 0; i < number; i++)
{
n[i].count = 0;
n[i].next = NULL;
}
int a[1001];
for (int i = 0; i < number; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i < number; i++)
{
if (a[i] >= 0) {
if (a[i] % number == i) {
}
else {
int j = i;
while (j != a[i] % number)
{
j = (j + number - 1) % number;
QNode qn = (QNode)malloc(sizeof(Node));
qn->next = n[i].next;
qn->number = a[j];
n[i].next = qn;
n[i].count++;
}
}
}
}
int cnt = number;
while (cnt)
{
int min = 100000;
int temp = 0;
for (int i = 0; i < number; i++)
{
if (n[i].count == 0 && a[i] < min) {
min = a[i];
temp = i;
}
}
n[temp].count--;
cnt--;
if (min >= 0) {
printf("%d", min);
if (cnt != 0)printf(" ");
}
for (int i = 0; i < number; i++)
{
if (n[i].count > 0) {
QNode q = n[i].next;
while (q!=NULL)
{
if (q->number == min) { n[i].count--; break; }
q = q->next;
}
}
}
}
system("pause");
return 0;
}