《2022年高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案》由会员分享，可在线阅读，更多相关《2022年高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案（13页珍藏版）》请在装配图网上搜索。
1、2022年高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案3.1 栈出栈入栈栈顶栈底ana1a2栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。不含元素的空表称为空栈。栈的特点：后进先出（Last In First Out），简称：LIFO。l 栈的表示和实现 和线性表类似，栈也有两种存储结构。 （1）顺序栈 顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。在一个程序中，常常会出现同时使用多个栈的情形。为
2、了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。栈1栈2栈1底栈1顶栈2顶栈2底（2）链栈 采用链式存储结构的栈简称链栈。 对于链栈，不含产生
3、单个栈溢出的情况，但要记得回收结点空间（dispose（p），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。【练习】 回文串识别输入一字符串，判断它是否为一回文串。所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：ten animals I slam in a net. （我将十只动物装在网里） 输入：一字符串 输出：Yes或No3.2 队列队列（queue）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列的特点：先进先出（|F
4、irst In First Out），简称：FIFO。a1 a2 a3 an 出队列出队列队头队尾l 队列的表示和实现和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。队头队尾【例3.2.1】逐行打印二项展开式 (a + b)i 的系数：杨辉三角形 (Pascals triangle) 1 1 i =1 1 2 12 1 5 5 13 1 4 6 4 14 1 510 10 5 15 1 6152015 6 16要求：采用队列实现！输入： n 层数（nba0，且b与
5、a互质）, 如果c筒装满水，a与b均为空筒，三个筒相互倒水且不准把水倒往三个筒之外，一个往另一个筒倒水记为一次倒水。问是否能量出d升水(cd0)，若能，请求出最少的倒水次数使它能倒出容量为d的水的方案。输入格式数据存放在当前目录下的文本文件“water.in”中。文件中以一行的形式存放四个正整数，分别a、b、c、d的值。输出格式答案输出到当前目录下的文本文件“water.out”中。第一次行是最少的倒水次数Q，第二起的Q行是每次例水时量简的水量，依次为a、b、c （输入与输出数据中同一行相邻两个数之间用空格区分。）输入输出举例water.in 3 7 10 5water.out 10 9 0
6、0 10 0 0 10 3 0 7 0 7 3 0 3 7 3 4 3 3 3 4 0 4 6 0 6 4 3 1 6 3 6 1 0 1 9 2 7 1 1 0 9 2 0 8 1 7 2 0 2 8 3 5 2 3 2 5 （仅有第二组才是最优的一个解。）3.3 栈的应用实例3.3.1 中缀表达式和后缀表达式对于高级语言程序中的表达式，在编译时求解用栈来实现。任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号，结束符）所组成。运算符在两个操作数之间的表达式，如a+b、e*f-d等，称为中缀表达式。求值时，一般会有运算符号的优先权和结
7、合权问题。例如：a+b*c-d，我们知道b*c要先求，但编译器只能从左到有逐一检查，检查到加号时尚无法知道是否可执行，待检查到乘号时，因乘号运算优先级比加号高，所有a+b不可以被执行，待继续基础到减号时，方可执行b*c。而后缀表达式是运算符在两个操作数之后，如ab*，也称为“逆波兰式”。后缀表达式可以顺序计算求值，所以编译程序常把中缀表达式变换成后缀表达式，然后再求值。下表是中缀表达式所对应的后缀表达式：中缀表达式后缀表达式A + B * CB * (D-C) + A40.+ (10.-8.) * 2. -16. / 8.ABC * +BDC-*A+40.10.8.-2. * + 16. 8.
8、 / -(一)、将中缀表达式转换成后缀表达式在转换过程中为了确定计算次序，要按运算符的优先级进行，各运算符优先级如下表，优先级数大的先执行。运算符 (乘方)* , /+ , -优先级321【例3.3.1】将中缀表达式转换成后缀表达式。 输入： 中缀表达式，如： B * (D-C) + A 输出： 后缀表达式，如： BDC-*A+【算法思想】设立一个栈来实现中缀表达式变后缀表达式。设中缀表达式在字符数组E中，E的末尾再加#作为结束符，将转成后缀表达式，存于字符串A中。对E中表达式自左向右扫描，遇数直接送到A中，若遇到运算符就考虑进栈，进栈的原则是保持栈顶的运算符优先级最高。即若欲进栈的算符是 (
9、 或欲进栈的运算符优先级大于栈顶运算符的优先级，则将算符入栈，否则从栈中退出算符送至A中，直至欲进栈的算符优先级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。若遇到)时，将栈中算符退出送入A中，直至退出( 为止。若遇表达式结束符#，则依次退出栈中算扫描E栈S转换至AB*B* (B(* (BD* ( -BD-* ( -BDC*BDC)+BDC-+BDC-*ABDC-*A#BDC-*A+ 图3_1符送入A中。根据上述算法，将中缀表达式B * (D-C) + A转换成后缀表达式BDC-*A+ 的过程图3_1所示。【参考程序段】const m=100; var E , A , S : array 1
10、.m of char; E中为中缀式，A中为后缀式，S为栈 i , j , t : integer;procedure postexp;begin i:=1; j:=1; t:=0; while E i # do begin case E i of a. z, A. Z : begin A j :=E i ; j:=j+1; end; ( : begin t:=t+1; S t := (; end; ) : begin while s t ( do begin A j :=s t ; j:=j+1; t:=t-1; end; t:=t-1; end; +, - : begin while (t
11、0) and (st () do begin A j :=S t ; j:=j+1; t:=t-1; end; t:=t+1; s t :=E i ; end; *, / : beginwhile (t0) and (S t = * or S t = /) do begin A j :=S t ; j:=j+1; t:=t-1; end; while t:=t+1; S t :=E i ; end; end; case i:=i+1; end; while while t0 do begin A j :=S t ; j:=j+1; t:=t-1; end; A j := #;end;(二)、对
12、后缀表达式求值计算一个后缀表达式的值，在算法上比中缀表达式要简单得多，这是因为后缀表达式有两个优点：表达式无括号，也不需考虑运算符的优先级。【算法思想】对后缀表达式求值要使用一个栈来实现。自左至右扫描后缀表达式，若遇数就入栈，若遇到运算符就从栈中退出两个数进行运算，并把计算结果入栈。如此下去，直至遇到结束符“#”为止。最后栈底元素值为所求得的结果。【练习】将一个中缀表达式转换成后缀表达式，并对后缀表达式求值。 输入格式： （输入文件 bds.in）第一行：中缀表达式，运算数均为大写字母，运算符含乘方 第二行开始： 每行为表达式中字母，及其对应的值，输入顺序按字典排序 输出格式： （输入文件 b
13、ds.out）第一行： 该中缀表达式所对应的后缀表达式 第二行： 该表达式的值输入输出举例：输入： (bds.in)输出： (bds.out)B * (D - C) + ACA 4B 10C 3D 8B D C - * A C +1143.3.2 地图着色问题图 3_3对地图着色，可使用“四染色”定理，它是计算机科学中的著名定理之一，可以用不多于四色对地图着色，使相邻的行政区域不重色。应用这个定理的结论，利用回溯算法可对一幅给定的地图染色。作为地图四色的示例如图 3_3所示，图中01、02、03、04、05、06、07为行政区编号，1色、2色、3色、4色为各区域的颜色，称为色数。【算法思想】从
14、编号为01的区域开始逐一进行染色，对每个区域用色数1，2，3，4依次进行试探，并尽可能取小色数。若当前所取色数与周围已染色的区域不重色，则把该区的色数入栈，否则依次使用下一色数进行试探。若从1色至4色均与相邻的某区域发生重色，则需退栈回溯，修改栈顶区域的色数。在实现此算法时，可用一个关系矩阵R ( 1: n , 1: n )来描述各区域之间的边界关系。若j123456710111110210000103100110041010110510110106110110070000000Ri第i区与第j区相邻（有共同边界），则R i , j 的值为1，否则为0。图 3_3中所示的地图关系矩阵如图 3_
15、4所示。为了记下每个区域当前染色结果而设立一个栈S( 1 : n )，栈的下标值表示区域号，栈中的内容是色数，如S 6 = 3表示06区域当前染色的色数是3。【参考程序段】const n=7; 地图中区域数type adjar=array1.n,1.n of 0.1; ads=array1.n of 1.4;procedure mapcolor (var r:adjr; var s:ads);图3_4 begin s 1:=1; 01区染1色 i:=2; j:=1; i 为区域号，j为染色号 while in do begin while ( j =4 ) and ( in ) do begi
16、n k:=1; k 指示已染色区域号 while ( ki ) and ( s k *R i , k j ) do begin k:=k+1; 判断相邻区是否已染色 if k 4 then begin i:= i-1; j:=s i +1; end; 变更栈顶区域的染色色数end; end;end;按图3_3所示地图执行上述算法时，栈的变化情况如图3_5所示。7163354344443422223223333322222222S11111111图3_5从关系矩阵R可以看出，当i = 6时，无论色数j1 , 2 , 3 , 4都产生与相邻区重色问题 （因与i = 6相邻的区是1，2，4，5区，从
17、栈S可见这四个区色数分别1，2，3，4，四种色全部用完。6区再用四种色数之一，必然重色）。因此必须变更栈顶色数，而5区当前色数为“4”，也不存在除4以外的可染色色数，则需继续退栈，变更S 4 :=4，由此S 5 :=3，然而此时仍然6区与相邻区重色，再次退栈，将S 3 改为S 3 :=3时才求得所有地区的染色解。3.4 栈与递归3.4.1 递归形式一般有两种直接递归和间接递归，而栈是实现递归的重要手段。(一)、直接递归子程序自己调用自己1 n=0nfac (n-1) n1【例2】 fac (n) = n! = 按上述递归定义形式写出fac(n) 函数如下：function fac(n:inte
18、ger):integer;beginif n=0 then fac:=1else fac:=n*fac(n-1);end;它的执行流程如下：fac (3)fac (3)fac (2)fac (1)fac (0)3fac (2)2fac (1)1fac (0)fac (0) = 16一般来说，递归子程序在调用本身前应有条件语句控制何时进行递归，何时递归结束。这个条件语句就是递归边界。例如，fac函数体中的“ if n=0 then fac:=1 ”。(二)、间接递归子程序A调用子程序B，子程序B又调用子程序A子程序A和B组合起来有两种结构形式：1B是A的局部对象例： procedure A;pr
19、ocedure B;beginA的子过程B的过程说明 A; 在B中调用A endbegin B; 在A中调用B end;2A和B是两个地位相同的子程序例： procedure B (形式参数表): forward; B的完整说明在后procedurde A;begin B (实参表); 在A中调用Bend;procedure B; B的首部缩写，形式参数表不再列出beginA; 在B中调用Aend;【例题3】求出一个在88的棋盘上，放置8个不能互相捕捉的“皇后”的所有布局。显然，一个使“皇后”间不能互相捕捉的合理布局应该是每列、每行确定有一个“皇后”，且在每条对角线上最多只有一个“皇后”。【数
20、据结构设计】从88的棋盘，我们很容易想到用二维数组来存储布局。但是，进一步分析，每行有且仅有一个“皇后”，我们可以仅用一维数组来存储布局。S 1 2 3 4 5 6 7 8S i 表示第i行“皇后”所处的列。这一数据结构的改进，将大大简化编程。【算法思路】1、 从空配置开始，在第1行至第top行为合理配置的基础上，递归调用自己而完成top+1行上的配置，直至第8行配置也是合理时，就找到一个解。因此，top=9是递归边界。2、 在任一行上可能的配置有8种。开始时配置在第1列，以后改变时，顺次选择第2列，第3列，直至第8列，当8列配置全不合理或者选中某一列配置时，则退出递归过程，通过恢复步数的形式
21、回溯，直到所有布局为止。3、 要在 ( i , top) 配置“皇后”（S top := i）的条件有两个： 第1至top-1行的第i 列不能有“皇后”，即Sji，1jtop-1； 经 ( i , top) 的两条对角线上不能有“皇后”，即： | S j -i | | j -top |，1jtop-1；【参考程序】program queen; var total : integer; 布局数 s : array1.8 of 1.8; 布局 procedure search(top:integer); var i,j : integer; p : boolean; p=true表示找到某列的配置
22、 begin if top8 then begin 配置成功，打印布局 total:=total+1; writeln(total, step: ); for i:=1 to 8 do write(si, ); writeln; end else begin for i:=1 to 8 do begin 由第1行开始，顺序选择 p:=true; if top1 then begin j:=1; 确定可否在(i,top)位置配置皇后 while (jtop) and p do begin if (sj=i) or (abs(sj-i)=abs(j-top) then p:=false; j:=j
23、+1; end; end; if p then begin top列配置成功 stop:=i; search(top+1); 递归执行top+1列上的配置 end; end; end; end;Begin total:=0; 布局数计数器清0 search(1);End.3.4.2 递归算法适用的场合1、数据的定义形式按递归定义 如斐波那契数列的定义： fn = fn-1 + fn-2 ； f0 = 1 ； f1 = 2 ；【练习3】对应的递归程序为： function fib ( n : integer ) : integer; begin if n=0 then 递归边界 else 递归
24、end; fib 这类问题可转化为递推算法，递归边界作为递推的边界条件，如上例： f 0:= 1; f 1:= 2; 递推边界 for i:=2 to n do f i := f i-1 + f i-2 ; fib:= f n ;2、数据之间的关系（即数据结构）按递归定义，如树的遍历、图的搜索等；3、问题解法按递归算法实现，如回溯法、分治法等；递归算法效率较低，费时费空间，但递归算法可以使一个蕴含递归关系的程序简洁精炼。【练习4】 输出N元集的R排列，及其排列种数。 （相关知识见数学基础补充 1） （输入： N R） 【练习5】 输出N元集的R组合，及其排列种数。 （输入： N R）练习3答案： fib:=2 fib:=fib(n-2)+fib(n-1);
2022年高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案
