文学研究统计.cpp

统计某篇英文小说中某些形容词的出现次数和位置。英文小说存于一个文本文件中

#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<assert.h>
class ListNode
{
public:
	int data;
	ListNode *link;
}; 
int *Next(char *p);
int kmp_findpat(char *s,char *p,int *N,int startindex);
//kmp算法事先声明.用于查找s中从startindex开始的字符串中有没有字符串p并返回他们匹配的首地址.
int read(char *p)
{
	ifstream in("novel.txt",ios::in|ios::binary);//利用ifstream读出文件novel.txt
	if(!in)
	{
		cout<<"文件打开失败!\n";
		return 1;
	}
	int c=1;//c为行数。
	char str[10000];//str用于存放每一行的字符串。
	ListNode *m=new ListNode;m->link=NULL;
	ListNode *s=m;//带有头结点的链表s。用于存放含有字符串的行的行数。 
	while(!in.eof())//文件结束就停止。
	{
		int a=0;//a为每行的含有字符的个数。
		in.getline(str,10000);//库函数中的getline函数,用于获得一行的字符串,赋值给str.
		str[in.gcount()]='\0';//在字符串赋值时要注意写，否则就会出现Internet发送报告。
		int startindex=0;
		if(kmp_findpat(str,p,Next(p),startindex)!=-1)
		{
			ListNode *n=new ListNode;
			n->link=NULL;
			n->data=c;
			m->link=n;
			m=n;//该行如果含有字符串，将行号记录进链表.
		}
		//由于kmp算法是找到了就返回首地址,并不能看清此行有多少个这个字符串,故找到后将startindex换为b+1,继续寻找.
		while(kmp_findpat(str,p,Next(p),startindex)!=-1)
		{
			a++;//每找到一个,a+1
			int b=kmp_findpat(str,p,Next(p),startindex);
			if(b!=-1)
				startindex=b+1;//从找到的位置后继续查找。
			else
				break;//查找直到找不到为止。
		}
		if(a!=0)
		{cout<<p<<"在"<<c<<"行中出现的次数为"<<a<<endl;}
		c++;
	}
	//输出含字符串的行数.
	if(s->link!=NULL)
	{
		ListNode *q=s->link;
		cout<<p<<"出现的行数为:第";
		while(q!=NULL)
		{
			cout<<q->data<<"、";
			q=q->link;
		}
		cout<<"行"<<endl;
	}
	else
		cout<<"不能在文章中找到此字符."<<endl;
	in.close();
	return 0;
}
//返回字符串p的特征向量.
int *Next(char *p)
{
	int m=strlen(p);//m为模板p的长度.
	assert(m>0);
	int *N=new int [m];
	assert(N!=0);
	N[0]=0;
	for(int i=1;i<m;i++)
	{
		int k=N[i-1];//第i-1位置的最长的前缀字符串.
		while(k>0&&p[i]!=p[k])
			k=N[k-1];
		if(p[i]==p[k])//根据p[i]比较第k位置前缀字符，决定N[i]
			N[i]=k+1;
		else
			N[i]=0;
	}
	return N;
}
int kmp_findpat(char *s,char *p,int *N,int startindex)
{//N为p的特征数组N
	int lastindex=strlen(s)-strlen(p);//s末尾再到数一个模板的长度位置.
	if(lastindex-startindex<0)//开始位置startindex的值过大，无法匹配成功。
		return -1;
	int i;int j=0;//i为指向s内部的游标.j为指向p内部的游标.
	for(i=startindex;i<strlen(s);i++)
	{
		while(p[j]!=s[i]&&j>0)
			j=N[j-1];
		if(p[j]==s[i])//当p的第j位和s的第i位相同时,继续循环.
			j++;
		if(j==strlen(p))
			return i-j+1;//成功匹配.
	}
	return -1;
}
void main()
{
	char b;
	//利用while循环输入。
	while(true)
	{
		cout<<"----------"<<"y:继续查找;n:退出,请输入："<<"----------"<<endl;
		cin>>b;
		if(b=='y')
		{
			char a[10];
			cout<<"输入查找的字符:"<<endl;
			cin>>a;
			read(a);//调用函数read（p）；
		}
		else if(b=='n')
			break;
		else
		{
			cout<<"输入错误，请重新输入。"<<endl;
		}
	}
}