当前位置:首页 > 编程教程 > c++编程 > 链栈的实现并解决行编辑程序问题及问题总结

链栈的实现并解决行编辑程序问题及问题总结

2017-03-16 09:31:50[c++编程]点击数:作者:未知 来源: 网络
随机为您推荐的文章:C++重载、重写、重定义

此文描述了C++重载、重写、重定义的文章,具体方法请看介绍一、重载(overload) 指函数名相同,但是它的参数表列个数或顺序,类型不同。但是不能靠返回类型来判断。 (1)相同的范围(在同

1、栈的链式存储结构,也称为链栈,是一种限制操作的链表,即规定链表中的插入和删除操作只能在链表开头进行,链栈的实现与链表的实现基本相同,头结点作为栈顶位置。链栈结构如图:

链栈的实现并解决行编辑程序问题及问题总结

2、行编辑程序问题:在用户输入一行的过程中,允许用户输入出差错,并在发现有误时可以及时更正。

解决方法:设立一个输入缓冲区,用以接收用户输入的一行字符,然后逐行存入用户数据区,并假设“#”为退格符,“@”为退行符。

例:假设从终端接受了这样两行字符:

whli##ilr#e(s#*s)

outcha@putchar(*s=#++);

则实际有效的是下列两行:

while(*s)

putchar(*s++);

链栈的实现并用其解决行编辑程序问题,代码如下:

#include <stdio.h>
#include <stdlib.h>
#define ELEMTYPE char

typedef struct SNode
{
      ELEMTYPE data;         // 数据域
      struct Snode *next;     // 链域
}*LinkStack;

// 链栈的初始化
LinkStack InitStack()
{
      LinkStack S = (LinkStack)malloc(sizeof(struct SNode));
      S->next = NULL;
      return S;
}

// 判栈空
int IsEmpty(LinkStack S)
{
      if(S->next == NULL)
      {
            return 1;
      } else
      {
            return 0;
      }
}

// 压栈
int Push(LinkStack top, ELEMTYPE x)
{
      LinkStack temp = (LinkStack)malloc(sizeof(struct SNode));
      if(!temp)
      {
            printf("分配失败!\n");
            return 0;
      } else
      {
            temp->data=x;
            temp->next=top->next;         // 不可少,少了不成链
            top->next=temp;
            return 1;
      }
}

// 弹栈
int Pop(LinkStack top, ELEMTYPE *x)
{
      LinkStack temp;
      temp = top->next;
      if (temp == NULL)
      {
            printf("栈已空,无法弹栈!\n");
            return 0;
      } else
      {
            top->next = temp->next;             // 不可少,少了不成链
            *x=temp->data;
            free(temp);
            return 1;
      }
}

// 链栈的清空
void ClearStack(LinkStack S)
{
      LinkStack temp;
      while(S->next)
      {
            temp = S->next;
            S->next = temp->next;
      }
}

// 链栈的销毁
void DestroyStack(LinkStack S)
{
      LinkStack temp;
      while(S->next)
      {
            temp = S;
            S=S->next;
            free(temp);
      }
      free(S);
}

// 行编辑问题
void LineEdit(LinkStack S)
{
      ELEMTYPE c, ch;
      int i;
      ch=getchar();
      while(ch!=EOF)					  // 文件结束符(end of file),Windows下ctrl+Z表示EOF
      {
            ELEMTYPE s[100]={0};         // 声明的时候进行初始化,作为清空语句把垃圾内存清理成'\0',也就是0x00(0)。可滤掉乱码
            while(ch!='\n')
            {
                  switch(ch)
                  {
                  case '#':
                        if(!IsEmpty(S))
                              Pop(S, &c);
                        break;
                  case '@':
                        ClearStack(S);
                        break;
                  default:
                        Push(S, ch);
                        break;
                  }
                  ch = getchar();
            }
            printf("输入的有效内容为:\n");
            for (i=0; !IsEmpty(S); ++i)
            {
                  Pop(S, &c);               
                  s[i] = c;
            }
            for (i=strlen(s)-1; i>=0; --i)		// 利用数组将有效内容正序输出
                  printf("%c", s[i]);
            printf("\n");
            ClearStack(S);
            ch=getchar();
      }

}

int main()
{
      LinkStack S = InitStack();
      LineEdit(S);
      DestroyStack(S);

      return 0;
}

运行结果如图:

链栈的实现并解决行编辑程序问题及问题总结

3)、起初在外层while循环外声明数组s[],结果运行程序,测试几行字符串后,前几个输出还挺正常,后面的会出现乱码现象。这是因为字符串输出前没使用清空语句把垃圾内存清理成’\0’,也就是0x00(0),可以在声明的时候进行初始化为{0},所以把数组的声明初始化放在外层while循环里面,这样每次进入内层while循环之前就会清空垃圾内存,滤掉乱码,这是C语言的习惯。

4)、链栈的清空操作,不能用free,free掉就是将申请的内存还回去了,之后就无法再使用了,链栈的清空就是使栈顶指针指向表头就好了,原先压入的数据清不清除效果都一样。

 

 

以上就是链栈的实现并解决行编辑程序问题及问题总结的全文介绍,希望对您学习和使用c++编程开发有所帮助.

这些内容可能对你也有帮助

更多c++编程可查看c++编程列表页。

TAGS: 编辑   程序