#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define NIL 0
typedef struct {
	int* Table;//儲存哈希節(jié)點的數組基地址
	int size;//哈希表長度
}HashTable;
//初始化哈希表
HashTable* InitHashTabel(int size) {
	HashTable* H = malloc(sizeof(HashTable));
	H->size = size;
	H->Table = (int*)malloc(sizeof(int) * size);
	//將所以槽位初始化為空閑狀態(tài)
	while (size > 0) H->Table[--size] = NIL;
	return H;
}
//哈希函數
int Hash(int data, int size) {
	return data % size;//除留余數法
}
//線性探測法解決哈希沖突
int LinearProbe(HashTable* H, int data) {
	int Pos = Hash(data, H->size);//通過哈希函數計算得到其哈希地址
	//若當前位置被占用
	while (H->Table[Pos] != NIL) {
		//若已存在當前鍵
		if (H->Table[Pos] == data) {
			return Pos;//返回其位置
		}
		Pos = (Pos + 1) % H->size;//線性探測下一個槽位
	}
	return Pos;//返回空閑位置
}
//插入哈希節(jié)點
int Insert(HashTable* H, int key) {
	int Pos = LinearProbe(H, key);//獲取該關鍵字應所在位置
	//判斷該關鍵字是否在哈希表中
	if (H->Table[Pos] != key) {
		H->Table[Pos] = key;
		return 1;//插入成功
	}
	return 0;//插入失敗
}
//查詢哈希節(jié)點
int Search(HashTable* H, int key) {
	//線性探測查找key是否在哈希表中
	int Pos = LinearProbe(H, key);
	if (H->Table[Pos] != NIL)
		return Pos;
	return -1;//所查元素不存在
}
//刪除哈希節(jié)點
int Delete(HashTable* H, int key) {
	int Pos = Search(H, key);//查找該關鍵字
	if (Pos != -1) {
		H->Table[Pos] = NIL;//直接將槽位置空
		return 1;//刪除成功，返回1
	}
	return 0;//刪除失敗，返回0
}
//打印哈希表節(jié)點
void print(HashTable* H) {
	for (int i = 0; i < H->size; i++) {
		if (H->Table[i] == NIL)
			printf("NIL  ");
		else  printf("%d  ", H->Table[i]);
	}
}
int main() {
	HashTable* H = InitHashTabel(10);
	printf("插入元素10、34、20、13、11、2:\n");
	Insert(H, 10);
	Insert(H, 34);
	Insert(H, 20);
	Insert(H, 13);
	Insert(H, 11);
	Insert(H, 2);
	print(H);
	printf("\n刪除13和20:\n");
	Delete(H, 13);
	Delete(H, 20);
	print(H);
}

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
//儲存一個元素的結構體
typedef struct {
	int key;
	//可添加其他元素
	char* value;//字符串元素
}ElementType;
//鏈表節(jié)點結構體
typedef struct node {
	ElementType data;
	struct node* next;
}Node;
//哈希表結構體
typedef struct {
	Node** Table;//哈希表指針數組基地址
	int Hash_size;//表長
}HashTable;
//初始化
HashTable* InitHashTable(int TableSize) {
	HashTable* H = malloc(sizeof(HashTable));
	H->Hash_size = TableSize;
	H->Table = (Node**)malloc(sizeof(Node*) * H->Hash_size);
	//初始化數組內每個指針
	for (int i = 0; i < H->Hash_size; i++) {
		H->Table[i] = NULL;
	}
	return H;
}
//哈希函數
int Hash(HashTable* H, int key) {
	return key % H->Hash_size;
}
//查找
Node* Search(HashTable* H, int key) {
	Node* p;
	int Pos;
	Pos = Hash(H, key);//計算哈希值
	p = H->Table[Pos];//該關鍵字應在鏈表的基地址
	//搜索該鏈表
	while (p != NULL && p->data.key != key)
		p = p->next;
	return p;
}
//插入
void Insert(HashTable* H, ElementType elem) {
	Node* p;
	int Pos;
	p = Search(H, elem.key);//查找該關鍵字
	if (p == NULL) {
		//若哈希表中不存在該關鍵字，頭插法插入新節(jié)點。
		Pos = Hash(H, elem.key);
		p = (Node*)malloc(sizeof(Node));
		p->data = elem;
		p->next = H->Table[Pos];
		H->Table[Pos] = p;
	}
}
//刪除
void Delete(HashTable* H, int key) {
	//查找該關鍵字是否在哈希表中
	if (Search(H, key) != NULL) {
		int Pos = Hash(H, key);
		Node* p1, * p2;
		p1 = H->Table[Pos];
		//若刪除的節(jié)點為頭結點
		if (p1->next == NULL) {
			H->Table[Pos] = NULL;
			free(p1);
		}
		else {
			while (p1->next->data.key != key)
				p1 = p1->next;
			p2 = p1->next;
			p1->next = p2->next;
			free(p2);
		}
	}
}
int main() {
	HashTable* H = InitHashTable(10);
	ElementType elem;
	Node* p;
	elem.key = 13;
	elem.value = "^_^";
	Insert(H, elem);
	elem.key = 6;
	elem.value = "QWQ";
	Insert(H, elem);
	p = Search(H, 13);
	printf("%d : %s\n", p->data.key, p->data.value);
	p = Search(H, 6);
	printf("%d : %s\n", p->data.key, p->data.value);
	Delete(H, 6);
}