数据结构课程设计-迷宫求解

数据结构课程设计

迷宫求解

学院：湖北工业大学计算机学院

教师：沈华老师

班级：12网络工程1班

学号：1210322118

姓名：饶进阳

时间：2013年12月22日

目 录

问题描述 ......................................................... 2

思路解析 .........................................................

程序流程 .........................................................

核心代码 .........................................................

源程序代码 ........................................................

程序运行实例 .....................................................

课设总结 .........................................................

3 4 5 6 12 14

1

迷宫求解

问题描述：

可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； 要求：

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

比如这是一个迷宫

电脑找出的出路

2

思 路

设定当前位置的初值为入口位置： do｛

若当前位置可通， 则｛

将当前位置插入栈顶；} 若该位置是出口位置，则结束；

否则切换当前位置的东邻块为新的当前位置； 否则｛

若栈不空且栈顶位置还有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；} 若{

栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；} 若{

栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；｝ ｝while(栈不空)

｛栈空说明没有路径存在｝

PS：类似动态求解方法 3

程序流程

第一次用visio做程序框图，所以只把程序的大概流程画出来了。

4

核心代码

//栈相关操作 int initlStack(Stack *S)

int pushStack(Stack S, coordinate e) int popStack(Stack S, coordinate *e) int getTop(Stack S, coordinate *e) void show(Stack S)

//创建一个迷宫 int creatMaze(Maze *m)

//打印出一个迷宫 void showMaze(Maze *m)

//求当前结点的下一个通路

coordinate passNext(Maze *m, int i, int j) //求迷宫路径

int solveMaze(Maze *m, Stack S) //模拟出路径

void showRoad(Maze m, Stack S) 5

程序源码：

#include #include

#define MAX 100

#define SIZE sizeof(Node)

//**************************** //栈

typedef struct { int x;//行 int y;//列 }coordinate;//坐标

typedef struct node{ coordinate data; struct node *next; }Node, *Stack;

//栈的相关操作

//栈初始化

//带头结点的链栈

int initlStack(Stack *S) { (*S) = (Node *)malloc(SIZE); if((*S) == NULL) { return 1; } (*S)->next = NULL; return 0; }

//入栈

int pushStack(Stack S, coordinate e) { Node *p; p = (Node *)malloc(SIZE); p->data.x = e.x; p->data.y = e.y; p->next = S->next; S->next = p; return 0;

}

//出栈

int popStack(Stack S, coordinate *e) { Node *p; if(S->next == NULL) { printf(\ return 2; } e->x = S->next->data.x; e->y = S->next->data.y; p = S->next; S->next = p->next; free(p); return 0; }

//读取栈顶

int getTop(Stack S, coordinate *e) { e->x = S->next->data.x; e->y = S->next->data.y; return 0; }

//显示

void show(Stack S) { Node *p; p = S->next; while(p != NULL) { printf(\ p = p->next; } printf(\}

//***************************

//*************************** //迷宫

typedef struct { int row; int col; int arr[MAX][MAX]; }Maze;

//创建一个迷宫

int creatMaze(Maze *m) { int i, j; printf(\ scanf(\ printf(\ for(i = 0; i <= MAX - 1; i++) { for(j = 0; j <= MAX - 1; j++) { m->arr[i][j] = 1; } } for(i = 1; i <= m->row; i++) { for(j = 1; j <= m->col; j++) { scanf(\ } } return 0; }

//显示迷宫信息

void showMaze(Maze *m) { int i, j; printf(\ for(i = 1; i <= m->row; i++) { for(j = 1; j <= m->col; j++) { printf(\ } printf(\ } printf(\ for(i = 1; i <= m->row; i++) { for(j = 1; j <= m->col; j++) { if(m->arr[i][j] != 0) { printf(\■ \ } else { printf(\□ \ } } printf(\ } }

//求当前结点的下个通路 //顺时针找

coordinate passNext(Maze *m, int i, int j) { coordinate k; if(m->arr[i][j+1] == 0) {//东 k.x = i; k.y = j+1; return k; } if(m->arr[i+1][j] == 0) {//南 k.x = i+1; k.y = j; return k; } if(m->arr[i][j-1] == 0) {//西 k.x = i; k.y = j-1; return k; } if(m->arr[i-1][j] == 0) {//北 k.x = i-1; k.y = j; return k; } else {//不存在 k.x = -1; k.y = -1; return k; } }

//求解迷宫

int solveMaze(Maze *m, Stack S) { int i, j; int boolean; coordinate a; i = 1; j = 1; do { if(m->arr[i][j] == 0) { a.x = i; a.y = j; m->arr[i][j] = 2; pushStack(S, a);

本文来源：https://www.bwwdw.com/article/b9t.html