C語言簡單的建立哈希表

一個課程設計，記錄一下QAQ

整個程式我使用while（1）循環來確定每次調用功能後回到首頁面，使用結構體将key和value關聯，采用指針實作動态記憶體配置設定。通過先構造資料表儲存資料，在資料表中進行插入、删除，再通過哈希函數構造哈希表，保證了哈希表的穩定性

//輸入為不重複的關鍵字，插入同理
//可由插入删除的順序變化來改變哈希表
#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#define NULL 0
typedef int KeyType;//起别名，友善辨識
typedef struct{
	KeyType key;
	char value;
}Table;

int Haxi(KeyType key,int length)//利用除留餘數法構造哈希函數
{
	int i,p,flag;
	for(p=length;p>=2;p--)//不超過表長的最大素數
	{
		for(i=2,flag=1;i<=p/2&&flag;i++)//通過不斷的除來判斷
		{
			if(p%i==0)
				flag=0;//不是則終止此循環
		}
		if(flag==1)
			break;//是的話終止循環
	}
	return key%p;//哈希位址
}

void Datatable(Table **ST,int n,int length)//儲存輸入的資料
{
	int i;
	(*ST)=(Table*)malloc(length*sizeof(Table));//動态配置設定記憶體的起始位址,和表長大小一樣，為了後面插入友善
	printf("\n 請輸入 %d 個資料: ",n);
	for(i=0;i<n;i++)
	{
		printf("\n第%d個:  (鍵 空格 值)",i+1);
		fflush(stdin);/*清除輸入緩沖區*/
		scanf("%d %c",&((*ST)[i].key),&((*ST)[i].value));
	}
}

void Haxitable(Table **HAXI,Table *ST,int n,int length)//建立哈希表
{
	int i,j;
	(*HAXI)=(Table*)malloc(length*sizeof(Table));
	for(i=0;i<length;i++)
	{
		(*HAXI)[i].key=NULL;//初始化
		(*HAXI)[i].value=0;
	}
	for(i=0;i<n;i++)
	{
		j=Haxi(ST[i].key,length);//獲得哈希位址
		while((*HAXI)[j].key!=NULL)//利用線性探測再散列解決沖突
			j=(j+1)%length;
		(*HAXI)[j].key=ST[i].key;//将資料放入哈希表
		(*HAXI)[j].value=ST[i].value;
	}
//	for(i=0;i<n;i++)
//		printf("資料庫第%d個是%d\n",i,ST[i].key);//驗證思路
	printf("\n哈希表制作完成\n");
}

void Show(Table *HAXI,int length)
{
	int i;
	printf("\n          ****************哈希表**************\n");
	printf("鍵:       *****");
	for(i=0;i<length;i++)
		printf("%6d",HAXI[i].key);
	printf("\n");
	printf("值:       *****");
	for(i=0;i<length;i++)
		printf("%6c",HAXI[i].value);
	printf("\n");
	printf("位址:     *****");
	for(i=0;i<length;i++)
		printf("%6d",i);
	printf("\n");
}		
int Search(Table *HAXI,KeyType key,int length)//查找方法
{
	int i;
	i=Haxi(key,length);//哈希函數獲得位置
	while(HAXI[i].key!=0&&HAXI[i].key!=key)
	{
		i=(i+1)%length;//利用構造時解決沖突的方法解決沖突
	}
	if(HAXI[i].key==0)
		return -1;
		else
			return i;
}

void Insert(Table **ST,KeyType key,int n,char value)//插入方法
{

	(*ST)[n].key=key;//直接在目前資料表後添加資料
	(*ST)[n].value=value;
}

int Delete(KeyType key,Table **ST,int n)//删除方法
{
	int i;
	for(i=0;i<n;i++)
	{
		if((*ST)[i].key==key)//找到需要删除的關鍵字
		{
			for(i;i<n-1;i++)
			{
				(*ST)[i].key=(*ST)[i+1].key;//數組的删除，需要移動
				(*ST)[i].value=(*ST)[i+1].value;
			}
			(*ST)[n-1].key=0;//讓最後一個資料為0
			(*ST)[n-1].value=0;
			break;//跳出循環
		}
		if((*ST)[i].key!=key&&i==n-1)
			return -1;
	}
	return 1;
}

void main()
{
	Table *ST,*HAXI;
	KeyType key;
	int n,length;
	int number,i;
	char value;
	printf("歡迎進行哈希表的制作，請進行選擇:\n");
	while(1)
	{
		printf("\n1  建立哈希表\n");
		printf("2  顯示哈希表\n");
		printf("3  查找元素\n");
		printf("4  插入元素\n");
		printf("5  删除元素\n");
		printf("6  退出\n");
		printf("請輸入你的選擇：");
		scanf("%d",&number);
		switch(number)
		{
		case 1:
			do
			{
				printf("\n 請輸入關鍵字個數和表長（個數,表長 且<=）：");
				scanf("%d,%d",&n,&length);
			}
			while(n>length);
			Datatable(&ST,n,length);
			Haxitable(&HAXI,ST,n,length);
			break;
		case 2:
			Show(HAXI,length);
			break;
		case 3:
			printf("請輸入想要查找的關鍵字：");
			scanf("%d",&key);
			if(Search(HAXI,key,length)==-1)
				printf("未查詢到");
				else
				printf("查找成功！位置是%d值為%c",Search(HAXI,key,length),HAXI[Search(HAXI,key,length)].value);
			break;
		case 4:
			if(n>=length)//判斷是否滿
				printf("哈希表已滿，不可插入！");
				else
				{
					printf("請輸入想要插入的關鍵字和值：");
					scanf("%d %c",&key,&value);
					Insert(&ST,key,n,value);
					n++;//資料需要加一再建立哈希表
					Haxitable(&HAXI,ST,n,length);
					printf("插入成功！目前有%d個資料,表長為%d ",n,length);
				}
			break;
		case 5:
			if(n==0)//判斷是否滿
				printf("哈希表為空，不可删除！");
			else
			{
			printf("請輸入想要删除的關鍵字：");
			scanf("%d",&key);
			if(Delete(key,&ST,n)==-1)//沒有找到則删除失敗
				printf("删除失敗");
			else
			{
				n--;
				Haxitable(&HAXI,ST,n,length);
				printf("删除成功！目前有%d個資料,表長為%d ",n,length);
			}
			}
			break;
		case 6:
			printf("謝謝使用！");
			exit(0);
		default :
			printf("輸入錯誤\n");
		}
	}

}
           

該程式可以對一定範圍内輸入正确執行：關鍵字大于0且不重複。對輸入資料大于表長、對空表進行删除、對滿表進行插入有正确反應，對輸入關鍵字為負數所産生的哈希位址為0(原因？)，對重複的關鍵字按輸入順序删除，對重複的關鍵字按輸入順序查找，對大約2000000000個資料内可以正常輸入。

肯定有很多不足

謝謝