【PTA数据结构 | C语言版】我爱背单词

本专栏持续输出数据结构题目集，欢迎订阅。

题目

作为一个勤奋的学生，你在阅读一段英文文章时，是否希望有个程序能自动帮你把没有背过的生词列出来？本题就请你实现这个程序。

输入格式：
输入第 1 行给出 1 个正整数 n（2≤n≤10^3），为已经背下来的单词的数量。
接下来输入的每行是不超过 20 个字符的、仅由小写英文字母组成的单词。题目保证没有重复的单词。

最后是一段整理好的英文文章，文章仅包含不超过 20 个字符的、仅由小写英文字母组成的单词，单词间以 1 个空格分隔。文章末尾以符号 # 表示结束，这个符号不属于文章的内容。题目保证文章中至少有 1 个生词，且全文一共包含不超过 10^3 个单词。

输出格式：
找出每个没有背过的生词，按照其在文章中出现的顺序输出，每行输出一个生词。注意：每个生词只输出一遍，不要重复输出。

输入样例：
5
a
your
is
case
correct
this is a test case that test the correctness of your program #

输出样例：
this
test
that
the
correctness
of
program

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>#define MAX_WORD_LENGTH 21  // 最大单词长度 + 1
#define MAX_VOCABULARY 1000 // 最大词汇量
#define HASH_TABLE_SIZE 2003 // 哈希表大小，使用质数减少冲突// 哈希表节点结构
typedef struct Node {char word[MAX_WORD_LENGTH];struct Node* next;
} Node;Node* hashTable[HASH_TABLE_SIZE];// 简单哈希函数
unsigned int hash(const char* str) {unsigned int hashval = 0;for (int i = 0; str[i] != '\0'; i++)hashval = str[i] + (hashval << 6) + (hashval << 16) - hashval;return hashval % HASH_TABLE_SIZE;
}// 插入单词到哈希表
void insert(const char* word) {unsigned int index = hash(word);Node* newNode = (Node*)malloc(sizeof(Node));strcpy(newNode->word, word);newNode->next = hashTable[index];hashTable[index] = newNode;
}// 检查单词是否在哈希表中
int contains(const char* word) {unsigned int index = hash(word);Node* current = hashTable[index];while (current != NULL) {if (strcmp(current->word, word) == 0)return 1;current = current->next;}return 0;
}// 检查单词是否已在生词列表中
int isNewWord(const char**生词列表, int 生词数量, const char* word) {for (int i = 0; i < 生词数量; i++) {if (strcmp(生词列表[i], word) == 0)return 0;}return 1;
}int main() {int n;char word[MAX_WORD_LENGTH];const char** newWords = NULL;int newWordCount = 0;// 初始化哈希表for (int i = 0; i < HASH_TABLE_SIZE; i++) {hashTable[i] = NULL;}// 读取已背单词scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s", word);insert(word);}// 读取文章并处理while (scanf("%s", word) == 1) {if (word[0] == '#') break; // 遇到结束符号// 检查是否为生词if (!contains(word) && isNewWord(newWords, newWordCount, word)) {// 动态扩容生词列表newWords = (const char**)realloc(newWords, (newWordCount + 1) * sizeof(const char*));char* newWord = (char*)malloc((strlen(word) + 1) * sizeof(char));strcpy(newWord, word);newWords[newWordCount++] = newWord;}}// 输出结果for (int i = 0; i < newWordCount; i++) {printf("%s\n", newWords[i]);}return 0;
}