教学大纲1 教学目的一些著名的计算机科学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。

算法与数据结构正是一门面向设计，且处于计算机学科核心地位的教育课程。

通过对算法与数据结构的系统学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础，对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。

计算机科学与技术专业的人员应该具有4种基本的专业能力：计算思维能力，算法设计与分析能力，程序设计和实现能力，计算机软硬件系统的认知，分析，设计与应用能力。

本课程着重于培养学生的算法设计与分析能力，程序设计和实现能力。

2 教学内容的结构模块以教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”为依据，以基本数据结构为知识单元，包括引论、表、栈、队列、排序与选择、树、图、集合、符号表、字典、优先队列、并查集共十二章节。

2.1 课堂教学大纲（共计52学时）第1章引论（4学时）知识点：本章介绍算法的基本概念、表达算法的抽象机制以及算法的计算复杂性概念和分析方法。

简要阐述数据类型、数据结构和抽象数据类型的基本概念以及这3个重要概念的区别和内在联系。

最后简要概述C语言的若干重要特性和采用C与自然语言相结合的方式描述算法的方法。

本章内容是后续各章叙述算法和描述数据结构的基础和准备。

重点：• 理解算法的概念。

• 理解什么是程序，程序与算法的区别和内在联系。

• 能够列举求解问题的基本步骤。

• 掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念。

• 掌握算法复杂性的渐近性态的数学表述。

• 了解表达算法的抽象机制。

• 熟悉抽象数据类型的基本概念。

• 熟悉数据类型和数据结构的概念。

• 理解数据结构、数据类型和抽象数据类型三者的区别和联系。

• 掌握用C语言描述算法与数据结构的方法。

难点：掌握用C语言描述算法与数据结构的方法第2章表（4学时）知识点：本章介绍抽象数据类型表的基本概念及其逻辑特征。

简要阐述实现抽象数据类型的一般步骤。

按照抽象数据类型设计和实现的一般性原则，详细介绍实践中常用的实现表的方法，如用数组实现表的方法、用指针实现表的方法、用间接寻址技术实现表的方法、用游标实现表的方法、单循环链表和双链表以及表的搜索游标的实现方法和步骤。

重点：• 理解表是由同一类型的元素组成的有限序列的概念。

• 熟悉定义在抽象数据类型表上的基本运算。

• 掌握实现抽象数据类型的一般步骤。

• 掌握用数组实现表的步骤和方法。

• 掌握用指针实现表的步骤和方法。

• 掌握用间接寻址技术实现表的步骤和方法。

• 掌握用游标实现表的步骤和方法。

• 掌握单循环链表的实现方法和步骤。

• 掌握双链表的实现方法和步骤。

• 熟悉表的搜索游标的概念和实现方法。

难点：掌握用数组实现表的步骤和方法、掌握用指针实现表的步骤和方法。

第3章栈（3学时）知识点：本章介绍抽象数据类型栈的基本概念及其逻辑特征。

按照抽象数据类型设计和实现的一般性原则，详细介绍实践中常用的用数组实现栈的方法和用指针实现栈的方法。

最后以集合的等价类划分问题为例讨论栈的应用方法。

本章介绍的抽象数据类型栈在后续各章中还会反复用到。

重点：• 理解栈是满足LIFO存取原则的表。

• 熟悉定义在抽象数据类型栈上的基本运算。

• 掌握用数组实现栈的步骤和方法。

• 掌握用指针实现栈的步骤和方法。

• 理解用栈解决实际问题的方法。

难点：用栈解决实际问题的方法。

第4章队列（3学时）知识点：本章介绍抽象数据类型队列的基本概念及其逻辑特征。

按照抽象数据类型设计和实现的一般性原则，详细介绍实践中常用的用指针实现队列的方法和用循环数组实现队列的方法。

最后以电路布线问题为例讨论队列的应用方法。

本章介绍的抽象数据类型队列在后续各章中还会反复用到。

重点：• 理解队列是满足FIFO存取原则的表。

• 熟悉定义在抽象数据类型队列上的基本运算。

• 掌握用指针实现队列的步骤和方法。

• 掌握用循环数组实现队列的步骤和方法。

• 理解用队列解决实际问题的方法。

难点：用队列解决实际问题的方法。

第5章排序与选择（6学时）知识点：本章讲授的主题是排序算法。

在明确了排序问题的提法及其实质后，介绍在实践中常用的简单排序算法，如冒泡排序算法、插入排序算法和选择排序算法的设计思想与分析方法。

快速排序算法是一个效率高且实用性强的排序算法。

本章用较大篇幅介绍快速排序算法的基本设计思想及其多方面的改进，借此展示算法设计中精益求精的设计思想和策略。

合并排序算法是另一个用分治和递归策略设计算法的经典例子。

本章对合并排序算法也展开深入细致的讨论。

计数排序算法和桶排序算法是2个典型的线性时间排序算法。

本章通过对这2个算法的讨论阐述线性时间排序算法的设计思想与分析方法，并进一步讨论线性时间排序算法与基于比较的排序算法的主要差别和适用范围。

本章还介绍与排序问题类似的选择问题及相应的算法。

从平均情况和最坏情况2个不同侧面研究算法的设计思想及实现方法。

重点：• 理解排序问题的实质。

• 掌握简单排序算法的设计思想与分析方法。

• 掌握快速排序算法的设计思想与分析方法。

• 理解随机化思想在快速排序算法中的应用。

• 掌握合并排序算法的基本思想及实现方法。

• 掌握计数排序算法的设计思想与分析方法。

•掌握桶排序算法的设计思想与分析方法。

• 理解线性时间排序与基于比较排序算法的主要差别和适用范围。

• 掌握平均情况下线性时间选择算法的设计思想与分析方法。

• 掌握最坏情况下线性时间选择算法的设计思想与分析方法。

难点：理解线性时间排序与基于比较排序算法的主要差别和适用范围第6章树（6学时）知识点：本章主要讲授常用的非线性层次结构树以及作为抽象数据类型的树的一般操作和一些常用的表示树的数据结构。

在给出树的准确定义后，讨论树的前序遍历、中序遍历和后序遍历方法。

对于一般情况下的树结构，介绍实践中常用的树的父结点数组表示法、树的儿子链表表示法和树的左儿子右兄弟表示法。

二叉树是一类非常重要的特殊的树形结构，也是本章内容的重点。

二叉树和ADT 二叉树的概念是本章的核心概念，在后续各章中也反复用到。

二叉树的顺序存储结构、二叉树的结点度表示法和用指针实现二叉树的方法是实现二叉树的3种常见方法。

本章着重讨论用指针实现二叉树的方法。

在此方法的基础上还引伸出线索二叉树结构。

最后以信号传输网络中最优信号增强装置布局问题为例讨论树结构在实际问题中的应用方法。

重点：• 理解树的定义和与树相关的结点、度、路径等术语。

• 理解树是一个非线性层次数据结构。

• 掌握树的前序遍历、中序遍历和后序遍历方法。

• 了解树的父结点数组表示法。

• 了解树的儿子链表表示法。

• 了解树的左儿子右兄弟表示法。

• 理解二叉树和ADT二叉树的概念。

• 了解二叉树的顺序存储结构。

• 了解二叉树的结点度表示法。

• 掌握用指针实现二叉树的方法。

• 理解线索二叉树结构及其适用范围。

难点：用指针实现二叉树的方法第7章图（12学时）知识点：本章讲授实践中常用的表示复杂非线性关系的数据结构图，以及作为抽象数据类型的图的一般操作和表示图的数据结构。

本章着重介绍图的邻接矩阵表示及其实现方法、图的邻接表表示及其实现方法以及图的紧缩邻接表表示方法。

在此基础上讨论遍历一个图的2个重要方法，即图的深度优先搜索和广度优先搜索算法。

对于实际应用中常遇到的最短路问题，本章详细叙述单源最短路径问题的Dijkstra算法和Bellman-Ford算法以及所有顶点对之间最短路径问题的Floyd算法。

最小支撑树问题是另一个经典的图论问题。

本章讨论构造最小支撑树的Prim算法和Kruskal算法。

讨论了无圈有向图DAG的拓扑排序及其最短路径和最长路径的求法。

最后介绍二分图的概念及其相关的图匹配问题，并讨论最大匹配问题的增广路径算法。

重点：• 理解图的定义和与图相关的有向图、无向图、赋权图、连通图等术语。

• 理解图是一个表示复杂非线性关系的数据结构。

• 掌握图的邻接矩阵表示及其实现方法。

• 掌握图的邻接表表示及其实现方法。

• 了解图的紧缩邻接表表示方法。

• 掌握图的广度优先搜索方法。

• 掌握图的深度优先搜索方法。

• 掌握单源最短路径问题的Dijkstra算法。

• 掌握带负权边的无向图的Bellman-Ford算法。

• 掌握所有顶点对之间最短路径问题的Floyd算法。

• 掌握无圈有向图DAG的拓扑排序算法。

• 掌握求DAG的最短路径、最长路径及所有顶点对之间的最短路径的算法。

• 掌握构造最小支撑树的Prim算法。

• 掌握构造最小支撑树的Kruskal算法。

• 理解图的最大匹配问题的增广路径算法。

难点：• 掌握单源最短路径问题的Dijkstra算法。

• 掌握带负权边的无向图的Bellman-Ford算法。

• 掌握所有顶点对之间最短路径问题的Floyd算法。

• 掌握构造最小支撑树的Prim算法。

• 掌握构造最小支撑树的Kruskal算法。

• 理解图的最大匹配问题的增广路径算法。

第8章集合（2学时）知识点：本章讲授的主题是集合和以集合为基础的抽象数据类型，并介绍了如何用位向量和链表两种方式实现集合。

重点：• 理解集合的概念。

• 理解以集合为基础的抽象数据类型。

• 掌握用位向量实现集合的方法。

• 掌握用链表实现集合的方法。

难点：掌握用位向量实现集合的方法。

第9章符号表（2学时）知识点：本章讲授了符号表的概念以及用数组、开散列、闭散列三种实现符号表的方法。

同时介绍了多种常用的散列函数构造方法，如：除余法、数乘法、平方取中法等以及主要的几种解决冲突的方法，如：线性探测法、二次探测法等。

重点：• 理解抽象数据类型符号表的概念。

• 掌握数组实现符号表的方法。

• 理解开散列和闭散列的概念。

• 掌握用开散列表实现符号表的方法。

• 掌握除余法、数乘法、平方取中法、基数转换法和随机数法等散列函数构造方法。

• 掌握采用线性重新散列技术的闭散列表实现符号表的方法。

难点：• 掌握用开散列表实现符号表的方法。

• 掌握采用线性重新散列技术的闭散列表实现符号表的方法。

第10章字典（4学时）知识点：本章介绍了字典的概念，用数组和二叉搜索树实现字典的方法，另外，在此基础上讲授了AVL树的概念及相关运算。

重点：• 理解以有序集为基础的抽象数据类型字典。

• 理解用数组实现字典的方法。

• 理解二叉搜索树的概念和实现方法。

• 掌握用二叉搜索树实现字典的方法。

• 理解AVL树的定义和性质。

• 掌握二叉搜索树的结点旋转变换及实现方法。

• 掌握AVL树的插入重新平衡运算及实现方法。

• 掌握AVL树的删除重新平衡运算及实现方法。