复习提纲数据结构

1、本次课重点：本次课重点：1. 数据结构的基本概念；数据结构的基本概念；2. 数据的逻辑结构、存储结构以数据的逻辑结构、存储结构以 及二者之间的关系；及二者之间的关系；3. 算法及特性。算法及特性。本次课重点：本次课重点：1. 估算算法时间复杂度的基本方法；估算算法时间复杂度的基本方法；2. 大大记号的意义；记号的意义；3.问题规模、基本语句；问题规模、基本语句；4. 线性表的定义；线性表的定义；5. 线性表的逻辑特征；线性表的逻辑特征；6. 顺序表的存储要点及存储特点；顺序表的存储要点及存储特点；7. 顺序表的随机存取特性；顺序表的随机存取特性；本次课重点：本次课重点：1. 1. 顺序表类的构

2、造函数；（了解）顺序表类的构造函数；（了解）2. 2. 顺序表插入、删除、查找操作的实现；顺序表插入、删除、查找操作的实现；3.3.顺序表插入、删除、查找操作的时间性能。顺序表插入、删除、查找操作的时间性能。本次课重点：本次课重点：1. 1. 单链表的存储要点及存储特点；单链表的存储要点及存储特点；2. 2. 单链表的顺序存取特性；单链表的顺序存取特性；3. 3. 单链表的插入、删除操作；单链表的插入、删除操作；4. 4. 单链表的插入、删除操作操作的时间性能。单链表的插入、删除操作操作的时间性能。本次课重点：本次课重点：1. 1. 单链表类的构造函数和析构函数（了解）；单链表类的构造函数和析

3、构函数（了解）；2. 2. 顺序表和单链表的比较；顺序表和单链表的比较；3. 3. 循环链表的存储结构；循环链表的存储结构；4. 4. 循环链表的操作。循环链表的操作。本次课重点：本次课重点：1. 1. 双链表的存储结构；双链表的存储结构；2. 2. 双链表的插入、删除操作；双链表的插入、删除操作；3. 3. 静态链表的存储结构；（了解）静态链表的存储结构；（了解）本次课重点：本次课重点：1. 1. 栈的定义及操作特性；栈的定义及操作特性；2. 2. 顺序栈及实现；顺序栈及实现；3. 3. 链栈及实现；链栈及实现；4. 4. 顺序栈和链栈的比较；顺序栈和链栈的比较；5. 5. 队列的定义及操作

4、特性；队列的定义及操作特性；6. 6. 循环队列及实现；循环队列及实现；7. 7. 顺序队列的假溢出现象。顺序队列的假溢出现象。本次课重点：本次课重点：1. 1. 循环队列及实现；循环队列及实现； 2. 2. 链队列及实现；链队列及实现；本次课重点：本次课重点：1. 1. 递归的定义；（课本上没有，讲课时有讲）递归的定义；（课本上没有，讲课时有讲） 2. 2. 树的定义；树的定义；3. 3. 树的基本术语；树的基本术语；4. 4. 树的遍历操作；树的遍历操作；本次课重点：本次课重点：1. 1. 树的双亲表示法；（了解）树的双亲表示法；（了解）2. 2. 树的孩子链表表示法；（了解）树的孩子链表

5、表示法；（了解）3. 3. 树的双亲孩子表示法；（了解）树的双亲孩子表示法；（了解）4. 4. 树的孩子兄弟表示法。树的孩子兄弟表示法。本次课重点：本次课重点：1.1.二叉树的基本术语和定义二叉树的基本术语和定义2.2.二叉树的性质（课本上的二叉树的性质（课本上的5 5个性质，个性质，不仅要掌握，而且要会灵活运用）不仅要掌握，而且要会灵活运用）3.3.二叉树的各种遍历操作二叉树的各种遍历操作本次课重点：本次课重点：* *已知一棵二叉树的前序序列和中序序列，如已知一棵二叉树的前序序列和中序序列，如何确定这棵二叉树（要求会操作，不是会讲何确定这棵二叉树（要求会操作，不是会讲理论）理论）1.1.二叉

6、树的顺序存储结构。二叉树的顺序存储结构。2.2.二叉链表存储结构。（熟练掌握）二叉链表存储结构。（熟练掌握）3.3.二叉树遍历算法的递归实现。（熟练掌握）二叉树遍历算法的递归实现。（熟练掌握）4.4.二叉树前序遍历的非递归算法。（了解）二叉树前序遍历的非递归算法。（了解）本次课重点：本次课重点：1.1.二叉树的二叉链表存储结构二叉树的二叉链表存储结构2.2.二叉树中序线索链表的建立二叉树中序线索链表的建立本次课重点：本次课重点：1.1.在中序线索链表上查找某个结点的后继。在中序线索链表上查找某个结点的后继。（了解）（了解）2. 2. 树转换为二叉树。（熟练掌握树转换为二叉树。（熟练掌握) )3

7、. 3. 森林转换为二叉树。（熟练掌握森林转换为二叉树。（熟练掌握) )4. 4. 二叉树转换为树（或森林）。（熟练掌握二叉树转换为树（或森林）。（熟练掌握) )本次课重点：本次课重点：1.1.哈夫曼树的构造方法。（熟练掌握哈夫曼树的构造方法。（熟练掌握) )2. 2. 哈夫曼编码与解码方法。哈夫曼编码与解码方法。本次课重点：本次课重点：1.1.图的定义和若干基本术语。（熟练掌握图的定义和若干基本术语。（熟练掌握) )2. 2. 图的深度优先遍历。（熟练掌握）图的深度优先遍历。（熟练掌握）本次课重点：本次课重点：1. 1. 图的广度优先遍历。（熟练掌握）图的广度优先遍历。（熟练掌握）2.2.图

8、的邻接矩阵存储结构。（熟练掌握图的邻接矩阵存储结构。（熟练掌握) )3.3.邻接矩阵存储类的构造函数。（熟练掌握邻接矩阵存储类的构造函数。（熟练掌握) )本次课重点：本次课重点：1.1.图的邻接表存储结构。（熟练掌握图的邻接表存储结构。（熟练掌握) )2.2.邻接表存储类的构造函数。（熟练掌握邻接表存储类的构造函数。（熟练掌握) )3.3.基于邻接表的深度优先遍历算法。（了解）基于邻接表的深度优先遍历算法。（了解）4.4.基于邻接表的广度优先遍历算法。（了解）基于邻接表的广度优先遍历算法。（了解）5.5.无向图的连通性。无向图的连通性。上次课重点：上次课重点： PrimPrim算法的求解思想、

9、过程及使用的最有利条算法的求解思想、过程及使用的最有利条件（稠密图）。（熟练掌握件（稠密图）。（熟练掌握) ) PrimPrim算法的伪代码描述。（了解）算法的伪代码描述。（了解） KruskalKruskal算法的求解思想、过程算法的求解思想、过程及使用的最有利及使用的最有利条件（稀疏图）条件（稀疏图）。（熟练掌握。（熟练掌握) )4. Kruskal4. Kruskal算法的伪代码描述。（了解）算法的伪代码描述。（了解）5. Dijkstra5. Dijkstra算法的求解思想、过程。（熟练掌握算法的求解思想、过程。（熟练掌握) )6. Dijkstra6. Dijkstra算法的伪代码描述。（了解）算法的伪代码描述。（了解）本次课重点：本次课重点：1. 1. 拓扑序列的定义。（掌握）拓扑序列的定义。（掌握）2. 2. 拓扑排序算法的求解思想及过程。（掌握拓扑排序算法的求解思想及过程。（掌握) )3. 3. 排序的基本术语，如内部排序、外部排序等。排序的基本术语，如内部排序、外部排序等。4. 4. 直接插入排序，起泡排序，快速排序算法思想，直接插入排序，起泡排序，快速排序算法思想，针对具体实例的操作过程，