BUAA数据结构第四次编程题——文本编辑操作模拟（简）a
看前须知
题目内容
问题描述
编写一程序模拟文本编辑操作。首先从标准输入读取一行字符串（字符个数不超过512），该行字符串是已经过n（大于0，小于等于10）步编辑操作后的结果。然后从下一行读取n，以及已发生过的n步编辑操作，编辑操作分行输入，输入格式为：
op pos str
其中op为编辑操作命令编码（在此只有插入和删除操作，1表示插入或2表示删除操作）；pos表示插入或删除的位置；str表示已经插入或删除的字符串（中间没有空格）。各数据间以一个空格分隔。
然后在空一行后，再分行输入当前将要进行的编辑操作，包括如下四种操作（操作编码分别为：1表示插入，2表示删除操作，3表示撤销（即undo操作），-1表示结束）：
1 pos str
表示将在pos位置插入字符串str（中间没有空格），各数据间以一个空格分隔；
2 pos n
表示将从pos位置开始删除n个字符（各数据间以一个空格分隔），若要删除的字符个数多于已有字符个数（即在文本中从pos开始的字符个数小于n），则按实际字符数删除即可。（提示：为了能够撤销删除操作，应按“2 pos str”形式保存命令。）
3
表示撤销最近执行的插入或删除操作，可以进行多次撤销操作，注意：也可以撤销之前已经发生过的n步编辑操作中的操作。
-1
表示退出编辑操作，在屏幕上输出最终编辑后的文本。
要求：
1、上述所有输入的编辑操作中的字符串str都不包含空白字符（空格符、制表符或换行符）；
2、插入操作中的位置pos大于等于0，并且小于等于当前文本的字符个数；0位置表示文本第一个字符的位置；若pos为当前文本的字符个数，则表示在文本最后插入字符串；
3、删除操作中的位置pos大于等于0，并且小于当前文字的字符个数；
4、若已无操作可撤销，则再进行撤销操作无效；
5、文本在编辑过程中，总字符个数不会超过512。
输入形式
先从键盘输入一行字符串，表示已经经过n步编辑操作后的文本串，然后在下一行输入一个正整数n，并分行输入n步插入或删除操作（表示按时间先后顺序已进行的操作），格式如上所述。随后空一行，再分行输入将要进行的编辑操作，格式如上所述。直到输入-1操作为止。
输出形式
在屏幕上输出最终编辑后的文本内容。
样例
【样例输入】
A Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle.???
4
1 20 ainer
2 0 ???
1 85 -
1 99 (LIFO)
3
2 110 10
1 110 Objects
2 98 1
2 0 1
2 108 10
3
3
3
-1
【样例输出】
A Stack is a container of objects that are inserted and removed according to the last-in first-out principle.Objects
样例说明
第一行输入的文本串是先后经过下面4次编辑操作后得到的：先在20位置插入了字符串ainer，然后删除了开始位置的字符串???，随后在85位置插入了一个字符-，最后在99位置插入了字符串(LIFO)。
随后输入了撤销操作，即撤销先前最后进行的“1 99 (LIFO)”操作，也就是将99位置的6个字符删除；
2 110 10：将文本串最后的字符串???删除；
1 110 Objects：在文本串末尾插入字符串Objects；
随后执行了三次删除操作，又执行了三次撤销操作，最后输入的-1表示编辑操作结束，在屏幕上输出最终编辑后的文本串。
题解
易错点和难点
本题介绍两种方法：
第一种是笔者采用的方法（含详细注释），我们知道对于撤回操作的处理其实使用栈来解决的，每一次撤回我们调用撤回时的函数就可以完成撤回操作。但是有没有不用动脑子的办法呢？当然有啊，我们直接把每一次操作完的句子存下来不就行了吗，相比于用栈来存储操作，我们为什么不能用栈来存储句子呢，需要撤回时，我们直接弹出上一步操作的句子不就完成了吗？当然这里也还需要特别小心的是，存储句子的这种行为对于前n部是没有用的，所以对于撤回时是不是前n部需要特别判断（判断存储句子的栈的栈顶是否为0），如果是前n部，我们再调用单独编写的函数不就行了吗，十分的简单。
第二种是大部分人用的，就是把前n部的操作和后面的操作何为一体，单独编写函数就行了。
参考代码
第一种：笔者的傻瓜代码
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<stdbool.h>
struct stack{
int op; //操作类型
int pos; //位置
char str[600]; //字符串
};
void insert(int pos,char *str); //操作n部后的插入函数
void del(int pos,char *str); //操作n部后的删除函数
void Delstring(int pos,char *str);//操作n部前的插入函数 ******注意与上面的不同
struct stack S[2000],SS[2000]; // S 是存储操作的内容 ， SS是存储上一步操作完成的句子*****注意
char s[1000],tmp[1000];
int top=0,topp=0; //top是S的 ，topp是SS的
int n,i,j,op;
int main()
{
gets(s); //读入字符串
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d %s",&S[i].op,&S[i].pos,S[i].str); //录入前n部操作
top++;
}
while(~scanf("%d",&op))
{
if(op==1)
{
S[top].op=1;
scanf("%d %s",&S[top].pos,S[top].str);
insert(S[top].pos,S[top].str); //插入
top++;
//puts(s);
}
else if(op==2)
{
S[top].op=1;
scanf("%d %s",&S[top].pos,S[top].str);
del(S[top].pos,S[top].str); //删除
top++;
//puts(s);
}
else if(op==3)
{
if(topp>0) //判断此时是否会回退的前n部操作 ，如果不会
{
top--; //退栈
topp--; //退栈
memset(s,0,sizeof(s));
strcpy(s,SS[topp].str); //把上一步的句子退回来
//puts(s);
}
else //判断此时是否会回退的前n部操作 ，如果是前n次操作
{
top--;
if(S[top].op==1)
{
Delstring(S[top].pos,S[top].str); //删除
//puts(s);
}
}
}
else if(op==-1)
{
break;
}
}
puts(s);
return 0;
}
void insert(int pos,char *str)
{
int l=strlen(s);
for(i=0;i<pos;i++)
tmp[i]=s[i];
strcat(tmp,str);
int ll=strlen(tmp);
for(i=pos,j=0;i<l;i++,j++)
tmp[ll+j]=s[i];
strcpy(SS[topp++].str,s); //注意同步拷贝
memset(s,0,sizeof(s));
strcpy(s,tmp); //注意同步拷贝
memset(tmp,0,sizeof(tmp));
}
void del(int pos,char *str)
{
int l=strlen(s);
for(i=0;i<pos;i++)
tmp[i]=s[i];
if(atoi(str)>=l-pos)
{
strcpy(SS[topp++].str,s); //注意同步拷贝
memset(s,0,sizeof(s));
strcpy(s,tmp); //注意同步拷贝
}
else
{
int ll=strlen(tmp);
for(i=pos+atoi(str),j=0;i<l;i++,j++)
tmp[ll+j]=s[i];
strcpy(SS[topp++].str,s); //注意同步拷贝
memset(s,0,sizeof(s));
strcpy(s,tmp); //注意同步拷贝
}
memset(tmp,0,sizeof(tmp));
}
void Delstring(int pos,char *str)
{
int l=strlen(s);
int ll=strlen(str);
for(i=0;i<pos;i++)
tmp[i]=s[i];
int lll=strlen(tmp);
for(i=pos+ll,j=0;i<l;i++,j++)
tmp[lll+j]=s[i];
memset(s,0,sizeof(s));
strcpy(s,tmp);
memset(tmp,0,sizeof(tmp));
}
第二种方法：其他大哥的代码（没有注释）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct operat{
int typ;
int pos;
char c[512];
}op_stack[22];
int top = -1;
int main(){
int n;
char txt[556];
gets(txt);
scanf("%d",&n);
for(int i=0;i<n;i++){
top++;
scanf("%d",&op_stack[top].typ);
scanf("%d",&op_stack[top].pos);
getchar();
scanf("%s",op_stack[top].c);
}
top++;
scanf("%d",&op_stack[top].typ);
while(op_stack[top].typ!=-1){
if(op_stack[top].typ==1){
scanf("%d",&op_stack[top].pos);
getchar();
scanf("%s",op_stack[top].c);
char tmp[556];
int i,j;
for(j=0;j<op_stack[top].pos;j++){
tmp[j]=txt[j];
}
for(i=0;i<strlen(op_stack[top].c);i++,j++){
tmp[j]=op_stack[top].c[i];
}
for(i=op_stack[top].pos;i<strlen(txt);i++,j++){
tmp[j]=txt[i];
}
tmp[j]='\0';
strcpy(txt,tmp);
}
else if(op_stack[top].typ==2){
scanf("%d",&op_stack[top].pos);
getchar();
int k;
scanf("%d",&k);
if(op_stack[top].pos+k-1>strlen(txt)){
k=strlen(txt) + 1 - op_stack[top].pos;
}
char tmp[556];
int i,j;
for(j=0;j<op_stack[top].pos;j++){
tmp[j]=txt[j];
}
for(i=op_stack[top].pos+k;i<strlen(txt);i++,j++){
tmp[j]=txt[i];
}
tmp[j]='\0';
for(i=0,j=op_stack[top].pos;j<op_stack[top].pos+k;j++,i++){
op_stack[top].c[i]=txt[j];
}
op_stack[top].c[i]='\0';
strcpy(txt,tmp);
}
else if(op_stack[top].typ==3){
top--;
if(op_stack[top].typ==1){
int k = strlen(op_stack[top].c);
char tmp[556];
int i,j;
for(j=0;j<op_stack[top].pos;j++){
tmp[j]=txt[j];
}
for(i=op_stack[top].pos+k;i<strlen(txt);i++,j++){
tmp[j]=txt[i];
}
tmp[j]='\0';
strcpy(txt,tmp);
top--;
}
else if(op_stack[top].typ==2){
char tmp[556];
int i,j;
for(j=0;j<op_stack[top].pos;j++){
tmp[j]=txt[j];
}
for(i=0;i<strlen(op_stack[top].c);i++,j++){
tmp[j]=op_stack[top].c[i];
}
for(i=op_stack[top].pos;i<strlen(txt);i++,j++){
tmp[j]=txt[i];
}
tmp[j]='\0';
strcpy(txt,tmp);
top--;
}
}
top++;
scanf("%d",&op_stack[top].typ);
}
puts(txt);
return 0;
}
补充测试的数据
测试点13这两点是对文本的先前的n次操作没有要求，主要考察的是对后面的操作以及撤销 而测试点245则是对文本的前n次操作有较多的考察，可能会一次性出现很多3。
输入1
20373623
0
1 2 3
1 2 3
1 2 3
1 2 6c
2 9 4
2 3 4
3
3
1 4 6
2 2 3
3
3
3
3
3
3
3
3
3
-1
输出1
20373623
输入2
A Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle.???
4
1 20 ainer
2 0 ???
1 85 -
1 99 (LIFO)
3
2 110 10
1 110 Objects
2 98 1
2 0 1
2 108 10
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
-1
输出2
A Stack is a contain objects that are inserted and removed according to the lastin first-out principle.???