四川大学软件学院实验报告课程名称数据结构实验课时8 实验项目文本编辑器实验时间12到14周实验目的了解c++类的封装和KMP算法。
实验环境Windows平台 VC6.0++实验内容（算法、程序、步骤和方法）部分函数创建思想：创建过程如下：a、定义LinkList指针变量*temp: LinkList *temp;b、定义文本输入变量ch，记录文本行数变量j，记录每行字符数变量i；c、申请动态存储空间：head->next=(LinkList *)malloc(sizeof(LinkList));d、首行头指针的前驱指针为空：head->pre=NULL;首行指针：temp=head->next;首行指针的前驱指针也为空：temp->pre=NULL;定义没输入字符时文章长度为0：temp->length=0;初始化为字符串结束标志，防止出现乱码：for(i=0;i<80;i++)temp->data[i]='\0';e、利用循环进行文本输入for(j=0;j<LINK_INIT_SIZE;j++)// 控制一页{ for(i=0;i<80;i++) //控制一行{ ch=getchar(); //接收输入字符temp->data[i]=ch; //给temp指向的行赋值····temp->length++;//行中字符长度加1if(ch=='#'){NUM=j; break; //文章结束时，Num来记录整个文章的行数}}}在字符输入的过程中，如果在单行输入的字符超过了80个字符，则需要以下操作：输入字符数大于80，重新分配空间建立下一行temp->next=(LinkList *)malloc(sizeof(LinkList)) ;给temp的前驱指针赋值：temp->next->pre=temp;temp指向当前行：temp=temp->next;将下一行初始化为字符串结束标志，防止出现乱码：for(i=0;i<80;i++)temp->data[i]='\0';记录整个文章的行数：temp->row=NUM+1;返回指向最后一行指针：return temp;文本输入部分到此结束。
实验流程图：menuchangegetline BmeSearchdelete_ch add_charchar display Endmain程序清单Header file#include<iostream>#include<string>using namespace std;int* get_next(char* T, int* next);//声明get_next函数以获取next数组。
int KMP(char *S, char *T);//声明KMP函数调用next函数来进行查找。
int get_choice();//选择要执行的功能。
void serach(string S);//定义查找函数，用于进行字符串查找。
void add_char(string &S);//定义添加函数，用于进行字符串添加。
void change(string &S);//定义替换函数，将修改指定位置上的字符为新指定的字符。
void delete_char(string &S);//定义删除函数，将用于删除指定位置上的字符。
void display(string &S);//显示函数，用于显示当前的字符串。
C++soure file#include"textedit.h"using namespace std;int* get_next(const char* T, int* next){//根据T字符串将所得到的next数组值存在next指针指向的数组中int i = 0, j = -1;int length = strlen(T);int *temp = next;*next = -1;while(i< length){if(j==-1 || *(T+i)==*(T+j)){//如果字符串中第i个字符与从头起第j个相同，则i,j分别向后移一位i++;j++;if(*(T+i)!=*(T+j))//当遇到第一个不相等的字符时，当前的j值就是next数组第i个元素的值*(next+i)=j;else*(next+i)=*(next+j); //如果相等，则从字符串开始第j个元素的next值与当前位置的值相同}elsej=*(next+j); //如果遇到第i个元素和从头起第j个元素不相同，则从第j个元素的next值的位置开始比较，即回溯}return temp;}int KMP(string S, string T){int S_Length = S.length();int T_Length = T.length();if( S_Length < T_Length) //如果目标串比要查找的串要短，直接返回失败return 0;int i = 0, j = 0;int* next = new int[T_Length];get_next(T.c_str(), next);while(i < S_Length && j < T_Length){if(j == -1 || *(S.c_str()+i) == *(T.c_str()+j)){ //如果对应i，j号元素相同，则依次向后错一位，否则通过next函数，将j指针回溯一定距离。
i++;j++;}elsej=*(next+j);}if(j>=T_Length)//实际上当j==T_Length时，即意味着查找成功，返回开始字符所在的位置，否则返回失败return i-T_Length+1;return 0;}int get_choice() //获取用户输入的选项，以进行相应操作。
{int temp;cout<<"请输入你即将执行的操作：\n1--查找\t2--添加\t3--替换\n4--删除\t5--显示当前字符串\t6--退出\n你的选择：";while(true){cin>>temp;if(temp<7&&temp>0)//只有输入1、2、3、4、5、6时候才会返回输入的选项。
return temp;else{cout<<"你的输入有误，请重新输入\n你的选择：";}}}void serach(string S){int k;string T;cout<<"请输入要查找的串：";cin.sync();//清空缓存区，否则将自动读入输入选项时候按下的回车键。
getline(cin,T);if(k=KMP(S,T))//KMP的返回值不为0即查找成功时候,if条件判断认为是真。
cout<<"所要查找的字符串从第"<<k<<"个字符开始。
"<<endl;elsecout<<"查找失败"<<endl;}void add_char(string &S){int k;string m;cout<<"请输入你想插入的位置：";while(true){cin>>k;if(k>=0&&k<=S.length())//插入的位置不能在字符串外面。
break;elsecout<<"你输入的位置有误。
请重新输入你想插入的位置：";}cout<<"请输入你要插入的字符串:";cin.sync();//同前getline(cin,m);S=S.insert(k,m); //将字符串m插到S的第k个位置上。
}void change(string &S){//调用String类中将第k个字符到第m个字符替换为新字符串的函数。
int k,m;string temp;cout<<"请输入由第几个字符开始替换：";while(true){cin>>k;if(k<S.length()&&k>=0)//起始位置必须小于长度且不能等于{cout<<"替换至第几个字符：";while(true){cin>>m;if(m<=S.length()&&m>k)//结尾位置必须不能大于字符串长度，并且不能小于起始位置。
break;elsecout<<"输入有误，请重新输入结尾:";}break;}elsecout<<"输入有误，请重新输入开头:";}cout<<"请输入要替换成的字符串：";cin.sync();getline(cin,temp);S.replace(k,m,temp); //将目标串替换至指定位置。
}void delete_char(string &S){int k,m;cout<<"请输入从第几个字符开始删：";while(true){cin>>k;if(k<S.length()&&k>=0)//若k==S.length()，则下面无法删除0个。
{cout<<"删除的字符个数为：";while(true){cin>>m;if((k+m)<=S.length()&&m>0)//同前，删除的最后一个字符的位置不能超出字符串的长度。
break;elsecout<<"输入有误，请重新输入个数:";}break;}elsecout<<"输入有误，请重新输入开始位置:";}S=S.erase(k,m);}void display(string &S){cout<<"当前的字符串为："<<endl;cout<<S.data()<<endl;}void main(){int choice;string S;cout<<"请输入一个字符串："<<endl;getline(cin,S);while(true){choice = get_choice();switch(choice){case 1:serach(S);break;case 2:add_char(S);break;case 3:change(S);break;case 4:delete_char(S);break;case 5:display(S);break;default: exit(0);}}}实验内容（算法、程序、步骤和方法）数据记录和计算结论（结果）基本达到了实验的要求。