2013级软件工程专业数据结构课程设计方案V10

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

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

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

4、流将该数组写入文件filename.huf中。（30分）（3）在上面程序的基础上，通过文件filename.huf解压文件file name. new,生产文件 file name.txt。（ 30 分）2. 全国交通咨询模拟问题描述处于不同目的的旅客对交通工具有不同的要求。例如，因公出差 的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费 尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。设计要求（1）提供对城市信息进行编辑（如：添加或删除）的功能（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻 表和飞机航班进

5、行编辑（增设或删除）的功能。（3）提供两种最优决策：最快到达和最省钱到达。全程只考虑 一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5） 咨询以用户和计算机的对话方式进行。 由用户输入起始站、 终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才 能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐 哪一趟列车或哪一次班机到何地。实现提示（1） 对全国城市交通图和列车时刻表及飞机航班表进行编辑，应 该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需 根据交通图给出各个路段的详细信息，例如：对

6、从北京到上海的火车， 需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、 到达 时间及票价等信息。（2）以邻接表作交通图的存储结构，表示边的结构内除含有邻接 点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发 和到达的时间等多种属性。（3）增加旅途中转次数最少的最优决策。3. 24点扑克牌游戏题目背景:一副牌中抽去大小王剩下 52张（如果初练也可只用110这40张牌），任意抽取4张牌（称牌组），用加、减、乘、除（可加括号） 把牌面上的数算成24。每张牌必须用一次且只能用一次，如抽出的 牌是 3、8、8、9,那么算式为（9-8） 8X3 或 3X8+ （9-8）或（9- 8 8）

7、 X3等。本题主要考查栈、集合、数组、递归、穷举等知识。可参考：http:/baike.baidu.eom/l in k?url=2KyoNLQJM9hd_KrFOTSNbwoN bbsM854nWlYHKe7qK61 YSiUZYeAsjORV oqsu81MteLCviY4Tf8CCX HG5 nWftTKhttp:/bbs.esd n.n et/topies/390499220http:/blog.si .c n/s/blog_5f3e269a0100dm5a.html http:/www.doei 版本1 :满分30分从52张牌中任意选取4张扑克牌，如下图，每张牌表示一个数 字输入由四

8、张被选择的扑克牌牌面的四个数字构成的一个表达式10*（8-6）+4，如下图点击验证按钮，显示消息:如输入的表达式为10+8+6-4,得不到正确的结果，显示消息:如输入的数据与纸牌数据不同，显示消息:点击刷新按钮，得到另外4张牌。版本2:满分40分如果存在多个解，显示这样的多个解。如解有：6+(8+1)*2, 8*(6-2-1),8, 6, 2, 1,可能的如果不存在解，显示无解消息。改进版本1，如果解存在，就显示该解L釦 21 Point Card G日mt?IFind d SuluUai(9* U>* 12/11Renesh由用户输入1到13之间的4个数，检查是否有解。rli¥

9、;)kilfour nurrb4rcbatw»An 1 to 13432(3+2+1 f4Fluid h Sillnrioiil- I 24-Poinl Qrd Gsme |l 24 Point Ordlnt> l numbers betwteii 1 to 1313 13 13 73No solutionfind a版本4:满分30分从52张牌中选择4张牌，这4张牌可能无解 从52张牌中选择4张牌的挑选次数是多少？ 在这些所有可能的选择中，有多少有解？Total nu mber of comb in ati ons is 270725Total nu mber of comb

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

11、的反面问题进一步解决其它结构的反面问题。版本3:满分30分修改硬币翻转规则，如规则改为对角线上的邻居被翻转，或者任意自定义的翻转规则。重新解决上述问题。5. 线性表、树、图的操作和演示(1)线性表：满分40分实现接口 MyList、抽象类MyAbstractList、基于顺序存储线性表 MyArrayList、基于链式存储的线性表 MyLinkedList。实现方式如下：给出MyArrayList和MyLinkedList操作的动画演示，如下图:Ent ET 3 VaXtiE thie adtsjxl$ Ecter wi index：:町Il >EltDe ±1eIntiD4

12、A xnde±!9| faisolTrimtaisuft实现栈MyStack和队列MyQueue。实现方式如下:给出MyStack和MyQueue的动画操作，如下图:Enter a value:6 巳少 | Pop But er a value：244 EngLiauE | PequiSMe树：满分20分设计实现二叉查找树，并以动画形式演示在其上的插入、查找、删除等操作。313懂Eo slonCnitaao"'nriDeriFijrXHziue：£Ht-并用动画方式显示无权图的深度优先遍历、广度优先遍历;图：满分40分设计 实现接口 Graph、抽象类 A

13、bstractGraph、具体类UnweightedGraph 和 WeightedGraph类。实现方式如下:诵紳圻# PFS TfrtSiarrijig Ciiyt |DFSTfer| SwchRt*ne*t11»111*1 U nweii b tcdGraphGraph Q. AbfracKjtaph QIIIIiIi»I1llntsrfiiccAbstract Clus*-WeiflhledGraph使用动画方式显示带权图的最小生成树、最短路径:Vhiihx hditie： K-Louidindte. jf<QQrdinatc;VHlnJf IJVei tex v liradexWeight (in*Starting Crt/tiding CrtfDisplay ShOElsst Aatn6. 模拟浏览器版本1满分（30分）编写程序，将一个Java文件转换为HTML 个文件。在HTML 文件中，关键字、注释和字面值分别用粗体的深蓝色、绿色和蓝色显 示。使用命令行参数传递Java文件和HTML文件。运行显示如下：/ This application program prints Welcome to Java public class Welcome