数据结构C语言描述4(图文结合)--栈的实现,中序转后序表达式的实现

前言

• 这个专栏将会用纯C实现常用的数据结构和简单的算法；
• 有C基础即可跟着学习，代码均可运行；
• 准备考研的也可跟着写，个人感觉，如果时间充裕，手写一遍比看书、刷题管用很多，这也是本人采用纯C语言实现的原因之一；
• 欢迎收藏 + 关注，本人将会持续更新。

什么是栈

栈是一种运算受限的线性表，它限定只能在表的一端进行插入和删除操作。

栈0的结构特性是：后进先出LIFO ( Last In First Out)。栈又被称为后进先出表。

两个重要概念：

栈顶:允许插入和删除的一端称作栈顶；

栈底:不允许插入和删除的一端称作栈底。

---

数组栈结构如下：

其中：

• 栈底元素：a₁ ；
• 栈顶元素：a_n ；
• 入栈顺序：a₁, a₂, …, a_n 依次入栈;
• 出栈顺序：a_n, a_n-1, …, a₁，先入的后出 ，只能在栈顶进行插入和删除。

---

链式栈结构：

链式栈原理就是：头插入、头删除。

栈的代码实现

ADT抽象操作：

• 创建栈
• 入栈
• 出栈
• 获取栈顶元素
• 栈是否为空
• 栈元素个数

数组栈

解释：用数组模拟栈。

📦 栈封装

封装元素：

• 数据
• 数组当前能存储的最大大小(容量)
• 栈顶游标

typedef struct Stack {DataType* data;size_t maxSize;    // int top;
}Stack;

---

💳 创建栈与栈初始化

这个步骤目标：创建栈，并且初始化栈变量；

栈顶初始化：-1，入栈：++top，出战：top--

Stack* create_stack()
{Stack* stack = (Stack*)calloc(1, sizeof(Stack));assert(stack);stack->top = -1;   // 栈顶初始值为 -1return stack;
}

---

📌 入栈

操作：就是数组向后添加元素

注意：就是扩容操作，这里不够就**++10**

void push(Stack* stack, DataType data)
{assert(stack);// 扩容if (stack->top == stack->maxSize - 1) {DataType* temp = (DataType*)realloc(stack->data, (stack->maxSize + 10) * sizeof(DataType));assert(temp);stack->maxSize += 10;stack->data = temp;}stack->data[++stack->top] = data;
}

---

🔝 获取栈顶元素和出栈

获取栈顶：获取数组下标为top元素

出栈：top减1

DataType top(Stack* stack)
{assert(stack);return stack->data[stack->top];
}void pop(Stack* stack)
{assert(stack);stack->top--;
}

---

🚄 万金油函数

• 获取栈大小
• 栈是否为空

这两个操作，没什么难度，看代码即可；

bool empty(Stack* stack)
{assert(stack);return stack->top == -1;
}size_t size(Stack* stack)
{assert(stack);return stack->top + 1;
}

---

⚗️ 总代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int DataType;typedef struct Stack {DataType* data;size_t maxSize;int top;
}Stack;Stack* create_stack()
{Stack* stack = (Stack*)calloc(1, sizeof(Stack));assert(stack);stack->top = -1;   // 栈顶初始值为 -1return stack;
}void push(Stack* stack, DataType data)
{assert(stack);// 扩容if (stack->top == stack->maxSize - 1) {DataType* temp = (DataType*)realloc(stack->data, (stack->maxSize + 10) * sizeof(DataType));assert(temp);stack->maxSize += 10;stack->data = temp;}stack->data[++stack->top] = data;
}DataType top(Stack* stack)
{assert(stack);return stack->data[stack->top];
}void pop(Stack* stack)
{assert(stack);stack->top--;
}bool empty(Stack* stack)
{assert(stack);return stack->top == -1;
}size_t size(Stack* stack)
{assert(stack);return stack->top + 1;
}int main()
{Stack* stack = create_stack();for (int i = 1; i <= 10; i++) {push(stack, i);}printf("size: %llu\n", size(stack));while (!empty(stack)) {printf("%d ", top(stack));pop(stack);}putchar('\n');printf("size: %llu\n", size(stack));return 0;
}

链式栈

🌇 实现方式：采用无头链表；

🌙 模拟：采用链表的头插和弹出头，来模拟入栈和出栈操作。

---

📦 栈封装

节点封装

• 存储元素、指针指向下一个节点

链表封装

• 采用在封装写法，创建一个指针，指向头节点，同时定义size，存储当前栈的大小，是这个在封装写法的核心。🤔 为什么说size是核心变量？？，图示如下：

typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;typedef struct Stack {Node* headNode;int size;
}Stack;

---

🖍 封装创建节点和创建栈函数

Node* create_node(DataType data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}Stack* create_stack()
{Stack* stack = (Stack*)calloc(1, sizeof(Stack));assert(stack);return stack;
}

---

📌 元素入栈

在封装写法的核心是变量size，当size==0的时候，说明这个时候是链表为空，这个时候插入就是创建头节点，其他情况就是正常头插，这样引入变量也可以避免指针指向被修改的问题，不需要采用二级指针。

图：

// 头插
void push(Stack* stack, DataType data)
{assert(stack);Node* newNode = create_node(data);if (stack->size == 0) {stack->headNode = newNode;}else {newNode->next = stack->headNode;stack->headNode = newNode;}stack->size++;
}

---

🤕 出栈和获取栈顶元素

获取栈顶：就是获取头节点元素过程；

出战：删除头节点，要注意的就是栈为空的情况。

图示：

DataType top(Stack* stack)
{assert(stack);assert(stack->headNode);return stack->headNode->data;
}void pop(Stack* stack)
{assert(stack);if (stack->size == 0) {return;}else {Node* temp = stack->headNode;stack->headNode = stack->headNode->next;free(temp);temp = NULL;}stack->size--;}

---

💛 万金油函数

采用在封装写法对获取元素和判断是否为空，有着天然的优势，代码如下：

bool empty(Stack* stack)
{assert(stack);return stack->size == 0;
}int size(Stack* stack)
{assert(stack);return stack->size;
}

---

总代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>// 采用无头链表实现typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;typedef struct Stack {Node* headNode;int size;
}Stack;Node* create_node(DataType data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}Stack* create_stack()
{Stack* stack = (Stack*)calloc(1, sizeof(Stack));assert(stack);return stack;
}// 头插
void push(Stack* stack, DataType data)
{assert(stack);Node* newNode = create_node(data);if (stack->size == 0) {stack->headNode = newNode;}else {newNode->next = stack->headNode;stack->headNode = newNode;}stack->size++;
}DataType top(Stack* stack)
{assert(stack);assert(stack->headNode);return stack->headNode->data;
}void pop(Stack* stack)
{assert(stack);if (stack->size == 0) {return;}else {Node* temp = stack->headNode;stack->headNode = stack->headNode->next;free(temp);temp = NULL;}stack->size--;}bool empty(Stack* stack)
{assert(stack);return stack->size == 0;
}int size(Stack* stack)
{assert(stack);return stack->size;
}int main()
{Stack* stack = create_stack();for (int i = 1; i <= 10; i++) {push(stack, i);}while (!empty(stack)) {printf("%d ", top(stack));pop(stack);}return 0;
}

栈的应用

其实在开发中用栈，要不用封装好容器，要么用数组模拟，不会像上面那种方式手写。

求和存储数据的二进制

要求：求一个数的二进制

// 一般栈开发中都有容器，直接调用，哪怕是C语言也是简单的模拟，如下
void test_stack()
{// 用栈存储并打印 666 的二进制int stack[1024] = { 0 };   // 数组模拟栈int top = -1;              // 定义栈顶int num = 666;int t = num;while (t) {stack[++top] = ((t & 1) == 1) ? 1 : 0;  // 入栈t >>= 1;}// 输出和弹出栈顶while (top != -1) {printf("%d", stack[top--]);  // 获取栈顶与出栈}
}

表达式求值详解

中缀表达式

我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间。

后缀表达式

后缀表达式也叫作逆波兰表达式，对于“9+(3-1)×3+10÷2”，如果要用后缀表示法应该是什么样子：“9 3 1-3*+10 2/+”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。后缀表达式如何求解表达式的值？

• 遍历后缀表达式，如果遇到数字则直接入栈，如果遇到操作符，则弹出栈顶的两个元素，进行计算后将结果入栈。
• 最终，栈内剩余的元素就是整个表达式的计算结果。

中缀转后缀

操作流程

• 如果栈顶元素的优先级大于等于当前操作符，则先将栈顶元素弹出并输出到后缀表达式中，再将当前操作符压入栈中。
• 如果遇到了左括号，则直接将其压入栈中，如果遇到了右括号，则弹出栈中的元素，直到遇到了左括号为止，并将这些元素输出到后缀表达式中。
• 最后，将栈中剩余的元素依次弹出，并输出到后缀表达式中。

⏰ 代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>/*
* 中缀：a + b * (c + d) / e - f
* 后缀：a b + c d + * e / f -
*/#define MAX_SIZE 2014
char stack[MAX_SIZE];  // 定义栈
int top = -1;bool isdigits(char figure)
{return ((figure - '0' >= 0) && (figure - '0' <= 9));
}bool is_operator(char op)
{return op == '+' || op == '-' || op == '*' || op == '/';
}int pri_operator(char key)
{switch (key){case '+':case '-':return 1;case '*':case '/':return 2;}return 0;
}void midToLast(char* p, char* q)
{assert(p);assert(q);while (*p != '\0') {// 是数字 255+43if (isdigits(*p)) {  // 是数字while (isdigits(*p) || *p == '.') {*q = *p;p++;q++;}// 加空格，输出好看好一点*q = ' ';q++;}else if (is_operator(*p)) {    // 运算符if (top == -1) {   // 栈空stack[++top] = *p;p++;}else if (pri_operator(stack[top]) >= pri_operator(*p)) {   // 栈顶符号 优先即大于等于 当先运算符while (top != -1 && is_operator(stack[top])) {    // 弹出*q = stack[top--];    q++;// 加空格，输出好看好一点*q = ' ';q++;}}else {stack[++top] = *p;p++;}}else if (*p == '(') {stack[++top] = *p;p++;}else if (*p == ')') {while (top != -1 && stack[top] != '(') {*q = stack[top--];q++;// 加空格，输出好看好一点*q = ' ';q++;}if (top != -1) {  // 不是-1，就是左括号top--;}p++;}}// 剩余运算while (top != -1) {*q = stack[top--];q++;// 加空格，输出好看好一点*q = ' ';q++;}*q = '\0';
}int main()
{// 10 33 22 - 10 * + 12 4 / + 0.25 +char midExpression[MAX_SIZE] = { "10+(33-32)*10+12/4+0.25" };char lastExpression[MAX_SIZE * 2] = "";midToLast(midExpression, lastExpression);printf("%s\n", lastExpression);return 0;
}/*输出：
10 33 32 - 10 * + 12 4 / + 0.25 +输出：
*/