13级--数据结构课程设计要求(2015-7).doc

起止周：1819周 周数：2周实习地点：东区2教616室 信息与计算科学实验室一、课程设计的目的数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。通过该课程设计，了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练学生用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计的基本要求1、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。3、按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括：a）需求分析：在该部分中叙述，每个模块的功能要求b）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。课程设计总结：总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容；4、每组实现的结果必须进行检查和演示；程序源代码和程序的说明文件必须上交，作为考核内容的一部分。5、课程设计报告附原代码，可以对重点函数及结构进行说明。报告格式见要求。6、报告提交形式：课程设计报告纸质和电子文档(按班级统一刻盘）。三、课程设计内容：1、内部排序演示【问题描述】设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。【基本要求】(1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；(2) 待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。(3) 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，用饼图或条形图进行表示，以便比较各种排序的优劣。(4) 界面友好，易与操作。采用菜单方式进行选择。【选做内容】(1) 对不同表长进行比较；(2) 验证各算法的稳定性；(3) 输出界面的优化。(4) 使用汉字显示。2、校园导游咨询【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1) 设计长春理工大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2) 为来访客人提供图中任意景点相关信息的查询。(3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。【选做内容】(1) 系统功能的完善；(2) 提供求任意两个景点之间的所有路径的功能；(3) 提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。(4) 使用汉字显示。3、哈夫曼编码/译码器【问题描述】设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。【基本要求】(1) 输入一个待压缩的文本文件名， 统计文本文件中各字符的个数作为权值，生成哈夫曼树；(2) 将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod），(3) 输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；(4) 显示指定的压缩文件和文本文件；(5) 界面友好，易与操作。采用菜单方式进行选择。【选做内容】(1) 把哈夫曼编码用二进制位紧缩到一个变量中，利用位运算进行真正的数据压缩，并求压缩比。(2) 显示哈夫曼树；(3) 使用汉字显示。4、运动会分数统计【问题描述】参加运动会有n个学校,学校编号为1n.比赛分成m个男子项目,和w个女子项目.项目编号为男子1.m,女子m+1.m+w.不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）【功能要求】：可以输入各个项目的前三名或前五名的成绩；能统计各学校总分；可以按学校编号、学校总分、男女团体总分排序输出；可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。【基本要求】（1）输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）（2）输出形式：有中文提示，各学校分数为整形（3）界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。（4）存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。5、文章编辑【问题描述】输入一页文字，程序可以统计出文字、数字、空格的个数。【基本要求】静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数【选做内容】输出删除某一字符串后的文章？6、乡卫生所选址【问题描述】 某乡有A，B，C，D，E 5个村庄，如下图所示，图中边上的权值表示两村之间的距离。现要在5个村庄中选某个村庄建立卫生所。其选址应使得距离卫生所最远的村庄到卫生所最近。AECDB 3 8 10 4 6 6 【基本要求】（1）给出各村庄之间最短距离的矩阵A。（2）卫生所应设在哪个村庄？（3）输出各村庄到卫生所的路径和路径长度。【选做内容】如果增加或者减少一个村庄，整个问题数据结构会有哪些变化？7、新产品研制工序序列【问题描述】 一个农业生产工具制造厂，完成一件农用新产品研制工程的各个工序以及相互之间的关系如图所示。只有各子工序顺利完成，完整的新产品才能研制完成。由于资源等条件的限制，需要一项一项地安排实施各个工序，请给出使新产品顺利完成的各个工序安排的可行方案。【基本要求】（1）选用一种存储结构，实现网络图的存储。（2）定义另一种存储结构，不在通过用户输入，而是直接将（1）中的存储结构中的数据导过来，编写算法实现此功能。（3）求出并输出保证工程顺利完成的各个工序按时间先后排列的一个线性序列。工 序 表工序代号工序名称紧前工序A产品设计-B工艺设计-C主件制造A BD下料，锻件加工AE外购配套件AF模具制造CG组装D E FH调试试用G8、自选题 允许有能力的同学自选题目，但题目必须按上面的格式写出“问题描述”和“具体要求”，且题目的工作量要达到或超过已给题目，并经指导教师审核同意才可以进行自选题目的课程设计。四、上交作业及成绩评定1、上交要求上交设计报告和相关光盘。光盘内容包括程序源码和使用说明。整个班级的设计均刻在一张光盘上，可按姓名或分组建立相关文件夹进行存储。（上交时每人交一份，文件夹的取名规则为：“学号 姓名”，如“200413498 高魁”。该文件夹下至少包括：“源代码”、 “可执行文件”。由学习委员收集刻盘按规定时间统一上交）2、评分标准根据完成任务的情况(必须进行系统演示)、课程设计报告书的质量和课程设计过程中的工作态度等按照30%、50%、20%加权