C language implements data structure maze experiment

This paper shares a simple data structure maze experiment with C language for your reference. The specific content is as follows

Analysis: The maze experiment mainly has two parts operation, its 1 is to the maze generation, its 2 is to seek the way to use the stack operation.

Steps:

1.. h file

1, the first is the generation of the maze, you can use random number seed generation, but the main logical part is not here, so here directly write dead, fixed.
Define 1 coordinate type structure, and 2 dimensional array labyrinth:

typedef struct {
 int x;
 int y;
}Pos;

// The labyrinth type 
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;

Then comes the declaration of the stack, where the elements are stored as coordinate types

// Order of the stack 
#define MAXSIZE 50
typedef struct {
 SElemType *base;
 SElemType *top;  // The stack pointer 
 int stacksize;
}SqStack;

3, stack operation function declaration

typedef int Status;
#define OK 1;
#define ERROR 0;

// Stack operations 
// Initialize the stack 
Status initStack(SqStack &s);
// The pressure of stack 
Status push(SqStack &s, SElemType e);
// Out of the stack 
SElemType pop(SqStack &s);
// Empty stack 
Status clearStack(SqStack &s);
// Destroy the stack 
void destroyStack(SqStack &s);
// Traversal stack 
Status stackTravel(SqStack s);

4, maze operation function declaration

// Initialization maze ( Both the starting point and the ending point are generated )
void initMaze(Maze &maze);
// Print a maze 
void showMaze(Maze maze);
// Looking for a way out; The incoming 1 A maze and a stack to find a way out 
void findWay(Maze &maze,SqStack &s);
// Judge the point 4 Whether there is access to the direction, there is forward 
Pos isExit(Pos p, Maze maze);

2.. cpp file

1. Import the required header files

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

2. Stack operation implementation

// Constructs an empty stack 
Status initStack(SqStack &s) {
 s.base = new SElemType[MAXSIZE];
 if (!s.base)
 {
 exit(OVERFLOW);// Allocation failure 
 }
 s.top = s.base;
 s.stacksize = MAXSIZE;
 return OK;
}

// Into the stack 
Status push(SqStack &s, SElemType e) {
 // Judgment stack full 
 if (s.top-s.base == s.stacksize)
 {
 return ERROR;
 }
 // In the element ,* Is the value of the fetch pointer 
 s.top++;
 *s.top = e;
 return OK;
}

// Out of the stack , with e Returns the top of the stack 
SElemType pop(SqStack &s) {
 SElemType e;
 // Verify that the stack is empty 
 if (s.top == s.base)
 {
 // Returns if null 1 A ( -1 . -1 ), the judgment is made by the external call 
 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;
 // Output the path traveled 
 cout <<"("<<p.x<<","<<p.y<<")"<< "-->";
 if ( p.x == 0 || p.y == 0|| p.x == 9 ||p.y == 9)
 {
 // The endpoint output is" End " 
  cout << "End";
 }
 }
 cout << endl;
 return 0;
}

3, maze operation implementation

/////////////////////////////////////// Maze operation ////////////////////////////////
// Initialize the function, pass in 1 A maze, randomly generated starting and ending points, as the starting point has 1 I'm going to limit it, so I'm going to start at the most appropriate points 
void initMaze(Maze &maze) {
 // Random number generation 
 srand((unsigned)time(NULL));
 int index = rand() % 36 + 1;
 int start = index % 6 + 1;
 // The initial value of the generation point is' 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;
 }
 // Randomly generated endpoint 'e' said 
 while (index = rand()%36+1)
 {
 // Exit at the top 
 if (index >1 &&index<10 && maze.square[1][index-1]!='s')
 {
  maze.square[0][index-1] = 'e';
  break;
 }
 // The exit is on the right. 
 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;
  }
 }
 // At the bottom of the export 
 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;
  }
 }
 // On the left side of the outlet 
 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;
 }
}
// Find the maze path 
void findWay(Maze &maze,SqStack &s) {
// First traverse to find the starting and ending points and save them 
 Pos start,end;
 for (int i = 0; i < 10; i++)
 {
 for (int j = 0; j < 10; j++) {
  if (maze.square[i][j] == 's')
  { // The starting point is pushed into the stack 
  start.x = i;
  start.y = j;
  push(s, start);
  }
  else if (maze.square[i][j] == 'e')
  { // exit 
  end.x = i;
  end.y = j;
  }
 }
 }
 // Search path 
 Pos go = start;
 // Not until we find the exit 
 while ( s.top->x != end.x || s.top->y != end.y)
 {
 // To obtain the 1 Step coordinates 
 Pos path = isExit(go, maze);
 if (path.x != go.x || path.y != go.y)
 {
  // forward 
  maze.square[path.x][path.y] = 'p';
  push(s, path);
  go = path;
 }
 // If all put directions fail (that is, the returned point is the incoming point), mark it as" @ ", out onto the stack 1 Point two, keep judging 
 else
 {
  // To go pop
  maze.square[path.x][path.y] = '@';
  pop(s);
  go = *s.top;
 }
 }
 maze.square[end.x][end.y] = 'e';
}

// Judge returns 1 Step path (order: lower right, upper left), pass into the position, start from the right to determine whether there is a path or exit, if there is, return the point in which direction 
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;
}

3. main function call

int main()
{
 while (true)
 {
 // create 1 A maze 
 Maze maze;
 initMaze(maze);
 // Initialize the 1 A stack 
 SqStack S;
 initStack(S);
 cout << "*****************************" << endl;
 cout << "* 1 , generate a maze   2 , exit  *" << endl;
 cout << "*****************************" << endl;
 cout << " Please enter your choice: ";
 int select = 0;
 cin >> select;
 if (select == 1)
 {
  cout << " Generate random starting and exit mazes: " << endl;
  showMaze(maze);
  cout << " Generate maze path: " << endl;
  findWay(maze, S);
  stackTravel(S);
  showMaze(maze);
  cout << endl;
 }
 if (select == 2)
 {
  clearStack(S);
  break;
 }
 }
 return 0;
}

Evaluation of 4.

This is a simple maze, but it basically realizes the pathfinding logic of the maze, and the improvements include:

1, because many places are written dead, so the reuse is not high, you can use a loop to randomly generate the starting point, the same is true for the generation of the maze
2, determine the path can be used to achieve recursive call forward logic