数据结构课程设计精品文稿.ppt

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

1、数据数据结构构课程程设计第1页，本讲稿共21页第第12章章 目目 录录v 12.1 课程设计的目的与内容课程设计的目的与内容v 12.2 课程设计的内容课程设计的内容v 12.3 A类题目类题目v 12.4 B类题目类题目v 12.4 C类题目类题目2 2第2页，本讲稿共21页 本章精选了本章精选了24个与数据结构相关的典型应用题目，并按从个与数据结构相关的典型应用题目，并按从易到难的顺序分为易到难的顺序分为A、B、C三个类别，通过一周或两周的时间由学三个类别，通过一周或两周的时间由学生独立完成其中一个题目。要顺利完成本章课题所规定的任务，需生独立完成其中一个题目。要顺利完成本章课题所规定的任

2、务，需要复习前面各章节介绍的各种逻辑结构、存储结构及基本算法，熟要复习前面各章节介绍的各种逻辑结构、存储结构及基本算法，熟练掌握并理解前面各章节的知识要点，并对部分知识点进行相互串练掌握并理解前面各章节的知识要点，并对部分知识点进行相互串联。由于部分课题对联。由于部分课题对计算机组成原理计算机组成原理和和算法分析与设计算法分析与设计等等课程的内容稍有涉及，认真完成本章的课题任务对后续课程的课程的内容稍有涉及，认真完成本章的课题任务对后续课程的学习也将不无帮助。学习也将不无帮助。3 3第3页，本讲稿共21页12.1 课程设计的目的与内容12.1.1 课程设计的目的课程设计的目的1了解并掌握数据结

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

4、作方法和作风。方法和作风。5通过课程设计完成具有一定深度和难度的题目。通过课程设计完成具有一定深度和难度的题目。6编写课程设计报告，锻炼软件开发文档撰写的基本方法。编写课程设计报告，锻炼软件开发文档撰写的基本方法。4 4第4页，本讲稿共21页12.2 课程设计的内容1问题分析和任务定义问题分析和任务定义 根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？2逻辑设计逻辑设计 对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模对问题描述中涉及的操作对象定义相应的数

5、据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。块，定义主程序模块和各抽象数据类型。3详细设计详细设计 定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。数据封装，基本操作的规格说明尽可能明确具体。5 5第5页，本讲稿共21页4程序编码程序编码 把详细设计的结果进一步转换为程序设计语言程

6、序。同时加入一些注解，使程序逻把详细设计的结果进一步转换为程序设计语言程序。同时加入一些注解，使程序逻辑概念清楚、维护方便。辑概念清楚、维护方便。5程序调试与测试程序调试与测试 程序调试采用自底向上，分模块进行。即先调试低层函数，再逐级调试上一层的函数。通过程程序调试采用自底向上，分模块进行。即先调试低层函数，再逐级调试上一层的函数。通过程序调试熟练掌握调试工具的各种功能；设计测试数据确定疑点，通过修改程序来证实它或绕过它。序调试熟练掌握调试工具的各种功能；设计测试数据确定疑点，通过修改程序来证实它或绕过它。程序调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单。程序调试正确后

7、，认真整理源程序及其注释，形成格式和风格良好的源程序清单。6结果分析结果分析程序运行结果不但要包括正确的输入及其输出结果，而且还要人为的输入一些含有程序运行结果不但要包括正确的输入及其输出结果，而且还要人为的输入一些含有错误的数据以考察其输出结果的正确性。同时进行算法的时间复杂性和空间复杂性错误的数据以考察其输出结果的正确性。同时进行算法的时间复杂性和空间复杂性分析。分析。7编写课程设计报告。编写课程设计报告。6 6第6页，本讲稿共21页12.1.312.1.3 课程设计报告课程设计报告1课题分析课题分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：以无歧义的陈述说明程序

8、设计的任务，强调的是程序要做什么？并明确规定：（1）输入的形式和输入值的范围；）输入的形式和输入值的范围；（2）输出的形式；）输出的形式；（3）程序所能达到的功能；）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2总体设计总体设计说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。说明本程序中用到的所有数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。7 7第7页，本讲稿共21页3详细设计详细设计 实现总体设计中定义的所有数据类型

9、，对每个操作只需要写出伪码算法；对主程序实现总体设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；也可以采用流程图、和其他模块也都需要写出伪码算法；也可以采用流程图、NS图或图或PAD图进行描述，画图进行描述，画出函数和过程的调用关系图。出函数和过程的调用关系图。4调试分析调试分析调试分析的内容包括：调试分析的内容包括：（1）调试过程中遇到的问题是如何解决的，以及对程序设计与实现的讨论和分析；）调试过程中遇到的问题是如何解决的，以及对程序设计与实现的讨论和分析；（2）算法的时间复杂度和空间复杂度的分析；）算法的时间复杂度和空间复杂度的分析；（3）对

10、算法的改进设想；）对算法的改进设想；（4）程序调试的收获和体会。）程序调试的收获和体会。8 8第8页，本讲稿共21页5用户使用说明用户使用说明 用户使用说明是为了告诉用户如何使用你编写的程序，并举例列出每一步的操作步骤。用户使用说明是为了告诉用户如何使用你编写的程序，并举例列出每一步的操作步骤。6测试结果测试结果 列出测试的输入数据和程序运行以后的输出结果，测试数据应该保证完整和严格。列出测试的输入数据和程序运行以后的输出结果，测试数据应该保证完整和严格。7参考文献参考文献 列出参考资料和书籍。列出参考资料和书籍。9 9第9页，本讲稿共21页12.1.4 课程设计的考核课程设计的考核 课程设计

11、的成绩分三部分给定。其中：设计过程的答辩占课程设计的成绩分三部分给定。其中：设计过程的答辩占60，设计作品（源代码）占，设计作品（源代码）占20，课程设计报告占，课程设计报告占20。成绩评定按照优秀、良好、中、及格，不及格五级或者按百分制实施。成绩评定按照优秀、良好、中、及格，不及格五级或者按百分制实施。本课程需要提交归档的材料清单如下：本课程需要提交归档的材料清单如下：（1）课程设计报告（电子稿和打印稿各一份）。）课程设计报告（电子稿和打印稿各一份）。（2）程序源代码文件夹（文件夹中只保留）程序源代码文件夹（文件夹中只保留.c或或.cpp、.dll、.lib等必须文件，编译过程中产生的各等必

12、须文件，编译过程中产生的各种参考文件、工程文件和种参考文件、工程文件和Debug文件夹等提交时一律删除）。文件夹等提交时一律删除）。1010第10页，本讲稿共21页11.2 课程设计的要求课程设计的要求1.课题的分类与选择课题的分类与选择 为了使不同编程基础的同学通过课程设计都能有所提高，为了使不同编程基础的同学通过课程设计都能有所提高，使所有同学都学有所获，根据课程设计题目的难度由低到高，使所有同学都学有所获，根据课程设计题目的难度由低到高，将所有课题分为将所有课题分为A、B、C三个类别。三个类别。教师可以根据学生的学习基础，结合学生本人的意愿，教师可以根据学生的学习基础，结合学生本人的意愿

13、，先对学生进行分组，然后各个小组以抽签的方式决定具体的先对学生进行分组，然后各个小组以抽签的方式决定具体的课程设计题目。学生也可以根据个人的能力自行选择有一定课程设计题目。学生也可以根据个人的能力自行选择有一定难度的其它数据结构课程设计课题，但是自选课题必须预先难度的其它数据结构课程设计课题，但是自选课题必须预先向指导老师提出申请，说明课题的内容、难度，以及实现的向指导老师提出申请，说明课题的内容、难度，以及实现的目标，经老师同意并立项以后方可进行。目标，经老师同意并立项以后方可进行。1111第11页，本讲稿共21页 2.课程设计的要求课程设计的要求 课程设计按照教学要求需要课程设计按照教学要

14、求需要1-2周时间完成，两周中每天至少要上机周时间完成，两周中每天至少要上机3-4小时来调试小时来调试程序，总共至少要上机调试程序程序，总共至少要上机调试程序30小时。为保证质量，要求每个学生将每天的上小时。为保证质量，要求每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。机调试程序的时间记录下来，作为评判成绩的标准之一。对题目中要求的功能进行分析，并且设计解决此问题的数据存储结构（有些课题中部分存储结构对题目中要求的功能进行分析，并且设计解决此问题的数据存储结构（有些课题中部分存储结构已经指定，则可采用指定的存储结构）和算法。给出实现算法功能的一组或多组测试数据，程序已经指

15、定，则可采用指定的存储结构）和算法。给出实现算法功能的一组或多组测试数据，程序调试通过以后，按照此测试数据进行程序运行的数据测试。调试通过以后，按照此测试数据进行程序运行的数据测试。程序要有基本的容错功能。不但能够在数据正常情况下运行，而且当数据出现错误时，应避程序要有基本的容错功能。不但能够在数据正常情况下运行，而且当数据出现错误时，应避免出现死循环。免出现死循环。1212第12页，本讲稿共21页课程设计课题总体要求如下：课程设计课题总体要求如下：（1）利用）利用C或或C+实现课题相应的程序，源程序要按照课程设计规定的规则来编写。实现课题相应的程序，源程序要按照课程设计规定的规则来编写。（2

16、）系统功能全部采用菜单控制，所有程序应上机调试通过并运行正确。）系统功能全部采用菜单控制，所有程序应上机调试通过并运行正确。（3）课程设计程序全部调试通过以后，也可以对课题的算法提出改进方案，并比较）课程设计程序全部调试通过以后，也可以对课题的算法提出改进方案，并比较不同算法的优缺点。不同算法的优缺点。（4）课程设计报告中应给出课题的总体分析、详细设计、算法过程的具体分析、系统所涉及的）课程设计报告中应给出课题的总体分析、详细设计、算法过程的具体分析、系统所涉及的逻辑结构图、数据所采用的存储结构图、程序流程图、采用的测试数据及其结果分析、算法时逻辑结构图、数据所采用的存储结构图、程序流程图、采

17、用的测试数据及其结果分析、算法时间和空间复杂度的分析等。间和空间复杂度的分析等。（5）课程设计报告正文不得少于）课程设计报告正文不得少于A4纸纸10页页（6）如果程序采用）如果程序采用C#或或Java等其它课堂上尚未开设的编程语言实现，必须预先向指导老师提等其它课堂上尚未开设的编程语言实现，必须预先向指导老师提出申请。出申请。1313第13页，本讲稿共21页1 1.3.3 A A类题目类题目 A类课题共类课题共6个，是难度较低的课题。个，是难度较低的课题。12.3.1 课题课题A1：多项式运算：多项式运算1设计目的设计目的（1）掌握线性表的顺序存储结构和链式存储结构。）掌握线性表的顺序存储结构

18、和链式存储结构。（2）掌握线性表的插入、删除等基本运算。）掌握线性表的插入、删除等基本运算。（3）掌握线性表的典型应用）掌握线性表的典型应用多项式运算（加、减、乘、除多项式运算（加、减、乘、除选做选做）。）。2主要内容主要内容 实现顺序结构或链式结构的多项式加减乘除运算，其中加法、减法和乘法功能为必做，实现顺序结构或链式结构的多项式加减乘除运算，其中加法、减法和乘法功能为必做，除法功能为选做。除法功能为选做。1414第14页，本讲稿共21页3设计要求设计要求（1）如果有两个同学同时完成该课题，要求分别采用顺序和链式两种存储结构。）如果有两个同学同时完成该课题，要求分别采用顺序和链式两种存储结构

19、。（2）如果多项式采用顺序结构存储，则多项式运算的最高次应能达到。）如果多项式采用顺序结构存储，则多项式运算的最高次应能达到。（3）通过菜单选择项输入两个多项式，通过菜单依次求得这两个多项式加、减、乘、除）通过菜单选择项输入两个多项式，通过菜单依次求得这两个多项式加、减、乘、除选做选做的运行结果，并比较程序运行结果和手工计算结果是否一致。的运行结果，并比较程序运行结果和手工计算结果是否一致。1515第15页，本讲稿共21页12.3.2 课题课题A2：求最小生成树：求最小生成树【基于邻接矩阵存储基于邻接矩阵存储】1设计目的设计目的（1）掌握无向图（或网）的邻接矩阵存储结构；）掌握无向图（或网）的

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

21、最小生成树。1616第16页，本讲稿共21页3设计要求设计要求（1）如果有两个同学同时完成该课题，要求分别采用）如果有两个同学同时完成该课题，要求分别采用Prim和和Kruskal算法求得该无向网的最小算法求得该无向网的最小生成树。生成树。（2）为方便编程，每个顶点均用一个英文字母作为标志。）为方便编程，每个顶点均用一个英文字母作为标志。（3）按选取边的顺序输出最小生成树的各条边。）按选取边的顺序输出最小生成树的各条边。1717第17页，本讲稿共21页12.3.3 12.3.3 课题课题课题课题A3A3：非递归求解：非递归求解：非递归求解：非递归求解HanoiHanoi问题问题问题问题12.3

22、.4 12.3.4 课题课题课题课题A4A4：迷宫问题：迷宫问题：迷宫问题：迷宫问题12.3.5 12.3.5 课题课题课题课题A5A5：中缀表达式转后缀并求值：中缀表达式转后缀并求值：中缀表达式转后缀并求值：中缀表达式转后缀并求值【运算对象为个位数运算对象为个位数运算对象为个位数运算对象为个位数】12.3.6 12.3.6 课题课题课题课题A6A6：二叉树的层次遍历：二叉树的层次遍历：二叉树的层次遍历：二叉树的层次遍历1818第18页，本讲稿共21页12.412.4 B B类题目类题目 B B类课题共类课题共类课题共类课题共9 9个，是难度适中的课题。个，是难度适中的课题。个，是难度适中的课

23、题。个，是难度适中的课题。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：文件记录读取并排序：文件记录读取并排序：文件记录

24、读取并排序：文件记录读取并排序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：稀疏矩阵的运算：稀疏矩阵的运算：稀疏矩阵的运算：稀疏矩阵的运算1

25、2.4.9 12.4.9 课题课题课题课题B9B9：基于十字链表有向图的遍历：基于十字链表有向图的遍历：基于十字链表有向图的遍历：基于十字链表有向图的遍历1919第19页，本讲稿共21页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：哈夫曼编码器：哈夫曼编码器2020第20页，本讲稿共21页C l i c k t o e d i t c o m p a n y s l o g a n .第21页，本讲稿共21页