各章讲重点.ppt

* * 数据结构 各章重点与难点 第一章 绪论 【学习目标】　　熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。 【重点和难点】　　本章讨论的都是一些基本概念，因此没有难点，重点在于了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。? 【知识点】　　数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度 第一章 绪论 （续） 【学习指南】 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。　　 2. 了解抽象数据类型的定义、表示和实现方法。　　 3. 熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。　　 4. 理解算法五个要素的确切含义和对算法正确性的理解。　　　 5. 掌握计算语句频度和估算算法时间复杂度的方法。 第二章 线性表 【学习目标】　1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 　2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 　3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 　4. 结合线性表类型的定义增强对抽象数据类型的理解。 【重点和难点】　　链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。 【知识点】　　线性表、顺序表、链表 【学习指南】 本章建议完成的算法设计题为：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38 第二章 线性表 (续) 第三章 栈和队列 【学习目标】　1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 　2. 熟练掌握栈类型的两种实现方法(顺序栈和链栈)。 　3. 熟练掌握循环队列和链队列的基本操作实现算法。 　4. 理解递归算法执行过程中栈的状态变化过程。 第三章 栈和队列 (续) 【重点和难点】　　栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。 【知识点】　　顺序栈、链栈、循环队列、链队列 【学习指南】　　本章建议完成的算法设计题为：3.15，3.17，3.19，3.22，3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。 第四章 串 【学习目标】1. 理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。 2. 理解串类型的各种存储表示方法。 (定长顺序,堆分配存储,块链存储) 　3. 理解串匹配的各种算法( BF / KMP )。　 第五章 数组和广义表 【学习目标】 1. 理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法。 2 .掌握广义表的结构特点及其存储表示方法。 　 3.掌握特殊矩阵的存储压缩表示方法。　 4.理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。 第五章 数组和广义表（续） 【重点和难点】　　本章重点是学习数组类型的定义及其存储表示。 【知识点】　　数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。广义表的类型定义、广义表的存储表示 【学习指南】　　从学习利用高级语言编制程序开始，数组是大家惯用的存储批量数据的工具，前几章讨论的线性结构的顺序存储结构也都是利用数组来描述的，那么数组本身又是怎么实现的呢？因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法。对于本章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法。 第六章 树和二叉树 【学习目标】 1．领会树和二叉树的类型定义，理解树和二叉树的结构差别 2．熟记二叉树的主要特性，并掌握它们的证明方法。 3．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 4．理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 5．熟练掌握二叉树和树的各种存储结构及其建立的算法。