简单行编辑器-数据结构-课程设计

中国矿业大学徐海学院计算机系《软件认知实践》报告姓名：学号：专业：设计题目：简单行编辑器指导教师：2012年12月25目录第1章题目概述.......................................1第1.1节题目要求..............................................................................1第1.2节主要难点..............................................................................2第2章系统流程图......................................3第3章数据结构和算法..................................4第4章核心代码分析....................................6第5章复杂度分析.....................................10第6章总结...........................................11参考文献..............................................13中国矿业大学徐海学院《软件认知实践》报告1第1章题目概述在这次课程设计中我选的题目是文本编辑，文本编辑几乎是每个使用电脑的人都会遇到的问题，特别是网络小说作家们。在文本的编辑中，我们会时常遇到文本信息的统计问题、小型子串的查找问题、子串的查找和删除问题等。如果靠人自己去观察和执行相关操作的话，不仅累人，而且很容易出错。而使用计算机程序去实现的话，则会省力不少，而且相对来说非常精确。本程序使用了较快速的查找算法，可以大大提高检索的效率，相信这可一极大的方便用户用电脑编辑文本文件。第1.1节题目要求文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；实现功能（1）文章内容的输入：包括字母、标点符号、数字等；（2）文章内容的统计：包括文章中大写字母、小写字母、数字、标点符中国矿业大学徐海学院《软件认知实践》报告2号、空格以及文章所有字数的个数的统计；（3）文章内容的处理：包括对文章内容的查找、删除以,其中在查找的过程中统计出该字符或字符串在文章中出现的次数；第1.2节主要难点本程序是对一段英文文章的内容进行处理，存储方式采用链式存储，没有文件操作，故本程序对其文本内容的所有操作都是在链表中进行的。对于文本的输入，采用头插法将文本信息存储到链表已申请好的存储空间中，在此部分设计中最大的问题在于输入文章过程中输入的字符数大于80时如何换行；对于文本内容的统计，使用循环对已存储的文章进行匹配，大写字母数、小写字母数、空格数、数字数直接通过比较即可得到，标点符号通过ASCⅡ比较即可得到；对于文本内容的处理，查找部分仍是使用循环对已存储的文章进行匹配，判断需要查找的字符或者字符串是否与文章中某部分内容相同，如果存在相同的记录相同的个数及位置并输出个数及位置。删除部分先使用程序的查找功能对文章中需要删除的字符或者字符串进行查找，然后对其进行删除。文本编辑的基本内容为查看文本文件内容，统计内容基本信息，查找子串是否存在及其出现次数，查找并删除所有的相关子串并重新输出文本内容等等。中国矿业大学徐海学院《软件认知实践》报告3第2章系统流程图开始主函数输入文字统计个数查找某一子串输出文字统计字母、数字、空格、某一字符串的个数以及文章总字数删除这一子串输出删除后的文章具体操作中国矿业大学徐海学院《软件认知实践》报告4第3章数据结构和算法1、定义结构体structline，文本行采用顺序存储，行与行之间采用链式存储.2、主要函数：intFindString(LINE*&head,char*str)/*统计str在文章中出现的次数*/求在一行中Str出现的次数的流程图：开始count=0;h=0;len1=0;len2=strlen(str);p-data[i]==str[0]i++k=0;j=0;p-data[i+j]==str[j]k++;j++;k=len2count++;i=i+k-1;结束YNYNNY中国矿业大学徐海学院《软件认知实践》报告5①．查找第一个字符，如果有第一个字符即p-data[i]==str[0]，设计数器k=0②．查找这个字符后面的字符与要查找的字符串是否匹配即p-data[i+j]==str[j]，如果匹配k++③．重复第二步，如果k=len2，则查找到，count++；如果没查找到，重新进行第一步。voiddelstringword(char*s,char*str)/*删除字符串*s中的字符串*str*/实现思想：①．从字符串s中寻找str第一次出现的位置*p=strstr(s,str);②．len=strlen(s);i=len-strlen(p)即前i项恰好不含要删除的字符串，将前i项复制到tmp中③．j=i+strlen(str)即要删除的字符串在i+1和j之间，将j之后的字符串复制到tmp中④．将tmp赋给串s，返回s输入文章时，以Ctrl+E(^E)为结尾，当tmp[0]==5时，发现输入^E，则退出输入。输出时文章时，如果tmp[strlen(tmp)-1]==5即发现表示结束的字符^E，用p-data[strlen(tmp)-1]='\0'除去最后一个控制符^E。strpijsfor(m=0;mi;m++)tmp[count++]=s[m];for(n=j;nlen;n++)tmp[count++]=s[n];tmp中国矿业大学徐海学院《软件认知实践》报告6第4章核心代码分析1.typedefstructline{char*data;structline*next;}LINE;/*创建一链表，同时向里面输入文本数据*/2./*统计字母数*/intCountLetter(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p-data);/*计算当前data里的数据元素的个数*/for(inti=0;iLen;i++)if((p-data[i]='a'&&p-data[i]='z')||(p-data[i]='A'&&p-data[i]='Z'))/*计算字母数*/count++;}while((p=p-next)!=NULL);/*遍历链表*/returncount;/*返回文章的字母总数*/}/*统计数字数*/intCountNumber(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p-data);/*计算当前data里的数据元素的个数*/for(inti=0;iLen;i++)if(p-data[i]=48&&p-data[i]=57)count++;/*计算数字数，ASCII码*/}while((p=p-next)!=NULL);/*遍历链表*/returncount;}中国矿业大学徐海学院《软件认知实践》报告7/*统计空格数*/intCountSpace(LINE*&head){LINE*p=head;intcount=0;do{intLen=strlen(p-data);/*计算当前data里的数据元素的个数*/for(inti=0;iLen;i++)if(p-data[i]==32)count++;/*计算空格数，空格ASCII码为32*/}while((p=p-next)!=NULL);/*遍历链表*/returncount;}/*统计文章的总字数*/intCountAll(LINE*&head){LINE*p=head;/*保存链表的首地址*/intcount=0;do/*计算总字符数*/{count+=strlen(p-data);}while((p=p-next)!=NULL);/*遍历链表*/returncount;}/*统计str在文章中出现的次数*/intFindString(LINE*&head,char*str){LINE*p=head;intcount=0;inth=0;intlen1=0;/*保存当前行的总字符数*/intlen2=strlen(str);/*待统计字符串的长度*/inti,j,k;do{len1=strlen(p-data);/*当前行的字符数*/for(i=0;ilen1;i++)/*字符匹配*/{if(p-data[i]==str[0]){k=0;for(j=0;jlen2;j++)if(p-data[i+j]==str[j])k++;中国矿业大学徐海学院《软件认知实践》报告8if(k==len2){count++;i=i+k-1;}}}}while((p=p-next)!=NULL);/*遍历链表*/returncount;}中国矿业大学徐海学院《软件认知实践》报告9第5章复杂度分析本算法的空间复杂度很低，空间复杂度为O(N)。但是本算法的时间复杂度比较高，输出函数、查找函数算法时间复杂度均为O（N），但是删除函数算法的时间复杂度较高。我暂时还问想到时间复杂度更小的算法，因此在这里我无法对该算法进行优化。中国矿业大学徐海学院《软件认知实践》报告10第6章总结为期一周的课程设计结束了，在这一周里我完成了编写文本编辑程序的任务。任务书上要求是对输入的信息进行操作，自己开始是不知道该向什么方向去努力，自己应该如何去编写这个程序，后来通过对照着任务书上的要求和到网上查找相关资料，慢慢找到了感觉。所以自己在整个课程设计的编写程序过程中遇到的困难及问题都通过查阅资料、向老师提问得以解决。本次课程设计自己最大的体会就是不管写什么程序，自己首先得对这个问题要分析透彻，要知道自己要干什么，然后才能让自己干什么。通过本次课程设计，我学到了很多：增强了查阅相关参考资料的能力，独立分析解决问题的能力；自己的上机动手的能力和对课程设计的理解，得到很多启示；课程设计为我们提供了一个即动手又动脑、独立实践的机会，将课本上的知识理论和实际有机的结合起来，锻炼了我们的分析解决实际问题的能力。这次课程设计使我我对数据逻辑结构的特点和存储表示方式的有了更深的了解和认识，培养了我在具体应用中选择合适的数据结构和存储结构的能力，同时也使我认识到自己在学习编程方面还有很多的不足。今后我要多读一些纺织方面的书籍，不能只拘泥于课本上的知识，并注重理论与实践的结合，多上机练习编写程序，提高自己的实际动手能力和独立思考的能力，不断充实自己，更好的掌握编程思想。中国矿业大学徐海学院《软件认知实践》报告11参考文献[1]严蔚敏、吴伟民主编，《数据结构》（C语言版），清华大学出版社，2002。[2]殷人昆等著，《数据结构》（C++版），清华大学出版社，2001。[3]金远平著，《数据结构》（C++描述），清华大学出版社，2005。[4]许卓群等著，《数据结构与算法》，高等教育出版社，2004。[5]FrankM.Carrano等著,《数据结构与Ｃ++高级教程》，清华大学出版社，2004。[6]严蔚敏、吴伟民著，《数据结构习题集》（C语言版），清华大学出版社。中国矿业大学徐海学院《软件认知实践》报告12附录一：源代码：#in