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

简介: 本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。

@[toc]

栈的应用

1.栈的括号匹配

问题分析:
问题还是很简单就是,利用栈的特性,左括号进栈,右括号出栈实现匹配,在栈空且所有括号都扫过一遍后结束
image.png

代码实战:

南京理工大学上机题目

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

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

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

输出格式
如果输入的字符串中的括号正确匹配则输出 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 中缀表达式改写为后缀表达式(手算)

  • 从左到右的找符号,找到合适的符号就把符号两边的操作数和符号写成后缀表达式的形式
    image.png

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

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

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

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

类似于中缀表达式改写为后缀表达式,只是遵循的是右优先原则

类似于后缀表达式的计算,但是是从右边开始依次入栈,遇到符号出栈.....

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

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

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

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

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

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

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

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

3.矩阵的压缩存储

3.1 对称矩阵的压缩存储

对称矩阵
image.png

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

    (1+n)*n/2

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

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

3.2 三角矩阵的压缩存储

下三角矩阵和上三角矩阵

压缩存储策略:按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

按行优先的原则,a~i~,~j~是第几个元素(注意是第几个元素)跟对称矩阵是一样的,当i<j的时候就是那个常数c,即n(n+1)/2

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

什么是三对角矩阵?
image.png

按行优先的原则,a~i~,~j~是第几个元素

前i-1行共3(i-1)-1个元素
a~i~,~j~是i行第j-i+2个元素
a~i~,~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 存储方法二 十字链表法

image.png

相关文章
|
20小时前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
14天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
14天前
|
存储 安全 数据库
除了 HashMap,还有哪些数据结构可以实现键值对存储?
【10月更文挑战第11天】 除了`HashMap`,其他常见支持键值对存储的数据结构包括:`TreeMap`(基于红黑树,键有序)、`LinkedHashMap`(保留插入顺序)、`HashTable`(线程安全)、`B-Tree`和`B+Tree`(高效存储大量数据)、`SkipList`(通过跳跃指针提高查找效率)及`UnorderedMap`(类似`HashMap`)。选择合适的数据结构需根据排序、并发、存储和查找性能等需求。
|
2天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
14天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
12 0
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
20天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
19天前
初步认识栈和队列
初步认识栈和队列
47 10
|
20天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
34 3
|
18天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
54 1