数据结构上机报告(迷宫)

数据结构上机报告（迷宫）迷宫求解小组成员问题提出：利用栈结构实现迷宫求解问题。迷宫求解问题如下：

心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示：问题分析及算法设计：1.迷宫中有障碍物的地方设置为1，没有障碍物的地方设置为0；2.设起点下标为(1,1)，终点下标为(10,8)；3.从起点出发(起点入栈),栈中存放走过的路径(坐标)；4.每次取栈顶元素，在其上下左右中选一个能走通的且没有走过的点入栈；5.若该点为终点；则结束，输出路径；6.若上下左右都不通或已走过,则出栈,栈空,则走不通。程序设计：用户手册：运行程序；根据提示，在“请输入迷宫矩阵，<10*10>：”后输入迷宫矩阵；按enter键，根据提示，在“请输入起始点<0~9>：”后输入起始点；按enter键，根据提示，在“请输入结束点<0~9>：”后输入结束点；按enter键，即可得出最短路径的长度和最短路径的坐标表示；关闭操作窗口，结束运行。附图例：调试报告：附录：程序代码：#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<<"请输入起始点(0~9):"<<endl; cin>>p0.x>>p0.y;}voidMaze::Initpn(){ cout<<"请输入结束点(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<<"输入的点不符合条件。"<<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