數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告(迷宮)

數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告（迷宮）迷宮求解小組成員問題提出：利用棧結(jié)構(gòu)實(shí)現(xiàn)迷宮求解問題。迷宮求解問題如下：

心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口，測試算法的迷宮如下圖所示：問題分析及算法設(shè)計(jì)：1.迷宮中有障礙物的地方設(shè)置為1，沒有障礙物的地方設(shè)置為0；2.設(shè)起點(diǎn)下標(biāo)為(1,1)，終點(diǎn)下標(biāo)為(10,8)；3.從起點(diǎn)出發(fā)(起點(diǎn)入棧),棧中存放走過的路徑(坐標(biāo))；4.每次取棧頂元素，在其上下左右中選一個(gè)能走通的且沒有走過的點(diǎn)入棧；5.若該點(diǎn)為終點(diǎn)；則結(jié)束，輸出路徑；6.若上下左右都不通或已走過,則出棧,?？?則走不通。程序設(shè)計(jì)：用戶手冊：運(yùn)行程序；根據(jù)提示，在“請輸入迷宮矩陣，<10*10>：”后輸入迷宮矩陣；按enter鍵，根據(jù)提示，在“請輸入起始點(diǎn)<0~9>：”后輸入起始點(diǎn)；按enter鍵，根據(jù)提示，在“請輸入結(jié)束點(diǎn)<0~9>：”后輸入結(jié)束點(diǎn)；按enter鍵，即可得出最短路徑的長度和最短路徑的坐標(biāo)表示；關(guān)閉操作窗口，結(jié)束運(yùn)行。附圖例：調(diào)試報(bào)告：附錄：程序代碼：#include<iostream>usingnamespacestd;structPoint{ intx; inty; intpre;};voidCopy(Point&a,Point&b){ a.x=b.x; a.y=b.y; a.pre=b.pre;}structQueue{ Pointp[100]; inthead=0; inttail=0;};voidAppend(Queue&d,Pointp){ d.p[d.tail].x=p.x; d.p[d.tail].y=p.y; d.p[d.tail].pre=p.pre; d.tail++;}voidDelete(Queue&d,Point&a){ Copy(a,d.p[d.head]); d.head++;}structStack{ Pointq[100]; inthead=0;};voidpush(Stack&s,Pointp){ s.q[s.head].x=p.x; s.q[s.head].y=p.y; s.head++;}voidpop(Stack&s){ s.head--; cout<<"("<<s.q[s.head].x<<","<<s.q[s.head].y<<")"<<endl;}classMaze{public: Pointp0; Pointpn; intm[10][10]; inti=0; intl;public: voidInitp0(); voidInitpn(); voidpdp0pn(); voidInitM(); voidkz(Queue&Q,Pointa);};voidmain(){ intu=0; QueueQ; StackS; MazeM; M.InitM(); M.Initp0(); Pointa=M.p0; M.Initpn(); Append(Q,a); while(1) { if(u==1) break; M.l=Q.tail; while(Q.head<M.l) { Delete(Q,a); if(a.x==M.pn.x&&a.y==M.pn.y) { u=1; break; } else { M.kz(Q,a); M.m[a.x][a.y]=1; } } M.i++; } cout<<"最短路徑的長度為："<<M.i-1<<endl; cout<<"最短路徑為："<<endl; while(a.pre>=0) { push(S,a); a=Q.p[a.pre]; } push(S,M.p0); while(S.head>0) { pop(S); }}voidMaze::Initp0(){ cout<<"請輸入起始點(diǎn)(0~9):"<<endl; cin>>p0.x>>p0.y;}voidMaze::Initpn(){ cout<<"請輸入結(jié)束點(diǎn)(0~9):"<<endl; cin>>pn.x>>pn.y;}voidMaze::InitM(){ cout<<"請輸入迷宮矩陣(10*10):"<<endl; for(inti=0;i<10;i++) { for(intj=0;j<10;j++) cin>>m[i][j]; }}voidMaze::pdp0pn(){ if(m[p0.x][p0.y]==1||m[pn.x][pn.y]==1) cout<<"輸入的點(diǎn)不符合條件。"<<endl;}voidMaze::kz(Queue&Q,Pointa){ Pointb; b.pre=Q.head-1; if(m[a.x-1][a.y]!=1&&a.x-1>=0) { b.x=a.x-1; b.y=a.y; Append(Q,b); } if(m[a.x+1][a.y]!=1&&a.x+1<=9) { b.x=a.x+1; b.y=a.y; Append(Q,b); } if(m[a.x][a.y-1]!=1&&a.y-1>=0) { b.x=a.x; b.y=a.y-1; Append(Q,b); }if(m[a.x][a.y+1]!=1&&a.y+1<=9) { b.x=a.x; b.y=a.y+1; Append(Q,b); }}/*11111111111000110011101001100