`

课程设计——迷宫问题（C++）

 
阅读更多
迷宫问题
1设计目的、要求
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
基本要求：
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。
（1）编写递归形式的算法，求得迷宫中所有可能的通路；
（2）以方阵形式输出迷宫及其通路。
2设计原理
主要采取三大模块：主程序模块、栈模块和迷宫模块
      栈模块：实现迷宫数据的抽象化和对迷宫数据的处理；
      迷宫模块：实现迷宫数据抽象类型；
主程序模块：初始化迷宫模块。
3采用软件、设备
   Microsoft  Visual  C++  6.0   微型电子计算机
4设计内容
1、迷宫模块：
以二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]和Maze[i][n+1] (0<=i<=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍，限定迷宫的大小m,n<=10。其中迷宫的入口位置和出口位置可由用户随时设定。
1.坐标位置类型: 
struct PosType /* 迷宫坐标位置类型 */
 {
   int x; /* 行值 */
   int y; /* 列值 */
 };

2.迷宫类型: 
#define MAXLENGTH 25 /* 设迷宫的最大行列为25 */
 typedef int MazeType[MAXLENGTH][MAXLENGTH];
     3.记录坐标的三个一元数组：
  int a[MAXLENGTH];
  int b[MAXLENGTH];
 int c[MAXLENGTH];
    2、栈模块：
1.栈类型SElemType:
struct SElemType/* 栈的元素类型 */
 {
   int ord; /* 通道块在路径上的＂序号＂ */
   PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */
   int di; /* 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) */
 };
      2.构造一个栈SElmType:
       struct SqStack   //SqStack
      {
          SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
         SElemType *top; /* 栈顶指针 */
         int stacksize; /* 当前已分配的存储空间，以元素为单位 */
      }; /* 顺序栈 */
     其中基本操作如下：
栈的初始化：
bool InitStack(SqStack *S)
 { /* 构造一个空栈S */
   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!(*S).base)
     exit(1); /* 存储分配失败 */
   (*S).top=(*S).base;
   (*S).stacksize=STACK_INIT_SIZE;
   return true;
 }
元素进栈：
bool Push(SqStack *S,SElemType e)
 { /* 插入元素e为新的栈顶元素 */
   if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
   {
     (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
     if(!(*S).base)
       exit(1); /* 存储分配失败 */
     (*S).top=(*S).base+(*S).stacksize;
     (*S).stacksize+=STACKINCREMENT;
   }
   *((*S).top)++=e;
   return true;
 }
判断栈是否为空：
 bool StackEmpty(SqStack S)
 { /* 若栈S为空栈，则返回true，否则返回false*/
   if(S.top==S.base)
     return true;
   else
     return false;
 }
删除栈顶元素使之为空：
bool Pop(SqStack *S,SElemType *e)
 { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回true；否则返回false */
   if((*S).top==(*S).base)
     return false;
   *e=*--(*S).top;
   return true;
 }
寻找公共路径的思想图如下：
设定当前为出始值的入口：
do{
   若当前位置可通，
   则{将当前位置插入栈顶；
      若该位置是出口位置，则结束；
      否则切换当前位置的东邻方块为新的当前位置；
     }
   否则{
        若栈不空且栈顶位置尚有其他方向未被探索，
          则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一邻块；
        若栈不为空且栈顶位置的四周均不可通，
          则{删除栈顶位置；
             若栈不为空，则重新测试新的栈顶位置，
                 直至找到一个可通的相邻块或出栈至栈空；
             }
 }
bool MazePath(PosType start,PosType end) /* 算法3.3 */
 { /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */
   /* 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */
   SqStack S;
   PosType curpos;
   SElemType e;
   InitStack(&S);
   curpos=start;
   do
   {
     if(Pass(curpos))
     { /* 当前位置可以通过，即是未曾走到过的通道块 */
       FootPrint(curpos); /* 留下足迹 */
       e.ord=curstep;
       a[curstep]=e.seat.x=curpos.x;
       b[curstep]=e.seat.y=curpos.y;
       c[curstep]=e.di=0;
       Push(&S,e); /* 入栈当前位置及状态 */
       curstep++; /* 足迹加1 */
       if(curpos.x==end.x&&curpos.y==end.y) /* 到达终点(出口) */
         return true;
       curpos=NextPos(curpos,e.di);
     }
     else
     { /* 当前位置不能通过 */
       if(!StackEmpty(S))
       {
         Pop(&S,&e); /* 退栈到前一位置 */
         curstep--;
         while((e.di==3) && (!StackEmpty(S))) /* 前一位置处于最后一个方向(北) */
         {
           MarkPrint(e.seat); /* 留下不能通过的标记(-1) */
           Pop(&S,&e); /* 退回一步 */
           curstep--;
         }
         if(e.di<3) /* 没到最后一个方向(北) */
         {
           e.di++; /* 换下一个方向探索 */
           Push(&S,e);
       a[curstep]=e.seat.x=curpos.x;
       b[curstep]=e.seat.y=curpos.y;
       c[curstep]=e.di;
           curstep++;
           curpos=NextPos(e.seat,e.di); /* 设定当前位置是该新方向上的相邻块 */
         }
       }
     }
   }while(!StackEmpty(S));
   return false;
 }3、主程序模块：
Void  main()
{
Do
{
   接受命令；
处理命令；
}while(命令!=“退出”)
}
程序如下：
void main()
 {
   PosType begin,end;
   int i,j,x,y,x1,y1;
   cout<<"请输入迷宫的行数,列数(包括外墙)：";
   cin>>x>>y;
   for(i=0;i<x;i++) /* 定义周边值为1(同墙) */
   {
     m[0][i]=1; /* 行周边 */
     m[x-1][i]=1;
   }
   for(j=1;j<y-1;j++)
   {
     m[j][0]=1; /* 列周边 */
     m[j][y-1]=1;
   }
   for(i=1;i<x-1;i++)
     for(j=1;j<y-1;j++)
       m[i][j]=0; /* 定义通道初值为0 */
   cout<<"请输入迷宫内墙单元数：";
   cin>>j;
   cout<<"请依次输入迷宫内墙每个单元的行数,列数："<<endl;
   for(i=1;i<=j;i++)
   {
    cin>>x1>>y1;
     m[x1][y1]=1; /* 定义墙的值为1 */
   }
   cout<<"迷宫结构如下:"<<endl;
   Print(x,y);
   cout<<"请输入起点的行数,列数：";
   cin>>begin.x>>begin.y;
   cout<<"请输入终点的行数,列数：";
   cin>>end.x>>end.y;
   if(MazePath(begin,end)) /* 求得一条通路 */
   {
    cout<<"此迷宫从入口到出口的一条路径如下:"<<endl;
       Print(x,y); /* 输出此通路 */
    cout<<"迷宫所走过路径的坐标及方向(0代表右,1代表下,2代表左,3代表上):"<<endl;
    for(i=1;i<curstep;i++)
    cout<<"("<<a[i]<<","<<b[i]<<","<<c[i]<<")"<<endl;
   }
   else
    cout<<"此迷宫没有从入口到出口的路径"<<endl;
}
5原始程序、数据
输入迷宫的行数和列数8,8；输入迷宫中障碍数17个；输入障碍物所在的坐标（1,2），（1,3），（1,4），(1,5),(1,6),(3,2),(3,3),（3,4）,(3,5),(3,6)（4,4）,(5,1),(5,2),（5,5），(6,1),(6,2),（6,3）。设置起点和终点分别为(1,1)和(6,6)。得到最终走出的路径和其走过路径的坐标及方向。
6结果分析
 
7参考文献
《数据结构实用教程》          清华大学出版社
《数据结构习题集》            清华大学出版社
8附录：
#include<iostream>
using namespace std;
struct PosType /* 迷宫坐标位置类型 */
 {
   int x; /* 行值 */
   int y; /* 列值 */
 };
#define MAXLENGTH 25 /* 设迷宫的最大行列为25 */
 typedef int MazeType[MAXLENGTH][MAXLENGTH]; /* 迷宫数组[行][列] */
 /* 全局变量 */
 MazeType m; /* 迷宫数组 */
 int curstep=1; /* 当前足迹,初值为1 */
 int a[MAXLENGTH];
 int b[MAXLENGTH];
 int c[MAXLENGTH];
 struct SElemType/* 栈的元素类型 */
 {
   int ord; /* 通道块在路径上的＂序号＂ */
   PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */
   int di; /* 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) */
 };
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
 #define STACKINCREMENT 2 /* 存储空间分配增量 */
 struct SqStack   //SqStack
 {
   SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
   SElemType *top; /* 栈顶指针 */
   int stacksize; /* 当前已分配的存储空间，以元素为单位 */
 }; /* 顺序栈 */
 bool Pass(PosType b)
 { /* 当迷宫m的b点的序号为1(可通过路径)，return true, 否则，return false。 */
   if(m[b.x][b.y]==1)
     return true;
   else
     return false;
 }
void FootPrint(PosType a)
 { /* 使迷宫m的a点的序号变为足迹(curstep) */
   m[a.x][a.y]=curstep;
 }
PosType NextPos(PosType c,int di)
 { /* 根据当前位置及移动方向，返回下一位置 */
   PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; /* {行增量,列增量} */
   /* 移动方向,依次为东南西北 */
   c.x+=direc[di].x;
   c.y+=direc[di].y;
   return c;
 }

 void MarkPrint(PosType b)
 { /* 使迷宫m的b点的序号变为-1(不能通过的路径) */
   m[b.x][b.y]=-1;
 }
bool InitStack(SqStack *S)
 { /* 构造一个空栈S */
   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!(*S).base)
     exit(1); /* 存储分配失败 */
   (*S).top=(*S).base;
   (*S).stacksize=STACK_INIT_SIZE;
   return true;
 }
bool Push(SqStack *S,SElemType e)
 { /* 插入元素e为新的栈顶元素 */
   if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
   {
     (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
     if(!(*S).base)
       exit(1); /* 存储分配失败 */
     (*S).top=(*S).base+(*S).stacksize;
     (*S).stacksize+=STACKINCREMENT;
   }
   *((*S).top)++=e;
   return true;
 }
 bool StackEmpty(SqStack S)
 { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
   if(S.top==S.base)
     return true;
   else
     return false;
 }
bool Pop(SqStack *S,SElemType *e)
 { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
   if((*S).top==(*S).base)
     return false;
   *e=*--(*S).top;
   return true;
 }
bool MazePath(PosType start,PosType end) /* 算法3.3 */
 { /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */
   /* 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */
   SqStack S;
   PosType curpos;
   SElemType e;
   InitStack(&S);
   curpos=start;
   do
   {
     if(Pass(curpos))
     { /* 当前位置可以通过，即是未曾走到过的通道块 */
       FootPrint(curpos); /* 留下足迹 */
       e.ord=curstep;
       a[curstep]=e.seat.x=curpos.x;
       b[curstep]=e.seat.y=curpos.y;
       c[curstep]=e.di=0;
       Push(&S,e); /* 入栈当前位置及状态 */
       curstep++; /* 足迹加1 */
       if(curpos.x==end.x&&curpos.y==end.y) /* 到达终点(出口) */
         return true;
       curpos=NextPos(curpos,e.di);
     }
     else
     { /* 当前位置不能通过 */
       if(!StackEmpty(S))
       {
         Pop(&S,&e); /* 退栈到前一位置 */
         curstep--;
         while((e.di==3) && (!StackEmpty(S))) /* 前一位置处于最后一个方向(北) */
         {
           MarkPrint(e.seat); /* 留下不能通过的标记(-1) */
           Pop(&S,&e); /* 退回一步 */
           curstep--;
         }
         if(e.di<3) /* 没到最后一个方向(北) */
         {
           e.di++; /* 换下一个方向探索 */
           Push(&S,e);
       a[curstep]=e.seat.x=curpos.x;
       b[curstep]=e.seat.y=curpos.y;
       c[curstep]=e.di;
           curstep++;
           curpos=NextPos(e.seat,e.di); /* 设定当前位置是该新方向上的相邻块 */
         }
       }
     }
   }while(!StackEmpty(S));
   return false;
 }

 void Print(int x,int y)
 { /* 输出迷宫的解 */
   int i,j;
   for(i=0;i<x;i++)
   {
     for(j=0;j<y;j++)
   cout<<'\t'<<m[i][j];
     cout<<endl;
   }
 }
//stack.h
 
void main()
 {
   PosType begin,end;
   int i,j,x,y,x1,y1;
   cout<<"请输入迷宫的行数,列数(包括外墙)：";
   cin>>x>>y;
   for(i=0;i<x;i++) /* 定义周边值为0(同墙) */
   {
     m[0][i]=1; /* 行周边 */
     m[x-1][i]=1;
   }
   for(j=1;j<y-1;j++)
   {
     m[j][0]=1; /* 列周边 */
     m[j][y-1]=1;
   }
   for(i=1;i<x-1;i++)
     for(j=1;j<y-1;j++)
       m[i][j]=1; /* 定义通道初值为1 */
   cout<<"请输入迷宫内墙单元数：";
   cin>>j;
   cout<<"请依次输入迷宫内墙每个单元的行数,列数："<<endl;
   for(i=1;i<=j;i++)
   {
    cin>>x1>>y1;
     m[x1][y1]=0; /* 定义墙的值为0 */
   }
   cout<<"迷宫结构如下:"<<endl;
   Print(x,y);
   cout<<"请输入起点的行数,列数：";
   cin>>begin.x>>begin.y;
   cout<<"请输入终点的行数,列数：";
   cin>>end.x>>end.y;
   if(MazePath(begin,end)) /* 求得一条通路 */
   {
    cout<<"此迷宫从入口到出口的一条路径如下:"<<endl;
       Print(x,y); /* 输出此通路 */
    for(i=1;i<curstep;i++)
    cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
   }
   else
    cout<<"此迷宫没有从入口到出口的路径"<<endl;
}
分享到：
| java.lang.ClassCastException解决方案(转 ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数据结构课程设计——迷宫问题

    很好，很受用，可以用来参考的，程序不长，很容易明白

    迷宫问题——数据结构

    本课程设计报告旨在解决迷宫问题，使用数据结构栈来实现迷宫问题的解决。迷宫问题是指在给定的迷宫中，找到一条从入口到出口的通路，否则证明迷宫中没有通路。为了解决这个问题，我们设计了一个程序，该程序使用链表...

    迷宫问题——数据结构课程设计迷宫问题完整版(含源代码).docx

    《迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)》是一份详细的实践教学材料，针对计算机科学与技术专业学生的算法与数据结构课程设计。该文档旨在通过解决迷宫问题来深入理解数据结构的应用，以及提高编程...

    迷宫问题——数据结构课程设计迷宫问题完整版(含源代码).pdf

    《迷宫问题——数据结构课程设计迷宫问题完整版》是一份详细的教学材料，涵盖了如何使用数据结构解决迷宫问题的全过程。这份资料是针对兰州理工大学计算机与通信学院2012年春季学期《算法与数据结构》课程设计的项目...

    迷宫课程设计

    ### 迷宫课程设计知识点详解 #### 一、问题背景及描述 迷宫实验源于心理学领域的一个经典案例，实验中，研究者会在一个无顶的大盒子里放置许多障碍（墙），仅留一处出口并放置一块奶酪以吸引实验对象——通常是...

    迷宫问题.docx(C/C++)-期末实验报告/课程设计

    《迷宫问题——C/C++实现与数据结构分析》 迷宫问题是一个经典的计算机科学问题，它涉及到数据结构的设计和算法的应用。在这个问题中，我们需要设计一种数据结构来表示迷宫，然后找到从入口到出口的路径。以下是...

    migong_迷宫_C++_strangedu5_

    【描述解析】：“用C语言设计实现的迷宫游戏程序，可供初学者参考”——虽然标题中提到的是C++，但描述中提及的是C语言，可能是描述文字的误写。我们假设这里实际指的是C++，因为标题明确指出了C++。这意味着这个...

    数据结构迷宫问题试验报告

    本文将深入探讨一个基于数据结构解决的实际问题——迷宫问题。迷宫问题通常涉及如何在一个复杂环境中找到从起点到终点的最短路径，这在很多实际场景中都有应用，如机器人导航、网络路由等。 迷宫问题可以通过多种...

    数据结构课程设计指导书

    #### 附录案例——迷宫与栈问题 **选题一：迷宫与栈问题** 在这个选题中，学生需要设计一个程序来解决迷宫问题，即寻找从起点到终点的路径。此问题可以通过栈数据结构来解决，利用栈的特点实现路径的回溯。具体...

    数据结构课程设计报告-迷宫求解.doc

    数据结构课程设计报告——迷宫求解主要关注的是如何运用数据结构和算法解决特定问题，即在给定的迷宫中找到从起点到终点的可行路径。报告详细介绍了设计过程，包括需求分析、数据结构的选择、算法设计、调试分析、...

    献给阿尔吉侬的花束——C++poj原题

    北京大学数据结构与算法课程作业代码，供广大学习c++的同学参考与学习

    数据结构课程设计.doc

    《数据结构》课程设计实验报告涉及了两个主要问题——迷宫问题求解和装箱问题求解，均采用C语言编程。这两个问题都需要利用数据结构和算法知识来解决。 1. 迷宫问题求解： 这是一个典型的路径搜索问题，可以使用...

    数据结构课程设计附带电子档报告

    在这个“数据结构课程设计”中，我们聚焦于一个具体的应用——迷宫设计，这涉及到路径搜索、图论和算法实现等多个重要概念。 迷宫设计通常涉及到两种主要的数据结构：矩阵和图。在二维迷宫中，我们可以使用二维数组...

    华科数据结构课程设计.7z

    《华科数据结构课程设计》是一份针对高等教育中计算机科学与技术专业的重要课程——数据结构进行深入学习和实践的资料集。数据结构是计算机科学的基础，它研究如何在内存中组织和管理数据，以实现高效的算法。这份...

    华南农业大学数据结构课程设计之贪吃蛇

    在华南农业大学的数据结构课程设计中，学生们被赋予了一个有趣且富有挑战性的任务——构建一个“疯狂贪吃蛇”游戏。这个项目旨在让学生们通过实际操作，深入理解和应用数据结构的基本概念，如队列、栈、链表等。下面...

    migongwenti.rar_graphical class_wintc_图形 迷宫

    《图形化迷宫程序设计——基于TC环境》 在计算机科学与技术领域，数据结构是不可或缺的基础课程之一，而迷宫问题则是数据结构课程中一个经典的实践课题。本项目名为“migongwenti.rar”，它是一个在DOS环境下利用...

    随机迷宫生成及最短路径寻找（QT实现可视化）（深度优先遍历）

    这个项目适用于计算机科学和技术、软件工程等专业的课程设计，旨在提升学生对数据结构、算法和图形用户界面设计的理解。以下是关于这个项目的详细知识点： 1. **迷宫生成算法**：迷宫生成通常采用两种经典方法——...

Magicbox
Global site tag (gtag.js) - Google Analytics