NOIP高中信息技术竞赛资料 - -数据结构(5)

第3章 栈

提示算法：为实现算符优先算法，可以实现2个工作栈，一个是操作数栈opnd，用来存放操作数，如3、4、8等，另一个是运算符栈optr，用来存放运算符。

首先将标志“#”进运算符栈的栈底。

然后依次扫描，按照栈的后进先出原则进行： （1）遇到操作数，进操作数栈；

（2）遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较， 若若高于栈顶元素则进栈，继续扫描下一符号，

否则，将运算符栈的栈顶元素退栈，形成一个操作码Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数a、b，让计算机对操作数与操作码完成一次运算操作，即aQb，并将其运算结果存放在操作数栈中……

模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。

附源程序：

第3章 栈

3.背包问题

问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。

算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。

若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。

具体实现：设用数组weight[1..N]，stack[1,N]分别存放物品重量和已经装入背包（栈）的物品序号，MaxW表示背包的最大装载量。每进栈一个物品，就从MaxW中减去该物品的质量,设i为待选物品序号,若MaxW-weight[i]>=0，则该物品可选；若MaxW-weight[i] < 0，则该物品不可选,且若i>n，则需退栈，若此时栈空，则说明无解。

练习:完整完成背包问题

第4章 队列

第4章 队列

队列与栈一样都是运算受限的线性表，但与栈的限制不同。

4.1 队列的概念及运算

队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。

假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。

图1

队列的运算：

为一种抽象数据类型，常用的队列运算有:

第4章 队列

4.2 队列的存储与实现

队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。

1.顺序队列及基本操作

（1）顺序队列：队列的顺序存储结构称为顺序队列，它是运算受限的顺序表。

（2）顺序队列的表示

①和顺序表一样，顺序队列用一个数组来存放当前队列中的元素。 ②由于随着入队和出队操作的变化，队列的队头和队尾的位置是变动的，所以应设置两个整型量front和rear分别指示队头和队尾在向量空间中的位置，它们的初值在队列初始化时均应置为0。通常称front为队头指针，称rear为队尾指针。

（3）顺序队列的基本操作

①入队：入队时将新元素插入rear所指的位置，然后将rear加1。 ②出队：出队时删去front所指的元素，然后将front加1并返回被删元素。 注意：

①当头尾指针相等时，队列为空。

②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

顺序队列基本操作如图3.3。

(c)A出队

(d)BC出队

0 front

rear

(a)空队列 B 1 front

C 2

3 rear

0 front

rear

(b)ABC入队 1

2

3 front rear

0 1

2

3

A 0 B 1

C 2

3 第4章 队列

图3.3 顺序队列基本操作

（4）顺序队列中的溢出现象

①“下溢”现象：当队列为空时，做出队操作产生的溢出现象。

②“真上溢”现象：当队列满时，做入队操作产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

③“假上溢”现象：由于入队和出队操作中，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用。当队列中实际元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。

（5）解决“假上溢”现象的方法

①当出现“假上溢”现象时，把所有的元素向低位移动，使得空位从低位区移向高位区，显然这种方法很浪费时间。

②把队列的向量空间的元素位置0~Queuesize-1看成一个首尾相接的环形，当进队的队尾指针等于最大容量，即rear==Queuesize时，使rear=0。

2.循环队列

（1）循环队列：把向量空间的元素位置首尾相接的顺序队列称为循环队列。 例如，设队列的容量Queuesize=8，元素a1，a2，a3，a4，a5，a6，a7依次入队，然后a1，a2，a3出队的循环队列如图3.4。

5 a6 4 a5 a4 2 6 a7 7 0 1 rear 3 front 图3.4 循环队列

（2）循环队列头尾指针的操作

循环队列Q进行出队、入队操作时，头尾指针仍要加1。当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：

①利用选择结构

if(i+1==QueueSize)//i为Q->front或Q->rear

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(5)在线全文阅读。