从标准输入中读入一个英文单词及查找方式,在一个给定的英文常用单词字典文件dictionary3000.txt中查找该单词,返回查找结果(查找到返回1,否则返回0)和查找过程中单词的比较次数。查找前,先将所有字典中单词读入至一个单词表(数组)中,然后按要求进行查找。字典中单词总数不超过3500,单词中的字符都是英文小写字母,并已按字典序排好序(可从课件下载区下载该字典文件)。字典中的单词和待查找单词的字符个数不超过20。 查找方式说明:查找方式以1~4数字表示,每个数字含义如下: 1:在单词表中以顺序查找方式查找,因为单词表已排好序,遇到相同的或第一个比待查找的单词大的单词,就要终止查找; 2:在单词表中以折半查找方式查找; 3:在单词表中通过索引表来获取单词查找范围,并在该查找范围中以折半方式查找。索引表构建方式为:以26个英文字母为头字母的单词在字典中的起始位置和单词个数来构建索引表,如: 字母 起始位置 单词个数 a 0 248 b 248 167 … … … 该索引表表明以字母a开头的单词在单词表中的开始下标位置为0,单词个数为248。 4:按下面给定的hash函数为字典中单词构造一个hash表,hash冲突时按字典序依次存放单词。hash查找遇到冲突时,采用链地址法处理,在冲突链表中找到或未找到(遇到第一个比待查找的单词大的单词或链表结束)便结束查找。用c语言写出方法四的代码
时间: 2023-07-14 13:11:42 浏览: 221
以下是方法四的代码,包括构造哈希表和哈希查找函数:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_WORD_LEN 20 // 最大单词长度
#define TABLE_SIZE 4000 // 哈希表大小
// 哈希表节点结构体
typedef struct HashNode {
char word[MAX_WORD_LEN+1]; // 单词
int index; // 在单词表中的下标
struct HashNode *next; // 冲突链表
} HashNode;
// 构造哈希表
void build_hash_table(char **word_list, int word_count, HashNode **hash_table) {
for (int i = 0; i < word_count; i++) {
HashNode *node = (HashNode *)malloc(sizeof(HashNode));
strncpy(node->word, word_list[i], MAX_WORD_LEN);
node->index = i;
node->next = NULL;
// 计算哈希值
int hash_value = 0;
for (int j = 0; j < strlen(word_list[i]); j++) {
hash_value = (hash_value * 26 + (word_list[i][j] - 'a')) % TABLE_SIZE;
}
// 处理冲突
if (hash_table[hash_value] == NULL) {
hash_table[hash_value] = node;
} else {
HashNode *cur = hash_table[hash_value];
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = node;
}
}
}
// 哈希查找函数
int hash_search(char *word, HashNode **hash_table, int *compare_count) {
// 计算哈希值
int hash_value = 0;
for (int i = 0; i < strlen(word); i++) {
hash_value = (hash_value * 26 + (word[i] - 'a')) % TABLE_SIZE;
}
// 在冲突链表中查找
HashNode *cur = hash_table[hash_value];
while (cur != NULL) {
(*compare_count)++;
if (strcmp(cur->word, word) == 0) {
return 1;
} else if (strcmp(cur->word, word) > 0) {
return 0;
}
cur = cur->next;
}
return 0;
}
int main() {
char **word_list = (char **)malloc(sizeof(char *) * 3500);
for (int i = 0; i < 3500; i++) {
word_list[i] = (char *)malloc(sizeof(char) * (MAX_WORD_LEN + 1));
}
// 读入单词表
FILE *fp = fopen("dictionary3000.txt", "r");
int word_count = 0;
while (fscanf(fp, "%s", word_list[word_count]) != EOF) {
word_count++;
}
fclose(fp);
// 构造哈希表
HashNode **hash_table = (HashNode **)malloc(sizeof(HashNode *) * TABLE_SIZE);
for (int i = 0; i < TABLE_SIZE; i++) {
hash_table[i] = NULL;
}
build_hash_table(word_list, word_count, hash_table);
// 读入待查找单词和查找方式
char word[MAX_WORD_LEN+1];
int method;
scanf("%s%d", word, &method);
// 查找单词并输出结果和比较次数
int compare_count = 0;
int found = 0;
switch (method) {
case 1:
for (int i = 0; i < word_count; i++) {
compare_count++;
if (strcmp(word_list[i], word) == 0) {
found = 1;
break;
} else if (strcmp(word_list[i], word) > 0) {
break;
}
}
break;
case 2: {
int left = 0, right = word_count - 1;
while (left <= right) {
compare_count++;
int mid = (left + right) / 2;
if (strcmp(word_list[mid], word) == 0) {
found = 1;
break;
} else if (strcmp(word_list[mid], word) > 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
break;
}
case 3: {
int index_table[26][2]; // 索引表
for (int i = 0; i < 26; i++) {
int j = 0;
while (j < word_count && word_list[j][0] - 'a' < i) {
j++;
}
index_table[i][0] = j;
while (j < word_count && word_list[j][0] - 'a' == i) {
j++;
}
index_table[i][1] = j - index_table[i][0];
}
int start = index_table[word[0]-'a'][0], end = start + index_table[word[0]-'a'][1] - 1;
int left = start, right = end;
while (left <= right) {
compare_count++;
int mid = (left + right) / 2;
if (strcmp(word_list[mid], word) == 0) {
found = 1;
break;
} else if (strcmp(word_list[mid], word) > 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
break;
}
case 4:
found = hash_search(word, hash_table, &compare_count);
break;
default:
printf("Invalid method\n");
return 1;
}
// 输出结果和比较次数
if (found) {
printf("1\n");
} else {
printf("0\n");
}
printf("%d\n", compare_count);
// 释放内存
for (int i = 0; i < 3500; i++) {
free(word_list[i]);
}
free(word_list);
for (int i = 0; i < TABLE_SIZE; i++) {
HashNode *cur = hash_table[i];
while (cur != NULL) {
HashNode *tmp = cur->next;
free(cur);
cur = tmp;
}
}
free(hash_table);
return 0;
}
```
阅读全文