数据结构辅导第二章 线性表（三）
发布时间：2024-04-18 10:04:32浏览次数：14数据结构辅导资料四主 题：第二章 线性表（三）内 容：我们这周主要学习第二章线性表（三）的相关内容，希望通过下面的内容能使同学们加深对本章相关知识的理解。本章节知识脉络：．栈的基本概念、栈的操作、栈的表示和实现；．链式栈的基本操作、栈的应用；栈与递归。重点和难点：．重点：顺序栈和链式栈的概念；递归的定义。．难点：掌握栈的操作、表示和实现；链式栈的基本操作；递归的概念。一、 栈1. 几个概念栈：限定仅能在末端进行插入和删除的线性表。栈顶：图中的 ，允许插入和删除的一端。栈底：图中的 ，不允许插入和删除的一端。栈是时间有序表：称为先进后出（）线性表或后进先出（）线性表。 栈的基本操作清空栈。将元素 放到栈的顶部。
""J.J/J122把上面 " 个圆盘从 8 移到 7&"J.J/122将 " 号盘从 8 移到 ""JJ.J/122将 " 个盘从 7 移到 66）递归过程与递归工作栈P递归过程在实现时，需要自己调用自己。P每次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。P层层向下递归，退出时的次序正好相反，因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 函数调用与递归实现）函数调用每个函数（包括主函数 "）的状态是由函数中所有自动变量的内容、函数参数的值、表明在调用函数的何处重新开始的返回地址决定的。包含所有这些信息的数据区称为活动记录或者栈结构，它是在运行栈上分配空间的。）活动记录通常包含以下信息：@ 函数所有参数的值；B 可以存储在其他地方的局部变量（自动变量），活动记录只包含它们的描述符和指向存放它们的位置的指针。C 回到调用程序的返回地址，即在调用完成之后紧接着此函数调用指令之后的指令的地址。I 一个指向调用程序的活动记录的动态链接指针。V 非 &# 类型的函数的返回值。 递归调用过程剖析
）举例定义一个数 . 的非负整数 " 次幂的函数是递归函数的一个很好的例子。这个函数最直接的定义是：xn={1 n=0x· xn−1n>0可以直接根据幂的定义写出计算xn的 ==函数：#%#.J"L"#"",;"!!0"01".:%.J"16函数 %通过以下语句在主函数 "中调用："",!%WXJ16）递归调用的追踪：第 次调用 %WXJ第 次调用 %WXJ第 次调用 %WXJ0第 次调用 第 次调用 WX第 次调用 X）递归与循环P递归函数可以使用循环来实现。P函数 %可以用另一种方法来实现：#""D(%#.J"L"#"", #!1 ;!.1")1" :!.1 "16
?）尾部递归尾部递归的特点：在每个函数的实现的末尾只使用一个递归调用，例如： &#", ;)0, (''''KK1 1 6 6W）单向递归单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，互相之间参数无关，并且这些递归调用语句，也与尾部递归一样处于算法的最后。单向递归的典型例子就是 "(( 数列。计算斐波那契数列的函数 "的定义：Fib(n)={n , n=0,1Fib(n−1)+Fib(n−2), n>1求解斐波那契数列的递归算法"L"L",;"'!""1""="16X）递归过程改为非递归过程P递归过程简洁、易编、易懂；P递归过程效率低，重复计算多；P改为非递归过程的目的是提高效率；P单向递归和尾部递归可直接用迭代实现非递归过程；P其他情形必须借助栈实现非递归过程。二、 本节例题
1. 进栈顺序为{a,b,c,d}的序列，出栈顺序不可能为（ ）。A. dcbaB. cdabC. abcdD. adcb答案：B2．对于栈操作数据的原则是（）。A．先进先出 B．后进先出 C．后进后出 D．不分顺序答案：B三、 思考题1. 采用顺序存储的两个栈共享空间 S[1..m]，top[i]代表第 i 个栈( i=1,2)的栈顶，栈 1 的底在S[1]，栈 2 的底在 S[m]，则栈满的条件是（）。A．top[2]-top[1]|=0 B．top[1]+1=top[2]C．top[1]+top[2]=m D．top[1]=top[2]答案：7 表达式 :－(＋# 的后缀表达式是（）。8．(#:=7．(:#=．(:#=9．=:(#答案：7
取出栈顶部的元素。获取栈顶部的元素，但不删除该元素。判断栈是否为空。判断栈是否已满。 栈的表示和实现栈的两种表示方式：①顺序方式；②链式方式。栈的顺序表示：栈顶指针 指向实际栈顶位置，初值为。假设数组大小为 ，!时，栈空，此时执行出栈操作，会发生下溢（"#$%）；! 时，栈满，此时执行进栈操作，会发生上溢（&$%）。2. 顺序栈 顺序栈的类定义'()*(+,(- *(+" .*(+*/!0122栈的构造函数 3*(+,#45(+1622栈的析构函数 7(","!!16 7(","!! .16 ("1 *(+')8##(".1 *(+')9.1 &# +,!1622清空栈&- "122栈顶 " .122最大的栈顶值 :(+122堆栈元素数组61
顺序栈的初始化操作'()*(+')--*(+" .*(+*/, .! .*(+*/1 *(+!"%4 .*(+*/51 !16 顺序栈的进栈操作'()*(+')*(+')--8##(".,;, (''<"1<''"#1 ":16!=1(+45!.1":16 顺序栈的出栈操作'()*(+')*(+')--9.,;, (''<""<''"#1 ":16.!(+451!1":16 两个栈共享栈空间该空间的两端分别设为两个栈的栈底，用 405!!和 45!! .指示。让两个栈的栈顶 405和 45都向中间伸展，直到两个栈的栈顶相遇，才认为发生了溢出。3. 链式栈 链式栈的进栈操作'()
"+#*(+')"+#*(+')--8##(".,>#'):!"%>#')122生成新结点)#!.122对 的数据域赋值)"+!122对 的指针域赋值!122 指向新结点":16 链式栈的出栈操作'()"+#*(+')"+#*(+')--9(".,;,22进行边界检查 (''<""<1 ":16>#'):!1.!)#1!)"+1#1":16 链式栈的清空操作'()&#"+#*(+')-- +,22同析构函数 >#'):".1 %,".!)"+1#1!".1664. 栈的应用 数制转换
将一个非负十进制整数转换成八进制数并输出。 括号匹配匹配一个字符串中的左右括号。算法： （）如果是左括号，就把它的位置编码压入栈中 （）如果是右括号，则与栈顶的位置编码所指的左括号匹配。 回文游戏（顺读与逆读字符串一样（不含空格）） 算法思想： （）读入字符串； （）去掉空格（原串）； （）压入栈； （?）原串字符与出栈字符依次比较；若不等，非回文；若直到栈空都相等，则为回文。 表达式计算表达式都由操作数（也称运算对象）、操作符（也称运算符）和分界符组成。）算术表达式的三种表示：@ 中缀（"A.）表示：'操作数)'操作符)'操作数)，例如，8=7B 前缀（A.）表示：'操作符)'操作数)'操作数)，例如，=87C 后缀（A.）表示：'操作数)'操作数)'操作符)，例如，87=后缀表示也叫做 D> 或逆波兰记号，参加运算的操作数总在操作符面前。利用后缀表示求解表达式的值时，从左向右顺序地扫描表达式。后缀表达式中不出现括号。后缀表达式例子E:0=（这个表达式对应的中缀表达式：:E=0）
）后缀表达式计算过程@ 顺序扫描表达式的每一项：如果是操作数，则压入栈中；如果是操作符')，连续从栈中退出两个操作数 F 和 G，形成运算指令 G')F，并将结果重新压入栈中。B 当扫描完表达式后，栈顶存放的就是计算结果。）中缀表达式计算平时所用的表达式都是中缀表示。如 8=7:92；中缀表示中有操作符的优先级问题，并可以加括号改变运算顺序。用中缀表示求解表达式的值需要利用两个栈来实现，一个暂存操作数，另一个暂存操作符。 计算中缀表达式算法思想：@ 设置两个工作栈 运算符栈 D，运算符栈的栈底为表达式的起始符H。 操作数栈 >9，操作数栈为空栈。B 设 代表栈内优先级，(代表栈外优先级C 依次读入表达式中的每个字符，若是 操作数，则进 >9 栈； 运算符 ，则和 D 中的栈顶元素 做比较再操作。若 ()，则运算符入栈；若 ('，则从 >9 栈顶弹出两个操作数，与 D 中的栈顶元素做运算，并将运算结果入 >9 栈；若 (!!，则 D 中的栈顶元素出栈。I 直至表达式扫描完毕。
各个算术操作符的优先级 中缀表达式求值的运算符优先算法 "#&.", 22设 D 和 >9 分别为运算符栈和运算数栈， 为运算符集合。"*(+D1DJKHK1"*(+>91(!L(1 %(M!KHKNNODM!KHK, ;M"(J,>9J(1(!L(1622( 是操作数 %((#ODJ(, (K'K-22栈顶元素优先级低 DJ(1(!L(1+1 (K!K-22优先级相等，托括号并接收下一个字符 DJ.1(!L(1+1 (K)K-22栈顶元素优先级高，退栈并将运算结果入栈 DJ1>9J1>9J1 >9JJJ1+1 622%(622%"O>91622&."?）中缀表达式向后缀表达式的转换扫描中缀表达式，将其转换成相应的后缀表达式。中缀表达式变换为后缀表达式的算法步骤可以总结为：@ 设置一个堆栈，初始时将栈顶元素置为“H<。B 顺序读入中缀表达式，当读到的单词为操作数时就将其输出，并接着读下一个单词。C 当读到的单词为操作符时，需要和栈顶操作符进行比较。令 .为当前扫描操作符的变量，.为当前栈顶操作符的变量。若 .的栈外优先级高于 .的栈内优先级，则将 .入栈，
否则将 .退栈并作为后缀表达式的一个单词输出。I 重复以上步骤直到表达式扫描完毕。5.栈与递归 递归概念 递归定义：P在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数 调用过程或函数 Q，而 Q 又调用 ，称之为间接递归。递归定义常用来定义函数和数列。例如，阶乘函数可以按照以下方式定义：n !={1, 当 n=0时（ 递归基础）n∗(n−1)!,当 n ≥ 1时 （递归体 ）P序列的递归定义有一个不好的特性：为了确定序列中一个元素 *"的值，首先需要计算这个元素之前所有元素（*、*、*"）的值或其中一部分的值。P递归定义的缺点：以迂回的方式进行计算。P等式比递归定义更可取，简化计算过程，不用计算第 0、、" 个元素的值，就可以计算第 " 个元素的值。P递归定义广泛应用的一个领域是程序语言的语法说明。语法按照方块图或者巴科斯范式进行说明。 以下三种情况常常用到递归方法。 定义是递归的，例如阶乘函数。 求解阶乘函数的递归算法： "L("L", ;"!!0"1 "":("1 6 数据结构是递归的，例如单链表结构。
搜索链表最后一个结点并打印其数值 '() &#"#>#'):;, ;;M!>R ;;)"+!!>R('';)#''"#1 "#;)"+1 6 问题的解法是递归的，例如 %;S"问题。有 8、7、 三个塔座，8 上套有 " 个直径不同的圆盘，按直径从小到大叠放，形如宝塔，编号 JJ"。要求将 " 个圆盘从 8 移到 ，叠放顺序不变，移动过程中遵循下列原则：@ 每次只能移动一个圆盘；B 圆盘可在三个塔座上任意移动；C 任何时刻，每个塔座上不能将大盘压倒小盘上。 %;S" 问题解决方法：当 "! 时，直接把圆盘从 8 移到 。当 ") 时，把上面 " 个圆盘从 8 移到 7；然后将 " 号盘从 8 移到 ；将 " 个盘从7 移到 。即把求解 " 个圆盘的 S" 问题转化为求解 " 个圆盘的 S" 问题，依次类推，直至转化成只有一个圆盘的 S" 问题。 %;S" 问题源码为：","1";T"";#+T1(";TU#TJ1";T*-U##+TJ1"JK8KJK7KJKK16&#"""J(.J(J(/,;"!!&J.J/122把一个圆盘从 8 移到 ,
