《数据结构与算法课程设计》任务书2014.doc

2014/2015学年第一学期 《数据结构与算法课程设计》任务书 一、课程设计目的 数据结构与算法课程设计是《数据结构》课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。 2.1 棋盘覆盖 【间题描述】 在一个2k×2k 个方格组成的棋盘中恰有一个方格与其它方格不同称该方格为一特殊方格且称该棋盘为一特殊棋盘在棋盘覆盖问题中要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格且任何2个L型骨牌不得重叠覆盖 （1）输入k以及特殊方格所在的行号dr和特殊方格的列号dc。 （2）要求输出每一步用什么形态L型骨牌覆盖 【实现提示】 使用分治策略，把棋盘划分成4个小棋盘，然后用一个L型骨牌覆盖将这4个小棋盘变为都具有特殊方格的棋盘。 2.2 Hanoi塔问题（*） 【问题描述】 设a，b，c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2,…,n，要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则（1）每次只能移动一个圆盘； 规则（2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上； 规则（3）在满足移动规则（1）和（2）的前提下，可将圆盘移至a，b，c中任一塔座上。 【基本要求】 （1）设计出Hannoi塔游戏，供用户玩； （2）提供正确的搬运方法。 【实现说明】 正确的搬运方法使用递归方法实现。 【测试数据】 2.3 矩阵连乘问题 【问题描述】 给定n个矩阵{},其中和是可乘的，i＝1,2,…,n-1。考察这n个矩阵的连乘积，通过加括号方式，找出矩阵乘积所需的最少计算量的方法。 【基本要求】 输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如。 【实现说明】 使用动态规划方法。 2.4 多边形游戏（*） 【问题描述】 多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“＋”或“*”。所有边依次用整数从1到n编号。 游戏第1步，将一条边删除。 随后n-1步按以下方式操作： 选择一条边E及由E连接着的2个顶点v1和v2； 用一个新的顶点取代边E及用E连接着的2个顶点v1和v2，将由顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点。 最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。 【基本要求】 设计该游戏供用户玩； 对于给定的多边形，给出最高得分计算。 【实现说明】 使用动态规划方法。 2.5 0-1背包问题 【问题描述】 给定n种物品和一背包。物品i的重量是，其价值为，背包的容量为c。问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大。 【基本要求】 使用动态规划、回溯法以及分支界限三种方法实现。 【测试数据】 【实现提示】 2.6 排序方法 【问题描述】 给定n个元素，要求对这n个元素进行排序。 【基本要求】 使用多种排序方法，越多越好； 比较每种排序方法的时间复杂度和空间复杂度。 【测试数据】 【实现提示】 2.7 哈夫曼编码译码器 【问题描述】 设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件 （压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。 【基本要求】 （1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树； （2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod） （3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。 【实现说明】 （1）在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、循环单链表、双向链表、循环双链表； （2）在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级； （3）二叉树本身也可以用静态数组模拟； （4）使用贪心算法 2.8 迷宫问题（*） 【问题描述】 设计一个迷宫并给出正确走法。如： 001111111111111 100011111111111 101100001111111 100011100000111 111011111110001 111000000001001 111000000011100 其中0表示可以走，1表示不能走，每一步只能向上下左右移动。 【基本要求】 （1）给出迷宫的正确走法，包括没有解的情况； （2）要求