20121-《数据结构集中上机》任务书1.doc

《数据结构集中上机》任务书 教学目的及基本要求 1．了解并掌握数据结构的设计方法，具备初步的独立分析和设计能力；2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 1．问题分析和任务定义。2．逻辑设计。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3．物理设计。定义相应的存储结构并写出各函数的伪码算法详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。．程序编码。．程序调试与测试。．结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。．编写设计报告。 简述存储结构和算法的基本思想。 列出调试通过的源程序。 列出上面程序对应的运行结果。 分析程序的优缺点、时空性能以及改进思想，写出心得体会。 三、成绩评定 ： 课程设计的成绩评定以选定课题的难易度、完成情况和设计报告为依据综合评分，设计报告占30％，设计作品占70％ 1． 公交车线路查询系统 2 2． 扑克游戏程序 3 3． 文本文件压缩： 3 4． 移动数字游戏 3 5． 排序算法性能分析 9 6． 散列表实现学生情况表 9 7． 三件有制约关系物品过河问题 10 8． 设计和实现多项式运算 10 9． 迷宫求解 10 10． 运动会分数统计 10 11． 订票系统 10 12． 文章编辑 11 13． 停车场管理 11 14． 校园导游咨询 12 公交车线路查询系统 问题描述 设计一个公交车线路查询系统，为用户提供最优乘车路线查询。 基本要求 （1）具有良好的用户界面 （2）自定义公交车、车站、路线等信息的逻辑结构，并实现文件存储 （2）公交车线路不少于5条，每条公交车站不少于10个 （3）支持用户提供最短距离路线（含换乘信息）查询 （4）支持用户提供最快速度路线（含换乘信息）查询 （5）支持用户提供最少换乘路线（含换乘信息）查询 测试数据 自行制作公交车、车站及路线信息。 实现提示 采用图结构，顶点表示车站，边表示局部线路，是对图遍历和最短路径算法的应用。 扑克游戏程序 1 发牌程序（随机、人工） 2 打牌程序（任意熟知的某类规则） 3 牌例存储（文件） 4 牌例演示 5 界面友好性设计 6 各类数据结构应用、分析 7 优胜策略设计、计算 文本文件压缩： 输入需要压缩的文本文件名，对该文件中的各个字符出现的频度进行统计，然后进行Huffman编码，再读入源文件，将源文件翻译成Huffman编码文件，输出到文件2.txt，最后读入2.txt文件，将Huffman编码文件翻译成文本文件，输出到3.txt。 要求计算压缩比输出：压缩比是编码后文件字符数除以编码前文件中含有字符数。 移动数字游戏 从一个含8个数字(用1-8表示)的方块以及一个空格方块(用0表示)的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其它位置上有3个方向可移动。 例如，假设一个3x3矩阵的初始状态为： 8 0 3 2 1 4 7 6 5 目标状态为： 1 2 3 8 0 4 7 6 5 则一个合法的移动路径为： 8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3 2 1 4 2 0 4 0 2 4 8 2 4 8 2 4 8 0 4 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 另外，在所用可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径;在上面的例子中，最短路径为5。如果不存在从初始状态到目标状态的任何路径，则称该组状态无解。 请设计算法找到从八方块的某初始状态到某目标状态的所有可能路径的最短路径，并用C/C++实现。 输入数据：程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成(0表示空格)，1-8表示8个数字方块)，每行3个数字，数字之间用空格隔开。假定start.txt和goal.txt不会相同。 输出数据：如果输入数据有解，输出一个表示最短路径的非负的整数;如果输入数据无解，输出-1.请在数字输出后在输出一回车换行符。 如果st