《数据结构》课程教学设计.docx

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

1、数据结构课程教学设计 数据结构课程教学设计 一、课程内容体系 1. 基本描述 课程中文名称:数据结构 课程英文译名:Data Structures 总学时:授课 40 学时实验 20 学时 授课对象:计算机专业、自动化专业、信息专业、通讯专业、数学专业 课程要求:必修课 课程分类:专业（技术）基础 开课时间:第4学期 先修课:工科数学分析、高级语言程序设计或C+程序设计、集合与图论2. 教学定位 数据结构是计算机科学与技术各专业及其相关的一门专业基础课；是计算机科学与技术专业课程体系中的核心课程之一；是设计和实现编译程序、操作系统、数据库系统和其它系统软件、应用软件的重要基础。其后续课程有操作

2、系统、编译原理、数据库系统概论、算法分析、图像处理等。在整个计算机知识体系中，数据结构具有不可替代的作用。瑞士著名的计算机科学家沃思教授曾提出:算法数据结构程序。算法:是对数据运算的描述；数据结构:是指数据的逻辑结构和存储结构。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。由此可见数据结构在解决计算机问题中的重要地位。 学习本课程旨在使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，掌握和不断提高运用数据结构解决实际问题的能力。通过本门课程的学习，使学生透彻地理解各种数据结构对象的特点，学会各种数

3、据结构的组织方法和实现方法，并进一步培养良好的程序设计编程能力。同时，学习数据结构的过程也是复杂程序设计的训练过程，要求学生编 写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。因此，要想有效地进行数据组织和程序开发，就必须掌握数据结构的知识。 课程的内容重点立足于基础知识和基础理论的掌握、应用能力的培养以及实践能力的提高。该课程通过一些最常用的数据结构的介绍，阐明了数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算时的动态性质及实际的执行算法。具体来说，就是从数据结构的逻辑结构、存储结构和数据的操作三个方面使学生较好的掌握

4、线性表、树、二叉树、图和文件等常用的数据结构的基本概念及构建方法。并掌握在各种常用数据结构上实现的查找和排序算法。同时对算法的时间和空间复杂性有一定的分析能力。在课程学习结束后要求学生针对简单的应用问题，能够选择合适的数据结构设计并编写出有效的算法程序。 本课程是实践性很强的一门课程，不但要求学生要深刻理会相应的基本理论、基本原理等知识，还要求学生亲自动手设计、上机实现各种算法，以达到使学生理论与实践相结合，综合应用各知识点的目的，巩固、加深所学的理论，并培养学生的科学研究能力和创新精神，并为后继课程的学习奠定坚实的基础。 3. 知识点与学时分配 第一章绪论（1学时） 数据结构的基本概念和术语

5、；数据结构在软件系统中的作用；课程的研究和学习内容等；算法及其特征；算法性能度量指标；算法时间和空间复杂性及其分析方法。 第二章线性表（4学时） 线性表的逻辑结构、各种存储结构、基本操作（算法）的实现及性能分析、不同存储结构的比较、线性表的应用等。 第三章栈与队列（4学时） 栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本操作。栈和队列的本质区别，并且能在相应的应用问题中正确选用它们。栈和队列的应用。 第四章串（2学时） 串的逻辑结构、存储结构及其上的基本操作，由于C语言及其它高级语言均已具备了较强的串处理功能，故重点讲述在实际中广泛使用的串的模式匹配算法。 第五章多维数组和广义

6、表（2学时） 多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏短阵的压缩存储方法及广义表的概念和性质。 第六章树（8学时） 二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历；树和森林与二叉树的转换；树（森林）与二叉树的应用（哈夫曼树及其应用、集合表示与等价分类、表达式求值） 习题课（1学时） 线性结构和树的习题 第七章图及其相关算法（8学时） 无向和有向图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法(最小生成树算法、求关节点和双连通分量算法、强连通性判定和求双连通分量的算法、拓扑分类算法、关键路径算法、最短路径算法等)。 第八章查找（4学时） 在线性表、树

7、结构和散列表上进行查找的基本思想和方法、查找算法的实现以及各种查找方法的时间性能(平均查找长度)分析；基于关键字的查找与基于关键字散列地址的查找的本质区别。 第九章内部排序（4学时） 内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。 习题课（2学时） 总结与习题 二、教材选择 本课程选用严蔚敏、吴伟民编写的数据结构（清华出版社、C语言版）。 该教材是国内的经典教材，一方面反映领域基础性、普遍性的知识，保持内容体系的完整，另一方面又紧跟科技发展，内容丰富，体系结构严谨，概念清晰，易学易懂，符合学生的认识规律，与该教材配套的习题集和上级指导一起形成了完

8、整的体系。该教材曾获“第二届普通高等学校优秀教材全国特等奖”和“1996年度国家科学技术进步奖三等奖”的基础上再版的，该教材目前的发行量已超过100万册。本教材具有以下特点:涵盖教学大纲内容，兼顾知识的广度和深度，适用面广；引入抽象数据类型的基本概念，有助于培养学生的数据抽象和算法设计能力；以C伪码语言描述存储结构和算法，有助于提高学生的程序设计能力；对算法进行详尽的定性或定量的时间分析，有助于奠定学生的算法分析基础；提供了全书120余个算法C语言源码、80余个算法执行过程的动态演示，有助于学生对数据结构和算法的分析和理解。 本课程的参考书选用郭福顺、廖明宏等编著的数据结构与算法基础、唐策善等

9、编著的数据结构用C语言描述，高等教育出版社出版和数据结构影印原版书籍。其中郭福顺、廖明宏等编著的数据结构与算法基础于2000年改造完成为21世纪高等教育规划教材数据结构与算法基础，由单纯的注重数据结构转变为数据结构与算法并重，保持了教材的先进性。本教材力求突出以下特点:简洁避开了高深的理论，简明扼要地介绍学生最需要的基础知识和技术；通俗通过通俗易懂的语言讲授计算机专业技术知识；先进在内容上吸收新技术、新动向，保持一定的前沿性。实用本套书能既适合于教，更适合于学，对高等学校计算机专业的教学具有较强的适用性。 三、课堂讲授 1、教学要求、重点、难点和教学内容 以线性表、树、二叉树、图等常用的数据结

10、构的逻辑结构、存储结构和数据的操作以及各种常用数据结构上实现的查找和排序算法为主要内容，培养和训练对算法的复杂性的分析能力以及选择合适的数据结构对实际的应用问题进行有效算法的设计能力。 第一章绪论 教学要求: 本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本操作及其在存储结构上如何实现这些基本操作。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是:数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系，抽象数据类型(ATD)的概念和实现方法，算法时间复杂性和空间复杂性分

11、析。本章难点是: 抽象数据类型(ATD)的概念和实现方法，算法时间复杂性和空间复杂性分析。 教学内容: 1. 数据结构的基本概念和术语。 (1) 数据、数据元素、数据项、数据结构等基本概念。 (2) 数据结构的逻辑结构、存储结构及数据操作的含义及其相互关系。 (3) 数据结构的两大类逻辑结构和四种常用的存储表示方法。 2. 抽象数据类型。 (1) 抽象数据类型的表示。 (2) 抽象数据类型的实现。 3. 算法的描述和分析 (1) 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。 (2) 算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。 (3) 算法描述和

12、算法分析的方法，对于一般算法能分析其时间复杂度。 第二章线性表 教学要求: 本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本操作及其在存储结构上如何实现这些基本操作。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是: 线性表ADT顺序存储实现中的创建、查找、插入和删除等基本操作及相关算法；ADT链式存储实现中单链表的创建、查找、插入和删除等基本操作及相关算法；双向链表的插入和删除等基本操作及相关算法；循环链表的特点及创建、查找、插入和删除等基本操作及相关算法。本章难点是:

13、 线性表ATD 的设计和实现，线性表ADT链式存储实现，包括双向链表、循环链表的基本操作和有关算法。 教学内容: 1. 线性表的逻辑结构 (1) 线性表的逻辑结构特征。 (2) 线性表上定义的基本操作，并能利用基本操作构造出较复杂的操作。 2. 线性表的顺序存储结构 (1) 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。 (2) 顺序表上的插入、删除操作及其平均时间性能分析。 (3) 利用顺序表设计算法解决简单的应用问题。 3. 线性表的链式存储结构 (1) 链表如何表示线性表中元素之间的逻辑关系。 (2) 链表中头指针和头结点的使用。 (3) 单链表、双链表、循环链表链接方

14、式上的区别。 (4) 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 (5) 单循环链表以及单循环链表上的算法与单链表上相应算法的异同点。 (6) 双链表的定义及其相关的算法。 (7) 利用链表设计算法解决简单的应用问题。 4. 顺序表和链表的比较 (1) 顺序表和链表的主要优缺点。 (2) 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。 第三章栈和队列 教学要求: 本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本操作。要求在掌握栈和队列的特点的基础上，提高利用栈和队列解决实际问题的应用水平。本章

15、重点是:栈、队列的定义、特点、性质和应用；ADT栈、ADT队列的设计和实现以及基本操作及相关算法。本章难点是:循环队列中对边界条件的处理；分析栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例，提高利用栈和队列解决实际问题的应用水平。 教学内容: 1. 栈的逻辑结构、存储结构及其相关算法 (1) 栈的逻辑结构特点，栈与线性表的异同。 (2) 顺序栈和链栈上实现的进栈、退栈等基本算法。 (3) 利用栈设计算法解决简单的应用问题。 2. 队列的逻辑结构、存储结构及其相关算法 (1) 队列的逻辑结构特点，队列与线性表的异同。 (2) 顺序队列(主要是循环队列)和链队列上实现的人队、出队等

16、基本算法。 (3) 队列“假溢出”的概念及其判别条件。 (4) 循环队列空和满的判断方法。 (5) 利用队列设计算法解决简单的应用问题。 3. 栈和队列的应用 (1) 栈和队列的特点，什么样的情况下能够使用栈或队列。 第四章串 教学要求: 本章目的是介绍串的逻辑结构、存储结构及其中上的基本操作，本章重点是: ADT串的设计、实现方法和基本操作；串的朴素模式匹配算法，KMP算法。本章难点是: 串的模式匹配算法中的KMP算法。 教学内容: 1. 串及其操作 (1) 串的有关概念及基本操作。 (2) 串与线性表的关系。 2. 串的存储结构 (1) 串的两种存储表示。 (2) 串上实现的模式匹配算法及

17、其时间性能分析。 (3) 使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。 第五章多维数组和广义表 教学要求: 本章目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念和性质，本章重点是:数组的存储表示方法；数组在存储结构中的地址计算方法；特殊矩阵压缩存储时的下标变换公式；稀疏矩阵的两种压缩存储方法；三元组表示稀疏矩阵时进行矩阵运算采用的算法。广义表的定义和性质。本章难点是:稀疏矩阵的压缩存储表示和实现算法。 教学内容: 1. 多维数组 (1) 多维数组的逻辑结构特征。 (2) 多维数组的顺序存储结构及地址计算方式。 (3) 数组是一种随

18、机存取结构的原因。 2. 短阵的压缩存储 (1) 特殊矩阵和稀疏矩阵的概念。 (2) 特殊矩阵和压缩存储时的下标变换方法。 (3) 稀疏矩阵的三元组表表示方法及有关算法。 3. 广义表的概念 (1) 广义表的有关概念及其与线性表的关系。 (2) 广义表的性质。 第六章树 教学要求: 本章目的是二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及其应用（优化判定过程和哈夫曼编码）等内容。本章重点是:二叉树的定义、结构特点和性质；ADT二叉树的设计和实现，二叉树存储结构的特点，三种遍历方式的递归和非递归算法。二叉树的线索化过程和算法；最优二叉树的

19、特性及建立最优二叉树和哈夫曼编码的方法。本章难点是: 二叉树的线索化算法；设计解决与树或二叉树相关的应用问题的有效算法。 教学内容: 1. 树的概念 (1) 树的逻辑结构特征。 (2) 树的不同表示方法。 (3) 树的常用术语及含义。 2. 二叉树 (1) 二叉树的递归定义及树与二叉树的差别。 (2) 二叉树的性质，了解相应的证明方法。 (3) 二叉树的存储方法、特点及适用范围。 3. 二叉树的遍历 (1) 二叉树的三种遍历算法，理解其执行过程。 (2) 确定三种遍历所得到的相应的结点访问序列。 (3) 以遍历算法为基础，设计有关算法解决简单的应用问题。 4. 线索二叉树 (1) 二叉树线索化

20、的目的及实质。 (2) 在中序线索树中查找给定结点的中序前趋和中序后继的方法。 (3) 查找给定结点的前序前趋和后序后继并非有效的原因。 5. 树和森林 (1) 树和森林与二叉树之间的转换方法。 (2) 树的各种存储结构及其特点。 (3) 树的遍历方法。 6. 哈夫曼树及其应用 (1) 最优二叉树和最优前缀码的概念及特点。 (2) 哈夫曼算法的思想。 (3) 根据给定的叶结点及其权值构造出相应的最优二叉树。 (4) 利用哈夫曼树优化判定过程。 (5) 根据最优二叉树构造对应的哈夫曼编码。 7. 表达式的树结构表示与求值 (1) 表达式的树结构表示与求值。 (2) 表达式的求值。 8. 集合的树

21、结构表示 (1) 集合的树结构表示法。 (2) 集合的操作算法的实现即改进。 (3) 集合等价分类算法及其实现。 第七章图及其相关算法 教学要求: 本章目的是掌握图论的基本术语、图的表示方法和遍历算法、以及有关图论的算法。本章重点是:图的定义、术语和性质；ADT图的设计和实现；图的邻接矩阵、邻接表的存储结构及其构造方法；图的两种遍历方法：深度优先遍历和广度优先遍历；最小生成树的算法、拓扑排序的算法；理解关键路径的算法，构造最短路径的Dijkstra算法和Floyed算法。本章难点是:有向无环图的关键路径算法，求最短路径的Dijkstra算法和Floyed算法。 教学内容: 1. 图的概念 (1

22、) 图的逻辑结构特征。 (2) 图的常用术语及含义。 2. 图的存储结构 (1) 邻接矩阵和邻接表这两种存储结构的特点及适用范围。 (2) 图的存储结构的建立。 (3) 根据应用问题的特点和要求选择合适的存储结构。 3. 图的遍历 (1) 连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法，其执行过程以及时间复杂性分析。 (2) 确定两种遍历所得到的顶点访问序列。 (3) 图的两种遍历与树的遍历之间的关系。 (4) 两种遍历所使用的辅助数据结构(栈或队列)在遍历过程中所起的作用。 (5) 利用图的两种遍历设计算法解决简单的应用问题。 4. 生成树和最小生成树 (1) 生成树和最小生成树的

23、概念。 (2) 对遍历给定的图，画出深度优先和广度优先生成树或生成森林。 (3) Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。 (4) 要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。 5. 无向图的双连通性 (1) 无向图的关节点和双连通图。 (2) 双连通图及其性质。 (3) 求关节点的算法。 (4) 求双连通分量的算法。 6. 有向图的强连通性 (1) 有向图的分支横边和归约图。 (2) 强连通分量算法的基本思想。 (3) 强连通分量算法。 7. 拓扑排序 (1) 拓扑排序的基本思想和步骤。 (2) 拓扑排序不成功的原因。 (3) 对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。 8. 关键路径 (1) AOE网的源点、汇点、关键路径和关键活动。 (2) 关键路径和关键活动分析。 (3) 利用先广拓扑分类求关键路径和关键活动的算法。