《数据结构课程设计09级.docVIP

计算机09级 《数据结构课程设计》任务书 课程设计的性质和目的 数据结构课程设计是计算机专业的专业课程，通过课程设计使学生进一步巩固课堂所学知识，全面熟悉、掌握数据结构的基本设计方法和技巧，进一步提高分析问题、解决问题及上机操作能力，为将来从事计算机工作打下一定的专业基础。 设计课题 课题一：迷宫问题 详细内容见后 课题二：马踏遍棋盘问题 详细内容见后 课题三：表达式求值问题 详细内容见后 课题四：B+树的实现 详细内容见后 课程设计报告要求 课程设计报告每人一份，必须包含如下几个方面的内容： 基本设计思想； 主要数据结构； 主要实施流程； 所有源代码； 课程设计总结与体会。 分组及选题办法 一人一组。 若选择课题四，则只需完成一题即可；否则，必须至少完成前三个课题中的任意两个。 成绩考核按个人课题完成情况、设计报告质量及对课程设计的态度等综合评定。 五、设计进度安排 讲课及上机调试时间安排： 各班具体时间另行安排 其余时间：查阅资料，确定方案，设计课题相关程序。 分组答辩，交课程设计报告。 设计课题一：迷宫问题 一、问题描述： 以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的可通的方块和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通道，或得出没有通道的结论。 二、基本要求： 用计算机模拟“迷宫问题”，求出其中一条通道。用数组MAZE[1..M][1..N]表示迷宫，有的可以通行（0表示），有的是路障（1表示），MAZE[1][1]为迷宫入口,MAZE[M][N]为迷宫出口,用非递归算法求出一条通路并用“■”标示所输出的路径(见运行示例)否则说明没有通路,继续生成迷宫,直到有通路。 三、测试数据及运行示例： 下面是利用一随机函数生成的0/1方阵及运行示例: 四、算法提示： 实现这一算法的具体方法很多（如堆栈,队列等）,但基本思想一般是回溯法使用MAZE[M][N]表示迷宫（如图２），为判定过程中是否越界，在其外围加一圈１作为路障，mark[M][N]作为标志数组，move[8][2]是行列增量数组（见图１-２）；建堆栈．约定（i,j）表示i行j列,direction 表示方向, 从入口开始探索路径：沿０-7八个方向依次试探，若某方向可通（为０），则该点连同方向入堆栈，从该点继续试探；若八个方向都不通，则取出堆栈顶点，从其标记的方向开始试探其余方向；直至找到出口（有通路）或堆栈为空(没有通路)。 设计课题二：马踏遍棋盘问题 一、问题提出 　　设计一个国际象棋的马踏遍棋盘的演示程序 二、基本要求 　　将马随机放在国际象标的8*8棋盘Board[8][8]某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1、2、……、64依次真入一个8*8的方阵，输出之。 三、测试数据 　　由自己批定。可自行指定一个马的初始位置（i,j），０≤i,j≤7。 四、实现提示 下图显示了马位于方格（2，3）时，8个可能的移动位置。 一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 7 3 4 5 4 5 6 7 (i-2,j+1)、（i-1,j+2）、(i+1,j+2)、(i+2,j+1) (i+2,j-1)、(i+1,j-2)、(i-1,j-2)、(i-2,j-1) 但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能位置可以用两个一维数组Htry1[0..7]和Htry2[0..7]来表示： 0 1 2 3 4 5 6 7 Htry1 -2 -1 1 2 2 1 -1 -2 0 1 2 3 4 5 6 7 Htry2 1 2 2 1 -1 -2 -2 -1 位于(i,j)的马可以走到的新位置是在棋盘范围内的(i+Htry[h],j+Htry2[h]),其中h=0,1,2,…,7。 每次在多个可走位置中选择其中一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。 设计课题三：表达式求值问题 一、问题提出 在高级语言程序中出现的数学表达式要进行求值运算，本课程设计要求模拟编译程序