C 栈模板及笔记

文章目录

• ​​Intro​​
• ​​1. 熟练掌握栈的定义、特性和栈的抽象数据类型，​​

• ​​定义​​

• ​​是 限定 仅在队尾 进行插入或删除操作的 先行比爱​​

• ​​特性​​

• ​​表尾端 栈顶 top​​
• ​​后进先出 原则​​

• ​​抽象数据类型​​

• ​​P57​​

• ​​2. 栈与递归的关系​​

• ​​递归​​

• ​​定义是递归的​​

• ​​存在一个函数 过程 数据结构 定义的内部 直接或者间接 出现定义本身的应用， 则称为递归的​​
• ​​阶乘 分治法​​

• ​​数据结构是递归的​​

• ​​LNode 结点 由 data next 组成，而next本身是一种指向LNode 的指针 即LNode定义中调用了自身， 所以连表示一种递归的数据结构​​
• ​​链表 二叉树​​

• ​​问题的解法是递归的​​

• ​​问题本身没有明显的递归结构，但是递归求解比迭代求解更加简单​​
• ​​Hanoi 八皇后 迷宫​​

• ​​关系​​

• ​​函数执行中，需要多次自我调用​​
• ​​调用函数和被调用函数之间的连接及信息交换需要通过栈来进行​​
• ​​多个函数嵌套调用时，按找“先调用后返回”的原则，函数之间的信息传递和控制转移必须由 栈 来进行，及系统将整个程序运行时所需要的数据空间安排在一个栈当中，没调用一个函数就在站定分配一个储存区，当一个函数退出时，就是放它的储存区，则当前执行的函数的数据必然在栈顶​​

• ​​顺序栈​​
• ​​链表栈​​
• ​​进制转换​​
• ​​括号匹配​​
• ​​DevLog​​

Intro

1. 熟练掌握栈的定义、特性和栈的抽象数据类型，

定义

是 限定 仅在队尾 进行插入或删除操作的 先行比爱

特性

表尾端 栈顶 top

后进先出 原则

抽象数据类型

P57

2. 栈与递归的关系

递归

定义是递归的

存在一个函数 过程 数据结构 定义的内部 直接或者间接 出现定义本身的应用， 则称为递归的

阶乘 分治法

数据结构是递归的

LNode 结点 由 data next 组成，而next本身是一种指向LNode 的指针 即LNode定义中调用了自身， 所以连表示一种递归的数据结构

链表 二叉树

问题的解法是递归的

问题本身没有明显的递归结构，但是递归求解比迭代求解更加简单

Hanoi 八皇后 迷宫

关系

函数执行中，需要多次自我调用

调用函数和被调用函数之间的连接及信息交换需要通过栈来进行

多个函数嵌套调用时，按找“先调用后返回”的原则，函数之间的信息传递和控制转移必须由 栈 来进行，及系统将整个程序运行时所需要的数据空间安排在一个栈当中，没调用一个函数就在站定分配一个储存区，当一个函数退出时，就是放它的储存区，则当前执行的函数的数据必然在栈顶

顺序栈

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXSIZE 100

typedef int Status;
typedef int Elem;

typedef struct sqStack
{
  int len;
  Elem *base;
  Elem *top;
}sqStack;

Status InitStack(sqStack &s)
{
  s.base = new Elem[MAXSIZE];
  if (!s.base) return 0;

  s.top = s.base;
  s.len = MAXSIZE;

  return 1;
}

Status Push(sqStack &s,Elem e)
{
  if (s.top - s.base == s.len) return 0; //满
  else *s.top++ = e;

  return 1;
}

Status Pop(sqStack &s, Elem &e)
{
  if (s.top == s.base) return 0; //空
  else e = *--s.top;

  return 1;
}

Status GetTop(sqStack &s)
{
  if (s.top != s.base) 
    return *(s.top - 1); //满意的写法 *了

  else return 0;
}

int main()
{
  sqStack s;
  //1
  InitStack(s);

  //1
  Push(s,1);
  
  //1
  cout << GetTop(s);

  //1
  Elem e;
  Pop(s, e);

  cout << e;
}

链表栈

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXSIZE 100

typedef int Status;
typedef int Elem;

typedef struct sqStack
{
  int len;
  Elem *base;
  Elem *top;
}sqStack;

Status InitStack(sqStack &s)
{
  s.base = new Elem[MAXSIZE];
  if (!s.base) return 0;

  s.top = s.base;
  s.len = MAXSIZE;

  return 1;
}

Status Push(sqStack &s,Elem e)
{
  if (s.top - s.base == s.len) return 0; //满
  else *s.top++ = e;

  return 1;
}

Status Pop(sqStack &s, Elem &e)
{
  if (s.top == s.base) return 0; //空
  else e = *--s.top;

  return 1;
}

Status GetTop(sqStack &s)
{
  if (s.top != s.base) 
    return *(s.top - 1); //满意的写法 *了

  else return 0;
}

int main()
{
  sqStack s;
  //1
  InitStack(s);

  //1
  Push(s,1);
  
  //1
  cout << GetTop(s);

  //1
  Elem e;
  Pop(s, e);

  cout << e;
}

进制转换

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXSIZE 100

typedef int Status;
typedef int Elem;

typedef struct sqStack
{
  int len;
  Elem *base;
  Elem *top;
}sqStack;

Status InitStack(sqStack &s)
{
  s.base = new Elem[MAXSIZE];
  if (!s.base) return -1;

  s.top = s.base;
  s.len = MAXSIZE;

  return 1;
}

Status Push(sqStack &s, Elem e)
{
  if (s.top - s.base == s.len) return -1;
  else *s.top++ = e;

  return 1;
}

Status Pop(sqStack &s, Elem &e)
{
  if (s.top == s.base) return -1;
  else e = *--s.top;

  return 1;
}

Status GetTop(sqStack &s)
{
  if (s.top != s.base)
    return *(s.top - 1);

  else return -1;
}

Status StackEmpty(sqStack &s)
{
  if (s.top == s.base)
    return 1;

  else return 0;
}

Status conversion(sqStack &s, int n, int key) //书上代码根本不对劲 你不觉得吗？ 改了一下 
{
  InitStack(s);

  while (n)
  {
    Push(s, (n%key));
    n /= key;
  }

  while (!(StackEmpty(s)))// StackEmpty 没有这个代码 自己补充 其实也很好想
  {
    Elem e;
    Pop(s, e);
    cout << e;
  }

  return 1;
}

int main()
{
  sqStack s;

  conversion(s, 10, 2);
}

括号匹配

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXSIZE 100

typedef int Status;
typedef char Elem;

typedef struct sqStack
{
  int len;
  Elem *base;
  Elem *top;
}sqStack;

Status InitStack(sqStack &s)
{
  s.base = new Elem[MAXSIZE];
  if (!s.base) return -1;

  s.top = s.base;
  s.len = MAXSIZE;

  return 1;
}

Status Push(sqStack &s, Elem e)
{
  if (s.top - s.base == s.len) return -1;
  else *s.top++ = e;

  return 1;
}

Status Pop(sqStack &s, Elem &e)
{
  if (s.top == s.base) return -1;
  else e = *--s.top;

  return 1;
}

Elem GetTop(sqStack &s)
{
  if (s.top != s.base)
    return *(s.top - 1);

  else return -1;
}

Status StackEmpty(sqStack &s)
{
  if (s.top == s.base) //什么叫真正的简洁.....
    return 1;

  else return 0;
}

Status Marchting(sqStack &s)
{
  InitStack(s);
  int flag = 1;
  char ch;
  cin >> ch;
  while (ch != '#' && flag) //！= # 的话 直接拿‘#’ 作为终止符了 
  {
    char tmp;
    switch (ch)
    {
    case '[':
    case '(':
      Push(s, ch);
      break;
    case ')':
      if (!StackEmpty(s) && GetTop(s) == '(')
        Pop(s, tmp);
      else flag = 0; //如果前一个不匹配 就没必要执行了 必然不是嘛
      break;
    case ']':
      if (!StackEmpty(s) && GetTop(s) == '[')
        Pop(s, tmp);
      else flag = 0;
      break;;
    }
    cin >> ch;
  }
  if (StackEmpty(s) && flag)
    return 1;

  else return 0;
}
int main()
{
  sqStack s;

  //[]# [()]# [)#
  cout << Marchting(s);
}

DevLog

sqStack 中 感觉很顺利
不得不说 我他妈逐渐原谅了 书上的代码
仔细看看(并不是很仔细) 也挺有道理的

&s 直接改变本身 这个还是想提一下
&e 直接返回给自己

Elem *base; Elem *top; 两个指针的用法与好处还是非常明显 毕竟我之前用顺序栈的时候都是直接刚过去… 那想过这个

*s.top++ = e; 这种简写方式 初看也是有点蛋疼的 真牛皮啊 不得不想起 >>1 这种蛋疼操作

进制转换部分

在输出结果部分一直出错 一支无输出结果
神奇
排查之后 发现是 while (!(StackEmpty(s))) 返回结果
-1 取反 为0
真实
太真实了

Status StackEmpty 空时 返回值改为 return 0 就OK

就这都坑了我半小时？…

另外 书上的 Status conversion(int N) 感觉不全
改为

Status conversion(sqStack &s, int n, int key)
{
  InitStack(s);

  while (n)
  {
    Push(s, (n%key));
    n /= key;
  }

  while (!(StackEmpty(s)))
  {
    Elem e;
    Pop(s, e);
    cout << e;
  }

  return 1;
}

书上 无 StackEmpty(s) 添加为

Status StackEmpty(sqStack &s)
{
  if (s.top == s.base)
    return 1;

  else return 0;
}

3.括号匹配
这个题 好理解 是真的好理解
看输入 选择 加flag 关门
但是我犯了几个小错误 不得不提

3.1 视频代码 的 ‘（’||‘[’是错误的！

3.2 真的要加break 不然我 pop 连续两下 人都傻了

3.3 原本我是 Status GetTop 这里有问题 返回值 所以我改成了 Elem GetTop 啊 以前感觉是装逼用的 elem 现在察觉真好用啊 大家一次解决

理解是理解啊 看着是真麻烦