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