文学研究助手

1、题目:文学研究助手【问题描述】文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个 实现这一目标的文字统计系统，称为“文学研究助手”。【基本要求】英文小说存放于一个文本文件中。待统计的词汇集合要依次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。【选作内容】（1）模式匹配要基于kmp算法（2）整个统计过程中只对小说文字扫描一遍以提高效率实验完成情况： 作内容与基本要求都已完成。 附加了二个功能：算出了所查询的关键词在其出现行的具体位置和在此行出现的次数。 序共达376行。程序特色之处：a、用了kmp

2、算法，大大提高了运算速率b、熟练且灵活地运用了链表知识c、熟练且灵活地运用了结构体知识概要设计：【抽象数据类型定义】adt 数据对象：英文字母、空格和标点符号的集合数据关系：其集合构成一篇可读性的文章基本操作： initlist(&l) 操作结果：构造一个空链表；initlist_node(&l)操作结果：构造一个总链表里的分链表；copy( &t, chars) (&l) 初始条件：已知chars 操作结果：chars数组中的字符付给t.ch;并计算出chars的长度赋给t.length createnode(&sl, str) 这个函数建立的是总链表里面的结点初始条件：已知str 操作结果

3、：建立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相同的开

4、始位置isnotcharactor(ch) 初始条件：已知字符ch 操作结果：判断ch是否为英文字母showlist_node(l) 初始条件：已知一个链表的头结点 操作结果：将链表的中信息打印出来，并将链表的某些信息再传递下去showlist(l) 初始条件：已知l的相关信息操作结果：打印出l的相关信息find(&stringlinklist, hstrline, row) 初始条件：已知stringlinklist, hstrline, row 操作结果：在串数据链表stringlinklist,读出查找的串strkey,与传入的串hstrline匹配如果成功将匹配的次数与行数row,写入

5、相对应的行行数据链表next(s, j) 初始条件：已知s，j 操作结果：kmp模式匹配的next函数,即找出自身匹配count_kmp(s, t, pos) 初始条件：已知字符串s和t，pos 操作结果：求串t在s中出现的次数程序使用说明a输入正确的打开文件方式，例如：h:code.txt b 输入所要查询的单词，每输入一个单词就按回车，并最后以符号“#”结束、 【程序模块调用关系】a 结构体调用情况整个结构体框架主要以建立两层链表为主体。stringlinklist,stringlinkhstringrowlinklistrowlink,showdataelem测试数据和结果用户输入统计的

6、关键字开始读文件情况统计情况如下：源代码：#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;

7、 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

8、struct stringlink head,tail; int len; stringlinklist; /以上为定义的所需要的结构体void copy(hstring &t, char *chars) int len; int i; len=strlen(chars);if(!len) t.ch=null; t.length=0; else t.ch = (char *) malloc(len*sizeof(char) ); if( !t.ch ) exit(0); for(i=0;ilen;i+) t.chi = charsi; t.chi=0;t.length = len; /返回子串

9、t在主串s中第pos个字符之后的位置。int index(hstring s,hstring t, int pos) int i=pos; int j=1; int c; while(i=s.length & jt.length) c=i-t.length; 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;k1;k-) for(i=1;i=a&ch=a&ch=z; return (!a); int index_kmp(hstring s,

10、hstring t, int pos) /kmp算法int i=pos,j=1; int c; while(i=s.length & jt.length&(isnotcharactor(s.chi-1) & isnotcharactor(s.chi-t.length-2) c=i-t.length; 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(it.length) c=isnotchar

11、actor(s.chi-1); d=isnotcharactor(s.chi-t.length-2); if(c & d) count+; j=1; return count; void initlist_node(rowlinklist &l) l.head = (rowlink)malloc(sizeof(rowlink); /为l.head 分配动态空间，并初始化l.tail = (rowlink)malloc(sizeof(rowlink); if(!l.head | !l.tail ) exit(0); l.head-next = l.tail-next = null; l.len

12、=0; void createnode_node(rowlink &rl, showdataelem elem) /创建节点 rl = (rowlink) malloc(sizeof(rowlink); if(!rl) exit(0); rl-data.count = elem.count; rl-data.row =elem.row; rl-next = null; void add_node(rowlinklist &ls, rowlink link) /附加节点if(ls.head-next = null) ls.head-next = link; else ls.tail-next-n

13、ext = link; ls.tail-next = link; ls.len +; void showlist(rowlinklist l) int n=0; rowlink h = l.head-next; while(h) printf(%5d,h-data.row); printf( %d,h-data.count); printf(n); /printf(%5dn,h-data.location); n=n+h-data.count;h = h-next; printf(n); printf(一共出现的次数:%2d,n); printf(n); /串数据链表void initlist

14、(stringlinklist &l) l.head = (stringlink)malloc(sizeof(stringlink); l.tail = (stringlink)malloc(sizeof(stringlink); if(!l.head | !l.tail ) exit(0); l.head-next = l.tail-next = null; l.len =0; void createnode(stringlink &sl, hstring str) sl = (stringlink) malloc(sizeof(stringlink); if(!sl) exit(0); s

15、l-str.ch=str.ch; sl-str.length=strlen(str.ch); initlist_node(sl-rowlist); sl-next = null; void addnode(stringlinklist &ls, stringlink link) if(ls.head-next = null) ls.head-next = link; else ls.tail-next-next = link; ls.tail-next = link; ls.len +; void find(stringlinklist &stringlinklist, hstring hst

16、rline,int row) /在串数据链表stringlinklist,读出查找的串strkey,与传入的串hstrline匹配/如果成功将匹配的次数与行数row,写入相对应的行行数据链表int count; int location; stringlink stringlink = stringlinklist.head-next;/找出第一个串while(stringlink) hstring strkey = stringlink-str; count=count_kmp(hstrline, strkey,1);/求匹配的次数location=index_kmp(hstrline,st

17、rkey, 1); if(location) printf(%s,strkey.ch); printf(在此行出现的位置为：);printf(%dn,location); printf(n); if(count0) rowlink rlink; showdataelem data; data.count = count; / printf(出现的次数:); / printf(%dn,count); / printf(出现的行数:); data.row=row; / data.location=location; / printf(%dn,data.location); / printf(%dn

18、,row); createnode_node(rlink,data); add_node(stringlink-rowlist,rlink);/写入相对应的行行数据链表 stringlink = stringlink-next;/找下一个 void showlist_node(stringlinklist l) stringlink h = l.head-next;while(h) printf(n); printf(关键字:); puts(h-str.ch); printf(该关键词分别出现在一下某行和此行出现的次数: ); printf(n); showlist(h-rowlist);/数

19、据链表中更具体的数据（出现的行和一共出现的次数）h = h-next; printf(n); printf(n); void main() /先打开要查询的文章，即打开文件file *fp; char filename100; printf(请输入文件名: ); gets(filename); if( !(fp=fopen(filename,r) ) printf(打开文件失败! ); exit(0); stringlinklist stringlinklist; initlist(stringlinklist);/建立头结点hstring hstrkey; stringlink string

20、link; char key100; /开始输入要查询的单词，并以#结尾printf(请输入要统计的词汇: ); printf(n); gets(key); while( strcmp(key,#) ) /当输入关键词为#时，则停止输入，开始进行统计 copy(hstrkey,key);/将输入的关键字赋值到hstrkey结构体中的ch中createnode(stringlink,hstrkey);/建立hstrkey结点 addnode(stringlinklist,stringlink);/将建立好的hstrkey结点附加到刚开始建立好的（头）结点的后面gets(key);/输入下一个关键

21、字并重复进行上述操作 char linelen;/申请一个静态数组，下面读文件的时候会用到，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; hstrline.ch=line;/将读的每行字符存入到hstrlin