2023考研408数据结构备考知识点:栈(下)

今天小编为大家整理了2023考研408数据结构知识点之栈的相关介绍,从栈和函数调用、栈的应用等方面为大家做详细的介绍,助力大家更好地备考,提高备考效率,顺利进入理想院校。

7:栈和函数调用

函数的调用符合先调用,后执行的特点,正好可以用栈来进行存储函数的调用过程;在用栈进行存储时,先调用的函数,先入栈,那么从栈底到栈顶依次是函数调用的顺序。

8:栈的应用

1、 符号匹配:程序中经常用到一些成对出现的符号,比如括号,对其进行是否成对检验是基本的编译问题,可利用堆栈特点是先检测算法。每扫描到一个左括号,将其入栈,扫描到右括号,将其出栈。扫描结束,若栈非空,返回0,说明左右括号个数不一致,否则返回1,说明二者个数匹配。
考研备考资料

2、 整数进制转换(eleType为unsigned类型):以十进制转八进制为例,其他进制类似。比如将一个十进制数字n转换为8进制数,对n除以8取余数,所有余数倒序输出即为对应的八进制数。
考研备考资料

3.表达式求值

(1)表达式的类型。

表达式有3个组成部分.分别是操作数、运算符、界限符号(包括小括号,.中括号)。

表达式有3种类型,分别是中缀表达式.前缀表达式(波兰式)、后缀表达式(逆波兰式)。这3种表达式可以使用表达式对应的二叉树的遍历来表示。例如,给定一个表达式:b-(a+5) * 3, 按照优先级顺序,构造出与表达式相对应的二叉树,其中运算符是二叉树的根,操作数是二叉树的左、右子树。

最后在这个构造好的二叉树上进行遍历,3种遄历顺序分别如下。.

前序遍历:根-左-右。

中序遍历:左-根-右。

后序遍历:左-右-根。

在最终二叉树的基础上可以得出以下表达式。

前缀表达式:一b* +a 5 3。

中缀表达式:b-(a+5) * 3。

后綴表达式:ba5+3*一。

(2)中缀表达式转后缀表达式。

①转化前先建立两个栈,命名为s1和s2。用栈s1存储表达式中的运算数,用栈s2存储符号。

②在转化的过程中,需从左到右扫描中綴表达式的每个运算数和符号,若是运算数则压入到栈sl中。

③若扫描到的是符号,设符号是C,则可能出现以下情况。

a若s2为空,则C压入到栈s2中。

b.若C为左括号,则C压入到栈s2中。

c.若s2的栈顶符号为左括号,则C压入到栈s2中。

d.若s2的栈顶符号的优先级小于C.则C压入到栈s2中(右括号的优先级最低)。

e.否则,就要将s2的栈顶符号弹出,从sl中弹出两个(也可能是1个)运算数.进行运算,并把运算的结果压回s1。

④扫描到表达式结束,若最后栈s2中还有符号,则将其依次出栈,并从s1中弹出两个(也可能是1个)运算数,进行运算,并把运算的结果压回sl。

⑤最终完成转化过程。

【23考研黄金期辅导课程推荐】23暑期集训营线上+线下VIP领学计划龙腾一对一专属VIP公共课+专业课全科辅导,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。


免责声明:本平台部分帖子来源于网络整理,不对事件的真实性负责,具体考研相关内容请以各院校的官网通知为准。 如果本站文章侵犯到您的权利,请联系我们(400-108-7500)进行删帖处理。

启航教育热门私房课

MORE
  • 2023考研VIP领学计划

    时间:随报随学
    形式:网课+面授
     

    查看详情

    在线咨询

  • 2023考研全年集训营

    时间:3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

  • 2023考研二战集训营

    3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

姓名

手机号

报考专业

请选择  
  • 计算机
  • 经济学
  • 金融硕士
  • 法律硕士
  • 应用统计
  • 机械工程
  • 管理学
  • 通信工程
  • 教育学
  • 心理学
  • 国际商务
  • 土木工程
  • 其他专业
一键申请
扫描上方二维码免费领取学习资料