数据结构。课程设计报告。
设计题目：迷宫求解。
专业机电一体化
班级 08专接本
学生。学号 1
指导教师高在村。
完成时间 2011. 5
一。实验内容 3
二。需求分析 3
三．总体设计 3
四．详细设计 5
五．** 9
六。测试 14
七。 总结 16
参考文献 17
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
要求：界面友好，函数功能要划分好；总体设计应画一流程图；程序要加必要的注释；要提供程序设计方案；程序一定要经得起测试；宁可功能少一点，也要能运行起来，不能运行的程序是没有价值的。
1.可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
要求：使用非递归算法。
2.用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立自己的迷宫；
3.用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了；
4.程序执行的命令包括：
（1）构造栈stack, t 描述迷宫中当前位置的结构类型， linknode链表结点三个类，其中stack是linknode的友元类。
2）构造存取迷宫的二维指针getmaze(int &m,int &n)
3）恢复迷宫restore(int **maze,int m,int n) （
4）在迷宫中寻找一条通路mazepath(int **maze,int m,int n)
5）输出所找到的通路printpath()
6) 定义当前位置移动的4个方向move数组。
存储结构：首先用二维指针存储迷宫数据，迷宫数据由用户输入。
一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。
1．从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。
经过的位置把0变为-1，带输出迷宫路径后在恢复迷宫院士为止。
2. 本程序有三个模块：
主程序模块。
三个类模块即其对象：实现栈链表抽象数据类型；
迷宫二维指针单元模块：存储迷宫，寻路径，输出迷宫，恢复迷宫。
二)流程图。
一).基本算法：
首先用二维指针存储迷宫数据，迷宫数据由用户输入。
一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。
迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。
每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。
用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。
二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；其余元素值用getmaze函数获取。
假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。
如果用二维数组move记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定：
x=x+move[loop][0]
y=y+move[loop][1]
从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。定义一个栈，按从入口到出口存取路径。
在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中，当前位置”-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。
如果没有新位置入栈，则返回到上一个位置。
到达出口后，最后一个位置入栈，输出路径，并回复路径。把-1变为0.
总之，入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。
二). 为实现算法，需要类的象数据类型：
类及其对象：
类 stack对象成员如下：
stack构造函数，置空栈操作结果：构造一个空的栈s。
stack析构函数
void push(t e); 把元素data压入栈中。
t pop使栈顶元素出栈。
t getpop取出栈顶元素。
void clear();把栈清空。
bool empty();判断栈是否为空，如果为空则返回1，否则返回0
t类迷宫中当前位置的结构类型：
t对象成员如下：
xx代表当前位置的行坐标。
yy代表当前位置的列坐标。
dir0:无效，1:东，2:南，3:西，4:北。
linknode类链表结点：
对象成员如下：
友元类 stack
t data
linknode *next
三).函数调用关系。
maingetmazemazepath
empy() getpop() push() printpath() restore()
popgetpoppush()
四) 算法的时间、空间复杂度。
1）本算法在空间上主要开辟了一个二维指针，规模都是迷宫(m+2)*(n+2)，一个是栈，一个是迷宫路径记录，输出时候调用栈，在恢复迷宫。
2）在时间上为简单的链表栈的存储结构，二维指针getmaze, restore两函数算法时间复杂度为o（(m+2)*(n+2)）,mazepath,printpath为o(1),（m为行数，n为列数）。
五) uml图。
*以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
c数据结构课程设计
重庆大学信息科学与工程学院。实验报告。课程名称 数据结构。实验名称 宿舍管理查询软件。专业 计算机科学与技术。班级 姓名 时间 2011年7月1日。1 实验内容。1 任务 为宿舍管理人员编写一个宿舍管理查询软件，程序设计要求 a.采用交互工作方式。b.建立数据文件 数据文件按关键字 姓名 学号 房号...
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...