数据结构实验报告-链栈编写迷宫

数据结构课程设计报告题目:用栈解决迷宫问题院系： 二系 专业班级： 10信息名： 学号： 指导教师： 2012年6月一需求分析1.1问题描述：以一个mXn的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论1.2基本要求：输入形式和输入值的范围：50行50列。输出形式：求得的通路以三元组(x,y,j)的形式输出，其中：(i,j)指示迷宫中的一个坐标，j表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1),(1,2,2),(2,2,2)，(3,2,3),(3,1,2),…。程序所能达到的功能：求出一条从入口到出口的通路及路径长度或得出没有通路的结论。二、概要设计1、数据结构以结构体储存迷宫信息，链栈储存结点及坐标。2、程序模块迷宫生产模块：手动生成迷宫。判断结点存在：防止结点的重复访问。路径查找模块：实现通路的查找，返回一条通路。路径输出模块：实现路径以题意要求输出。3、各模块之间的调用关系及算法设计三、详细分析结构体：intarry[M][N]；intmax_x,max_y;链栈的设计：intvex_x,vex_y;structpoint*next;intdirection;创建迷宫：cout〈〈〃请输入迷宫的列和列：〃；cin>>a.max_x>>a.max_y;for（i=1;i〈=a.max_x;i++）{输入各数组元素}returna;查找栈中结点判断是否与当前结点相等：Point*p=head;While（p非空）{if（但前坐标与栈中某坐标相等）return1p=p->next;}Return0；5•迷宫函数，返回一条通道或者NULL：Point*top,*p;intj,find,x,y;do{while（方向j〈4）{find=0；switch（j）//1234分别表示东南西北{case1：if（纵坐标加1后在迷宫内，且当前结点为0,且当前结点没有在栈中出现）{当前结点进栈；把方向j赋予当前结点方向；find=1;}break;case2：if（纵横标加1后在迷宫内，且当前结点为0,且当前结点没有在栈中出现）{当前结点进栈；把方向j赋予当前结点方向；find=1;}break；case3:if（纵做标减1后在迷宫内，且当前结点为0,且当前结点没有在栈中出现）{当前结点进栈；把方向j赋予当前结点方向；find=1;}break；case4:if（纵横标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现）{当前结点进栈；把方向j赋予当前结点方向；find=1;}break;}if（find==1）{j++;break;}elsej++;}if（j>4）{if（栈顶前一个结点不为空）{当前结点出栈且方向加1}elsereturnNULL;}}while（当前结点不是出口）returntop;输出函数：inti=0,top=0;Point*stack[M];if（栈顶为空）cout〈〈”没通路”〈〈endl;else{while（栈顶不为空）{通过一个顺序栈将链栈逆序;top++;}While（top>0）{输出结果}}主函数：voidmain（）{sdroad;Point*po;road=creat（）;po=secret（road）;disp（po）;}

四、测试与分析1•测试数据：程序运行结果截图:(1).4行4列迷宫矩阵:'==■'-11C;\DocumentsandSettings1'1.,Adm... ^3官宫T=T=f=f=¥¥壽AASS出出勺・ra01—dzL—dzL1100迷宫通道如下；<±,1,1><±,2,±><±,3,2><2,3,3><2,2,2><3,2,2><4,2,1X4,3,1>PressAnyJteiF1:ocontinue官宫T=T=f=f=¥¥壽AASS出出勺・ra01—dzL—dzL1100迷宫通道如下；<±,1,1><±,2,±><±,3,2><2,3,3><2,2,2><3,2,2><4,2,1X4,3,1>PressAnyJteiF1:ocontinue(2).6行6列迷宫矩阵:*1"C:\Document5and虫"ing矶.Adniini血日tor虞面谜宫卩血..■回密迷宫的行数:F入迷宫的列数:j第1行：00011a1111出第6仃16511

0011001009,3,2X6,3,1X6,4,1X6,5,0>essanpheytocontinue(3).没路的情况:2•分析：(1).输入所要建立的迷宫的行列数;(2).输入矩阵，0表通道，1表示墙；.从入口(1,1)进入先判断东面是否为通道，若通则进入，否则在判断下一个方向(1,2,3,4表是东南西北，起始为东按顺时针转动)。如4行4列矩阵，入口(1,1)东面为通道进入(1,2)；东面仍为通道进入(1,3)；东面不通，往南，南通进入(2,3),东面为通进入(2,4)；4个方向都不通返回(2,3)；且往南不通，在往西，通进入(2,3)……五、总结：1．收获：通过本试验我对链栈有了更深入的了解，对链栈的使用更加熟练。让我深知要想熟练掌握一门算法大量的编程训练是必不可少的，在编写的过程中我们更容易发现问题所在，对算法有更深会的理解。2．遇到问题：在将算法应用到迷宫问题过程中，遇到了不少问题，反复琢磨和查找相关书籍才将其解决。首先，是如何用链栈储存调用迷宫矩阵中的相关坐标；再次，是判断方向的转变使其不会重复走过的路经；最后，当所行路经不通时如何退出返回到迁移结点。3．从一个小的迷宫问题，引出了许多知识，这种探索式的学习是很有重要意义的。从迷宫基本的操作到链栈的运用和理解，提高了我程序的调试能力和对算法的深入思考，加深了对数据结构的的认识。六、附录：源程序清单:#include<iostream>usingnamespacestd;#definemaxsize20typedefstruct〃定义迷宫{intarry[maxsize][maxsize];〃二维数组存放迷宫信息intmax_x,max_y;//迷宫的行数和和列数}sd;typedefstructpoint{intvex_x,vex_y;〃结点的横纵坐标structpoint*next;//指向下一个结点intdirection;//下一个结点的方向}Point;sdcreat()//创建迷宫{inti,j;sda;cout<<"请输入迷宫的行数："；cin>>a.max_x;cout<<"请输入迷宫的列数："；cin>>a.max_y;for(i=1;i<=a.max_x;i++){cout<<"输出第"<<i<<"行：";for(j=1;j<=a.max_y;j++)cin>>a.arry[i][j];}cout<<endl;returna;}intfound(intx,inty,Point*head){Point*p=head;while(p!=NULL){if(x==p->vex_x&&y==p->vex_y)return1;p=p->next;}return0;}Point*secret(sda)//迷宫函数，返回一条通路或者NULL{Point*top,*p;//top为栈的栈顶指针intj,find,x,y;p=(Point*)malloc(sizeof(Point));p->next=NULL;p->vex_x=1;p->vex_y=1;//p->next=NULL;top=p;j=1；//j为方向，1,2,3,4分别为东，南，西，北do{while(j<=4){find=0;//find判断是否有符合条件的结点，若有为1,没有为0・x=p->vex_x;y=p->vex_y;switch(j){case1:if(y+1<=a.max_x&&!a.arry[x][y+1]&&!found(x,y+1,top))//若纵坐标加1后，在迷宫范围内，当前结点为0，当店结点没有在链栈中出现，则当前结点加入链栈{p=(Point*)malloc(sizeof(Point));p->vex_x=x;p->vex_y=y+1;p->next=top;top->direction=j;〃当前结点在上一个结点的方向top=p;find=1;}break;case2:if(x+1<=a.max_x&&!a.arry[x+1][y]&&!found(x+1,y,top)){p=(Point*)malloc(sizeof(Point));p->vex_x=x+1;p->vex_y=y;p->next=top;top->direction=j;top=p;find=1;}break;case3:if(y-1>=1&&!a.arry[x][y-1]&&!found(x,y-1,top)){p=(Point*)malloc(sizeof(Point));p->vex_x=x;p->vex_y=y-1;p->next=top;top->direction=j;top=p;find=1;}break;case4:if(x-1<=1&&!a.arry[x-1][y]&&!found(x-1,y,top)){p=(Point*)malloc(sizeof(Point));p->vex_x=x-1;p->vex_y=y;p->next=top;top->direction=j;top=p;find=1;}break;}if(find==1)〃若找到符合条件的结点，则j赋1,然后退出while循环{j=1;break;}else j++;〃若没有，j加1}f(j>4)//4个方向都找不到符合条件的结点时.{if(top->next!=NULL)〃若top不空，则出栈，方向j加1{p=p->next;top=p;//使栈顶结点指向前一个节点,原节点删除j=top->direction+1;top->direction=j;}elsereturnNULL;//若top空，则返回NULL}}while(top->vex_x!=a.max_x||top->vex_y!=a.max_y);//若果当前结点不是出口，则继续进行do循环returntop;}voiddisp(Point*po)〃输出结果{inti=0,top=0;Point*stack[maxsize];if(po==NULL)cout<<"没路"<<endl;else{while(po!=NULL)〃通过一个栈将链栈逆序{stack[top++]=po;po=po->next;}cout<<"迷宫通道如下："<<endl;while(top>1){top--;cout<<"("<<sta