廣東省汕頭市金山中學(xué)高中信息技術(shù)競賽班數(shù)據(jù)結(jié)構(gòu)專項(xiàng)培訓(xùn)教程03棧和隊(duì)列教案

1、3 棧和隊(duì)列3.1 棧出棧入棧棧頂棧底ana1a2棧（stack）是一種僅限于在稱為棧頂（top）的一端進(jìn)行插入和刪除操作的線性表，另一端則被為棧底（bottom）。不含元素的空表稱為空棧。棧的特點(diǎn)：后進(jìn)先出（Last In First Out），簡稱：LIFO。l 棧的表示和實(shí)現(xiàn) 和線性表類似，棧也有兩種存儲結(jié)構(gòu)。 （1）順序棧 順序棧即采用的順序存儲結(jié)構(gòu)來表示棧，通常采用數(shù)組來實(shí)現(xiàn)。采用順序棧受數(shù)組空間的約束，有“溢出”的可能，編程前應(yīng)作空間估算，若有溢出可能，應(yīng)作溢出判斷及相應(yīng)的處理。在一個(gè)程序中，常常會出現(xiàn)同時(shí)使用多個(gè)棧的情形。為了不因棧上溢而產(chǎn)生錯(cuò)誤中斷，必須給每個(gè)棧預(yù)分一個(gè)較大的空

2、間，但這并不容易做到，因?yàn)闂?shí)際所用的最大空間很難估計(jì)；而且各個(gè)棧的實(shí)際使用量在使用期間是變化的，往往會有這樣的情況，即其中一個(gè)棧發(fā)生上溢，而另一個(gè)棧還是空的。設(shè)想，若令多個(gè)棧共享空間，則將提高空間的使用效率，并減少發(fā)生棧上溢的可能。所以，可以采用兩個(gè)棧共享空間的方法：假設(shè)在程序中需設(shè)兩個(gè)棧，并共享一維數(shù)組空間。則利用“棧底位置不變”的特性，可將兩個(gè)棧的棧底分別設(shè)在數(shù)組空間的兩端，然后各自向中間伸展（如圖），僅當(dāng)兩個(gè)棧的棧頂相遇時(shí)才可能發(fā)生上溢。棧1棧2棧1底棧1頂棧2頂棧2底（2）鏈棧 采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧簡稱鏈棧。 對于鏈棧，不含產(chǎn)生單個(gè)棧溢出的情況，但要記得回收結(jié)點(diǎn)空間（dispose（

3、p），否則會出現(xiàn)整個(gè)空間被占滿，new（p）過程無法實(shí)現(xiàn)（即無法申請新的結(jié)點(diǎn)空間）的情況?！揪毩?xí)】 回文串識別輸入一字符串，判斷它是否為一回文串。所謂回文串是指去掉其中的空格與標(biāo)點(diǎn)符號等非字母符號后，從前后兩個(gè)方向讀到的串相同，例如：ten animals I slam in a net. （我將十只動物裝在網(wǎng)里） 輸入：一字符串 輸出：Yes或No3.2 隊(duì)列隊(duì)列（queue）是所有的插入都在一端進(jìn)行，而所有的刪除都在另一端進(jìn)行的線性表。允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。隊(duì)列的特點(diǎn)：先進(jìn)先出（|First In First Out），簡稱：FIFO。a

4、1 a2 a3 an 出隊(duì)列出隊(duì)列隊(duì)頭隊(duì)尾l 隊(duì)列的表示和實(shí)現(xiàn)和棧一樣，隊(duì)列也有順序存儲和鏈?zhǔn)酱鎯煞N表示和實(shí)現(xiàn)方法。在順序存儲結(jié)構(gòu)中，同樣有溢出可能，即元素因隊(duì)滿而無法入隊(duì)。對于隊(duì)列來說，可以采用循環(huán)隊(duì)列的技巧，僅當(dāng)隊(duì)頭與隊(duì)尾相遇時(shí)為隊(duì)滿。隊(duì)頭隊(duì)尾【例3.2.1】逐行打印二項(xiàng)展開式 (a + b)i 的系數(shù)：楊輝三角形 (Pascals triangle) 1 1 i =1 1 2 12 1 5 5 13 1 4 6 4 14 1 510 10 5 15 1 6152015 6 16要求：采用隊(duì)列實(shí)現(xiàn)！輸入： n 層數(shù)（nba0，且b與a互質(zhì)）, 如果c筒裝滿水，a與b均為空筒，三個(gè)筒相互倒

5、水且不準(zhǔn)把水倒往三個(gè)筒之外，一個(gè)往另一個(gè)筒倒水記為一次倒水。問是否能量出d升水(cd0)，若能，請求出最少的倒水次數(shù)使它能倒出容量為d的水的方案。輸入格式數(shù)據(jù)存放在當(dāng)前目錄下的文本文件“water.in”中。文件中以一行的形式存放四個(gè)正整數(shù)，分別a、b、c、d的值。輸出格式答案輸出到當(dāng)前目錄下的文本文件“water.out”中。第一次行是最少的倒水次數(shù)Q，第二起的Q行是每次例水時(shí)量簡的水量，依次為a、b、c （輸入與輸出數(shù)據(jù)中同一行相鄰兩個(gè)數(shù)之間用空格區(qū)分。）輸入輸出舉例water.in 3 7 10 5water.out 10 9 0 0 10 0 0 10 3 0 7 0 7 3 0 3

6、7 3 4 3 3 3 4 0 4 6 0 6 4 3 1 6 3 6 1 0 1 9 2 7 1 1 0 9 2 0 8 1 7 2 0 2 8 3 5 2 3 2 5 （僅有第二組才是最優(yōu)的一個(gè)解。）3.3 棧的應(yīng)用實(shí)例3.3.1 中綴表達(dá)式和后綴表達(dá)式對于高級語言程序中的表達(dá)式，在編譯時(shí)求解用棧來實(shí)現(xiàn)。任何一個(gè)表達(dá)式是由操作數(shù)（常量、常量名、變量名）、運(yùn)算符（算術(shù)、關(guān)系和邏輯三種運(yùn)算符）和界限符（左、右圓括號，結(jié)束符）所組成。運(yùn)算符在兩個(gè)操作數(shù)之間的表達(dá)式，如a+b、e*f-d等，稱為中綴表達(dá)式。求值時(shí)，一般會有運(yùn)算符號的優(yōu)先權(quán)和結(jié)合權(quán)問題。例如：a+b*c-d，我們知道b*c要先求，但

7、編譯器只能從左到有逐一檢查，檢查到加號時(shí)尚無法知道是否可執(zhí)行，待檢查到乘號時(shí)，因乘號運(yùn)算優(yōu)先級比加號高，所有a+b不可以被執(zhí)行，待繼續(xù)基礎(chǔ)到減號時(shí)，方可執(zhí)行b*c。而后綴表達(dá)式是運(yùn)算符在兩個(gè)操作數(shù)之后，如ab*，也稱為“逆波蘭式”。后綴表達(dá)式可以順序計(jì)算求值，所以編譯程序常把中綴表達(dá)式變換成后綴表達(dá)式，然后再求值。下表是中綴表達(dá)式所對應(yīng)的后綴表達(dá)式：中綴表達(dá)式后綴表達(dá)式A + B * CB * (D-C) + A40.+ (10.-8.) * 2. -16. / 8.ABC * +BDC-*A+40.10.8.-2. * + 16. 8. / -(一)、將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式在轉(zhuǎn)換過程中

8、為了確定計(jì)算次序，要按運(yùn)算符的優(yōu)先級進(jìn)行，各運(yùn)算符優(yōu)先級如下表，優(yōu)先級數(shù)大的先執(zhí)行。運(yùn)算符 (乘方)* , /+ , -優(yōu)先級321【例3.3.1】將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。 輸入： 中綴表達(dá)式，如： B * (D-C) + A 輸出： 后綴表達(dá)式，如： BDC-*A+【算法思想】設(shè)立一個(gè)棧來實(shí)現(xiàn)中綴表達(dá)式變后綴表達(dá)式。設(shè)中綴表達(dá)式在字符數(shù)組E中，E的末尾再加#作為結(jié)束符，將轉(zhuǎn)成后綴表達(dá)式，存于字符串A中。對E中表達(dá)式自左向右掃描，遇數(shù)直接送到A中，若遇到運(yùn)算符就考慮進(jìn)棧，進(jìn)棧的原則是保持棧頂?shù)倪\(yùn)算符優(yōu)先級最高。即若欲進(jìn)棧的算符是 ( 或欲進(jìn)棧的運(yùn)算符優(yōu)先級大于棧頂運(yùn)算符的優(yōu)先級，則將算符

9、入棧，否則從棧中退出算符送至A中，直至欲進(jìn)棧的算符優(yōu)先級大于棧頂算符的優(yōu)先級，這時(shí)才將欲進(jìn)棧的算符入棧。若遇到)時(shí)，將棧中算符退出送入A中，直至退出( 為止。若遇表達(dá)式結(jié)束符#，則依次退出棧中算掃描E棧S轉(zhuǎn)換至AB*B* (B(* (BD* ( -BD-* ( -BDC*BDC)+BDC-+BDC-*ABDC-*A#BDC-*A+ 圖3_1符送入A中。根據(jù)上述算法，將中綴表達(dá)式B * (D-C) + A轉(zhuǎn)換成后綴表達(dá)式BDC-*A+ 的過程圖3_1所示?！緟⒖汲绦蚨巍縞onst m=100; var E , A , S : array 1.m of char; E中為中綴式，A中為后綴式，S為

10、棧 i , j , t : integer;procedure postexp;begin 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 (t0) and (st () do begin A j :

11、=S t ; j:=j+1; t:=t-1; end; t:=t+1; s t :=E i ; end; *, / : beginwhile (t0) 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 t0 do begin A j :=S t ; j:=j+1; t:=t-1; end; A j := #;end;(二)、對后綴表達(dá)式求值計(jì)算一個(gè)后綴表達(dá)式的值，在算法上比中綴表達(dá)

12、式要簡單得多，這是因?yàn)楹缶Y表達(dá)式有兩個(gè)優(yōu)點(diǎn)：表達(dá)式無括號，也不需考慮運(yùn)算符的優(yōu)先級?！舅惴ㄋ枷搿繉缶Y表達(dá)式求值要使用一個(gè)棧來實(shí)現(xiàn)。自左至右掃描后綴表達(dá)式，若遇數(shù)就入棧，若遇到運(yùn)算符就從棧中退出兩個(gè)數(shù)進(jìn)行運(yùn)算，并把計(jì)算結(jié)果入棧。如此下去，直至遇到結(jié)束符“#”為止。最后棧底元素值為所求得的結(jié)果?！揪毩?xí)】將一個(gè)中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，并對后綴表達(dá)式求值。 輸入格式： （輸入文件 bds.in）第一行：中綴表達(dá)式，運(yùn)算數(shù)均為大寫字母，運(yùn)算符含乘方 第二行開始： 每行為表達(dá)式中字母，及其對應(yīng)的值，輸入順序按字典排序 輸出格式： （輸入文件 bds.out）第一行： 該中綴表達(dá)式所對應(yīng)的后綴表達(dá)式

13、第二行： 該表達(dá)式的值輸入輸出舉例：輸入： (bds.in)輸出： (bds.out)B * (D - C) + ACA 4B 10C 3D 8B D C - * A C +1143.3.2 地圖著色問題圖 3_3對地圖著色，可使用“四染色”定理，它是計(jì)算機(jī)科學(xué)中的著名定理之一，可以用不多于四色對地圖著色，使相鄰的行政區(qū)域不重色。應(yīng)用這個(gè)定理的結(jié)論，利用回溯算法可對一幅給定的地圖染色。作為地圖四色的示例如圖 3_3所示，圖中01、02、03、04、05、06、07為行政區(qū)編號，1色、2色、3色、4色為各區(qū)域的顏色，稱為色數(shù)?！舅惴ㄋ枷搿繌木幪枮?1的區(qū)域開始逐一進(jìn)行染色，對每個(gè)區(qū)域用色數(shù)1，2

14、，3，4依次進(jìn)行試探，并盡可能取小色數(shù)。若當(dāng)前所取色數(shù)與周圍已染色的區(qū)域不重色，則把該區(qū)的色數(shù)入棧，否則依次使用下一色數(shù)進(jìn)行試探。若從1色至4色均與相鄰的某區(qū)域發(fā)生重色，則需退棧回溯，修改棧頂區(qū)域的色數(shù)。在實(shí)現(xiàn)此算法時(shí)，可用一個(gè)關(guān)系矩陣R ( 1: n , 1: n )來描述各區(qū)域之間的邊界關(guān)系。若j123456710111110210000103100110041010110510110106110110070000000Ri第i區(qū)與第j區(qū)相鄰（有共同邊界），則R i , j 的值為1，否則為0。圖 3_3中所示的地圖關(guān)系矩陣如圖 3_4所示。為了記下每個(gè)區(qū)域當(dāng)前染色結(jié)果而設(shè)立一個(gè)棧S( 1

15、 : n )，棧的下標(biāo)值表示區(qū)域號，棧中的內(nèi)容是色數(shù)，如S 6 = 3表示06區(qū)域當(dāng)前染色的色數(shù)是3?！緟⒖汲绦蚨巍縞onst n=7; 地圖中區(qū)域數(shù)type adjar=array1.n,1.n of 0.1; ads=array1.n of 1.4;procedure mapcolor (var r:adjr; var s:ads);圖3_4 begin s 1:=1; 01區(qū)染1色 i:=2; j:=1; i 為區(qū)域號，j為染色號 while in do begin while ( j =4 ) and ( in ) do begin k:=1; k 指示已染色區(qū)域號 while ( k

16、i ) and ( s k *R i , k j ) do begin k:=k+1; 判斷相鄰區(qū)是否已染色 if k 4 then begin i:= i-1; j:=s i +1; end; 變更棧頂區(qū)域的染色色數(shù)end; end;end;按圖3_3所示地圖執(zhí)行上述算法時(shí)，棧的變化情況如圖3_5所示。7163354344443422223223333322222222S11111111圖3_5從關(guān)系矩陣R可以看出，當(dāng)i = 6時(shí)，無論色數(shù)j1 , 2 , 3 , 4都產(chǎn)生與相鄰區(qū)重色問題 （因與i = 6相鄰的區(qū)是1，2，4，5區(qū)，從棧S可見這四個(gè)區(qū)色數(shù)分別1，2，3，4，四種色全部用完。

17、6區(qū)再用四種色數(shù)之一，必然重色）。因此必須變更棧頂色數(shù)，而5區(qū)當(dāng)前色數(shù)為“4”，也不存在除4以外的可染色色數(shù)，則需繼續(xù)退棧，變更S 4 :=4，由此S 5 :=3，然而此時(shí)仍然6區(qū)與相鄰區(qū)重色，再次退棧，將S 3 改為S 3 :=3時(shí)才求得所有地區(qū)的染色解。3.4 棧與遞歸3.4.1 遞歸形式一般有兩種直接遞歸和間接遞歸，而棧是實(shí)現(xiàn)遞歸的重要手段。(一)、直接遞歸子程序自己調(diào)用自己1 n=0nfac (n-1) n1【例2】 fac (n) = n! = 按上述遞歸定義形式寫出fac(n) 函數(shù)如下：function fac(n:integer):integer;beginif n=0 the

18、n fac:=1else fac:=n*fac(n-1);end;它的執(zhí)行流程如下：fac (3)fac (3)fac (2)fac (1)fac (0)3fac (2)2fac (1)1fac (0)fac (0) = 16一般來說，遞歸子程序在調(diào)用本身前應(yīng)有條件語句控制何時(shí)進(jìn)行遞歸，何時(shí)遞歸結(jié)束。這個(gè)條件語句就是遞歸邊界。例如，fac函數(shù)體中的“ if n=0 then fac:=1 ”。(二)、間接遞歸子程序A調(diào)用子程序B，子程序B又調(diào)用子程序A子程序A和B組合起來有兩種結(jié)構(gòu)形式：1B是A的局部對象例： procedure A;procedure B;beginA的子過程B的過程說明 A

19、; 在B中調(diào)用A endbegin B; 在A中調(diào)用B end;2A和B是兩個(gè)地位相同的子程序例： procedure B (形式參數(shù)表): forward; B的完整說明在后procedurde A;begin B (實(shí)參表); 在A中調(diào)用Bend;procedure B; B的首部縮寫，形式參數(shù)表不再列出beginA; 在B中調(diào)用Aend;【例題3】求出一個(gè)在88的棋盤上，放置8個(gè)不能互相捕捉的“皇后”的所有布局。顯然，一個(gè)使“皇后”間不能互相捕捉的合理布局應(yīng)該是每列、每行確定有一個(gè)“皇后”，且在每條對角線上最多只有一個(gè)“皇后”。【數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)】從88的棋盤，我們很容易想到用二維數(shù)組來存儲

20、布局。但是，進(jìn)一步分析，每行有且僅有一個(gè)“皇后”，我們可以僅用一維數(shù)組來存儲布局。S 1 2 3 4 5 6 7 8S i 表示第i行“皇后”所處的列。這一數(shù)據(jù)結(jié)構(gòu)的改進(jìn)，將大大簡化編程?！舅惴ㄋ悸贰?、 從空配置開始，在第1行至第top行為合理配置的基礎(chǔ)上，遞歸調(diào)用自己而完成top+1行上的配置，直至第8行配置也是合理時(shí)，就找到一個(gè)解。因此，top=9是遞歸邊界。2、 在任一行上可能的配置有8種。開始時(shí)配置在第1列，以后改變時(shí)，順次選擇第2列，第3列，直至第8列，當(dāng)8列配置全不合理或者選中某一列配置時(shí)，則退出遞歸過程，通過恢復(fù)步數(shù)的形式回溯，直到所有布局為止。3、 要在 ( i , top)

21、 配置“皇后”（S top := i）的條件有兩個(gè)： 第1至top-1行的第i 列不能有“皇后”，即Sji，1jtop-1； 經(jīng) ( i , top) 的兩條對角線上不能有“皇后”，即： | S j -i | | j -top |，1jtop-1；【參考程序】program queen; var total : integer; 布局?jǐn)?shù) s : array1.8 of 1.8; 布局 procedure search(top:integer); var i,j : integer; p : boolean; p=true表示找到某列的配置 begin if top8 then begin 配置成功，打印布局 total:=total+1; writeln(total, step: ); for i:=1 to 8 do write(si, ); writeln; end else begin for i:=1 to 8 do begin 由第1行開始，順序選擇 p:=true; if top1 then begin j:=1; 確定可否在(i,top)位