文章编辑课程设计报告

1、 实 验 报 告（课程设计） 课程名称： 数据结构 实验项目名称：文章编辑 学院： 计算机与软件学院 指导教师： 报告人： 实验时间 实验报告提交时间： 教务处制实验项目名称一、问题描述描述算法设计的内容、约束条件，要求达到的目标等内容。（由老师公布）输入一页文字，每行最多不超过80个字符，共n行；程序可以统计出文字、数字、空格的个数要求在光标下（与记事本相似）做插入、删除等操作要求能够存盘，并能对老文件打开进行修改操作采用的数据结构及其算法：线性结构采用顺序存储方式；查找、插入、删除二、基本要求描述算法设计项目应达到的基本要求。应该实现基本的删除插入查找打开文件以及存盘等操作.并能对打开的文

2、件里的内容进行插入删除查找等操作,并且在进行完这些操作之后能够进行存盘.三、分析与实验分析算法设计方法，拟采用的数据结构（类结构）与主要算法实现原理等内容。拟采用链表进行操作,与字符串结合.主要运用了kmp算法进行查找操作,在删除中也有涉及.void getnext(string p, int next) /求模式串p的nextj的值 int j = 0, k = -1;next0 = -1;int length = p.length() - 1;while (j length)if (k = -1 | pj = pk)k+;j+;nextj = k;elsek = nextk;int kmp

3、find(string p, int next, string q,int search) /用kmp算法在主串中查找子串,p为主串,q为子串int i = 0, j = 0, k = 0, plength = p.length(), qlength=q.length(),flag=0,t=0;while (i plength)if (j = -1 | pi = qj)i+;j+;elsej = nextj;if (j = qlength)flag+;searcht= i-qlength;/flag存放的是每一次匹配到的字符的首位置 t+;return flag;search数组存放子串出现的

4、位置.四、实验步聚详细介绍实验操作步骤（程序流程图及必要说明）。开始操作 主 界 面5406321打开文件,默认在d盘调用系统函数,将文件存到d盘(d盘是代码编写时候的默认盘,可以更改)程序运行结束!输入5之后进入查找页面,输入要查找的字符(串),调用kmp算法将要查找的字符(串)在主串中出现的位置存到定义的数组中,然后在输出的时候将其变色.根据输入的字符(串)进行删除操作,在此过程中调用了kmp算法,找到了要删除的字符(串)在主串中出现的位置,将其存到数组中,然后进行逐个的删除输入数字2之后进行文章的输入,文章输入中不允许输入汉字,其它字符均可,输入#输入停止.插入是根据输入的行和列的位置进

5、行插入输入的字符(串),字符串的输入遇到回车就会停止.根据输入的位置将子串插到主串中.输入的时候,先是根据字符数组进行输入,然后存到链表中,并将输入的字符逐个的存放到刚开始定义的空的字符串中,这样方便进行之后的插入删除查找操作,而且用的kmp算法的操作对象也是字符串,因此将输入的内容存放到字符串中对之后的操作有很大的便利.五、测试与结论粘贴算法设计程序运行的截图，并加以简单文字说明。程序运行必须覆盖算法的各种情况，最后说明算法设计程序是否满足算法设计实验目标和要求。主界面:先打开文件进行操作:删除操作:查找操作:查找一个字符的情况:查找两个字符的情况:查找两个以上字符的情况:删除操作:插入操作

6、:存盘:退出:直接输入进行各种操作:查找操作:插入操作:删除操作:存盘操作:存盘的时候每行存的是80个字符.6、 实验总结主要说明算法的特点，特别是重点说明独创或创新部分，相关实验最有价值的内容，在哪些方面需要进一步了解或得到帮助，以及编程实现算法设计的感悟等内容。刚开始做的时候并没有考虑那么多,只是想实现查找某个字符出现的次数,但是那样太简单了与实验目的不符,最后用kmp算法实现各种个数的字符的查找,并且在此基础上进行各种操作(删除),存盘和打开文件的时候出现一些问题,也自行解决了.在此次试验中意识到数据结构算法的灵活性.之前学的kmp算法是进行子串和主串的匹配,没有考虑那么多,在此次试验中

7、实现了多个循环过程,从而达到实验目的.7、 程序清单程序清单如下:#include#include#include#include #include#include using namespace std;#define max 100000struct lnode char data;lnode *next;lnode *linklist;handle hout;string s ;int sum=0,punnum=0,fignum=0,spacenum=0,english=0; /定义全局变量,统计数字字母空格标点符号的个数int nextmax; /定义next数组int searchm

8、ax;lnode *searchlinklist(lnode *l,int posnum) /查找位置int j;lnode *p;p=l;j=1;while(p & jnext ;j+;if(!p | jposnum)return null;return (p);int search(lnode *l,char item) /查找元素int j=0;lnode *p;p=l;while(p)if(p-data =item)j+;p=p-next ;return j;int insertlinklist(lnode *l,int item,int pos) / 链表的插入lnode *p,*s

9、;p=searchlinklist(l,pos-1);if(!p)return -1;s=new lnode;s-data =item;s+=s-data ;s-next =p-next ;p-next =s;return 1;lnode *creatlinklist(char *ch,int len) /创建单链表int i;lnode *l,*s;if(lendata =ch0;s =ch0;s-next =null;l=s;for(i=2;inext ;p-next =p-next -next ;item=q-data ;delete(q);return (item);int showl

10、inklist(lnode *l) /链表的输出lnode *p;if(!l)return -1;p=l;while(p-next )coutdata;p=p-next ;coutdata endl;return 1;void bluecolor( ) /将字体变为蓝色handle hout = getstdhandle(std_output_handle);setconsoletextattribute(hout,foreground_blue | foreground_green |foreground_intensity); / 前景色_加强void redcolor() /将字体变为红

11、色handle hout = getstdhandle(std_output_handle);setconsoletextattribute(hout,foreground_red | foreground_intensity); / 前景色_加强void greencolor() /字体变为绿色handle hout = getstdhandle(std_output_handle);setconsoletextattribute(hout,foreground_green |foreground_intensity); / 前景色_加强void whitecolor() /将字体恢复为白色

12、handle hout = getstdhandle(std_output_handle);setconsoletextattribute(hout,foreground_blue | foreground_red |foreground_green); void getnext(string p, int next) /求模式串p的nextj的值 int j = 0, k = -1;next0 = -1;int length = p.length() - 1;while (j length)if (k = -1 | pj = pk)k+;j+;nextj = k;elsek = nextk;

13、int kmpfind(string p, int next, string q,int search) /用kmp算法在主串中查找子串,p为主串,q为子串int i = 0, j = 0, k = 0, plength = p.length(), qlength=q.length(),flag=0,t=0;while (i plength)if (j = -1 | pi = qj)i+;j+;elsej = nextj;if (j = qlength)flag+;searcht= i-qlength;/flag存放的是第一次匹配到的字符的首位置 t+;return flag;void jie

14、mian() /主界面函数bluecolor( );cout*endl;cout* *endl;cout* 请输入0-6之间数字选择要执行的操作! *endl;cout* 输入#时,输入截止. *endl;cout*endl;cout* *endl;cout* *endl;cout* 1.打开文件 2.输入 3.删除 4.插入 5.查找 6.存盘 0.退出 *endl;cout* *endl;cout* *endl;cout*endl;cout请根据菜单提示,输入要执行的操作!endl;whitecolor();void input() /输入sum=0,punnum=0,fignum=0,s

15、pacenum=0,english=0; cout请输入文章内容:=48 & chi=a & chi=a & chi=33 & chi=91 & chi=123 & chi=126)punnum+;else if(chi= )spacenum+;i+;system(cls);greencolor();cout文字:sum 数字:fignum 字母:english 标点符号:punnum 空格:spacenumendl;whitecolor();linklist=creatlinklist(ch,sum); /创建链表void tongji(string ss) /统计在删除插入过程中各种字符数

16、目的变化int i=0,j=0;while(i=48 & ssi=a & ssi=a & ssi=33 & ssi=91 & ssi=123 & ssi=126)punnum+;else if(ssi= )spacenum+;i+;greencolor();cout文字:sum 数字:fignum 字母:english 标点符号:punnum 空格:spacenumendl;whitecolor();void tongjidel(string ss) /统计在删除插入过程中各种字符数目的变化int i=0,j=0;while(i=48 & ssi=a & ssi=a & ssi=33 & ss

17、i=91 & ssi=123 & ssiss.length()break;i+;greencolor();cout文字:sum 数字:fignum 字母:english 标点符号:punnum 空格:spacenum=1 & m=6)switch(m)case 1:/1.打开文件system(cls); /清屏函数file.open(d:file.txt, ios:in);char in2;int num = 0;cout 打开文本如下： endl;s=;while (!file.eof()file.read(in, 1);in1 = 0;if(in0!=0)s+=in0;cout in;fi

18、le.close();coutendl;tongji(s); /统计字符串s中各种字符的数目jiemian();break;case 2:/2.输入system(cls);input(); /输入jiemian();break;case 3:/3.删除int newpos;string s1=,s2=;string item;coutsendl;cout请输入要删除的字符:item;getchar();getnext(item,next); /获取子串nextnewpos=kmpfind(s,next, item,search); /查找到要删除字符串所在的位置if(newpos=0)redc

19、olor();cout要删除的字符(串)不存在!endl;whitecolor();elseint startpos=0;coutitem在主串中出现在首次位置为:search0/80+1行search0%80+1列endl;for(int t=0;tnewpos;t+)for(int i=startpos;isearcht;i+)s1+=si;for(int j=searcht+item.length();jsearcht+1;j+)s1+=sj;startpos=searcht+1;tongjidel(item);for(int j=searcht+item.length();js.len

20、gth();j+)s1+=sj;s=s1;redcolor();cout删除后的字符串为:endl;whitecolor();coutsendl;jiemian();break;case 4:/4.插入system(cls);coutsendl; /输出原字符串int newpos,m,n;string s1=,s2=; /定义空字符串string item;while(true)greencolor();cout请输入要插入的位置:endl;cout请输入要插入的行:m;cout请输入要插入的列:n;whitecolor();newpos=(m-1)*80+n-1; /运行窗口默认值为每行8

21、0if(newposs.length() | newpos0)redcolor();cout插入位置有误,请重新输入:endl;whitecolor();elsebreak;greencolor();cout请输入要插入的字符:item;tongji(item);if(newpos=0)item+=s;s=item;else if(newpos=s.length()-1)s=s+item;elsefor(int i=0;inewpos;i+)s1+=si;for(i=newpos;i=s.length();i+)s2+=si;s=s1+item+s2;greencolor();cout插入后的

22、结果如下:endl;whitecolor();coutsendl;jiemian();break;case 5:/5.查找 oksystem(cls);string find;int pos;coutsendl;greencolor();cout请输入要查找的字符:find; /输入要查找的字符,输出其出现的首位置getnext(find,next);pos=kmpfind(s,next, find,search); /子串在主串中的位置if(pos=0)redcolor();cout主串中不包含要查找的字符(串)!endl;whitecolor();elseint startpos=0;redcolor();coutfind在主串中出现在首次位置为:search0/80+1 行 search0%80+1 列 首次出现的字符(串)变色