精华内容
下载资源
问答
  • 迷宫求解数据结构课程设计报告.doc
  • 迷宫设计,初步设计,包括实验报告,详细讲解,属于大学程序语言入门设计。
  • 数据库课程设计 迷宫问题 附有可执行的代码
  • 是有关数据结构课程设计的实验报告.也许会有用.
  • 数据结构C语言课程设计报告! 关于使用穷举法求解的,用链栈作为存储结构。该资源只是提供课程设计报告,并不提供源程序。作为一个写作模板提供。
  • 为了保证在任何位置上都能沿原路返回,这就需要一个后进先出的结构来存储起位置,所以用到了栈的概念。 在问题的求解过程中,用到了对栈的定义、栈的初始化、栈的空间的申情、栈的销毁等有关栈的知识。 通过这次...
  • 数据结构课程设计迷宫问题代码及报告
  • 迷宫中从入口到出口的所有路径是一个经典的程序设计问题,即从入口出发,顺某一方向向前...本需求的编写目的在于将C语言与数据结构结合起来,使程序能够顺利进行,并且简洁,在此基础上更好的理解并运用数据结构知识
  • 数据结构与算法设计 迷宫问题实验报告 实验二 专业物联网工程 班级物联网1班 学号15180118 姓名刘沛航 实验目的 ?本程序是利用非递归的方法求出一条走出迷宫的路径并将路径输出首先由用户输入一组二维数组来组成迷宫...
  • 数据结构课程设计——迷宫问题课程设计报告

    万次阅读 多人点赞 2012-07-03 16:42:50
    上学时没学过数据结构和算法,于是现在有机会就自学。下面是我最近在等待进入项目组期间,花了1小时学习了一下迷宫问题。下面是我学习时找到的一篇课程设计报告,然后自己先看懂,然后又在VC6.0下运行了。 迷宫...

    上学时没学过数据结构和算法,于是现在有机会就自学。下面是我最近在等待进入项目组期间,花了1小时学习了一下迷宫问题。下面是我学习时找到的一篇课程设计的报告,然后自己先看懂,然后又在VC6.0下运行了。

    迷宫问题

    一.需求设计:以一个m*m 的方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口的通道,或得出没有通路的结论。

    二.概要设计:

    存储结构:

    采用了数组以及结构体来存储数据,在探索迷宫的过程中用到的栈,属于顺序存储结构。

    /*八个方向的数组表示形式*/

       int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}};

       /*用结构体表示位置*/

       struct position

       {

          int x,y;

       };

       position stack[m*m+1];

    基本算法:

    走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索;如果8个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。

    每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若退回到了入口处,则说明不存在通路。

    用一个字符类型的二维数组表示迷宫,数组中每个元素取值“0”(表示通路)或“1”(表示墙壁)。迷宫的入口点在位置(1,1)处,出口点在位置(m,m)处。设计一个模拟走迷宫的算法,为其寻找一条从入口点到出口点的通路。

    二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”,表示迷宫的边界;第1行第1列元素和第m行第m列元素置成“0”,表示迷宫的入口和出口;其余元素值用随机函数产生。

    假设当前所在位置是(x,y)。沿某个方向前进一步,它可能到达的位置最多有8个。

    如果用二维数组move记录8个方向上行下标增量和列下标增量,则沿第i个方向前进一步,可能到达的新位置坐标可利用move数组确定:

            x=x+move[i][0]

            y=y+move[i][1]

    从迷宫的入口位置开始,沿图示方向顺序依次进行搜索。在搜索过程中,每前进一步,在所到位置处做标记“”(表示这个位置在通路上),并将该位置的坐标压入栈中。每次后退的时候,先将当前所在位置处的通路标记“”改成死路标记“×”(表示这个位置曾到达过但走不通,以后不要重复进入),然后将该位置的坐标从栈顶弹出。搜索到出口位置时,数组中那些值为“”的元素形成一条通路。

    三.详细设计:

    源程序:

     

    /*
    
       迷宫问题
    
       走迷宫的过程可以模拟为一个搜索的过程:每到一
    
    处,总让它按东、东南、南、西南、西、西北、北、东北
    
    个方向顺序试探下一个位置;如果某方向可以通过,并且不
    
    曾到达,则前进一步,在新位置上继续进行搜索;如果个
    
    方向都走不通或曾经到达过,则退回一步,在原来的位置上
    
    继续试探下一位置。
    
        每前进或后退一步,都要进行判断:若前进到了出
    
    口处,则说明找到了一条通路;若退回到了入口处,则说明
    
    不存在通路。
    
        用一个字符类型的二维数组表示迷宫,数组中每个元素
    
    取值“0”(表示通路)或“1”(表示墙壁)。迷宫的入口点在
    
    位置(1,1)处,出口点在位置(m,m)处。这个算法,为
    
    其寻找一条从入口点到出口点的通路。
    
    */
    
    #include<stdio.h>
    
    #include<iostream>
    
    #include<stdlib.h>
    
    #include<time.h>
    
     
    
    int main(void)
    
    {
    
       int m=1;
    
       while (m!=0)
    
       {
    
    #if 0
    
          /* 数组不支持动态的定义 */
    
          printf("输入m,使得为m*m的方阵迷宫(m>0 输入0 时退出:)\n");
    
          scanf ("%d",&m);
    
    #endif
    
          m = 8;
    
          printf("迷宫矩阵的大小为:%d * %d\n", m, m);
    
     
    
          /*设定n*n的方阵迷宫*/
    
          /*数组的形式表示八个方向*/
    
          int move[8][2]={{0,1},{1,1},{1,0},
    
                    {1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}};
    
       
    
          /*用结构体表示位置*/
    
          struct position
    
          {
    
             int x;
    
             int y;
    
          };
    
     
    
          /*用于记录和输出迷宫探路中相关符号,包括1 .*/
    
          char maze[10][10];
    
     
    
          /*用栈来存储探路过程中的数据*/
    
          position stack[64+1];
    
          int top;/*栈顶*/
    
          int i,x,y,ok;
    
          position p;
    
     
    
          /*二维数组的第0行、第m+1行、第0列、第m+1列元素全
    
          置成"1",表示迷宫的边界;第1行第1列元素和第m行第m列
    
          元素置成"0",表示迷宫的入口和出口;其余元素值用随机
    
          函数产生。*/
    
          srand(time(0));  /* 产生一个随机种子 */
    
          for(x=1;x<=m;x++)
    
             for(y=1;y<=m;y++)
    
                maze[x][y]=48+rand()%2;
    
     
    
          maze[1][1]='0';maze[m][m]='0';     /* 入口 */
    
     
    
          for(x=0;x<=m+1;x++)
    
          {
    
             maze[x][0]='1';maze[x][m+1]='1';  /* 边界 */
    
          }
    
     
    
          for(y=0;y<=m+1;y++)
    
          {
    
             maze[0][y]='1';maze[m+1][y]='1';  /* 边界 */
    
          }
    
     
    
          p.x=1;p.y=1;
    
          top=1;stack[top]=p;
    
          maze[1][1]='.';
    
     
    
          /*开始探路
    
             走迷宫的过程可以模拟为一个搜索的过程:每到一
    
          处,总让它按东、东南、南、西南、西、西北、北、东北
    
          个方向顺序试探下一个位置;如果某方向可以通过,并且不
    
          曾到达,则前进一步,在新位置上继续进行搜索;如果个
    
          方向都走不通或曾经到达过,则退回一步,在原来的位置上
    
          继续试探下一位置。
    
             每前进或后退一步,都要进行判断:若前进到了出
    
          口处,则说明找到了一条通路;若退回到了入口处,则说明
    
          不存在通路。*/
    
          do{
    
             p=stack[top];
    
             ok=0;i=0;
    
             while((ok==0)&&(i<8))
    
             {
    
                x=p.x+move[i][0];
    
                y=p.y+move[i][1];
    
                if(maze[x][y]=='0')
    
                {
    
                    p.x=x;p.y=y;
    
                    stack[++top]=p;
    
                    maze[x][y]='.';
    
                    ok=1;
    
                }
    
                i++;
    
             }
    
             if(i==8)
    
             {
    
                maze[p.x][p.y]='*';
    
                top--;
    
             }
    
          } while((top>0)&&((p.x!=m)||(p.y!=m)));
    
     
    
          /*输出探路结果*/
    
          if(top==0)
    
          {
    
             printf("没有路径\n");
    
          }
    
          else 
    
          {
    
             printf("有路径\n");
    
          }
    
     
    
          /*输出探路迷宫留下的踪迹*/
    
    #if 0
    
          for(x=1;x<=m;x++)
    
          {
    
             printf("\n");
    
             for(y=1;y<=m;y++) 
    
                printf("%c ",maze[x][y]);
    
          }
    
    #else
    
          /*输出整个迷宫*/
    
          for(x=0; x <= m + 1; x++)
    
          {
    
             printf("\n");
    
             for(y=0;y<=m+1;y++) 
    
                printf("%c ",maze[x][y]);
    
          }
    
    #endif
    
          printf("\n");
    
     
    
          system("pause"); 
    
     
    
       }
    
     
    
       return 0;
    
    }


    四.调试分析:

    测试数据和结果:

    有路径的情况,

    无路径的情况,

    算法时间复杂度:

             O(m²)

    对相关问题的思考:

           这个迷宫问题的算法中,要在开始设置迷宫的大小。在探索迷宫路线的过程中,是通过不断的尝试来得到最终的结果,由于不能对已经设定为可走路径进行返回,所以在这个算法中有时候可能不能得到走出迷宫的路径。如下:

     

    原文来自:http://wenku.baidu.com/view/43040e73f242336c1eb95e29.html
    展开全文
  • 迷宫问题课程设计,有完整的源代码和完整的word文档报告
  • 数据结构迷宫实验代码及完整实验报告 数据结构实验实验三栈和队列的应用计算机科学与技术系 0901 班组 长:辛志鹏 组 员:张发辉、田飞、赵金桃日 期:2011 年 4 月 21 日实验报告2009 级 0901 班 2011 年 4 月 21 ...

    41528d3028836879cd698677c3999917.gif数据结构迷宫实验代码及完整实验报告

    数据结构实验实验三栈和队列的应用计算机科学与技术系 0901 班组 长:辛志鹏 组 员:张发辉、田飞、赵金桃日 期:2011 年 4 月 21 日实验报告2009 级 0901 班 2011 年 4 月 21 日实验类型:综合设计型 实验地点:软件实验室三 组长:辛志鹏(45) 组员:张发辉(36),赵金桃(22),田 飞 (32)一 实验题目栈和队列的应用二 需求分析本程序是利用非递归的方法求出一条走出迷宫的路径,并将路径输出。首先由用户输入一组二维数组来组成迷宫,确认后程序自动运行,1. 当迷宫有完整路径可以通过时,以 0 和 1 所组成的迷宫形式输出,标记所走过的路径结束程序; 2. 当迷宫无路径时,提示输入错误结束程序。 程序执行的命令:1 创建迷宫 ;2 求解迷宫;3 输出迷宫求解;三 概要设计本程序中采用的数据模型,用到的抽象数据类型的定义,程序的主要算法流程及各模块之间的层次调用关系程序基本结构:设定栈的抽象数据类型定义:ADT Stack {数据对象:D={ | ∈CharSet,i=1,2,3,…,n,n=0;}数据关系:R={| , ∈D,i=2,…,n}设置迷宫的抽象类型ADT maze{数据对象:D={ai|ai∈‘ ’, ‘@’,‘#’,‘1’,i=1,2,…,n,n=0}数据关系:R={r,c}r={|ai-1,ai∈D, i=1,2,…,n,}c=|ai-1,ai∈D, i=1,2,…,n,}结构体定义:typedef struct //迷宫中 x 行 y 列的位置{ int x;int y;}PosType;typedef struct //栈类型{ int ord; //通道块在路径上的“序号”PosType seat; //通道块在迷宫中的“坐标位置”int di; //从此通道块走向下一通道块的“方向”}MazeType;typedef struct{ MazeType *base;MazeType *top;int stacksize;}MazeStack;基本函数:Status InitStack(MazeStack if(!S.base)exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}\\20091001452)出栈操作Status Pop(MazeStack e = *--S.top;return OK;}\\20091001453)判断栈是否为空Status StackEmpty(MazeStack return ERROR;}\\20091001454)迷宫路径求解Status MazePath(PosType start, PosType end)//迷宫路径求解{PosType curpos;MazeStack S;MazeType e;int curstep;InitStack(S);curpos = start; //设定当前位置为入口位置curstep = 1; //探索第一步cout ’。六 使用说明首先由用户输入一组二维数组来组成迷宫,确认后程序自动运行,1、 当迷宫有完整路径可以通过时,以 0 和 1 所组成的迷宫形式输出,标记所走过的路径结束程序; 2、 当迷宫无路径时,提示输入错误结束程序。 程序执行的命令:1 创建迷宫 ;2 求解迷宫;3 输出迷宫求解;七 测试结果八 实验总结1. 本次实验利用了关于栈的相关知识,入栈、出栈、判断栈满、增加存储空间等等,使学习到的知识能够很好的结合利用,在实际的操作中加强熟练程度。 2. 对于没有掌握好的知识,应该及时的参考课本或者网络资源,使知识落实到实处,不留空白。 3. 关于迷宫中行走方向的选择这一块需要重点的练习,函数的运用不够灵活。 九 模块分工2009100145 辛志鹏 入栈、出栈和判断栈是否为空2009100136 张发辉 迷宫路径求解 2009100122 赵金桃 调用函数 2009100132 田 飞 探索下一位置、标记走过和作废的路径附完整代码:#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef struct//迷宫中 x 行 y 列的位置{int x;int y;}PosType;typedef struct//栈类型{int ord; //通道块在路径上的“序号”PosType seat; //通道块在迷宫中的“坐标位置”int di; //从此通道块走向下一通道块的“方向”, //1:东 2:北 3:西 (顺时针)}MazeType;typedef struct{MazeType *base;MazeType *top;int stacksize;}MazeStack;#include using namespace std;Status InitStack(MazeStack Status Push(MazeStack Status Pop(MazeStack Status StackEmpty(MazeStack Status MazePath(PosType start, PosType end);Status Pass(PosType void FootPrint(PosType pos);PosType NextPos(PosType curPos, int void MakePrint(PosType pos);//迷宫地图,0 表示墙壁,1 表示通路, 入口:mazeMap[1][1], 出口 mazeMap[8][8]int mazeMap[10][10] ={ //0,1,2,3,4,5,6,7,8,9{0,0,0,0,0,0,0,0,0,0}, //0{0,1,1,0,1,1,1,0,1,0}, //1{0,1,1,0,1,1,1,0,1,0}, //2{0,1,1,1,1,0,0,1,1,0}, //3{0,1,0,0,0,1,1,1,1,0}, //4{0,1,1,1,0,1,1,1,1,0}, //5{0,1,0,1,1,1,0,1,1,0}, //6{0,1,0,0,0,1,0,0,1,0}, //7{0,0,1,1,1,1,1,1,1,0}, //8{0,0,0,0,0,0,0,0,0,0} //9};int main(){PosType mazeStart, mazeEnd;mazeStart.x = 1;//开始与结束点mazeStart.y = 1;mazeEnd.x = 8;mazeEnd.y = 8;cout = S.stacksize){S.base = (MazeType

    展开全文
  • C++ 课程设计 报告和源文件 迷宫 交通图 链表(仓库管理) 本人的结课作品 100% 原创 希望大家喜欢 因为文件较多 要的分多一点 但是觉得不会让你失望!
  • 设计思路:程序首先要考虑迷宫的表示,这是一个二维关系图,所以可选择二维数组来存储。数组元素只有两种值0和1,分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索,则依据按键来确定探索...
  • 数据结构实践》设计报告迷宫求解 因为学校要求答辩结课,给了很多题目都不太会,决定把感兴趣的都做一做,在这存档备用。 课程设计题目:迷宫求解 课程设计主要内容和要求: 一.设计目的: 1.掌握栈的特点及其...

    《数据结构实践》设计报告—迷宫求解

    因为学校要求答辩结课,给了很多题目都不太会,决定把感兴趣的都做一做,在这存档备用。

    课程设计题目:迷宫求解

    课程设计主要内容和要求:

    一.设计目的:
    1.掌握栈的特点及其描述方法
    2.掌握链栈的各种基本操作

    二.设计内容和要求:
    由0和1构成的m*n维矩阵表示一个迷宫,其中0表示通路,1表示墙壁。迷宫入口为(1,0),出口为(m-1,n)。迷宫随机产生。试编一算法求出从入口到出口的一条通路,或显示没有通路。要求实现如下功能:
    1.从键盘输入m和n,随机产生迷宫。
    2.找到一条通路即可,若没有显示“No path!”。

    --------------------------------------------------------------------

    一、题目描述

    以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍,设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

    在这里插入图片描述

    二、解题思路

    建立一个迷宫:
    1、先建立一个数组假设数组存储的全为墙(wall),假设迷宫只有一条正确的道路。
    2、确定迷宫的起点(route),以起点为根节点向下搜索,搜索到墙(wall),将墙变为路(route)。
    3、我们挖的道路就像树结构,树上有很多的分支,分支也有子分支,每个子分支都不能相交,相交就说明墙被推倒了,那么此时的迷宫就可能存在多条正确道路,那么基于唯一道路的原则,我们向某个方向搜索一块新的区域时,要先判断新区域是否有形成回路的可能,如果可能要立即停止并换个方向搜索。
    4、因为采用了递归的方式,所以给迷宫外层围上墙之后,再在墙外围上一条路。避免程序永久执行下去。

    寻找迷宫路径:
    1、 将迷宫起点压栈,标记已走过道路。
    2、 向四个方向遍历,寻找是路的邻接点。
    3、 确认邻接点可行将邻接点压栈,标记邻接点为可行路径。如果邻接点不可行,则将邻接点弹栈。
    4、 重复,遍历到出口节点,输出路径。
    5、 如栈空,输出No path!

    三、主要数据结构

    1、使用数组存储迷宫,方便好看。使用静态二维数组作为参数传递比较麻烦,一般需要指明第二维的长度,但在本题情况中,第二维长度未知。所以使用malloc内存动态分配数组,既保证数组连续性,又方便传递参数。

    int **Maze = (int**)malloc(M * sizeof(int *));
    	for(i=0;i<M;i++){
            Maze[i]=(int*)malloc(N * sizeof(int));
    	}
    

    2、使用栈存储迷宫路径,因为栈的原则是先进后出,符合迷宫走错路就退一步的特点。栈使用链式存储方式,用于存放遍历的点和下一个点运动的方向。

    struct MG{
        int i;
        int j;
        int di;     ///记录方向
    }Stack[MaxSize];///栈:存放路径
    

    四、相关算法介绍

    深度优先搜索:目的是要达到被搜索结构的叶结点。即在搜索其余的结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着结点走到不能再深入为止,然后返回到某一个结点,再继续选择其他结点搜索。当不再有其他结点可选择时,说明搜索已经结束。

    使用图的深度遍历:
    (1)从迷宫起点节点V开始访问
    (2)访问这个节点V,标记为可行的路径;
    (3)从v的未被访问的非"墙"邻接点中选取一个顶点w,重复第二步。如果v没有未访问的非"墙"邻接点,把这个节点的可行路径标记移除,回溯至上一节点;
    (4)重复上述第(2)、(3)步,直至遍历到迷宫的出口节点。

    五、源程序

    #include<stdio.h>
    #include<time.h>
    #include<math.h>
    #include <stdlib.h>
    ///墙和路径的标识
    #define wall  0
    #define route 1
    #define path  3
    #define MaxSize 100///规定栈空间最大是100
    
    struct MG{
        int i;
        int j;
        int di;     ///记录方向
    }Stack[MaxSize];///栈:存放路径
    int top=-1;
    
    ///声明函数
    void CreateMaze(int **maze, int x, int y);
    void mgpath(int **maze,int M, int N);
    
    int main() {
        srand((unsigned)time(NULL));/***生成随机数***/
    
        int M,N;
        printf("请输入迷宫长度M,宽度N(长宽差2,空格间隔)\n");
        scanf("%d %d/n",&M,&N);
        M=M+2;N=N+2;///加上外侧包围墙体,最外侧包围路径。
    
    	int i,j;
    	int **Maze = (int**)malloc(M * sizeof(int *));
    	for(i=0;i<M;i++){
            Maze[i]=(int*)malloc(N * sizeof(int));
    	}/***int *a=(int*)malloc(n*sizeof(int));
            表示定义一个int类型的指针变量a,
            并申请n*sizeof(int)个字节(即4*n个字节)的存储空间。***/
    
    ///防止搜索路时超出边界,把最外围层设为路径。
    	for (i=0; i<M; i++){
            Maze[i][0]=route;
    		Maze[i][N-1]=route;
    	}
    	for (i=0; i<N; i++){
    	    Maze[M-1][i]=route;
    		Maze[0][i]=route;
        }
    	///创造迷宫,(2,2)为起点
    	CreateMaze(Maze, 2, 2);
    
    	///画迷宫的入口
    	Maze[2][1] = route;
    
    	///算法随机性,出口不一定在(M-3,N-2)处,需要寻找出口。
    	for (i=M-3; i>=0; i--) {
    		if (Maze[i][M-3]==route) {
    			Maze[i][N-2] = route;
    			break;
    		}
    	}
    
    	///打印迷宫。
    	for (i=0; i<M; i++) {
    		for (j=0; j<N; j++) {
    			if (Maze[i][j]==route) {
    				printf(" 0 ");
    			}
    			else {
    				printf(" 1 "); ///█墙壁,测试用。
    			}
    		}
    		printf("\n");
    	}
    	printf("迷宫路径如下:\n");
        mgpath(Maze,M,N);
    
    	for(i=0;i<M;i++)
            free((int *)Maze[i]);
        free((int *)Maze);
    
    	return 0;
    }
    
    void CreateMaze(int **maze, int x, int y) {
    	maze[x][y] = route;
    	///确保四个方向随机
    	int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };///向上,下,左,右移动
    	int i,j,k;
    	for (i=0; i<4; i++) {
    		int r = rand() % 4;
    		int t = direction[0][0];
    		direction[0][0] = direction[r][0];
    		direction[r][0] = t;
    		t = direction[0][1];
    		direction[0][1] = direction[r][1];
    		direction[r][1] = t;
    	}
    
    	///决定下一步去往那个方向
    	for (i=0; i<4; i++) {
    		int dx=x;
    		int dy=y;
    
    		int range = 1;
    		while (range>0) {
    			dx += direction[i][0];
    			dy += direction[i][1];
    
    			///排除掉回头路
    			if (maze[dx][dy] == route) {
    				break;
    			}
    
    			///判断是否挖穿路径
    			int count = 0;
    			for (j=dx-1;j<dx+2;j++) {
    				for (k=dy-1;k<dy+2;k++) {
    		///abs(j-dx) + abs(k-dy) == 1 确保只判断九宫格的四个特定位置
    		///abs 绝对值函数
    					if (abs(j-dx)+abs(k-dy)==1 && maze[j][k]==route){
    						count++;
    					}
    				}
    			}
    
    			if (count > 1) {
    				break;
    			}
    
    			///确保不会挖穿时,前进
    			--range;
    			maze[dx][dy] = route;
    		}
    
    		///没有挖穿危险,以此为节点递归
    		if (range <= 0) {
    			CreateMaze(maze, dx, dy);
    		}
    	}
    }
    
    void mgpath(int **Maze,int M, int N){
        int i,j,di;/// i,j表示当前位置,di为方向
        int find,k;/// find为是否找到了可走点,找到为1,k用于读取
        top++;
        Stack[top].i=2;      ///初始位置(2,2)
        Stack[top].j=1;
        Stack[top].di=-1;
        Maze[2][1]= path;
    
        while(top>-1){       ///只要栈Stack不为空就继续走
            i=Stack[top].i;
            j=Stack[top].j;
            di=Stack[top].di;
            if(i==M-3&&j==N-2)         ///找到了出口,输出路径
            {
                for(k=0; k<=top; k++)
                {
                    printf("(%d,%d) ",Stack[k].i,Stack[k].j);
                }
                break;
           }
            find=0;
            ///di:0上1右2下3左四个方向,找可走点
    
            while(di<4 && find==0){    ///在4个方向内,寻找可走点
                di++;
                switch(di)
                {
                case 0:i=Stack[top].i-1;
                       j=Stack[top].j;
                       break;   ///上面
                case 1:i=Stack[top].i;
                       j=Stack[top].j+1;
                       break;   ///右边
                case 2:i=Stack[top].i+1;
                       j=Stack[top].j;
                       break;   ///下面
                case 3:i=Stack[top].i;
                       j=Stack[top].j-1;
                       break;  ///左边
                }
                if(Maze[i][j]==route){///找到可走点
                    find=1;
                }
            }
    
            if(find == 1)           ///找到了下一个可走结点
            {
                Stack[top].di=di;   ///修改原栈顶元素的di值
                top++;              ///下一个可走结点进栈
                Stack[top].i=i;
                Stack[top].j=j;
                Stack[top].di=-1;
                Maze[i][j]=path;        ///避免重复走到该结点
            }else                   ///没找到
            {
                Maze[Stack[top].i][Stack[top].j]=route;   ///让该位置变为其他路径的可走结点
                top--;
            }
        }
        if(top==-1){
                printf("No path!");
           }
    }
    
    
    

    六、时空分析(这个是真的不会,凑合弄的,凑合看吧。)

    建立一个迷宫:
    寻找迷宫路径:
    因为算法不稳定,其时空复杂度不仅和m,n有关,还和Maze[ ][ ]的具体数值有关。
    最坏情况下:每个点都试探过才走到终点。此时时间复杂度为:(m×n-1) ×4,(其中4为4个方向),空间复杂度m×n+100=m×n,(其中m×n为存储迷宫图空间,100为栈空间);
    再好情况下:一次试探过就走到终点。此时时间复杂度为:(min(m,n)-1),空间复杂度m×n;
    该算法时间复杂度为:[(m×n-1) ×4+(min(m,n)-1)]/2,约为2×m×n
    空间复杂度为3×m×n/2

    七、运行结果及分析

    在这里插入图片描述
    1、尝试使用在全为墙的数组中使墙随机生成路径,因为不确定性太大,每个wall都有50%的可能成为路,生成回路或者没有路径的可能性太大,决定使用深度搜索算法,缺点是只有一条路径。
    2、从键盘中输入行数与列数,调用CreateMaze函数随机生成一个迷宫,缺陷在于行数和列数的差值固定,只能为二。
    3、迷宫生成后调用mgpath函数寻找迷宫路径,因为算法问题只能生成一条且必有一条函数,所以只能输出一条路径,如有多条路径的算法可以定义length,再新建一个栈,使用length和top做比较,可以输出多条路径和最短路径。

    //例如
    if(top+1<minlen)           //比较是否是最短路径
       {
          for(k=0;k<=top;k++)     //是最短,保存路径
             Path[k]=Stack[k];
             minlen=top+1;
       }
    

    八、问题

    其实测试的时候出了很多问题,
    比如M和N的差值只能是二,其他的就会报错,

    ///算法随机性,出口不一定在(M-3,N-2)处,需要寻找出口。
    	for (i=M-3; i>=0; i--) {
    		if (Maze[i][M-3]==route) {
    			Maze[i][N-2] = route;
    			break;
    		}
    	}
    

    还有这个,如果挖到最后一行或最后一列,感觉应该用两个for循环,如果一个挖到出口列,把挖到的路到出口中间那一列的墙打通;一个挖到出口行,把挖到的路到出口中间那一行的墙打通。这么写也能运行,那我就凑合了。
    具体是为什么,我也没搞明白。

    九、参考。

    关于怎样生成一个迷宫:
    https://blog.csdn.net/jjwwwww/article/details/82872922
    关于怎样寻找迷宫路径:
    https://blog.csdn.net/zhouchenghao123/article/details/83626222

    展开全文
  • 数据结构的课程设计迷宫问题,用C++实现的,附带报告
  • c语言 数据结构 课程设计报告 迷宫+西文图书管理+命题公式真值 这是一个完整的报告 ,比较实用 ,祝您学习愉快!
  • 数据结构课程设计5个 约瑟夫环 迷宫问题 个人账簿管理 宿舍管理软件 一元多项式计算 有源代码和实验报告 绝对有用很好的
  • 数据结构课程设计,题目为迷宫求解,word文档报告
  • 本程序主要是对任意给定的迷宫,求出一条从入口到出口的...使我们基本掌握线性表及栈上基本运算的实现,进一步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题,培养我们的动手能力。
  • 关于数据结构课程设计迷宫问题,包含报告
  • 迷宫问题的课程设计,实验报告,程序修改,基于c++6.0的程序设计
  • 数据结构课程设计之迷宫求解,仅仅是设计报告
  • 数据结构实验报告 迷宫求解问题实验 上机环境 DevC++ 二程序设计相关信息 1实验题目迷宫求解问题 问题描述 实验题3.5 改进3.1.4节中的求解迷宫问题程序要求输出如图3.14所示的迷宫的所有路径并求最短路径长度及最短...
  • 数据结构课程设计报告 PAGE PAGE 2 南京林业大学 数据结构课程设计报告 专业 计算机科学与技术 课程名称 数据结构 姓名 学号 090801126 指导老师 时间: 2011年1月 目录要点 具体内容题目 1 需求分析功能要求 2 概要...
  • C语言数据结构课程设计,迷宫问题,链栈实现,读取迷宫文件。包括具体实现过程、设计报告

空空如也

空空如也

1 2 3 4
收藏数 77
精华内容 30
关键字:

数据结构迷宫设计报告

数据结构 订阅