#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef int datatype;typedef struct Node
{struct Node *next;datatype data;
}*Linklist;//创建节点
Linklist Create_node()
{Linklist p=(Linklist)malloc(sizeof(struct Node));if(NULL==p)return NULL;//初始化指针域p->next=NULL;//初始化数据域p->data=0;return p;
}//找到<=m的最大质数，m=待排列数的长度*4/3，返回下标
int prime_max(int m)
{for(int i=m;i>=2;m--){int flag=0;//sqrt(i)《====》根号ifor(int j=2;j<sqrt(i);j++){if(i%j==0){flag=1;break;}}if(flag==0)return i;}
}//哈希表的插入void hash_insert(int key,Linklist hash[],int m)
{int p=prime_max(m);int sub=key%p;Linklist head=hash[sub];//创建链表的头Linklist s=Create_node();//创建节点s->data=key;//判空if(NULL==head){head=s;hash[sub]=s;return;}//存在多个节点s->next=head;head=s;hash[sub]=head;//更新哈希表的头
}
//哈希表的输出
void show(Linklist hash[],int m)
{for(int i=0;i<m;i++){printf("%d: ",i);Linklist p=hash[i];//定义指针P指向哈希表的头while(p!=NULL) //遍历哈希表，输出链表数据域的数据{printf("%d ",p->data);p=p->next;}printf("NULL\n");}
}int main(int argc, const char *argv[])
{int arr[]={25,51,8,22,26,67,11,16,54,41};//将数据存入哈希表中int len=sizeof(arr)/sizeof(arr[0]);int m=len*4/3;Linklist hash[m];//定义指针数组for(int i=0;i<m;i++){hash[i]=NULL;//防止野指针}for(int i=0;i<m;i++)//将数组中的元素插入到哈希表中{hash_insert(arr[i],hash,m);}//输出show(hash,m);return 0;
}运行结果：
