本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

作為一個勤奮的學生，你在閱讀一段英文文章時，是否希望有個程序能自動幫你把沒有背過的生詞列出來？本題就請你實現這個程序。

輸入格式：
輸入第 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;
}