<sup id="sjju3"><noscript id="sjju3"></noscript></sup>
    <big id="sjju3"></big>

  • <blockquote id="sjju3"></blockquote>
    <blockquote id="sjju3"></blockquote>

      <td id="sjju3"></td>

      <big id="sjju3"></big>
        <code id="sjju3"><strong id="sjju3"><dl id="sjju3"></dl></strong></code>
      1. C语言实现数据结构迷宫实验

         更新时间:2019年03月24日 15:53:45   作者:燃烧的钥匙   我要评论

        这篇文章主要为大家详细介绍了C语言实现数据结构迷宫实验,具有一定的参考价值,感兴趣的小伙伴们可以参?#23478;?#19979;

        本文实例为大家分享了C语言实现简单的数据结构迷宫实验,供大家参考,具体内容如下

        分析:迷宫实验主要有两部分操作,其一是对迷宫的生成,其二是寻路使用栈的操作。

        步骤:

        一、.h文件

        1、首先是迷宫的生成,可以使用随机数种子生成,但主要逻辑部分并不在此,所以在这里直?#26377;此潰?#22266;定下?#30784;?br /> 定义一个坐标类型的结构体,?#25237;?#32500;数组迷宫:

        typedef struct {
         int x;
         int y;
        }Pos;
        
        //迷宫类型
        typedef struct {
         int square[10][10] = 
         {
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,0,0,0,0,0,0,1},
        {1,1,1,1,0,1,1,1,0,1},
        {1,0,0,0,0,1,0,1,0,1},
        {1,0,1,1,1,1,0,1,1,1},
        {1,0,0,0,0,1,0,0,0,1},
        {1,0,1,1,0,0,0,1,0,1},
        {1,0,1,1,1,0,1,1,1,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1},
         };
        }Maze;
        typedef Pos SElemType;

        2、然后是对栈的声明,栈里储存的元素为坐标类型

        //顺序栈
        #define MAXSIZE 50
        typedef struct {
         SElemType *base;
         SElemType *top;  //栈顶指针
         int stacksize;
        }SqStack;
        
        

        3、栈操作函数声明

        typedef int Status;
        #define OK 1;
        #define ERROR 0;
        
        //栈的相关操作
        //初始化栈
        Status initStack(SqStack &s);
        //压栈
        Status push(SqStack &s, SElemType e);
        //出栈
        SElemType pop(SqStack &s);
        //清空栈
        Status clearStack(SqStack &s);
        //摧毁栈
        void destroyStack(SqStack &s);
        //遍历栈
        Status stackTravel(SqStack s);

        4、迷宫操作函数声明

        //初始化迷宫(同时生成起始点和终点)
        void initMaze(Maze &maze);
        //打印迷宫
        void showMaze(Maze maze);
        //寻?#39029;?#36335;;传入一个迷宫和栈?#39029;?#20986;路
        void findWay(Maze &maze,SqStack &s);
        //判?#32454;?#28857;的四个方向是否有通路,有就前进
        Pos isExit(Pos p, Maze maze);

        二、.cpp文件

        1、导入所需头文件

        #include "pch.h"
        #include <iostream>
        #include<time.h>
        #include<stdlib.h>
        using namespace std;

        2、栈操作实现

        //构造空栈
        Status initStack(SqStack &s) {
         s.base = new SElemType[MAXSIZE];
         if (!s.base)
         {
         exit(OVERFLOW);//分配失败
         }
         s.top = s.base;
         s.stacksize = MAXSIZE;
         return OK;
        }
        
        //入栈
        Status push(SqStack &s, SElemType e) {
         //判断栈满
         if (s.top-s.base == s.stacksize)
         {
         return ERROR;
         }
         //存入元素,*为取指针的值
         s.top++;
         *s.top = e;
         return OK;
        }
        
        //出栈,用e返回栈顶值
        SElemType pop(SqStack &s) {
         SElemType e;
         //判断栈为空
         if (s.top == s.base)
         {
         //若为空则返回一个(-1,-1)的点,判断由外部调用时进行
         e.x = -1;
         e.y = -1;
         return e;
         }
         e = *s.top;
         s.top--;
         return e;
        }
        
        Status clearStack(SqStack &s) {
         s.top = s.base;
         return OK;
        }
        
        void destroyStack(SqStack &s) {
         s.top = NULL;
         s.stacksize = 0;
         free(s.base);
        }
        
        Status stackTravel(SqStack s) {
         while (s.top != s.base)
         {
         s.base++;
         Pos p = *s.base;
         //输出走过的路径
         cout <<"("<<p.x<<","<<p.y<<")"<< "-->";
         if ( p.x == 0 || p.y == 0|| p.x == 9 ||p.y == 9)
         {
         //终点输出为“End”
          cout << "End";
         }
         }
         cout << endl;
         return 0;
        }

        3、迷宫操作实现

        ///////////////////////////////////////迷宫操作////////////////////////////////
        //初始化函数,传入一个迷宫,随机生成起点和终点,由于起点有一定限制,所以这里起点也固定为几个最合?#23454;?#28857;
        void initMaze(Maze &maze) {
         //生成随机数
         srand((unsigned)time(NULL));
         int index = rand() % 36 + 1;
         int start = index % 6 + 1;
         //生成起始点数值为‘s'
         switch (start)
         {
         case 1:
         maze.square[1][1] = 's';
         break;
         case 2:
         maze.square[3][8] = 's';
         break;
         case 3:
         maze.square[3][6] = 's';
         break;
         case 4:
         maze.square[6][8] = 's';
         break;
         case 5:
         maze.square[8][3] = 's';
         break;
         case 6:
         maze.square[8][8] = 's';
         break;
         }
         //随机生成终点'e'表示
         while (index = rand()%36+1)
         {
         //出口在顶部
         if (index >1 &&index<10 && maze.square[1][index-1]!='s')
         {
          maze.square[0][index-1] = 'e';
          break;
         }
         //出口在?#20063;?
         else if (index>10 &&index <19)
         {
          if (maze.square[index-10][8] != 1 && maze.square[index-10][8]!='s') {
          maze.square[index-10][9] = 'e';
          break;
          }
         }
         //底部出口
         else if (index >19&&index<28)
         {
          if (maze.square[8][index - 19] != 's' && maze.square[8][index - 19] != 1) {
          maze.square[9][index - 19] = 'e';
          break;
          }
         }
         //左侧出口
         else if (index >28 && index <=36)
         {
          if (maze.square[index-28][1] != 1 &&maze.square[index-28][1] != 's')
          {
          maze.square[index - 28][0] = 'e';
          break;
          }
         }
         }
        }
        
        void showMaze(Maze maze) {
         for (int i = 0; i < 10; i++)
         {
         for (int j = 0; j < 10; j++)
         {
          if (maze.square[i][j] == 1)
          {
          cout << "* ";
          }
          else if (maze.square[i][j] == 0)
          {
          cout << " ";
          }
          else
          {
          cout << (char)maze.square[i][j]<<" ";
          }
         }
         cout << endl;
         }
        }
        //寻找迷宫路径
        void findWay(Maze &maze,SqStack &s) {
        //首先遍历?#39029;?#36215;始点和终点并保存下来
         Pos start,end;
         for (int i = 0; i < 10; i++)
         {
         for (int j = 0; j < 10; j++) {
          if (maze.square[i][j] == 's')
          { //起点压入栈内
          start.x = i;
          start.y = j;
          push(s, start);
          }
          else if (maze.square[i][j] == 'e')
          { //出口
          end.x = i;
          end.y = j;
          }
         }
         }
         //寻找路径
         Pos go = start;
         //直到找到出口才结束
         while ( s.top->x != end.x || s.top->y != end.y)
         {
         //获得下一步坐标
         Pos path = isExit(go, maze);
         if (path.x != go.x || path.y != go.y)
         {
          //前进
          maze.square[path.x][path.y] = 'p';
          push(s, path);
          go = path;
         }
         //如果所有放向都走不通(即返回的点是传入的点),则将其标为“@?#20445;?#20986;栈到上一个点,继续判断
         else
         {
          //走不通pop
          maze.square[path.x][path.y] = '@';
          pop(s);
          go = *s.top;
         }
         }
         maze.square[end.x][end.y] = 'e';
        }
        
        //判断返回下一步路径(顺序:右下左上),传入所处位置,从右边开始判断是否又通路或者出口,有就返回哪个方向上的点
        Pos isExit(Pos p,Maze maze) {
         Pos tempP = p;
        if (maze.square[tempP.x][tempP.y+1] == 0 || maze.square[tempP.x][tempP.y + 1] == 'e')
         {
         tempP.y++;
         }
         else if(maze.square[tempP.x+1][tempP.y] == 0 || maze.square[tempP.x +1][tempP.y] == 'e')
         {
         tempP.x++;
         }
         else if (maze.square[tempP.x][tempP.y - 1] == 0 || maze.square[tempP.x][tempP.y - 1] == 'e')
         {
         tempP.y--;
         }
         else if (maze.square[tempP.x - 1][tempP.y] == 0 || maze.square[tempP.x - 1][tempP.y] == 'e')
         {
         tempP.x--;
         }
         return tempP;
        }
        

        三、main函数调用

        int main()
        {
         while (true)
         {
         //创建一个迷宫
         Maze maze;
         initMaze(maze);
         //初始化一个栈
         SqStack S;
         initStack(S);
         cout << "*****************************" << endl;
         cout << "* 1、生成迷宫  2、?#39034;?*" << endl;
         cout << "*****************************" << endl;
         cout << "请输入你的选择:";
         int select = 0;
         cin >> select;
         if (select == 1)
         {
          cout << "生成随机起点?#32479;?#21475;迷宫:" << endl;
          showMaze(maze);
          cout << "生成迷宫路径:" << endl;
          findWay(maze, S);
          stackTravel(S);
          showMaze(maze);
          cout << endl;
         }
         if (select == 2)
         {
          clearStack(S);
          break;
         }
         }
         return 0;
        }

        四、评价

        这是个叫简易的迷宫,但基本实现了迷宫的寻路逻辑,可改进的地方有:

        1、因为很多地方?#27492;?#20102;,所以复用性不高,可以用循环遍历来随机生成起点,同理迷宫的生成也是这样
        2、判?#19979;?#24452;可以用递归调用实现前进逻辑

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

        相关文章

        最新评论

        2018白小姐一肖中特马
        <sup id="sjju3"><noscript id="sjju3"></noscript></sup>
        <big id="sjju3"></big>

      2. <blockquote id="sjju3"></blockquote>
        <blockquote id="sjju3"></blockquote>

          <td id="sjju3"></td>

          <big id="sjju3"></big>
            <code id="sjju3"><strong id="sjju3"><dl id="sjju3"></dl></strong></code>
          1. <sup id="sjju3"><noscript id="sjju3"></noscript></sup>
            <big id="sjju3"></big>

          2. <blockquote id="sjju3"></blockquote>
            <blockquote id="sjju3"></blockquote>

              <td id="sjju3"></td>

              <big id="sjju3"></big>
                <code id="sjju3"><strong id="sjju3"><dl id="sjju3"></dl></strong></code>