题目是这样子的：

7-18 Hashing - Hard Version

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

没去看讲解前自己想的，大概想法是先把余数和位置的差为0的那些数按从小到大的顺序插进去，再把剩下的数一个个插进去。结果运行超时，而且在Insert_nonzero那里总是段错误，就写到博客里记下来了。

下面是代码：

//思路：先算出每个数除以表长的余数，余数一样的一起处理
//余数一样的，位置越靠后越晚输入
//余数和位置的差很重要！差组成部分应该是:余数相同且差比它小的(记作a)、a与它之间插入的一些... 
//输出方式不止一种的，输出那个最小的 
//最终思路：先将差值为0的从小到大插入链表，然后再将差值不为0的一个个插进去

#include<stdio.h>
#include<stdlib.h>
typedef struct Node *PtrToNode;
typedef PtrToNode List;
struct Node
{
	int Data;//存放数据 
	int Remainder;//每个数除以表长的余数
	int Difference;//位置减余数的差
	PtrToNode Next;//指向下一个结点 
};

//表排序
void TableSort(List HashTable,int Size,int Table_1[],int choice)//choice为1表示按data排序，为2表示按difference排序 
{
	int i,j,temp;
	 
	if(choice==1)//按Data从小到大排
	{
	    //给Table排序 
		for(i=1;i<Size;i++)
	    {
	    	temp=Table_1[i];
	    	for(j=i;j>0&&HashTable[temp].Data<HashTable[Table_1[j-1]].Data;j--)
	    	    Table_1[j]=Table_1[j-1];
	    	Table_1[j]=temp;
	    }
	}
	else if(choice==2)//按Difference从小到大排
	{
	    //给Table排序 
		for(i=1;i<Size;i++)
	    {
	    	temp=Table_1[i];
	    	for(j=i;j>0&&HashTable[temp].Difference<HashTable[Table_1[j-1]].Difference;j--)
	    	    Table_1[j]=Table_1[j-1];
	    	Table_1[j]=temp;	
	    }
	} 
}

void Insert_zero(List Output,List HashTable,int Table_1[],int Zero_Size)
{
	PtrToNode NewCell;
	int i; 
	
	//先把Difference为0的按Data从小到大排序 
	TableSort(HashTable,Zero_Size,Table_1,1);
	
	//插入 
	for(i=Zero_Size-1;i>=0;i--)
	{
		NewCell=(PtrToNode)malloc(sizeof(struct Node));
		NewCell->Data=HashTable[Table_1[i]].Data;
		NewCell->Difference=HashTable[Table_1[i]].Difference;
		NewCell->Remainder=HashTable[Table_1[i]].Remainder;
		//头插
		NewCell->Next=Output->Next;
		Output->Next=NewCell; 
	}
}

//difference已经从小到大排了，直接按顺序一个个插进去就好了 
void Insert_nonzero(List Output,List HashTable,int Table_1[],int Size)
{
	int i,j;
	PtrToNode P_Node=(PtrToNode)malloc(sizeof(struct Node));
	PtrToNode P_OutputNode=Output->Next;
	PtrToNode pre;//用来插入的辅助指针 
	for(i=0;i<Size;i++)
	{
		if(HashTable[Table_1[i]].Difference!=0)
		{
			//找到要插入的位置 
			while(P_OutputNode&&P_OutputNode->Remainder!=HashTable[Table_1[i]].Remainder)
		        P_OutputNode=P_OutputNode->Next;
		    pre=P_OutputNode; 
			j=HashTable[Table_1[i]].Difference-1;
			while(pre&&j>0)
			{
				pre=pre->Next;
				j--;
			}
			//插在pre后 
			HashTable[Table_1[i]].Next=(PtrToNode)malloc(sizeof(struct Node));
			HashTable[Table_1[i]].Next=pre->Next;
			*P_Node=HashTable[Table_1[i]];
			pre->Next=P_Node; 
		}
	}
}

void print_OutputList(List Output)
{
	PtrToNode p=Output->Next;
	while(p)
	{
		printf("%d",p->Data);
		if(p->Next!=NULL)
		    printf(" ");
	}
}


int main()
{
	int N;
	scanf("%d",&N);
	
	//把数据放进表里 
	List HashTable=(List)malloc(N*sizeof(struct Node));//用来存放各个数以及他们的位置和余数 
	int Data,Remainder,Difference;
	int Size=0;//Table的大小 
	int Zero_Size=0;//记录位置与余数差为0的个数 
	int i;
	for(i=0;i<N;i++)
	{
		scanf("%d",&Data);
		if(Data!=-1)
		{
			Size++;
			Remainder=Data%N;
			Difference=i-Remainder;
            if(Difference<0)
                Difference=Difference+N;
			if(Difference==0)
			    Zero_Size++;
			HashTable[Size-1].Data=Data;
			HashTable[Size-1].Difference=Difference;
			HashTable[Size-1].Remainder=Remainder;
		}
	}
	//按difference从小到大排，为后面插入difference非0的项做准备
	//Table_1为表排序对应的Table 
	int *Table_1=(int *)malloc((Size)*sizeof(int)); 
	//初始化Table
	for(i=0;i<Size;i++)
	    Table_1[i]=i;
	TableSort(HashTable,Size,Table_1,2); 
	
	//先将位置减余数的差为0的放进Output，并按Data从小到大排 
	List Output=(List)malloc(sizeof(struct Node));
    Output->Next=NULL;
	Insert_zero(Output,HashTable,Table_1,Zero_Size);
	
	//再把位置减余数的差不为0的插进去
	Insert_nonzero(Output,HashTable,Table_1,Size);
	
	//输出
	print_OutputList(Output);
	
	return 0; 
}