信息學(xué)競(jìng)賽數(shù)據(jù)結(jié)構(gòu)專項(xiàng)培訓(xùn)教程03棧和隊(duì)列

出（bottom 入出…………棧棧和線性表類似，棧也有兩種結(jié)構(gòu)（1．所以，可以采用兩個(gè)棧共享空間的方法：假設(shè)在程序中需設(shè)兩個(gè)棧，并共維數(shù)組棧1 棧1 棧2 棧2（2．采用鏈 （dispos（pii+1從第i行數(shù)據(jù)計(jì)算并存放第i+1行數(shù)據(jù)輸出：O表示老隊(duì)員，Y[問(wèn)題描述有三個(gè)分別裝有a水、b水和c水的量筒（c>b>a>0，且ba）,c筒裝滿水，a與b均為空筒，三個(gè)筒相互倒水且把水倒往三個(gè)筒之外，一個(gè)往另一個(gè)倒出容量為d[輸入格式 [輸出格式 c（）37109000030707303734333404606431092085§3.3§3.3.1運(yùn)算優(yōu)先級(jí)比加號(hào)高，所有a+bb*c。而后綴表達(dá)式是運(yùn)算符在兩個(gè)操作數(shù)之后，如ab*A+B*B*(D-C)+40.+(10.-8.)*2.-16./ABC*+40.10.8.-2.*+16.8./ 321B*D-CBDC-E中，E的末尾再加‘#’作為結(jié)束符，將轉(zhuǎn)成后綴表達(dá)式，存于字符串A中。(’或欲進(jìn)棧的運(yùn)算符優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)，則將算符入棧，否則從棧中退出算符送至AB*B**B(*B*B**B(*BD*(-*(C*)++A+#B*(D-CA轉(zhuǎn)換成BDC-*A+3_1所示。 E,A,S:array E中為中綴式，A中為后綴式，S為棧}i,j,t:integer; E[i]<>’#’do E[i]of‘a(chǎn)’..‘z’,‘A’..‘Z’ A[j]:=E[i ‘(’ S[t]:=‘)’ s[t]<>‘(’ A[j]:=s[t ‘+’,‘-’ (t<>0)and(s[t]<>‘(’) dobeginA[j]:=S[t]; s[t]:=E[i‘*’,‘/’ while(t<>0)and(S[t]=‘*’or S[t]=‘/’)dobeginA[j]:=S[t]; end; S[t]:=E[i t< A[j]:=S[t A[j]:=輸入格式：（輸入文件bds.in）輸出格式：（輸入文件bds.out）第二行：該表達(dá)式的值輸入：輸出：B*(D-C)+BDC-*AC^A §3.3.2地圖問(wèn)于四色對(duì)地圖，使相鄰的行政區(qū)域不重色。應(yīng)用3色、401的區(qū)域開始逐一進(jìn)行染色，對(duì)每1，2，3，4依次進(jìn)行試探，并盡可能14色均與相鄰的某區(qū)域發(fā)生重

圖Rji1234567101111102100001031001100410101Rji123456710111110210000103100110041010110510110106110110070000000S1:n)，棧的下標(biāo)值表S63表示063。 mapcolor(varr:adjr; vars:ads);s[ {011色 {i為區(qū)域號(hào)，j為染色號(hào)} (j<=4)and(i<n) {k指示已染域號(hào) (k<i)and(s[k]*R[i,k]<>j {判斷相鄰區(qū)是否已染色ifk<i {用j+1色繼續(xù)試探} s[i]:=

{與相鄰區(qū)不重色，染色結(jié)果進(jìn)棧，繼續(xù)對(duì)下1色進(jìn)行試探} j.> i:=i- j:=s[i {變更棧頂區(qū)域的染數(shù)432213422143221342213212321423213423211342321 2 Ri6j＝1234數(shù)“4也不存在除4以外的可染數(shù)則需繼續(xù)退棧變更S[4]:=4，由此S[5]:=3， §3.4.1遞歸形式一般有兩種——直接遞歸和間接遞歸，而棧是實(shí)現(xiàn)遞歸的重要2】fac(nn

n×fac(n- fac(n)functionfac(n:integer):integer;ifn=0thenelsefac:=n*fac(n-

fac

fac fac facfac63×fac 2×fac 1×fac fac(0)=這個(gè)條件語(yǔ)句就是遞歸邊界。例如，fac函數(shù)體中的“if fac:=1(二)AB，子程序B又調(diào)用子程序AB1．BA的局部對(duì)象procedureA;procedureB;A…

{B… {A…2．AB例：procedureB(形式參數(shù)表):forward; {B的完整說(shuō)明在后}procedurdeA;…B(實(shí)參表 {在A中調(diào)用procedureB; {B的首部縮寫，形式參數(shù)表不再列出}… {B…38×8S Si]i8行配置也是合理時(shí)，就找到一個(gè)解。因此，top=93itop)（S[topi）1top-1iS[j]≠i，1≤j≤top-itop)的兩條對(duì)角線上不能有“皇后|S[j-i||j-top|，1≤j≤top-programqueen;total s:array[1..8]of1..8; proceduresearch(top:integer);i,j:p:boolean; ifthenbegin wrin(total,'step:fori:=1to8dowrite(s[i],'');elsebeginfori:=1to8dobegin 1iftop>1then while(j<top)andpdobeginif(s[j]=i)or(abs(s[j]-i)=abs(j-top))thenp:=false;ifpthenbegin top+1 0} 如斐波那契數(shù)列的定義：fnfn-1+fn-2f0=1；f1=2 fib(n:integer)