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

2024-09-11 381

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

@[toc]

栈的应用

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
按行优先的原则,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 三对角矩阵(带状矩阵)

什么是三对角矩阵?

按行优先的原则,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

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

栈的应用

1.栈的括号匹配

代码实战:

问题分析: