数据结构课程设计

《数据结构》课程设计实践指导书

一、实践的目的和任务

《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；主要任务是通过对给定问题的求解，使学生在运用《数据结构》、程序设计以及其它所学课程中的各种基本技术和理论，在建立问题模型、构造求解算法、设计数据结构、编程及上机调试等方面得到全面的锻炼，从而能更深刻地理解《数据结构》的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。

二、实践的内容和要求 （一）实践内容

实践内容为数据结构课程完成后，运用《数据结构》、程序设计以及其它所学课程中的知识和技术来解决实际的问题。在解决实际应用性问题时，按照计算机解决问题的步骤进行以下几个方面的工作：采用简明、严格的问题描述，建立模型，设计求解方法，用计算机实现求解方法，最后进行测试和文档制作。

1、建立模型

许多问题的最初描述既不精确又不简练，还有一些问题不可能简单而精确地用计算机可求解的形式来描述，即使有些可用计算机求解的问题，也需要在很大范围内确定问题的参数，而那些合理的参数值只有通过实验才能确定。因此，要用计算机解决问题，必须首先要以简明、严格的方式将问题描述清楚。数学或其它科学中的几乎所有分支都可作为某一类具体问题的抽象模型。例如，在涉及到若干对象及其相互间关系的问题时所用的数学模型为图论；数值计算问题中常用的数学模型为线性方程组（用于求解电路的电流强度或结构中的应力）或微分方程（用于预报人口增长情况或化学反应速度等）；在符号与文本处理问题时常用字符串及形式语法作为模型（如编译系统）。《数据结构》课程中所介绍的各种结构均可作为一种模型。

2、构造算法

对问题建立了适当的数学模型后，就可以依据这一模型求解。最初的目标是给出一个算法形式的解法，这是设计的核心部分。所给出的算法并非一定要用某种计算机语言来描述，但应能较方便地转换为某种计算机语言程序。

1

在建立了适当的数学模型后，某些问题就可以转换为一些经典问题或基于某些经典问题的综合或变异形式的求解。例如，如果所转换出的模型为图，则可能借助于图的深度遍历、广度遍历、求最小生成树、求最短路径、拓扑排序、关键路径、二分图的匹配、图的着色等问题的求解算法来实现。在问题的求解没有可借助的方法时，需要自己构思求解方法。在构造求解方法时，需要注意对时间、空间、程序实现以及其它有关性能的要求。另外，在构造算法时，最好是在数学模型上构造。

3、选择设计数据结构

在确定了求解算法后，就可以开始编程方面的构思了。从算法到程序还是有一定的距离的，为此，需要做两方面的工作，其一是选择合适的数据结构以存储所涉及到的数据，其二是用指定的计算机语言来描述算法。在选择数据结构时，除了要能将所需的数据存储起来外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。《数据结构》课程中已经对此作了很好的理论准备。在实际应用时，需根据问题的要求进行合理的选择以及综合。

4、编程

编程的另一个方面是用指定的计算机语言来描述算法和数据结构，并将其转换为完整的上机程序。这包括提供必要的辅助程序段，如建立和输入一个结构，显示结构，跟踪程序的运行等。另外，在编程过程中可能还需要设置数据结构，也要为这些结构提供基本运算。在设计时，如果所用的结构是《数据结构》实验中已经完成的，可以直接拿来调用，如果没用，则需要重新设计。

5、总结

对设计进行总结和讨论，包括本设计的优、缺点，时间、空间性能，与其它可能存在的求解方法之间的比较等。通过总结，可以对问题求解有更全面、深入的认识，从而达到由典型到全面、由具体到一般的飞跃，实现设计的目标，这是设计所不可缺少的重要内容。这部分内容应作为设计报告中的一个组成部分。

（二）要求

1、熟练掌握各种数据结构的逻辑结构特性、存储结构与常用操作算法； 2、能分析课程设计的相应题目，结合理论学习考虑用一种或多种数据结构建立模型来解决问题；

3、能分析并设计在某种数据结构下解决问题的步骤即算法；

4、熟练掌握面向对象程序设计思想方法与编译系统的使用方法，能较好地编写程序实现数据结构与算法，解决实际问题

5、能较好地进行程序的静态检查与动态调试与测试 6、能按要求写好课程设计报告

2

三、实践教学实施办法

根据课程设计实践的性质、内容和要求，采用下面的步骤进行实施： 1、选题

课程设计前一周，在数据结构课程设计课题表中，根据课程设计的时间和个人能力，在老师的协助下选择适当难度的课程设计课题，每个课题都有相应的要求或说明。参加课程设计的学生首先要了解设计的任务，仔细阅读各题的设计要求，然后根据自己的基础和能力情况从中选择一题。若学生对课题表以外的相关课题较感兴趣，希望选作课程设计的课题时，应征得指导教师的认可，并写出明确的设计要求和说明。

2、课程设计

根据选择问题的描述，建立模型，设计求解方法，用计算机实现求解方法，设计测试数据，完成测试，生成可运行的设计系统。

3、验收

在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能认可设计部分的结束。

4、撰写课程设计设计报告

设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告应包含封面、任务书（设计任务、要求及所用软件环境或工具）、目录、正文和参考文献等，以规定的格式书写、并装订成册，书写工整、排版及图、表要清楚。正文部分包含的内容如下：

（1）需求分析

以无歧义的语言陈述说明课程设计要解决问题的任务。阐述的时候避开具体的算法和涉及的数据结构，对要完成的任务作出明确的回答，强调的是做什么，而不是怎么做。

（2）概要设计

对解决问题涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并给出模块之间的调用关系。

（3）详细设计

选择或设计数据结构的存储结构，实现存储结构的基本运算、设计的模块构成、各模块的简要说明、流程图、调用关系表等。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数

3

据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。

（4）所设计系统的组成（程序和设计的测试数据）及使用说明

设计系统包含内容是程序文件、测试数据以及如何使用的阐述。程序可以以相关文件名及文件内容说明的形式给出；测试数据要给出数据内容并说明设计该测试数据的理由；使用说明要写出别人使用你的系统应该如何去操作。

（5）测试结果及程序清单（可以打印）

采用自底向上，分模块进行，即先调试、测试低层函数。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；

（6）设计总结和体会 四、考核方式和成绩评定

由指导教师根据学生完成任务的情况、课程设计报告的质量和课程设计过程中的工作态度等综合打分。课程设计结束时，要求学生写出课程设计报告，可运行的软件系统（包括源程序）。课程设计成绩：上机情况（20%）包括出勤情况、调试表现。设计报告占40％，设计系统占40％。

成绩评定实行优、良、中、及格和不及格五个等级。不及格者不能得到相应的学分，需重新做课程设计，经指导教师考核及格后，方可取得相应学分。

五、数据结构课程设计选题

对下列题目每个同学的课程设计任务按下式确定： 课程设计任务=（选题序号-1） ＋1 1.集合运算器设计

问题描述：设计合适的存储结构组织集合中的元素，并在此数据结构上实现集合的运算。

实现的功能：集合的交、并、差、求子集运算、判断元素是否属于一个集合、判断某个集合是否是该集合的子集等操作的演示程序。

要求：

（1）描述集合模型，分析需要完成的功能，设计高效的数据结构完成总体设计，搭好框架，确定人机对话的界面，定义、实现集合的运算；

（2）界面友好，函数功能要划分好 （3）要有算法设计的流程图 （4）程序要加必要的注释 （5）要提供程序测试方案

4

2.向量运算器设计

问题描述：设计合适的存储结构组织向量，并在此数据结构上实现向量的运算。

实现的功能：向量的加、减、数乘、数量积、向量积、向量的模，单位向量，判断两个向量的相关性等操作的演示程序。

要求：

（1）描述向量模型，分析需要完成的功能，设计高效的数据结构完成总体设计，搭好框架，确定人机对话的界面，定义、实现向量的运算；

（2）界面友好，函数功能要划分好 （3）要有算法设计的流程图 （4）程序要加必要的注释 （5）要提供程序测试方案 3.长整数四则运算设计

问题描述：设计合适的存储结构组织超长型的整型数据，并在此存储结构上实现四则运算。

实现的功能：超长整数的加、减、乘、除、二次方、2次开方等运算的演示程序。

要求：

（1）描述超长整数的模型，分析需要完成的功能，设计高效的数据结构完成总体设计，不能对超长整数的长度进行限制，搭好框架，确定人机对话的界面，定义、实现四则运算；

（2）界面友好，函数功能要划分好 （3）要有算法设计的流程图 （4）程序要加必要的注释 （5）要提供程序测试方案 4. 商店存货管理系统设计

问题描述：设计合适的存储结构组织某商店的商品，对商品进行有效管理。 实现的功能：能建立文件将存储结构中的各种商品进行保存和装载到系统，要求商品能够分类管理，按照类别对各种商品信息进行增加，修改和删除以及简单的排序；所有商品要求每次出货按照进货时间最早且最接近保质期中止时间的货物。

要求：

5

本文来源：https://www.bwwdw.com/article/hzb3.html