文学研究人员要统计某篇英文小说中某些形容词的出现次数和位置.试写一个实现这一目标的文学统计表,称为"文学研究助手"
【基本要求】
a。英文小说存在于一个文本文件中.待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后完成.程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计
b。模式匹配要基于KMP算法
c。整个统计过程中只对小说文字扫描一次,以提高效率
【测试数据】
以当前的源程序文件作为测试目标
【实现提示】
约定小说中的词汇一律不跨行
【思路演示】
【代码过程】
1。
//base.h//------------------- 公用的常量和类型 ----------------------------#include<stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 typedef int Status; //函数的返回值//~2。
//hstring.h
//----------------- 串的堆分配存储表示 ---------------------------
typedef struct{
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串长度
}HString;
//----------------- 栈的基本操作的算法实现 --------------------------------
Status StrInit(HString &T){
//初始化串
T.ch=NULL; T.length=0;
return OK;
}
Status StrAssign(HString &T, char *chars){
//生成一个其值等于串常量chars的串T
//if(T.ch) free(T.ch); //释放原有的串空间
int len; char *c;
for(len=0, c=chars;*c;++len,++c); //求chars的长度i;
if(!len) {T.ch=NULL; T.length=0;}
else{
if( !(T.ch = (char *) malloc(len*sizeof(char) ) ))
exit(OVERFLOW);
for(int i=0;i<len;i++) T.ch[i] = chars[i];
T.ch[i]='/0'; //结尾加上/0
T.length = len;
}
return OK;
}
int StrLength(HString s){
//返回串长度
return s.length;
}
void StrPrint(HString s){
//打印串
for(int i=0;i<s.length;i++)
printf("%c",s.ch[i]);
//printf("/t");
}
int Index(HString s,HString t, int pos){
//返回子串t在主串s中第pos个字符之后的位置。如不存在，则返回0
int i=pos,j=1;
while(i<=s.length && j<=t.length){
if(s.ch[i-1]==t.ch[j-1]) i++,j++;
else i=i-j+2,j=1;
}
if(j>t.length) return i-t.length;
else return 0;
}
int Next(HString s,int j){
//KMP模式匹配的next函数
if(j==1) return 0;
for(int k=j-1;k>1;k--){
for(int i=1;i<k;i++){
if(s.ch[i-1] != s.ch[j-k+i-1])
break;
}
if(i==k) break;
}
return k;
}
int Index_KMP(HString s,HString t, int pos){
//KMP算法
int i=pos,j=1;
while(i<=s.length && j<=t.length){
if(j==0 || s.ch[i-1]==t.ch[j-1]) i++,j++;
else j=Next(t,j);
}
if(j>t.length) return i-t.length;
else return 0;
}
int IsNotCharactor(char ch){
//判断该字符是不是字母
return !(ch>='a'&&ch<='z' || ch>='A'&&ch<='Z');
}
int StrCount_KMP(HString s,HString t,int pos){
//求串t在s中出现的次数
int i=pos,j=1;
int count=0;
while(i<=s.length ){
if(j==0 || s.ch[i-1]==t.ch[j-1]) i++,j++;
else j=Next(t,j);
if(j>t.length) {
//if(s.ch[i-1]==' '||s.ch[i-1]=='/0') //如果下一个字符为' ',或者为串的结尾
// if(s.ch[i-t.length-2]==' ' || i-t.length-2<0) //并且前一个字符为' '，或者为串的开头
if(IsNotCharactor(s.ch[i-1]) && IsNotCharactor(s.ch[i-t.length-2])) //如果该字符串的前一和后一字符不是字母,说明找到了
count++; //次数++
j=1;
}
}
return count;
}
3。
//linklist.h//-------------------- 行数据链表 --------------------------------------
typedef struct LRowDataElem{
int row; //所在行 int count; //次数
}LRowDataElem;typedef struct LRowNode{ LRowDataElem data; struct LRowNode *next;}LRowNode,*RowLink;typedef struct{ RowLink head,tail; int len;}RowLinkList; //行数据链表//----------------- 行数据链表的基本操作的算法实现 --------------------------------Status InitList(RowLinkList &L){ L.head = (RowLink)malloc(sizeof(RowLink)); L.tail = (RowLink)malloc(sizeof(RowLink)); if(!L.head || !L.tail ) exit(OVERFLOW); L.head->next = L.tail->next = NULL; L.len =0; return OK;}Status CopyElem(LRowDataElem &e1,LRowDataElem e2){ e1.count = e2.count; e1.row = e2.row; return OK;}Status CreateNode(RowLink &rl, LRowDataElem elem){ //创建节点 rl = (RowLink) malloc(sizeof(RowLink)); if(!rl) exit(OVERFLOW); CopyElem(rl->data,elem); rl->next = NULL; return OK;}Status Append(RowLinkList &ls, RowLink link){ //附加节点 if(ls.head->next == NULL) ls.head->next = link; else ls.tail->next->next = link; ls.tail->next = link; ls.len ++; return OK;}Status PrintList(RowLinkList L){ //打印列表 RowLink h = L.head->next;
while(h ){
printf("%d : %d ",h->data.row, h->data.count); h = h->next;
} printf(" "); return OK;}4。
//stringLinklist.h//-------------------- 串数据链表 --------------------------------------typedef struct StringNode{ HString str; //要查找的串 RowLinkList rowlist; //串匹配的行数据列表,每个串对应一个 StringNode *next;}StringNode,*StringLink;typedef struct{ StringLink head,tail; int len;}StringLinkList;//----------------- 串数据链表的基本操作的算法实现 --------------------------------Status InitList(StringLinkList &L){ L.head = (StringLink)malloc(sizeof(StringLink)); L.tail = (StringLink)malloc(sizeof(StringLink)); if(!L.head || !L.tail ) exit(OVERFLOW); L.head->next = L.tail->next = NULL; L.len =0; return OK;}Status CreateNode(StringLink &sl, HString str){ sl = (StringLink) malloc(sizeof(StringLink)); if(!sl) exit(OVERFLOW); StrInit(sl->str); StrAssign(sl->str, str.ch); InitList(sl->rowlist); sl->next = NULL; return OK;}Status Append(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 ++; return OK;}Status StringListCount(StringLinkList &stringLinkList, HString hstrLine,int row){ //在串数据链表stringLinkList,读出查找的串strkey,与传入的串hstrLine匹配 //如果成功将匹配的次数与行数row,写入相对应的行行数据链表 StringLink stringLink = stringLinkList.head->next; //找出第一个串 while(stringLink){ HString strkey = stringLink->str; int count=StrCount_KMP(hstrLine, strkey,1); //求匹配的次数 if(count>0) { RowLink rLink; LRowDataElem data; data.count = count;data.row=row; CreateNode(rLink,data); Append(stringLink->rowlist,rLink); //写入相对应的行行数据链表 } stringLink = stringLink->next; //找下一个 } return OK;}Status PrintList(StringLinkList L){ //打印串数据链表的信息 StringLink h = L.head->next; while(h ){ printf("字符串:"); StrPrint(h->str); printf(" 出现的位置和次数是: "); PrintList(h->rowlist); h = h->next; } printf(" "); return OK;}//~5。
//test.cpp#include"base.h"#include "hstring.h"#include"linklist.h"#include "stringLinkList.h"#include<stdlib.h>#define LEN 1000