C语言实现哈希表：插入、查找、删除和平均查找长度

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

#define SIZE 13

int hash(int key) { return key % SIZE; }

void insert(int A[], int key) { int index = hash(key); int i = 0; while (A[(index + i) % SIZE] != -1) { i++; } A[(index + i) % SIZE] = key; }

int search(int A[], int key) { int index = hash(key); int i = 0; while (A[(index + i) % SIZE] != key) { if (A[(index + i) % SIZE] == -1) { return -1; } i++; } return (index + i) % SIZE; }

void delete(int A[], int key) { int index = search(A, key); if (index != -1) { A[index] = -1; } }

float avg_search_len(int A[], int key) { int index = hash(key); int i = 0; int count = 0; while (A[(index + i) % SIZE] != key) { if (A[(index + i) % SIZE] == -1) { return -1; } i++; count++; } return (float) (count + 1) / 2; }

int main() { int A[SIZE] = {-1}; int keys[] = {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77}; int n = sizeof(keys) / sizeof(keys[0]);

// 插入关键字
for (int i = 0; i < n; i++) {
    insert(A, keys[i]);
}

// 查找关键字为29的记录
int index = search(A, 29);
if (index != -1) {
    printf('找到了，位置是%d\n', index);
} else {
    printf('没找到\n');
}

// 删除关键字为77的记录
delete(A, 77);

// 插入关键字77
insert(A, 77);

// 计算平均查找长度
float avg_len = avg_search_len(A, 29);
if (avg_len != -1) {
    printf('平均查找长度为%.2f\n', avg_len);
} else {
    printf('没找到\n');
}

return 0;

}