数据结构课程设计大纲-2015秋.doc

《数据结构与算法》课程设计大纲 一课程设计教学目的及基本要求 1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二课程设计内容及安排 1、问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2、逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。 3、物理设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。 4、程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。 5、程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 6、结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 7、编写课程设计报告。（具体格式参见附录。） 三课程设计考核方法及成绩评定 课程设计结束时，要求学生写出课程设计报告（附源程序），可运行的软件系统。课程设计成绩分两部分，设计报告占30％，设计作品占70％。四课程设计注意事项 课程设计报告要求 按格式要求完成实习报告，每人用A4纸打印课程设计报告（源代码可不打印），此外，请学习委员将所有同学的源代码收齐后刻在一张光盘上，光盘上分别为每位同学的资料建一个文件夹（名为“班学号姓名”，如111-01-XXX），其中存入该同学课程设计的源程序及课程设计报告的电子文档。 下学期开学第一周周一交。 第一次上机之前请各位同学对实现题目仔细研究，最好能有自己的思路。第一次上机时和指导老师交流对题目的理解。班学号姓名 请各位同学自行完成课程设计内容。如有网上下载或同学间雷同，成绩将以不通过计！！！ 请各位同学把实习题目当作产品来完成。追求完善，不要应付老师检查，程序要求有良好的结构及编码风格，有必要的注释。 为了减少调试时间，可以把测试数据及操作都使用文件存储，也可在“项目属性”中指定参数。 必须在机房完成实习。  《数据结构与算法》课程设计题目、1或0，其中1表示有效像元，0表示图像的背景。如果一个元素在另外一个元素的上、下、左、右四个方向，称两个元素为相邻元素。“像元分组”算法是将二值图像中处于相邻的元素进行分组标号，使得属于同一个分组的像元集合，其编号都相同。如下图所示： 分组前 分组后 【要求】 使用“队列”来实现二值图像的像元分组，图像数据采用TXT文件形式给出，把分组结果图像输出到另外一个文件中。 【测试数据】 二值图像分组.txt  2、基于非递归算法的无向图连通分量的识别 【问题描述】 对于一个无向连通图，从图中某一顶点出发，通过多次调用深度优先有哪些信誉好的足球投注网站（DFS）算法可以找到多个连通分量。然而图的深度优先有哪些信誉好的足球投注网站（DFS）算法一般采用递归算法来实现，鉴于二叉树遍历算法可以转换为非递归算法来实现，试编写基于DFS的非递归遍历算法的无向图的连通分量的识别程序。 【算法提示】 设置一个栈结构；在遍历时，每访问一个顶点w，就将w压入栈中，然后访问w的一个未被访问的邻接顶点……；如果在遍历过程中，某顶点的所有邻接顶点都已被访问过，就从栈顶删去该顶点；然后继续访问当前栈顶元素的一个未被访问过的邻接顶点，当栈为空时，遍历操作结束。 【要求】 DFS的非递归实现+连通分量的标识；采用图形绘制函数（GDI），在MFC视图中绘制出所有可能的连通分量。 【测试数据】  3、软件压缩/解压缩软件 Szip（Huffman算法及应用） 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进