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

前言

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

文章目录

    • 什么是栈
    • 栈的代码实现
      • 数组栈
      • 链式栈
    • 栈的应用
      • 求和存储数据的二进制
      • 表达式求值详解
        • 中缀表达式
        • 后缀表达式
        • 中缀转后缀

什么是栈

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

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

两个重要概念：

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

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

数组栈结构如下：

在这里插入图片描述

其中：

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

链式栈结构：

在这里插入图片描述

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

栈的代码实现

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;   // 栈顶初始值为 -1
	return 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;   // 栈顶初始值为 -1
	return 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+43
		if (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 +输出：
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/920968.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

数据结构之一：复杂度

数据结构之一：复杂度

相关代码&#xff1a;SData/test_22/main.c Hera_Yc/bit_C_学习 - 码云 - 开源中国 数据结构&#xff1a;在内存当中存储、组织数据的方式。&#xff08;顺序表、链表、栈、队列、树等&#xff09;。 算法&#xff1a;与数据结构配合使用&#xff0c;是对数据的处理。&#…
阅读更多...
【鸿蒙技术分享：探索 HarmonyOS 开发之旅】

【鸿蒙技术分享：探索 HarmonyOS 开发之旅】

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
Houdini和Blender如何使用CPU云渲染

Houdini和Blender如何使用CPU云渲染

近期&#xff0c;渲染101云渲染农场在产品和服务方面进行了重要更新&#xff0c;进一步提升了我们平台的渲染能力和兼容性&#xff0c;助力各位用户高效完成创作。云渲码6666 渲染101云渲码6666 1. Houdini和Blender支持CPU云渲染 我们不断拓展云渲染的工具和平台支持&#x…
阅读更多...
02 —— Webpack 修改入口和出口

02 —— Webpack 修改入口和出口

概念 | webpack 中文文档 | webpack中文文档 | webpack中文网 修改入口 webpack.config.js &#xff08;放在项目根目录下&#xff09; module.exports {//entry设置入口起点的文件路径entry: ./path/to/my/entry/file.js, }; 修改出口 webpack.config.js const path r…
阅读更多...
网络编程 作业1

网络编程 作业1

1.c #include <myhead.h> #define IP "192.168.60.45" #define PORT 6666 #define BACKLOG 100 void fun(int sss) {if(sssSIGCHLD){while(waitpid(-1,NULL,0)>0);}} int main(int argc, const char *argv[]) {//1.捕获子进程退出时的信号if(signal(SIGCHL…
阅读更多...
【2024亚太杯亚太赛APMCM C题】数学建模竞赛｜宠物行业及相关产业的发展分析与策略｜建模过程+完整代码论文全解全析

【2024亚太杯亚太赛APMCM C题】数学建模竞赛｜宠物行业及相关产业的发展分析与策略｜建模过程+完整代码论文全解全析

第一个问题是&#xff1a;请基于附件 1 中的数据以及你的团队收集的额外数据&#xff0c;分析过去五年中国宠物行业按宠物类型的发展情况。并分析中国宠物行业发展的因素&#xff0c;预测未来三年中国宠物行业的发展。 第一个问题&#xff1a;分析中国宠物行业按宠物类型的发展…
阅读更多...
外排序中的归并排序

外排序中的归并排序

外排序中的归并排序 7.11 外排序中的归并排序相关基础知识原理最终参考程序 7.11 外排序中的归并排序 外部排序&#xff1a;数据元素太多不能同时放在内存中&#xff0c;根据排序过程的要求不能在内外存之间移动数据的排序。&#xff08;下文也称外排序&#xff09; 例如 1 G…
阅读更多...
wsl2中kali linux下的docker使用教程（教程总结）

wsl2中kali linux下的docker使用教程（教程总结）

一、前言 上一篇关于kali linux的文章是图形界面的配置&#xff0c;这里作者准备补充两点&#xff0c;一点是在使用VNC时&#xff0c;如果F8不能用的话&#xff0c;可以试试AltF8&#xff1b;然后就是VNC在初始化设置时的三个设置选项依次是密码、再输一次以及设置仅观看密码。…
阅读更多...
Linux系统使用valgrind分析C++程序内存资源使用情况

Linux系统使用valgrind分析C++程序内存资源使用情况

内存占用是我们开发的时候需要重点关注的一个问题&#xff0c;我们可以人工根据代码推理出一个消耗内存较大的函数&#xff0c;也可以推理出大概会消耗多少内存&#xff0c;但是这种方法不仅麻烦&#xff0c;而且得到的只是推理的数据&#xff0c;而不是实际的数据。 我们可以…
阅读更多...
【通俗理解】ELBO（证据下界）——机器学习中的“情感纽带”

【通俗理解】ELBO（证据下界）——机器学习中的“情感纽带”

【通俗理解】ELBO&#xff08;证据下界&#xff09;——机器学习中的“情感纽带” 关键词提炼 #ELBO #证据下界 #变分推断 #机器学习 #潜变量模型 #KL散度 #期望 #对数似然 第一节&#xff1a;ELBO的类比与核心概念【尽可能通俗】 ELBO&#xff0c;即证据下界&#xff0c;在…
阅读更多...
【pyspark学习从入门到精通14】MLlib_1

【pyspark学习从入门到精通14】MLlib_1

目录 包的概览 加载和转换数据 在前文中&#xff0c;我们学习了如何为建模准备数据。在本文中&#xff0c;我们将实际使用这些知识&#xff0c;使用 PySpark 的 MLlib 包构建一个分类模型。 MLlib 代表机器学习库。尽管 MLlib 现在处于维护模式&#xff0c;即它不再积极开发…
阅读更多...
业务架构、数据架构、应用架构和技术架构

业务架构、数据架构、应用架构和技术架构

TOGAF(The Open Group Architecture Framework)是一个广泛应用的企业架构框架&#xff0c;旨在帮助组织高效地进行架构设计和管理。 TOGAF 的核心就是由我们熟知的四大架构领域组成:业务架构、数据架构、应用架构和技术架构。 企业数字化架构设计中的最常见要素是4A 架构。 4…
阅读更多...
阿里巴巴官方「SpringCloudAlibaba全彩学习手册」限时开源！

阿里巴巴官方「SpringCloudAlibaba全彩学习手册」限时开源！

最近我在知乎上看过的一个热门回答&#xff1a; 初级 Java 开发面临的最大瓶颈在于&#xff0c;脱离不出自身业务带来的局限。日常工作中大部分时间在增删改查、写写接口、改改 bug&#xff0c;久而久之就会发现&#xff0c;自己的技术水平跟刚工作时相比没什么进步。 所以我们…
阅读更多...
后端数据增删改查基于Springboot+mybatis mysql 时间根据当时时间自动填充，数据库连接查询不一致，mysql数据库连接不好用

后端数据增删改查基于Springboot+mybatis mysql 时间根据当时时间自动填充，数据库连接查询不一致，mysql数据库连接不好用

目录 后端数据增删改查Springboot 实体&#xff08;entity&#xff09;类引进添加UserMapper接口 创建对用的UserController注意数据库查询不一致新增数据更新删除postman测试 后端数据增删改查 基于之前构建系统&#xff0c;实现用户数据的CRUD。 打开navicat16&#xff0c;…
阅读更多...
堆外内存泄露排查经历

堆外内存泄露排查经历

优质博文&#xff1a;IT-BLOG-CN 一、问题描述 淘宝后台应用从今年某个时间开始docker oom的量突然变多&#xff0c;确定为堆外内存泄露。 后面继续按照上一篇对外内存分析方法的进行排查(jemalloc、pmap、mallocpmap/mapsNMTjstackgdb)&#xff0c;但都没有定位到问题。至于…
阅读更多...
WebSocket详解、WebSocket入门案例

WebSocket详解、WebSocket入门案例

目录 1.1 WebSocket介绍 http协议&#xff1a; webSocket协议&#xff1a; 1.2WebSocket协议&#xff1a; 1.3客户端&#xff08;浏览器&#xff09;实现 1.3.2 WebSocket对象的相关事宜&#xff1a; 1.3.3 WebSOcket方法 1.4 服务端实现 服务端如何接收客户端发送的请…
阅读更多...
Vue3 源码解析（三）：静态提升

Vue3 源码解析（三）：静态提升

什么是静态提升 Vue3 尚未发布正式版本前&#xff0c;尤大在一次关于 Vue3 的分享中提及了静态提升&#xff0c;当时笔者就对这个亮点产生了好奇&#xff0c;所以在源码阅读时&#xff0c;静态提升也是笔者的一个重点阅读点。 那么什么是静态提升呢&#xff1f;当 Vue 的编译器…
阅读更多...
C++优选算法十四 优先级队列（堆）

C++优选算法十四 优先级队列（堆）

C 中的优先级队列&#xff08;Priority Queue&#xff09;是一种容器适配器&#xff0c;它提供队列的功能&#xff0c;但元素不是按照插入的顺序被访问&#xff0c;而是根据它们的优先级被访问。默认情况下&#xff0c;优先级队列是一个最大堆&#xff08;Max-Heap&#xff09;…
阅读更多...
综合练习--轮播图

综合练习--轮播图

本篇博客将教大家实现一个基础的轮播图。 源代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0&qu…
阅读更多...
“AI玩手机”原理揭秘：大模型驱动的移动端GUI智能体

“AI玩手机”原理揭秘：大模型驱动的移动端GUI智能体

作者&#xff5c;郭源 前言 在后LLM时代&#xff0c;随着大语言模型和多模态大模型技术的日益成熟&#xff0c;AI技术的实际应用及其社会价值愈发受到重视。AI智能体&#xff08;AI Agent&#xff09;技术通过集成行为规划、记忆存储、工具调用等机制&#xff0c;为大模型装上…
阅读更多...
最新文章

Copyright @ 2022~2023