栈的基本操作

2023-10-05 10:08:40

栈的基本操作（必做，设计性实验）

实验目的
熟练掌握栈的抽象数据类型，能在相应的应用问题中正确选用它，熟练掌握栈的实现方法（顺序和链式），两种存储结构和基本操作的实现算法，注意空和满的判断条件及它们的描述方法。深入了解栈的特性，能在实际问题的背景下灵活运用他们，并加深对这种结构的理解。
实验内容
用栈实现形如a+b&b+a@的中心对称的字符序列的检验。
数据结构定义
采用了栈来存储数据，采用了栈的先进后出的特性，充分利用了此特性进行存储我们需要的字符序列。栈是限定仅在表尾进行插入删除操作的线性表。定义了一个栈，包含了头指针，尾指针，以及栈的长度，方便进行下一步的操作。
算法思想及算法设计
先用数据结构栈来记录&前面的序列（根据此题的特性，后进先出为中心对称的特性）
在& 前面所有数据全部进栈之后，一一出栈与接下来接受的序列相比较，最终得出结果。

Status bijiao()
{
 Stack a; //初始化栈操作
 a.base = a.top = new SElemType[STACK_INIT_SIZE];
 a.StackSize = 0;

 char chs = getchar();
 while (chs != '&')
 {
   //进行入栈操作：
   if (a.StackSize > STACK_INIT_SIZE)
   {
     cout << "OVERFLOW" << endl; //先进行判断，数据溢出的情况
     return OVERFLOW;
   }
   else
   {
     a.base[a.StackSize] = chs;
     a.StackSize++;
     a.top++;
   }
   chs = getchar();
 }
 chs = getchar(); //接受一个新的字符
 while (chs != '@')
 {
   if (a.StackSize == 0) //后面序列较长
   {
     cout << "序列并非中心对称，且后面序列较长" << endl;
     return FALSE;
   }

   ch = a.base[a.StackSize - 1]; //出栈操作
   a.StackSize--;
   a.top--;

   if (ch != chs) //序列不等的情况
   {
     cout << "序列不相等" << endl;
     return FALSE;
   }
   else
   {
     chs = getchar();
   }
 }
 if (a.StackSize > 0) //前面序列较长
 {
   cout << "序列并非中心对称，且前面序列较长" << endl;
   return FALSE;
 }
 else
 {
   cout << "序列为中心对称" << endl;
   return OK;
 }
}

实验代码

#include <stdio.h>
#include <iostream>
using namespace std;
#include "constant.h"
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType char
struct SqStack
{
   char *base;
   char *top;
   int StackSize;
};
typedef struct SqStack Stack;



  
#include "shujujiegou3.hpp"
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
 Stack a; //初始化栈操作
 a.base = a.top = new SElemType[STACK_INIT_SIZE];
 a.StackSize = 0;

 cout << "请输入要比对的字符序列,以&隔开，以@字符结束\n"
      << endl;
 char chs;
 chs = getchar();
 int i = 0;
 while (chs != '&')
 {
   //进行入展操作：
   if (a.StackSize > STACK_INIT_SIZE)
   {
     cout << "OVERFLOW" << endl; //先进行判断
     return OVERFLOW;
   }
   else
   {
     a.base[a.StackSize] = chs;
     a.StackSize++;
     a.top++;
   }
   chs = getchar();
 }
 char ch;
 chs = getchar();
 while (chs != '@')
 {
   if (a.StackSize == 0) //后面序列较长
   {
     cout << "序列并非中心对称，且后面序列较长" << endl;
     return FALSE;
   }

   ch = a.base[a.StackSize - 1]; //出战操作
   a.StackSize--;
   a.top--;

   if (ch != chs) //序列不等的情况
   {
     cout << "序列不相等" << endl;
     return FALSE;
   }
   else
   {
     chs = getchar();
   }
 }
 if (a.StackSize > 0) //前面序列较长
 {
   cout << "序列并非中心对称，且前面序列较长" << endl;
   return FALSE;
 }
 else
 {
   cout << "序列为中心对称" << endl;
   return OK;
 }
}

分析与总结
（1）算法复杂度分析及优、缺点分析
算法时间复杂度为O（n），算法原理较为简单，只是将前面序列存储进栈，然后依靠栈的特性，对接下来的元素一一进行比较。缺点是可能会在出入栈操作时弄错。时间复杂度仍待优化。

（2）实验总结
在写代码过程中，本体出现4中情况，写代码的时候要考虑清楚之后在进行书写代码，防止后面把自己给弄迷了。要仔细的考虑全部可能出现的结果。还有对栈的操作更加清楚，例如如何入栈，如何保证数据能进去和出去，这两点很重要。我本次做实验的过程中就把入栈操作的S.stacksize++给省了，然后就出现了错误。

码农公寓

相关文章