简单的文本编辑器

合肥学院

计算机科学与技术系课程设计报告2009〜2010学年第二学期课程数据结构与算法课程设计名称简单的文本编辑器学生姓名学号专业班级指导教师李红沈亦军2010年6月

题目：（简单的文本编辑器）功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一字符或者子串，并将后面的字符前移。（4）插入某一字符或者子串。（5）查找某一字符或者子串。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出〃全部字母数〃、〃数字个数〃、〃空格个数〃、〃文章总字数〃（3）输出删除某一字符串后的文章。一、问题分析和任务定义本程序要求设计的文本编辑器可以实现（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一字符或者子串，并将后面的字符前移。（4）插入某一字符或者子串。（5）查找某一字符或者子串。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出〃全部字母数〃、〃数字个数〃、〃空格个数〃、〃文章总字数〃（3）输出删除某一字符串后的文章。实现上述功能需完成关键问题有：1、如何解决在文章输入时的每行不超过80个字符的问题。2、如何利用串的有关函数来解决文本编辑器的统计、删除、插入、查找这几个功能。本程序中主要涉及到串和文件处理方面的知识，故本实验的数据存储应为串的存储方式-顺序表，顺序串属于线性逻辑结构。其存储形式如图1所示逻辑地址图1顺序串的存储示意图逻辑地址由于该文本编辑器的主要的功能为统计、删除、插入、查找。顺序串中也具有相应的函数可以实现。对于统计出文章中英文字母数和空格数及整篇文章总字数，可以用结点中的几个整形变量来表示;对于统计某一字符串在文章中出现的次数并输出该次数和查找某一字符或者子串这两个功能，可以利用一个函数表示出来。首先是对该字符或字符串的查找，这里需要用到串的模式匹配算法；对于插入和删除某个字符和字符串，可以简单地利用串有关方面的函数即可实现功能。对于如何将解决在文章输入时的每行不超过80个字符，可以利用在满80字符后的存储空间内增加换行符'\n'加以解决。二、数据结构的选择和概要设计本程序中的文本信息，采用顺序串来存储，存储的结构即为顺序表。现定义串的数据类型：在该程序用到的串中，除了定义一个字符型数组ch[max]来存储文章中的字符外，还定义了用来描述文章中的内容长度的整型变量curlen。除此之外，为了方便统计文章中的各类字数，另外定义了四个整型变量numl，num2，num3，num4，分别用来表示文章中的字母数、空格数、数字个数和总字数。结点的类型描述如下：typedefstruct(charch[max];intcurlen;//文章的内容大小intnum1;//字母数intnum2;//空格数intnum3;//数字个数intnum4;//总字数}seqstring;结点的结构如图2表示curlennum1num2num3num4图2seqstring结点的结构根据该程序的数据结构和所要实现的功能，应该先定义各功能函数，函数包括在串s中寻找串t(串的模式匹配算法)函数voidindex(seqstring*s,seqstring*t)、串的插入函数seqstring*insert(seqstring*s1,inti,seqstring*s2)、串的初始化函数seqstring*create(seqstring*s)、统计各类数的个数函数seqstring*Count1(seqstring*t1)、查找某个字或字段的函数voidCount2(seqstring*t1,seqstring*t2)、字段的删除函数seqstring*Delete(seqstring*s,inti,intj)、密码函数voidmima()。各子函数定义完成后即需要完成主函数的表述。整个文本编辑器程序的功能实现应如下：首先将指定文本文档kcsj_TXT中的字符信息赋值给自定义串的字符数组中，其次是利用各函数对该字符数组进行处理，得到需要的数值信息。最后，在实现对文章的插入和删除功能时，应将字符数组中的所有字符信息重新写进文本文档kcsj_TXT中，以实现对其的修改。程序流程图如图3所示

N图3QQQQQQQ判断是否等于ciphermain_menu()YNNNNNYNN退出程序Insert()Delete()Count1()CountN图3QQQQQQQ判断是否等于ciphermain_menu()YNNNNNYNN退出程序Insert()Delete()Count1()Count2()Fputc()Printf()putchar()main()create()输入order的值三、详细设计和编码由于本程序的主要考察对象是串中的一系列函数问题，所以在此，先对顺序串的函数进行详细论述。1、顺序串的插入函数seqstring*insert(seqstring*s1,inti,seqstring*s2)，该函数的形参i的作用是表示在结点*s1的字符数组中第i个数后插入结点*s2中的字符数组，该函数的核心语句是两个for循环for(intm=s1->curlen;m>i;m--)s1->ch[m+n-1]=s1->ch[m-1];for(m=i,n=0;n<s2->curlen;n++,m++)s1->ch[m]=s2->ch[n];(需要指出的是，其中的变量n表示的是待插入结点中的字符数组的长度)第一个for循环的目的是为了将结点*s1中字符数组的第i个数以后的所有数组元素依次向后移动n个位置，腾出的新位置即为结点*s2中的字符数组待插入的地方。故第二个for循环即为将结点*s2中的字符数组插入其中，完成顺序串的插入操作。2、文章的输入函数seqstring*create(seqstring*s)，该函数的作用是输入文章，并将文章中的字符依次赋值给字符。该函数的关键问题在于如何解决所要求的每行最多不超过80个字符的问题。解决方法如下：首先需定义两个整型变量order和Num。将其赋值1。order是为了对每行的字符进行统计，检查是否达到80个字符。Num是记录输入的字数。这里可分为两种情况。第一是在用户手动输入回车的情况下，只需将order赋值-1即可；第二是在用户未合法换行下，程序在用户输入需添加换行符的位置自动添加换行符，以控制每行的字数。注：由于换行符不在屏幕上显示，变量order的实际作用是指示文章中新输入字符的下标，故重新赋值时，应赋值为-1。3、数组统计各类数个数的函数seqstring*Count1(seqstring*t1)，该函数完成统计字数的思想是利用字母和数字中的ASCII码值的大小规律来实现的。由于在文件中涉及到换行符'\n'，所以如果粗略地使用字符数组的长度来表示文章的字数时，将无法避开换行符的统计。故在此使用了语句：if((t1->ch[i]>='a'&&t1->ch[i]<='z')||(t1->ch[i]>='A'&&t1->ch[i]<='Z')||(t1->ch[i]>='0'&&t1->ch[i]<='9'))来作为文章总字数的判断语句。4、在串s中寻找串t(串的模式匹配算法)函数voidindex(seqstring*s,seqstring*t)和查找字段函数voidCount2(seqstring*t1,seqstring*t2)是联合使用，来查找文章中的某个字段并输出其在文章中出现的次数。Count2函数中，依次把输入的字符值赋给结点seqstring*t2的字符数组中，接着调用函数voidindexo在函数voidindex中，核心算法为：for(i=0;i<=n-m;i++,y++){for(k=i,j=0;j<m;k++,j++){if(s->ch[k]=='\n'){x++;y=0;}if(s->ch[k]!=t->ch[j])break;if(j==m-1){order++;printf("第％d行第％d个字开始",x,y);}这里的变量x,y初始均赋值为1,x用来指示字符数组扫描到第x行，y用来表示扫描到该行中的第y个位置。n和m分别代表两个结点中字符数组的长度。当(s->ch[k]=='\n')时，x自加1，表示扫描换了一行，y赋值0(由于换行符'\n'在数组中也占据一个位置，所以y不能赋值1)。为了方便解释，这里借用两个串的例子加以说明。假设串S=”s0,s1,s2...s(n-1)”,串T=''t0,t1,t2...t(m-1)",(1)从串S的第1个字符s0开始，将串T中的字符依次与S中的字符比较，若s0=t0，s1=t1,s2=t2,...,s(m-1)=t(m-1)，则匹配成功，输出该字符串在文章中的具体位置。(2)若存在s(k)!=t(k)(k<m)，则无需继续比较，该趟匹配不成功，可改为从串S的第2个字符s1开始，重复上述步骤。(3)若该趟匹配仍然不成功，改为从串S的第3个字符s2开始，重复上述步骤，，直到s(i)=t0,s(i+1)=t1,s(i=2)=t2,...,s(i+m-1)=t(m-1),则匹配成功，输出si在串S中的具体位置。(4)若最后一次匹配(第n-m+1)次，仍然不能得到s(n-m)=t0,S(n-m+1)=t1,...,s(n-1)=t(m-1),则整个模式匹配不成功，输出NULL和该段在文章出现的次数为0(5、字段的删除函数seqstring*Delete(seqstring*s,inti,intj)，主要的算法思想是将串S中从第i个字符开始的连续j个字符删除，形成新串s(需要将第i+j个字符至最后一个字符依次前移j个位置，同时串s的长度需要减j(6、密码函数是作为该程序的一个小小的润色，其实现功能比较简单(其核心算法为：if(a==cipher)Order=1;else(printf("\n请第三次输入密码:\n");scanf("%d”,&b);if(b==cipher)Order=1;elseprintf("\n对不起，您没有访问权限!\n");}使用两个if判断语句，用来实现第二次和第三次输入密码的判断问题。主函数的流程即为对各函数的调用实现(用了一个switch语句来实现对整个程序的宏观调控(需要提到的是，本程序为了在调试时的观看方便和简洁，用到了语句system("cls")；(该语句中的CIS实现的是清屏作用，清除的是上一个回车的屏显内容。三、上机调试1、错误分析及改正：本程序的第一个重要错误的截图为图4所示：MieroscftVisuslC++DtbugLibrDebugAziEertionFailed!Frogj-sm：D皿龚冉'数据皓构课程设计，数据皓构课程设计\Debng\Cpp1.白眼File:tgetc.cLim：4iErprH5Sii：iTl-号饪沱：s!=NULLForirLtc-rniationonhowycmprCigi_：=LfTic：=lTlcause：itlas+ionfailura,shmtheVisnalC++docuirierLtationuil：±SEei_ts.(FrhgeRptrytodytiug：theapplicaticm)匚剪涎□〔重试⑥翎略①图4程序的第一个错误截图该错误的主要原因是程序中所用到的txt文本文档的存储路径不正确。即需要将该文本文档放到和cpp文件同一个文件夹里。本程序第二个错误的截图如图5所示：清技照菜单提示远择操作：仲主意二必须输入大写，史章中的宇母数、数字个数、空格个数、总宇数分别是:113,117渝入回车键返回主菜单：图5程序的第二个错误截图该错误为逻辑错误。文章中的正确字数应该是319，但此时显示的却是417。其原因为将文章的总字数统计用t->curlen表示，即字符数组的长度。由于字符数组中不仅存储字母和数字，还存储有标点符号、空格符‘’、换行符‘\n’，所以会产生该错误。只要将字数统计用整型变量num4表示即可解决。本程序中有个很重要的细节问题，即getchar();语句的使用。由于本程序在插入字符时，用到的是语句：for(i=0;i<t3->curlen;i++){ah=getchar();t3->ch[i]=ah;}在执行时，一般以回车键作为结束输入标志。如不在该for语句之前添加getchar();语句。则将导致输入数组元素之前所按下的回车键也赋值到字符数组中。2、时间、空间性能分析该程序的空间性能大体上体现在各子函数的空间性能上，最终可归结到顺序表的空间性能的分析上。各算法的空间性能均较好。只是对于顺序表的数组空间大小的定义很难把握。像该程序中只要用到的字符数组ch[max]。由于文章的字数一般都比较多，再加上符号、换行符、空格符的加入，故在此程序中的max初始值为1000。会造成一些必不可少的空间浪费。该程序的时间性能也主要体现在各个子函数的时间性能上，由于插入和删除时主要和移动的元素有关，所以其算法的时间复杂度为O(n).，串的初始化函数也为O(n)。统计字数函数与数组的长度无关，所以其算法的时间复杂度为0(1)。这里重点需指出的是串的模式匹配算法的时间复杂度。虽然之前提到了其循环次数计算值为m(n-m+1)次，但显然实际的模式匹配中字符的比较次数不会超过m(n-m+1)次。但如果子串中的最后一个元素为主串中的最后一个元素时，该算法确实需要执行m(n-m+1)次。所以，串的模式匹配算法在最坏情况下的时间复杂度为0(m(n-m))，当n>>m时，时间复杂度可表示为0(mn)。五、测试结果及其分析应F:\教据结构课程设计\薮据结构课程设计\裁据结构课程设计请输入文章内容，以键皓豆二Qccccccccccccccccdddddddddddddddddddd55555555555555555555rrprrrpi'rrpi'rrrH图6输入文章内容请按照荣单提示造择操作：〈注意:必须输入大与?>c金文章的内容为：11till1111ill1illililtillill11111111111iilaaaaaaaaaaaaaaaaaaaaaaaJjbJjbbbbbbbbbbJjbccccccccccccccccdddddddddddddddddddd55555555555555555555I'rrrrrpprriTrrrvi'Pi'输入回车镣很回主菜单图7显示文章内容清投照菜单提示选择操作:〈注意=必须输入大写?>0文章中的宇反数、数宇个麴空格个数、总宇数分别目94G291CG七回车键返回主菜隼二图8输出文章各类数的信息请技照菜单提示选择操作；〈江芯=必须输入大写?〉L请输入您要查技的字段，该以在艾章出现的位置为：常对〒第44个宜开始赛行第4S个宇开始第2行隽华个宇升始该段在支章出现的次数为：3人回卑键返回主菜单二图9查找和统计某段信息请技照菜羊提3选择操作：H三意:必须输入大乓],D清输X.您熟删除V专的佑容〈第「，个字开始，具州臆的字教"1160箝出删除日的R萱内容：5S55555555G55555555rrrrrrrrrrrrrrri1-rrrr输入回车健返回主茉单:图10删除某段信息六、用户使用说明本文本编辑器只能对指定用户输入的文章进行简单的统计、查找、删除等基础功能，不能用于对复杂文字文件的操作。执行程序后，输入123456登录密码进入主菜单。按照主菜单上的提示调用各个函数来执行文本编辑器的各项功能。注意：提示按回车键返回时，不可用其它的键代替，否则将发生短暂错误。七、参考文献王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月何钦铭，颜晖.C语言程序设计.北京：高等教育出版社，2008年1月八、附录#include<stdio.h>#include<malloc.h>#include<stdlib.h>#definemax1000intcipher=123456;intOrder=1;charchoice;typedefstruct(charch[max];intcurlen;//文章的内容大小intnum1;//字母数intnum2;//空格数intnum3;//数字个数intnum4;//总字数}seqstring;seqstring*insert(seqstring*s1,inti,seqstring*s2)(//串的插入函数intn=s2->curlen;for(intm=s1->curlen;m>i;m--)s1->ch[m+n-1]=s1->ch[m-1];//将结点*s1中字符数组的第i个数以后的所有数组元素依次向后移动n个位置，〃腾出的新位置即为结点*s2中的字符数组待插入的地方for(m=i,n=0;n<s2->curlen;n++,m++)s1->ch[m]=s2->ch[n];//将结点*s2中的字符数组插入其中，完成顺序串的插入操作s1->curlen=s1->curlen+s2->curlen;free(s2);returns1;}seqstring*create(seqstring*s)(//文章的输入函数charah='a';inti=1,order=1,Num=1;//order作为标志，来控制每行是否超过80个字ah=getchar();s->ch[0]=ah;while(ah!='#'){ah=getchar();s->ch[i]=ah;order++;Num++;i++;//此时i指向数组下一个存储单元if(ah=='\n')//在手动输入回车情况下order=-1;if(order==80){//在用户未合法换行下，程序增加换行s->ch[i]='\n';Num++;i++;order=-1;}}s->curlen=Num-1;//除去结束标志符'#'returns;}seqstring*Count1(seqstring*t1){〃统计各类数的个数inti;for(i=0;i<t1->curlen;i++){if((t1->ch[i]>='a'&&t1->ch[i]v='z')ll(t1->ch[i]>='A'&&t1->ch[i]v='Z'))t1->num1++;elseif(t1->ch[i]=='')t1->num2++;elseif(t1->ch[i]>='0'&&t1->ch[i]<='9')t1->num3++;if((t1->ch[i]>='a'&&t1->ch[i]<='z')ll(t1->ch[i]>='A'&&t1->ch[i]<='Z')ll(t1->ch[i]>='0'&&t1->ch[i]<='9'))t1->num4++;}returnt1;}voidindex(seqstring*s,seqstring*t){//在串s中寻找串t(串的模式匹配算法)intn,m,i,j,k,order=0,x=1,y=1;n=s->curlen;m=t->curlen;printf(-该段在文章出现的位置为:\n");for(i=0;i<=n-m;i++,y++){for(k=i,j=0;j<m;k++,j++){if(s->ch[k]=='\n'){x++;y=0;}//用来表示待查找字段在文章中的行数和位置数if(s->ch[k]!=t->ch[j])break;if(j==m-1){order++;printf("第％d行第％d个字开始",x,y);}}}if(order==0)printf("NULL");printf(-该段在文章出现的次数为:％d”,order);}voidCount2(seqstring*t1,seqstring*t2){//查找某个字或字段，并输出其在文章中的位置inti=0,num=0;charah='a';while(ah!='\n'){ah=getchar();t2->ch[i]=ah;i++;}//将待查找的字段赋值给字符数组t2->curlen=i-1;index(t1,t2);}seqstring*Delete(seqstring*s,inti,intj){//字段的删除函数for(intk=s->curlen-j,m=i-1,n=i+j-1;k>0;m++,n++,k--)s->ch[m]=s->ch[n];s->curlen=s->curlen-j;returns;}voidmima(){inta,b;printf("\n请第二次输入密码:\n");scanf("%d”,&a);if(a==cipher)Order=1;else(printf("\n请第三次输入密码:\n");scanf("%d”,&b);if(b==cipher)Order=1;elseprintf("\n对不起，您没有访问权限!\n");}}voidmain_menu(){printf("浓※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※浓※※※\n");TOC\o"1-5"\h\zprintf("浓§M\n");printf("浓§主菜单耳※\n");printf("浓§耳※\n");printf("浓§◎查看软件说明请按I(Introduce)◎耳※\n");printf("浓§耳※\n");printf("※耳◎显示文章内容请按C(Content)◎耳※\n");printf("浓§耳※\n");printf("※耳◎输出文章各类数的信息请按O(Output)◎耳※\n");printf("浓§耳※\n");printf("※耳◎查找和统计文本中某段信息请按L(Lookup)◎耳※\n");printf("浓§耳※\n");printf("※耳◎插入某段信息请按A(Add)◎耳※\n");printf("浓§耳※\n");printf("※耳◎删除某段信息请按D(Delete)◎M\n");printf("M\n");printf("※耳◎※将文章保存至文本文档中S(save)§◎M\n");printf("M\n");printf("*◎※退出系统请按Q(Quit)§◎M\n");printf("浓§M\n");printf("浓※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※浓※※※\n");printf("\n\n请按照菜单提示选择操作：(注意:必须输入大写!)”);scanf("%c”,&choice);getchar();}intmain(void)(seqstring*t1,*t2,*t3;inti,j,k,m,l,order;charah;FILE*fp1;system("color1A");t1=(seqstring*)malloc(sizeof(seqstring));t2=(seqstring*)malloc(sizeof(seqstring));t3=(seqstring*)malloc(sizeof(seqstring));t1->num1=t1->num2=t1->num3=t1->num4=0;printf("请输入登录密码:\n");scanf("%d”,&order);if(order!=cipher){Order=0;mima();}if(Order==0)return0;getchar();system("cls");//清除上个回车键的屏显内容printf("请输入文章内容，以'#键结束:\n");t1=create(t1);getchar();system("cls");main_menu();while(choice!='Q')switch(choice)(case'C':printf("\n");printf("该文章的内容为:\n");for(i=0;i<t1->curlen;i++)putchar(t1->ch[i]);printf("\n\n\n输入回车键返回主菜单”)；getchar();system("cls");main_menu();break;case'O':t1=Count1(t1);printf("\n");printf(-文章中的字母数、数字个数、空格个数、总字数分别是:\n”);printf("%d\n%d\n%d\n%d”,t1->num1,t1->num3,t1->num2,t1->num4);printf("\n\n\n输入回车键返回主菜单:，getchar();system("cls");main_menu();break;case'L':printf("\n");printf("请输入您要查找的字段:\n");Count2(t1,t2);printf("\n\n\n输入回车键返回主菜单:，getchar();system("cls");main_menu();break;case'A':printf("\n");printf("\n请输入您要插入的字数和字段:\n");scanf("%d”,&m);t3->curlen=m;getchar(