《数据结构》课程设计班级： 10计本2班姓名：邓寅森学号： 2010305202指导教师：杨老师完成日期： 2011年12月计算机科学与技术系课程设计评分表课程名称： 数据结构 简易文本编辑器教师签名：日期：一、需求分析1.1 问题描述传统的纸质文档已经不能满足大家的需求，有容易丢失、查找不方便等缺点。

计算机信息管理为人们的生活、工作提供了方便，提高了效率。

“简易文本编辑器”是为了帮助老师、同学或其他一些需要使用文本编辑的人员进行管理和分析的一种计算机应用程序。

1.2 基本任务通过用户调查分析及实际需求，系统需要实现如下基本任务：（1）输入数据信息建立文本；（2）查询文本中满足要求的信息；（3）插入新的信息到文本中；（4）删除不再需要的文本信息；(5) 查看所有的文本信息。

二、概要设计为了完成需求分析的基本任务，主要从以下3个方面进行设计：2.1 主界面设计为了实现简易文本编辑器的各项功能，设计了一个含有多个菜单项的主控菜单模块以操作系统的各项功能，以方便用户使用系统。

系统进入菜单运行界面如图所示：简易文本编辑器主菜单2.2 数据结构设计系统采用线性表的顺序存储结构表示和存储“简易文本编辑器”中的信息。

实现文本的输入，删除，插入，查找，显示功能。

2.3 系统功能设计运行程序，提示进入菜单，按“回车键”进入主菜单，再可以在主菜单上进行各项操作。

每次进入菜单，选择“1键”新建文本，然后才可以进行其他操作，或者按“0键”选择退出。

三、模块设计3.1 模块设计系统主要包含主程序模块和其它操作模块。

其调用关系如图所示。

模块调用示意图3.2 系统子模块及其功能设计本系统共设计了16个子模块，各程序的函数名及功能说明如下：1、/*由模式串nextval值*/void GetNextval(SqVString T,int nextval[])2、/*模式匹配KMP算法*/int KMPIndex(SqVString S,int pos,int next[],SqVString T)3、/*初始化串*/void InitString(SqVString *S,char *str)4、/*串插入*/int StrInsert(SqVString *S,int pos,SqVString T)5、/*串删除*/int StrDelete(SqVString *S,int pos,int len)6、/*求子串*/int SubStr(SqVString S,int pos,int len,SqVString *T)7、/*串连接*/int Concat(SqVString *S,SqVString T)8、/*串赋值*/int StrAssign(SqVString *S,char *value)9、void InputString() //新建10、void DeleteString()//删除11、void DeleteSubstring()//删除12、void InsertSubstring()//查找13、void DisplayString()//显示14、void cd()//进入界面15、void ts()//主菜单16、void tc()//退出3.3 系统模块之间的调用关系系统的16个子模块之间的主要调用关系所示：系统函数调用关系图四、详细设计4.1 数据结构设计系统采用线性表的顺序存储结构存储通讯录信息。

4.2 系统主要模块设计(1)建立文本模块，由void InitString(SqVString *S,char *str)函数实现。

该模块的算法思想是：○1按照给定的线性表存储空间的初始化分配量分配存储空间，若分配成功，则往下进行；○2令线性表长为0；○3令线性表当前存储容量为给定的线性表存储空间的初始化分配量。

该模块的算法描述如下：见源程序(2)查看文本中得所有记录，需要一个模式匹配intKMPIndex(SqVString S,int pos,int next[],SqVString T)函数实现。

该模块的算法思想是：在此略该模块的算法描述如下：见源程序（其它模块设计略）五、调试分析5.1、调试方法：首先打开Microsoft Visual C++ 6.0 ，运行程序，出现错误修改再运行，直至运行结果0 error ，0 warning结束。

接着进入程序界面，看程序能否实现所要求的各项功能，再作下一步的修改。

5.2、调试结果主菜单新建显示删除查找插入退出5.3、程序出现的问题：还有几个程序模块未能成功调用。

（其他问题见“第八项中未能解决的问题”）六、用户使用说明当用户打开程序，就会提示按【回车键】进入，按【回车键】则进入主菜单页面，进入主菜单，选择【1键】，新建文本信息，编辑好后，按照程序中的文字提示，返回到主菜单，此时在主菜单选择其他操作，当进入各项操作，均有提示。

每一操作完成，按【回车键】返回主菜单，选择【0键】，安全退出程序！七、参考文献《数据结构理论与实践》——杨永斌八、对所设计的软件进行自我评价，如创新点、未解决的问题等情况说明。

拿到该课程题目，准备仿照电脑上的文本编辑器写该程序，由于我所学不是扎实，于是就借助课本上所学的串与数组，写好了这个程序，程序能够正确的完成，程序充分包含了本学期的所学内容，体现了数据结构的特点。

继续沿用了清屏函数，是屏幕看起来很舒服，不至于那么杂乱。

未解决的问题：○1在完成插入，查找功能的时候，出现了问题，当程序执行到此处时，程序未能进入下一步，而是直接退出了。

○2当进入主菜单后，只能选择【1键】或者退出，这是未能得到优化的。

○3块移动（行块，列块移动），正确存盘、取盘；正确显示总行数等功能未能完成。

九、程序源代码：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#define STRSIZE 100#define MAXSTRING 60#define MAXLINE 24/*存储结构*/typedef struct{char*ch;int length;}SqVString;/*由模式串nextval值*/void GetNextval(SqVString T,int nextval[]){int j=0,k=-1;nextval[0]=-1;while(j<T.length){if(k==-1||T.ch[j]==T.ch[k]){j++;k++;if(T.ch[j]==T.ch[k])nextval[j]=nextval[k];elsenextval[j]=k;}elsek=nextval[k];}}/*模式匹配KMP算法*/int KMPIndex(SqVString S,int pos,int next[],SqVString T) {int i=pos,j=0,r;while(i<S.length && j<T.length){if(i<S.ch[i]==T.ch[j]){++i;++j;}else if(j==0)++i;elsej=next[j];}if(j>=T.length)r=i-T.length;elser=-1;return r;}/*初始化串*/void InitString(SqVString *S,char *str){int i;char *c;int len=0;c=str;while(*c!='\n'){len++;c++;}/*求str的长度*/S->ch=(char *)malloc(len *sizeof(char));/*申请动态数组空间*/ S->length=len;/*置串的当前长度*/for(i=0;i<S->length;i++)S->ch[i]=str[i];/*赋值串值*/}/*串插入*/int StrInsert(SqVString *S,int pos,SqVString T){int i;int len;if(pos<0 || pos>S->length){cout<<" \t\t插入位置不合法，其取值范围应该是[0,length]";return 0;}len=S->length+T.length;S->ch=(char *)realloc(S->ch,len *sizeof(char));if(!S->ch){cout<<" \t\t分配空间出错，无法完成串插入操作";return 0;}for(i=S->length-1;i>=pos;i--)S->ch[i=T.length]=S->ch[i];for(i=0;i<T.length;i++)S->ch[i+pos]=T.ch[i];S->length=len;return 1;}/*串删除*/int StrDelete(SqVString *S,int pos,int len){int i;int length;char *str;if(pos<0 || len<=0 || pos>S->length ||S->length<=0){cout<<" \t\t删除位置pos及删除长度len不合法，无法完成删除操作";return 0;}length=S->length-len;if(length<=0)length=pos;/*若pos+len大于串长，则从pos删到串尾*/str=(char *)malloc(length*sizeof(char));if(!str){cout<<" \t\t分配空间出错，无法完成串的删除操作";return 0;}for(i=0;i<pos;i++)str[i]=S->ch[i];for(i=pos+len;i<S->length;i++)str[i-len]=S->ch[i];free(S->ch);S->length=length;S->ch=str;return 1;}/*求子串*/int SubStr(SqVString S,int pos,int len,SqVString *T){int i;if(S.length<=0){cout<<" \t\t空串，无法完成求子串操作";return 0;}if(pos<0 || pos>S.length || len<=0){cout<<" \t\t子串位置pos及子串长度len不合法，无法完成求子串操作";return 0;}if(pos+len>S.length)len=S.length-pos+1;/*当子串长度超过主串长度，则只取到串尾即可*/ if(T->length)free(T->ch);/*释放S的原有空间*/T->ch=(char *)malloc(len *sizeof(char));if(!T->ch)cout<<" \t\t分配空间出错，无法完成求子串操作";return 0;}for(i=0;i<len;i++)T->ch[i]=S.ch[i+pos];T->length=len;return 1;}/*串连接*/int Concat(SqVString *S,SqVString T){int i;int len;len=S->length+T.length;S->ch=(char *)realloc(S->ch,len *sizeof(char));if(!S->ch){cout<<" \t\t分配空间出错，无法完成串连接操作";return 0;}for(i=0;i<T.length;i++)S->ch[i+S->length]=T.ch[i];S->length=len;return 1;}/*串赋值*/int StrAssign(SqVString *S,char *value){int count=0;int i;char *c;//S=(SqVString *)malloc(sizeof(SqVString));if(S->length!=0)free(S->ch);/*释放S的原有空间*/c=value;while(*c!='\n'){count++;c++;}/*求value的长度*/if(!count)/*value为空串*/S->ch=NULL;S->length=0;}else{S->ch=(char *)malloc(count);if(!S->ch){cout<<"\t\t分配空间出错，无法完成串赋值操作";return 0;}for(i=0;i<count;i++)S->ch[i]=value[i];S->length=count;}return 1;}SqVString *lines[MAXLINE];void InputString(){char buffer[MAXSTRING];SqVString *tmp;int LineNum=0;flushall();cout<<"\t\t================================================"<<endl;cout<<"\t\t 新建文本 "<<endl;cout<<"\t\t================================================"<<endl;cout<<"\t\t[请输入文本，每以回车结束，一段以#结束行]"<<endl;do{cin>>buffer;tmp=(SqVString *)malloc(sizeof(SqVString));InitString(tmp,buffer);lines[LineNum]=tmp;LineNum++;}while(buffer[0]!='#');// cout<<" \t\tOK...";}void DeleteString(){int i;cout<<"\t\t================================================"<<endl;cout<<"\t\t 删除文本 "<<endl;cout<<"\t\t================================================"<<endl;cout<<" \t\t请输入要删除行的行号:";cin>>i;free(lines[i-1]);while(lines[i]->ch[0]!='#'){lines[i-1]=lines[i];i++;}lines[i-1]=lines[i];cout<<" \t\tOK..."<<endl;}void InsertSubstring(){int i=0;int pos=0;char buffer[MAXSTRING];SqVString tmp;cout<<"\t\t================================================"<<endl;cout<<"\t\t 插入子串 "<<endl;cout<<"\t\t================================================"<<endl;cout<<" \t\t请输入子串所在的行号:";cin>>i;cout<<" \t\t请输入插入位置:";cin>>pos;cout<<" \t\t请输入子串值:";cin>>buffer;InitString(&tmp,buffer);StrInsert(lines[i],pos,tmp);cout<<" \t\tOK..."<<endl;}void DeleteSubstring(){int i=0;int pos=0;int len=0;cout<<"\t\t================================================"<<endl;cout<<"\t\t 删除子串 "<<endl;cout<<"\t\t================================================"<<endl;cout<<" \t\t请输入子串所在的行号:";cin>>i;cout<<"\n\t\t请输入删除的起始位置:";cin>>pos;cout<<" \t\t请输入删除的字符数:";cin>>len;StrDelete(lines[i],pos,len);cout<<"\t\t OK..."<<endl;}void FindSubstring(){int i=0;int pos=0;char buffer[MAXSTRING];int next[MAXSTRING];SqVString tmp;cout<<"\t\t================================================"<<endl;cout<<"\t\t 查找文本 "<<endl;cout<<"\t\t================================================"<<endl;cout<<" \t\t请输入要查找的子串:";cin>>buffer;InitString(&tmp,buffer);GetNextval(tmp,next);while(lines[i]->ch[0]!='#'){if((pos=KMPIndex(* lines[i],0,next,tmp))!=-1){cout<<" \t\t[子串"<<buffer<<" 在第"<<i+1<<" 行的"<<pos<<"位置上出现]"<<endl;return;}i++;}cout<<" \t\tOK..."<<endl;}void DisplayString(){int i=0;cout<<"\t\t================================================"<<endl;cout<<"\t\t 显示文本 "<<endl;cout<<"\t\t================================================"<<endl;while(lines[i]->ch[0]!='#'){cout<<lines[i]->ch<<endl;i++;}cout<<" \t\tOK..."<<endl;}void cd()//进入界面{cout<<endl<<endl;cout<<"\t\t"<<"____________________________________________"<<endl;cout<<"\t\t"<<"--------------------------------------------"<<endl;cout<<"\t\t"<<"♀欢·迎·使·用♀"<<endl;cout<<"\t\t"<<"♂————————————————————♂"<<endl;cout<<"\t\t"<<"→简易文本编辑器←"<<endl;cout<<"\t\t"<<"······················"<<endl;cout<<"\t\t"<<"--------------------------------------------"<<endl;cout<<"\t\t"<<"↓重庆工商大学派斯学院↓"<<endl;cout<<"\t\t"<<"↑计算机科学系↑"<<endl;cout<<"\t\t"<<"♀制作人: 10计本2班邓寅森♀"<<endl;cout<<"\t\t"<<"∶ 2011年11月∶"<<endl;cout<<"\t\t"<<"♂————————————————————♂"<<endl;cout<<"\t\t"<<"____________________________________________"<<endl;cout<<"\t\t"<<"→→→点击【回车】进入←←←"<<endl;cout<<"\t\t"<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;cout<<"\t\t";}void ts(){cout<<endl;cout<<"\t\t--------------------------------"<<endl;cout<<"\t\t 主菜单 "<<endl;cout<<"\t\t--------------------------------"<<endl;cout<<"\t\t 1、输入文本"<<endl;cout<<"\t\t 2、删除一行"<<endl;cout<<"\t\t 3、插入子串"<<endl;cout<<"\t\t 4、删除子串"<<endl;cout<<"\t\t 5、查找子串"<<endl;cout<<"\t\t 6、显示文本"<<endl;cout<<"\t\t 0、退出"<<endl;cout<<"\t\t--------------------------------"<<endl;cout<<"\t\t 注:进入本程序·请首先选择 1 "<<endl;cout<<"\t\t--------------------------------"<<endl;cout<<" \t\t请输入您的选择:";}void tc(){cout<<endl;cout<<"\t\t======================================="<<endl;cout<<"\t\t 安全退出·谢谢使用 "<<endl;cout<<"\t\t======================================="<<endl; }void main(){int choice;cd();getchar();system("cls");do{ts();cin>>choice;if(choice<0||choice>6)continue;switch(choice){case 1:system("cls"); InputString();break;case 2:system("cls");DeleteString();break;case 3:system("cls");InsertSubstring();break;case 4:system("cls");DeleteSubstring();break;case 5:system("cls");FindSubstring();break;case 6:system("cls");DisplayString();break;case 0:tc();exit(0);}getchar();system("cls");}while(1);}。