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

1、中国矿业大学徐海学院计算机系软件认知实践报告姓 名： 学 号： 专 业： 设计题目： 简单行编辑器 指导教师： 2012年12月25目 录第1章 题目概述1第1.1节 题目要求1第1.2节 主要难点2第2章 系统流程图3第3章 数据结构和算法4第4章 核心代码分析6第5章 复杂度分析10第6章 总结11参考文献13中国矿业大学徐海学院软件认知实践报告第1章 题目概述在这次课程设计中我选的题目是文本编辑，文本编辑几乎是每个使用电脑的人都会遇到的问题，特别是网络小说作家们。在文本的编辑中，我们会时常遇到文本信息的统计问题、小型子串的查找问题、子串的查找和删除问题等。如果靠人自己去观察和执行相关操作

2、的话，不仅累人，而且很容易出错。而使用计算机程序去实现的话，则会省力不少，而且相对来说非常精确。本程序使用了较快速的查找算法，可以大大提高检索的效率，相信这可一极大的方便用户用电脑编辑文本文件。第1.1节 题目要求文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2） 统计某一字符串在文章中出现的次数，并输出该次数； （3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数

3、字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数" （3）输出删除某一字符串后的文章；实现功能（1）文章内容的输入：包括字母、标点符号、数字等； （2）文章内容的统计：包括文章中大写字母、小写字母、数字、标点符号、空格以 及文章所有字数的个数的统计；（3）文章内容的处理：包括对文章内容的查找、删除以,其中在查找的过程中统计出该字符或字符串在文章中出现的次数；第1.2节 主要难点本程序是对一段英文文章的内容进行处理，存储方式采用链式存

4、储，没有文件操作，故本程序对其文本内容的所有操作都是在链表中进行的。对于文本的输入，采用头插法将文本信息存储到链表已申请好的存储空间中，在此部分设计中最大的问题在于输入文章过程中输入的字符数大于80时如何换行；对于文本内容的统计，使用循环对已存储的文章进行匹配，大写字母数、小写字母数、空格数、数字数直接通过比较即可得到，标点符号通过ASC比较即可得到；对于文本内容的处理，查找部分仍是使用循环对已存储的文章进行匹配，判断需要查找的字符或者字符串是否与文章中某部分内容相同，如果存在相同的记录相同的个数及位置并输出个数及位置。删除部分先使用程序的查找功能对文章中需要删除的字符或者字符串进行查找，然后

5、对其进行删除。文本编辑的基本内容为查看文本文件内容，统计内容基本信息，查找子串是否存在及其出现次数，查找并删除所有的相关子串并重新输出文本内容等等。第2章 系统流程图第3章 数据结构和算法1、 定义结构体 struct line，文本行采用顺序存储，行与行之间采用链式存储.2、主要函数：int FindString(LINE * &head,char *str) /*统计str在文章中出现的次数*/求在一行中Str出现的次数的流程图：开始count=0;h=0;len1=0; len2=strlen(str);p->datai=str0i+k=0;j=0;p->datai+

6、j=strjk+;j+;k=len2count+;i=i+k-1;结束YNYNNY查找第一个字符，如果有第一个字符即p->datai=str0，设计数器k=0查找这个字符后面的字符与要查找的字符串是否匹配即p->datai+j=strj，如果匹配k+重复第二步，如果k=len2，则查找到，count+；如果没查找到，重新进行第一步。void delstringword(char *s,char *str) /*删除字符串*s中的字符串*str*/ strpi jsfor(m=0;m<i;m+)tmpcount+=sm;for(n=j;n<len;n+)tmpcount+

7、=sn;tmp实现思想：从字符串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)为结尾，当tmp0=5时，发现输入 E，则退出输入。输出时文章时，如果tmpstrlen(tmp)-1=5即发现表示结束的字符E，用p->datastrlen(tmp)-1='0'除去最后一个控制符 E。第4章 核心

8、代码分析1.typedef struct line char *data; struct line *next;LINE; /*创建一链表，同时向里面输入文本数据*/2./*统计字母数*/int CountLetter(LINE * &head) LINE *p=head; int count=0;do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<Len;i+)if(p->datai>='a'&&p->datai<='z'

9、)|(p->datai>='A'&&p->datai<='Z') /*计算字母数*/count+; while(p=p->next)!=NULL); /*遍历 链表*/return count; /*返回文章的字母总数*/*统计数字数*/int CountNumber(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<Len;i+) i

10、f(p->datai>=48 && p->datai<=57)count+;/*计算数字数，ASCII码*/ while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计空格数*/int CountSpace(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<Len;i+) if(p->datai=32)count+;

11、 /*计算空格数，空格ASCII码为32*/ while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计文章的总字数*/int CountAll(LINE * &head) LINE *p=head; /*保存链表的首地址*/ int count=0; do /*计算总字符数*/ count+=strlen(p->data); while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计str在文章中出现的次数*/int FindString(LINE * &head,c

12、har *str) LINE *p=head; int count=0; int h=0; int len1=0; /*保存当前行的总字符数*/ int len2=strlen(str); /*待统计字符串的长度*/ int i,j,k; do len1=strlen(p->data); /*当前行的字符数*/for(i=0;i<len1;i+) /*字符匹配*/ if(p->datai=str0)k=0; for(j=0;j<len2;j+) if(p->datai+j=strj) k+;if(k=len2)count+;i=i+k-1; while(p=p-&

13、gt;next)!=NULL); /*遍历 链表*/ return count;第5章 复杂度分析本算法的空间复杂度很低，空间复杂度为O(N)。但是本算法的时间复杂度比较高，输出函数、查找函数算法时间复杂度均为O（N），但是删除函数算法的时间复杂度较高。我暂时还问想到时间复杂度更小的算法，因此在这里我无法对该算法进行优化。第6章 总结为期一周的课程设计结束了，在这一周里我完成了编写文本编辑程序的任务。任务书上要求是对输入的信息进行操作，自己开始是不知道该向什么方向去努力，自己应该如何去编写这个程序，后来通过对照着任务书上的要求和到网上查找相关资料，慢慢找到了感觉。所以自己在整个课程设计的编写程

14、序过程中遇到的困难及问题都通过查阅资料、向老师提问得以解决。本次课程设计自己最大的体会就是不管写什么程序，自己首先得对这个问题要分析透彻，要知道自己要干什么，然后才能让自己干什么。通过本次课程设计，我学到了很多：增强了查阅相关参考资料的能力，独立分析解决问题的能力；自己的上机动手的能力和对课程设计的理解，得到很多启示；课程设计为我们提供了一个即动手又动脑、独立实践的机会，将课本上的知识理论和实际有机的结合起来，锻炼了我们的分析解决实际问题的能力。这次课程设计使我我对数据逻辑结构的特点和存储表示方式的有了更深的了解和认识，培养了我在具体应用中选择合适的数据结构和存储结构的能力，同时也使我认识到自

15、己在学习编程方面还有很多的不足。今后我要多读一些纺织方面的书籍，不能只拘泥于课本上的知识，并注重理论与实践的结合，多上机练习编写程序，提高自己的实际动手能力和独立思考的能力，不断充实自己，更好的掌握编程思想。参考文献1 严蔚敏、吴伟民主编，数据结构（C语言版），清华大学出版社，2002。2 殷人昆等著，数据结构（C+版），清华大学出版社，2001。3 金远平著，数据结构（C+描述），清华大学出版社，2005。4 许卓群等著，数据结构与算法，高等教育出版社，2004。5 Frank M.Carrano等著,数据结构与+高级教程，清华大学出版社，2004。6 严蔚敏、吴伟民著，数据结构习题集（C语

16、言版），清华大学出版社。附录一：源代码：#include<iostream.h>#include <string.h>#include <stdio.h> /*文本每行以字符串形式存储，行与行之间以链表存储*/typedef struct line char *data; struct line *next;LINE; /*创建一链表，同时向里面输入文本数据*/void Create(LINE * &head) printf ("请输入一页文章，以Ctrl+E(E)为结尾(每行最多输入80字符!):n");LINE *p=new

17、LINE; /*首先为链表 建立一个附加表头结点*/ head=p; /*将p付给 表头指针*/ char tmp100; while(1) gets(tmp); /*输入字符串！*/ if(strlen(tmp)>80) printf("每行最多输入80字符"); break; if(tmp0=5)break; /*如果发现输入 E，则退出输入*/ p=p->next=new LINE; p->data=new charstrlen(tmp)+1; /*为结点分配空间 */ strcpy(p->data,tmp); if(tmpstrlen(tmp

18、)-1=5) /*除去最后一个控制符 E */ p->datastrlen(tmp)-1='0' break; p->next=NULL; /*最后的一个指针为空 */ head=head->next;/*统计字母数*/int CountLetter(LINE * &head) LINE *p=head; int count=0;do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<Len;i+)if(p->datai>='a'&

19、;&p->datai<='z')|(p->datai>='A'&&p->datai<='Z') /*计算字母数*/count+; while(p=p->next)!=NULL); /*遍历 链表*/return count; /*返回文章的字母总数*/*统计数字数*/int CountNumber(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p->data); /*计算当前 data 里的数据元

20、素的个数*/ for(int i=0;i<Len;i+) if(p->datai>=48 && p->datai<=57)count+;/*计算数字数，ASCII码*/ while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计空格数*/int CountSpace(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<

21、Len;i+) if(p->datai=32)count+; /*计算空格数，空格ASCII码为32*/ while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计文章的总字数*/int CountAll(LINE * &head) LINE *p=head; /*保存链表的首地址*/ int count=0; do /*计算总字符数*/ count+=strlen(p->data); while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计str在文章中出现的次数*/

22、int FindString(LINE * &head,char *str) LINE *p=head; int count=0; int h=0; int len1=0; /*保存当前行的总字符数*/ int len2=strlen(str); /*待统计字符串的长度*/ int i,j,k; do len1=strlen(p->data); /*当前行的字符数*/for(i=0;i<len1;i+) /*字符匹配*/ if(p->datai=str0)k=0; for(j=0;j<len2;j+) if(p->datai+j=strj) k+;if(k

23、=len2)count+;i=i+k-1; while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*删除指定的字符串*/void delstringword(char *s,char *str) /* *s为输入的字符串，*str为将要删除的字符*/char *p=strstr(s,str); /*从字符串s中寻找str第一次出现的位置*/ char tmp80; int len=strlen(s); int i=len-strlen(p); int j=i+strlen(str); int count=0; for(int m=0;m<i;m+)tmpcount+=sm; for(int n=j;n<len;n+)tmpcount+=sn; tmpcount='0' strcpy(s,tmp); /*返回新的字符串*/void DelString(LINE * &head,char *str) LINE *p=head; do if(strstr(p->data,str)!=NULL)delstringword(p->data,str);