云南大学软件学院数据结构实验报告
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □
序号学号姓名成绩
1
2
3
指导教师（签名）
学期：
任课教师:
实验题目: 实验四数组的表示及其应用
小组长:
联系电话:
电子邮件:
完成提交时间：年月日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：姓名：本人承担角色：课题分析，算法设计，程序编写，后期调试，完成实验报告
综合得分：（满分100分）
指导教师：年月日
（注：此表在难度为C时使用，每个成员一份。）
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：姓名：本人承担角色：课题分析，算法设计，后期调试
综合得分：（满分100分）
指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）
（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)
（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）
本次实验，我们小组制作了一个具有一定可玩度的迷宫游戏，利用了随机数生成代码的方式生成了一个每次运行程序都不一样的迷宫。
主要算法：构造一个树，在地图中的一个指定位置（由游戏难度决定）设定一个起始点，将这个地图的序号为奇数的点看为一个个节点，将起始点看作树的根，然后取系统的时钟信号，生成一个伪随机数，用来随机地生成地图，当这一个树构造完毕，即遍历完所有的目标点位后，一个比较规则的迷宫也就建成了，从起点到终点有且只有一条路。
主要子程序：键盘监听程序：利用一个文本框来监听键盘，响应一系列键盘的事件，此子程序一直在后台运行，随时保持监听状态。
二、【实验设计(Design)】(20%)
（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
namespace 实验四迷宫第三次尝试 //调用本程序的命名空间
{
public partial class Form1 : Form //定义一个窗口类
{
public Form1() //窗口1的构造函数，用于初始化某些控件
private void button1_Click(object sender, EventArgs e) //当用户点下“开始游戏”按钮的响应事件
public void CreatMaze() //创造并显示一个合法的迷宫
public void ToNorth() //控制小人向上方走一步
public void ToSouth() //控制小人向下方走一步
public void ToEast() //控制小人向右边走一步
public void ToWest() //控制小人向左边走一步
public void IfArrive() //判断小人是否到达终点
public void dista() //计算小人与终点之间的距离
public void keyup() //当用户按下向上箭头的时间
public void keydown() //当用户按下向下箭头的时间
public void keyright() //当用户按下向右箭头的时间
public void keyleft() //当用户按下向左箭头的时间
private void button2_Click(object sender, EventArgs e) //当用户点击帮助按钮时的响应事件 private void button3_Click(object sender, EventArgs e) //当用户点击关于按钮时的响应事件 private void textBox1_KeyDown(object sender, KeyEventArgs e) //监听键盘输入子程序
}
public partial class Form2 : Form //定义一个窗口类
{
public Form2() //窗口2的构造函数，用于初始化相关的函数和控件
private void button1_Click(object sender, EventArgs e) //当用户点击确认按钮时的响应事件
private void radioButton1_CheckedChanged(object sender, EventArgs e) //用户选择大师级难度的响应事件
private void radioButton2_CheckedChanged(object sender, EventArgs e) //用户选择高手级难度的响应事件
private void radioButton3_CheckedChanged(object sender, EventArgs e) //用户选择标准级难度的响应事件
private void radioButton4_CheckedChanged(object sender, EventArgs e) //用户选择低手级难度的响应事件
private void radioButton5_CheckedChanged(object sender, EventArgs e) //用户选择菜鸟级难度的响应事件
}
}
三、【实现描述（Implement）】(30%)
（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）
深度优先遍历算法：深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。
将这个算法运用到迷宫中即：
将所有的点位全部设置为“墙”，只保留一个其实点位为“路”，然后利用深度优先算
