数据结构文本编辑实验报告解读.docx

四川大学计算机学院 学生实验报告 实验名称：文本编辑 指导老师：孙界平 姓名： 学号：2015141461019 班级：物联网8班 日期：2016/12/15 实验题目： 文本编辑，字符串操作。 实验目的与要求： 实现对文本的插入、删除、替换、查找等功能。 掌握C++类的使用。 掌握字符串模式匹配算法，如简单字符串模式匹配算法，首尾字符串模式匹配算法，KMP字符串模式匹配算法等。 实验的环境： 1、Windows 8.1操作系统 2、Visual Studio 2015 编译器 3、C++库函数 4、x86计算机 算法描述： 在C++中，有string类，它是由char类型实现的一个类，可以表示一段字符，并且有着大量的库函数可以使用，非常方便，因此，我们可以采用它辅助构建我们自己的类，从而实现对字符串的操作，即对文本的编辑。 1、 mystring类 我们希望能够将我们想要作用在一个串中的操作（函数）封装在一个类中，从而能够非常方便地进行定义、实现。每次通过mystring类创建一个对象，通过对象可以获得一个string类的串（文本），对象可以使用类中的函数实现对该对象下的string类串进行操作。 如下是mystring类的定义： #ifndef MYSTRING_H #define MYSTRING_H #include string using namespace std; class mystring { public: mystring(); int search(string P);//查找 void exchange(int n,char s);//替换 void insert(int n,char s);//插入 void del(int n);//删除 void show();//输出 protected: string T;//主串 }; #endif 可以看到通过mystring的类，我们得到一个受保护的string类型主串“T”，也就是我们想要进行操作的文本。在公有类型中，有查找、替换、插入、删除以及输出函数，分别对主串“T”实现对应的操作。 2、 构造函数实现 对于类而言，每创建一个对象都需要有构造函数进行初始化。在mystring类中，构造函数主要是获得想要操作的串，运用getline()函数获得。 3、 查找函数实现 查找函数需要找到主串T中是否有子串P，采用简单字符串模式匹配算法。查找从P中第一个字符在T中第一次出现的位置开始，即第pos个字符。 首先将子串P从第0个字符起与主串T的第pos位字符起依次对应字符，若全部对应相等，则表明已经找到匹配，成功终止；否则，将子串P从第0个字符起与主串T的第pos+1个字符起依次比较对应字符，过程与之前类似。如此进行，直到某次成功匹配，或某次T中无足够剩余字符与P中各字符对应比较为止。（为实现一般性，可以初始化pos=0） 在某一趟匹配中，模式串P的所有字符都与目标串T中的对应字符相等，这是匹配成功，返回本趟匹配在目标串T中开始的位置，也就是模式串中P的第0个字符在目标串T中的位置。 P已经移动到最后可能与T比较的位置，但对应字符不是完全相同，则表示目标串T中没有出现与模式串P相同的子串，匹配失败，返回-1. int mystring::search(string P) { int i=0,j=0; while(iT.length() jP.length()) { if(T[i]==P[j]) { i++;j++; } else { i=i-j+1;j=0; } } if(j=P.length())return i-j+1;//匹配成功 else return -1;//匹配失败 } 4、 替换函数实现 替换串T中某个位置的字符，函数参数需要给出位置和替换上的字符。当给出的位置数据大于主串长度时，无法插入。当位置数据不大于长度时，直接替换即可。 5、 插入函数实现 函数参数给出插入的位置，我们在这里给出第n个字符，在它的前面插入字符。在n+1位置添加字符后，原先在第n位置后面的字符都向后移位。由于string是一个容器，大小空间不变，因此需要单独添加最后一个字符。幸运的是，string类中重载了运算符“=”和“+”，直接运用字符串T加上最后一个字符即可。 void mystring::insert(int n,char s) { int m=T.length(); char a=T[T.length()-1]; if(nT.length()) { cout无法插入; } else { fo