数据结构设计.doc

数 据 结 构 课程设计报告书 班级 计算机121 学号 1208010128 姓名 郑晶 指导老师 刘勇 目录 一．课程设计的目的和任务……………………………………………………………………3 二、课程设计名称：迷宫的求解问题…………………………………………………………3 问题的描述……………………………………………………………………………………3 基本要求………………………………………………………………………………………3 算法思想………………………………………………………………………………………3 需要解决的问题………………………………………………………………………………3 模块划分………………………………………………………………………………………3 源程序为………………………………………………………………………………………3 测试结果为……………………………………………………………………………………4 三、课程设计名称：生死者游戏………………………………………………………………7 问题的描述……………………………………………………………………………………7 问题的解决方法………………………………………………………………………………7 模块划分………………………………………………………………………………………8 函数之间的调用关系…………………………………………………………………………8 程序包含的函数………………………………………………………………………………8 源程序为………………………………………………………………………………………8 程序的运行结果为……………………………………………………………………………10 四、课程设计的名称：二叉树基本操作的实现………………………………………………10 问题的描述……………………………………………………………………………………10 源程序为………………………………………………………………………………………10 测试结果为……………………………………………………………………………………14 五、课程设计的名称：图的基本操作的实现…………………………………………………15 问题的描述为…………………………………………………………………………………15 源程序为………………………………………………………………………………………15 测试结果为……………………………………………………………………………………19 六、二叉排序树的设计与实现以及快速排序算法的实现……………………………………20 问题的描述为…………………………………………………………………………………20 源程序为………………………………………………………………………………………20 测试结果为……………………………………………………………………………………25 一、课程设计的目的和任务： 使学生进一步理解和掌握课程上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本技能 二、课程设计名称：迷宫的求解问题 问题的描述： 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。 求解迷宫问题，即找出从入口到出口的路径。 基本要求： 建立一个大小为m*n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来； 找出一条通路的二元组（i，j)数据序列，（i,j）表示通路上某一点的坐标 在屏幕上输出迷宫和通路 算法思想： 采用回溯法， 回溯法是一种不断试探且及时纠正错误的有哪些信誉好的足球投注网站方法。本问题可从入口出发，按某一方向向未走过的前方探索，若能走通，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 这也是一种“穷举求解”的方法。 需要解决的问题： 表示迷宫的数据结构 试探方向 （3）栈的设计 （4）防止重复到达某点，避免发生死循环 5、模块划分： （1) 表示一个m行n列迷宫 用maze[m][n]表示，0=im,0=jn maze[i][j]=0; 通路 Maze[i][j]=1; 不通 迷宫的定义： #define