"迷宫求解算法设计"
数据结构课程设计报告班级:计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