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

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