文学研究助手（数据结构课程设计）

文学研究助手

一、问题描述：

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。 英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

二、需求分析：

1、 文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均由用户从键盘输

入； 2、 “单词”定义：由字母构成的字符序列，中间不含空格字符且区分大小写；

3、 待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符； 4、 在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出

现两次的只输出一个行号； 5、 测试数据：文本文件为本次实习中的word.txt:待统计的词集： he she it has to here can not is was

三、概要设计：

拟采用对两个有序表进行相互比较的策略进行“单词匹配”。程序中将涉及下列三个抽象数据类型：

1. 定义“单词”类型： ADT Aword{

数据对象：D={Si | Si ∈标准c字符串集合,i = 1,2,3,…….,n,n ≥ 0} 数据关系：R1={} | Si-1,Si ∈ D,i = 1,2,3,…..,n} 基本操作：

NewWord(WordType *nw,Sequence cha) 初始条件：cha为字符序列；

操作结果：生成一个其值为给定字符序列的单词； WordCmp(WordType wd1,WordType wd2) 初始条件：单词wd1和单词wd2已存在；

操作结果：若wd1wd2，则返 回1；

1

PrintWord(WordType wd)

初始条件：单词wd已存在；

操作结果：在计算机终端上显示单词wd； }ADT AWord 2. 定义有序表类型： ADT OrderList{

数据对象：D={Si | Si ∈AWord,i = 1,2,3,…….,n,n ≥ 0} 数据关系：R1={} | Si-1,Si ∈ D,Si-1

操作结果：构造一个空的有序表； DestroyList(OrderList *L)

初始条件：有序表L已存在；

操作结果：销毁L的结构，并释放所占空间； LocateElem(OrderList L,ElemType e,LinkType *q) 初始条件：有序表L已存在；

操作结果： 若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置， 并返回函数值FRUE；否则q指示第一个大于e的元素的前驱的位置， 并返回函数值FALSE； InsertAfter(OrderList *L,LinkType q,LinkType s)

初始条件：有序表L已存在，q指示L中一个元素； 操作结果：在有序表L中q指示的元素之后插入元素s； ListCompare(OrderList La,OrderList Lb,EqelemList *s) 初始条件：有序表La和Lb已存在； 操作结果：以s返回其中相同元素； }ADT OrderList

3. 定义单词文本串文件类型如下： ADT TextString{

数据对象：D={Si | Si ∈标准c字符集,i = 1,2,3,…….,n,n ≥ 0}；

数据关系：D中字符被“换行符”分割成若干行，每一行的字符间满足下列关系：

R1={} | Si-1,Si ∈ D,i = 1,2,3,…..,n} 基本操作：

2

Initialization(FILE **fr) 初始条件：文件fr已存在；

操作结果：打开文件fr，设定文件指针指向文件中第一行第一个字符； GetAWord(FILE *f,Sequence *st) 初始条件：文件f已打开；

操作结果：从文件指针所指字符起提取一个“单词st”； ExtractWord(FILE *f,OrderList *ta)

初始条件：文件f已打开，文件指针指向文件f中某一行的第一个字符；

操作结果：提取该行中所有单词，并构成单词的有序表ta，本操作结束时，文件指针 指向文件f中下一行的第一个字符； match(FILE *f,OrderList pat,ResultType rs)

初始条件：文件f已打开，文件指针指向文件f中第一个字符；pat为包含所有待查 询单词的有序表； 操作结果：rs为查询结果； }ADT TextString

4. 本程序包含四个模块：

1） 主程序模块：主函数设计如下 int main ( ) {

}；

2） 单词单元模块-------实现单词类型； 3） 有序表单元模块--------实现有序表类型；

4） 单词文本串文件单元模块------实现文本串文件类型； 各模块间的调用关系如下：

文本文件单元模块 有序表单元模块- 单词单元模块 3

输入信息和文件初始化； 生成测试目标词汇表；

统计文件中每个待测单词出现的次数和位置； 输出测试结果；

主程序模块

四、详细设计

1、主程序中的宏定义：

#define MAXSIZE 1000 //字符空间的最大容量 #define MAXLEN 20 //单词的最大长度 #define MAXNUM 16 //一行中单词最多个数 #define FALSE 0 #define TRUE 1

2、存储结构 /**

* 堆结构的定义 */

typedef struct{

char stores[MAXSIZE];

int freep; /*当前可用空间开始位置*/ }HeapSpace; HeapSpace sp; /**

* 单词数据类型定义 */

typedef struct{ //单词在堆中的位置描述 int stadr; /*单词在对空间中的开始位置*/ int len; /*单词长度*/ }WordType;

typedef struct{ //单词描述 char ch[MAXLEN]; /*单词字符串*/ int size; /*单词长度*/ }Sequence; /**

* 有序表类型定义 */

typedef WordType ElemType;

typedef struct NodeType{ //单词有序表结点定义 ElemType data;

struct NodeType *next; }NodeType,*LinkType;

typedef struct{ //单词有序表定义 LinkType head; /*有序表头指针*/ LinkType tail; /*有序表尾指针*/ int size; /*有序表结点个数*/ }OrderList;

4

/**

* 记录一行中匹配成功单词在目标词汇表中的位置 */

typedef struct{

int eqelem[MAXNUM]; /*单词在目标词汇表中的位置*/ int last; /*匹配成功单词的个数*/ }EqelemList; /**

* 文件测试相关的数据类型定义 */

typedef struct Node{ //单词在文件中的位置 int elem; /*被测单词在文件中的行号*/ struct Node *next;/*指向下一个行号结点的指针*/ }Node,*Link;

typedef struct{ //单词统计分析记录结构定义 WordType data; /*被测试的单词*/

int count; /*在文件中出现的次数*/

Link Next; /*记录出现的所有行号的脸表头指针*/ }HeadNode; /**

* 文本文件测试结果记录定义 */

typedef HeadNode ResultType[MAXNUM]; typedef int status;

3、主要算法设计：

/*---------------------与单词相关的函数---------------------*/ /*------------------------------------------------------------------*/ /* 定义新单词函数 */ /* 功能：把新单词放入堆中 */ /* 参数：WordType *nw--单词描述信息指针 */ /* Sequence cha--单词信息 */ /* 返回值：操作成功与否的状态信息 */ /* 0--操作失败，空间不足；1--操作成功*/ /*--------------------------------------------------------------*/ status NewWord(WordType *nw,Sequence cha) { int i,k;

if(sp.freep+cha.size>=MAXSIZE) { printf(\ getchar(); return 0;

5

本文来源：https://www.bwwdw.com/article/u1l2.html