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

时间:2021-05-20

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

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

步骤:

一、.h文件

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

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 50typedef 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);//寻找出路;传入一个迷宫和栈找出出路void findWay(Maze &maze,SqStack &s);//判断该点的四个方向是否有通路,有就前进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、迷宫操作实现

///////////////////////////////////////迷宫操作//////////////////////////////////初始化函数,传入一个迷宫,随机生成起点和终点,由于起点有一定限制,所以这里起点也固定为几个最合适的点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函数调用

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、判断路径可以用递归调用实现前进逻辑

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

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章