C语言实现建立哈希表并实现查找某一数据元素用二次探测再散列的方法解决冲突

#include <stdio.h> #include <stdlib.h> #include <stdbool.h>

#define HASH_SIZE 10 //哈希表大小 #define EMPTY_ELEMENT -1 //表示该位置没有元素

int hash_table[HASH_SIZE]; //哈希表

//哈希函数 int hash(int key) { return key % HASH_SIZE; }

//插入元素 void insert(int key) { int index = hash(key); //计算哈希值

//如果该位置已经有元素了，就进行二次探测
int i = 1;
while (hash_table[index] != EMPTY_ELEMENT)
{
    index = (index + i * i) % HASH_SIZE;
    i++;
}

hash_table[index] = key; //插入元素

}

//查找元素 bool search(int key) { int index = hash(key); //计算哈希值

//如果该位置不是要找的元素，就进行二次探测
int i = 1;
while (hash_table[index] != key)
{
    if (hash_table[index] == EMPTY_ELEMENT) //如果该位置为空，说明没有找到
        return false;

    index = (index + i * i) % HASH_SIZE;
    i++;
}

return true; //找到了

}

int main() { //初始化哈希表 for (int i = 0; i < HASH_SIZE; i++) hash_table[i] = EMPTY_ELEMENT;

//插入元素
insert(5);
insert(15);
insert(25);
insert(35);

//查找元素
printf("%d\n", search(5)); //输出1
printf("%d\n", search(10)); //输出0

return 0;