数据结构DS复习章节

1、数据结构课程授课教案课程名称：数据结构英文名称：Data Structure学时数及学分：6432学时 41学分授课班级：2005级2班教材名称及作者、出版社、出版时间：数据结构（C语言版），严蔚敏 吴伟民，北京：清华大学出版社，2004 一、 课程的目的、要求和任务数据结构是计算机专业的一门必修的核心基础课程。是计算机程序设计的重要理论技术基础，它对理论和实践的要求都相当高，具有相当的难度，且内容较多。本课程旨在讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构在计算机中的存储结构，以及进行各种非数值运算的方法，让学生学习、分析和研究计算机加工数据对象的特性，掌握数据的组织方法，以便选择合

2、适的数据的逻辑结构和存储结构，设计相应的操作运算。在计算机应用领域中，尤其是在系统软件和应用软件的设计和应用中都要用到各种数据结构，这对提高软件设计和程序编制水平都有很大的帮助。二、课程主要教学内容本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。1. 掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构

3、、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法；2. 掌握各种主要数据结构的特点、机内表示、处理数据的算法设计，以及算法分析、组织、处理数据的理论和方法，建立良好的编程风格；培养数据的抽象能力。三、课程教学重点与难点1. 教学重点：线性表、栈、队列、二叉树、图典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法思想。2. 教学难点：各种数据结构的应用和进行操作实现。四、参考书1. 数据结构（C语言版），严蔚敏、吴伟民编著，清华大学出版社，2006年7月2. 数据结构与算法设计,王晓东,电子工业出版社,2002.33. 数据结构（C语言篇）

4、习题与解析,李春葆, 清华大学出版社4. 数据结构学习指导与典型题解，朱占立等编著，西安交通大学出版社5. 数据结构题集（C语言版）, 严蔚敏 吴伟民, 清华大学出版社6. 数据结构 殷人昆 编著, 清华大学出版社 7. 数据结构 张选平 雷永梅, 机械工业出版社，2002.1第一章 绪论1. 教学内容(1) 数据结构的基本概念和术语；(2) 数据的逻辑结构、存储结构；(3) 抽象数据类型在软件设计中的意义；(4) 算法的概念和算法的时间和空间复杂度分析。2. 教学目的及要求(1) 掌握数据结构的基本概念，理解数据结构和算法的关系；(2) 抽象数据类型的表示和实现；(3) 类C语言描述算法的机

5、制；(4) 掌握算法复杂性分析的方法和技巧。3. 教学重点(1) 本课程的主要内容；(2) 数据结构的基本概念和术语，抽象数据类型，算法和算法的时间复杂度分析4. 教学难点(1) 抽象数据类型的表示和实现(2) 算法的时间复杂度分析；5. 教学思路与教学方法(1) 讲授数据结构课程的主要内容以及在软件分析和设计中意义；(2) 讲授抽象数据类型在软件设计中的意义；(3) 讲授算法的概念和算法的时间复杂度分析方法；(4) 例题讲解算法的时间复杂度分析方法；(5) 作业(6) 对于重点和难点，通过例题讨论讲解。6. 习题与思考题(1) 填空题a） 数据的逻辑结构可形式地用一个二元组B(D，S)来表示

6、，其中D是_，S是_。b） 存储结构可根据数据元素在机器中的位置是否连续分为_，_。c） 算法的基本要求有_，_，_，_，_。 d） 度量算法效率可通过_，_两方面进行。(2) 简述下列术语： a） 数据、数据元素、数据对象、数据结构b） 数据的存储结构、逻辑结构；c） 数据类型和抽象数据类型(3) 举例说明一下数据结构和算法的关系。(4) 试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。例如：求下列算法的时间复杂度： i=1; while(i<=n) i=i*3;答：O（logn）第二章 线性表（8学时）1. 教学内容(1) 线性表的逻辑结构特征；线性表上定义的基

7、本运算，并利用基本运算构造出较复杂的运算；(2) 线性表的顺序存储结构、a） 特点；b） 基本操作的实现算法（初始化、插入、删除、查找等）；(3) 线性表的链式存储结构及基本操作的实现算法；a） 线性链表的特点、类型定义，以及基本操作（初始化、插入、删除、查找等）的实现算法；b） 循环链表、双向链表的定义、特点及操作的实现。2. 教学目的及要求(1) 掌握线性表的逻辑特点；(2) 掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。(3) 掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和

8、删除等基本算法及其时间复杂度。(4) 循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。(5) 领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能3. 教学重点(1) 线性表的定义和抽象数据类型；顺序和链式存储结构；(2) 顺序表的设计；(3) 链表（单链表、循环链表、双向链表）的设计。4. 教学难点(1) 顺序表操作的算法设计，以及单链表操作的算法设计；(2) 完整应用程序的结构5. 教学思路与教学方法(1) 讲授本章节的基本概念，先逻辑结构，后存储结构；(2) 讲授各存储结

9、构下操作实现的主要思想；(3) 在C+开发环境下，计算机演示完整应用程序的结构，以及编辑、编译和运行的方法；(4) 例题讲解；对于重点和难点，通过程序演示，作业来突出。 (5) 辅助手段：多媒体演示板书6. 习题与思考题（见PPT课件，并完成实验二的实验题目）第三章 栈和队列（8学时）1. 教学内容(1) 栈的基本概念、特点，与一般线性表的区别； (2) 栈顺序表示和实现、链式表示和实现；(3) 栈的典型应用：数制转换问题；括号匹配问题；栈与递归；(4) 队列的基本概念、特点，与一般线性表的区别；(5) 顺序队列、顺序循环队列、链式队列、队列应用；优先级队列。2. 教学目的及要求(1) 理解栈

10、的概念；(2) 掌握顺序栈和链式栈的设计方法；(3) 理解队列的概念，掌握顺序循环队列和链式队列的设计方法；(4) 了解栈和队列的应用方法，掌握栈和队列的基本应用。3. 教学重点(1) 顺序栈和链栈的设计方法、典型应用；(2) 顺序循环队列和链式队列的设计方法。4. 教学难点(1) 栈和队列的实现；(2) 应用栈实现表达式的求值；(3) 顺序队列的假溢出现象，顺序循环队列的队空和队满判断方法。 5. 教学思路与教学方法(1) 课堂教学以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点和难点的算法的核心部分通过提问及增加板书进行详细讲解。(2) 对算法的实现要求采用VC+ 开发环境，配合大屏

11、幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。(3) 每次下课前布置若干思考题，待下次上新课前进行提问，或完成课堂练习，加强互动。(4) 根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。6. 习题与思考题（见PPT课件，并完成实验三的实验题目）第四章 串（2学时）1. 教学内容(1) 串的基本概念、存储结构（顺序存储、链式存储）、顺序存储结构下基本操作的实现算法；(2) 串的模式匹配：Brute-Force算法。(3) 联系C语言中串的存储方法及串函数，并围绕两种基本存储结构进行分析。2. 教学目的及要求(1) 了解串类型的抽象数据类型定义；(

12、2) 熟悉串的有关概念，串和线性表的关系；(3) 了解串的表示和实现（串的各种存储结构，比较它们的优、缺点，从而学会在何时选用何种存储结构为宜）；(4) 理解串的两种模式匹配算法的思想、实现及时间复杂度的分析； 3. 教学重点(1) 串的存储结构；(2) 了解串的模式匹配。4. 教学难点5. 教学思路与教学方法(1) 以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；(2) 课后做习题，并课外上机实验，练习基本操作的实现及模式匹配的实例训练，以巩固课堂所学知识点。(3) 板书设计：a） 以文字描述为主，要点及关键词用不同颜色标注；b） 涉及有关存储结构、算法时，通过示意图描述；(4) 提

13、问：a） 空串和空白串有无区别？b） 回顾：C语言中串的存储方法及有关串函数。6. 习题与思考题（见PPT课件，并完成实验四的实验题目）第五章 数组和广义表（6学时）1. 教学内容(1) 数组的定义及其实现机制；(2) 特殊矩阵（包括n阶对称矩阵、n阶三角矩阵）的压缩存储方法；(3) 稀疏矩阵的压缩存储方法：三元组顺序表、十字链表，以及稀疏矩阵实现转置和相加运算；(4) 广义表的结构特点、基本操作及其存储表示方法2. 教学目的及要求(1) 理解了解数组的逻辑结构和存储表示；掌握数组在以行/列为主的存储结构中的地址计算方法；(2) 掌握特殊矩阵的压缩存储方式及下标变换公式；(3) 了解稀疏矩阵压

14、缩存储方法的特点和适用范围，理解以三元组表示的稀疏矩阵进行矩阵运算采用的处理方法；(4) 掌握广义表的结构特点极其存储表示方法，以及对非空广义表进行分解的两种分析方法；(5) 了解广义表的递归算法设计。3. 教学重点(1) 稀疏矩阵的三元表存储表示及稀疏矩阵转置的两种实现方法。(2) 多维数组的表示和实现；(3) 特殊矩阵的压缩存储；(4) 稀疏矩阵的压缩存储。4. 教学难点(1) 稀疏矩阵的十字链表的定义和建立算法。5. 教学思路与教学方法(1) 从具体的矩阵实例出发，先分析其特点，然后围绕以上知识点进行讲述。(2) 以课堂多媒体教学为主，辅助以黑板推导有关计算、绘图分析；(3) 课后做习题

15、，并上机实验，练习特殊矩阵、稀疏矩阵的压缩存储方法，以巩固课堂所学知识点。(4) 板书设计：a） 以文字描述为主，要点及关键词用不同颜色标注；b） 对压缩存储方法通过示意图描述；c） 对于实例，通过链接到VC环境下实际运行。(5) 重点突出：通过课堂强调与透彻分析，课后练习进行。(6) 难点解决：通过实例讲解，并在VC环境下实际运行实例，使学生真实体会算法设计全过程。(7) 师生互动设计：a） 提问：数组与线性表的区别与联系？b） 回顾：线性表的两种存储结构表示方法。6. 习题与思考题（见PPT课件，并完成实验四的实验题目）第六章 树和二叉树（10学时）1. 教学内容(1) 二叉树的定义和性质

16、，性质的应用(2) 二叉树的存储结构（特别是二叉链表存储结构）(3) 二叉树的各种遍历算法（先序、中序、后序、层次）及其应用；能根据先序和中序，中序和后序确定一棵二叉树。(4) 线索二叉树的建立、遍历的基本思想，能画出按先序、中序、后序遍历次序建立的线索二叉树；(5) 二叉树的应用哈夫曼树，哈夫曼编码；(6) 树和二叉树之间的转换2. 教学目的及要求(1) 树与二叉树的基本概念；(2) 二叉树的性质与存储结构；(3) 掌握二叉树的遍历算法和二叉树问题的遍历算法设计分析和实现。3. 教学重点(1) 二叉树的性质、二叉树的存储结构；(2) 二叉树的遍历算法和二叉树遍历算法的应用；(3) 哈夫曼树在

17、编码方面的应用方法。4. 教学难点(1) 二叉树的性质以及利用这些性质分析问题的方法；(2) 二叉树问题的遍历算法设计分析和实现。5. 教学思路与教学方法(1) 讲授本章节的基本概念，先逻辑结构，后存储结构；(2) 讲授各存储结构下的实现的主要思想；(3) 计算机演示存储结构下的实现；(4) 例题讲解；(5) 作业(6) 辅助手段：多媒体演示(7) 对于重点和难点，通过程序演示，作业来突出。6. 习题与思考题（见PPT课件，并完成实验五的实验题目）第七章 图（10学时）1. 教学内容(1) 图的基本概念、图的存储结构；(2) 图的程序实现、图的遍历、最小生成树、最短路径等。2. 教学目的及要求

18、(1) 了解图的定义和术语(2) 掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；(3) 理解图的深度和广度遍历方法和算法设计方法；(4) 了解图的连通性问题极其判断；(5) 理解最小生成树的概念、普里姆算法和克鲁斯卡尔算法；(6) 有向无环图极其应用（拓扑排序和关键路径）；(7) 了解最短路径问题的基本概念和从一个结点到其余各结点最短路径的算法。3. 教学重点(1) 图的邻接矩阵和图的邻接表存储结构；(2) 图的深度和广度遍历方法；(3) 普里姆算法和克鲁斯卡尔算法。4. 教学难点(1) 图操作的实现方法。5. 教学思路与教学方法(1) 课堂教学以课堂讲授为主，采用多媒体教学方式以增大

19、信息量；(2) 图中的概念很多，采取先讲实例应用，再总结概念定义的方法学习效果会好些；(3) 对重点和难点算法的核心部分通过板书进行详细讲解。(4) 对算法的实现要求采用VC+开发环境，配合大屏幕投影演示，增强理论结合实际的效果和提高学生的学习兴趣。(5) 每次下课前布置若干思考题，待下次上新课前进行提问。(6) 根据课程内容，在讲课中适当采取设立问题，请同学给出回答的方法加强师生互动，提高教学效果。6. 习题与思考题（见PPT课件，并完成实验六的实验题目）第八章 查找（8学时）1. 教学内容(1) 顺序查找、二分查找、索引顺序查找算法；(2) 二叉排序树的查找、插入与删除算法；了解二叉平衡树

20、的基本概念(3) 常用的哈希函数的设计方法：除留余数法、直接定址法、数字分析法；哈希冲突解决方法：开放地址法、链表法。(4) 哈希表的完整设计过程，包括：哈希表的构建、元素的插入与删除、哈希表查找效率。2. 教学目的及要求(1) 掌握静态查找表的四种查找方法（顺序查找、折半查找、静态树表、索引查找）的实现；(2) 掌握动态查找表（二叉排序树、二叉平衡树、B-和B+树、键树）的构造和查找方法；(3) 掌握哈希表构造方法，哈希表的查找以及衡量查找效率的平均查找长度的讨论。3. 教学重点(1) 二分查找；(2) 二叉排序树的查找；(3) 哈希表查找。4. 教学难点(1) 哈希表中哈希函数的设计与哈希冲突解决方法。5. 教学思路与教学方法(1) 以课堂多媒体教学为主，辅助以黑板进行绘图分析；(2) 课后完成上机实验，练习二分查找、二叉排序树查找及哈希表查找的算法设计，以巩固课堂所学知识点。(3) 板书设计：a） 以文字描述为主，要点及关键词用不同颜色标注；