数据结构实验报告-栈和队列(迷宫图最短路径)

1、第第 页五、附录源代码:/本程序在windows7、visualstudio2008环境下调试运行成功#includeusingnamespacestd;voidEnQueue(inti,intj,intk);/入队一个节点voidDeQueue(int*i,int*j,int*k);/获取当前节点的序号和对应的迷宫坐标，然后出列boolGetNextPos(int*i,int*j,intcount);/得到下一个邻接点的位置voidShortestPath_BFS(inti,intj);/广度优先遍历寻找最短路径voidShortestPath();/输出最短路径voidPrint();/输

2、出迷宫形状intMap1010=1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1;structNodeintparent_id;/保存父节点的位置intnode_id;/当前节点的序号，以便传递给孩子节点intx,y;/当前结点对应的坐标Q10*10

3、;的序号，多个节点形成队列/每个节点包含迷宫坐标、队列中的序号、父节点intfront=0,rear=0;/队列头指针和尾指针voidmain()coutvv程序说明：vvnvvl.输出路径为最短路径；vvnvv2.默认的出口在最右下角，如有需要可以调整。”vvnvvn;coutvv初始地图如下：vvendl;Print();inti,j;reinput:coutvv请输入起点坐标(x,y)：vvendl;if(Mapij)coutvv不能从该处出发，请重新输入！vvendl;gotoreinput;ShortestPath_BFS(i,j);coutvv最短路径之一如下：vvendl;Sho

4、rtestPath();voidEnQueue(inti,intj,intk)/保存当前节点对应的坐标位置/保存当前节点对应的坐标位置/保存父节点的序号/保存当前节点序号Qrear.y=j;Qrear.parent_id=k;Qrear.node_id=rear;rear+;voidDeQueue(int*i,int*j,int*k)*i=Qfront.x;*j=Qfront.y;*k=Qfront.node_id;front+;/出列一个节点boolGetNextPos(int*i,int*j,intcount)switch(count)TOC o 1-5 h zcase1:(*j)+;re

5、turn1;/右case2:(*i)+;return1;/下case3:(*j)-;return1;/左case4:(*i)-;return1;/上default:return0;voidShortestPath_BFS(inti,intj)intcount,m,n,k;EnQueue(i,j,-1);Map11=1;/起点入队,标记起点已走过while(true)count=1;DeQueue(&i,&j,&k);n=i,m=j;/保存当前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij)EnQueue(i,j,k);Mapij=1;if(i=8&j=9)return;/到达终点,(8,9)是默认终点，可以任意修改i=n;j=m;/保证遍历当前坐标的所有相邻位置voidShortestPath()inti,j,k,sum(0);k=rear-1;while(k!=-1)i=Qk.x;j=Qk.y;Mapij=2;k=Qk.parent_id;cout0123456789endl;for(i=0;i10;i+)couti;for(j=0;j10;j+)if(Mapij=2)sum+;coutvv讣elsecoutvv”；coutendl;coutvv最短路径长度：vvsumvvendl;voidPrint()cout01