（数据结构作业）用C语言写的一个迷宫

2019-11-06 07:12:12

字体：大中小

来源：转载

供稿：网友

编译环境：win8.1+VS2015 说明：这是数据结构学完栈和队列写的作业。利用随机数生成一张迷宫图，然后用队列找出最短路径，用栈输出之。可以动态显示最短路径喔~~~最后，这个作业用了文件分离写（头文件声明，.cpp文件定义）。 Last but not least:输入的行数和列数都不能太大（12以下）。因为：队列中找最短路径的时候要存储很多位置，当图太大的时候位置就变多了不是，这时候队列就会溢出的（也就是队列装不下那么多位置信息了）。

===========上代码了=================

//file name:stack.h#ifndef STACK_H#define STACK_H#include "queue.h"#define MAXSIZE 10000typedef int Status; /*返回状态值*/typedef struct{ int i, j;/*坐标值*/ int next;/*前一个位置在队列中的序号*/}SElemType;/*队列结构*/typedef struct { int top; SElemType elem[MAXSIZE];}SqStack;Status InitStack(SqStack *); //构造一个空栈Status StackEmpty(SqStack);//若栈为空，返回TRUE，否则返回FALSEStatus Push(SqStack *, ElemType);//插入元素作为新的栈顶元素Status Pop(SqStack *, SElemType *);//若栈不空，删除栈顶元素，用e返回其值#endif // !STACK_H//file name:stack.cpp#include<stdio.h>#include"stdlib.h"#include"stack.h"#include"queue.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2Status InitStack(SqStack *S) //构造一个空栈{ S->top = -1; return OK;}//InitStackStatus StackEmpty(SqStack S)//若栈为空，返回TRUE，否则返回FALSE{ if (S.top == -1) return TRUE; else return FALSE;}//StackEmptyStatus Push(SqStack *S, ElemType e)//插入元素作为新的栈顶元素{ if(S->top>=MAXSIZE-1){//栈满 PRintf("The stack is full!/n"); return ERROR; } ++S->top; S->elem[S->top].i = e.i; S->elem[S->top].j = e.j; S->elem[S->top].next = e.pre; return OK;}//PushStatus Pop(SqStack *S, SElemType *e)//若栈不空，删除栈顶元素，用e返回其值{ if (S->top == -1) { printf("Empty stack!/n"); return ERROR; } e->i = S->elem[S->top].i; e->j = S->elem[S->top].j; e->next = S->elem[--S->top].next; return OK;}//Pop//file name:queue.h#ifndef QUEUE_H#define QUEUE_H#define MAXSIZE 10000typedef int Status; /*返回状态值*//*队列中数据元素类型*/typedef struct{ int i, j;/*坐标值*/ int pre;/*前一个位置在队列中的序号*/}ElemType;/*队列结构*/typedef struct { int front, rear; ElemType elem[MAXSIZE];}SQQueue;Status InitQueue(SqQueue *); /*构造一个空队列Q*/int QueueLength(SqQueue); /*返回队列Q的元素个数，即队列的长度*/Status EnQueue(SqQueue *, ElemType);/*插入元素e为Q的新的队尾元素*/Status DeQueue(SqQueue *, ElemType *); /*若队列不为空，则删除Q的队头元素，用e返回其值*/Status QueueEmpty(SqQueue);/*若队列为空，则返回真*/Status GetHead(SqQueue, ElemType *); /*若队列不空，用e返回队头元素*/#endif // !QUEUE_H//file name:queue.cpp#include<stdio.h>#include<stdlib.h>#include "queue.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2Status InitQueue(SqQueue *Q) /*构造一个空队列Q*/{ Q->front = Q->rear = 0; return OK;}//InitQueueStatus EnQueue(SqQueue *Q, ElemType e)/*插入元素e为Q的新的队尾元素*/{ if (QueueLength(*Q) >= MAXSIZE - 1) {//队满 printf("Queue is full!Can not continue to find the way.../n"); exit(OVERFLOW); } else { Q->elem[Q->rear].i = e.i; Q->elem[Q->rear].j = e.j; Q->elem[Q->rear].pre = e.pre; Q->rear++; } return OK;}//Enqueueint QueueLength(SqQueue Q) /*返回队列Q的元素个数，即队列的长度*/{ return Q.rear;}//QueueLengthStatus DeQueue(SqQueue *Q, ElemType *e) /*若队列不为空，则删除Q的队头元素，用e返回其值*/{ if (QueueEmpty(*Q)) return ERROR; e->i = Q->elem[Q->front].i; e->j = Q->elem[Q->front].j; e->pre = Q->elem[Q->front].pre; Q->front++; return OK;}//DeQueueStatus QueueEmpty(SqQueue Q) /*若队列为空，则返回真*/{ if (Q.front == Q.rear) return TRUE; else return FALSE;}//QueueEmptyStatus GetHead(SqQueue Q, ElemType *e) /*若队列不空，用e返回队头元素*/{ if (QueueEmpty(Q)) {//如果队空 printf("The queue is empty!/n"); return ERROR; } *e = Q.elem[Q.front]; return OK;}//GetHead//file name:maze.h#ifndef MAZE_H#define MAZE_H#include "queue.h"#define M 12#define N 12#define SUCCESS 1#define FAIL 0typedef int Status;typedef struct { int x, y;}DType;Status ProduceArray(int ***, int, int); //动态生成一个二维数组Status ProduceMap(int **, int, int);//利用0 1随机数生成一张图(1为墙)Status PrintMap(int **, int, int, int, int);//打印迷宫图Status FindPath(int**, const int, const int); //寻找路线Status ShowShortPath(int**, int, int, SqQueue); //打印最短路#endif // !MAZE_H//file name:maze.cpp#include<stdio.h>#include<stdlib.h>#include<time.h>#include<Windows.h>#include"maze.h"#include"stack.h"Status ProduceArray(int ***array, int row, int col){ int i; *array = (int **)malloc((row + 2) * sizeof(int *)); for (i = 0; i < (row + 2); i++) { (*array)[i] = (int *)malloc((col + 2) * sizeof(int *)); } return SUCCESS;}/*生成一张图*/Status ProduceMap(int **MAZE,int row,int col){ int i, j; srand((unsigned)(time(NULL))); //随机种子 for (i = 0; i <= row + 1; i++) { for (j = 0; j <= col + 1; j++) { /*围墙的处理*/ if (i == 0 || j == 0 || i == (row + 1) || j == (col + 1)) MAZE[i][j] = 1; else { MAZE[i][j] = ((rand() % 10) > 6 ? 1 : 0);/*产生随机数,控制产生的概率*/ } } } /*入口和出口*/ MAZE[1][1] = MAZE[row][col] = 0; return SUCCESS;}//ProduceMapStatus PrintMap(int **MAZE, int row, int col,int cur_x,int cur_y){ system("cls"); int i, j; const char *BAR = "▓"; //障碍物图案"▓" const char *OBJ = "㊣"; //物体位置图案"㊣" for (i = 0; i <= row + 1; i++) { for (j = 0; j <= col + 1; j++) { if (MAZE[i][j] == 1) { //障碍物 printf(BAR); } else if (i == cur_x&&j == cur_y) { //移动对象 printf(OBJ); } else if (MAZE[i][j] == 0) //可通位置，2个空格 printf(" "); } printf("/n"); } printf("Current position:(%d,%d)/n/n", cur_x, cur_y); return SUCCESS;}//PrintMapStatus FindPath(int **MAZE, int row, int col) //寻找路线{ ElemType head, e; int x, y, i, j, k; SqQueue Q;//队列 static int **MARK;//标记数组 const DType Direction[8] = { { -1,-1 },{ -1,0 },{ -1,1 },{ 0,1 }, { 1,1 },{ 1,0 },{ 1,-1 },{ 0,-1 } }; ProduceArray(&MARK, row, col); MARK[0][0] = 0;//初始化为零 InitQueue(&Q);//队列的初始化 e.i = 1, e.j = 1, e.pre = -1;//起点位置 EnQueue(&Q, e);//将起点放入队列 MARK[1][1] = 1;//标记数组将起点标记为已通过 while(!QueueEmpty(Q)){//当队列不为空时 GetHead(Q, &head);//取出队头元素给head x = head.i, y = head.j; for (k = 0; k < 8; k++) { //依次探查各个方向 i = x + Direction[k].x; j = y + Direction[k].y; if (MAZE[i][j] == 0 && MARK[i][j] != 1) {//未通过且可行路 e.i = i, e.j = j, e.pre = Q.front; EnQueue(&Q, e);//将新的路放到队尾 MARK[x][y] = 1;//标记已走路 } if (i == row&&j == col) {//如果到达出口 ShowShortPath(MAZE, row, col, Q); return SUCCESS; } }//for end DeQueue(&Q, &head); }//while end //无法通过 return FAIL;}//FindPathStatus ShowShortPath(int **MAZE,int row,int col,SqQueue Q) //打印最短路线{ SqStack S; InitStack(&S); SElemType e; int cur_x, cur_y; int count = 0; DType Way[100]; int i = Q.rear - 1; while (i != -1) { Push(&S, Q.elem[i]); i = Q.elem[i].pre; } printf(">>>>One of the shortest way:/n"); while (!StackEmpty(S)) { Pop(&S, &e); cur_x = e.i, cur_y = e.j; Way[count].x = cur_x, Way[count++].y = cur_y; PrintMap(MAZE, row, col, cur_x, cur_y); Sleep(1000); } for (i = 0; i < count; i++) { printf("(%d,%d)/t", Way[i].x, Way[i].y); if ((i+1) % 5 == 0) printf("/n"); } printf("/n>>>>the shortest way need: %d steps/n/n",count); return SUCCESS;}//ShowShortPath//file name:main.cpp#include<stdio.h>#include<windows.h>#include"maze.h"int main(){ int row, col; int **MAZE; /*输入行和列生成迷宫图*/ printf("/n>>>Input the maze's row and column(row<11,column<11): "); scanf("%d%d", &row, &col); while (row <= 0 || row>10 || col <= 0 || col>10) { printf("Dataes error!Please input suitable dataes/n"); printf("/n>>>Input the maze's row and column: "); scanf("%d%d", &row, &col); } printf("/n>>>>>>>>>>A map is being created.../n"); Sleep(500); ProduceArray(&MAZE, row, col);//动态生成一个二维数组 ProduceMap(MAZE,row, col);//生成一张迷宫图 PrintMap(MAZE, row, col, 1, 1);//打印迷宫 printf("/n============>Finding the ways.../n"); printf(">>>Caculating the shortest way.../n"); Sleep(1000); if (FindPath(MAZE, row, col) == 0) { printf("Can not arrive!/n"); } system("pause"); return 0;}

最后说几句：1、个人觉得这个算法挺好的，当时老师要求的是自己定义几张图来测试有路和没有路的情况，但是通过这个来控制障碍物的方法只需要调一下产生的概率就好了如下面的“6”可以改大或改小，试试就知道了=_=