文学研究助手(设计性实验)
1. 需求分析
问题描述
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这
一目标的文字统计系统,称为“文学研究助手”。
基本要求
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在
程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置的行号,
格式自行设计。
测试数据
以源程序模拟英文小说,编程语言保留字集作为待统计的词汇集。
实现提示
设小说非空且以文件形式存放,其中的词汇一律不跨行。这样,每读入一行,就统计每
个词在这行中的出现次数和出现位置的行号,后者可以用链表存储。若某行中出现了不止一
次,不必存多个相同的行号。数据结构采用二维链表,单词结点链接成一个链表,每个单词
的行号组成一个链表,单词结点作为行号链表的头结点。
选作内容
(1)模式匹配要基于 KMP 算法。
(2)整个统计过程中只对小说文字扫描一遍以提高效率。
(3)假设小说中的每个单词或者从行首开始,或者前置以一个空格符。利用单词匹配特
点另写一个高效的统计程序,与 KMP 算法统计程序进行效率比较。
(4)推广到更一般的模式匹配问题,并设待查模式串可以跨行。
思考题
怎样考虑分词问题?怎样考虑多模式匹配问题?
2. 概要设计
(1) 为了实现本程序,需要定义广义链表的数据结构
// 行号节点,用于存储出现位置的行号
typedef struct line_node {
int line_num;
struct line_node* next;
} LineNode;
// 单词节点,用于存储单词和出现位置的行号
typedef struct word_node {
char* word;
struct line_node* line_head;
struct word_node* next;
} WordNode;