18实验报告

软件工程专业类课程实验报告课程名称：数据结构学院专业：计算机科学与技术学生姓名：黄翔宇学号：2013060105001日期：2014年12月5日电子科技大学计算机学院实验中心电子科技大学实验报告实验名称：第二个项目迷宫游戏实验要求：基本要求：从文件中/读出迷宫数据，寻找并打印路径通路；存储迷宫数据到文件。文件中迷宫地图数据格式为：长宽入口出口迷宫地图数据迷宫地图数据由01二进制组成，1表示墙壁，0表示通路。可以采用字符显示迷宫地图和路径，比如□表示通路，▇表示墙壁，※表示找到的路径。也可以采用windows窗体设计和绘制迷宫地图和路径中级要求：寻找多入口多出口地图的所有通路高级要求：自动生成迷宫地图实验代码：#includeiostream#includefstream#includectime#includecstdlib#definepath0#definewall2#definestep1#defineold3#defineOut4#defineup10#definedown11#defineleft12#defineright13usingnamespacestd;typedefstructnode{intx,y;node*next;};classlist{private:node*head;public:list(){head=newnode[1];head-next=NULL;head-x=0;}voidadd(intx,inty){node*p=newnode[1];p-x=x;p-y=y;p-next=NULL;if(head-next==NULL){head-next=p;}else{p-next=head-next;head-next=p;}head-x++;}voidRandChooseSide(int*x,int*y){inti=RandInt(1,head-x),j;node*tmp1,*tmp2;for(tmp1=head,j=0;ji-1;j++,tmp1=tmp1-next);tmp2=tmp1-next;*x=tmp2-x;*y=tmp2-y;tmp1-next=tmp2-next;(head-x)--;delete[]tmp2;}boolIsEmpty(){if(head-next==NULL)returntrue;returnfalse;}intRandInt(inti,intj){srand((unsigned)time(NULL));inttmp;if(i==j){returni;}else{tmp=rand()%(j-i+1)+i;}returntmp;}};classMaze{private:int**maze,*pre;listl;intwidth,height;public:Maze(intwidth,intheight)//width--列数--y,height--行数--x,width&height必须是奇数{this-height=height;this-width=width;maze=newint*[height];pre=newint[width*height];for(inti=0;iheight;i++){maze[i]=newint[width];}for(inti=0;iheight;i++)for(intj=0;jwidth;j++){maze[i][j]=1;if(i%2==1&&j%2==1)maze[i][j]=0;}for(inti=0;iwidth*height;i++){pre[i]=i;//i=x*width+y+1}for(inti=1;iheight-1;i++)for(intj=1;jwidth-1;j++){if((i%2==1&&j%2==0)||(i%2==0&&j%2==1))l.add(i,j);}}intfindPre(inti){if(pre[i]==i){returni;}else{returnfindPre(pre[i]);}}voidRandChooseSide(int*x,int*y){l.RandChooseSide(x,y);}voidCreateMaze(){intx,y;intpre1,pre2;do{RandChooseSide(&x,&y);if(x%2==1)//有点问题。。。{pre1=findPre(x*width+y);pre2=findPre(x*width+y+2);if(pre1!=pre2)//判断边的左右是否连通{maze[x][y]=0;if(pre1pre2){pre[x*width+y+2]=pre1;//将右边的并入左边的集合pre[pre2]=pre1;}else{pre[x*width+y]=pre2;pre[pre1]=pre2;}}}else{pre1=findPre(x*width-width+y+1);pre2=findPre(x*width+width+y+1);if(pre1!=pre2){maze[x][y]=0;if(pre1pre2){pre[x*width+width+y+1]=pre1;//将下面的并入上面的pre[pre2]=pre1;}else{pre[x*width-width+y+1]=pre2;pre[pre1]=pre2;}}}}while((findPre(width+2)!=findPre((width-2)*width+height-1)));//判断首尾是否在同一集合中}voidshow(){for(inti=0;iheight;i++){for(intj=0;jwidth;j++){if(maze[i][j]==0)cout;else{cout█;}}coutendl;}}voidfput(){fstreamf1;f1.open(d:\\maze.txt,ios::out);f1heightwidth01height-1width-2endl;for(inti=0;iheight;i++){for(intj=0;jwidth;j++){if(maze[i][j]==1){f12;}else{f10;}}f1endl;}}};classstack{public:intx,y;stack*next;stack(){next=NULL;}};stack*CreatNode(stack*top,intnx,intny,int**labyrinth){stack*creat=newstack;creat-x=nx;creat-y=ny;creat-next=top;top=creat;labyrinth[creat-x][creat-y]=1;returntop;}boolStackEmpty(stack*top){returntop==NULL;}stack*StackDelete(stack*top,int**labyrinth){if(top-next==NULL)returnNULL;else{stack*np=newstack;np=top;labyrinth[np-x][np-y]=old;top=top-next;deletenp;returntop;}}intProbe(int**labyrinth,intx,inty,intlength,intheight,intmapData){if(x-1=0){if(labyrinth[x-1][y]==mapData)returnup;}if(x+1height){if(labyrinth[x+1][y]==mapData)returndown;}if(y-1=0){if(labyrinth[x][y-1]==mapData)returnleft;}if(y+1length){if(labyrinth[x][y+1]==mapData)returnright;}return0;}stack*Search(int**labyrinth,stackenter,stackexit,intlength,intheight){stack*top;inti,j,forward;top=&enter;i=enter.x,j=enter.y;for(;;){forward=Probe(labyrinth,i,j,length,height,path);if(forward==up){i--;top=CreatNode(top,i,j,labyrinth);}elseif(forward==down){i++;top=CreatNode(top,i,j,labyrinth);}elseif(forward==left){j--;top=CreatNode(top,i,j,labyrinth);}elseif(forward==right){j++;top=CreatNode(top,i,j,labyrinth);}else{top=StackDelete(top,labyrinth);if(top==NULL)returntop;i=top-x,j=top-y;}labyrinth[i][j]=step;forward=Probe(labyrinth,i,j,length,height,Out);if(forward==up||forward==down||forward==left||forward==right)break;}returntop;}intrun(){fstreammapFile;mapFile.open(d:\\maze.txt,ios::in);if(!mapFile){cerrFilecannotbeopened!;return-1;}intlength,height,i,j;mapFilelengthheight;stackenter,exit;mapFileenter.xenter.y;mapFileexit.xexit.y;int**labyrinth=newint*[length];labyrinth[0]=newint[height*length];for(i=1;ilength;i++){labyrinth[i]=labyrinth[i-1]+height;}for(j=0;jheight;j++)for(i=0;ilength;i++)mapFilelabyrinth[i][j];labyrinth[exit.x][exit.y]=Out;stack*top;top=Search(labyrinth,enter,exit,length,height);if(top==NULL){coutNopathsforthislabyrinth!;return-1;}coutpath:endl;for(j=0;jheight;j++){for(i=0;ilength;i++){if(labyrinth[i][j]==wall||labyrinth[i][j]==Out)cout█;elseif(labyrinth[i][j]==step)cout★;elsecout;}coutendl;}coutThepathofthelabyrinthwasover.;}intmain(){MazeA(25,25);//此处长宽需奇数A.CreateMaze();A.fput();A.show();strings;coutusing\path\toshowthepathendl;while(1){cins;if(s==path){run();return0;}else{couterror