软件工程专业数据结构课程设计方案V1.

1、2013 级软件工程专业数据结构课程设计方案V1.0一、课程任务要求独立完成一个或多个较为完整的应用需求分析，在完成设计和编程大型作业的过程中， 深化对数据结构课程中概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高；经过查找参考资料、 技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。二、具体要求1. 每人应至少独立完成一道题目并撰写课程报告， 具体题目由任课老师组织分配，题目一旦选定，未经老师同意，不得私自更换，否则总评成绩为缺成绩。2. 按时出勤，旷课 2 次直接取消答辩资格， 旷课 1 次总评成

2、绩降低 1 个等级。3. 听从值班老师安排，按所选题目分区坐在指定位置。4. 按时提交课程设计资料，未按格式或未在规定时间提交资料的，总评成绩为缺成绩。三、具体安排1. 时间： 18 周周一至周五上午、下午2. 地点： 4-312（1、2、3 题）、4-313（4、5、6 题）3. 答辩时间： 19 周周 1 上午、下午4. 课程设计具体考核标准和流程由题目指导老师负责。四、课程设计题目与内容1. 数据压缩与解压缩利用哈夫曼编码完成数据的压缩与解压缩，具体要求如下：（ 1）哈夫曼编码的动画显示，程序运行界面如下：（ 40 分）在上面文本框中输入待编码的字符串， 点击 “Show Huffman

3、 Tree按”钮输入，生成哈夫曼树并显示该字符串的哈夫曼编码。如下图所示：在下面文本框中输入二进制哈夫曼串， 点击 “Decode Text，”能够还原为原来的字符。比如输入 001 显示 w ，输入 01001 显示 ow ，如下图所示：（ 2）在上面程序的基础上，编写程序，在控制台或 GUI 中输入文件名（如 filename.dat)，通过哈夫曼数据压缩算法生成 filename.new,同时，使用数组存储每个字符哈夫曼编码， 通过对象输出流将该数组写入文件 filename.huf 中。（ 30 分）（ 3）在上面程序的基础上，通过文件filename.huf 解压文件filename

4、.new，生产文件 filename.txt。（30 分）2. 全国交通咨询模拟 问题描述 处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 设计要求 （1）提供对城市信息进行编辑（如：添加或删除）的功能。（ 2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。（ 3）提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。（ 4）旅途中耗费的总时间应该包括中转站

5、的等候时间。（ 5）咨询以用户和计算机的对话方式进行。 由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达， 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 实现提示 （1）对全国城市交通图和列车时刻表及飞机航班表进行编辑， 应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息， 例如：对从北京到上海的火车，需给出北京至天津、 天津至徐州及徐州至上海各段的出发时间、 到达时间及票价等信息。（2）以邻接表作交通图的存储结构， 表

6、示边的结构内除含有邻接点的信息外，还应包括交通工具、 路程中耗费的时间和花费以及出发和到达的时间等多种属性。（3）增加旅途中转次数最少的最优决策。3. 24 点扑克牌游戏题目背景：一副牌中抽去大小王剩下52 张（如果初练也可只用110 这 40张牌），任意抽取 4 张牌（称牌组），用加、减、乘、除（可加括号）把牌面上的数算成24。每张牌必须用一次且只能用一次，如抽出的牌是 3、8、8、9，那么算式为 （9-8）83 或 38+（9-8）或（9- 8 8）3 等。本题主要考查栈、集合、数组、递归、穷举等知识。可参考：/link?url=2KyoNLQJM

7、9hd_KrFOTSNbwoNbbsM854nWlYHKe7qK61YSiUZYeAsj0RV oqsu81MteLCviY4Tf8CCXHG5nWftTK/topics/390499220/s/blog_5f3e269a0100dm5a.html/p-364720041.html版本 1：满分 30 分从 52 张牌中任意选取4 张扑克牌，如下图，每张牌表示一个数字输入由四张被选择的扑克牌牌面的四个数字构成的一个表达式10*(8-6)+4 ，如下图点 按 ， 示消息：如 入的

8、表达式 10+8+6-4，得不到正确的 果， 示消息：如 入的数据与 牌数据不同， 示消息：点 刷新按 ，得到另外4 牌。版本 2： 分 40 分改 版本 1，如果解存在，就 示 解。如果存在多个解， 示 的多个解。如 8，6，2， 1，可能的解有： 6+(8+1)*2 ，8*(6-2-1) ，如果不存在解， 示无解消息。由用户输入 1 到 13 之间的 4 个数，检查是否有解。版本 4：满分 30 分从 52 张牌中选择 4 张牌，这 4 张牌可能无解。从 52 张牌中选择 4 张牌的挑选次数是多少？在这些所有可能的选择中，有多少有解？Total number of combinations

9、 is 270725Total number of combinations with solutions is 217781 The solution ratio is 0.8044362360328747成功的几率是多少？编程求解上述问题。4. 16 枚硬币的反面问题题目背景：教材中的 9 枚硬币问题使用的是 3*3 的矩阵，假设在一个 4*4 的矩阵中放置了 16 枚硬币。该问题可进一步变化为如 2*3， 2*4，3*4等等任意结构的情形。本题主要考查对图的结构和图的广度优先遍历操作的掌握。版本 1：满分 30 分参考 9 枚硬币反面问题的模型， 建立 16 枚硬币反面问题的模型，以及其

10、他结构的模型。版本 2：满分 40 分参考 9 枚硬币反面问题的解决方法， 解决 16 枚硬币的反面问题。进一步解决其它结构的反面问题。版本 3：满分 30 分修改硬币翻转规则， 如规则改为对角线上的邻居被翻转，或者任意自定义的翻转规则。重新解决上述问题。5. 线性表、树、图的操作和演示(1)线性表：满分 40 分实现接口 MyList 、抽象类 MyAbstractList 、基于顺序存储线性表MyArrayList 、基于链式存储的线性表MyLinkedList 。实现方式如下：给出 MyArrayList 和 MyLinkedList 操作的动画演示，如下图：实现栈 MyStack 和队

11、列 MyQueue。实现方式如下：MyStackMyArrayListMyQueueMyLinkedList给出 MyStack 和 MyQueue 的动画操作，如下图：(2)树：满分 20 分设计实现二叉查找树，并以动画形式演示在其上的插入、查找、删除等操作。(3)图：满分 40 分设 计 实 现 接 口Graph 、 抽 象 类AbstractGraph 、 具 体 类UnweightedGraph 和 WeightedGraph类。实现方式如下：并用动画方式显示无权图的深度优先遍历、广度优先遍历；使用动画方式显示带权图的最小生成树、最短路径：6. 模拟浏览器版本 1：满分（分）编写程序，将一个 Java文件转换为 HTML 一个文件。在 HTML 文件中，关键字、 注释和字