当前位置：文档之家 › 广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列

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

  • 格式：doc
  • 大小：117.00 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

广东省汕头市金山中学高中信息技术奥林匹克信息学竞赛

广东省汕头市金山中学高中信息技术奥林匹克信息学竞赛

集合与记录类型§6.1 集合类型§6.1.1 集合类型的定义集合是同类型对象的一个汇集，它是指同类型对象汇集在一起构成的数据结构。

集合的每一个对象称为集合的元素。

集合元素必须是有序简单数据类型，集合元素的类型称为集合的基类型。

集合的一般形式为：TYPE <类型标识符> = set of <基类型>;基类型可以是整型、字符型、布尔型、枚举型、子界型等，但不能是实型或结构类型。

例如：TYPE letter = set of ‘A’.. ‘Z’;var ch1, ch2 : letter;也可以直接写成：var ch1, ch2 : set of ‘A’.. ‘Z’;在Pascal中集合是用一组括在方括号中的元素来表示，元素之间用逗号分隔。

如：[A, B , C , D] 是四个枚举量的集合[ 1 .. 20 ] 表示1到20的所有整数的集合[ ‘0’ ] 是单元素集[ ] 表示空集一个集合类型变量的取值，可以是基类型中所有元素按不同的组合而构成的子集。

例如，上面说明变量ch1的类型是letter，它可以是下列的组合：[‘A’ .. ‘Z’] 全集[‘A’, ‘B’, ‘Q’] 任一子集[‘A’ .. ‘C’ , ‘X’ ..‘Z’ ][‘A’ ] 单元素集[ ] 空集空集与所有的集合类型都兼容。

§6.1.2 集合类型的运算ch1:=[ [‘A’ .. ‘C’]];是合法的集合赋值。

对集合除可以进行赋值运算外，还可以进行以下运算：·交（*）运算：两集合之交 S1*S2 为一集合，所得元素由S1、S2中相同的元素组成。

如： [ 0..7 ] * [ 0..4 ] = [ 0..4 ]·并（+）运算：两集合之并 S1+S2 为一集合，所得元素由S1、S2中所有相同的元素组成。

如： [ 0..7 ] + [ 0..4 ] = [ 0..7 ][ 0 , 1 ] + [ 1 , 4 , 6 ] = [ 0 , 1 , 4 , 6 ]·差（-）运算：两集合之差 S1-S2 为一集合，所得元素由只存在于S1而不在S2的那些元素组成。

《数据结构栈和队列》课件

《数据结构栈和队列》课件
在操作系统中，任务按照 优先级顺序进入队列，系 统按照队列的先进先出原 则进行任务调度。
网络通信
在网络通信中，数据包按 照到达顺序进入队列，等 待处理。
打印任务管理
打印任务按照到达顺序进 入队列，等待打印机的空 闲时间进行处理。
05
栈与队列的比较
结构比较
栈和队列是两种不同的数据结构，它们在结构上有明显的区 别。
课程目标
掌握栈和队列的基本 概念、原理和应用场 景；
能够运用栈和队列解 决实际问题和算法设 计。
理解栈和队列在解决 实际问题中的作用和 优势；
02
数据结构概述
数据结构定义
数据结构定义
数据结构是数据元素之间相互关系和数据元素属性的 抽象表示。
数据结构组成
数据元素、数据元素之间的关系和数据元素的属性。
表达式求值：例如，括号内的运算优先级高于括号外的运算，可以使用栈来保存括 号和运算符，以便正确地计算表达式的值。
深度优先搜索（DFS）：在图的遍历中，可以使用栈来保存待访问的节点，实现深 度优先搜索。
04
队列（Queue）
队列的定义
01
队列是一种先进先出（FIFO）的数据结构，用于存储元素的集 合。
07
总结与展望
本章总结
栈和队列是两种常见的数据结构，具有特定的操作规则和特性。
通过学习栈和队列，我们掌握了先进先出（FIFO）和后进先出（LIFO）的 原理，以及如何在程序中实现这些数据结构。
本章还介绍了栈和队列在实际问题中的应用，如括号匹配、表达式求值等 。
数据结构的发展趋势与未来展望
01
随着计算机技术的不断发展，数据结构也在不断演进
02
队列中的元素遵循先入队后出队的规则，即最早进入队列的元

数据结构-栈和队列PPT课件

数据结构-栈和队列PPT课件
初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。
.
15
栈的抽象数据类型定义
StackTraverse(S, visit( )) 初始条件：栈 S 已存在且非空，visit( )为元素的访问
函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数
visit( )，一旦visit( )失败，则操作失败。 } ADT Stack
.
29
3.1.2.2 栈的静态顺序存储表示
4 弹栈(元素出栈)
Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素*/ { if ( S.top==0 ) return ERROR ; /* 栈空，返回错误标志 */ *e=S.stack_array[S.top] ; S.top-- ; return OK ; }
.
11
3.1.1 栈的基本概念
2 栈的抽象数据类型定义
ADT Stack{ 数据对象：D ={ ai|ai∈ElemSet, i=1,2,…,n，n≥0 } 数据关系：R ={<ai-1, ai>|ai-1，ai∈D, i=2,3,…,n } 基本操作：初始化、进栈、出栈、取栈顶元素等
} ADT Stack
进栈（push） 出栈(pop)
top
an
⋯⋯
ai ⋯⋯
a2
bottom
a1
图3-1 顺序栈示意图
.
6
栈的示意图
入栈
• 特点
• 先进后出（FILO） 出栈 • 后进先出（LIFO）
栈顶 栈顶 栈顶
a3 a2
插入：入栈、进栈、压栈 删除：出栈、弹栈

广东省汕头市金山中学高中信息技术竞赛班第二阶段培训第六课集合与记录类型的综合应用教案

广东省汕头市金山中学高中信息技术竞赛班第二阶段培训第六课集合与记录类型的综合应用教案
过程：
- 各组代表依次上台展示讨论成果，包括主题的现状、挑战及解决方案。
- 其他学生和教师对展示内容进行提问和点评，促进互动交流。
- 教师总结各组的亮点和不足，并提出进一步的建议和改进方向。
6. 课堂小结（5分钟）
目标：回顾本节课的主要内容，强调集合与记录类型综合应用的重要性和意义。
过程：
- 简要回顾本节课的学习内容，包括集合与记录类型的基本概念、组成部分、案例分析等。
4. 学生小组讨论（10分钟）
目标：培养学生的合作能力和解决问题的能力。
过程：
- 将学生分成若干- 小组内讨论该主题的现状、挑战以及可能的解决方案。
- 每组选出一名代表，准备向全班展示讨论成果。
5. 课堂展示与点评（15分钟）
目标：锻炼学生的表达能力，同时加深全班对集合与记录类型的认识和理解。
四、教学资源
1. 软硬件资源：计算机教室、投影仪、电子白板、网络连接。
2. 课程平台：学校内部的教学管理系统、在线学习平台。
3. 信息化资源：《高中信息技术竞赛教程》第二阶段培训用书、教学PPT、案例分析文档、在线练习题库。
4. 教学手段：讲授法、案例分析法、小组讨论法、实践操作法、互动提问法。
五、教学过程设计
3. 学生可能遇到的困难和挑战：在学习集合和记录类型的综合应用时，学生可能会遇到以下困难和挑战：首先，对于集合和记录类型的概念和操作理解不够深入，难以将其应用于实际问题中。其次，对于集合和记录类型的综合应用场景和解决方法不够清晰，难以灵活运用所学知识解决实际问题。此外，学生在实际操作过程中可能会遇到一些具体的技术难题，如集合的交集、并集和差集运算等，需要通过实践和指导来克服。
2. 集合与记录类型基础知识讲解（10分钟）

广东省汕头市金山中学高中信息技术奥林匹克信息学竞赛

广东省汕头市金山中学高中信息技术奥林匹克信息学竞赛

数组【引例】输入20个数，将它们按从大到小的次序排序后输出。

讨论：如果按我们前面学的知识，我们应设20个变量来存储这20个数，如果要排序的数不是20个，而是100个，那我们就应设100个变量？没这么笨吧，我们有更好的办法解决。

§5.1 一维数组数组是由固定数量．．．．的相同类型．．．．的元素按一定顺序排列而成。

只有一个下标类型的数组称为一维数组。

1．数组类型定义和说明类型定义的一般形式为：TYPE <类型标识符> = ARRAY [下标类型] OF <基类型>；数组说明：VAR <数组名> ：<数组类型标识符>；数组名是由用户定义的标识符，下标类型可以是子界类型或枚举类型，下标规定了数组元素的个数和排列次序。

基类型表示数组中每个元素的类型，它可以是任何数据类型，但同一数组中的元素类型必须相同。

如：typeA = array [1..20] of integer;B = array [0..50] of char;Varx , y : A;a : B;其中x 、y 被说明为A 类型数据，即均为拥有20个元素的数组，下标从1到20，元素类型为整型；a 被说明为B 类型数据，即拥有51个元素的数组，下标从0到50，元素类型为字符型。

★ 数组也可以直接在说明部分说明数组的类型，如：var x , y : array [1..20] of integer;a : array [0..50] of char;数组中的每个元素都是变量，每个元素在数组中有固定的位置，可以用数组名及方括号括起的下标．．来表示。

如a 数组中的第5个元素可表示为：a [4]数组元素的运算和变量相同，如：readln (a[4]); x[3]:=x[3]+y[1];2．数组元素的赋值和引用如为一个数组A[1..10] 赋值，可用下列语句实现：for i:=1 to 10 do read (A[i]);如果两个数组类型相同，如数组x 和y ，可用赋值语句： x:=y ；把y 的10个元素值赋给x 的相应元素，它等效于： for i:=1 to 20 do x[i]:=y[i]; 但要给数组元素赋同一个值，不能这样赋值：x:=0;0 1 2 3 4 5 6 7 …… 50 a 下标而应该用如下语句：for i:=1 to 20 do x[i]:=0;【例1】求100以内的所有素数。

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

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

§3 栈和队列§3.1 栈栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。

不含元素的空表称为空栈。

栈的特点：后进先出（Last In First Out），简称：栈的表示和实现和线性表类似，栈也有两种存储结构。

（1）．顺序栈顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。

采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。

在一个程序中，常常会出现同时使用多个栈的情形。

为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。

设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。

所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。

则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。

（2）．链栈采用链式存储结构的栈简称链栈。

对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。

【练习】回文串识别输入一字符串，判断它是否为一回文串。

所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：ten animals I slam in a net. （我将十只动物装在网里）输入：一字符串 输出：Yes 或No§3.2 队列队列（queue ）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。

允许插入的一端称为队尾（rear ），允许删除的一端称为队头（front ）。

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案

§9 内部排序在《数据结构》里，排序一般分为：插入排序、交换排序、选择排序、归并排序和基数排序五种。

写在前面的话：在看下面的各种算法之前，请先想想，如果给你一个无序的数列，你如何去排序？设计出你自己的算法。

还有没有其它方法？相信自己的能力，排序算法是连小学生都可以设计出的！不希望以后听到这样的话：“排序的算法我忘了……”，排序算法不是背出来的！§9.1 插入排序(Insertion Sort)基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

排序过程：【示例】： [初始关键字] [49] 38 65 97 76 13 27 49J=2(38) [38 49] 65 97 76 13 27 49J=3(65) [38 49 65] 97 76 13 27 49J=4(97) [38 49 65 97] 76 13 27 49J=5(76) [38 49 65 76 97] 13 27 49J=6(13) [13 38 49 65 76 97] 27 49J=7(27) [13 27 38 49 65 76 97] 49J=8(49) [13 27 38 49 49 65 76 97]§9.2选择排序基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

排序过程：【示例】：初始关键字 [49 38 65 97 76 13 27 49]第一趟排序后 13 [38 65 97 76 49 27 49]第二趟排序后 13 27 [65 97 76 49 38 49]第三趟排序后 13 27 38 [97 76 49 65 49]第四趟排序后 13 27 38 49 [49 97 65 76]第五趟排序后 13 27 38 49 49 [97 97 76]第六趟排序后 13 27 38 49 49 76 [76 97]第七趟排序后 13 27 38 49 49 76 76 [97]最后排序结果 13 27 38 49 49 76 76 97§9.3 冒泡排序 (BubbleSort)基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

信息学竞赛班数据结构专项培训教程—— 03栈和队列

§3栈和队列§3.1 栈栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。

不含元素的空表称为空栈。

栈的特点：后进先出（Last In First Out），简称：LIFO。

栈的表示和实现和线性表类似，栈也有两种存储结构。

（1）．顺序栈顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。

采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。

在一个程序中，常常会出现同时使用多个栈的情形。

为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。

设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。

所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。

则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。

（2）．链栈采用链式存储结构的栈简称链栈。

对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。

【练习】 回文串识别输入一字符串，判断它是否为一回文串。

所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：ten animals I slam in a net. （我将十只动物装在网里）输入：一字符串 输出：Yes 或No§3.2 队列队列（queue ）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。

允许插入的一端称为队尾（rear ），允许删除的一端称为队头（front ）。

DS03-栈和队列课件PPT


获取队头元素（Front）： 返回队列头部的元素值， 但不删除该元素。
获取队尾元素（Rear）： 返回队列尾部的元素值， 但不删除该元素。
04 栈和队列的应用
栈在括号匹配中的应用
总结词
栈在括号匹配中起到关键作用，通过后进先 出的原则，可以判断括号是否匹配。
详细描述
栈在括号匹配中起到关键作用，它遵循后进 先出的原则，即最后进入的元素最先出来。 通过使用栈，我们可以有效地判断一个括号 的序列是否匹配。当遇到左括号时，将其压 入栈中；当遇到右括号时，从栈顶取出一个 元素进行匹配。如果栈为空或者取出的元素 与右括号不匹配，则说明括号序列不匹配。
返回栈顶的元素值，但不删除该元素。
判断栈是否为空（isEmpty）
判断栈是否为空，如果是空则返回true，否 则返回false。
03 队列的概念和操作
队列的定义
01
队列是一种特殊的线性表，它只允 许在表的前端（front）进行删除 操作，在表的后端（rear）进行插 入操作。
02
队列具有先进先出（FIFO）的特性， 最早进入队列的元素将最先出队。
作。
课程目标
掌握栈和队列的基本 概念、特性和操作。
能够实现栈和队列的 基本操作，并解决实 际问题。
理解栈和队列在算法 设计中的应用。
02 栈的概念和操作
栈的定义
栈是一种特殊的线性表，只允 许在表的一端进行插入和删除 操作。
栈的插入操作称为压栈，删除 操作称为弹栈。
栈具有后进先出（Last In First Out，LIFO）的特性。
THANKS FOR WATCHING
感谢您的观看
队列的性质
队列是一种线性数据结构，遵循先进 先出原则。

信息学竞赛班数据结构专项培训教程——03栈和队列

信息学竞赛班数据结构专项培训教程——03栈和队列栈和队列是数据结构中重要的两种线性结构，它们分别具有后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的特点。

在信息学竞赛中，掌握栈和队列的基本概念、实现方式及应用场景是非常重要的。

本文将为大家介绍栈和队列的相关知识，并讲解一些典型的应用题。

首先，我们来介绍栈。

栈是一个只允许在一端插入和删除操作的线性表，这一端被称为栈顶。

栈的插入操作称为入栈，栈的删除操作称为出栈。

由于栈的特点是后进先出，所以最后入栈的元素将是第一个出栈的元素。

栈可以用数组和链表实现。

使用数组实现栈时，需要定义一个指针top来指示当前栈顶的位置，同时需要一个数组来存放栈元素。

入栈操作相当于在数组中将元素放入top位置，并将top指针向上移动；出栈操作相当于将top所指位置的元素移出，并将top指针向下移动。

使用链表实现栈时，需要定义一个结点结构体包含数据域和指针域，指针域指向下一个结点。

入栈操作相当于在链表头部插入一个结点，并将头指针指向新的结点；出栈操作相当于将头指针指向的结点删除，并将头指针指向下一个结点。

接下来，我们来介绍队列。

队列是一个只允许在一端插入和在另一端删除的线性表，插入操作一般称为入队，删除操作一般称为出队。

队列的特点是先进先出，即第一个入队的元素将是第一个出队的元素。

队列也可以用数组和链表实现。

使用数组实现队列时，需要定义两个指针front和rear，分别指示队列的头部和尾部位置。

入队操作相当于在rear位置插入元素，并将rear指针向后移动；出队操作相当于删除front位置的元素，并将front指针向后移动。

使用链表实现队列时，需要定义一个结点结构体包含数据域和指针域，指针域指向下一个结点。

同时需要定义头指针和尾指针，分别指示队列的头部和尾部。

入队操作相当于在尾指针位置插入结点，并将尾指针移到下一个结点；出队操作相当于删除头指针指向的结点，并将头指针移到下一个结点。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

栈和队列§3.1 栈栈（stack ）是一种仅限于在称为栈顶（top ）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom ）。

不含元素的空表称为空栈。

栈的特点：后进先出（Last In First Out ），简称：LIFO 。

栈的表示和实现 和线性表类似，栈也有两种存储结构。

（1）．顺序栈顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。

采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。

在一个程序中，常常会出现同时使用多个栈的情形。

为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。

设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。

所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。

则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。

（2）．链栈采用链式存储结构的栈简称链栈。

对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose （p ）），否则会出现整个空间被占满，new （p ）过程无法实现（即无法申请新的结点空间）的情况。

【练习】 回文串识别输入一字符串，判断它是否为一回文串。

所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：ten animals I slam in a net. （我将十只动物装在网里） 输入：一字符串 输出：Yes 或No§3.2 队列队列（queue ）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。

允许插入的一端称为队尾（rear ），允许删除的一端称为队头（front ）。

队列的特点：先进先出（|First In First Out ），简称：FIFO 。

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

在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。

对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。

【例3.2.1】逐行打印二项展开式 (a + b )i 的系数： 杨辉三角形 (Pascal’s triangle)要求：采用队列实现！输入： n ——层数（n<50）25 输出：如上图的数字阵列 【算法思路】分析第 i 行元素与第 i +1行元素的关系目的是从前一行的数据可以计算下一行的数据 从第 i 行数据计算并存放第 i+1 行数据a 1 a 2 a 3 …… a n 出队列 出队列队头 队尾 队头 队尾 1 1 i = 11 2 1 21 5 5 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6从数据结构上，可设计一个足够长的一维数组，以实现上述算法。

【练习】根据上述思路分析，用队列的方法完成例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.in3 7 10 5water.out10 90 0 10 0 0 103 0 7 0 7 30 3 7 3 4 33 34 0 4 60 6 4 3 1 63 6 1 0 1 92 7 1 1 0 92 0 8 1 7 20 2 8 3 5 23 2 5（仅有第二组才是最优的一个解。

）§3.3 栈的应用实例§3.3.1 中缀表达式和后缀表达式对于高级语言程序中的表达式，在编译时求解用栈来实现。

任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号，结束符）所组成。

运算符在两个操作数之间的表达式，如a+b、e*f-d等，称为中缀表达式。

求值时，一般会有运算符号的优先权和结合权问题。

例如：a+b*c-d，我们知道b*c要先求，但编译器只能从左到有逐一检查，检查到加号时尚无法知道是否可执行，待检查到乘号时，因乘号运算优先级比加号高，所有a+b不可以被执行，待继续基础到减号时，方可执行b*c。

而后缀表达式是运算符在两个操作数之后，如ab*，也称为“逆波兰式”。

后缀表达式可以顺序计算求值，所以编译程序常把中缀表达式变换成后缀表达式，然后再求值。

(一)、将中缀表达式转换成后缀表达式在转换过程中为了确定计算次序，要按运算符的优先级进行，各运算符优先级如下表，优先级数大的先执行。

输入：中缀表达式，如： B * (D-C) + A输出：后缀表达式，如： BDC-*A+【算法思想】设立一个栈来实现中缀表达式变后缀表达式。

设中缀表达式在字符数组E中，E的末尾再加‘#’作为结束符，将转成后缀表达式，存于字符串A中。

对E中表达式自左向右扫描，遇数直接送到A中，若遇到运算符就考虑进栈，进栈的原则是保持栈顶的运算符优先级最高。

即若欲进栈的算符是‘( ’或欲进栈的运算符优先级大于栈顶运算符的优先级，则将算符入栈，否则从栈中退出算符送至A中，直至欲进栈的算符优先级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。

若遇到‘)’时，将栈中算符退出送入A中，直至退出‘( ’为止。

若遇表达式结束符‘#’，则依次退出栈中算符送入A中。

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

【参考程序段】const m=100;var E , A , S : array [1..m] of char;{ E中为中缀式，A中为后缀式，S为栈}i , j , t : integer;procedure postexp; 扫描E 栈S 转换至AB * B* * ( B( * ( BD * ( -BD- * ( -BDC * BDC) + BDC-+ + BDC-*A BDC-*A# BDC-*A+图3_1begini:=1; j:=1; t:=0;while E[ i ]<>’#’ do begincase E[ i ] of‘a’.. ‘z’, ‘A’.. ‘Z’ : beginA[ j ]:=E[ i ]; j:=j+1;end;‘(’ : begint:=t+1; S[ t ]:= ‘(’;end;‘)’ : beginwhile s[ t ]< > ‘(’ do beginA[ j ]:=s[ t ]; j:=j+1; t:=t-1;end;t:=t-1;end;‘+’, ‘-’ : beginwhile (t< >0) and (s[t]< > ‘(’) do beginA[ j ]:=S[ t ]; j:=j+1; t:=t-1;end;t:=t+1; s[ t ]:=E[ i ];end;‘*’, ‘/’ : beginwhile (t< >0) and (S[ t ]= ‘*’ or S[ t ]= ‘/’) do beginA[ 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 beginA[ j ]:=S[ t ]; j:=j+1; t:=t-1;end;A[ j ]:= ‘#’;end;(二)、对后缀表达式求值计算一个后缀表达式的值，在算法上比中缀表达式要简单得多，这是因为后缀表达式有两个优点：表达式无括号，也不需考虑运算符的优先级。

【算法思想】对后缀表达式求值要使用一个栈来实现。

自左至右扫描后缀表达式，若遇数就入栈，若遇到运算符就从栈中退出两个数进行运算，并把计算结果入栈。

如此下去，直至遇到结束符“#”为止。

最后栈底元素值为所求得的结果。

【练习】将一个中缀表达式转换成后缀表达式，并对后缀表达式求值。

输入格式：（输入文件 bds.in）第一行：中缀表达式，运算数均为大写字母，运算符含乘方‘^’第二行开始：每行为表达式中字母，及其对应的值，输入顺序按字典排序输出格式：（输入文件 bds.out）第一行：该中缀表达式所对应的后缀表达式第二行：该表达式的值输入： (bds.in) 输出： (bds.out)B * (D - C) + A^CA 4B 10C 3D 8 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色均与相邻的某区域发生重色，则需退栈回溯，修改栈顶区域的色数。