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

相关文章
|
2月前
|
存储 编译器 C语言
C语言存储类详解
在 C 语言中,存储类定义了变量的生命周期、作用域和可见性。主要包括:`auto`(默认存储类,块级作用域),`register`(建议存储在寄存器中,作用域同 `auto`,不可取地址),`static`(生命周期贯穿整个程序,局部静态变量在函数间保持值,全局静态变量限于本文件),`extern`(声明变量在其他文件中定义,允许跨文件访问)。此外,`typedef` 用于定义新数据类型名称,提升代码可读性。 示例代码展示了不同存储类变量的使用方式,通过两次调用 `function()` 函数,观察静态变量 `b` 的变化。合理选择存储类可以优化程序性能和内存使用。
149 82
|
1天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
19天前
|
存储 C语言
深入C语言内存:数据在内存中的存储
深入C语言内存:数据在内存中的存储
|
26天前
|
存储 C语言
C语言中的浮点数存储:深入探讨
C语言中的浮点数存储:深入探讨
|
18天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
30 3
|
C语言
软件设计师1991年下午试题2(C语言 压缩矩阵乘法)
阅读下列说明和流程图,回答问题1和问题2,把解答写在答卷的对应栏内。 [说明] 流程图用来计算矩阵 K,Y 的乘积 Z,其中 X,Y,Z 均为 m 行 m 列的下三角方阵,即行号小于列号的元素均为零的 m 阶方阵。
647 0
|
9天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
27 10
|
2天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
8天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
32 7
|
8天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
21 4