2-基本數(shù)據(jù)結(jié)構(gòu)1

ACM/ICPC程序設(shè)計(jì)基本數(shù)據(jù)結(jié)構(gòu)及其在程序設(shè)計(jì)中的應(yīng)用張淑平程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)(DataStructure)是數(shù)據(jù)的計(jì)算機(jī)表示和相應(yīng)的一組操作。算法(Algorithm)就是解決問題的方法或過程?；緮?shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)集合樹結(jié)構(gòu)圖結(jié)構(gòu)線性表?xiàng)ｊ?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è)元素可供刪除棧：插入和刪除操作只允許在表尾進(jìn)行隊(duì)列：在表尾插入、在表頭刪除串：元素為字符的線性表，有求子串、子串定位、子串替換等操作(a1，a2，…，ai，…，an)表頭元素表尾元素?cái)?shù)據(jù)結(jié)構(gòu)中的存儲(chǔ)結(jié)構(gòu)－－元素及元素間關(guān)系的存儲(chǔ)數(shù)組鏈表數(shù)組用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素.表中任一元素可以隨機(jī)存取.插入或刪除一個(gè)元素需要移動(dòng)其他元素.a1a2...aian...dai+1由下標(biāo)確定數(shù)組元素a[i]：Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)例如：由n個(gè)元素構(gòu)成的一維數(shù)組a鏈表鏈?zhǔn)酱鎯?chǔ):任意存儲(chǔ)單元存儲(chǔ)元素鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域插入或刪除一個(gè)元素,只需修改結(jié)點(diǎn)指針域訪問任一元素必須從鏈表頭指針開始a2ai...a1ai+1...an...鏈表結(jié)點(diǎn)鏈?zhǔn)酱鎯?chǔ):任意存儲(chǔ)單元存儲(chǔ)元素鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域插入或刪除一個(gè)元素,只需修改結(jié)點(diǎn)指針域訪問任一元素必須從鏈表頭指針開始數(shù)據(jù)data指針next

structNode{

ElemTypedata；//數(shù)據(jù)元素

struct

Node*next；//指向后繼結(jié)點(diǎn)的指針};單向鏈表線性表：(a1，a2，…，ai-1，ai，ai+1，…，an)(a)單向鏈表…a2a1an∧an-1…aiai-1ai+1head頭結(jié)點(diǎn)(b)帶頭結(jié)點(diǎn)的單向鏈表…a2a1an∧an-1…aiai-1ai+1head雙向鏈表和循環(huán)鏈表線性表：(a1，a2，…，ai-1，ai，ai+1，…，an)head…a1∧a2an-1anai…∧(a)雙向鏈表taila2a1anan-1…(b)循環(huán)單鏈表單鏈表的插入和刪除鏈?zhǔn)酱鎯?chǔ):任意存儲(chǔ)單元存儲(chǔ)元素鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域插入或刪除一個(gè)元素，只需修改結(jié)點(diǎn)指針域訪問任一元素必須從鏈表頭指針開始頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)的單向鏈表…a2a1an∧an-1…aiai-1ai+1head單鏈表中插入元素將元素ai所在結(jié)點(diǎn)的地址賦給元素e結(jié)點(diǎn)的指針域：S->next=P->next;aiai-1…ai+1…PeS修改元素ai-1所在結(jié)點(diǎn)指針域的值：

P->next=S;②①單鏈表中刪除元素ai修改元素ai-1所在結(jié)點(diǎn)指針域的值：P->next=P->next->next;aiai-1…ai+1…P例1:UglyNumbersUglynumbersarenumberswhoseonlyprimefactorsare2,3or5.Thesequence1,2,3,4,5,6,8,9,10,12,15,...showsthefirst11uglynumbers.Byconvention,1isincluded.Writeaprogramtofindandprintthe1500'thuglynumber.算法思路:一個(gè)正整數(shù)m可表示如下：

m=(p1)j1*(p2)j2*…*(pn)jnUglynumber=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)態(tài)分配.例2：TheBlocksProblem

編號(hào)為0~n-1的n個(gè)木塊，放在編號(hào)為0~n-1的n個(gè)格子里,可對(duì)它們進(jìn)行四種有效的操作。01234n-1...InitialBlockWorldmoveaontob：先將a和b上的其他木塊移回到它們的初始位置，然后將木塊a摞在木塊b上.moveaoverb：先將木塊a上的其他木塊移到它們的初始位置后，然后將木塊a摞到包含了木塊b的那一堆木塊上面pileaontob：先將木塊b上的所有木塊移回到它們的初始位置，然后將木塊a及其上的木塊移到木塊b上.

pileaoverb：將包含木塊a的那一摞木塊移到包含了木塊b的那一堆木塊上面.moveaontob先將a和b上的其他木塊移回到它們的初始位置，然后將木塊a摞在木塊b上.01234567890123456789Example:move3onto6012345678901234567893moveaoverb先將木塊a上的其他木塊移到它們的初始位置后，然后將木塊a摞到包含了木塊b的那一堆木塊上面.01234567890123456789Example:move3over6012345678901234567893pileaontob

先將木塊b上的所有木塊移回到它們的初始位置，然后將木塊a及其上的木塊移到木塊b上.Example:pile3onto6012345678901234567890123456780123456789999012345678012345678pileaoverb將包含木塊a的那一摞木塊移到包含了木塊b的那一堆木塊上面.Example:pile3over6012345678901234567890123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

輸入數(shù)據(jù)樣本0:01:19242:3:34:5:58766:7:8:9:

input：output：10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程：InitialBlockWorld01234567890123456789格子編號(hào)10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：01234567890123456789Anycommandinwhicha=borinwhichaandbareinthesamestackofblocksisanillegalcommand.Allillegalcommandsshouldbeignoredandshouldhavenoaffectontheconfigurationofblocks.10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：0123456789012345678910move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理過程(續(xù))：01234567890123456789output：10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit

處理結(jié)果012345678901234567890:01:19242:3:34:5:58766:7:8:9:

input：分析設(shè)計(jì)的操作:f(i):

把疊在木塊i上的其他木塊放回初始位置.m(i,j):

把i及其以上的木塊全疊到包含j的上方.moveaontob=>f(a),f(b),m(a,b)moveaoverb=>f(a),m(a,b)pileaontob=>f(b),m(a,b)pileaoverb=>m(a,b)按以上規(guī)則，用鏈表的操作直接模擬即可.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu):structNode{

intNo；//木塊編號(hào)

structNode*next；//指向后繼結(jié)點(diǎn)的指針};structNode*Station[25];intBplace[25];0∧Station[0]1∧Station[1]2∧Station[2]3∧Station[3]4∧Station[4]5∧Station[5]6∧Station[6]7∧Station[7]8∧Station[8]9∧Station[9]0Bplace[0]1Bplace[1]2Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]7Bplace[7]8Bplace[8]9Bplace[9]示例：012345678901234567890Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]0Bplace[0]1Bplace[1]1Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]5Bplace[7]5Bplace[8]1Bplace[9]pile9over6p示例(續(xù))：012345678901234567890Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]0Bplace[0]1Bplace[1]1Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]5Bplace[7]5Bplace[8]1Bplace[9]pile9over6∧pqq->next=p示例(續(xù))：012345678901234567890Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]0Bplace[0]1Bplace[1]1Bplace[2]3Bplace[3]4Bplace[4]5Bplace[5]6Bplace[6]5Bplace[7]5Bplace[8]1Bplace[9]pile9over6∧pq66示例(續(xù))：01234567890123456789pile9over60Station[0]1Station[1]2Station[2]3Station[3]4Station[4]5Station[5]6Station[6]7Station[7]8Station[8]∧∧∧∧9∧∧∧∧∧∧Station[9]∧示例結(jié)束例3:RomanRouletteN個(gè)人排成一圈，按順時(shí)針從1到N編號(hào)。從1開始順時(shí)針數(shù)到第k個(gè)人，讓其出圈，接著數(shù)到第k個(gè)人，讓他站在出圈者的位置上。然后從出圈者的后繼位置開始數(shù)，重復(fù)上述過程直到環(huán)中只剩1個(gè)人。當(dāng)N=5,k=2時(shí)，出環(huán)者的順序?yàn)椋?，5，3，1；最后留下4。輸入：N，k輸出：I，使得從第I個(gè)人開始數(shù)，最后能留下第1人。模擬過程N(yùn)＝5，k＝2123451出圈序列：22出去接著從1開始數(shù)模擬過程(續(xù)1)N＝5，k＝214523出圈序列：2344占據(jù)2的位置模擬過程(續(xù)2)N＝5，k＝21354出圈序列：23接著從1開始數(shù)55出去模擬過程(續(xù)3)N＝5，k＝2354出圈序列：2，5接著數(shù)1144占據(jù)5的位置模擬過程(續(xù)4)N＝5，k＝213出圈序列：2，54接著數(shù)133出去模擬過程(續(xù)5)N＝5，k＝2134出圈序列：2，5，3接著數(shù)411占據(jù)3的位置模擬過程(續(xù)6)N＝5，k＝214接著數(shù)出圈序列：2，5，3411出去，環(huán)內(nèi)僅剩1人，結(jié)束1模擬過程(續(xù)7)N＝5，k＝214出圈序列：2，5，3，1計(jì)數(shù)時(shí)需要避免計(jì)算已出圈的元素分析當(dāng)N＝5，k＝2時(shí)

從1開始數(shù)，留下4；從2開始數(shù)，留下5；從3開始數(shù)，留下1；因此，輸入5、2時(shí)，按照要求，應(yīng)輸出3一般的情況：從1開始數(shù)，留下i；

從2開始數(shù)，留下i＋1；…

從n-i+1開始數(shù)，留下i+(n-i+1)-1=n；

從n-i+2開始數(shù)，留下i+(n-i+2)-1=1；

即對(duì)任意輸入，設(shè)程序均從1開始數(shù)，則最后第i人留下，若希望第1人留下，則應(yīng)從第n－i＋2人開始數(shù)，因此輸出：n－i＋2。存儲(chǔ)結(jié)構(gòu)用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)進(jìn)行模擬，除了考慮計(jì)數(shù)問題外，還特別需要注意指針的運(yùn)算用數(shù)組作為存儲(chǔ)結(jié)構(gòu)，重點(diǎn)在于計(jì)數(shù)的處理#include<fstream.h>#include<vector>int

surviver(int

n,intk);intmain(){

ifstreamfin("E.in");

ofstream

fout("E.out");

intn,k;for(;fin>>n>>k&&n;){if(n==1)

fout<<1<<endl;else

fout<<n-surviver(n,k)+2<<endl;}return0;}RomanRoulette程序?qū)崿F(xiàn)(uva130)surviver(n,k)從第1人開始數(shù)，返回值為留下的人的編號(hào)i。輸出：n－i＋2，使第1人留下int

surviver(int

n,intk){std::vector<int>people;

inti,p=-1,p2;for(i=0;i<n;i++)people.push_back(i+1);while(people.size()>1){p=(p+k)%people.size();

for(i=0,p2=p;i<k;i++){p2=(p2+1)%people.size();if(p2==p)i--;}people[p]=people[p2];people.erase(people.begin()+p2);if(p>p2)p--;}returnpeople[0];}RomanRoulette程序?qū)崿F(xiàn)(uva130)用線性表保存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)棧的示意棧的修改是按照后進(jìn)先出的原則進(jìn)行的，所以棧稱為后進(jìn)先出的線性表（LIFO）an

an-1

a2

a1…

棧底

入棧

出棧棧頂棧運(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的過程。A元素A入棧棧運(yùn)算示例(續(xù))A元素A入棧B元素B入棧設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。break棧運(yùn)算示例(續(xù))A元素A入棧元素B入棧BC元素C入棧設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。break棧運(yùn)算示例(續(xù))A元素A入棧元素B入棧元素C入棧CB元素C出棧C設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。break棧運(yùn)算示例(續(xù))A元素A入棧元素B入棧元素C入棧元素C出棧

C元素B出棧B,B設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。break棧運(yùn)算示例(續(xù))A元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧C，BD元素D入棧設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。breakC，B棧運(yùn)算示例(續(xù))A元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧元素D入棧C，B，DD元素D出棧設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。breakC，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的過程。break棧運(yùn)算示例(續(xù))元素A入棧元素B入棧元素C入棧元素C出棧元素B出棧元素D入棧元素D出棧元素A出棧C，B，D，AE元素E入棧設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。breakC，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的過程。break棧運(yùn)算示例(續(xù))Push(A)Push(B)Push(C)pop()pop()Push(D)pop()pop()Push(E)pop()C，B，D，A，EA，B，C，D，E設(shè)有A、B、C、D、E五個(gè)元素依次進(jìn)入一個(gè)棧，得到輸出序列CBDAE的過程。例4：Railzoj1259火車有n節(jié)車廂，順序編號(hào)為1,2,3,...,n，從A駛?cè)?，從B駛出，車站里能停放任意多節(jié)車廂。一旦進(jìn)入車站就不再回到A方向的鐵軌上，一旦進(jìn)入B方向鐵軌，不再回車站。判斷一個(gè)指定車廂順序能否從B方向駛出。例5:AnagramsbyStack(zoj1004)問題：有一個(gè)字母序列，對(duì)它每個(gè)元素進(jìn)行入棧、出棧操作。判斷是否能得到指定輸出序列，如果可以，則輸出相應(yīng)的棧操作。input：madamadammoutput：[iiiioooiooiiiiooooioiioioioiooiioioiooio]8123456781234567入口出口例6：迷宮問題尋找一條從入口到出口的通路東南迷宮問題(續(xù))北(上)西(左)前進(jìn)方向：上(北)、下(南)、左(西)、右(東)首先從下方開始，按照逆時(shí)針方向搜索下一步可能前進(jìn)的位置迷宮問題(續(xù))入口出口在迷宮周圍加墻，避免判斷是否出界812345678123456790908123456781234567迷宮問題(續(xù))9090在尋找出口的過程中，每前進(jìn)一步，當(dāng)前位置入棧；每回退一步，棧頂元素出棧棧(1,1)i8123456781234567迷宮問題(續(xù))9090棧(1,1)(2,1)向下方前進(jìn)一步i迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)i(3,1)向下方前進(jìn)一步ii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(4,1)(3,1)i向下方前進(jìn)一步breakiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(5,1)(3,1)(4,1)向下方前進(jìn)一步breakiiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前進(jìn)一步breakiiiiii迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前進(jìn)一步breakiiiiii@迷宮問題(續(xù))81234567812345679090向下方、右方、左方均不能前進(jìn)，上方是來路，則后退棧(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)breakiiiii@@迷宮問題(續(xù))81234567812345679090棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前進(jìn)，下方路不通，上方是來路，則后退breakiiiii@@81234567迷宮問題(續(xù))0981234567812345679090棧(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前進(jìn)一步breakiiiiii@@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)breakiiiiiii@@81234567迷宮問題(續(xù))0981234567812345679090向下方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)breakiiiiiii@@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreakiiiiiii@ii@迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)breakiiiiiii@iii@81234567迷宮問題(續(xù))0981234567812345679090向下方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)breakiiiiiii@iii@i迷宮問題(續(xù))81234567812345679090向下方前進(jìn)一步棧(1,1)(2,1)(3,1)(4,1)(5,1)(8,5)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)breakiiiiiii@iii@ii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(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)breakiiiiiii@iii@iii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(jìn)一步棧(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)breakiiiiiii@iii@ii迷宮問題(續(xù))81234567812345679090下方路不通，向右方前進(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)ii(8,7)breakiiiiiii@iii@iiii81234567迷宮問題(續(xù))981234567090用棧保存了路徑棧(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)迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909011迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790901122迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090112233迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909011223434迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909011223453455迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909011262345345656迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909017126723453456576迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909017812678234534565786迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790901789126782345345657896迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909178912678234510310456105789610迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909091789126782345101131110114561011578961011迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)81234567812345679090917891267812234510113111011124561011125789610121112迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909091789131267812234510113111011124561011121357896101312111213迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)8123456781234567909091789131267812234510113111011124561011121357896101312111213迷宮問題(最短路徑)入口出口借助于隊(duì)列可求得入口到出口的最短路徑(若存在)812345678123456790909棧與遞歸遞歸是描述或解決一類問題的簡(jiǎn)單方法遞歸定義的函數(shù)運(yùn)行時(shí)需要控制棧的支持longf(intn){if(n>1)returnn*f(n-1);elsereturn1;}遞歸函數(shù)的執(zhí)行STL中的棧#include<iostream>#include<cstdlib>#include<stack>usingnamespacestd;intmain(){stack<int>s;

s.push(1);

s.pop();

s.push(10);s.push(11);

cout<<s.top()<<endl;

cout<<s.size()<<endl;

cout<<s.empty()<<endl;return0;}TheC++Stackisacontaineradapterthatgivestheprogrammerthefunctionalityofastack--specifically,aFILO(first-in,last-out)datastructureStackconstructors:constructanewstackempty:trueifthestackhasnoelementspop:removesthetopelementofastackpush:addsanelementtothetopofthestacksize:retur