数据结构迷宫问题.docx

《数据结构迷宫问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计题目8：迷宫问题一、设计目的1．掌握栈的概念和运算。2.掌握队列的概念和运算。二、设计内容和要求问题描述：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。[测试数据]迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。12345678001000100010001000001101011100100001000001000101011110011100010111000000程序代码#includeusingnamespacest

2、d;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10structPoint{intx;inty;ints;};classStack{private:Point*contain;inttop;intstacksize;public:Stack();~Stack();voidClearStack();boolStackEmpty();intStackLength();voidGetTop(Point&e);voidPush(Pointe);voidPop(Point&e);};Stack::Stack(){top=-1;con

3、tain=newPoint[STACK_INIT_SIZE];stacksize=STACK_INIT_SIZE;}Stack::~Stack(){delete[]contain;}voidStack::ClearStack(){top=-1;}boolStack::StackEmpty(){if(top>-1)returnfalse;elsereturntrue;}intStack::StackLength(){returntop+1;}voidStack::GetTop(Point&e){if(top!=-1)e=contain[top];}voidStack::P

4、ush(Pointe){if(top==stacksize-1){Point*temp=newPoint[stacksize+STACKINCREMENT];for(inti=0;i-1){e=contain[top];top--;}}//全局变量intmap[22]

5、[22];Stacks;intp=0;boolc_map(Pointa,Pointb){Pointc;if(a.x==b.x&&a.y==b.y)p=1;if(p)returntrue;if(map[a.x][a.y]==0){s.Push(a);map[a.x][a.y]=5;if(a.s!=0){c.s=3;c.x=a.x;c.y=a.y+1;c_map(c,b);}if(a.s!=1){c.s=2;c.x=a.x+1;c.y=a.y;c_map(c,b);}if(a.s!=2){c.s=1;c.x=a.x-1;c.y=a.y;c_map(c,b);}if(a.s!

6、=3){c.s=0;c.x=a.x;c.y=a.y-1;c_map(c,b);}if(!p){s.Pop(c);map[c.x][c.y]=0;}}if(p)returntrue;returnfalse;}intmain(){inti,j;intm=9,n=8;charc;intMap[20][20]={{0,0,1,0,0,0,1,0},{0,0,1,0,0,0,1,0},{0,0,0,0,1,1,0,1},{0,1,1,1,0,0,1,0},{0,0,0,1,0,0,0,0},{0,1,0,0,0,1,0,1},{0,1,1,1,1,0,0,1},{1,1,0,0,

7、0,1,0,1},{1,1,0,0,0,0,0,0}};Pointa,b;a.x=1;a.y=1;b.x=9;b.y=8;cout<<"1.输入迷宫2.默认迷宫"<>c;if(c=='1'){cout<<"请输入行数："<>m;cout<<"请输入列数："<>n;cout<<"请输入迷宫："<>Map[i][j];cout<<"请输入起点坐标：(原点坐标为(1,1))"<>