行文本编辑算法思想(堆栈)！

ゝ一世哀愁。 2022-05-08 07:04 129阅读 0赞

**问题:在本文内输入一段字符，计算机不可能直接就将用户输入的字符写入文本，肯定要先建立一个缓存区，待用户修改完毕后，再写入。假设当用户输入abcde时发现多写了一个e，继续输入退格(\#)。。。等等。利用堆栈即可实现。**

**算法:假设这里只处理两种特殊的字符，退格字符\#和清除上一行字符@,那么只需要将除上述两个字符以外的其他字符依次入栈，当接收到\#字符时则出栈一个元素(即相当于删除一个),当接收到@字符时则将栈清空，依次这么循环。但需要注意，这样的循环是建立在文本指针没到EOF和'\\n'的情况下，当这个循环完成后，说明指针到了EOF或者说用户输入了换行符，而无论如何都得先在文本内写入这个'\\n'(在DOS中输入回车后上一行是不能改的,说明用户确定了此次输入)，再次判断是否到EOF，若是结束，若不是则继续循环。内循环外主要是处理一下出现回车符的情况，避免用户已经换行了而输入一个@后直接被全删除了这种BUG。**

#include <stdio.h>
    #include <malloc.h>
    #include <process.h>
    #define S_SIZE 100   //栈的空间大小
    #define STACKINCREAMENT 10//增加空间
    struct SqStack{
    	int *base; //栈底
    	int *top;  //栈顶
    	int stacksize;   //栈当前的存储空间
    };
    	FILE *fp;//全局文件指针
    void main()
    {//子函数声明
    	void InitStack(SqStack &S);//初始化空栈
    	void push(SqStack &S,int e);//进栈
        void pop(SqStack &S,int &e);//出栈
    	void clearstack(SqStack &S);        //清空栈
    	void destroystack(SqStack &S);      //销毁栈
        int StackEmpty(SqStack S);         //判空
    	void LineEdit();
    	//主函数开始
        fp=fopen("test.txt","w");
    	if(fp)
    	{   LineEdit();
    		fclose(fp);
    		printf("写入成功，请查看！");}
    	else
    		printf("写入失败！");
    }
    void InitStack(SqStack &S)
    {S.base=(int *)malloc(S_SIZE*sizeof(int));
    S.stacksize=S_SIZE;
    S.top=S.base;//初始化空栈
    }
    void push(SqStack &S,int e)
    {//进栈
    	if(S.top-S.base>=S.stacksize)
    	{S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int));
    	S.top=S.base+S.stacksize;
    	S.stacksize+=STACKINCREAMENT;}
    	*(S.top)=e;
    	S.top++;	  }
    void pop(SqStack &S,int &e)
    {//出栈
    	if(S.base!=S.top)
    	{S.top--;
    	e=*S.top;}
    }
    void clearstack(SqStack &S)
    {S.top=S.base;}//清空栈
    void destroystack(SqStack &S)
    {free(S.base);//销毁指针，释放内存
     S.base=NULL;
     S.top=NULL;
     S.stacksize=0;
    }
    int StackEmpty(SqStack S)
    {
    	if(S.base==S.top)
    		return 1;
    	else
    		return 0;
    }
    void LineEdit()
    {
    	SqStack s;char ch;int e;
    	InitStack(s);
    	printf("请输入一段文本以^Z作为结束:\n");
    	ch=getchar();
    	while(ch!=EOF)
    	{
    		while(ch!=EOF && ch!='\n')
    		{
    			switch(ch)
    			{
    			case '#':if(!StackEmpty(s))
    						 pop(s,e);
    				break;  //弹出一个
    			case '@':clearstack(s);break;   //清空一行
    			default :push(s,ch);//其他字符则入栈
    			}
    			ch=getchar();
    		}
    		//将当前栈中所有元素写入文本
    		//上面的循环结束说明要么到了文本结尾，要么有换行字符
    		while(s.base<s.top)
    		{
    			fputc(*s.base++,fp);
    		}
    		fputc('\n',fp);
    		clearstack(s);
    		if(ch!=EOF)
    			ch=getchar();
    	}
    }

**![1355556813_4736.jpg][]![1355556816_8517.jpg][]**

[1355556813_4736.jpg]: https://img-my.csdn.net/uploads/201212/15/1355556813_4736.jpg
[1355556816_8517.jpg]: https://img-my.csdn.net/uploads/201212/15/1355556816_8517.jpg