1、第一章 棧 棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來(lái)的壓在底下，隨后一件一件往上堆。取走時(shí)，只能從上面一件一件取。堆和取都在頂部進(jìn)行，底部一般是不動(dòng)的。棧就是一種類(lèi)似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行刪除和插入的一端稱(chēng)棧頂，另一堆稱(chēng)棧底。插入一般稱(chēng)為進(jìn)棧（PUSH），刪除則稱(chēng)為退棧（POP）。 棧也稱(chēng)為后進(jìn)先出表（LIFO表）。 一個(gè)?？梢杂枚ㄩL(zhǎng)為的數(shù)組來(lái)表示，用一個(gè)棧指針TOP指向棧頂。若TOP0，表示?？眨琓OP=N時(shí)棧滿。進(jìn)棧時(shí)TOP加。退棧時(shí)TOP減。當(dāng)TOP0時(shí)為下溢。棧指針在運(yùn)算中永遠(yuǎn)指向棧頂。1、進(jìn)棧（PUSH）算法若TOP時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先

2、檢查棧是否已滿，滿則溢出；不滿則作）；TOP+（棧指針加，指向進(jìn)棧地址）；STOP=X，結(jié)束（X為新進(jìn)棧的元素）；2、退棧（POP）算法若TOP0，則給出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作)；X=STOP，（退棧后的元素賦給X）；TOP-，結(jié)束（棧指針減，指向棧頂）。進(jìn)棧、出棧的c+實(shí)現(xiàn)過(guò)程程序：#define n 100void push(int s,int *top,int *x) /入棧 if (*top=n) printf(overflow); else (*top)+; s*top=*x; void pop(int s,int *y,int *top

3、) /出棧 if (*top=0) printf(underflow); else *y=s*top; (*top)-; 對(duì)于出棧運(yùn)算中的“下溢”，程序中僅給出了一個(gè)標(biāo)志信息，而在實(shí)際應(yīng)用中，下溢可用來(lái)作為控制程序轉(zhuǎn)移的判斷標(biāo)志，是十分有用的。對(duì)于入棧運(yùn)算中的“上溢”，則是一種致命的錯(cuò)誤，將使程序無(wú)法繼續(xù)運(yùn)行，所以要設(shè)法避免。 堆棧的數(shù)組模擬 十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是實(shí)現(xiàn)計(jì)算的基本問(wèn)題，解決方法很多，下面給出一種算法原理：N=(N / d)dN % d （其中 / 為整除運(yùn)算，%為求余運(yùn)算）。 例如：(1348)10(2504)8運(yùn)算過(guò)程如下：NN / 8N % 89413NN / 8

4、N % 81348168416821021252021、填空：(9413)10=( )8=( )16=( )22、數(shù)制轉(zhuǎn)化程序#include#includeusing namespace std;#define size 100int asize+1,n,d,i=0,j;main() coutn; coutd; do a+i=n%d; n=n/d; while(n!=0); for (j=i;j=1;j-)coutaj; return 0;3、火車(chē)站列車(chē)調(diào)度示意圖如下，假設(shè)調(diào)度站兩側(cè)的軌道為單向行駛軌道。 如果進(jìn)站的車(chē)廂序列為123，則可能的出站車(chē)廂序列是什么？ 如果進(jìn)站的車(chē)廂序列為1234

5、56，問(wèn)能否得到135426和435612的出站序列?！纠?】括號(hào)的匹配（表達(dá)式的合法性檢查）【問(wèn)題描述】 假設(shè)一個(gè)表達(dá)式有英文字母（小寫(xiě)）、運(yùn)算符（+，*，/）和左右小（圓）括號(hào)構(gòu)成，以“”作為表達(dá)式的結(jié)束符。請(qǐng)編寫(xiě)一個(gè)程序檢查表達(dá)式中的左右圓括號(hào)是否匹配，若匹配，則返回“YES”；否則返回“NO”。假設(shè)表達(dá)式長(zhǎng)度小于255，左圓括號(hào)少于20個(gè)?！舅惴ǚ治觥?假設(shè)輸入的字符串存儲(chǔ)在c中（char c256 ）。 我們可以定義一個(gè)棧：char smaxn+1; int top; 用它來(lái)存放表達(dá)式中從左往右的左圓括號(hào)（maxn=20）。 算法的思路為：順序（從左往右）掃描表達(dá)式的每個(gè)字符ci，若

6、是“（”，則讓它進(jìn)棧；若遇到的是“）”，則讓棧頂元素出棧；當(dāng)棧發(fā)生下溢或當(dāng)表達(dá)式處理完畢而棧非空時(shí)，都表示不匹配，返回“NO”；否則表示匹配，返回“YES”。 #include#includeusing namespace std;#define maxn 20char c256;bool judge(char c256) int top=0,i=0; while (ci!=) if (ci=() top+; if (ci=) if (top0) top-; else return 0; i+; if (top!=0) return 0; /檢測(cè)棧是否為空。不空則說(shuō)明有未匹配的括號(hào) else

7、return 1;main() scanf(%s,c); if (judge(c)printf(YES); else printf(NO); return 0;【例2】編程求一個(gè)后綴表達(dá)式的值【問(wèn)題描述】 從鍵盤(pán)讀入一個(gè)后綴表達(dá)式（字符串），只含有0-9組成的運(yùn)算數(shù)及加（+）、減（）、乘（*）、除（/）四種運(yùn)算符。每個(gè)運(yùn)算數(shù)之間用一個(gè)空格隔開(kāi)，不需要判斷給你的表達(dá)式是否合法。以作為結(jié)束標(biāo)志。【算法分析】 后綴表達(dá)式的處理過(guò)程很簡(jiǎn)單，過(guò)程如下：掃描后綴表達(dá)式，凡遇操作數(shù)則將之壓進(jìn)堆棧，遇運(yùn)算符則從堆棧中彈出兩個(gè)操作數(shù)進(jìn)行該運(yùn)算，將運(yùn)算結(jié)果壓棧，然后繼續(xù)掃描，直到后綴表達(dá)式被掃描完畢為止，此時(shí)棧底

8、元素即為該后綴表達(dá)式的值。 比如，169*(4+3)轉(zhuǎn)換成后綴表達(dá)式為： 16943+*，在字符數(shù)組A中的形式為：棧中的變化情況：運(yùn)行結(jié)果：-47#include#include#include#includeusing namespace std;int stack101;char s256;int comp(char s256) int i=0,top=0,x,y; while (i=strlen(s)-2) switch (si) case +:stack-top+=stacktop+1; break; case -:stack-top-=stacktop+1; break; case

9、*:stack-top*=stacktop+1; break; case /:stack-top/=stacktop+1; break; default:x=0; while (si!= ) x=x*10+si+-0; stack+top=x; break; i+; /while return stacktop;main() printf(input a string(_over):); gets(s); printf(result=%d p(s); return 0; 棧的用途極為廣泛，在源程序編譯中表達(dá)式的計(jì)算、過(guò)程的嵌套調(diào)用和遞歸調(diào)用等都要用到棧，下面以表達(dá)式計(jì)算為例子加以說(shuō)明。源程序編

10、譯中，若要把一個(gè)含有表達(dá)式的賦值語(yǔ)句翻譯成正確求值的機(jī)器語(yǔ)言，首先應(yīng)正確地解釋表達(dá)式。例如，對(duì)賦值語(yǔ)句X4823; (式 11.1) 其正確的計(jì)算結(jié)果應(yīng)該是，但若在編譯程序中簡(jiǎn)單地按自左向右掃描的原則進(jìn)行計(jì)算，則為：X122324321 這結(jié)果顯然是錯(cuò)誤的。因此，為了使編譯程序能夠正確地求值，必須事先規(guī)定求值的順序和規(guī)則。通常采用運(yùn)算符優(yōu)先數(shù)法。一般表達(dá)式中會(huì)遇到操作數(shù)、運(yùn)算符和語(yǔ)句結(jié)束符等，以算術(shù)運(yùn)算符為例，對(duì)每種運(yùn)算賦予一個(gè)優(yōu)先數(shù)，如： 運(yùn)算符： 優(yōu)先數(shù)： （語(yǔ)句結(jié)束符“；”的優(yōu)先數(shù)為零） 在運(yùn)算過(guò)程中，優(yōu)先數(shù)高的運(yùn)算符應(yīng)先進(jìn)行運(yùn)算（但遇到括號(hào)時(shí)，應(yīng)另作處理）。按這樣的規(guī)定，對(duì)式（11.1

11、）自左向右進(jìn)行運(yùn)算時(shí)，其計(jì)算順序就被唯一地確定下來(lái)了。計(jì)算順序確定后，在對(duì)表達(dá)式進(jìn)行編譯時(shí)，一般設(shè)立兩個(gè)棧，一個(gè)稱(chēng)為運(yùn)算符棧（OPS），另一個(gè)稱(chēng)為操作數(shù)棧（OVS），以便分別存放表達(dá)式中的運(yùn)算符和操作數(shù)。編譯程序自左向右掃描表達(dá)式直至語(yǔ)句結(jié)束，其處理原則是：凡遇到操作數(shù)，一律進(jìn)入操作數(shù)棧；當(dāng)遇到運(yùn)算符時(shí)，則將運(yùn)算符的優(yōu)先數(shù)與運(yùn)算符棧中的棧頂元素的優(yōu)先數(shù)相比較；若該運(yùn)算符的優(yōu)先數(shù)大，則進(jìn)棧；反之，則取出棧頂?shù)倪\(yùn)算符，并在操作數(shù)棧中連續(xù)取出兩個(gè)棧頂元素作為運(yùn)算對(duì)象進(jìn)行運(yùn)算，并將運(yùn)算結(jié)果存入操作數(shù)棧，然后繼續(xù)比較該運(yùn)算符與棧頂元素的優(yōu)先數(shù)。例如式（11.1）中，當(dāng)掃描到“”和“”時(shí)都要將運(yùn)算符入棧。

12、接著掃描到“”號(hào)， 其優(yōu)先數(shù)小于乘號(hào)所以乘號(hào)退棧，并執(zhí)行，將結(jié)果再存入操作數(shù)棧。再將“”號(hào)的優(yōu)先數(shù)與運(yùn)算符棧的棧頂元素“”號(hào)的優(yōu)先數(shù)相比較，兩者相等，所以再將加號(hào)退棧，進(jìn)行，結(jié)果為，再入棧，接著，由于運(yùn)算棧已空，所以減號(hào)入棧。當(dāng)掃描到“”時(shí)，操作數(shù)入棧。當(dāng)掃描到“；”時(shí)，其優(yōu)先數(shù)最低， 所以減號(hào)退棧并執(zhí)行20-3，結(jié)果為17并入棧。因已掃描到語(yǔ)句結(jié)束符，所以表達(dá)式的求值結(jié)束，結(jié)果為17?！纠?】模擬計(jì)算機(jī)處理算術(shù)表達(dá)式過(guò)程。從鍵盤(pán)上輸入算術(shù)表達(dá)式串（只含、運(yùn)算符，允許含括號(hào)），輸出算術(shù)表達(dá)式的值。設(shè)輸入的表達(dá)式串是合法的。【算法分析】建立兩個(gè)棧，一個(gè)是操作數(shù)棧（number），一個(gè)是運(yùn)算符棧（

13、symbol），根據(jù)運(yùn)算符的優(yōu)先級(jí)對(duì)兩個(gè)棧進(jìn)行相應(yīng)的操作。#include#include#include#includeusing namespace std;int number101,i=0, p=1;char symbol101,s256, t256; void push() /算符入棧運(yùn)算 symbol+p=si;void pop() /運(yùn)算符棧頂元素出棧,并取出操作數(shù)棧元素完成相應(yīng)的運(yùn)算 switch (symbolp-) case +:numberp+=numberp + 1;break; case -:numberp-=numberp + 1;break; case *:num

14、berp*=numberp + 1;break; case /:numberp/=numberp + 1;break; bool can() /判斷運(yùn)算符的優(yōu)先級(jí)別,建立標(biāo)志函數(shù) if (si=+|si=-)&symbolp!=() return 1; if (si=*|si=/)&(symbolp=*|symbolp=/)return 1; return 0;main() printf(String :);gets(s); sstrlen(s)=);symbolp=(; while (i=0&si=9) /取數(shù)入操作數(shù)棧 x=x*10+si+-0; numberp=x; do if (si=

15、) /右括號(hào)處理 while (symbolp!=() pop(); number-p=numberp + 1; else /根據(jù)標(biāo)志函數(shù)值作運(yùn)算符入?；虺鰲＿\(yùn)算處理 while (can() pop(); push(); i+; while (istrlen(s)&si-1=); printf(Result=%d, number0); return 0;1、表達(dá)式括號(hào)匹配(stack.cpp)【問(wèn)題描述】 假設(shè)一個(gè)表達(dá)式有英文字母（小寫(xiě)）、運(yùn)算符（+，*，/）和左右?。▓A）括號(hào)構(gòu)成，以“”作為表達(dá)式的結(jié)束符。請(qǐng)編寫(xiě)一個(gè)程序檢查表達(dá)式中的左右圓括號(hào)是否匹配，若匹配，則返回“YES”；否則返回“

16、NO”。表達(dá)式長(zhǎng)度小于255，左圓括號(hào)少于20個(gè)?！据斎胛募?輸入文件stack.in包括一行數(shù)據(jù)，即表達(dá)式，【輸出文件】 輸出文件stack.out包括一行，即“YES” 或“NO”?！緲永斎?】2*(x+y)/(1-x)【樣例輸出1】 YES【樣例輸入2】 (25+x)*(a*(a+b+b)【樣例輸出2】 NO【上機(jī)練習(xí)】2、括弧匹配檢驗(yàn)(check.cpp)【問(wèn)題描述】 假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（ ）或（ （ ）或 ( ( ) ) ）均為錯(cuò)誤的匹配?，F(xiàn)在的問(wèn)題是，要求檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？輸入

17、一個(gè)只包含圓括號(hào)和方括號(hào)的字符串，判斷字符串中的括號(hào)是否匹配，匹配就輸出 “OK” ，不匹配就輸出“Wrong”。輸入一個(gè)字符串：（），輸出：OK【輸入格式】 輸入僅一行字符（字符個(gè)數(shù)小于255）【輸出格式】 匹配就輸出 “OK” ，不匹配就輸出“Wrong”。 【輸入樣例】check.in（）【輸出樣例】check.outWrong3、字符串匹配問(wèn)題【問(wèn)題描述】 字符串中只含有括號(hào) (),判斷輸入的字符串中括號(hào)是否匹配。如果括號(hào)有互相包含的形式，從內(nèi)到外必須是,(),，例如。輸入: () 輸出:YES，而輸入()， ()都應(yīng)該輸出NO。【輸入格式】strs.in 文件的第一行為一個(gè)整數(shù)n，表

18、示以下有多少個(gè)由括好組成的字符串。接下來(lái)的n行，每行都是一個(gè)由括號(hào)組成的長(zhǎng)度不超過(guò)255的字符串?！据敵龈袷健縮trs.out 在輸出文件中有N行，每行都是YES或NO?！据斎霕永?()()()()()()()()()()()()【輸出標(biāo)例】YESYESYESYESNO4、計(jì)算(calc.cpp)【問(wèn)題描述】小明在你的幫助下，破密了Ferrari設(shè)的密碼門(mén)，正要往前走，突然又出現(xiàn)了一個(gè)密碼門(mén)，門(mén)上有一個(gè)算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“”求出的值就是密碼。小明數(shù)學(xué)學(xué)得不好，還需你幫他的忙。(“/”用整數(shù)除法)【輸入】輸入文件calc.in共1行，為一個(gè)算式。【輸出】輸出文件calc.out共1行，就是密碼。【輸入樣例】calc.in1+(3+2)*(72+6*9)/(2) 【輸出樣例】calc.out258 【限制】100%的數(shù)據(jù)滿足：算式長(zhǎng)度=30 其中所有數(shù)據(jù)在231-1的范圍內(nèi)。5、車(chē)廂調(diào)度(train.cpp)【問(wèn)題描述】 有一個(gè)火車(chē)站，鐵路如圖所示，每輛火車(chē)從A駛?cè)?，再?gòu)腂方向駛出，同時(shí)它的車(chē)廂可以重新組合。假設(shè)從A方向駛來(lái)的火車(chē)有n節(jié)（n=1000