当前位置:首页 >> 学科竞赛 >>

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案


§3
§3.1 栈

栈和队列

栈(stack)是一种仅限于在称为栈顶(top)的一端进行插入和删除操作的线性表, 另一端则被为栈底(bottom) 。不含元素的空表称为空栈。 栈的特点:后进先出(Last In First Out) ,简称:LIFO。
栈顶 出栈 入栈

an

/>?

栈的表示和实现 和线性表类似,栈也有两种存储结构。 (1) .顺序栈

栈底

… … a1 a2

顺序栈即采用的顺序存储结构来表示栈,通常采用数组来实现。 采用顺序栈受数组空间的约束,有“溢出”的可能,编程前应作空间估算,若有溢出 可能,应作溢出判断及相应的处理。 在一个程序中,常常会出现同时使用多个栈的情形。为了不因栈上溢而产生错误中断, 必须给每个栈预分一个较大的空间,但这并不容易做到,因为栈实际所用的最大空间很难 估计;而且各个栈的实际使用量在使用期间是变化的,往往会有这样的情况,即其中一个 栈发生上溢,而另一个栈还是空的。设想,若令多个栈共享空间,则将提高空间的使用效 率,并减少发生栈上溢的可能。 所以,可以采用两个栈共享空间的方法:假设在程序中需设两个栈,并共享一维数组 空间。则利用“栈底位置不变”的特性,可将两个栈的栈底分别设在数组空间的两端,然 后各自向中间伸展(如图) ,仅当两个栈的栈顶相遇时才可能发生上溢。
栈1 栈1底 栈1顶 栈2顶 栈2 栈2底

(2) .链栈 采用链式存储结构的栈简称链栈。 对于链栈,不含产生单个栈溢出的情况,但要记得回收结点空间(dispose(p) ) ,否 则会出现整个空间被占满,new(p)过程无法实现(即无法申请新的结点空间)的情况。

【练习】 回文串识别

输入一字符串, 判断它是否为一回文串。 所谓回文串是指去掉其中的空格与标点符 号等非字母符号后,从前后两个方向读到的串相同,例如: ten animals I slam in a net. (我将十只动物装在网里) 输入:一字符串 输出:Yes 或 No

§3.2 队列 队列(queue)是所有的插入都在一端进行,而所有的删除都在另一端进行的线性表。 允许插入的一端称为队尾(rear) ,允许删除的一端称为队头(front) 。 队列的特点:先进先出(|First In First Out) ,简称:FIFO。
出队列

a1
队头

a2

a3 ?? an
队尾

出队列

?

队列的表示和实现 和栈一样,队列也有顺序存储和链式存储两种表示和实现方法。

在顺序存储结构中,同样有溢出可能,即元素因队满而无法入队。对于队列来说,可 以采用循环队列的技巧,仅当队头与队尾相遇时为队满。
队头 队尾

【例 3.2.1】逐行打印二项展开式 (a + b)i 的系数: 杨辉三角形 (Pascal’s triangle) 1 1 1 1 1 1 6 5 15 4 10 20 5 6 10 15 2 5 4 5 6 1 1 1 1 1 1 i= 1 2 3 4 5 6

要求:采用队列实现! 输入: n ——层数(n<50)25

输出:如上图的数字阵列 【算法思路】 分析第 i 行元素与第 i+1 行元素的关系

目的是从前一行的数据可以计算下一行的数据 从第 i 行数据计算并存放第 i+1 行数据

从数据结构上,可设计一个足够长的一维数组,以实现上述算法。

【练习】根据上述思路分析,用队列的方法完成例 3.2.1。 【练习】再用二维数组,用其它方法完成例 3.2.1。

【练习】侦察兵队列 有一个侦察班,由 11 人组成,其中 6 名是老侦察员,5 名是新侦察员。一次执勤要穿 越敌人的一道封锁线。根据当时的情况,队伍只能单线纵向排列,且前面第一、二人越过 后,第三个人要返回报告情况,该侦察员随后编到队伍的末尾。接着第四、五人越过,第 六人报告并排到末尾。依此类推。最后三人一齐顺次过去。越过封锁线后,队伍便形成老、 新交替的队形。请问,穿越前队伍该怎样排? 要求:采用队列实现! 输出:O 表示老队员,Y 表示新队员

【练习】倒水问题

[问题描述] 有三个分别装有 a 升水、b 升水和 c 升水的量筒(c>b>a>0,且 b 与 a 互质), 如果 c 筒装满水,a 与 b 均为空筒,三个筒相互倒水且不准把水倒往三个筒之外,一个往另一个 筒倒水记为一次倒水。问是否能量出 d 升水(c>d>0),若能,请求出最少的倒水次数使它能 倒出容量为 d 的水的方案。

[输入格式] 数据存放在当前目录下的文本文件“water.in”中。 文件中以一行的形式存放四个正整数,分别 a、b、c、d 的值。 [输出格式] 答案输出到当前目录下的文本文件“water.out”中。 第一次行是最少的倒水次数 Q,第二起的 Q 行是每次例水时量简的水量,依次为 a、b、 c (输入与输出数据中同一行相邻两个数之间用空格区分。 ) [输入输出举例] water.in 3 7 10 5 water.out 10 9 0 0 10 0 3 0 7 0 0 3 7 3 3 3 4 0 0 6 4 3 3 6 1 0 2 7 1 1 2 0 8 1 0 2 8 3 3 2 5 (仅有第二组才是最优的一个解。 ) §3.3 栈的应用实例

0 7 4 4 1 1 0 7 5

10 3 3 6 6 9 9 2 2

§3.3.1 中缀表达式和后缀表达式 对于高级语言程序中的表达式,在编译时求解用栈来实现。任何一个表达式是由操作 数(常量、常量名、变量名) 、运算符(算术、关系和逻辑三种运算符)和界限符(左、右 圆括号,结束符)所组成。 运算符在两个操作数之间的表达式,如 a+b、e*f-d 等,称为中缀表达式。求值时,一 般会有运算符号的优先权和结合权问题。例如:a+b*c-d,我们知道 b*c 要先求,但编译器 只能从左到有逐一检查,检查到加号时尚无法知道是否可执行,待检查到乘号时,因乘号 运算优先级比加号高,所有 a+b 不可以被执行,待继续基础到减号时,方可执行 b*c。 而后缀表达式是运算符在两个操作数之后,如 ab*,也称为“逆波兰式” 。后缀表达式 可以顺序计算求值,所以编译程序常把中缀表达式变换成后缀表达式,然后再求值。 下表是中缀表达式所对应的后缀表达式: 中缀表达式 A + B * C B * (D-C) + A 40.+ (10.-8.) * 2. -16. / 8. 后缀表达式 ABC * + BDC-*A+ 40.10.8.-2. * + 16. 8. / -

(一)、将中缀表达式转换成后缀表达式 在转换过程中为了确定计算次序,要按运算符的优先级进行,各运算符优先级如下表, 优先级数大的先执行。 运算符 优先级 ^ (乘方) 3 * , / 2 + , 1

【例 3.3.1】将中缀表达式转换成后缀表达式。 输入: 中缀表达式,如: B * (D-C) + A 输出: 后缀表达式,如: BDC-*A+ 【算法思想】 设立一个栈来实现中缀表达式变后缀表达式。 设中缀表达式在字符数组 E 中,E 的末尾再加‘#’作为结束符,将转成后缀表达式, 存于字符串 A 中。 对 E 中表达式自左向右扫描,遇数直接送到 A 中,若遇到运算符就考虑进栈,进栈的 原则是保持栈顶的运算符优先级最高。即若欲进栈的算符是 ‘( ’或欲进栈的运算符优先 级大于栈顶运算符的优先级,则将算符入栈,否则从栈中退出算符送至 A 中,直至欲进栈 的算符优先级大于栈顶算符的优先级,这时才将欲进栈的算符入栈。若遇到‘)’时,将栈 中算符退出送入 A 中,直至退出‘( ’为止。若遇表达式结束符‘#’ ,则依次退出栈中算

符送入 A 中。 根据上述算法,将中缀表达式 B * (D-C) + A 转换 成后缀表达式 BDC-*A+ 的过程图 3_1 所示。

扫描 E B * ( D

栈S * *( *( *(-

转换至 A B B B BD

【参考程序段】 BD *(const m=100; C * BDC var E , A , S : array [1..m] of char; ) + BDC{ E 中为中缀式,A 中为后缀式,S 为栈} + + BDC-* i , j , t : integer; A BDC-*A procedure postexp; # BDC-*A+ begin 图 3_1 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< >0) and (s[t]< > ‘(’) do begin A[ j ]:=S[ t ]; j:=j+1; t:=t-1; end; t:=t+1; s[ t ]:=E[ i ]; end; ‘*’, ‘/’ : begin while (t< >0) 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 t< >0 do begin A[ j ]:=S[ t ]; j:=j+1; end; A[ j ]:= ‘#’; end; (二)、对后缀表达式求值

t:=t-1;

计算一个后缀表达式的值,在算法上比中缀表达式要简单得多,这是因为后缀表达式 有两个优点:表达式无括号,也不需考虑运算符的优先级。 【算法思想】 对后缀表达式求值要使用一个栈来实现。 自左至右扫描后缀表达式,若遇数就入栈,若遇到运算符就从栈中退出两个数进行运 算,并把计算结果入栈。如此下去,直至遇到结束符“#”为止。最后栈底元素值为所求得 的结果。 【练习】将一个中缀表达式转换成后缀表达式,并对后缀表达式求值。 输入格式: (输入文件 bds.in) 第一行:中缀表达式,运算数均为大写字母,运算符含乘方‘^’ 第二行开始: 每行为表达式中字母,及其对应的值,输入顺序按字典排序 输出格式: (输入文件 bds.out) 第一行: 该中缀表达式所对应的后缀表达式 第二行: 该表达式的值 输入输出举例: 输入: (bds.in) B * (D - C) + A^C A 4 B 10 C 3 D 8 输出: (bds.out) B D C - * A C ^ + 114

§3.3.2 地图着色问题

对地图着色,可使用“四染色”定理,它是计算机科学中的著名定理之一,可以用不 多于四色对地图着色,使相邻的行政区域不重色。应 用这个定理的结论, 利用回溯算法可对一幅给定的地 图染色。作为地图四色的示例如图 3_3 所示,图中 01、02、03、04、05、06、07 为行政区编号,1 色、 2 色、3 色、4 色为各区域的颜色,称为色数。 【算法思想】 从编号为 01 的区域开始逐一进行染色,对每 个区域用色数 1,2,3,4 依次进行试探,并尽可能 取小色数。 若当前所取色数与周围已染色的区域不重 色,则把该区的色数入栈,否则依次使用下一色数进 行试探。 若从 1 色至 4 色均与相邻的某区域发生重色, 则需退栈回溯,修改栈顶区域的色数。 在实现此算法时,可用一个关系矩阵 R ( 1: n , 1: n )来描述各区域之间的边界关 系。若 第 i 区与第 j 区相邻(有共同边界) ,则 R[ i , j ]的值为 1,否则为 0。图 3_3 中所示的 地图关系矩阵如图 3_4 所示。为了记下每个区域 当前染色结果而设立一个栈 S( 1 : n ),栈的下 标值表示区域号,栈中的内容是色数,如 S[ 6 ] = 3 表示 06 区域当前染色的色数是 3。 R i 1 2 3 j 1 0 1 1 2 1 0 0 3 1 0 0 4 1 0 1 5 1 0 1 1 0 1 0 6 1 1 0 1 1 0 0 7 0 0 0 0 0 0 0 图 3_3

【参考程序段】 4 1 0 1 0 const n=7; {地图中区域数} 5 1 0 1 1 type adjar=array[1..n,1..n] of 0..1; 6 1 1 0 1 ads=array[1..n] of 1..4; 7 0 0 0 0 procedure mapcolor (var r:adjr; var s:ads); begin 图 3_4 s[ 1]:=1; {01 区染 1 色} i:=2; j:=1; { i 为区域号,j 为染色号} while i<n do begin while ( j< =4 ) and ( i<n ) do begin k:=1; { k 指示已染色区域号} while ( k<i ) and ( s[ k ]*R[ i , k ]<>j ) do begin k:=k+1; { 判断相邻区是否已染色} if k<i then j:=j+1 { 用 j+1 色继续试探} else begin

s[ i ]:= j; i:=i+1; j:=1; end; { 与相邻区不重色,染色结果进栈,继续对下 一区从 1 色进行试探} end; if j.> 4 then begin i:= i-1; j:=s[ i ]+1; end; { 变更栈顶区域的染色色数} end; end; end; 按图 3_3 所示地图执行上述算法时,栈的变化情况如图 3_5 所示。 7 6 5 4 3 2 S 1 4 3 2 2 1 → 3 4 2 2 1 → 3 2 1 图 3_5 从关系矩阵 R 可以看出,当 i = 6 时,无论色数 j=1 , 2 , 3 , 4 都产生与相邻区重 色问题 (因与 i = 6 相邻的区是 1,2,4,5 区,从栈 S 可见这四个区色数分别 1,2,3, 4,四种色全部用完。6 区再用四种色数之一,必然重色) 。因此必须变更栈顶色数,而 5 区当前色数为“4” ,也不存在除 4 以外的可染色色数,则需继续退栈,变更 S[ 4 ]:=4, 由此 S[ 5 ]:=3,然而此时仍然 6 区与相邻区重色,再次退栈,将 S[ 3 ]改为 S[ 3 ]:=3 时才求得所有地区的染色解。 → 2 3 2 1 → 4 2 3 2 1 → 3 4 2 3 2 1 → 1 3 4 2 3 2 1

§3.4 栈与递归 §3.4.1 递归形式一般有两种——直接递归和间接递归,而栈是实现递归的重要手段。 (一)、直接递归——子程序自己调用自己 1 【例 2】 fac (n) = n! = n×fac (n-1) function fac(n:integer):integer; begin if n=0 then fac:=1 else fac:=n*fac(n-1); n=0 n>1

按上述递归定义形式写出 fac(n) 函数如下:

end; 它的执行流程如下: fac (3) fac (2) fac (1) fac (0)

fac (3) 6 3×fac (2) 2×fac (1) 1×fac (0) fac (0) = 1 一般来说,递归子程序在调用本身前应有条件语句控制何时进行递归,何时递归结束。 这个条件语句就是递归边界。例如,fac 函数体中的“ if n=0 then fac:=1 ” 。 (二)、间接递归——子程序 A 调用子程序 B,子程序 B 又调用子程序 A 子程序 A 和 B 组合起来有两种结构形式: 1.B 是 A 的局部对象 例: procedure A; procedure B; begin A 的子过程 B ? 的过程说明 A; {在 B 中调用 A} ? end begin ? B; {在 A 中调用 B} ? end; 2.A 和 B 是两个地位相同的子程序 例: procedure B (形式参数表): forward; {B 的完整说明在后} procedurde A; begin ? B (实参表); {在 A 中调用 B} end; procedure B; {B 的首部缩写,形式参数表不再列出} begin ? A; {在 B 中调用 A} ?

end; 【例题 3】 求出一个在 8×8 的棋盘上,放置 8 个不能互相捕捉的“皇后”的所有布局。 显然,一个使“皇后”间不能互相捕捉的合理布局应该是——每列、每行确定有一个“皇 后” ,且在每条对角线上最多只有一个“皇后” 。 【数据结构设计】 从 8×8 的棋盘, 我们很容易想到用二维数组来存 储布局。 但是,进一步分析,每行有且仅有一个“皇后” , 我们可以仅用一维数组来存储布局。 S 2 3 4 5 6 7 8 S[ i ] 表示第 i 行“皇后”所处的列。 这一数据结构的改进,将大大简化编程。 【算法思路】 1、 从空配置开始,在第 1 行至第 top 行为合理配置的基础上,递归调用自己而完成 top+1 行上的配置,直至第 8 行配置也是合理时,就找到一个解。因此,top=9 是递归边界。 2、 在任一行上可能的配置有 8 种。开始时配置在第 1 列,以后改变时,顺次选择第 2 列, 第 3 列,??,直至第 8 列,当 8 列配置全不合理或者选中某一列配置时,则退出递 归过程,通过恢复步数的形式回溯,直到所有布局为止。 3、 要在 ( i , top) 配置“皇后” (S[ top ]:= i)的条件有两个: ① 第 1 至 top-1 行的第 i 列不能有“皇后” ,即 S[j]≠i,1≤j≤top-1; ② 经 ( i , top) 的两条对角线上不能有“皇后” , 即: | S[ j ]-i | ≠ | j -top |,1≤j≤top-1; 【参考程序】 program queen; var total : integer; {布局数} s : array[1..8] of 1..8; {布局} procedure search(top:integer); var i,j : integer; p : boolean; {p=true 表示找到某列的配置} begin if top>8 then begin {配置成功,打印布局} 1

total:=total+1; writeln(total,' step: '); for i:=1 to 8 do write(s[i],' '); writeln; end else begin for i:=1 to 8 do begin {由第 1 行开始,顺序选择} p:=true; if top>1 then begin j:=1; {确定可否在(i,top)位置配置皇后} while (j<top) and p do begin if (s[j]=i) or (abs(s[j]-i)=abs(j-top)) then p:=false; j:=j+1; end; end; if p then begin {top 列配置成功} s[top]:=i; search(top+1); {递归执行 top+1 列上的配置} end; end; end; end; Begin total:=0; search(1); End.

{布局数计数器清 0}

§3.4.2 递归算法适用的场合 1、数据的定义形式按递归定义 如斐波那契数列的定义: fn = fn-1 + fn-2 ; f0 = 1 ; 【练习 3】对应的递归程序为: function fib ( n : integer ) : integer; begin if n=0 then {递归边界} else end; {fib} {递归} f1 = 2 ;

★ 这类问题可转化为递推算法,递归边界作为递推的边界条件,如上例: 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 排列, 及其排列种数 Pnr 。 (相关知识见 《数学基础补充 §1》 ) (输入: N R)

r 【练习 5】 输出 N 元集的 R 组合,及其排列种数 C n 。

(输入: N 练习 3 答案:① fib:=2

R) ② fib:=fib(n-2)+fib(n-1);


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案_学科...to n do if visited[ i ]:=false then bfs( i ); end; (队列 / 栈?...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案_学科竞赛_高中教育_教育专区。§4 §4.1 串的匹配 串 子串的定位操作称为串的模式匹配,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案_学科竞赛_高中教育_教育专区。§1 §1.1 什么是数据结构 概论 数据结构(Data ...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案_其它课程_高中教育_教育专区。§7 §7.1 树的概念 树 【定义】 树(Tree)是 n(n>0...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案_学科竞赛_高中教育_教育专区。§2 §2.1 线性表的定义及其基本运算 线性表 线性表是...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案_学科竞赛_高中教育_教育专区。§6 §6.1 广义表的定义 广义表 广义表 (Lists) 又称...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案_学科竞赛_高中教育_教育专区。§5 §5.1 特殊矩阵 §5.1.1 三角矩阵与...
广东省汕头市金山中学高中信息技术 pascal教程02 第二课 读懂程序教案
广东省汕头市金山中学高中信息技术 pascal教程02 第二课 读懂程序教案_其它课程_高中教育_教育专区。第二课 读懂程序接下来,我们要学着去读懂程序。 我们用上节课...
第3章 数据结构习题题目及答案 栈和队列
数据结构第3章栈和队列自... 10页 2下载券 数据...一、基础知识题 3.1 有五个数依次进栈:1,2,3,...
更多相关标签:
广东省汕头市金山中学 | 广东省汕头市 | 广东省汕头市潮阳区 | 广东省汕头市潮南区 | 广东省汕头市邮编 | 广东省汕头市澄海区 | 广东省汕头市金平区 | 广东省汕头市地图 |