本文实例为大家分享了C语言实现简单的数据结构迷宫实验，供大家参考，具体内容如下
分析：迷宫实验主要有两部分操作，其一是对迷宫的生成，其二是寻路使用栈的操作。
步骤：
一、.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 50typedef 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); |
二、.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;} |
三、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;} |
四、评价
这是个叫简易的迷宫，但基本实现了迷宫的寻路逻辑，可改进的地方有：
1、因为很多地方写死了，所以复用性不高，可以用循环遍历来随机生成起点，同理迷宫的生成也是这样
2、判断路径可以用递归调用实现前进逻辑
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/weixin_42509364/article/details/84196761
