欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

C语言数据结构之迷宫求解问题

来源:本站原创|时间:2020-01-10|栏目:C语言|点击:

现在网上各种对于迷宫的求解,版本多的数不胜数。本人小白一枚,贴上自己对迷宫的求解这个小项目,自己写的。望能帮助一些同样有困难的人,毕竟我当时费解了好一会儿时间呢。

首先,先标明对于迷宫求解这个项目,首先我提出自己的思路,利用“穷举求解”的方法(严蔚敏老师数据结构一书中提到,一开始不知方法其名。)其实简单来说就是一条路一条路去试,当然不能随便试,我的方法是按照从入口出发,顺一个方向向前探索,走得通就继续向前走;否则留下标记沿原路退回并换一个方向继续探索,直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构(对于栈并没有详细阐述)。

//调用头文件
#ifndef AFXSTD_H
#define AFXSTD_H 
 
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
using namespace std; 
// cout; cin;C++的输入输出
#endif
//迷宫的结构体的创建
#ifndef MAZE_H
#define MAZE_H
 
#define ROWSIZE 10  //迷宫大小
#define COLSIZE 10
#define Reachable 0 //可以到达的结点
#define Bar   1 //障碍物
#define Foot  2 //足迹
#define Mark  3 //不可通路标记
typedef int MapType[ROWSIZE][COLSIZE]; // 地图类型 
 
typedef struct 
{
 int row;// x
 int col;// y;
}PosType;     //坐标结构体
 
typedef struct
{
 int ord;   //通道块在道路上的序号
 PosType seat;  //小人坐标
 int di; // 方向 // 1 2 3 4
}MElemType;  //试迷宫小人的结构
 
typedef MElemType SElemType; // 和stack 关联
 
 
 
bool MazePass(MapType maze,PosType curpos);
void FootPrint(MapType maze,PosType curpos);  //足迹打印
PosType NextPos(PosType curpos,int di);    //下一个位置
void MarkPrint(MapType maze,PosType curpos);   //打印不可通标记
bool MazePath(MapType maze,PosType start,PosType end); //迷宫解谜核心
void PrintMap(MapType maze);       //打印地图
 
 
#endif
//栈的结构体
#include"Maze.h"
#ifndef SEQSTACK_H
#define SEQSTACK_H
#define STACKSIZE 100
 
//typedef int SElemType;
 
struct SeqStack
{
 SElemType *data;
 int maxsize;
 int top;
};
 
void Init_Stack(SeqStack &st);
void Destroy_Stack(SeqStack &st);
void Stack_Clear(SeqStack &st);
bool Stack_Empty(SeqStack &st);
bool Stack_Full(SeqStack &st);
int Stack_Size(SeqStack &st);
bool Stack_Push(SeqStack &st,const SElemType &x);
bool Stack_Pop(SeqStack &st, SElemType &x);
 
SElemType GetTop(SeqStack &st);
void Pop(SeqStack &st);
 
#endif

以上是头文件的创建,和结构体的创建,现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑,切记切记!!

现在贴出函数的代码,解释我会尽力都写清楚。(栈的问题我后续会重新再仔细阐述的,这次的重点在于迷宫的求解,所以直接贴出栈的详细代码,望谅解。)

//这里是栈的实现代码
#include"AfxStd.h"
#include"Stack.h"
 
bool Stack_Resize(SeqStack &st)
{
 SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2);
 if(NULL == s) return false;
 for(int i = 0;i<= st.top;++i)
 {
 s[i] = st.data[i];
 }
 free(st.data);
 st.data = s;
 st.maxsize = st.maxsize * 2;
 return true;
}
void Init_Stack(SeqStack &st)
{
 st.maxsize = STACKSIZE;
 st.top = -1;
 st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize);
 if(NULL == st.data)
 {
 exit(0);
 }
}
void Destroy_Stack(SeqStack &st)
{
 free(st.data);
 st.data = NULL;
 st.maxsize = 0;
 st.top = -1;
}
 
void Stack_Clear(SeqStack &st)
{
 st.top = -1;
}
bool Stack_Empty(SeqStack &st)
{
 return Stack_Size(st) == 0;
}
bool Stack_Full(SeqStack &st)
{
 return Stack_Size(st) == st.maxsize;
}
 
int Stack_Size(SeqStack &st)
{
 return st.top + 1;
}
 
bool Stack_Push(SeqStack &st,const SElemType &x)
{
 if(Stack_Full(st) && ! Stack_Resize(st))
 {
 return false;
 }
 st.data[++st.top] = x;
 return true;
}
bool Stack_Pop(SeqStack &st, SElemType &x)
{
 if(Stack_Empty(st))
 {
 return false;
 }
 x = st.data[st.top--];
 return true;
}
//调用前面创建的头文件
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"
 
 
/////////////////////////////////////////////////
 
bool MazePass(MapType maze,PosType curpos) //判断是否可以通过
{
 return maze[curpos.row][curpos.col] == Reachable; //判断当前结点是否能通过
}
void FootPrint(MapType maze,PosType curpos)  //打印足迹 
{
 maze[curpos.row][curpos.col] = Foot;  
}
PosType NextPos(PosType curpos,int di)    //对下一个结点方向的判断
{
 switch(di)
 {
 case 1: curpos.row+=1; break;// 1
 case 2: curpos.col-=1; break;// 2
 case 3: curpos.row-=1; break;// 3
 case 4: curpos.col+=1; break;// 4
 }
 return curpos;
}
void MarkPrint(MapType maze,PosType curpos)   //不能通过的结点留下不能通过的标记
{
 maze[curpos.row][curpos.col] = Mark;
}
 
bool MazePath(MapType maze,PosType start,PosType end)//(核心)迷宫解谜
{
 bool res = false;       //定义一个res参数为布尔型
 PosType curpos = start;     //初始当前位置为入口
 int curstep = 1;        // 初始探索方向为1
 SeqStack st;          //路径存储栈
 MElemType e;          //初始探索小人
 Init_Stack(st);         //初始化栈
 do{
 if(MazePass(maze,curpos))     //当前位置可通过,即是未曾走到过的坐标
 {
 FootPrint(maze,curpos);    //留下足迹
 e.di = 1, e.seat = curpos,e.ord = curstep++;
 Stack_Push(st,e);      //加入路径中
 if(curpos.row == end.row && curpos.col == end.col)
 {
 res = true;
 break;
 }        //到达终点
 curpos = NextPos(curpos,1);  //探索下一位置
 }
 else
 {
 if(!Stack_Empty(st))    //当前位置不能通过
 {
 Stack_Pop(st,e);
 while(e.di == 4 && !Stack_Empty(st))
 {
  MarkPrint(maze,e.seat);  
  Stack_Pop(st,e);    // 留下不能通过的标记,并退回一步
 }
 if(e.di < 4)
 {
  e.di+=1;     // 换下一个方向探索
  Stack_Push(st,e);   //再次记录路径
  curpos = NextPos(e.seat,e.di); // 当前位置设为新方向的相邻块
 }
 }
 }
 }while(!Stack_Empty(st));  //当栈空摧毁栈,返回失败参数
 Destroy_Stack(st);    
 return res;
}
void PrintMap(MapType maze)   //打印地图
{
 for(int i = 0;i<ROWSIZE;++i)
 {
 for(int j = 0;j<COLSIZE;++j)
 {
 printf("%2d",maze[i][j]);
 }
 printf("\n");
 }
 printf("\n");
}

以上就是迷宫的详细解释,希望能帮助到大家。后面再添加我的测试文件。

#include"AfxStd.h"
#include"Maze.h"
 
int main()
{
 MapType maze ={      //一开始地图的创建
 {1,1,1,1,1,1,1,1,1,1},
 {1,0,1,1,1,1,1,1,1,1},
 {1,0,0,0,0,0,0,0,0,1},
 {1,0,0,0,1,1,1,1,0,1},
 {1,0,0,0,1,1,1,1,0,1},
 {1,0,1,1,1,1,0,0,0,1},
 {1,0,1,1,1,1,1,1,1,1},
 {1,0,0,0,0,0,0,1,1,1},
 {1,0,1,1,1,1,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1},
 };
 PosType start={1,1},end={8,8};
 PrintMap(maze);      //打印初始地图
 MazePath(maze,start,end);
 PrintMap(maze);      //打印迷宫解法
 return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

上一篇:详解C++ 动态库导出函数名乱码及解决

栏    目:C语言

下一篇:C语言实现小型电子词典

本文标题:C语言数据结构之迷宫求解问题

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/395.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有