数据结构辅导第二章 线性表(三)
发布时间:2024-04-18 10:04:32浏览次数:20数据结构辅导资料四主 题:第二章 线性表(三)内 容:我们这周主要学习第二章线性表(三)的相关内容,希望通过下面的内容能使同学们加深对本章相关知识的理解。本章节知识脉络:.栈的基本概念、栈的操作、栈的表示和实现;.链式栈的基本操作、栈的应用;栈与递归。重点和难点:.重点:顺序栈和链式栈的概念;递归的定义。.难点:掌握栈的操作、表示和实现;链式栈的基本操作;递归的概念。一、 栈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 移到 ,