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

《数据结构实验报告《三、串及其应用》.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告《三、串及其应用》.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告三、串及其应用 数据结构实验报告-串及其应用之文学研究助手专业班级： 电信班时间：2021年X月X日数据结构实验报告-串及其应用之文学研究助手【问题描述】文学研究人员需要统计某篇英文小说中某些单词（特别是形容词）的出现次数和位置，甚至连数字和标点符号的个数也可以统计。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。 【基本要求】1、输入一页文字，静态存储一页文章，每行最多不超过80个字符，共N行； 2、分别统计出其中英文字母数、空格数、标点符号及整篇文章总字数； 3、统计某一字符串在文章中出现的次数，并输出该次数； 4、删除某一子串，并将后面的字符前移。 【运用拓展】

2、1、保存输入文章到本地text文本中； 2、模式匹配基于KMP算法； 3、仿真友好界面显示： （1）、要求用菜单选择操作，分别用几个子函数实现相应的功能； （2）、输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 （3）、输出形式：1）、分行输出用户输入的各行字符； 2）、分5行输出“全部字母数“、“数字个数“、“空格个数“、“标点符号个数”“文章总字数“； 3）、输出删除某一字符串后的文章。 【涉及的知识点】链串的插入，删除，查找，模式匹配（knp算法）及文件的写入与写出，用switch,case语句进行菜单的选择，用while语句进行循环，用if语句进行条件的判断等

3、等。 【设计思路】、总体思路：本文采用链式存储字符串，链串的插入采用后插法，以#为字符串结束的标志。在插入字符串的同时用文件存储字符串。 、删除算法的基本思路：输入要删除的字符串，同样以#结束，然后在文中查找该字符串，若找到了则把它删除，同时长度要减少； 否则，没找到不能删除。 查找算法与删除算法类似； 但也有不同之处，不同在于：这里是要查找某字符串在文中出现的次数，因此，当找到该字符串后还要继续往后查找，并将次数加1； 直到文章的末尾才结束查找。 、用菜单做选择：用switch，case语句进行选择判断，并用类的对象调用类的成员函数以实现特定的功能。由于采用链式存储字符串，它是按一个一个的字

4、符进行存储的，当遇到空隔和换行符时它会忽略不计。为了解决这一问题，本文采用替换的方法当要输入空格时就输入：，当要输入换行符时就输入，在输出时，遇到：就输出空格，遇到就输出换行符。 、功能设计根据提示选择是否开始yn选择操作退出调用相应函数是否继续？、详细设计Linklist类中有一个保护成员head（指针类型）； 公有成员中包含一个整型变量len，用于计算字符串的长度； 另外还包含5个子函数，分别是： 1，voidrcreat()函数，用尾插法建立链串，并将字符串存入文件，遇到#时结束； 2，voidprint(link*head)函数，用于输出链串，当遇到的字符为冒号（：）时输出空格，当遇到

5、的字符为（）时输出换行，当遇到的字符大于等于48并且小于等于57时，数字个数加1，当遇到的字符为标点符号时，相应的标点符号数加1，并输出； 判断完后指针后移。 3，voiddeletel(link*head,link*head2)为删除字符串的函数，其中head是指向输入的文章的第一个字符，head2是指向要删除的字符串的第一个字符，采用模式匹配的算法进行查找，若在文中找到了一个字符与要删除的第一个字符相同，则指针分别往后移，若文中的下一个字符与第二个字符不相同，则继续找文中的下一个字符与要删除的字符从第一个字符开始从新匹配，直到要删除的字符都匹配完； 找到了要删除的字符串在文中的位置后，将文

6、中与这串字符匹配的第一个字符开始到最后一个匹配的这段字符删除； 若没有找到该字符串则不能删除。 4，voidprint2(link*head2)函数，输出要删除的字符串，其中，head2指向要删除的字符串的第一个字符。 5，void*found(link*head,link*head2)函数用于查找字符串在文中出现的次数； 设置一个整型变量num，用于统计出现次数，其初始值为0。同样采用模式匹配的算法，但不同的是，找到第一次在文中出现的位置后num+1，并且还要继续找文中的下一个，找到了又要num+1，直到文章的末尾，然后输出num值。 、部分函数模块流程图： void*found(link*

7、head,link*head2)intnum=0;link*P,*Q,*R;P=head-next;Q=head2-next;R=P;While(P!=NULL)&(Q!=NULL)if(P-data=Q-data)elseR=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【运行环境】电脑环境：Windows7&WindowsXP&Windowsvista软件环境：VisualC+6.0&Visualstudio2021#include#include/包含头文件usingna

8、mespacestd;classbunchpublic:chardata;bunch*next;/bunchclassbunchlistprotected:bunch*head;public:intlen;bunch*creat()ofstreamSaveFile(“cpp-home.txt“,ios_base:binary);/创建本地文本文件bunch*s,*p,*r;charch;coutch;p=r=newbunch;/申请新的空间p-next=NULL;/后插法添加字符while(ch!=#)/不为#时录入字符并保存在文本中s=newbunch;s-data=ch;r-next=s;

9、r=s;SaveFilech;/whiler-next=NULL;/结束输入并返回字符串数据SaveFile.close();returnp;/*creatvoidprint(bunch*head)/输出文本intnum=0;/赋初值intspace=0;intlen=0;intword=0;intdouhao=0;intsentence=0;ifstreamin(“cpp-home.txt“);/读入创建的txt文本文件bunch*p;p=head-next;while(p-next!=NULL)/不为空文件是扫描需要记录的信息len+;/长度先自加1if(p-data=:)/将冒号改为空格

10、输出coutdata=,)/逗号的形式和空格一致，不赘述word+;douhao+;coutdata=.)/点的形式和空格一致，不赘述coutdata=?)/问号的形式和空格一致，不赘述coutdata=48)&(p-datadata=)/将双杠改为换行输出coutnext;R=P;while(P!=NULL)&(Q!=NULL)/不为空时再进行删除操作if(P-data=Q-data)P=P-next;Q=Q-next;elseT=T-next;R=R-next;P=R;Q=HEAD-next;if(Q=NULL)coutnext;elsecoutnext;void*found(bunch*head,bunch*HEAD)intnum=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;elseR=R-next;P=R;Q=HEAD-next;if(Q=NULL)num+;R=R-next;P=R;Q=HEAD-next;if(num0)coutc;while(c=y)coutchoice;switch(choice)case1:coutc;cout“谢谢使用！“endl; 4