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

PAGEPAGE8《数据结构与算法》课程设计大纲（一）课程设计教学目的及基本要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（二）课程设计内容及安排1、问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2、逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3、物理设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4、程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。5、程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。6、结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。7、编写课程设计报告。（具体格式参见附录课程设计报告格式。）（三）课程设计考核方法及成绩评定课程设计结束时，要求学生写出课程设计报告（附源程序），可运行的软件系统。课程设计成绩分两部分，设计报告占30％，设计作品占70％。（四）课程设计注意事项课程设计报告要求按格式要求完成实习报告，每人用A4纸打印课程设计报告（源代码可不打印），此外，请学习委员将所有同学的源代码收齐后刻在一张光盘上，光盘上分别为每位同学的资料建一个文件夹（名为“班学号姓名”，如114111-01-XXX），其中存入该同学课程设计的源程序及课程设计报告的电子文档。下学期开学第一周周一交。第一次上机之前请各位同学对实现题目仔细研究，最好能有自己的思路。第一次上机时和指导老师交流对题目的理解。最后一次上机时接受指导老师成果检查，并在当周将课程设计报告电子版和源代码（注意去除debug调式目录）打包，发到指导老师邮箱。统一邮件主题和压缩包命名：数据结构课程设计+班学号姓名请各位同学自行完成课程设计内容。如有网上下载或同学间雷同，成绩将以不通过计！！！请各位同学把实习题目当作产品来完成。追求完善，不要应付老师检查，程序要求有良好的结构及编码风格，有必要的注释。为了减少调试时间，可以把测试数据及操作都使用文件存储，也可在“项目属性”中指定参数。必须在机房完成实习。

《数据结构与算法》课程设计题目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）程序使用命令行方式运行压缩命令：SZipATest.Haf1.doc解压缩命令：SZipXTest.Haf2.doc或SZipXTest.Haf用户输入的命令不正确时，给出提示。（5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。【提高要求】（1）基于Windows对话框界面，可选择输入/输出文件名，有压缩进度条显示。（2）采用不同的数据集，比较其压缩比，采用最有效的压缩方式。（3）多个文件的压缩。（4）试构建程序框架，使其能添加新的压缩/解压缩算法（例如书上LZW压缩算法）。【测试数据】约40000字符左右。示例数据.txt，80K，采用WinRar压缩后为43K；示例数据.doc，144K，采用WinRar压缩后为52K。

4、电话簿软件的实现（动态查找表算法的应用）【问题描述】在很多实际应用中，动态索引结构在文件创建或初始装入记录时生成，在系统运行过程中插入或删除记录时，为了保持较好的检索性能，索引结构本身将随之发生改变。教材上已经介绍的动态查找数据结构包括：二叉搜索树（BST）、平衡二叉树（AVL）、红黑树（RBT）、B-树。本题要求选取一种已经学过的动态搜索树结构，设计并实现一个手机电话薄软件。【基本要求】一个完整的电话簿软件应具有以下功能：（1）支持复式电话簿数据的存储，数据条目不少于500条。每个人名下可保存的信息包括：姓名、手机号码、住宅电话号码、办公电话号码、电子邮件地址、所属群组、备忘录等。（2）支持电话簿记录的添加、删除、编辑等操作。（3）将不同类型的人群按照同事、朋友、家人、商务伙伴等分组，支持群组记录的添加、删除、编辑等操作。（4）支持所有电话簿记录的导入、导出操作，外部数据采用TXT格式。（5）支持电话簿记录的各种查询操作，具体包括：①逐条翻看能显示所有的电话簿记录，支持分屏查看。②电话号码查找输入一个电话号码（手机、住宅、办公），能将包含该号码的电话簿记录显示出来。③人名查找输入一个人名（全名或者部分名），能将包含该姓名的电话簿记录显示出来。④群组查找选择一种群组类型，能将属于该群组的所有电话簿记录显示出来。（6）要求使用BST或者AVL实现动态索引结构。【提高要求】（1）系统支持铃声库和图片库的数据存储，提供添加、删除、修改、播放等操作。铃声库和图片库可直接使用文件目录进行管理；铃声格式可使用WAV、MP3或者WMV格式；图片格式可使用BMP、JPG等格式。（2）电话簿记录信息支持：来电铃声、来电图片等信息，用户可通过界面编辑或者浏览某条电话簿记录的来电铃声、来电图片。（3）人名查询支持：输入姓名的首字母查找。（4）使用红黑树或者B-树的数据结构，来实现动态索引结构。【测试数据】自行随机生成500~1000条电话簿数据记录。【实现提示】（1）设计合适的电话簿数据文件格式；（2）设计合适的索引文件格式。《数据结构与算法》课程设计报告学号：班级序号：姓名：指导教师：成绩：中国地质大学信息工程学院软件工程系2016年1月课程设计报告格式1．需求规格说明（<五号宋体>，具体内容：问题描述，求解的问题是什么）2．总体分析与设计（1）设计思想：（<五号宋体>，具体内容：存储结构、主要的算法思想。）（2）设计表示：（<五号宋体>，具体内容：子程序（过程或函数）的规格说明，通过调用关系图表示它们之间的调用关系。）（3）详细设计表示：（<五号宋体>，具体内容：主要算法的框架。）3．编码 （<五号宋体>，具体内容：问题是如何解决的，编码过程中的困难与解决方法。）4．程序及算法分析（<五号宋体>，具体内容：使用说明、程序运行结