采用了以栈为基础,在栈的基础上进行迷宫的求解,用Stack和Maze两个文件来实现功能。
Stack.h的实现如下:
#pragma once
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
typedef int DirectiveType; //下一个通道方向
#define RANGE 100 //迷宫大小
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//------------ 栈的顺序存储实现 ------------------------------
typedef struct
{
int row; //迷宫中的行
int col; //迷宫中的列
}PosType; //坐标(row,col)
typedef struct
{
int step; //当前位置在路径上的"序号"
PosType seat; //当前的坐标位置
DirectiveType di; //往下一个坐标位置的方向
}SElemType; //栈的元素类型
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
bool InitStack(SqStack &s); //栈的创建,即构造一个空栈
bool GetTop(SqStack s,SElemType &e); //如栈不为空,用e返回栈顶元素
bool Push(SqStack &s, SElemType e); //在栈中插入元素
bool Pop(SqStack &s, SElemType &e); //删除栈顶元素
bool StackEmpty(SqStack s); //判断栈为不为空
bool DestoryStack(SqStack &s); //销毁栈
Stack.cpp实现如下:
#include "Stack.h"
#include "Maze.h"
bool InitStack(SqStack &s)
{ //栈的初始化
s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!s.base)
{
exit(-2);
}
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return true;
}
bool GetTop(SqStack s, SElemType &e )
{
if( s.top == s.base)
{
return false;
}
e = *(s.top-1);
return true;
}
bool Push(SqStack &s, SElemType e)
{
if(s.top-s.base >= s.stacksize)
{ //栈满,追加存储空间
s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!s.base)
{
exit(-2);
}
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*s.top++ = e;
return true;
}
bool Pop(SqStack &s, SElemType &e)
{
if(s.top==s.base)
return false;
e = * --s.top;
return true;
}
bool StackEmpty(SqStack s)
{
return s.base == s.top;
}
bool DestoryStack(SqStack &s)
{
free(&s);
return true;
}
Maze.h实现如下:
typedef int DirectiveType; //下一个通道方向
#define RANGE 100 //迷宫大小
#define ROW 10 //迷宫的行数
#define COL 10 //迷宫的列数
typedef struct
{
int m,n;
int arr[RANGE][RANGE];
}MazeType;
bool InitMaze(MazeType &maze, int a[ROW][COL], int row, int col);//初始化迷宫
bool Pass(MazeType maze,PosType curpos); //判断能否通过
bool FootPrint(MazeType &maze,PosType curpos); //留下足迹
bool MarkPrint(MazeType &maze,PosType curpos); //留下不能通过的标记
PosType NextPos(PosType curpos, DirectiveType di); //curpos当前位置
//返回当前节点的下一节点
bool PosEqual(PosType pos1, PosType pos2); //判断两节点是否相等
void PrintMaze(MazeType maze,int row,int col);
bool MazePath(MazeType &maze,PosType start, PosType end); //求解一条路径
Maze.cpp实现如下:
#include "Stack.h"
#include "Maze.h"
bool InitMaze(MazeType &maze, int a[ROW][COL], int row, int col)
{
int i,j;//设置迷宫maze的初值,包括加上边缘一圈的值
for(i=1;i<row-1;i++)
{
for(j=1;j<col-1;j++)
{
maze.arr[j] = a[j];
}
}
//加上围墙
for(j=0;j<row;j++)
{
maze.arr[0][j] = maze.arr[row-1][j]=1;
}
for(i=0;i<col;i++)
{
maze.arr[0] = maze.arr[col-1]=1;
}
return true;
}
bool Pass(MazeType maze,PosType curpos)
{ //判断当前节点是否通过
if(maze.arr[curpos.row][curpos.col] == 0)
{
return true;
}
else
{
return false;
}
}
bool FootPrint(MazeType &maze,PosType curpos)
{ //留下足迹
maze.arr[curpos.row][curpos.col]=2;//走过且走得通
return true;
}
bool MarkPrint(MazeType &maze,PosType curpos)
{//留下不能通过的标记
maze.arr[curpos.row][curpos.col]=3; //走过但走不通
return true;
}
SElemType CreateSElem(int step, PosType pos, int di)
{
SElemType e;
e.step = step;
e.seat = pos;
e.di = di;
return e;
}
PosType NextPos(PosType curpos, DirectiveType di)//curpos当前位置
{//返回当前节点的下一节点
PosType pos = curpos;
switch(di)
{
case 1: //右
pos.col++;
break;
case 2: //下
pos.row++;
break;
case 3: //左
pos.col--;
break;
case 4: //上
pos.row--;
break;
}
return pos;
}
bool PosEqual(PosType pos1, PosType pos2)
{//判断是不是出口
if(pos1.row==pos2.row && pos1.col==pos2.col)
{
return true;
}
else
{
return false;
}
}
void PrintMaze(MazeType maze,int row,int col)
{//打印路径
int i,j;
printf(" ");
for(i=0;i<col;i++)//打印列数名
{
printf("%d ",i);
}
printf("\n");
for(i=0;i<row;i++)
{
printf("%d ",i);//打印行数名
for(j=0;j<col;j++)
{
switch(maze.arr[j])
{
case 0:
printf(" ");//没走过,但是通路
break;
case 1:
printf("# ");//障碍
break;
case 2:
printf("* ");//走过且走得通
break;
case 3:
printf("@ ");//走过但走不通
break;
default:
break;
}
}
printf("\n");
}
}
bool MazePath(MazeType &maze, PosType start, PosType end)
{ //求解迷宫maze中,从入口start到出口end的一条路径
SqStack s;
SElemType e;
InitStack(s);
PosType curpos = start;
int curstep = 1; //探索第一步
do{
if( Pass(maze,curpos) )
{ //如果当前位置可以通过,即是未曾走到的通道块
FootPrint(maze,curpos); //留下足迹
e = CreateSElem(curstep,curpos,1); //创建元素
Push(s,e);
if( PosEqual(curpos,end) )
{
return true;
}
curpos=NextPos(curpos,1); //获得下一节点
curstep++; //探索下一步
}
else{ //当前位置不能通过
if(!StackEmpty(s))
{
Pop(s,e);
while(e.di==4 && !StackEmpty(s) ) //找寻了四个方向
{
MarkPrint(maze,e.seat);
Pop(s,e); //留下不能通过的标记,并退回一步
}
if(e.di<4)
{
e.di++; //换一个方向探索
Push(s,e);
curpos = NextPos(e.seat,e.di); //设定当前位置是该方向上的相邻块
}
}
}
}while(!StackEmpty(s));
return false;
}
主测试函数如下:
#include "Stack.h"
#include "Maze.h"
void main()
{
char cmd;//命令
int i,j;
PosType start,end;
MazeType maze;
int a[ROW][COL] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,0,0,1},
{1,0,0,1,1,1,0,0,1,1},
{1,1,0,0,0,0,0,0,1,1},
{1,1,0,1,1,1,1,0,1,1},
{1,1,0,0,1,1,1,0,1,1},
{1,1,1,0,1,1,1,0,0,1},
{1,1,1,0,0,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
printf("\n----------原始迷宫(加外围围墙)(0 表示通路,1 表示障碍)---------\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ",a[j]);
}
printf("\n");
}
InitMaze(maze,a,ROW,COL);
do{
int flag=0;//是不是越界de标志。0即没越界执行下一步,1即循环再次输入
do{
printf("\n输入迷宫入口坐标( <0,0>到<9,9>之间 ): ");
scanf("%d,%d",&start.row,&start.col);
if(start.col>COL-1 || start.row>ROW-1 ||start.col<0||start.row<0)
{
printf("越界!");
flag=1;
}
else
{
flag=0;
}
}while(flag);
do{
printf("输入迷宫出口坐标( <0,0>到<9,9>之间 ): ");
scanf("%d,%d",&end.row , &end.col);
if( end.col>COL-1 || end.row>ROW-1 ||end.col<0||end.row<0)
{
printf("越界!\n");
flag=1;
}
else
{
flag=0;
}
}while(flag);
if(MazePath(maze,start,end))//找到一条路径
{
printf("\n---------从当前入口到出口有通路 * 组成的路径----------\n");
PrintMaze(maze,ROW,COL);
}
else
{
printf("\n---------从入口到出口没有通路!-----\n");
}
printf("\n 需要继续吗?: ");
scanf(" %c",&cmd);
}while(cmd=='Y'||cmd=='y');
}
源码来自 算法源码:
http://www.eyesourcecode.com/forum-algorithm-1.html
- 大小: 11.9 KB
分享到:
相关推荐
迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解...
迷宫求解课设
vc++编写的迷宫求解程序 课程名称:数据结构课程设计(A) 课程编号:L11008 一、 实现功能: 输入迷宫的行数(假设为M)和列数(假设是N),单击创建迷宫按钮,随机生成一个M行N列的迷宫,单击显示路径按钮,如果...
c语言数据结构迷宫求解 严蔚敏版 使用栈和结构体
课程设计之迷宫求解问题,绝对物有说值!............
初学数据结构和C语言,尝试实现了迷宫求解问题。代码组织比较差,改进的地方也有很多,博君一乐而已。希望能够帮助到别人
迷宫求解MFC代码
题目 3 迷宫求解 1、问题描述 可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出。 2、要求 在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、源程序、测试数据...
数据结构 迷宫求解 C++ 数据结构 迷宫求解 C++ 数据结构 迷宫求解 C++
c#迷宫求解算法 根据严蔚敏c得来 c#迷宫求解算法
数据结构里的迷宫求解。严蔚敏书里的迷宫求解,是用C语言写的,简单易懂。迷宫随机生成。
迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++
迷宫求解(8个方向),INPUT.TXT保存输入迷宫,OUTPUT.TXT保存输出迷宫路径
迷宫求解 数据结构 地方
迷宫求解算法,数据结构c语言,自己写的。
很好的一个迷宫求解程序。此程序用0和1来随机产生一个迷宫,然后用栈的基本操作来实现迷宫的求解。很适合用于数据结构栈应用的课程设计。
数据结构 课程设计 迷宫求解课程设计 数据结构 课程设计 迷宫求解课程设计 数据结构 课程设计 迷宫求解课程设计
数据结构(严蔚敏)中迷宫求解的代码,C语言写的