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

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

课程设计名称： 指导老师： 指导方式： 课程设计教材 数据结构课程设计09102版 服务课程名称： 数据结构 课程设计周数： 1-2周 王中华（wangzh@sdju.edu.cn） 集体辅导与个别答疑相结合 陈元春等编著的《实用数据结构基础》，中国铁道出版社 课程设计适用班级： BX0805、BX0806 课程设计授课单位： 上海电机学院 电子信息学院 计算机基础教学部 及主要参考资料： 严蔚敏，吴伟民编著的《数据结构》，清华大学出版社 一、课程设计教学目的及基本要求

1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

5．设计的题目要求达到一定工作量，并具有一定的深度和难度。

6．编写出课程设计报告，报告正文不得少于10页（其中正文文字部分不得少于七页，代码不算页数）。

二、课程设计内容及安排

1．问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？

2．逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图； 3．详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；

4．程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；

1

5．程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；

6．结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 7．编写课程设计报告

三、设计报告的内容

设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及要求如下：

封面：题目、班级、学号、姓名、指导教师和完成日期。 正文包括以下7个内容：

1．需求分析：以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：

(1) 输入的形式和输入值的范围； (2) 输出的形式；

(3) 程序所能达到的功能；

(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结

果。

2．概要设计：说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3．详细设计：实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；可采用流程图N–S图或PAD图进行描述，画出函数和过程的调用关系图。

4．调试分析内容包括：

(1) 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和

分析；

(2) 算法的时间复杂度和空间复杂度的分析和改进设想； (3) 经验和体会等。

5．用户使用说明：说明如何使用你编写的程序，详细列出每一步的操作步骤。 6．测试结果：列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。 7．参考文献：列出参考的相关资料和书籍。

2

四、课程设计考核方法及成绩评定

课程设计结束时，要求学生写出课程设计报告（不附源程序），不得少于10页，可运行的软件系统（包括源程序）。

课程设计成绩分两部分，设计过程答辩占60％，设计作品及报告各占20％；如果最终的设计作品源代码及设计报告不按时提交则直接判为不及格。

按照优秀、良好、中、及格，不及格五级或者百分制给予成绩。 需要提交的材料清单：

1、课程设计报告（电子稿、打印稿）

2、程序源代码文件夹（文件夹中只保留.c或.cpp、.dll、.lib等必须文件，编译过程中产生的其它文件及Debug文件夹等提交时一律删除）

命名格式：假设BX0504班学号为8号的同学叫张三做的课题B7，则其设计报告电子稿及源代码文件夹均命名为“BX050408张三B7：稀疏矩阵的运算”，该名字中间不要添加任何空格或其他字符。

五、进度安排

阶段任务 系统分析与设计 编代码、调试和测试 设计论文书写 演示软件和答辩 1周时间安排 1天 2天 1.5天 0.5天 2周时间安排 2天 4天 3天 1天 六、课程设计题目[共22题]（最多两人一题）

A类题目[共8题]

课题A1：求AOE（Active Of Edge,边活动）网的关键路径 1．设计目的

? 了解事件（顶点）和活动（弧）的相关概念。 ? 掌握AOE网（即边带权值的图）的存储方法。 ? 进一步掌握用回溯法求AOE网的关键路径。 ? 理解关键路径的相关含义。 2．主要内容

AOE网是一个边带权的有向无环图，其中，顶点表示事件（Event），弧表示活动（Active），弧的权表示活动持续的时间。通常，AOE网可用来估算工程的完成时间。

例如，下图是一个假想的有11项活动的AOE网。其中有9个事件A，B，C，

3

D，E，F，G，H，I，每个事件表示在它之前的活动已经完成，在它之后的活动才可以开始。如A表示整个工程开始，I表示整个工程结束，E表示a4和a5都已经完成，a7和a8才可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，a1活动需要6个时间单位，a2需要4个时间单位。

图A1-1 AOE网

图 A1-2 图 A1-3

所有顶点的最早发生时刻和最晚发生时刻计算方法如下：

假设顶点V的最早发生时间为Early(V)，顶点V的最早发生时间为Late(V)，则图A1-2中的弧头顶点H的最早发生时间

Early(H)?Max(Early(Ri)?wi)

即为所有弧尾顶点的最早发生时间和其对应弧权值之和的最大值； 图A1-3中的弧尾顶点R的最晚发生时间

Late(R)?Min(Late(Hi)?wi)

即为所有弧头顶点的最晚发生时间和其对应弧权值之差的最小值。按以上方法求出图A1-1中所有顶点的最早和最晚发生时刻如表A1-1所示。

表A1-1 事件（即结点） A B

发生时刻 最早 0 6 4

最晚 0 6 C D E F G H I 4 5 7 7 16 14 18 6 8 7 10 16 14 18 算法步骤：

（1）输入AOE网的顶点总数和所有顶点标志（每个顶点都用一个大写英文字母

作为标 …… 此处隐藏：2129字，全部文档内容请下载后查看。喜欢就下载吧 ……