个人中心
gpt4 book ai didi

C语言实现数据结构迷宫实验

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 35 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言实现数据结构迷宫实验由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

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

步骤:

1、.h文件 。

1、首先是迷宫的生成，可以使用随机数种子生成，但主要逻辑部分并不在此，所以在这里直接写死，固定下来。 定义一个坐标类型的结构体，和二维数组迷宫:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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、然后是对栈的声明，栈里储存的元素为坐标类型 。

?
1
2
3
4
5
6
7
//顺序栈
#define MAXSIZE 50
typedef struct {
  SElemType *base;
  SElemType *top; //栈顶指针
  int stacksize;
}SqStack;

3、栈操作函数声明 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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、迷宫操作函数声明 。

?
1
2
3
4
5
6
7
8
//初始化迷宫(同时生成起始点和终点)
void initMaze(Maze &maze);
//打印迷宫
void showMaze(Maze maze);
//寻找出路；传入一个迷宫和栈找出出路
void findWay(Maze &maze,SqStack &s);
//判断该点的四个方向是否有通路，有就前进
Pos isExit(Pos p, Maze maze);

2、.cpp文件 。

1、导入所需头文件 。

?
1
2
3
4
5
#include "pch.h"
#include <iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;

2、栈操作实现 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//构造空栈
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、迷宫操作实现 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
///////////////////////////////////////迷宫操作////////////////////////////////
//初始化函数，传入一个迷宫，随机生成起点和终点，由于起点有一定限制，所以这里起点也固定为几个最合适的点
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 ;
  }
  //出口在右侧
  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) {
//首先遍历找出起始点和终点并保存下来
  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;
  }
  //如果所有放向都走不通（即返回的点是传入的点），则将其标为“@”，出栈到上一个点，继续判断
  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;
}

3、main函数调用 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int main()
{
  while ( true )
  {
  //创建一个迷宫
  Maze maze;
  initMaze(maze);
  //初始化一个栈
  SqStack S;
  initStack(S);
  cout << "*****************************" << endl;
  cout << "* 1、生成迷宫 2、退出 *" << endl;
  cout << "*****************************" << endl;
  cout << "请输入你的选择：" ;
  int select = 0;
  cin >> select;
  if (select == 1)
  {
  cout << "生成随机起点和出口迷宫：" << endl;
  showMaze(maze);
  cout << "生成迷宫路径：" << endl;
  findWay(maze, S);
  stackTravel(S);
  showMaze(maze);
  cout << endl;
  }
  if (select == 2)
  {
  clearStack(S);
  break ;
  }
  }
  return 0;
}

4、评价 。

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

1、因为很多地方写死了，所以复用性不高，可以用循环遍历来随机生成起点，同理迷宫的生成也是这样 2、判断路径可以用递归调用实现前进逻辑 。

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

原文链接：https://blog.csdn.net/weixin_42509364/article/details/84196761 。

最后此篇关于C语言实现数据结构迷宫实验的文章就讲到这里了,如果你想了解更多关于C语言实现数据结构迷宫实验的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

35 4 0
文章推荐： Python实现学生管理系统的完整代码(面向对象)
文章推荐： SpringBoot做junit测试的时候获取不到bean的解决
文章推荐： C++单例类模板详解
文章推荐： SpringBoot在RequestBody中使用枚举参数案例详解
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com