迷宫问题求解.doc

山东理工大学计算机学院
课程设计
(数据结构)
班级
姓名
学号
指导教师
二○一一年一月二十日
课程设计任务书及成绩评定
课题名称
迷宫问题求解
Ⅰ、题目的目的和要求:
1、设计目的
巩固和加深对数据结构的理解,通过上机实验、调试程序,加深对课本知识的理解,最终使学生能够熟练应用数据结构的知识写程序。
(1)通过本课程的学习,能熟练掌握几种基本数据结构的基本操作。
(2)能针对给定题目,选择相应的数据结构,分析并设计算法,进而给出问题的正确求解过程并编写代码实现。
2、设计题目要求:
问题描述:求迷宫中从一个入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路返回,换一个方向再继续探索,直到所有可能的通路都探索到为止;假如所有可能的通路都探索到而未能到达出口,则所假定的迷宫没有解。
基本要求:首先实现一个以链表作存储结构的栈的类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向,可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出。栈是一个后进先出的结构,可以用来保存从入口到当前位置的路径。
以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(n,n)。为处理方便起见,在迷宫的四周加一圈障碍。对于迷宫任何一个位置,均约定东、南、西、北四个方向可通。
Ⅱ、设计进度及完成情况
日期
内容
-
选取参考书,查阅有关文献资料,完成资料搜集和系统分析工作。
~
创建相关数据结构,录入源程序。
~
调试程序并记录调试中的问题,初步完成课程设计报告。
~
上交课程设计报告打印版并进行课程设计答辩,要求每个同学针对自己的设计回答指导教师3-4个问题。
考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。
Ⅲ、主要参考文献及资料
[1] 严蔚敏数据结构(C语言版)清华大学出版社 1999
[2] 严蔚敏数据结构题集(C语言版)清华大学出版社 1999
[3] 谭浩强 C语言程序设计清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定:
设计成绩: (教师填写)
指导老师: (签字)
二○一一年一月二十一
目录
第一章概述 1
第二章系统分析 2
第三章概要设计 4
第四章详细设计 7
第五章运行与测试 13
第六章总结与心得 16
参考文献: 17
第一章概述
课程设计是实践性教学中的一个重要环节,它以某一课程为基础,可以涉及和课程相关的各个方面,是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用,理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课,是计算机理论和应用的核心基础课程。
数据结构课程设计,要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面,加深对课程基本内容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
本次课设我选择了迷宫问题,迷宫求解是数据结构课程的一个经典问题。
迷宫问题要求寻找一条从入口到出口的路径。即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前走;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路,通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解,所以选择了迷宫这一经典问题作为本次课设的内容。
第二章系统分析
求迷宫中从一个入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路返回,换一个方向再继续探索,直到所有可能的通路都探索到为止;假如所有可能的通路都探索到而未能到达出口,则所假定的迷宫没有解。
迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求解迷宫通路的算法中要应用“栈”的思想。
1:基本原理分析
迷宫问题通常是用“穷举求解”方法