C语言实现哈希表：线性探查法解决冲突

#include <stdio.h>

#define MAXSIZE 13 // 哈希表大小 #define EMPTY -1 // 哈希表空标志

int hash(int key) { return key % MAXSIZE; // 哈希函数，对应题目中的H(k) }

int search(int key, int table[]) { int pos = hash(key); int i = 0; while (table[pos] != EMPTY && table[pos] != key) { pos = (pos + 1) % MAXSIZE; // 线性探查 i++; } if (table[pos] == key) { return i + 1; // 查找成功，返回查找长度 } else { return -1; // 查找失败 } }

void insert(int key, int table[]) { int pos = hash(key); while (table[pos] != EMPTY) { pos = (pos + 1) % MAXSIZE; // 线性探查 } table[pos] = key; // 插入 }

void delete(int key, int table[]) { int pos = hash(key); while (table[pos] != EMPTY && table[pos] != key) { pos = (pos + 1) % MAXSIZE; // 线性探查 } if (table[pos] == key) { table[pos] = EMPTY; // 删除 } }

int main() { int table[MAXSIZE]; // 哈希表 int data[] = {16,74,60,43,54,90,46,31,29,88,77}; // 待插入数据 int i, len, sum = 0;

// 初始化哈希表
for (i = 0; i < MAXSIZE; i++) {
    table[i] = EMPTY;
}

// 插入数据
for (i = 0; i < sizeof(data)/sizeof(int); i++) {
    insert(data[i], table);
}

// 计算查找成功时的平均查找长度
len = search(29, table);
if (len != -1) {
    printf('查找成功，平均查找长度为：%d\n', len);
} else {
    printf('查找失败！\n');
}

// 删除77并重新插入
delete(77, table);
insert(77, table);

// 输出哈希表
printf('哈希表：\n');
for (i = 0; i < MAXSIZE; i++) {
    printf('%d ', table[i]);
}
printf('\n');

return 0;

}