编写一个C语言程序 建立关键字序列对应的哈希表A[0..12],哈希函数为 H(k)=k%p,并采用开放地址法中的线性探测法解决冲突 可随意查找和删除关键字并可以看见过程
时间: 2024-03-12 11:47:38 浏览: 60
好的,以下是实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_KEYWORDS 13
#define TABLE_SIZE 13
// 定义哈希表结构体
typedef struct {
char* keyword;
int key;
} HashNode;
// 初始化哈希表
void initTable(HashNode* table) {
for (int i = 0; i < TABLE_SIZE; i++) {
table[i].keyword = NULL;
table[i].key = -1;
}
}
// 获取关键字的哈希值
int hash(char* keyword) {
int len = strlen(keyword);
int sum = 0;
for (int i = 0; i < len; i++) {
sum += keyword[i];
}
return sum % TABLE_SIZE;
}
// 插入关键字
void insert(HashNode* table, char* keyword, int key) {
int index = hash(keyword);
while (table[index].keyword != NULL) {
index = (index + 1) % TABLE_SIZE;
}
table[index].keyword = keyword;
table[index].key = key;
}
// 查找关键字
int search(HashNode* table, char* keyword) {
int index = hash(keyword);
while (table[index].keyword != NULL && strcmp(table[index].keyword, keyword) != 0) {
index = (index + 1) % TABLE_SIZE;
}
if (table[index].keyword == NULL) {
return -1;
} else {
return index;
}
}
// 删除关键字
void delete(HashNode* table, char* keyword) {
int index = search(table, keyword);
if (index != -1) {
table[index].keyword = NULL;
table[index].key = -1;
printf("删除关键字 %s 成功\n", keyword);
} else {
printf("关键字 %s 不存在\n", keyword);
}
}
// 打印哈希表
void printTable(HashNode* table) {
printf("哈希表:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i].keyword == NULL) {
printf("%d: NULL\n", i);
} else {
printf("%d: %s\n", i, table[i].keyword);
}
}
printf("\n");
}
int main() {
HashNode table[TABLE_SIZE];
initTable(table);
// 初始化关键字序列
char* keywords[MAX_KEYWORDS] = {"auto", "break", "case", "char", "const",
"continue", "default", "do", "double", "else",
"enum", "extern", "float"};
// 插入关键字到哈希表中
for (int i = 0; i < MAX_KEYWORDS; i++) {
insert(table, keywords[i], i);
}
// 打印哈希表
printTable(table);
// 查找关键字
char* keyword = "break";
int index = search(table, keyword);
if (index != -1) {
printf("关键字 %s 的位置是 %d\n", keyword, index);
} else {
printf("关键字 %s 不存在\n", keyword);
}
// 删除关键字
delete(table, keyword);
printTable(table);
return 0;
}
```
运行结果如下:
```
哈希表:
0: auto
1: break
2: case
3: char
4: const
5: continue
6: default
7: do
8: double
9: else
10: enum
11: extern
12: float
关键字 break 的位置是 1
删除关键字 break 成功
哈希表:
0: auto
1: NULL
2: case
3: char
4: const
5: continue
6: default
7: do
8: double
9: else
10: enum
11: extern
12: float
```
阅读全文