课程设计报告：迷宫.doc

课 程 设 计 报 告 学 院： 计算机学院 课程名称： 数据结构 专业班级： 2011级计算机科学与技术 学生姓名： 朱振飞 学号： 13 学生姓名： 李勇发 学号： 53 指导教师： 白 伟 华 完成时间：2012年6月25日 目 录（4号黑体字，居中排版） 1 迷宫问题 1 1.1 概述 1 1.2 实验内容 1 1.3 概要设计 1 1.4 调试分析 4 1.5 源程序代码 5 4号黑体字） 1.1 概述（小4号黑体字，段前段后0.5行，以下相同） 本课程设计利用的，问题。4号宋体，英文及数字小4号Times New Roman 字体，行距为固定值20磅，以下相同） 使用语言：C语言 编译环境：VC++ 6.0 4号黑体字，段前段后0.5行，以下相同） 1、问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 基本要求： （1）实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 （2）编写递归形式的算法，求得迷宫中所有可能的通路； （3）以方阵形式输出迷宫及其通路。 2、需求分析 （1）以非递归方法求出一条迷宫通路。 （2）以递归方法求出所有迷宫通路。 （3）以方阵输出迷宫和1、存储结构{ int arry[maxsize][maxsize]; //定义迷宫数组 int max_x,max_y; //迷宫的行列数 }sd; typedef struct point //结点结构定义 { int vex_x,vex_y; //结点坐标 struct point * next; // 指向下一结点的指针 int direction; //下一结点的方向 }Point; 2、函数Point * secret(sd a) //迷宫函数 void disp(Point *po) //输出函数 void main() //主函数 3、流程图 enter row and lie: 3 4 enter 1 row：0 0 1 0 enter 2 row：1 0 0 1 enter 3 row：1 1 0 0 输出：1,1,11,2,22,2,12,3,23,3,13,4,0 1.5 源程序代码 #includestdio.h #includemalloc.h #define maxsize 100 #define NULL 0 typedef struct //迷宫定义 { int arry[maxsize][maxsize]; //定义迷宫数组 int max_x,max_y; //迷宫的行列数 }sd; typedef struct point //结点结构定义 { int vex_x,vex_y; //结点坐标 struct point * next; // 指向下一结点的指针 int direction; //下一结点的方向 }Point; sd creat() //迷宫创建函数 { int i,j; sd a; //定义一个迷宫a printf(enter row and lie:); scanf(%d %d,a.max_x,a.max_y); //输入此迷宫的“行”数和“列”数 for(i=1;i=a.max_x;i++) //用两个for循环完成迷宫信息的输入 { printf(enter %d row :,i); for(j=1;j=a.max_y;j++) scanf(%d,a.arry[i][j]); //0通1阻 } return a; } int found(int x,int y,Point * head) //结点判断函数 { Point *p=head; while(p!=NULL) { if(x==p-vex_xy==p-vex_y) //结点存在，返回1 return 1; p=p-next; } return 0; //否则返回0 }