信息学奥赛数据结构教程PASCAL版.doc

信息学奥赛数据结构教程PASCAL版第二课堆栈和队列一、堆栈1概述栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。好果我们把冼净的碗“摞上”称为进栈，把“取用碗”称为出栈，那么，上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”，或者说，元素的插入和删除是在表的一端进行而已。一般而言，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。若给定一个栈S=（a1, a2，a3，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。栈中元素按a1, a2，a3，an 的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，a1 。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此栈又称为后进先出(LIFOLast In First Out)表。我们常用一个图来形象地表示栈，其形式如下图：通常，对栈进行的运算主要有以下几种：（1） 往栈顶加入一个新元素，称进栈；（2） 删除栈顶元素，称退栈；（3） 查看当前的栈顶元素，称读栈。此外，在使用栈之前，首先需要建立一个空栈，称建栈；在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。2栈的存储结构栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。因此，当用编程语言写程序时，用一维数组来建栈十分方便。例如，设一维数组STACK1.n 表示一个栈，其中n为栈的容量，即可存放元素的最大个数。栈的第一个元素，或称栈底元素，是存放在STACK1处，第二个元素存放在STACK2处，第i个元素存放在STACKi处。另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0，当top=n时，表示栈满。3对栈的几种运算的实现方法：（1）建栈这比较简单，只要建立一个一维数组，再把栈顶指针置为零。栈的容量根据具体的应用要求而定。（2）测试栈测试栈顶指针的值，若top=0，则栈空；若top=n，则栈满。（3）读栈若top=0，则栈空，无栈顶元素可读，出错；若top0，则回送栈顶元素的值STACKtop。 使用一维数组来实现以上三种运算都比较简单，不必为其专门编写过程，只要在需要时，在程序中直接写入适当的语句即可。至于进栈和出栈也不复杂，下面给出它们的算法。（4）进栈将栈顶指针加1后，再把新元素送到栈顶。假设新元素x为整型。procedure pushstack(var stack:arraytype;var top:integer;n:integer;x:elementtype);beginif top=n then begin witeln(Stack full!); halt endelse begin top:=top+1; stacktop:= x endend;（5） 退栈取得栈顶元素的值后，再把栈顶指针top减1。procedure popstack(stack:arraytype;var top:integer;var x:elementtype);beginif top=0 then begin writeln(Stack empty!); halt endelse begin x:=stacktop; top:=top-1 endend;4栈的应用举例处理表达式是高级语言的编绎中的一个基本问题。它的实现是栈的一个重要应用。通过对处理表达式的讨论，可以帮助我们进一步了解栈的性能。【例5-1】为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为后缀运算符在后，如X/Y写为XY/表达式。在这样的表示中可以不用括号即可确定求值的顺序，如：(P+Q)*(RS) PQ+RS*。后缀表达式的处理过程如下：扫描后缀表达式，凡遇操 作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。 输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与 输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由（加）、（减）、（乘）、（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。以下是一个运行实例，下划线表示输入。Input a expression:XA（YB） Z FXAYBZF 算法设计设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。标准程序中的数组f用来存放运算符之间的优先级关系，1表示前面的运算符优先于后面的运算符，-1表示后面的运算符优先于前面的运算符，0表示前面的运算符的优先级与后面的运算符相同，2表示这两个运算符如果在扫描中相遇的话，意味着该表达式是错误的。需要补充的是：左括号的优先级是最高的，而里层的左括号比外层的左括号更优先，右括号的优先级是除#号以外最低的，但左括号和右括号的优先级则是相等的，这样定义的目的是为了消去括号。上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。下图是对范例表达式的扫描示意图：程序清单program ex5_1(input,output);const max=100;op_set:set of char=+,-,*,/;letter:set of char=A.Z,a.z;varexpression,result:string;procedure scan(expression:string);vari,top1,top2:integer;ovs:array 1.max of stringmax;ops:array 1.max of char;f:array#./,#./ of shortint; f=firstbeginf+,+:=1; f+,-:=1; f+,*:=-1; f+,/:=-1;f+,(:=-1; f+,):=1; f+,#:=1;f-,+:=1; f-,-:=1; f-,*:=-1; f-,/:=-1;f-,(:=-1; f-,):=1; f-,#:=1;f*,+:=1; f*,-:=1; f*,*:=1; f*,/:=1;f*,(:=-1; f*,):=1; f*,#:=1;f/,+:=1; f/,-:=1; f/,*:=1; f/,/:=1;f/,(:=-1; f/,):=1; f/,#:=1;f(,+:=-1; f(,-:=-1; f(,*:=-1; f(,/:=-1;f(,(:=-1; f(,):=0; f(,#:=2;f),+:=2; f),-:=2; f),*:=2; f),/:=2;f),(:=2; f),):=2; f),#:=2;f#,+:=-1; f#,-:=-1; f#,*:=-1; f#,/:=-1;f#,(:=-1; f#,):=2; f#,#:=0;expression:=expression+#;ops1:=#; top1:=0; top2:=1;for i:=1 to length(expression) dobeginif expressioni in letterthen begin top1:=top1+1; ovstop1:=expressioni endelse beginwhile fopstop2,expressioni=1 dobeginovstop1-1:=ovstop1-1+ovstop1+opstop2;top1:=top1-1;top2:=top2-1end;if fopstop2,expressioni=0then top2:=top2-1else begin top2:=top2+1;opstop2:=expressioni end;endend;result:=ovs1end;beginwrite(Input a expression:);readln(expression);scan(expression);writeln(The result is: ,result)end.二、队列1、概述队列(Queue)也是线性表的一种特殊情况，但它与栈不同，其所有的插入均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插入的一端称队尾(Rear)，允许删除的一端称队头(Front)。队列的结构特点是先进队的元素先出队。假设有队列Q=（a1, a2，a3，an），则队列Q中的元素是按a1, a2，a3，an的次序进队，而第一个出队的应该是a1，第二个出队的应该是 a2，只有在ai-1出队以后，ai才可以出队（1in）。因此，通常又把队列叫做先进先出（FIFIFirst In First Out）表。关于队列的运算主要包括以下几种：进队（插入）把一个新元素添加在队列的末尾；出队（删除）撤去队头元素；查看（读队头）查看当前队头元素。此外，还有建立队列和测试队列等。2、队列的存储结构同栈一样，在计算机中，可以用向量作为队列的存储结构，并且常借助于编程语言中的一维数组来实现。为了指示队头和队尾的位置，还要再设置两个指针变量：front和rear分别指向队列的头和尾。假设有一个队列，我们用一维数组QUEUE1.n来表示，n为队列的最大容量，并约定头指针front总是指在队列中实际头元素的前面一个位置上，而尾指针rear总是指向队尾元素。采用这样的约定后，只有当队列中没有元素即队空时，才会出现front=rear，因此front=rear被用作测试队空的条件。显然，队列的初始状态为front=rear=0。3、对队列的几种运算的实现方法：（1）建队数组说明type arraytype=array1.n of elementtype;var Q:arraytype; front:=0;rear:=0;（2）测队空若front=rear，则队空。（3）读队头x:=Qfront+1;（4）进队procedure addQ(var Q:arraytype;var rear:integer; n:integer; x:elementtype);beginif rear=n then begin writeln(Queue full!); halt endelse begin rear:=rear+1; Qrear:=x endend;（5）出队procedure deleteQ(var Q:arraytype;var front;rear ,n:integer;var x:elementtype);beginif front=rearthen begin writeln(Queue empty!); halt endelse begin front:=front+1; x:=Qfrontendend;四、队列应用举例【例5-2】一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。样例：INPUTD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2OUTPUT26.95（该数据表示最小费用） 问题分析看到这道题，许多人都马上判断出穷举是不可行的，因为数据都是以实数的形式给出的。但是，不用穷举，有什么方法是更好的呢？递推是另一条常见的思路，但是具体方法不甚明朗。既然没有现成的思路可循，那么先分析一下问题不失为一个好办法。由于汽车是由始向终单向开的，我们最大的麻烦就是无法预知汽车以后对汽油的需求及油价变动；换句话说，前面所买的多余的油只有开到后面才会被发觉。提出问题是解决的开始。为了着手解决遇到的困难，取得最优方案，那就必须做到两点，即只为用过的汽油付钱；并且只买最便宜的油。如果在以后的行程中发现先前的某些油是不必要的，或是买贵了，我们就会说：“还不如当初不买。”由这一个想法，我们可以得到某种启示：假设我们在每个站都买了足够多的油，然后在行程中逐步发现哪些油是不必要的，以此修改我们先前的购买计划，节省资金；进一步说，如果把在各个站加上的油标记为不同的类别，我们只要在用时用那些最便宜的油并为它们付钱，其余的油要么是太贵，要么是多余的，在最终的计划中会被排除。要注意的是，这里的便宜是对于某一段路程而言的，而不是全程。算法设计由此，我们得到如下算法：从起点起(包括起点)，每到一个站都把油箱加满（终点除外）；每经过两站之间的距离，都按照从便宜到贵的顺序使用油箱中的油，并计算花费，因为这是在最优方案下不得不用的油；如果当前站的油价低于油箱中仍保存的油价，则说明以前的购买是不够明智的，其效果一定不如购买当前加油站的油，所以，明智的选择是用本站的油代替以前购买的高价油，留待以后使用，由于我们不是真的开车，也没有为备用的油付过钱，因而这样的反悔是可行的；当我们开到终点时，意味着路上的费用已经得到，此时剩余的油就没有用了，可以忽略。数据结构采用一个队列：存放由便宜到贵的各种油，一个头指针指向当前应当使用的油（最便宜的油），尾指针指向当前可能被替换的油（最贵的油）。在一路用一路补充的过程中同步修改数据，求得最优方案。注意：每到一站都要将油加满，以确保在有解的情况下能走完全程。并假设出发前油箱里装满了比出发点贵的油，将出发点也看成一站，则程序循环执行换油、用油的操作，直到到达终点站为止。本题的一个难点在于认识到油箱中油的可更换性，在这里，突破现实生活中的思维模式显得十分重要。程序清单program ex5_2(input,output);const max=1000;type recordtype=recordprice,content:realend;vari,j,n,point,tail:longint;content,change,distance2,money,use:real;price,distance,consume:array0.max of real;oil:array 0.max of recordtype;beginwrite(Input DI,C,D2,P:);readln(distance0,content,distance2,price0);write(Input N:);readln(n);distancen+1:=distance0;for i:=1 to n dobeginwrite(Input D,i,P,i,:);readln(distancei,pricei)end;distance0:=0;for i:=n downto 0 do consumei:=(distancei+1-distancei)/distance2;for i:=0 to n doif consumeicontent thenbegin writeln(No Solution); halt end;money:=0; tail:=1; change:=0;oiltail.price:=price0*2; oiltail.content:=content;for i:=0 to n dobeginpoint:=tail;while (point=1) and (oilpoint.price=pricei) dobeginchange:=change+oilpoint.content;point:=point-1end;tail:=point+1;oiltail.price:=pricei;oiltail.content:=change;use:=consumei; point:=1;while (use1e-6) and (point=oilpoint.contentthen beginuse:=use-oilpoint.content;money:=money+oilpoint.content*oilpoint.price;point:=point+1 endelse beginoilpoint.content:=oilpoint.content-use;money:=money+use*oilpoint.price;use:=0end;for j:=point to tail do oilj-point+1:=oilj;tail:=tail-point+1;change:=consumeiend;writeln(money:0:2)end.【例5-3】分油问题：设有大小不等的3个无刻度的油桶，分别能够存满，X，Y，Z公升油（例如X=80，Y=50，Z=30）。初始时，第一个油桶盛满油，第二、三个油桶为空。编程寻找一种最少步骤的分油方式，在某一个油桶上分出targ升油（例如targ=40）。若找到解，则将分油方法打印出来；否则打印信息“UNABLE”等字样，表示问题无解。问题分析 这是一个利用队列方法解决分油问题的程序。分油过程中，由于油桶上没有刻度，只能将油桶倒满或者倒空。三个油桶盛满油的总量始终等于开始时的第一个油桶盛满的油量。算法设计 分油程序的算法主要是，每次判断当前油桶是不是可以倒出油，以及其他某个油桶是不是可以倒进油。如果满足以上条件，那么当前油桶的油或全部倒出，或将另一油桶倒满，针对两种不同的情况作不同的处理。程序中使用一个队列Q，记录每次分油时各个油桶的盛油量和倾倒轨迹有关信息，队列中只记录互不相同的盛油状态（各个油桶的盛油量），如果程序列举出倒油过程的所有不同的盛油状态，经考察全部状态后，未能分出TARG升油的情况，就确定这个倒油问题无解。队列Q通过指针front和rear实现倒油过程的控制。程序清单program ex5_3(input,output);const maxn=5000;type stationtype=array1.3 of integer;elementtype=recordstation:stationtype;out,into:1.3;father:integerend;queuetype=array 1.maxn of elementtype;varcurrent,born:elementtype;q:queuetype;full,w,w1:stationtype;i,j,k,remain,targ,front,rear:integer;found:boolean;procedure addQ(var Q:queuetype;var rear:integer; n:integer; x:elementtype);beginif rear=nthen begin writeln(Queue full!); halt endelse begin rear:=rear+1; Qrear:=x endend;procedure deleteQ(var Q:queuetype;var front:integer;rear,n:integer;var x:elementtype);beginif front=rearthen begin writeln(Queue empty!); halt endelse