1、ACM/ICPC程序設(shè)計(jì),基本數(shù)據(jù)結(jié)構(gòu) 及其在程序設(shè)計(jì)中的應(yīng)用,程序=數(shù)據(jù)結(jié)構(gòu)+算法,數(shù)據(jù)結(jié)構(gòu)(Data Structure)是數(shù)據(jù)的計(jì)算機(jī)表示和相應(yīng)的一組操作。 算法(Algorithm)就是解決問(wèn)題的方法或過(guò)程。,基本數(shù)據(jù)結(jié)構(gòu),線性結(jié)構(gòu) 非線性結(jié)構(gòu) 集合,樹(shù)結(jié)構(gòu) 圖結(jié)構(gòu),線性表 棧 隊(duì)列 串,線性結(jié)構(gòu),線性表: 由n個(gè)元素組成的有限序列。每個(gè)元素有確定的前驅(qū)和后繼。,元素之間的關(guān)系僅限于前趨、后繼關(guān)系 表、棧、隊(duì)列、串,元素的存儲(chǔ)方式 數(shù)組 鏈表,線性結(jié)構(gòu),由n個(gè)元素組成的有限序列。每個(gè)元素有確定的前驅(qū)和后繼。,表：不限制元素的插入和刪除位置。有n+1個(gè)位置可供插入，n個(gè)元素可供刪除 棧：

2、插入和刪除操作只允許在表尾進(jìn)行 隊(duì)列：在表尾插入、在表頭刪除 串：元素為字符的線性表，有求子串、子串定位、子串替換等操作,(a1，a2，ai，an),數(shù)組,用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素. 表中任一元素可以隨機(jī)存取. 插入或刪除一個(gè)元素需要移動(dòng)其他元素.,由下標(biāo)確定數(shù)組元素ai： Loc(ai)=Loc(a1)+(i-1)*d (1in),例如：由n個(gè)元素構(gòu)成的一維數(shù)組a,鏈表,鏈?zhǔn)酱鎯?chǔ):任意存儲(chǔ)單元存儲(chǔ)元素 鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域 插入或刪除一個(gè)元素,只需修改結(jié)點(diǎn)指針域 訪問(wèn)任一元素必須從鏈表頭指針開(kāi)始,鏈表結(jié)點(diǎn),鏈?zhǔn)酱鎯?chǔ):任意存儲(chǔ)單元存儲(chǔ)元素 鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域 插入或刪

3、除一個(gè)元素,只需修改結(jié)點(diǎn)指針域 訪問(wèn)任一元素必須從鏈表頭指針開(kāi)始,struct Node ElemType data； /數(shù)據(jù)元素 struct Node *next； /指向后繼結(jié)點(diǎn)的指針 ;,單向鏈表,線性表： (a1，a2，ai-1，ai，ai+1，an),(a) 單向鏈表,雙向鏈表和循環(huán)鏈表,線性表： (a1，a2，ai-1，ai，ai+1，an),單鏈表的插入和刪除,鏈?zhǔn)酱鎯?chǔ):任意存儲(chǔ)單元存儲(chǔ)元素 鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域 插入或刪除一個(gè)元素，只需修改結(jié)點(diǎn)指針域 訪問(wèn)任一元素必須從鏈表頭指針開(kāi)始,頭結(jié)點(diǎn),帶頭結(jié)點(diǎn)的單向鏈表,單鏈表中插入元素,將元素ai所在結(jié)點(diǎn)的地址賦給元素e結(jié)點(diǎn)的

4、指針域： S-next = P-next;,修改元素ai-1所在結(jié)點(diǎn)指針域的值： P-next = S;,單鏈表中刪除元素ai,修改元素ai-1所在結(jié)點(diǎn)指針域的值： P-next = P-next -next;,例1:Ugly Numbers,Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . shows the first 11 ugly numbers. By convention, 1 is included.

5、 Write a program to find and print the 1500th ugly number.,算法思路: 一個(gè)正整數(shù)m可表示如下： m = (p1)j1 * (p2)j2 * *(pn)jn Ugly number = 2j1 * 3j2 * 5j3 (j1,j2,j3=0) 在已知序列中,找一個(gè)最小的數(shù),使得它乘以2比已知序列最后一個(gè)元素大;找一個(gè)最小的數(shù),使得它乘以3比最后一個(gè)元素大;找一個(gè)最小的數(shù),使得它乘以5比最后一個(gè)元素大. 在這三個(gè)乘積中找最小的添加到表尾,反復(fù)按此規(guī)則構(gòu)造遞增序列,直到表中有1500個(gè)元素。 可以用數(shù)組預(yù)先分配1500個(gè)單元,也可以用鏈表動(dòng)

6、態(tài)分配.,例2：The Blocks Problem,編號(hào)為0n-1的n個(gè)木塊，放在編號(hào)為0n-1的n個(gè)格子里, 可對(duì)它們進(jìn)行四種有效的操作。,0,1,2,3,4,n-1,.,Initial Block World,move a onto b ：先將a和b上的其他木塊移回到它們的初始位置，然后將木塊a摞在木塊b上.,move a over b ：先將木塊a上的其他木塊移到它們的初始位置后，然后將木塊a摞到包含了木塊b的那一堆木塊上面,pile a onto b ：先將木塊b上的所有木塊移回到它們的初始位置，然后將木塊a及其上的木塊移到木塊b上.,pile a over b ：將包含木塊a的那一

7、摞木塊移到包含了木塊b的那一堆木塊上面.,move a onto b 先將a和b上的其他木塊移回到它們的初始位置，然后將木塊a摞在木塊b上.,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,Example: move 3 onto 6,3,move a over b 先將木塊a上的其他木塊移到它們的初始位置后，然后將木塊a摞到包含了木塊b的那一堆木塊上面.,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,Example: move 3 over 6,3,pile a onto b 先將木塊b上的所有木塊移回到它們的初始位置，然后將

8、木塊a及其上的木塊移到木塊b上.,Example: pile 3 onto 6,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,pile a over b 將包含木塊a的那一摞木塊移到包含了木塊b的那一堆木塊上面.,Example: pile 3 over 6,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over

9、9 quit,輸入數(shù)據(jù)樣本,0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:,input：,output：,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程：,Initial Block World,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,格子 編號(hào),10 move 9 onto 1 move 8 over

10、1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù))：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,

11、5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,

12、處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,Any command in which a = b or in which a and b are in the same stack of blocks i

13、s an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 o

14、nto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5

15、,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,處理過(guò)程(續(xù)) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,output：,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2

16、 over 1 move 4 over 9 quit,處理結(jié)果,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:,input：,分析,設(shè)計(jì)的操作: f(i): 把疊在木塊i上的其他木塊放回初始位置. m(i,j): 把i及其以上的木塊全疊到包含j的上方.,move a onto b = f(a),f(b),m(a,b) move a over b = f(a),m(a,b) pile a onto b = f(b),m(a,b) pile a over b = m(

17、a,b),按以上規(guī)則，用鏈表的操作直接模擬即可.,數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì),設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu):,struct Node int No； /木塊編號(hào) struct Node *next； /指向后繼結(jié)點(diǎn)的指針 ;,struct Node *Station25; int Bplace25;,示例 ：,pile 9 over 6,示例(續(xù))：,0,Station0,1,Station1,2,Station2,3,Station3,4,Station4,5,Station5,6,Station6,7,Station7,8,Station8,9,Station9,pile 9 over 6,q-next = p,示例

18、(續(xù)) ：,0,Station0,1,Station1,2,Station2,3,Station3,4,Station4,5,Station5,6,Station6,7,Station7,8,Station8,9,Station9,pile 9 over 6,6,6,示例(續(xù)) ：,pile 9 over 6,示例結(jié)束,例3: Roman Roulette,N個(gè)人排成一圈，按順時(shí)針從1到N編號(hào)。從1開(kāi)始順時(shí)針數(shù)到第k個(gè)人，讓其出圈，接著數(shù)到第k個(gè)人，讓他站在出圈者的位置上。然后從出圈者的后繼位置開(kāi)始數(shù)，重復(fù)上述過(guò)程直到環(huán)中只剩1個(gè)人。當(dāng)N=5,k=2時(shí)，出環(huán)者的順序?yàn)椋?，5，3，1；最后留下

19、4。 輸入：N，k 輸出：I，使得從第I個(gè)人開(kāi)始數(shù)，最后能留下第1人。,模擬過(guò)程,N5，k2,1,2,3,4,5,1,出圈序列：,2,2出去,接著從1開(kāi)始數(shù),模擬過(guò)程(續(xù)1),N5，k2,1,4,5,2,3,出圈序列：2,3,4,4占據(jù)2的位置,模擬過(guò)程(續(xù)2),N5，k2,1,3,5,4,出圈序列：2,3,接著從1 開(kāi)始數(shù),5,5出去,模擬過(guò)程(續(xù)3),N5，k2,3,5,4,出圈序列：2，5,接著數(shù),1,1,4,4占據(jù)5的位置,模擬過(guò)程(續(xù)4),N5，k2,1,3,出圈序列：2，5,4,接著數(shù),1,3,3出去,模擬過(guò)程(續(xù)5),N5，k2,1,3,4,出圈序列：2，5，3,接著數(shù),4,1,

20、1占據(jù)3的位置,模擬過(guò)程(續(xù)6),N5，k2,1,4,接著數(shù),出圈序列：2，5，3,4,1,1出去，環(huán)內(nèi)僅剩1人，結(jié)束,1,模擬過(guò)程(續(xù)7),N5，k2,1,4,出圈序列：2，5，3，1,計(jì)數(shù)時(shí)需要避免計(jì)算已出圈的元素,分析,當(dāng)N5，k2時(shí) 從1開(kāi)始數(shù)，留下4； 從2開(kāi)始數(shù)，留下5； 從3開(kāi)始數(shù)，留下1； 因此，輸入5、2時(shí)，按照要求，應(yīng)輸出3,一般的情況： 從1開(kāi)始數(shù)，留下i； 從2開(kāi)始數(shù)，留下i1； 從n-i+1開(kāi)始數(shù)，留下i+ (n-i+1) -1 = n； 從n-i+2開(kāi)始數(shù)，留下i+ (n-i+2) -1 = 1； 即對(duì)任意輸入，設(shè)程序均從1開(kāi)始數(shù)，則最后第i人留下，若希望第1人留下

21、，則應(yīng)從第ni2人開(kāi)始數(shù)，因此輸出：ni2。,存儲(chǔ)結(jié)構(gòu),用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)進(jìn)行模擬，除了考慮計(jì)數(shù)問(wèn)題外，還特別需要注意指針的運(yùn)算,用數(shù)組作為存儲(chǔ)結(jié)構(gòu)，重點(diǎn)在于計(jì)數(shù)的處理,#include #include int surviver(int n,int k); int main() ifstream fin(E.in); ofstream fout(E.out); int n,k; for(;finnk ,Roman Roulette程序?qū)崿F(xiàn) (uva 130),surviver(n,k) 從第1人開(kāi)始數(shù)，返回值為留下的人的編號(hào)i。 輸出：ni2，使第1人留下,int surviver(in

22、t n,int k) std:vector people; int i,p=-1,p2; for(i=0;i1) p = (p+k) % people.size(); for(i=0,p2=p;ip2) p-; return people0; ,Roman Roulette程序?qū)崿F(xiàn) (uva 130),用線性表保存,n個(gè)人放進(jìn)環(huán)里,數(shù)到第k個(gè)人,繼續(xù)往后數(shù)k個(gè)人,前者出去，后者 取代他的位置,棧和隊(duì)列,棧：僅在表尾進(jìn)行插入刪除的線性表,后進(jìn)先出。 棧常用于模擬和深度優(yōu)先搜索。 隊(duì)列：在表尾插入，在表頭刪除，先進(jìn)先出。 隊(duì)列常用于模擬和廣度優(yōu)先搜索。,(a1，a2，ai，an),棧的示意,棧的修

23、改是按照后進(jìn)先出的原則進(jìn)行的，所以棧稱(chēng)為后進(jìn)先出的線性表（LIFO）,棧底,入棧,出棧,棧頂,棧運(yùn)算示例,例如，有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，若得到的輸出序列是CBDAE ，那么棧中的運(yùn)算是如何進(jìn)行的？,空棧,棧運(yùn)算示例(續(xù)),設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,A,元素A入棧,棧運(yùn)算示例(續(xù)),A,元素A入棧,B,元素B入棧,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,棧運(yùn)算示例(續(xù)),A,元素A入棧 元素B入棧,B,C,元素C入棧,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列

24、CBDAE的過(guò)程。,break,棧運(yùn)算示例(續(xù)),A,元素A入棧 元素B入棧 元素C入棧,C,B,元素C出棧,C,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,棧運(yùn)算示例(續(xù)),A,元素A入棧 元素B入棧 元素C入棧 元素C出棧,C,元素B出棧,B,B,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,棧運(yùn)算示例(續(xù)),A,元素A入棧 元素B入棧 元素C入棧 元素C出棧 元素B出棧,C，B,D,元素D入棧,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,C，B,棧運(yùn)算示

25、例(續(xù)),A,元素A入棧 元素B入棧 元素C入棧 元素C出棧 元素B出棧 元素D入棧,C，B，D,D,元素D出棧,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,C，B，D,棧運(yùn)算示例(續(xù)),空棧,元素A入棧 元素B入棧 元素C入棧 元素C出棧 元素B出棧 元素D入棧 元素D出棧,C，B，D，A,元素A出棧,A,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,棧運(yùn)算示例(續(xù)),元素A入棧 元素B入棧 元素C入棧 元素C出棧 元素B出棧 元素D入棧 元素D出棧 元素A出棧,C，B，D，A,E,元素E入棧,設(shè)有A、

26、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,C，B，D，A,棧運(yùn)算示例(續(xù)),空棧,元素A入棧 元素B入棧 元素C入棧 元素C出棧 元素B出棧 元素D入棧 元素D出棧 元素A出棧 元素E入棧,C，B，D，A，E,元素E出棧,E,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過(guò)程。,break,棧運(yùn)算示例(續(xù)),Push(A) Push(B) Push(C) pop() pop() Push(D) pop() pop() Push(E) pop(),C，B，D，A，E,A，B，C，D，E,設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，

27、得到輸出序列CBDAE的過(guò)程。,例4：Rail,zoj 1259 火車(chē)有n節(jié)車(chē)廂，順序編號(hào)為1,2,3,.,n，從A駛?cè)耄瑥腂駛出，車(chē)站里能停放任意多節(jié)車(chē)廂。一旦進(jìn)入車(chē)站就不再回到A方向的鐵軌上，一旦進(jìn)入B方向鐵軌，不再回車(chē)站。判斷一個(gè)指定車(chē)廂順序能否從B方向駛出。,例5: Anagrams by Stack(zoj 1004),問(wèn)題：有一個(gè)字母序列，對(duì)它每個(gè)元素進(jìn)行入棧、出棧操作。判斷是否能得到指定輸出序列，如果可以，則輸出相應(yīng)的棧操作。,input：,madam adamm,output：, i i i i o o o i o o i i i i o o o o i o i i o i o

28、 i o i o o i i o i o i o o i o ,例6：迷宮問(wèn)題,尋找一條從入口到出口的通路,東,南,迷宮問(wèn)題(續(xù)),北(上),西(左),前進(jìn)方向：上(北)、下(南)、左(西)、右(東),首先從下方開(kāi)始，按照逆時(shí)針?lè)较蛩阉飨乱徊娇赡芮斑M(jìn)的位置,迷宮問(wèn)題(續(xù)),入口,出口,在迷宮周?chē)訅Γ苊馀袛嗍欠癯鼋?8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,迷宮問(wèn)題(續(xù)),9,0,9,0,在尋找出口的過(guò)程中，每前進(jìn)一步，當(dāng)前位置入棧；每回退一步，棧頂元素出棧,i,8,1,2,3,4,5,6,

29、7,8,1,2,3,4,5,6,7,迷宮問(wèn)題(續(xù)),9,0,9,0,棧,(1,1),(2,1),向下方前進(jìn)一步,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),i,(3,1),向下方前進(jìn)一步,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(4,1),(3,1),i,向下方前進(jìn)一步,break,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),

30、(5,1),(3,1),(4,1),向下方前進(jìn)一步,break,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(6,1),(3,1),(4,1),(5,1),向下方前進(jìn)一步,break,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),向下方前進(jìn)一步,break,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,

31、2,3,4,5,6,7,9,0,9,0,向下方 、右方、左方均不能前進(jìn)，上方是來(lái)路，則后退,棧,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),向右方、左方均不能前進(jìn)，下方路不通，上方是來(lái)路，則后退,break,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宮問(wèn)題(續(xù)),0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,

32、9,0,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前進(jìn)一步,break,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(5,3),(5,2),break,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宮問(wèn)題(續(xù)),0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1

33、),(6,1),(5,2),(5,3),break,i,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,4),(5,2),(5,3),(6,3),i,break,i,i,i,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(6,5),(5,2),(5,3),(6,3

34、),(6,4),break,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宮問(wèn)題(續(xù)),0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(7,5),(5,2),(5,3),(6,3),(6,4),(6,5),break,i,i,i,i,i,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,5),

35、(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,i,i,i,i,i,i,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,i,i,i,i,i,i,i,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一

36、步,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,7),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),break,i,i,i,i,i,i,i,i,i,i,i,i,迷宮問(wèn)題(續(xù)),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前進(jìn)一步，到達(dá)出口,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),i,i,(8,7),break,i,i,i,i,i,i,i

37、,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宮問(wèn)題(續(xù)),9,0,用棧保存了路徑,棧,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),(8,7),迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7

38、,9,0,9,0,1,1,2,2,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,2,3,3,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,2,3,4,3,4,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,2,3,4,

39、5,3,4,5,5,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,6,2,3,4,5,3,4,5,6,5,6,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,7,1,2,6,7,2,3,4,5,3,4,5,6,5,7,6,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4

40、,5,6,7,9,0,9,0,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,6,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,7,8,9,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,9,6,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,1,2,6,7,8,2,3,4,5,10,3,10,4,5

41、,6,10,5,7,8,9,6,10,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,1,2,6,7,8,2,3,4,5,10,11,3,11,10,11,4,5,6,10,11,5,7,8,9,6,10,11,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,1

42、1,12,4,5,6,10,11,12,5,7,8,9,6,10,12,11,12,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,

43、9,0,9,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,迷宮問(wèn)題(最短路徑),入口,出口,借助于隊(duì)列可求得入口到出口的最短路徑(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,棧與遞歸,遞歸是描述或解決一類(lèi)問(wèn)題的簡(jiǎn)單方法 遞歸定義的函數(shù)運(yùn)行時(shí)需要控制棧的支持,long f(int n) if (n1) return n*f(n-1); else return 1; ,遞歸函數(shù)的執(zhí)行,STL中的棧,#

44、include #include #include using namespace std; int main() stack s; s.push(1); s.pop(); s.push(10); s.push(11); cout s.top() endl; cout s.size() endl; cout s.empty() endl; return 0; ,The C+ Stack is a container adapter that gives the programmer the functionality of a stack - specifically, a FILO (first-in, last-out) data structure Stack constructors:construct a new stack empty:true if the stack has no elements pop:removes the top element of a stack push:adds an element to the top of