2023年7月20日发(作者：)

题目:文学研究助手

【问题描述】

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个

实现这一目标的文字统计系统，称为“文学研究助手”。

【基本要求】

英文小说存放于一个文本文件中。待统计的词汇集合要依次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。

程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

【选作内容】

（1）模式匹配要基于KMP算法

（2）整个统计过程中只对小说文字扫描一遍以提高效率

实验完成情况：

② 作内容与基本要求都已完成。

②附加了二个功能：算出了所查询的关键词在其出现行的具体位置和在此行出现的次数。

③ 序共达376行。

程序特色之处：

A、用了KMP算法，大大提高了运算速率

B、熟练且灵活地运用了链表知识

C、熟练且灵活地运用了结构体知识

概要设计：

【抽象数据类型定义】

ADT

数据对象：英文字母、空格和标点符号的集合

数据关系：其集合构成一篇可读性的文章

基本操作：

InitList(&L)

操作结果：构造一个空链表；

InitList_node(&L)

操作结果：构造一个总链表里的分链表；

copy( &T, chars) (&L)

初始条件：已知chars 操作结果：chars数组中的字符付给;并计算出chars的长度赋给

CreateNode(&sl, str)

这个函数建立的是总链表里面的结点初始条件：已知str

操作结果：建立sl结构体中某要素的节点，并将str相应值赋值给sl CreateNode_node (&sl, str)

这个函数建立的是总链表里面分链表的结点初始条件：已知str 操作结果：建立sl结构体中某要素的节点，并将str相应值赋值给sl

addnode(&ls, link)

这个函数建立的是总链表

初始条件：已知ls和link 操作结果：将link附加到ls后面

add_node(&ls, link)

这个函数建立的是总链表里分链表

初始条件：已知ls和link 操作结果：将link附加到ls后面

Index_KMP (s, t, pos)

初始条件：已知字符串s，t 操作结果：找出s中与t相同的开始位置

IsNotCharactor(ch)

初始条件：已知字符ch

操作结果：判断ch是否为英文字母

ShowList_node(L)

初始条件：已知一个链表的头结点

操作结果：将链表的中信息打印出来，并将链表的某些信息再传递下去

ShowList(L)

初始条件：已知L的相关信息

操作结果：打印出L的相关信息

find(&stringLinkList, hstrLine, row)

初始条件：已知stringLinkList, hstrLine, row

操作结果：在串数据链表

stringLinkList,

读出查找的串strkey,与传入的串hstrLine匹配如果成功将匹配的次数与行数row,

写入相对应的行行数据链表

Next(s, j)

初始条件：已知s，j

操作结果：KMP模式匹配的next函数,即找出自身匹配

Count_KMP(s, t, pos)

初始条件：已知字符串s和t，pos

操作结果：求串t在s中出现的次数

程序使用说明

A．输入正确的打开文件方式，例如：h:

B． 输入所要查询的单词，每输入一个单词就按回车，并最后以符号“#”结束

、

【程序模块调用关系】

A 结构体调用情况

整个结构体框架主要以建立两层链表为主体。

stringLinkList,

stringLink

Hstring

RowLinkList

RowLink

,

测试数据和结果

用户输入统计的关键字

ShowDataElem

开始读文件情况

统计情况如下：

源代码：

#include

#include

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

#define NULL 0

#define LEN 81 // 串的堆分配存储表示

typedef struct HString

{

char *ch;

int length;

}HString;

typedef struct ShowDataElem

{

int row;

int count;

int location;

}ShowDataElem;

//行数据链表

typedef struct LRowNode

{

ShowDataElem data;

struct LRowNode *next;

}LRowNode,*RowLink;

typedef struct

{

RowLink head;

RowLink tail;

int len;

}RowLinkList;

//串数据链表

typedef struct StringNode

{

HString str;

RowLinkList rowlist;

StringNode *next;

}StringNode,*StringLink;

typedef struct

{

StringLink head,tail;

int len;

}StringLinkList;

//以上为定义的所需要的结构体

void copy(HString &T, char *chars)

{

int len;

int i;

len=strlen(chars);

if(!len) {

=NULL;

=0;

}

else

{

= (char *) malloc(len*sizeof(char) );

if( ! )

exit(0);

for(i=0;i

[i] = chars[i];

[i]='0';

= len;

}

}

//返回子串t在主串s中第pos个字符之后的位置。

int Index(HString s,HString t, int pos)

{

int i=pos;

int j=1;

int c;

while(i<= && j<=)

{

if([i-1]==[j-1])

i++,j++;

else

{

i=i-j+2;

j=1;

}

}

if(j>)

{

c=;

return c;

}

else

return 0;

}

int Next(HString s,int j)

{ //KMP模式匹配的next函数

if(j==1)

return 0;

int k,i; for(k=j-1;k>1;k--)

{

for(i=1;i

{

if([i-1] != [j-k+i-1])

break;

}

if(i==k)

break;

}

return k;

}

int IsNotCharactor(char ch)

{ //判断该字符是不是字母

int a;

a=ch>='a'&&ch<='z' || ch>='A'&&ch<='Z';

return (!a);

}

int Index_KMP(HString s,HString t, int pos)

{ //KMP算法

int i=pos,j=1;

int c;

while(i<= && j<=)

{

if(j==0 || [i-1]==[j-1])

{

i++;

j++;

}

else

j=Next(t,j);

}

if(j>&&(IsNotCharactor([i-1])

&& IsNotCharactor([-2])))

{

c=;

return c;

}

else

return 0;

}

int Count_KMP(HString s,HString t,int pos)

{ //求t在s中出现的次数

int c,d; int i=pos;

int j=1;

int count=0;

while(i<= )

{

if(j==0 || [i-1]==[j-1])

{

i++;

j++;

}

else

j=Next(t,j);

if(j>)

{

c=IsNotCharactor([i-1]);

d=IsNotCharactor([-2]);

if(c && d)

count++;

j=1;

}

}

return count;

}

void InitList_node(RowLinkList &L)

{

= (RowLink)malloc(sizeof(RowLink));

//为 分配动态空间，并初始化

= (RowLink)malloc(sizeof(RowLink));

if(! || ! )

exit(0);

->next = ->next = NULL;

=0;

}

void CreateNode_node(RowLink &rl, ShowDataElem elem)

{ //创建节点

rl = (RowLink) malloc(sizeof(RowLink));

if(!rl)

exit(0);

rl-> = ;

rl-> =;

rl->next = NULL;

}

void add_node(RowLinkList &ls, RowLink link)

{ //附加节点

if(->next == NULL)

->next = link;

else

->next->next = link;

->next = link;

++;

}

void ShowList(RowLinkList L)

{

int n=0;

RowLink h = ->next;

while(h)

{

printf("%5d",h->);

printf(" %d",h->);

printf("n");

//printf("%5dn",h->on);

n=n+h->;

h = h->next;

}

printf("n");

printf("一共出现的次数:%2d",n);

printf("n");

}

//串数据链表

void InitList(StringLinkList &L)

{

= (StringLink)malloc(sizeof(StringLink));

= (StringLink)malloc(sizeof(StringLink));

if(! || ! )

exit(0);

->next = ->next = NULL;

=0;

}

void CreateNode(StringLink &sl, HString str)

{

sl = (StringLink) malloc(sizeof(StringLink));

if(!sl) exit(0);

sl->=; sl->=strlen();

InitList_node(sl->rowlist);

sl->next = NULL;

}

void addnode(StringLinkList &ls, StringLink link)

{

if(->next == NULL)

->next = link;

else

->next->next = link;

->next = link;

++;

}

void find(StringLinkList &stringLinkList, HString hstrLine,int row)

{

//在串数据链表stringLinkList,读出查找的串strkey,与传入的串hstrLine匹配

//如果成功将匹配的次数与行数row,写入相对应的行行数据链表

int count;

int location;

StringLink stringLink = ->next;

//找出第一个串

while(stringLink)

{

HString strkey = stringLink->str;

count=Count_KMP(hstrLine, strkey,1);

//求匹配的次数

location=Index_KMP(hstrLine,strkey, 1);

if(location)

{

printf("%s",);

printf("在此行出现的位置为：");

printf("%dn",location);

printf("n");

}

if(count>0)

{

RowLink rLink;

ShowDataElem data;

= count;

// printf("出现的次数:");

// printf("%dn",count);

// printf("出现的行数:"); =row;

// on=location;

// printf("%dn",on);

// printf("%dn",row);

CreateNode_node(rLink,data);

add_node(stringLink->rowlist,rLink);

//写入相对应的行行数据链表

}

stringLink = stringLink->next;

//找下一个

}

}

void ShowList_node(StringLinkList L)

{

StringLink h = ->next;

while(h)

{

printf("————————————————n");

printf("关键字:");

puts(h->);

printf("该关键词分别出现在一下某行和此行出现的次数: ");

printf("n");

ShowList(h->rowlist);

//数据链表中更具体的数据（出现的行和一共出现的次数）

h = h->next;

printf("————————————————n");

}

printf("n");

}

void main()

{ //先打开要查询的文章，即打开文件

FILE *fp;

char filename[100];

printf("请输入文件名: ");

gets(filename);

if( !(fp=fopen(filename,"r")) )

{

printf("打开文件失败!! ");

exit(0);

}

StringLinkList stringLinkList;

InitList(stringLinkList);//建立头结点

HString hstrkey;

StringLink stringLink;

char key[100];

//开始输入要查询的单词，并以#结尾

printf("请输入要统计的词汇: ");

printf("n");

gets(key);

while( strcmp(key,"#") )

//当输入关键词为#时，则停止输入，开始进行统计

{

copy(hstrkey,key);

//将输入的关键字赋值到hstrkey结构体中的ch中

CreateNode(stringLink,hstrkey);

//建立hstrkey结点

addnode(stringLinkList,stringLink);

//将建立好的hstrkey结点附加到刚开始建立好的（头）结点的后面

gets(key);

//输入下一个关键字并重复进行上述操作

}

char line[LEN];

//申请一个静态数组，下面读文件的时候会用到，

int row=0;

/*

char ch;

int p;

printf("请输入要查询的词的个数：n");

ch=getchar();

printf("%cn",ch);

p=ch-'0';

*/

//开始读文件，并以长度为LEN（用户定义的长度）为一行读，只到文章结束

printf("———————————————开始阅读文章———————————————————n");

printf("n");

while( fgets(line,LEN,fp) )//fges为读文件的函数

{

row++;

//每读完一行row加一

printf("第%d行:",row);

printf("n");

}

puts(line);

HString hstrLine;

=line;

//将读的每行字符存入到中

=strlen(line);

//用strlen函数计算出line的长度用将其赋值到中

find(stringLinkList,hstrLine,row);

//在hstrLine寻找是否有与stringLinkList链表中单词相匹配的

}

printf("————————开始统计————————n");

ShowList_node(stringLinkList);

//将查询结果找出来

经验体会：

1) 理解分析问题的能力得到提高。设计一个应用程序关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。本程序要求我从文件中读取单词的位置，就是在文件中检索字符串，这样一抽象，问题的脉络就清晰了。接下来，如何读取，读取后如何映射，映射的字符串又怎么和待查字符串关联，这就构成了解决问题的几大关键模块。逐个解析，整个程序的框架就了然于胸了特别要指出的是，对整个程序的把握，随着编程工作的深入， 是越来越深刻，而且新的思路也是层出不穷。

2）对程序设计语言的细微之处又了更深刻的理解。由于字符串的操作是很原始

的几于原子的操作，所以更能看清楚平时我们所用的字符串操作函数在底层的实现机制。

致谢

在编著过程中，感谢那些帮助我的同学，有了他们，我的课程设计才能顺利进行下去。

感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程中出现的一些错误可能无法迅速查出解决，他们的帮助为我节省了宝贵的时间。

衷心感谢！

参考文献

[1] 严蔚敏，吴伟民.数据结构(C语言版).北京：清华大学出版社,1997.4

[2] 严蔚敏，吴伟民,米宁.数据结构题集(C语言版).北京：清华大学出版社,1999.2