数据结构基础详解(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

相关文章
|
1月前
|
存储 编译器 C语言
C语言存储类详解
在 C 语言中,存储类定义了变量的生命周期、作用域和可见性。主要包括:`auto`(默认存储类,块级作用域),`register`(建议存储在寄存器中,作用域同 `auto`,不可取地址),`static`(生命周期贯穿整个程序,局部静态变量在函数间保持值,全局静态变量限于本文件),`extern`(声明变量在其他文件中定义,允许跨文件访问)。此外,`typedef` 用于定义新数据类型名称,提升代码可读性。 示例代码展示了不同存储类变量的使用方式,通过两次调用 `function()` 函数,观察静态变量 `b` 的变化。合理选择存储类可以优化程序性能和内存使用。
142 82
|
3天前
|
存储 C语言
C语言中的浮点数存储:深入探讨
C语言中的浮点数存储:深入探讨
|
1月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
1月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
12月前
|
存储 缓存 C语言
数据结构——双链表(C语言)
数据结构——双链表(C语言)
|
4月前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
29 2
|
4月前
|
算法 C语言
数据结构——单向链表(C语言版)
数据结构——单向链表(C语言版)
42 2
|
5月前
|
存储 缓存 程序员
初阶数据结构之---顺序表和链表(C语言)
初阶数据结构之---顺序表和链表(C语言)
|
11月前
|
测试技术 C语言
数据结构单链表的实现(C语言)
数据结构单链表的实现(C语言)
24 0
|
5月前
|
存储 C语言
数据结构之单链表详解(C语言手撕)
数据结构之单链表详解(C语言手撕)
85 1