当前位置: 首页 > news >正文

数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值特殊矩阵的压缩存储

文章目录

  • 栈的应用
    • 1.栈的括号匹配
    • 代码实战:
    • 问题分析:
    • 2.栈的表达式求值
      • 2.1 中缀、后缀、前缀表达式
      • 2.2 中缀表达式改写为后缀表达式(手算)
      • 2.3 后缀表达式的计算(手算)
      • 2.4 中缀表达式转前缀表达式(手算)和计算前缀表达式
      • 2.5后缀表达式的计算(机算)
      • 2.6 中缀表达式转后缀表达式(机算)
      • 2.7 中缀表达式的计算(栈实现)
  • 3.矩阵的压缩存储
    • 3.1 对称矩阵的压缩存储
    • 3.2 三角矩阵的压缩存储
    • 3.3 三对角矩阵(带状矩阵)
    • 3.4 稀疏矩阵压缩存储
      • 3.4.1 存储方法一 结构体方式存储
      • 3.4.2 存储方法二 十字链表法

栈的应用

1.栈的括号匹配

问题分析:
问题还是很简单就是,利用栈的特性,左括号进栈,右括号出栈实现匹配,在栈空且所有括号都扫过一遍后结束
在这里插入图片描述

代码实战:

南京理工大学上机题目

苗苗今天刚刚学会使用括号,不过他分不清小括号,中括号,大括号和尖括号,不知道怎么使用这些括号,请帮助他判断括号使用是否正确。

注意:不需要区分括号的优先级。

输入格式
共一行,包含一个由 <,(,{,[,>,),},] 构成的字符串。

输出格式
如果输入的字符串中的括号正确匹配则输出 yes,否则输出 no。

数据范围
输入字符串长度不超过 10000

输入样例:

(){}

输出样例:

yes

问题分析:

  • 想到用栈来实现括号匹配的问题
  • 第一步,肯定是实现栈的基础操作(当然为了简单快捷,选择静态存储的方式实现栈)
    • 栈的定义
    • 栈的初始化
    • 入栈
    • 出栈
    • 判空
  • 具体问题具体分析
    • 写一个括号匹配函数,模拟整个过程
    • 主函数中补上字符串的输入

完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MaxSize 100001
typedef struct{char data[MaxSize]; //静态数组存放栈中元素 int top;           // 栈顶元素 
}SqStack;void InitSqStack(SqStack &S)
{S.top=-1;
}bool StackEmpty(SqStack S)
{if(S.top==-1)return true;return false;
}bool Push(SqStack &S,char x)
{S.data[++S.top]=x;return true;
}bool Pop(SqStack &S,char &x)
{x=S.data[S.top--];return true;
}bool BracketCheck(char str[])
{SqStack S;InitSqStack(S);for(int i=0;i<strlen(str);i++)    //-1是因为fgets函数读入最后一个字符是/n要去掉 {if(str[i]=='<'||str[i]=='('||str[i]=='{'||str[i]=='[') //匹配到左括号 {Push(S,str[i]);}else                                                   //匹配到右括号 {	char x; Pop(S,x);if(str[i]=='>'&&x!='<')return false;if(str[i]==')'&&x!='(')return false;if(str[i]=='}'&&x!='{')return false;if(str[i]==']'&&x!='[')return false;}}return StackEmpty(S); //检索完全部括号后,栈空说明匹配成功
}
int main()
{char str[MaxSize];fgets(str,MaxSize,stdin);// 检查字符串的最后一个字符是否为换行符,并去除它  int len = strlen(str);  if (len >0&&str[len-1] =='\n') {  str[len-1] ='\0';  }  if(BracketCheck(str))printf("yes");else printf("no");
}

在这里插入图片描述

2.栈的表达式求值

2.1 中缀、后缀、前缀表达式

在学习栈的表达式求值之前 明确的概念

中缀表达式(符号在中间)

a+b
a+b-c

后缀表达式(符号在后边)

ab+
ab+c-

前缀表达式(符号在前边)

+ab
-+abc


引子:为学习计算机机算做铺垫,计算机更喜欢处理后缀表达式这种形式

2.2 中缀表达式改写为后缀表达式(手算)

  • 从左到右的找符号,找到合适的符号就把符号两边的操作数和符号写成后缀表达式的形式
    在这里插入图片描述

2.3 后缀表达式的计算(手算)

  • 从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算,合体为一个操作数
    在这里插入图片描述

从左往右我们发现,最后出现的操作数先被运算,想到栈这种数据结构

2.4 中缀表达式转前缀表达式(手算)和计算前缀表达式

类似于中缀表达式改写为后缀表达式,只是遵循的是右优先原则
在这里插入图片描述
类似于后缀表达式的计算,但是是从右边开始依次入栈,遇到符号出栈…

2.5后缀表达式的计算(机算)

  • 从左到右扫描,
  • 遇到操作数就入栈,遇到符号就将栈顶两个操作数出栈,符号计算完再入栈
  • 直到全部扫描一遍后,若表达式合法,最后栈中只会留下一个结果就是最后结果
    在这里插入图片描述

2.6 中缀表达式转后缀表达式(机算)

  • 遇到操作数,直接加入后缀表达式
  • 遇到界限符,遇到"(“直接入栈,直到遇见”)“,把此时”(“上面的所有运算符都依次出栈加入后缀表达式,注意”(“不加入,”)"也入栈
  • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到“(”或栈空则停止。之后再把当前运算符入栈。

2.7 中缀表达式的计算(栈实现)

本质就是将中缀表达式转后缀表达式和后缀表达式的计算结合起来

用栈实现中缀表达式的计算:
初始化两个栈,操作数栈和运算符栈若扫描到操作数,压入操作数栈
若扫描到运算符或界限符,则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈)

在这里插入图片描述

矩阵的压缩存储通过数组的形式来实现

3.矩阵的压缩存储

3.1 对称矩阵的压缩存储

对称矩阵
在这里插入图片描述

在这里插入图片描述

  • 对称矩阵大小存储的大小是多少

(1+n)*n/2

  • 按行优先的原则,ai,j是第几个元素(注意是第几个元素)

先算前面行一共有多少个,再加上当前的列坐标
1+2+3+…(i-1)再+j 个元素即i(i-2)/2+j个元素
如果是下标那就得-1

3.2 三角矩阵的压缩存储

下三角矩阵和上三角矩阵
在这里插入图片描述
压缩存储策略:按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c
在这里插入图片描述
按行优先的原则,ai,j是第几个元素(注意是第几个元素)跟对称矩阵是一样的,当i<j的时候就是那个常数c,即n(n+1)/2

3.3 三对角矩阵(带状矩阵)

什么是三对角矩阵?
在这里插入图片描述
主对角元素的矩阵,上下左右下标差值不等于1的情况下为0
在这里插入图片描述
按行优先的原则,ai,j是第几个元素

前i-1行共3(i-1)-1个元素
ai,j是i行第j-i+2个元素
ai,j是第2i+j-2个元素
如果数组下标从0开始 k=2i+j-3

若已知数组下标k,如何得到i, j ?

前i-1行共3(i-1)-1个元素
前i行共3i-1个元素
显然,3(i-1)-1 <k+1 ≤ 3i-1
在这里插入图片描述

3.4 稀疏矩阵压缩存储

稀疏矩阵:非零元素远远少于矩阵元素的个数
压缩存储策略:
顺序存储―一三元组<行,列,值>

3.4.1 存储方法一 结构体方式存储

定义一个结构体,存储i,j,v

3.4.2 存储方法二 十字链表法

在这里插入图片描述
在这里插入图片描述

相关文章:

数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值特殊矩阵的压缩存储

文章目录 栈的应用1.栈的括号匹配代码实战:问题分析:2.栈的表达式求值2.1 中缀、后缀、前缀表达式2.2 中缀表达式改写为后缀表达式(手算)2.3 后缀表达式的计算(手算)2.4 中缀表达式转前缀表达式&#xff08;手算)和计算前缀表达式2.5后缀表达式的计算(机算)2.6 中缀表达式转后缀…...

C# 关于多线程同步不同实现方式

栏目总目录 AutoResetEvent class MainClass {// the array of consumer threadsprivate static List<Thread> consumers new List<Thread> ();// the task queueprivate static Queue<Action> tasks new Queue<Action>();// the synchronisation o…...

【人工智能学习笔记】4_2 深度学习基础之多层感知机

感知机概述 感知机是人工智能最早的模型,是一种有监督的算法,本质上是一个二分类问题,是神经网络和支持向量机的基础缺点:感知机智能解决单纯的线性问题 感知机的过程 多层感知机的层级结构 多层感知机的层级结构主要包括输入层、隐藏层和输出层、可以用于拟合非线性函数。…...

WPS2019如何打出各种横线

WPS2019如何打出各种横线 测试于WPS2019...

Vue获取后端重定向拼接的参数

前言 比如我们要重定向这样一个连接&#xff1a; http://192.168.2.189:8081?nameadmin springboot重定向&#xff1a; Vue获取&#xff1a; getParam(param) {var reg new RegExp("(^|&)" param "([^&]*)(&|$)");var r location.searc…...

vscode spring boot项目编辑yaml不自动提示补全如何解决

文章目录 properties能够自动弹出提示但是YAML文件就不会自动弹出提示ctrl空格不出提示的解决办法 properties能够自动弹出提示 但是YAML文件就不会自动弹出提示 只是不会自动弹出来而已&#xff0c;按ctrl空格即可解决 ctrl空格不出提示的解决办法 如果按ctrl空格没有用 …...

算法练习题19——leetcode141环形链表

题目描述 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&a…...

基于人类反馈的强化学习概述

文章目录 RLHF 概述人类反馈数据的收集由于对齐标准难以通过形式化的优化目标进行建模,因此研究人员提出了基于人类反馈的强化学习(Reinforcement Learning from Human Feedback, RLHF),引入人类反馈对大语言模型的行为进行指导。我们将首先介绍基于人类反馈的强化学习的整…...

【SIT1463Q】带振铃抑制功能的CAN收发器,替代TJA1463

【SIT1463Q】带振铃抑制功能的CAN收发器&#xff0c;替代TJA1463 SIT1463Q核心亮点&#xff1a; 满足ISO11898-2:2016高速CAN规范的物理层要求和CiA601-4&#xff1a;2019 SIC规范要求。 支持高达8Mbps的数据速率。 更稳定的位时序&#xff0c;比特对称性增强&#xff0c;降低…...

CCF刷题计划——坐标变换(其二)(前缀和)

坐标变换&#xff08;其二&#xff09; 首先我按照一般的逻辑写出来&#xff0c;居然超时了&#xff1f;&#xff1f;&#xff1f; 之后想了想&#xff0c;还是觉得大有可为的&#xff0c;对拉伸前缀积&#xff0c;对旋转前缀和成功解决问题。 80分&#xff1a;超时 #inclu…...

游戏开发简述

《黑神话&#xff1a;悟空》爆红后&#xff0c;游戏开发一时成为热点。作为个人或小公司&#xff0c;能否进入游戏开发领域。从纯技术角度而言&#xff0c;并不是可望不可即&#xff1a; 另&#xff1a;学会了&#xff0c;哪怕自己干不成&#xff0c;招游戏开发的岗位也不少&am…...

最新前端开发VSCode高效实用插件推荐清单

在此进行总结归类工作中用到的比较实用的、有助于提升开发效率的VSCode插件。大家有其他的好插件推荐的也欢迎留言评论区哦&#x1f604; 基础增强 Chinese (Simplified) Language Pack: 提供中文界面。 Code Spell Checker: 检查代码中的拼写错误。 ESLint: 集成 ESLint&…...

分布式调度方案:Elastic-Job

文章目录 一、什么是分布式调度二、Elastic-Job 介绍三、Elastic-Job 实战3.1 环境搭建3.1.1 本地部署3.1.2 服务器部署3.1.3 Zookeeper 管控台界面 3.2 入门案例3.3 SpringBoot 集成 Elastic-Job3.4 任务分片&#xff08;★&#xff09;3.5 Dataflow 类型调度任务 一、什么是分…...

网络安全工程师(白帽子)企业级学习路线

第一阶段&#xff1a;安全基础&#xff08;入门&#xff09; 第二阶段&#xff1a;Web渗透&#xff08;初级网安工程师&#xff09; 第三阶段&#xff1a;进阶部分&#xff08;中级网络安全工程师&#xff09;...

数据结构详细解释

数据结构 1. 线性数据结构 数组&#xff08;Array&#xff09; 定义&#xff1a;数组是一种固定大小的、元素类型相同的线性数据结构。元素在内存中是连续存储的&#xff0c;可以通过索引直接访问。 特点&#xff1a; 支持常数时间的随机访问&#xff08;O(1)&#xff09;。…...

7.1图像平移

目录 实验原理 示例代码&#xff11; 运行结果&#xff11; 示例代码&#xff12; 运行结果&#xff12; 实验原理 OpenCV中&#xff0c;图像平移是一种基本的几何变换&#xff0c;指的是将图像中的每一个像素点沿着水平方向或垂直方向移动一定的距离。图像平移不改变图像…...

海外云手机是否适合运营TikTok?

随着科技的迅猛发展&#xff0c;海外云手机逐渐成为改变工作模式的重要工具。这种基于云端技术的虚拟手机&#xff0c;不仅提供了更加便捷、安全的使用体验&#xff0c;还在电商引流和海外社媒管理等领域展示了其巨大潜力。那么&#xff0c;海外云手机究竟能否有效用于运营TikT…...

IT 行业中常见的专业名称及其含义

API&#xff08;Application Programming Interface&#xff09; API 是应用程序编程接口&#xff0c;定义了不同软件系统之间如何互相通信的规则和方式。开发人员使用 API 将应用程序与外部服务集成&#xff0c;进行数据交换或调用外部功能。 IDE&#xff08;Integrated Deve…...

全球开店,Shopee东南亚入驻指南|用友BIP电商通引领电商出海新潮流

在全球化的浪潮中&#xff0c;东南亚市场以其蓬勃的发展态势成为中国企业出海的首选之地。得益于其语言、物流、仓储、距离及政策的友好性&#xff0c;东南亚市场已成为企业海外拓展的必争之地。作为东南亚领先的电商平台&#xff0c;Shopee以其庞大的用户基础和高度的用户活跃…...

java当中什么是NIO

Java中的NIO&#xff08;Non-blocking I/O&#xff09;即非阻塞I/O&#xff0c;是Java 1.4中引入的一种新的I/O API&#xff0c;用于替代传统的I/O&#xff08;即BIO, Blocking I/O&#xff09;。与传统的阻塞式I/O相比&#xff0c;NIO提供了更高效的I/O操作&#xff0c;特别是…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...