2012秋《数据结构课程设计》指导书-潘丽丽new.docVIP

《数据结构》指导书 中南林业科技大学 计算机与信息工程学院 软件工程教研室2012年月 成绩评定 =课程设计答辩（%）+%）＋课程设计报告（%）、要求上交的成果的内容必须由以下四个部分组成，缺一不可上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；上交程序的说明文件：（保存在.中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；课程设计报告：（保存在word 文档中，文件名要求 按照姓名-学号-课程设计报告起名，如文件名为张三-01-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；数据结构课程设计1) 问题描述 2) 基本要求 .1所示。 至少能够分析一个硬盘的磁盘结构，最好能自由显示磁盘所有扇区的数据。 图.1 建议的磁盘浏览器设计界面与功能 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 2 1 1 0 1 0 1 1 1 1 1 3 1 0 1 0 0 0 0 0 1 1 4 1 0 1 1 1 0 1 1 1 1 5 1 1 0 0 1 1 0 0 0 1 6 1 0 1 1 0 0 1 1 0 1 7 1 1 1 1 1 1 1 1 1 1  2) 基本要求 设计数据结构存储迷宫； 设计存储结构保存从入口到出口的通路； 设计算法完成迷宫问题的求解； 分析算法的时间复杂度。 3) 设计思想 可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的有哪些信誉好的足球投注网站方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都有哪些信誉好的足球投注网站到，或找到一条通路，或无路可走又返回到入口点。 在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。 可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向 v (0≤v≤7) 到达新点（i，j）的坐标：i=x+move[v].x ； j=y+move[v].y。 算法用伪代码描述如下： 1. 栈初始化； 2. 将入口点坐标(x , y)及该点的方向d（设为-1）入栈； 3. 当栈不空时循环执行下述操作： 3.1 (x , y , d)==栈顶元素出栈； 3.2 求出下一个要试探的方向d++ ; 3.3 沿顺时针试探每一个方向，执行下述操作： 3.3.1 如果方向d可走，则 3.3.1.1 将(x , y , d)入栈； 3.3.1.2 求新点坐标(i, j)； 3.3.1.3 将新点(i , j)切换为当前点(x , y)； 3.3.1.4 若(x, y)是终点，则算法结束； 否则，重置d=0； 3.3.2 否则，试探下一个方向d++； 3、 抽签游戏 1) 问题描述 抽签是我们日常生活中经常遇到的一件事，并且其形式有很多种。这里介绍一种抽签游戏，如图3.1所示，最上面一排是游戏的参加者——称为抽签者，最下面一排是签号（奖品、公差等）。每个人依次顺着竖线往下走，当碰到横线时，即转横向前进，碰到竖线再往下，以此类推，则游戏结束后，抽签者会一一对应到最下面一排的签号。 2) 基本要求 (1) 设计存储结构存储抽签者、签号、游戏用横线、竖线等； (2) 设计算法实现抽签； (3) 存储游戏的最终结果。 3) 设计思想 分析上面的抽签游戏的示例，遇到一条横线，代表这两个竖线的数据就要交换顺序，例如，原来的顺序为{A0, A1, A2, A3, A4}，经过第0层横线后，顺序为{A1, A0, A3, A2, A4}，再经过第1层横线后，顺序为{A1,A3,A0,A2,A4}，以此类推，最后顺序为{A4, A1, A0, A2, A3}，对应到{p0, p1, p2, p3, p4}。在该游戏中，需解决以下问题： (1) 抽签游戏可以多人参与，只要加上竖线和横线即可。那么，如何表示这些参与者呢？ 解决：假设有n个人参加，可以用一个一维数组A[n]来记录n个抽签者。 (2) 签号如何存储？ 解决：签号的存储也可设计成一个一