数据结构是计算机科学与技术、网路工程、软体工程、信息安全等专业的重要基础课，是这些专业的核心课程之一，是一门集技术性、理论性和实践性于一体的课程。

本书重点介绍抽象数据类型、基本数据结构、算法性能评价、C++语言描述数据结构、数据结构的套用等内容，进一步使读者理解数据抽象与面向对象编程实现的关係，提高使用计算机解决实际问题的能力。

本书内容包括基本数据类型、抽象数据类型、算法效率分析、顺序表、鍊表、树和二叉树、图、多维数组等内容。

本书结构合理，内容丰富，算法理论分析详细，数据结构的算法描述丰富。书中用C++语言编写的算法代码都已调试通过，便于自学。

本书可作为高等学校计算机科学与技术、网路工程、软体工程、信息安全等专业以及军事院校的基础合训或其他相关专业的教材和参考书

第1章数据结构概述

1.1基本概念

1.1.1数据、数据元素和数据对象

1.1.2数据结构

1.2数据结构的分类

1.3抽象数据类型

1.3.1两种软体设计方法

1.3.2数据类型

1.3.3抽象数据类型

1.4算法和算法分析

1.4.1算法的概念

1.4.2算法分析

习题

第2章顺序表

2.1线性表

2.1.1线性表的抽象数据类型表示

2.1.2线性表的类表示

2.2数组

2.2.1数组的抽象数据类型

2.2.2数组元素的插入和删除

2.2.3数组的套用

2.3栈

2.3.1栈的抽象数据类型及其实现

2.3.2栈的套用

2.4伫列

2.4.1伫列的抽象数据类型及其实现

2.4.2优先权伫列

2.4.3伫列的套用——离散事件驱动模拟

习题

第3章鍊表

3.1动态数据结构

3.2单鍊表

3.2.1基本概念

3.2.2单鍊表结点类

3.2.3单鍊表类

3.2.4栈的单鍊表实现

3.2.5链式伫列

3.2.6鍊表的套用举例

3.3循环鍊表

3.4双鍊表

习题

第4章排序

4.1基本概念

4.2插入排序

4.2.1直接插入排序

4.2.2折半插入排序

4.2.3Shell排序

4.3选择排序

4.3.1直接选择排序

4.3.2树形选择排序

4.4交换排序

4.4.1冒泡排序

4.4.2快速排序

4.5分配排序

4.5.1基本思想

4.5.2基数排序

4.6归併排序

*4.7外部排序

4.7.1二路合併排序

4.7.2多路替代选择合併排序

4.7.3最佳合併排序

*4.8排序算法的时间下界

习题

第5章查找

5.1基本概念

5.2顺序查找

5.3折半查找

5.4分块查找

5.5字元串的模式匹配

5.5.1朴素的模式匹配算法

5.5.2KMP匹配算法

5.5.3算法效率分析

5.6散列查找

5.6.1概述

5.6.2散列函式

5.6.3冲突的处理

5.6.4散列查找的效率

习题

第6章树和二叉树

6.1树的概念

6.2二叉树

6.2.1二叉树的概念

6.2.2二叉树的性质

6.2.3二叉树的存储方式

6.2.4树(树林)与二叉树的相互转换

6.3树(树林)、二叉树的遍历

6.3.1树(树林)的遍历

6.3.2二叉树的遍历

6.4抽象数据类型BinaryTree以及类BinaryTree

6.4.1抽象数据类型BinaryTree

6.4.2一个完整包含类BinaryTreeNode和类BinaryTree实现的例子

6.5二叉树的遍历算法

6.5.1非递归(使用栈)的遍历算法

6.5.2线索化二叉树的遍历

习题

第7章树形结构的套用

7.1二叉排序树

7.1.1二叉排序树与类BinarySTree

7.1.2二叉排序树的检索、插入和删除运算

7.1.3等机率查找对应的最佳二叉排序树

7.2平衡的二叉排序树

7.2.1平衡的二叉排序树与类AVLTree

7.2.2平衡二叉排序树的插入和删除

7.2.3类AVLTree与AVL树高度

7.3B树、B+树

*7.423树

*7.5红黑树

7.6Huffman最优二叉树

7.6.1Huffman最优二叉树概述

7.6.2树编码

7.7堆排序

*7.8判定树

*7.9等价类和并查集

7.9.1等价类

7.9.2并查集

*7.10键树

习题

第8章图

8.1基本概念

8.2图的存储表示

8.2.1相邻矩阵表示图

8.2.2图的邻接表表示

8.2.3邻接多重表

8.3构造Graph类

8.3.1基于邻接表表示的Graph类

8.3.2Graph类的实现

8.4图的遍历

8.4.1深度优先遍历

8.4.2广度优先遍历

8.5最小代价生成树

8.6单源最短路径问题——Dijkstra算法

8.7每一对顶点间的最短路径问题

8.8有向无迴路图

8.8.1DAG图和AOV、AOE网

8.8.2AOV网的拓扑排序

8.8.3AOE网的关键路径

习题

第9章多维数组

9.1多维数组的顺序存储

9.2特殊矩阵的顺序存储

9.3稀疏矩阵的存储

9.4抽象数据类型稀疏矩阵与class SparseMatrix

习题

附录Nodelib.h

参考文献

C O N T E N T S

表目录

表1.1学生情况表

表5.1四种处理冲突方法的平均查找长度

表8.1从S到其他结点的最短路径

表8.2Dijkstra算法中dist数组的变化情况

表8.3计算机软体专业必修课程

C O N T E N T S

图目录

图1.1基本的逻辑结构

图1.2基本的逻辑结构

图1.3矩形游泳池

图2.1顺序存储的栈

图2.2中缀表达式的计值过程

图2.3后缀表达式的计值

图2.4中缀表达式转换成后缀表达式的过程

图2.5汉诺塔问题的递归求解过程

图2.6活动记录的进栈情况

图2.7活动记录的退栈情况

图2.8顺序存储的伫列

图2.9伫列的操作

图2.10循环伫列的队空和队满

图2.11事件驱动过程

图2.12事件优先伫列的管理

图3.1单鍊表

图3.2从鍊表中删除一个结点

图3.3往鍊表中插入一个结点

图3.4附加头结点的单鍊表

图3.5一个实际的单鍊表结构

图3.6空的循环鍊表

图3.7双链结点

图3.8双鍊表

图3.9往双鍊表中插入一个结点

图3.10从双鍊表中删除一个结点

图4.1直接插入排序过程

图4.2折半查找过程

图4.3Shell排序过程

图4.4直接选择排序

图4.5第一次树形选择排序选出最小排序码13

图4.6第二次树形选择排序选出最小排序码14

图4.7起泡排序过程

图4.8一趟快速排序的比较过程

图4.9基数排序的分配和收集过程

图4.10二路归併过程

图4.112路归併排序示意

图4.12实现5路合併败者树

图4.13实现5路合併一次替代选择后的败者树

图4.14顺序合併的3路合併树

图4.153路最佳合併树

图4.16三个排序码排序过程对应的判定树

图5.1折半查找过程

图5.2分块查找过程

图5.3第一趟比较

图5.4第二趟比较

图5.5朴素的模式匹配算法执行过程

图5.6模式P="abcabcd"的next数组的计算过程

图5.7基于KMP匹配算法的模式匹配过程

图5.8用分离的同义词子表解决冲突

图5.9用结合的同义词子表解决冲突

图5.10几种不同的解决碰撞方法时的平均检索长度（横坐标为负载因子的取值）

图6.1家族树

图6.2二叉树的五种基本形态

图6.3表达式二叉树

图6.4深度为3的满二叉树

图6.5特殊的二叉树

图6.6i与i+1在同一层的完全二叉树

图6.7i与i+1不在同一层的完全二叉树

图6.8完全二叉树的顺序存储

图6.9非完全二叉树的顺序存储

图6.10二叉树的LeftChild-RightChild表示

图6.11树(树林)与二叉树之间相互转换

图6.12树林的例

图6.13图6.12对应的二叉树

图6.14二叉树遍历实例

图6.15对称序线索树

图6.16在对称序线索化二叉树中插入新结点

图7.1二叉排序树

图7.2构造二叉排序树

图7.3二叉排序树中删除一个结点

图7.4删除结点11后的另一种形式

图7.5两种不同的二叉排序树

图7.6两棵扩充二叉树

图7.7最佳二叉排序树的构造

图7.8二叉树与结点的平衡因子

图7.9平衡的二叉排序的生成过程(带★的点为插入后引起不平衡的点)

图7.10二叉排序树的平衡旋转

图7.11AVL二叉排序树结点的删除(结点中右边数字代表平衡因子)

图7.12一棵7阶的B-树

图7.13图7.12中B-树的插入（插入3后）

图7.14图7.13中B-树的插入（插入25后）

图7.15图7.14中删除元素80

图7.16图7.14中删除元素4

图7.17在图7.16中删除元素60

图7.18在图7.17中删除元素70

图7.19一棵3阶的B+-树

图7.20两棵不同形式的2-3树

图7.212-3树的插入

图7.22图7.20(b)中插入8后2-3树的变化图

图7.232-3树的删除

图7.24一棵阶为2的红黑树

图7.25红黑树的生长过程

图7.26一棵2阶红黑树

图7.27红黑树中删除元素88

图7.28图7.27调整后的红黑树

图7.29图7.27中删除元素71

图7.30图7.29调整后的红黑树

图7.31图7.30中删除元素63

图7.32调整图7.31后的红黑树

图7.33一棵扩充的二叉树

图7.34哈夫曼最优树的构造过程

图7.35Huffman编码树

图7.36树T

图7.37树T0

图7.38树T1

图7.39Huffman 编码树

图7.40堆对应的完全二叉树

图7.41堆中插入新结点

图7.42堆中根结点的删除

图7.43筛法建堆过程

图7.44堆排序过程

图7.45三个元素排序的判定树

图7.46鉴别伪币的判定树

图7.47用父指针表示的树型结构存储的并查集

图7.48并查集的查找、合併过程

图7.49Union加权规则示意图

图7.50路径压缩的例子

图7.51键树示例

图7.52由图7.51压缩后的键树

图7.53键树中插入记录

图8.1无向图和有向图

图8.2图G4=(V,E)

图8.3图G3的强连通分量

图8.4G1的生成树

图8.5G3的生成树林

图8.6图G5(网路)

图8.7图的邻接表表示

图8.8G5的邻接表表示

图8.9图8.7(a)的邻接多重表表示

图8.10图8.7(c)的多重鍊表表示

图8.11图8.7(c)的十字鍊表表示

图8.12有向图深度优先搜寻过程

图8.13无向图深度方向优先遍历

图8.14广度优先生成树(树林)

图8.15T的变化图

图8.16Prim算法构造最小生成树的过程(g,g′为两棵最小生成树)

图8.17Kruskal构造最小生成树的过程

图8.18有向图G

图8.19按最短路径长度递增的次序找最短路径

图8.20含三个顶点的有向网路

图8.21表达式树

图8.22共享结点后的表达式树

图8.23表示各课程优先关係的AOV网

图8.24一个AOE网的例

图8.25图8.24的关键路径为(a1,a4,a8,a11)或(a1,a4,a7,a10)

图9.1稀疏矩阵的三元组表示

图9.2带辅助行向量的二元组表示

图9.3稀疏矩阵的行鍊表表示

图9.4稀疏矩阵的正交表表示