"迷宫求解算法设计"
数据结构课程设计报告班级:计HR07—7姓名:顾仁杰学号:0720010705 2009年01月07日
概要:
本报告主要介绍迷宫求解算法设计,使用栈数据结构来解决迷宫问题。通过分析迷宫矩阵,寻找一条路径,并将其输出。该算法设计了一个结点结构,用来存储迷宫元素,并定义了pop()函数和push()函数来实现栈的操作。
需求分析:
* 输入形式:迷宫矩阵
* 输入值范围:0或1
* 输出形式:路径(倒序输出)或“No Answer !!!”
* 程序功能:判断迷宫可否走通,若走通输出路径,走不通输出“No Answer !!!”
概要设计:
1. 数据结构:使用栈数据类型,走通则压入栈,走不通则出栈。
2. 程序模块:
* 定义结点结构用来存储迷宫元素
* 定义pop()函数和push()函数来实现栈的操作
3. 各模块之间的调用关系:
* 在main()函数中,判断当前结点上下左右是否存在可通路径
* 若有则压入栈中,并将此点标志为1,即已走过,避免重复
* 若当前结点无通路,则出栈,返回到上一节点,继续判断是否可通
详细设计:
void main() {
while(row!=6||col!=9) {
if(a[row][col+1]==0) {
col=col+1;
push(row,col);
a[row][col]=1;
continue;
}
if(a[row-1][col]==0) {
row=row-1;
push(row,col);
a[row][col]=1;
continue;
}
if(a[row][col-1]==0) {
col=col-1;
push(row,col);
a[row][col]=1;
continue;
}
if(a[row+1][col]==0) {
row=row+1;
push(row,col);
a[row][col]=1;
continue;
}
pop();
if(p->next==NULL)break;
row=p->row;
col=p->col;
}
if(row==6&&col==9) {
while(p!=NULL) {
printf("%d %d\n",p->row+1,p->col+1);
pop();
}
} else {
printf("No Answer !!!");
}
}
测试与分析:
若迷宫有多条路径,则只输出其中一条。测试结果为路径(此路径为倒序),若不是通路,则测试结果为“No Answer !!!”。
总结:
通过这次课程设计,我更加了解栈的应用,栈的先进先出的特点,在解决迷宫问题上,非常方便!走不通可以随时后退,即出栈;走通又可以随时前进,即入栈,在以后解决实际问题上,我又多了一种实用的思想。
附录:
#include "stdio.h"
#include "stdlib.h"
struct node {
int row;
int col;
struct node *next;
};
1