目录

第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稀疏矩阵的正交表表示