#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#define NULLKEY -1//单元为空
#define DELKEY -2//单元内容被删除
#define M 20
typedef struct
{
	int key;//关键字
	int count;//统计哈希冲突探测次数
}HashTable;
//插入到哈希表
void InsertHT(HashTable ha[], int* n, int m,int p,int key)//n为哈希表的元素个数，m为哈希表的表长总数
{
	int i, adr;
	adr = key % p;//获得插入的哈希地址
	if (ha[adr].key == NULLKEY || ha[adr].key == DELKEY)
	{
		ha[adr].key = key;
		ha[adr].count = 1;
	}
	else
	{
		i = 1;
		do
		{
			adr = (adr + 1) % m;
			i++;
		} while (ha[adr].key != NULLKEY && ha[adr].key != DELKEY);
		ha[adr].key = key;
		ha[adr].count = i;
	}
	n++;//哈希表的元素个数
}
//创建哈希表
void CreateHT(HashTable ha[], int* n, int m, int p, int keys[],int n1)
{
	int i;
	//初始化哈希表内容
	for (int i = 0; i < m; i++)
	{
		ha[i].key = NULLKEY;
		ha[i].count = 0;
	}
	n = 0;//统计插入的个数
	for (i = 0; i < n1; i++)
	{
		InsertHT(ha, n, m, p, keys[i]);
	}
	printf("哈希表如下:\n");
	for (int j = 0; j < m; j++)
	{
		printf("%d  比较次数 %d\n", ha[j].key,ha[j].count);
	}
	printf("\n");
}
//查找哈希表
int SearchHT(HashTable ha[],int p,int m,int n1,int key)
{
	int i, Hi;
	int HO = key % p;//求出key的哈希地址
	if (ha[HO].key == NULLKEY)
	{
		ha->count = 1;
		return -1;
	}
	else if (ha[HO].key == key)
	{
		ha->count = 1;
		return HO;
	}
	else
	{
		ha->count = 1;
		for (i = 1; i <= n1; i++)
		{
			Hi = (HO + i) % m;
			if (ha[Hi].key == NULLKEY)
			{
				ha->count = ha->count + i;
				return -1;
			}
			else if (ha[Hi].key == key)
			{
				ha->count = ha->count + i;
				return Hi;
			}
		}
	}
}
//删除哈希值
bool DeleteHT(HashTable ha[], int* n, int m, int p, int key)
{
	int i = 1, adr;
	adr = key % p;
	while(ha[adr].key != NULLKEY && ha[adr].key != key)
	{
		adr = (adr + i) % m;
		i++;
	}
	if (ha[adr].key == key)
	{
		ha[adr].key = DELKEY;
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	HashTable ha[M];
	int keys[] = { 19,14,23,1,68,20,84,27,55,11,10,79 };
	int n1 = sizeof(keys) / sizeof(keys[0]);
	int n;
	int p = 13;
	//哈希表的创建+打印
	CreateHT(ha, &n, M, p, keys, n1);
	//哈希表的查找
	int num = 79;
	int result = SearchHT(ha, p, M,n1, num);
	if (result != -1)
	{
		printf("找到key = %d,位置在 %d 比较次数为%d\n", num, result,ha->count);
	}
	else
	{
		printf("没有找到key = %d , 比较次数为%d\n", num, ha->count);
	}
	//删除哈希值
	num = 23;
	DeleteHT(ha, &n, M, p, num);
	printf("删除后:\n");
	for (int j = 0; j < M; j++)
	{
		if (ha[j].key != NULLKEY && ha[j].key != DELKEY)
		{
			printf(" %d ", ha[j].key);
		}
		else {
			printf(" * ");
		}
	}
	printf("\n");
	return 0;
}