1、棧滿isFull一東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院本章主要內(nèi)容本章主要內(nèi)容n棧棧n棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n棧與遞歸棧與遞歸n隊(duì)列隊(duì)列n隊(duì)列的應(yīng)用：電路布線隊(duì)列的應(yīng)用：電路布線2棧棧n定義：只允許在表的末端進(jìn)行插入和刪除的線性定義：只允許在表的末端進(jìn)行插入和刪除的線性表表n特點(diǎn)：先進(jìn)后出特點(diǎn)：先進(jìn)后出n棧的操作棧的操作n進(jìn)棧進(jìn)棧 push三三n出棧出棧 pop三三n棧頂棧頂 top三三n置空置空 setEmpty三三n判斷是否為空判斷是否為空 isEmpty三三n棧滿棧滿 isFull三三3棧棧n棧的數(shù)組表示棧的數(shù)組表示n棧的操作棧的操作n進(jìn)棧進(jìn)棧 push三三n出棧出棧 pop三

2、三n棧頂棧頂 top三三n置空置空 makeEmpty三三n判斷是否為空判斷是否為空 isEmpty三三n棧滿棧滿 isFull三三4topabtopctop空棧空棧top棧棧n棧的單鏈表表示棧的單鏈表表示r棧的數(shù)組表示可能棧滿棧的數(shù)組表示可能棧滿r棧的單鏈表表示無棧滿問題棧的單鏈表表示無棧滿問題r入棧在表頭進(jìn)行插入操作入棧在表頭進(jìn)行插入操作r出棧在表頭進(jìn)行刪除操作出棧在表頭進(jìn)行刪除操作5topcbanull棧棧n進(jìn)棧順序?yàn)檫M(jìn)棧順序?yàn)?1,2,3)，出棧順序能否為，出棧順序能否為(3,1,2)?r不能，不能，3出棧時(shí)，說明出棧時(shí)，說明2和和1都在棧里，而且都在棧里，而且2必須先于必須先于1出棧

3、出棧6321top作業(yè)：作業(yè)：1，2，3，4，5，6依次進(jìn)棧，若出棧順序?yàn)橐来芜M(jìn)棧，若出棧順序?yàn)?，3，4，6，5，1則棧大小至少為多少？則棧大小至少為多少？棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n一個(gè)表達(dá)式由操作數(shù)一個(gè)表達(dá)式由操作數(shù)(亦稱運(yùn)算對(duì)象亦稱運(yùn)算對(duì)象)、操作符、操作符 (亦亦稱運(yùn)算符稱運(yùn)算符) 和分界符組成。和分界符組成。n算術(shù)表達(dá)式三種表示算術(shù)表達(dá)式三種表示r中綴中綴(infix)表示表示 ，如，如 A+B；r前綴前綴(prefix)表示表示 ，如，如 +AB；r后綴后綴(postfix)表示表示 ，如，如 AB+；7棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n中綴表達(dá)式：中綴表達(dá)

4、式：A + B * ( C - D ) - E / Fn后綴表達(dá)式：后綴表達(dá)式：A B C D - * + E F / -n表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋罕磉_(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簉優(yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)高的先計(jì)算；r優(yōu)先級(jí)相同的自左向右計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；r當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開始計(jì)算。當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開始計(jì)算。n前綴和中綴表達(dá)式求值需要兩個(gè)棧；后綴表達(dá)式求值前綴和中綴表達(dá)式求值需要兩個(gè)棧；后綴表達(dá)式求值只需一個(gè)棧，相對(duì)簡單些。只需一個(gè)棧，相對(duì)簡單些。8棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n從左向右掃描表達(dá)式，用一個(gè)棧暫存掃描到的操作數(shù)從左向右掃

5、描表達(dá)式，用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。或計(jì)算結(jié)果。n后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn)，括號(hào)在后綴表達(dá)式中不出現(xiàn)9R1R2 2R3R4R5A B C D - * + E F / -R1R2 2R3R4R5A+B*(C-D)-E/F中綴表達(dá)式：中綴表達(dá)式：后綴表達(dá)式：后綴表達(dá)式：10作業(yè)：作業(yè)：寫出下列中綴表達(dá)式的后綴表達(dá)式寫出下列中綴表達(dá)式的后綴表達(dá)式A*B*C-A+B-C+DA*(-B)+C(A+B)*D+E/(F+A*D)+CA&B|!(EF)1.!(A & !(BD) | (CE

6、)棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n后綴表達(dá)式求值過程后綴表達(dá)式求值過程r順序掃描后綴表達(dá)式每一項(xiàng)順序掃描后綴表達(dá)式每一項(xiàng)r若該項(xiàng)是操作數(shù)，則進(jìn)棧若該項(xiàng)是操作數(shù)，則進(jìn)棧r若該項(xiàng)是操作符若該項(xiàng)是操作符，若是單目運(yùn)算符，則出棧一個(gè)操作數(shù)若是單目運(yùn)算符，則出棧一個(gè)操作數(shù)X，并將計(jì)算結(jié)果，并將計(jì)算結(jié)果X進(jìn)棧進(jìn)棧若是雙目運(yùn)算符，則連續(xù)出棧兩個(gè)操作數(shù)若是雙目運(yùn)算符，則連續(xù)出棧兩個(gè)操作數(shù)X和和Y，并將計(jì)算，并將計(jì)算結(jié)果結(jié)果X Y進(jìn)棧進(jìn)棧r當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。最后的計(jì)算結(jié)果。11棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表

7、達(dá)式求值12步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作符操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=A+R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)

8、算退棧，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5top空?？諚opBACDtoptoptopA B C D - * + E F / -后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值13步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作符操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=A+

9、R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)算退棧，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5BACDtoptoptopR1=C-DA B C D - * + E F / -后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值14步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作符

10、操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=A+R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)算退棧，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5BAtopR1=C-DtoptopA B C D - * + E F / -R2=B*R1后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求

11、值15步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作符操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=A+R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)算退棧

12、，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5AtoptopA B C D - * + E F / -R2=B*R1R3=A+R2空棧空棧top后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值16步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作符操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=

13、A+R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)算退棧，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5toptopA B C D - * + E F / -R3=A+R2EFtop后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值17步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作

14、符操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=A+R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)算退棧，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5A B C D - * + E F / -R3=A+R2EFtopR4=E/Ftoptop后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式

15、求值18步步輸入輸入類型類型動(dòng)作動(dòng)作棧中內(nèi)容棧中內(nèi)容1置空棧置空棧2A操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A3B操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B4C操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C5D操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧A B C D6-操作符操作符D、C退棧，計(jì)算退棧，計(jì)算R1=C-D進(jìn)棧進(jìn)棧A B R17*操作符操作符R1、B退棧，計(jì)算退棧，計(jì)算R2=B*R1進(jìn)棧進(jìn)棧A R28+操作符操作符R2、A退棧，計(jì)算退棧，計(jì)算R3=A+R2進(jìn)棧進(jìn)棧R39E操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E10F操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧R3 E F11/操作符操作符F、E退棧，計(jì)算退棧，計(jì)算R4=E / F進(jìn)棧進(jìn)棧R3 R412-操作符操作符R4、R3退棧，計(jì)算退

16、棧，計(jì)算R5=R3-R4進(jìn)棧進(jìn)棧R5A B C D - * + E F / -R3=A+R2R4=E/FtoptopR5=R3-R4空?？諚op后綴表達(dá)式求值過程：后綴表達(dá)式求值過程：棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式r使用棧將中綴表達(dá)式轉(zhuǎn)換成前綴或后綴表達(dá)式。使用棧將中綴表達(dá)式轉(zhuǎn)換成前綴或后綴表達(dá)式。r為了實(shí)現(xiàn)轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級(jí)。為了實(shí)現(xiàn)轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級(jí)。結(jié)束符結(jié)束符“#”優(yōu)先級(jí)最低優(yōu)先級(jí)最低左括號(hào)左括號(hào)“(”棧外優(yōu)先級(jí)最高，進(jìn)棧后極低棧外優(yōu)先級(jí)最高，進(jìn)棧后極低右括號(hào)右括號(hào)“)”棧外優(yōu)先級(jí)極低棧外優(yōu)先級(jí)極

17、低其他進(jìn)棧后優(yōu)先級(jí)加其他進(jìn)棧后優(yōu)先級(jí)加1，這可滿足自左向右計(jì)算要求，這可滿足自左向右計(jì)算要求19各個(gè)算術(shù)操作符的優(yōu)先級(jí)各個(gè)算術(shù)操作符的優(yōu)先級(jí)操作符操作符#(* / %+ - )isp(棧內(nèi)優(yōu)先級(jí)棧內(nèi)優(yōu)先級(jí))01536icp(棧外優(yōu)先級(jí)棧外優(yōu)先級(jí))06421棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值n中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式算法中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式算法r操作符棧初始化，結(jié)束符操作符棧初始化，結(jié)束符#進(jìn)棧，讀入中綴表達(dá)式的首字進(jìn)棧，讀入中綴表達(dá)式的首字符符chr重復(fù)執(zhí)行以下步驟，直到重復(fù)執(zhí)行以下步驟，直到ch=#，同時(shí)棧頂操作符也是，同時(shí)棧頂操作符也是#，停止循環(huán)停止循環(huán)若若ch是操作數(shù)直接

18、輸出，讀入下一字符是操作數(shù)直接輸出，讀入下一字符ch若若ch是操作符，比較是操作符，比較ch和棧頂操作符和棧頂操作符op優(yōu)先級(jí)：優(yōu)先級(jí)：若icp(ch) isp(op)，令ch進(jìn)棧，讀入下一字符ch若icp(ch) isp(op)，退棧，并輸出若icp(ch)=isp(op)，退棧不輸出；若退出的是(，則讀入下一個(gè)字符chr算法結(jié)束，輸出序列即為所得后綴表達(dá)式算法結(jié)束，輸出序列即為所得后綴表達(dá)式20棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值 21步步輸入輸入類型類型動(dòng)作動(dòng)作棧內(nèi)容棧內(nèi)容后綴輸出后綴輸出0#進(jìn)棧進(jìn)棧#1A操作數(shù)操作數(shù)# A 2+操作符操作符isp(#) icp(+), 進(jìn)棧進(jìn)棧#

19、+A3B操作數(shù)操作數(shù)# + AB4*操作符操作符isp(+) icp(*), 進(jìn)棧進(jìn)棧# + *AB5(操作符操作符isp(*) icp( ( ), 進(jìn)棧進(jìn)棧# + * (AB6C操作數(shù)操作數(shù)# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退棧退棧# + * (ABCDisp( ) = icp( ), 退棧退棧# + *ABCD-中綴表示轉(zhuǎn)換為后綴表示過程：中綴表示轉(zhuǎn)換為后綴表示過程：ABCD-*+EF/-)(AC后綴輸出：后綴輸出：#+toptop空棧空棧top*（-toptoptopB棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值 22步步輸入輸入類型類型動(dòng)作動(dòng)作棧內(nèi)容

20、棧內(nèi)容后綴輸出后綴輸出0#進(jìn)棧進(jìn)棧#1A操作數(shù)操作數(shù)# A 2+操作符操作符isp(#) icp(+), 進(jìn)棧進(jìn)棧# +A3B操作數(shù)操作數(shù)# + AB4*操作符操作符isp(+) icp(*), 進(jìn)棧進(jìn)棧# + *AB5(操作符操作符isp(*) icp( ( ), 進(jìn)棧進(jìn)棧# + * (AB6C操作數(shù)操作數(shù)# + * (ABC7-操作符操作符isp( ( ) icp( ) ), 退棧退棧# + * (ABCDisp( ( ) = icp( ) ), 退棧退棧# + *ABCD-中綴表示轉(zhuǎn)換為后綴表示過程：中綴表示轉(zhuǎn)換為后綴表示過程：ABCD-*+EF/-)(AB CD-后綴輸出：后綴輸出：#

21、+*（-toptoptop棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值 23步步輸入輸入類型類型動(dòng)作動(dòng)作棧內(nèi)容棧內(nèi)容后綴輸出后綴輸出10-操作符操作符isp(*) icp(-), 退棧退棧# + ABCD-*isp(+) icp(-), 退棧退棧#ABCD-*+isp(#) icp(-), 進(jìn)棧進(jìn)棧# -ABCD-*+11E操作數(shù)操作數(shù)# -ABCD-*+E12/操作符操作符isp(-) icp(/), 進(jìn)棧進(jìn)棧# - /ABCD-*+E13F操作數(shù)操作數(shù)# - /ABCD-*+EF14#操作符操作符isp(/) icp(#), 退棧退棧# -ABCD-*+EF/isp(-) icp(-), 退棧

22、退棧# + ABCD-*isp(+) icp(-), 退棧退棧#ABCD-*+isp(#) icp(-), 進(jìn)棧進(jìn)棧# -ABCD-*+11E操作數(shù)操作數(shù)# -ABCD-*+E12/操作符操作符isp(-) icp(/), 進(jìn)棧進(jìn)棧# - /ABCD-*+E13F操作數(shù)操作數(shù)# - /ABCD-*+EF14#操作符操作符isp(/) icp(#), 退棧退棧# -ABCD-*+EF/isp(-) data = x) return f; else Search(f-link, x); 29a1firsta2a3annullstruct LinkNode Type data; LinkNode *

23、link;棧與遞歸棧與遞歸n問題解法是遞歸的問題解法是遞歸的r例如，漢諾塔例如，漢諾塔 (Tower of Hanoi) 問題的解法問題的解法有有3根標(biāo)號(hào)為根標(biāo)號(hào)為A、B、C的柱子，的柱子，A柱上又疊著柱上又疊著64個(gè)從小到大排個(gè)從小到大排放的盤子。目的是要將放的盤子。目的是要將A柱的盤子全部移到柱的盤子全部移到C柱上。移動(dòng)條柱上。移動(dòng)條件是一次只能移動(dòng)一個(gè)盤子，移動(dòng)過程中大盤子不能放在小盤件是一次只能移動(dòng)一個(gè)盤子，移動(dòng)過程中大盤子不能放在小盤子上面子上面r求解漢諾塔問題的遞歸算法求解漢諾塔問題的遞歸算法若若 n = 1，將盤子直接從，將盤子直接從 A 柱移到柱移到 C 柱。柱。否則，執(zhí)行以下

24、三步：否則，執(zhí)行以下三步：用 C 柱做過渡，將 A 柱上的(n-1) 個(gè)盤子移到 B 柱上；將 A 柱上最后一個(gè)盤子直接移到 C 柱上；用 A 柱做過渡，將 B 柱上的(n-1) 個(gè)盤子移到 C 柱上。30棧與遞歸棧與遞歸n問題解法是遞歸的問題解法是遞歸的r例如，漢諾塔例如，漢諾塔 (Tower of Hanoi) 問題的解法問題的解法31void Hanoi ( int n, char A, char B, char C ) if (n = 1) printf( move %s, A, to %s , C ); else Hanoi ( n-1, A, C, B ); printf ( mo

25、ve %s, A, to %s , C ); Hanoi ( n-1, B, A, C ); 3個(gè)圓盤的漢諾塔的移動(dòng)個(gè)圓盤的漢諾塔的移動(dòng)棧與遞歸棧與遞歸n問題解法是遞歸的問題解法是遞歸的r例如，漢諾塔例如，漢諾塔 (Tower of Hanoi) 問題的解法問題的解法324個(gè)圓盤的漢諾塔的移動(dòng)個(gè)圓盤的漢諾塔的移動(dòng)棧與遞歸棧與遞歸n用棧將遞歸轉(zhuǎn)換為非遞歸用棧將遞歸轉(zhuǎn)換為非遞歸r漢諾塔漢諾塔 (Tower of Hanoi) 問題的解法問題的解法33void Hanoi ( int n, char a, char b, char c) Stack S; initStack(S); Node q;

26、q.n = n; q.A = a; q.B = b; q.C = c; Push (S, q); while ( ! StackEmpty(S) ) Pop(S, q); n = q. n; a = q.A; b = q.B; c = q.C; if ( n = 1 ) printf (“Move %c”, a, “ to %c”, c); else q.n = n-1; q.A = b; q.B = a; q.C = c; Push (S, q); q.n = 1; q.A = a; q.B = b; q.C = c; Push (S, q); q.n = n-1; q.A = a; q.B

27、 = c; q.C = b; Push (S, q); Struct Node int n; char A,B,C;(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-C棧與遞歸棧與遞歸n用棧將遞歸轉(zhuǎn)換為非遞歸用棧將遞歸轉(zhuǎn)換為非遞歸r漢諾塔漢諾塔 (Tower of Hanoi) 問題的解法問題的解法34(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A

28、,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(3,A,B,C)空?？諚op棧與遞歸棧與遞歸n用棧將遞歸轉(zhuǎn)換為非遞歸用棧將遞歸轉(zhuǎn)換為非遞歸r漢諾塔漢諾塔 (Tower of Hanoi) 問題的解法問題的解法35(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(1,A,B,C)(2,B,A,C)(2,A,C,B)toptop棧與遞歸棧與遞歸n用棧將遞歸轉(zhuǎn)換為非

29、遞歸用棧將遞歸轉(zhuǎn)換為非遞歸r漢諾塔漢諾塔 (Tower of Hanoi) 問題的解法問題的解法36(3,A,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-Ctop(1,A,B,C)(2,B,A,C)(1,C,A,B)toptop(1,A,C,B)(1,A,B,C)toptop空?？諚op棧與遞歸棧與遞歸n用棧將遞歸轉(zhuǎn)換為非遞歸用棧將遞歸轉(zhuǎn)換為非遞歸r漢諾塔漢諾塔 (Tower of Hanoi) 問題的解法問題的解法37(3,A

30、,B,C)A-C(2,A,C,B)(1,A,B,C)(2,B,A,C)(1,A,B,C)(1,A,C,B)(1,C,A,B)(1,B,C,A)(1,B,A,C)(1,A,B,C)A-CA-BC-BB-AB-CA-C(1,A,B,C)(1,B,A,C)toptop(1,B,C,A)top空?？諚op尋找凸包尋找凸包n給定平面上給定平面上n個(gè)點(diǎn)的集合個(gè)點(diǎn)的集合Q，求，求Q的凸包的凸包38Q的的convex hull是一個(gè)凸多邊形是一個(gè)凸多邊形P，Q的點(diǎn)或者在的點(diǎn)或者在P上或者在上或者在P內(nèi)內(nèi)凸多邊形凸多邊形P是具有如下性質(zhì)多邊形：是具有如下性質(zhì)多邊形：連接連接P內(nèi)任意兩點(diǎn)的邊都在內(nèi)任意兩點(diǎn)的邊都

31、在P內(nèi)內(nèi)尋找凸包尋找凸包nGraham-scan的基本思想的基本思想r找到最下最左頂點(diǎn)，其他頂點(diǎn)與它連線找到最下最左頂點(diǎn)，其他頂點(diǎn)與它連線r按夾角從小到大排序按夾角從小到大排序r夾角最小的開始，尋找凸包點(diǎn)夾角最小的開始，尋找凸包點(diǎn)39尋找凸包尋找凸包nGraham-scan的基本思想的基本思想尋找凸包尋找凸包nGraham-scan的基本思想的基本思想尋找凸包尋找凸包nGraham-scan的基本思想的基本思想尋找凸包尋找凸包nGraham-scan的基本思想的基本思想尋找凸包尋找凸包nGraham-scan的基本思想的基本思想尋找凸包尋找凸包nGraham-scan的基本思想的基本思想尋找凸

32、包尋找凸包nGraham-scan的基本思想的基本思想尋找凸包尋找凸包nGraham-scan的基本思想的基本思想47Graham-scan(Q)1. 求求Q中中y-坐標(biāo)值最小的點(diǎn)坐標(biāo)值最小的點(diǎn)p0；2. 按照與按照與p0極角極角(逆時(shí)針方向逆時(shí)針方向)大小排序大小排序Q中其余點(diǎn)，中其余點(diǎn)， 結(jié)果為結(jié)果為；3. Push(p0, S); Push(p1, S); Push(p2, S);4. FOR i=3 TO m DO5. While Next-to-top(S)、Top(S)和和pi形成非左移動(dòng)形成非左移動(dòng) Do6. Pop(S);7. Push(pi, S);8. Rerurn S；O(nlogn)O(n)O(1)O(n)總時(shí)間復(fù)雜度總時(shí)間復(fù)雜度O(nlogn)循環(huán)為什么是循環(huán)為什么是O(n)最多最多n次入棧，次入棧，那么出棧也是最多那么出棧也是最多n次次隊(duì)列隊(duì)列n定義定義n隊(duì)列是只允許