-
第一章绪论
本章将首先介绍数据结构的非数值计算研究方向、数据结构基本概念，以及数据结构所研究的三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算，讨论线性结构（线性表、栈、队列）和非线性结构（树、图、集合）的逻辑特征，以及数据存储的四种基本方法；然后介绍算法的概念、特性、评价标准、描述、与程序的区别等；最后介绍算法分析与复杂度计算，尤其是时间复杂度的概念及计算。
-
●1.1数据结构的概念
本节主要介绍数据结构的研究方向、数据结构基本概念以及数据结构研究的三方面内容。
-
●1.2算法及其特点
本节主要介绍算法的概念、特性、评价标准、描述、与程序的区别等。
-
●1.3算法分析与复杂度计算
本节主要介绍算法分析与复杂度计算，尤其是时间复杂度的概念及计算。
-
第二章线性表
本章将介绍绍线性表的定义、运算，讨论线性表的两种存储结构——顺序表和链表，以及在这两种存储结构上实现的基本运算。
-
●2.1线性表的概念
本节主要介绍线性表的定义和线性表的基本操作。
-
●2.2线性表的顺序存储
本节主要介绍线性表顺序存储的概念和线性表顺序存储基本操作的实现。
-
●2.3线性表的链式存储（上）
逻辑上线性表其存储方式有顺序存储和链式存储。这一讲主要介绍链式存储中单链表的定义以及头插法和尾插法创建单链表的实现过程。
-
●2.4线性表的链式存储（中）
线性表的顺序存储不适合做插入与删除操作，而链表的特性使在线性表插入删除操作实现起来非常便利，所以需要经常做插入和删除操作的线性表适合采取链式存储。本讲主要介绍单链表的插入和删除操作的实现。
-
●2.5线性表的链式存储（下）
单链表的每个结点中只有一个指向直接后继结点的next指针域，因此链表操作时只能按单一方向从前向后进行搜索，无法向前搜索，即使引入单循环链表问题也没有根本解决，因此引入了双向链表，即在链表的每一个结点中有两个指针域，一个指向直接前驱一个指向直接后继。本节主要学习单循环链表以及双向链表的插入删除操作的实现。
-
第三章栈与队列
栈和队列是两种重要的数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制，栈按照“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，因此它们也被称为受限的线性表。
-
●3.1栈的定义与顺序栈
栈是限制在表的一端进行插入和删除的线性表。允许插入和删除的一端为栈顶，另一端为栈底，当表中没有元素时称为空栈。栈的基本操作是插入和删除，一般称为入栈和出栈。栈按照存储结构可分为顺序栈和链栈两类，顺序栈一般用数组来实现，链栈用链指针连接数据元素节点来实现。
-
●3.2链栈与栈的应用
链栈是栈的一种实现形式，通过链指针连接数据元素来实现。栈的应用包括表达式求值，括号匹配。
-
●3.3队列的定义及顺序队列
队列是限制在表的一段进行插入，另一端进行删除的的线性表，分别对应于入队和出队操作。队列按照存储结构可分为顺序队列和链队列两类，顺序队列一般用数组实现，链队列用链指针连接数据元素节点来实现。
-
●3.4 链队列与队列的应用
链队列是队列的一种实现形式，通过链指针连接数据元素来实现。
-
●3.5栈在消除递归中的应用举例
递归是一种常用的算法设计思想。递归算法通常描述简洁、思路清晰、程序可读性和可维护性好，但递归程序的执行因其时间和空间开销的增大而效率很低。如何将递归过程变为非递归执行过程？结合函数调用特征以及栈的工作特征，因此在消除递归函数时通常使用栈这种数据结构。本节主要通过一个实例介绍栈在消除递归过程中的应用。
-
●3.6栈与队列的综合应用
栈与队列的综合应用
-
第四章串
串（即字符串）是一种特殊的线性表，它的数据元素仅有字符组成，计算机非数值处理对象经常是字符串数据，如在汇编和高级语言的编译程序中，源代码和目标代码都是字符串数据；在商业应用程序中，客户的姓名和地址，商品的名称和产地等信息，一般也是作为字符串处理的。另外串还有自身的特性，常常把一个串作为一个整体来处理，因此，在这一章把串作为独立的概念加以研究，介绍串的存储结构以及基本运算。
-
●4.1串的定义与运算
串的定义与基本运算：字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的。串的基本运算较多，主要有串拷贝、串连接、串比较、求串长、求子串等。
-
●4.2串的简单模式匹配-BF算法
串的简单模式匹配-BF算法
-
●4.3串的模式匹配-KMP算法
串的模式匹配-KMP算法
-
第五章数组与广义表
数组与广义表
-
●5.1数组的概念与存储
数组的概念与存储
-
●5.2广义表及其存储
广义表及其存储
-
第六章树与二叉树
树是一种非线性的逻辑结构，它描述的数据元素之间的关系是一对多的，呈现出类似自然界中树的形状。这种树形的层次结构在生活中广泛存在，其应用也十分广泛。本章介绍树的有关概念和性质、二叉树的概念、存储、遍历、树、森林与二叉树的转换、哈夫曼树等。
-
●6.1树的基本概念
树形结构是一类非常重要的非线性结构，是以分支关系定义的层次结构，其应用非常广泛，其中二叉树是本章的重点。
-
●6.2二叉树的概念与存储
二叉树是最基本、最重要的树形结构，它有5个重要性质，主要的存储方法是二叉链表存储。
-
●6.3树与二叉树性质与应用举例
本节将对树与二叉树相关性质的应用习题进行解答。
-
●6.4 二叉树的遍历
二叉树的遍历是树与二叉树的许多操作的基础。本节主要介绍二叉树的4种遍历算法思想及其算法实现过程。这4种遍历有：先根遍历、中根遍历、后根遍历和层次遍历。对于前3种遍历本讲仅涉及其递归算法实现。
-
●6.5二叉树遍历的非递归算法实现
二叉树遍历的非递归算法实现
-
●6.6树与森林
本小节的主要内容一是树的存储表示法，二是树、森林与二叉树之间的转换，三是树和森林的遍历法。
-
●6.7二叉树的线索化(上）
二叉树的线索化(上）
-
●6.8二叉树的线索化(下）
二叉树的线索化(下）
-
●6.9哈夫曼树的构造
信息编码方法的优劣直接影响信息传递的效率。一种好的编码方法应该满足译码无二义性，总编码长度最短。哈夫曼编码就是一种能满足这两个条件的编码方法。本节主要学习哈夫曼编码的原理以及如何构造哈夫曼树的算法过程。
-
第七章图
图是一种逻辑关系更为复杂的一种逻辑结构，其应用十分广泛。本章首先介绍图的基本概念和有关术语，介绍图的两种存储方式（邻接矩阵、邻接表），接着学习图的两种遍历算法（图的深度和广度优先遍历）以及最小生成树的构造（普里姆算法和克鲁斯卡尔算法），最后学习最短路径（Dijkstra算法和Floyd算法）和拓扑排序和关键路径；
-
●7.1图的概念与性质
要学习图的算法，首先必须了解图的概念及相关术语。本节介绍图的定义和有关图的一些术语以及图的一些基本性质。
-
●7.2图的存储
图在计算机中的存储有多种方案，本节主要介绍图的邻接矩阵以及邻接表存储。由于图的各种操作实现均依赖于其存储结构，因此要求理解并掌握这两种不同存储结构的特点。
-
●7.3图的深度遍历
图的遍历是图的许多操作的基础。图的常用的两种遍历方法是深度优先搜索和广度遍历。本节主要学习深度优先遍历的算法思想，并介绍了基于邻接矩阵和邻接表的深度优先遍历的实现。
-
●7.4图的广度遍历
图的常用两种遍历方法是深度优先搜索和广度优先搜索。本节主要学习广度优先遍历策略的算法思想，并介绍了基于邻接矩阵和邻接表的广度优先遍历的实现。
-
●7.5最小生成树-prim算法
在图的广泛应用中，一个非常常见的应用是构造最小生成树。Prim算法是一种构造连通图的最小生成树的贪心算法，本节主要学习Prim的算法思想及其算法实现。
-
●7.6最小生成树-kruskal算法
Kruskal算法是另一种构造连通图的最小生成树的算法，本节介绍Kruskal算法思想以及算法实现。
-
●7.7单源最短路径-Dijkstra算法
在许多图的应用中，另一个常见的应用就是找最短路径，其中一个就是求单源最短路径，即寻求从图的某个顶点出发到其余各顶点的最短路径。本节主要介绍Dijkstra算法的思想及算法实现。
-
●7.8两点之间最短路径-Floyd算法
Floyd算法主要用于构造图中任意两点间的最短路径。本节主要介绍Floyd算法思想及其算法实现。
-
●7.9拓扑排序
一个大的工程能否顺利完工，其中一个关键问题是在其所有子工程构成的AOV网中能否确定一个顶点的拓扑序列。本节介绍拓扑序列的构造思想以及算法实现。
-
●7.10关键路径
关键路径
-
●7.11图的应用
图的应用
-
第八章查找
查找
-
●8.1查找的概念与顺序查找
查找的概念与顺序查找
-
●8.2折半查找
折半查找
-
●8.3平衡二叉树
树表形式的动态查找
-
●8.4树表形式的动态查找
平衡二叉树
-
●8.5地址映射下的动态查找-哈希查找
地址映射下动态查找-哈希查找
-
●8.6B树与B+树
B树与B+树
-
第九章排序
本章介绍了排序的概念及常用排序方法，包括插入排序中的直接插入、折半插入排序和希尔排序，交换排序中的冒泡排序和快速排序，选择排序中的简单选择和堆排序等。每种排序算法分别介绍了基本思想、排序过程、具体实现及主要性能指标。
-
●9.1 排序基本概念
本节首先介绍了和排序相关的基本概念，主要包括排序的定义、目的、分类及排序算法的性能重要评价指标，最后给出了本章排序算法中所需使用的数据类型定义。
-
●9.2直接插入排序及折半插入排序
直接插入排序与折半排序
-
●9.3希尔排序
本节介绍了插入排序中的直接插入和折半插入排序。二者的区别为在有序表中查找插入位置时，分别采用了顺序查找和折半查找。在平均情况下，由于折半插入排序减少了查找过程关键字的比较次数，其性能高于直接插入排序。
-
●9.4冒泡排序
本节介绍了交换排序中的冒泡排序，其核心思想是对待排序范围内相邻元素关键字进行比较，发现逆序则交换。单向冒泡排序的冒泡方向有自下至上和自上至下两种，通过采用双向冒泡算法可有效提高原有单向冒泡算法的效率。
-
●9.5快速排序
本节介绍了交换排序中的快速排序。快速排序在每趟排序中通过左右交替方向的扫描将基准元素定位在数据表的恰当位置上。将当数据表规模较大时，在平均情况下它是所有内部排序方法中速度最快的一种。
-
●9.6简单选择排序
本节介绍了选择排序中的简单选择排序。简单选择排序通过每趟排序在待排序范围中选择出关键字最小或最大的元素，之后和待排序范围中第一个元素进行交换的方法来实现数据表的有序排列。
-
●9.7堆排序
堆排序通过引入树形选择思想对简单选择排序进行了改进，将待排序的数据表看作是完全二叉树的顺序存储形式。本节介绍了最大及最小堆的概念，堆排序基本思想，初始堆建立和利用最大堆实现升序排列的堆排序具体实现方法。
-
●9.8归并排序
归并排序
-
●9.9基数排序
基数排序