编译环境：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，否则返回FALSE
Status 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;elsereturn 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;elsereturn 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);//取出队头元素给headx = 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 endDeQueue(&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”可以改大或改小，试试就知道了=_=
#MAZE[i][j] = ((rand() % 10) > 6 ? 1 : 0);/产生随机数,控制产生的概率/#
2、这是用文件分离写的，直接复制粘贴不能运行！