@[toc]
问题分析:
问题还是很简单就是,利用栈的特性,左括号进栈,右括号出栈实现匹配,在栈空且所有括号都扫过一遍后结束
南京理工大学上机题目
苗苗今天刚刚学会使用括号，不过他分不清小括号，中括号，大括号和尖括号，不知道怎么使用这些括号，请帮助他判断括号使用是否正确。
注意：不需要区分括号的优先级。
输入样例：
(){}
输出样例：
yes
- 想到用栈来实现括号匹配的问题
- 第一步,肯定是实现栈的基础操作(当然为了简单快捷,选择静态存储的方式实现栈)
- 栈的定义
- 栈的初始化
- 入栈
- 出栈
- 判空
- 具体问题具体分析
- 写一个括号匹配函数,模拟整个过程
- 主函数中补上字符串的输入
完整代码如下:
在学习栈的表达式求值之前 明确的概念
中缀表达式(符号在中间)
后缀表达式(符号在后边)
前缀表达式(符号在前边)
引子:为学习计算机机算做铺垫,计算机更喜欢处理后缀表达式这种形式
- 从左到右的找符号,找到合适的符号就把符号两边的操作数和符号写成后缀表达式的形式
- 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
从左往右我们发现,最后出现的操作数先被运算,想到栈这种数据结构
类似于中缀表达式改写为后缀表达式,只是遵循的是右优先原则
类似于后缀表达式的计算,但是是从右边开始依次入栈,遇到符号出栈.....
- 从左到右扫描,
- 遇到操作数就入栈,遇到符号就将栈顶两个操作数出栈,符号计算完再入栈
- 直到全部扫描一遍后,若表达式合法,最后栈中只会留下一个结果就是最后结果
- 遇到操作数,直接加入后缀表达式
- 遇到界限符,遇到"("直接入栈,直到遇见")",把此时"("上面的所有运算符都依次出栈加入后缀表达式,注意"("不加入,")"也入栈
- 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式,若碰到“(”或栈空则停止。之后再把当前运算符入栈。
本质就是将中缀表达式转后缀表达式和后缀表达式的计算结合起来
用栈实现中缀表达式的计算:
初始化两个栈，操作数栈和运算符栈若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈)
矩阵的压缩存储通过数组的形式来实现
对称矩阵
- 对称矩阵大小存储的大小是多少
(1+n)*n/2 - 按行优先的原则,a~i~,~j~是第几个元素(注意是第几个元素)
先算前面行一共有多少个,再加上当前的列坐标
1+2+3+...(i-1)再+j 个元素即i(i-2)/2+j个元素
如果是下标那就得-1
下三角矩阵和上三角矩阵
压缩存储策略:按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c
按行优先的原则,a~i~,~j~是第几个元素(注意是第几个元素)跟对称矩阵是一样的,当i<j的时候就是那个常数c,即n(n+1)/2
什么是三对角矩阵?
按行优先的原则,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
稀疏矩阵:非零元素远远少于矩阵元素的个数
压缩存储策略:
顺序存储―一三元组<行，列，值>
定义一个结构体,存储i,j,v
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/5250.html