#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define M 20
#define NULLDEL -1
#define DELDEY -2typedef struct
{int key;int count;
}HashTable;//创建和插入
void Insert(HashTable ha[], int m, int p, int key)
{int i, HO, HI;HO = key % p;if (ha[HO].key == NULLDEL || ha[HO].key == DELDEY){ha[HO].key = key;ha[HO].count = 1;}else{i = 1;do{HI = (HO + i * i) % m;i++;} while (ha[HI].key != NULLDEL && ha[HI].key != DELDEY);ha[HI].key = key;ha[HI].count = i;}
}
void Create(HashTable ha[],int m,int n1,int p,int keys[])
{int i;for (i = 0; i < m; i++){ha[i].key = NULLDEL;ha[i].count = 0;}for (i = 0; i < n1; i++){Insert(ha, m, p, keys[i]);}printf("二次探测法哈希表如下:\n");for (i = 0; i < m; i++){printf("%d 查找次数 %d 次\n", ha[i].key,ha[i].count);}
}
//查找
int Search(HashTable ha[], int m, int p, int key)
{int HO, HI;HO = key % p;if (ha[HO].key == NULLDEL){ha[HO].count = 1;return -1;}else if (ha[HO].key == key){ha[HO].count = 1;return HO;}else{ha[HO].count = 1;for (int i = 0; i < m; i++){HI = (HO + i * i) % m;//HO还是那个HO，这里变的是HI和i的值if (ha[HI].key == NULLDEL){ha->count = ha[HO].count + i;//哈希冲突的次数return -1;}else if (ha[HI].key == key){ha->count = ha[HO].count + i;return HI;}}}
}
//删除哈希值
bool deleteNode(HashTable ha[], int m, int p, int key)
{int HO,i = 1;HO = key % p;while (ha[HO].key != NULLDEL && ha[HO].key != key){HO = (HO + i * i);i++;}if (ha[HO].key == key){ha[HO].key = DELDEY;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 p = 13;Create(ha, M, n1, p, keys);int key = 79;int result = Search(ha, M, p, key);if (result!=-1){printf("找到 %d 位置在 %d 哈希冲突 %d 次\n", key, result, ha->count);}else {printf("找不到 %d 哈希冲突 %d 次\n", key, ha->count);}key = 23;deleteNode(ha, M, p, key);printf("删除 %d 元素后遍历如下:\n", key);for (int i = 0; i < M; i++){if (ha[i].key != NULLDEL && ha[i].key != DELDEY){printf(" %d ", ha[i].key);}else {printf(" * ");}}return 0;
}
