数据结构实验报告《三、串及其应用》

数据结构实验报告- - - - 串及其应用之文学研究助手 专业班级：
电信班 时间：2011年X月X日 数据结构实验报告- - - - 串及其应用之文学研究助手 【问题描述】 文学研究人员需要统计某篇英文小说中某些单词（特别是形容词）的出现次数和位置，甚至连数字和标点符号的个数也可以统计。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

【基本要求】 1、输入一页文字，静态存储一页文章，每行最多不超过80个字符，共N行；

2、分别统计出其中英文字母数、空格数、标点符号及整篇文章总字数；

3、统计某一字符串在文章中出现的次数，并输出该次数；

4、删除某一子串，并将后面的字符前移。

【运用拓展】 1、保存输入文章到本地text文本中；

2、模式匹配基于KMP算法；

3、仿真友好界面显示：
（1）、要求用菜单选择操作，分别用几个子函数实现相应的功能；

（2）、输入数据的形式和范围：可以输入大写、小写的英文字母、任何数 字及标点符号。

（3）、输出形式：1）、分行输出用户输入的各行字符；

2）、分5行输出“全部字母数“、“数字个数“、“空格个 数“、“标点符号个数”“文章总字数“；

3）、输出删除某一字符串后的文章。

【涉及的知识点】 链串的插入，删除，查找，模式匹配（knp算法）及文件的写入与写出，用switch,case语句进行菜单的选择，用while语句进行循环，用if语句进行条件的判断等等。

【设计思路】 、总体思路：本文采用链式存储字符串，链串的插入采用后插法，以‘#’ 为字符串结束的标志。在插入字符串的同时用文件存储字符串。

、删除算法的基本思路：输入要删除的字符串，同样以‘#’结束，然后在文中查找该字符串，若找到了则把它删除，同时长度要减少；
否则，没找到不能删除。

查找算法与删除算法类似；
但也有不同之处，不同在于：这里是要查找某字符串在文中出现的次数，因此，当找到该字符串后还要继续往后查找，并将次数加1；
直到文章的末尾才结束查找。

、用菜单做选择：用switch，case语句进行选择判断，并用类的对象调用类的成员函数以实现特定的功能。由于采用链式存储字符串，它是按一个一个的字符进行存储的，当遇到空隔和换行符时它会忽略不计。为了解决这一问题，本文采用替换的方法——当要输入空格时就输入‘：’，当要输入换行符时就输入’＼＼’，在输出时，遇到‘：’就输出空格，遇到‘＼＼’就输出换行符。

、功能设计 根据提示选择是否开始 y n 选择操作 退出 调用相应函数 是否继续？ 、详细设计 Linklist类中有一个保护成员head（指针类型）；

公有成员中包含一个整型变量len，用于计算字符串的长度；

另外还包含5个子函数，分别是：
1，void rcreat()函数，用尾插法建立链串，并将字符串存入文件，遇到#时结束；
2，void print(link *head)函数，用于输出链串，当遇到的字符为冒号（：）时输出空格，当遇到的字符为（＼＼）时输出换行，当遇到的字符大于等于48并且小于等于57时，数字个数加1，当遇到的字符为标点符号时，相应的标点符号数加1，并输出；
判断完后指针后移。

3，void deletel(link *head,link * head2)为删除字符串的函数，其中head 是指向输入的文章的第一个字符，head2是指向要删除的字符串的第一个字符，采用模式匹配的算法进行查找，若在文中找到了一个字符与要删除的第一个字符相同，则指针分别往后移，若文中的下一个字符与第二个字符不相同，则继续找文中的下一个字符与要删除的字符从第一个字符开始从新匹配，直到要删除的字符都匹配完；
找到了要删除的字符串在文中的位置后，将文中与这串字符匹配的第一个字符开始到最后一个匹配的这段字符删除；
若没有找到该字符串则不能删除。

4，void print2(link *head2)函数，输出要删除的字符串，其中，head2 指向要删除的字符串的第一个字符。

5，void *found(link *head,link *head2)函数用于查找字符串在文中出现的次数；
设置一个整型变量num，用于统计出现次数，其初始值为0。同样采用模式匹配的算法，但不同的是，找到第一次在文中出现的位置后num+1，并且还要继续找文中的下一个，找到了又要num+1，直到文章的末尾，然后输出num值。

、部分函数模块流程图：
void *found(link *head,link *head2) int num=0; link *P,*Q,*R; P=head->next ; Q=head2->next ; R=P; While (P!=NULL)&&(Q!=NULL) if(P->data==Q->data ) else R=R->next; P=R; Q=head2->next ; P=P->next ; Q=Q->next ; if(Q==NULL) num++; R=R->next; P=R; Q=head2->next 【运行环境】 电脑环境：Windows 7 & Windows XP & Windows vista 软件环境：Visual C++ 6.0 & Visual studio 2008 #include<iostream> #include<fstream> //包含头文件 using namespace std; class bunch { public: char data; bunch *next; };//bunch class bunchlist { protected: bunch *head; public: int len; bunch *creat() { ofstream SaveFile(“cpp-home.txt“,ios_base::binary);//创建本地文本文件 bunch *s,*p,*r; char ch; cout<<“输入多个字符（用冒号代替空格，用双杠(＼＼)代替换行符），为#是算法结束“; cin>>ch; p=r=new bunch; //申请新的空间 p->next =NULL; //后插法添加字符 while (ch!=＇#＇) //不为#时录入字符并保存在文本中 { s=new bunch; s->data =ch; r->next =s; r=s; SaveFile<<ch; //写入文件 cin>>ch; }//while r->next =NULL; //结束输入并返回字符串数据 SaveFile.close(); return p; }//*creat void print(bunch *head) //输出文本 { int num=0; //赋初值 int space=0; int len=0; int word=0; int douhao=0; int sentence=0; ifstream in(“cpp-home.txt“); //读入创建的txt文本文件 bunch *p; p=head->next ; while(p->next!=NULL) //不为空文件是扫描需要记录的信息 { len++; //长度先自加1 if(p->data==＇:＇)//将冒号改为空格输出 { cout<<＇ ＇; space++; //碰到空格号，空格数目自加1 word++; //字符数目自加1 p=p->next ; //移动到下一位循环扫描信息 }//if“：” if(p->data ==＇,＇)//逗号的形式和空格一致，不赘述 { word++; douhao++; cout<<＇,＇; p=p->next ; }//if“，” if(p->data ==＇.＇)//点的形式和空格一致，不赘述 { cout<<＇.＇; word++; sentence++; p=p->next ; }//if“.” if(p->data ==＇?＇)//问号的形式和空格一致，不赘述 { cout<<＇?＇; word++; sentence++; p=p->next ; }//if“？” if((p->data>=48)&&(p->data<=57))//当碰到的是数字0~9时记录 { cout<<p->data ; num++; //数字统计自加1 p=p->next ; //跳到下一位 }//if“0~9“ if(p->data==＇＼＼＇)//将双杠改为换行输出 { cout<<＇＼n＇; p=p->next ; }//if“＼＼“ else //其他情况就记录字母 cout<<p->data; p=p->next ; }//while word=word+1; //单词数自加1 sentence=sentence+1; //句子数自加1 cout<<endl; //换行输出所有统计信息 cout<<“总的字符数为：“<<len<<endl; cout<<“空格数为：“<<space<<endl; cout<<“逗号总数为：“<<douhao<<endl; cout<<“单词数为：“<<word<<endl; cout<<“句子总数为：“<<sentence<<endl; cout<<“数字个数为：“<<num<<endl; cout<<endl; } void deletel(bunch*head,bunch *HEAD) //删除操作 { bunch *P,*Q,*R,*T; T=head; P=head->next; Q=HEAD->next; R=P; while((P!=NULL)&&(Q!=NULL))//不为空时再进行删除操作 { if(P->data==Q->data ) { P=P->next ; Q=Q->next ; } else { T=T->next; R=R->next; P=R; Q=HEAD->next ; } } if(Q==NULL) { cout<<“ find the word“<<endl; T->next=P->next; } else { cout<<“the word hav＇t found!“<<endl; } } void PRINT(bunch *HEAD) {ifstream in(“home.text“); bunch *q; q=HEAD->next ; while(q!=NULL) { cout<<q->data ; q=q->next ; } } void *found(bunch *head,bunch *HEAD) { int num=0; bunch *P,*Q,*R; P=head->next ; Q=HEAD->next ; R=P; while((P!=NULL)&&(Q!=NULL)) { if(P->data==Q->data ) { P=P->next ; Q=Q->next ; } else { R=R->next; P=R; Q=HEAD->next ; } if(Q==NULL) { num++; R=R->next; P=R; Q=HEAD->next ; } } if(num>0) {cout<<“good!word have found.“<<endl; cout<<“there are“<<＇ ＇<<num<<＇ ＇<<“times have appeared.“<<endl;} else cout<<“sorry,hav＇t found the word.“<<endl; return 0; } }; void main() {int choice; char c; bunch *p,*q,*Y; bunchlist a; cout<<“********************************************************************************“<<endl; cout<<“* 欢迎使用文本编辑器！ *“<<endl; cout<<“* *“<<endl; cout<<“* 1 ：新建文本 2 ：输出文本 3 ：删除一串字符 4 查找单词出现的次数 *“<<endl; cout<<“********************************************************************************“<<endl; cout<<“Go or not?(＇y＇means yes,＇n＇means no),enter y or n.“<<endl; cin>>c; while(c==＇y＇){ cout<<“请输入您的选择 ... ...“<<endl; cin>>choice; switch(choice) { case 1: cout<<“新建文本:“<<endl; p=a.creat (); break; case 2: cout<<“输出结果为：“<<endl; a.print (p); break; case 3: cout<<“输入要删除的字符串：“<<endl; Y=a.creat(); a.deletel(p,Y); cout<<“删除“; a.PRINT(Y); cout<<“后的文章为：“<<endl; a.print(p); break; case 4: cout<<“请输入要查找的单词：“; q=a.creat(); a.found (p,q); break; default: cout<<“you have choice a wrong number!“<<endl; break; } cout<<“Go or not?(＇y＇means yes,＇n＇means no)“<<endl; cin>>c; } cout<<“谢谢使用！“<<endl; }