第12章　数据结构课程设计.ppt

《第12章　数据结构课程设计.ppt》由会员分享，可在线阅读，更多相关《第12章　数据结构课程设计.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2011年5月11日星期三1第12章 目 录 12.1 课程设计的目的与内容课程设计的目的与内容 12.2 课程设计的内容课程设计的内容 12.3 A类题目类题目 12.4 B类题目类题目 12.4 C类题目类题目 本章精选了本章精选了24个与数据结构相关的典型应用题目，个与数据结构相关的典型应用题目，并按从易到难的顺序分为并按从易到难的顺序分为A、B、C三个类别，通过一周或三个类别，通过一周或两周的时间由学生独立完成其中一个题目。要顺利完成本两周的时间由学生独立完成其中一个题目。要顺利完成本章课题所规定的任务，需要复习前面各章节介绍的各种逻章课题所规定的任务，需要复习前面各章节介绍的各种逻辑

2、结构、存储结构及基本算法，熟练掌握并理解前面各章辑结构、存储结构及基本算法，熟练掌握并理解前面各章节的知识要点，并对部分知识点进行相互串联。由于部分节的知识要点，并对部分知识点进行相互串联。由于部分课题对课题对计算机组成原理计算机组成原理和和算法分析与设计算法分析与设计等课程等课程的内容稍有涉及，认真完成本章的课题任务对后续课程的的内容稍有涉及，认真完成本章的课题任务对后续课程的学习也将不无帮助。学习也将不无帮助。12.1 课程设计的目的与内容12.1.1 课程设计的目的课程设计的目的1了解并掌握数据结构与算法的设计方法，培养独立分析问题的能力；了解并掌握数据结构与算法的设计方法，培养独立分析

3、问题的能力；2综合运用所学的数据结构基本理论和方法，提高在计算机应用中解决实际问题综合运用所学的数据结构基本理论和方法，提高在计算机应用中解决实际问题的能力；的能力；3初步掌握软件开发过程的问题分析、系统设计、程序编码、程序调试、数据测初步掌握软件开发过程的问题分析、系统设计、程序编码、程序调试、数据测试等基本方法和技能；试等基本方法和技能；4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者应该具训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者应该具备的科学的工作方法和作风。备的科学的工作方法和作风。5通过课程设计完成具有一定深度和难度的题目。通过课程设计完成具有一

4、定深度和难度的题目。6编写课程设计报告，锻炼软件开发文档撰写的基本方法。编写课程设计报告，锻炼软件开发文档撰写的基本方法。12.2 课程设计的内容1问题分析和任务定义问题分析和任务定义 根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？条件是什么？2逻辑设计逻辑设计 对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。心的原则划分模块，定义主程序模块和各抽象数据类型。3详细

5、设计详细设计 定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。可能做到数据封装，基本操作的规格说明尽可能明确具体。4程序编码程序编码 把详细设计的结果进一步转换为程序设计语言程序。同时加入一些注解，把详细设计的结果进一步转换为程序设计语言程序。同时加入一些注解，使程序逻辑概念清楚、维护方便。使程序逻辑概念清楚、维护方便。5

6、程序调试与测试程序调试与测试 程序调试采用自底向上，分模块进行。即先调试低层函数，再逐级调试程序调试采用自底向上，分模块进行。即先调试低层函数，再逐级调试上一层的函数。通过程序调试熟练掌握调试工具的各种功能；设计测试数据确上一层的函数。通过程序调试熟练掌握调试工具的各种功能；设计测试数据确定疑点，通过修改程序来证实它或绕过它。程序调试正确后，认真整理源程序定疑点，通过修改程序来证实它或绕过它。程序调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单。及其注释，形成格式和风格良好的源程序清单。6结果分析结果分析程序运行结果不但要包括正确的输入及其输出结果，而且还要人为的输入一些程序

7、运行结果不但要包括正确的输入及其输出结果，而且还要人为的输入一些含有错误的数据以考察其输出结果的正确性。同时进行算法的时间复杂性和空含有错误的数据以考察其输出结果的正确性。同时进行算法的时间复杂性和空间复杂性分析。间复杂性分析。7编写课程设计报告。编写课程设计报告。12.1.312.1.3 课程设计报告课程设计报告1课题分析课题分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：（1）输入的形式和输入值的范围；）输入的形式和输入值的范围；（2）输出的形式；）输出的形式；（3）程序所能达到的功能；）程序所能达

8、到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2总体设计总体设计说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。层次（调用）关系。3详细设计详细设计 实现总体设计中定义的所有数据类型，对每个操作只需要写出伪码算法；实现总体设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；也可以采用流程图、对主程序和其他模块也都需要写出伪码算法；也可以采用

9、流程图、NS图或图或PAD图进行描述，画出函数和过程的调用关系图。图进行描述，画出函数和过程的调用关系图。4调试分析调试分析调试分析的内容包括：调试分析的内容包括：（1）调试过程中遇到的问题是如何解决的，以及对程序设计与实现的讨论和）调试过程中遇到的问题是如何解决的，以及对程序设计与实现的讨论和分析；分析；（2）算法的时间复杂度和空间复杂度的分析；）算法的时间复杂度和空间复杂度的分析；（3）对算法的改进设想；）对算法的改进设想；（4）程序调试的收获和体会。）程序调试的收获和体会。5用户使用说明用户使用说明 用户使用说明是为了告诉用户如何使用你编写的程序，并举例列出每一用户使用说明是为了告诉用户

10、如何使用你编写的程序，并举例列出每一步的操作步骤。步的操作步骤。6测试结果测试结果 列出测试的输入数据和程序运行以后的输出结果，测试数据应该保证完列出测试的输入数据和程序运行以后的输出结果，测试数据应该保证完整和严格。整和严格。7参考文献参考文献 列出参考资料和书籍。列出参考资料和书籍。12.1.4 课程设计的考核课程设计的考核 课程设计的成绩分三部分给定。其中：设计过程的答辩占课程设计的成绩分三部分给定。其中：设计过程的答辩占60，设计作品，设计作品（源代码）占（源代码）占20，课程设计报告占，课程设计报告占20。成绩评定按照优秀、良好、中、及格，不及格五级或者按百分制实施。成绩评定按照优秀

11、、良好、中、及格，不及格五级或者按百分制实施。本课程需要提交归档的材料清单如下：本课程需要提交归档的材料清单如下：（1）课程设计报告（电子稿和打印稿各一份）。）课程设计报告（电子稿和打印稿各一份）。（2）程序源代码文件夹（文件夹中只保留）程序源代码文件夹（文件夹中只保留.c或或.cpp、.dll、.lib等必须文件，编等必须文件，编译过程中产生的各种参考文件、工程文件和译过程中产生的各种参考文件、工程文件和Debug文件夹等提交时一律删除）。文件夹等提交时一律删除）。11.2 课程设计的要求1.课题的分类与选择课题的分类与选择 为了使不同编程基础的同学通过课程设计都能有所提为了使不同编程基础的

12、同学通过课程设计都能有所提高，使所有同学都学有所获，根据课程设计题目的难度由高，使所有同学都学有所获，根据课程设计题目的难度由低到高，将所有课题分为低到高，将所有课题分为A、B、C三个类别。三个类别。教师可以根据学生的学习基础，结合学生本人的意愿，教师可以根据学生的学习基础，结合学生本人的意愿，先对学生进行分组，然后各个小组以抽签的方式决定具体先对学生进行分组，然后各个小组以抽签的方式决定具体的课程设计题目。学生也可以根据个人的能力自行选择有的课程设计题目。学生也可以根据个人的能力自行选择有一定难度的其它数据结构课程设计课题，但是自选课题必一定难度的其它数据结构课程设计课题，但是自选课题必须预

13、先向指导老师提出申请，说明课题的内容、难度，以须预先向指导老师提出申请，说明课题的内容、难度，以及实现的目标，经老师同意并立项以后方可进行。及实现的目标，经老师同意并立项以后方可进行。2.课程设计的要求课程设计的要求 课程设计按照教学要求需要课程设计按照教学要求需要1-2周时间完成，两周中每天至少要上机周时间完成，两周中每天至少要上机3-4小时来调试程序，总共至少要上机调试程序小时来调试程序，总共至少要上机调试程序30小时。为保证质量，要求每小时。为保证质量，要求每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一

14、。对题目中要求的功能进行分析，并且设计解决此问题的数据存储结构（有对题目中要求的功能进行分析，并且设计解决此问题的数据存储结构（有些课题中部分存储结构已经指定，则可采用指定的存储结构）和算法。给些课题中部分存储结构已经指定，则可采用指定的存储结构）和算法。给出实现算法功能的一组或多组测试数据，程序调试通过以后，按照此测试出实现算法功能的一组或多组测试数据，程序调试通过以后，按照此测试数据进行程序运行的数据测试。数据进行程序运行的数据测试。程序要有基本的容错功能。不但能够在数据正常情况下运行，而且当程序要有基本的容错功能。不但能够在数据正常情况下运行，而且当数据出现错误时，应避免出现死循环。数据

15、出现错误时，应避免出现死循环。课程设计课题总体要求如下：课程设计课题总体要求如下：（1）利用）利用C或或C+实现课题相应的程序，源程序要按照课程设计规定的规则来实现课题相应的程序，源程序要按照课程设计规定的规则来编写。编写。（2）系统功能全部采用菜单控制，所有程序应上机调试通过并运行正确。）系统功能全部采用菜单控制，所有程序应上机调试通过并运行正确。（3）课程设计程序全部调试通过以后，也可以对课题的算法提出改进方案，并）课程设计程序全部调试通过以后，也可以对课题的算法提出改进方案，并比较不同算法的优缺点。比较不同算法的优缺点。（4）课程设计报告中应给出课题的总体分析、详细设计、算法过程的具体分

16、析、）课程设计报告中应给出课题的总体分析、详细设计、算法过程的具体分析、系统所涉及的逻辑结构图、数据所采用的存储结构图、程序流程图、采用的测系统所涉及的逻辑结构图、数据所采用的存储结构图、程序流程图、采用的测试数据及其结果分析、算法时间和空间复杂度的分析等。试数据及其结果分析、算法时间和空间复杂度的分析等。（5）课程设计报告正文不得少于）课程设计报告正文不得少于A4纸纸10页页（6）如果程序采用）如果程序采用C#或或Java等其它课堂上尚未开设的编程语言实现，必须预等其它课堂上尚未开设的编程语言实现，必须预先向指导老师提出申请。先向指导老师提出申请。1 1.3.3 A A类题目类题目 A类课题

17、共类课题共6个，是难度较低的课题。个，是难度较低的课题。12.3.1 课题课题A1：多项式运算：多项式运算1设计目的设计目的（1）掌握线性表的顺序存储结构和链式存储结构。）掌握线性表的顺序存储结构和链式存储结构。（2）掌握线性表的插入、删除等基本运算。）掌握线性表的插入、删除等基本运算。（3）掌握线性表的典型应用）掌握线性表的典型应用多项式运算（加、减、乘、除多项式运算（加、减、乘、除选做选做）。）。2主要内容主要内容 实现顺序结构或链式结构的多项式加减乘除运算，其中加法、减法和实现顺序结构或链式结构的多项式加减乘除运算，其中加法、减法和乘法功能为必做，除法功能为选做。乘法功能为必做，除法功能

18、为选做。3设计要求设计要求（1）如果有两个同学同时完成该课题，要求分别采用顺序和链式两种存储结）如果有两个同学同时完成该课题，要求分别采用顺序和链式两种存储结构。构。（2）如果多项式采用顺序结构存储，则多项式运算的最高次应能达到。）如果多项式采用顺序结构存储，则多项式运算的最高次应能达到。（3）通过菜单选择项输入两个多项式，通过菜单依次求得这两个多项式加、）通过菜单选择项输入两个多项式，通过菜单依次求得这两个多项式加、减、乘、除减、乘、除选做选做的运行结果，并比较程序运行结果和手工计算结果是否一致。的运行结果，并比较程序运行结果和手工计算结果是否一致。12.3.2 课题课题A2：求最小生成树：

19、求最小生成树【基于邻接矩阵存储基于邻接矩阵存储】1设计目的设计目的（1）掌握无向图（或网）的邻接矩阵存储结构；）掌握无向图（或网）的邻接矩阵存储结构；（2）掌握基于邻接矩阵存储结构无向图的遍历方法。）掌握基于邻接矩阵存储结构无向图的遍历方法。（3）掌握利用）掌握利用Prim或或Kruskal算法求解最小生成树的过程。算法求解最小生成树的过程。2主要内容主要内容（1）输入给定无向网的顶点总数和所有顶点标志；）输入给定无向网的顶点总数和所有顶点标志；（2）输入无向网中边的总数，并利用循环依次输入各条边的端点标志及权值，）输入无向网中边的总数，并利用循环依次输入各条边的端点标志及权值，建立该无向网的

20、邻接矩阵存储结构；建立该无向网的邻接矩阵存储结构；（3）用）用Prim或者或者Kruskal算法求该无向网最小生成树。算法求该无向网最小生成树。3设计要求设计要求（1）如果有两个同学同时完成该课题，要求分别采用）如果有两个同学同时完成该课题，要求分别采用Prim和和Kruskal算法求算法求得该无向网的最小生成树。得该无向网的最小生成树。（2）为方便编程，每个顶点均用一个英文字母作为标志。）为方便编程，每个顶点均用一个英文字母作为标志。（3）按选取边的顺序输出最小生成树的各条边。）按选取边的顺序输出最小生成树的各条边。12.3.3 12.3.3 课题课题课题课题A3A3：非递归求解：非递归求解

21、：非递归求解：非递归求解HanoiHanoi问题问题问题问题12.3.4 12.3.4 课题课题课题课题A4A4：迷宫问题：迷宫问题：迷宫问题：迷宫问题12.3.5 12.3.5 课题课题课题课题A5A5：中缀表达式转后缀并求值：中缀表达式转后缀并求值：中缀表达式转后缀并求值：中缀表达式转后缀并求值【运算对象为个位数运算对象为个位数运算对象为个位数运算对象为个位数】12.3.6 12.3.6 课题课题课题课题A6A6：二叉树的层次遍历：二叉树的层次遍历：二叉树的层次遍历：二叉树的层次遍历12.412.4 B B类题目类题目 B B类课题共类课题共类课题共类课题共9 9个，是难度适中的课题。个，

22、是难度适中的课题。个，是难度适中的课题。个，是难度适中的课题。12.4.1 12.4.1 课题课题课题课题B1B1：哈希查找的实现与分析：哈希查找的实现与分析：哈希查找的实现与分析：哈希查找的实现与分析12.4.2 12.4.2 课题课题课题课题B2B2：有向无环图的判定及拓扑排序：有向无环图的判定及拓扑排序：有向无环图的判定及拓扑排序：有向无环图的判定及拓扑排序12.4.3 12.4.3 课题课题课题课题B3B3：浮点数的：浮点数的：浮点数的：浮点数的IEEE754IEEE754标准格式转换标准格式转换标准格式转换标准格式转换12.4.4 12.4.4 课题课题课题课题B4B4：文件记录读取

23、并排序：文件记录读取并排序：文件记录读取并排序：文件记录读取并排序12.4.5 12.4.5 课题课题课题课题B5B5：大整数运算：大整数运算：大整数运算：大整数运算12.4.6 12.4.6 课题课题课题课题B6B6：平衡二叉树的构造及输出：平衡二叉树的构造及输出：平衡二叉树的构造及输出：平衡二叉树的构造及输出12.4.7 12.4.7 课题课题课题课题B7B7：二叉树的中序线索化及其非栈非递归遍历：二叉树的中序线索化及其非栈非递归遍历：二叉树的中序线索化及其非栈非递归遍历：二叉树的中序线索化及其非栈非递归遍历12.4.8 12.4.8 课题课题课题课题B8B8：稀疏矩阵的运算：稀疏矩阵的运

24、算：稀疏矩阵的运算：稀疏矩阵的运算12.4.9 12.4.9 课题课题课题课题B9B9：基于十字链表有向图的遍历：基于十字链表有向图的遍历：基于十字链表有向图的遍历：基于十字链表有向图的遍历12.5 12.5 C C类题目类题目 C类课题共类课题共9个，是难度较高的课题。个，是难度较高的课题。12.5.1 课题课题C1：求：求AOE网的关键路径网的关键路径12.5.2 课题课题C2：求有向图的强连通分量：求有向图的强连通分量12.5.3 课题课题C3：非递归方式遍历二叉树：非递归方式遍历二叉树12.5.4 课题课题C4：求最小生成树：求最小生成树【基于邻接表存储结构基于邻接表存储结构】12.5.5 课题课题C5：Dijkstra算法求最短路径算法求最短路径12.5.6 课题课题C6：拼写检查器：拼写检查器12.5.7 课题课题C7：中缀表达式转后缀并求值：中缀表达式转后缀并求值【运算对象为多位数运算对象为多位数】12.5.8 课题课题C8：哈夫曼编码器：哈夫曼编码器12.5.8 课题课题C8：哈夫曼编码器：哈夫曼编码器