C语言编写哈希表实例

#include <stdio.h> 
#include <stdlib.h> 

typedef struct node{ 
int number; 
struct node *next; 
}Node; 

int main(void){ 
int i,first=1; 
Node *hash[1000]={NULL}; 
for(i=0;i<1000;i++){ 
int inp,fx; 
scanf("%d",&inp); 
fx=inp/10; 
if(hash[fx]==NULL){ 
hash[fx]=(Node *)malloc(sizeof(Node)); 
hash[fx]->number=inp; 
hash[fx]->next=NULL; 
}else if(hash[fx]->number>inp){ 
Node *temp; 
temp=(Node *)malloc(sizeof(Node)); 
temp->number=inp; 
temp->next=hash[fx]; 
hash[fx]=temp; 
}else{ 
Node *temp,*insert; 
for(temp=hash[fx]; temp->next!=NULL;temp=temp->next) 
if(temp->next->number>inp) 
break; 
insert=(Node *)malloc(sizeof(Node)); 
insert->number=inp; 
insert->next=temp->next; 
temp->next=insert; 
} 
} 

for(i=1;i<1000;i++){ 
Node *temp; 
for(temp=hash[i];temp!=NULL;temp=temp->next) 
if(first){ 
printf("%d",temp->number); 
first=0; 
}else 
printf(" %d",temp->number); 
} 
return 0; 
}

假设有1000个值小于10000的正整数，用构造散列表的方法将1000个正整数按由小到大的次序放入表中。（负载因子a=1）试写出你的排序算法。 
（显然散列中的数应被散列函数从小到大排列，换句话说，散列函数应是一个单调递增的函数。很容易想到f（x）=[x/10]+1，其中[x]表示不大于x的最大整数。此函数的值域为{x | x∈[1，1000]且x∈N+}，编程是为了方便起见，将函数改为f（x）=[x/10]以便操作，值域为{x | x∈[0，999]且x∈N+}。冲突采用拉链法来解决，每个链表中用插入排序法排序，最后按顺序输出。时间复杂度O（n）。）