第 1章　绪论
1.1　什么是数据结构　1
1.2　基本术语　2
1.3　算法和算法分析　4
1.3.1 算法的定义及特性　4
1.3.2 算法的设计要求　5
1.3.3 算法分析　5
本章小结　8
习题　8
第 2章　线性表
2.1　线性表的定义及其基本运算　9
2.1.1 线性表的定义　9
2.1.2 线性表的基本运算　10
2.2　顺序表　10
2.2.1 顺序存储　10
2.2.2 顺序表的定义及其基本运算　11
2.2.3 顺序表的运算实例　15
2.3　单链表　17
2.3.1 单链表的定义及其基本运算　17
2.3.2 单链表的运算实例　22
2.3.3 静态链表　24
2.3.4 循环链表　26
2.4　双向链表　29
2.4.1 双向链表的定义　29
2.4.2 双向链表的基本运算　30
2.4.3 双向循环链表　31
2.5 顺序表和链表的比较　31
2.6　链表的应用　32
本章小结　35
习题　36
第3章　栈和队列
3.1　栈的基本概念及其基本运算　37
3.1.1 栈的基本概念　37
3.1.2 栈的基本运算　37
3.2　栈的顺序存储结构　38
3.2.1 顺序栈的表示和实现　38
3.2.2 两个栈共享存储空间　40
3.3　栈的链式存储结构　41
3.4　栈的应用　42
3.4.1 数制转换　42
3.4.2 括号匹配检测　42
3.4.3 递归　43
3.4.4 算术表达式求值　45
3.4.5 栈的运算实例　46
3.5　队列　48
3.5.1 队列的定义　48
3.5.2 队列的基本运算　48
3.5.3 队列的链式存储结构　48
3.5.4 队列的顺序存储结构　50
3.5.5 队列的运算实例　53
本章小结　55
习题　55
第4章 数组
4.1　数组的基本概念、基本运算和顺序存储　56
4.1.1 数组的基本概念　56
4.1.2 数组的基本运算　57
4.1.3 数组的顺序存储　57
4.2　矩阵的压缩存储　60
4.2.1 特殊矩阵的压缩存储　60
4.2.2 稀疏矩阵的压缩存储　61
本章小结　66
习题　66
第5章 串
5.1　串的基本概念及其基本运算　68
5.1.1 串的基本概念　68
5.1.2 串的基本运算　69
5.2　串的存储结构　70
5.2.1 定长顺序存储结构　70
5.2.2 堆分配存储结构　72
5.2.3 块链存储结构　74
5.3　串的模式匹配算法　76
5.4　串的KMP算法　78
5.5　串的应用　80
本章小结　81
习题　82
第6章 树
6.1　树的定义、基本概念及其基本运算　85
6.1.1 树的定义　85
6.1.2 结点之间的关系　86
6.1.3 树的其他概念　86
6.1.4 树的基本运算　87
6.2　树的存储表示法　88
6.3　二叉树　90
6.3.1 二叉树的定义　90
6.3.2 二叉树的形态　90
6.3.3 二叉树的基本运算　91
6.3.4 二叉树的性质　91
6.3.5 二叉树的存储结构　92
6.4　二叉树的遍历、确定和常用操作　94
6.4.1 二叉树的遍历　94
6.4.2 二叉树的确定　96
6.4.3 二叉树的常用操作　97
6.5　线索二叉树　101
6.5.1 线索二叉树的基本概念　101
6.5.2 线索二叉树的常用操作　103
6.6　树和森林　106
6.6.1 树与二叉树的相互转换　106
6.6.2 森林与二叉树的相互转换　108
6.6.3 树与森林的遍历　109
6.7　哈夫曼树及其应用　109
6.7.1 哈夫曼树的定义和基本概念　109
6.7.2 哈夫曼编码　111
6.8　二叉树的应用——表达式求值　113
本章小结　114
习题　115
第7章 图
7.1　图的基本概念　119
7.1.1 图、有向图、无向图　119
7.1.2 图的基本运算　120
7.1.3 图的基本术语　120
7.2　图的存储结构　123
7.2.1 邻接矩阵　124
7.2.2 邻接表　126
7.3　图的遍历　128
7.3.1 深度优先搜索　129
7.3.2 广度优先搜索　130
7.4　生成树和最小生成树　131
7.4.1 生成树和最小生成树的概念　131
7.4.2 Kruskal算法　133
7.4.3 Prim算法　134
7.5　AOV网和拓扑排序　134
7.5.1 AOV网和拓扑排序的概念　135
7.5.2 拓扑排序算法　136
7.6　AOE网和关键路径　138
7.6.1 AOE网和关键路径的概念　139
7.6.2 关键路径的确定　140
7.7　最短路径　142
7.7.1 最短路径的概念　142
7.7.2 Dijkstra算法　143
7.7.3 Floyd算法　144
本章小结　145
习题　145
第8章 排序
8.1　排序的基本概念　148
8.2　插入排序　149
8.3　交换排序　151
8.3.1 冒泡排序　151
8.3.2 快速排序　152
8.4　选择排序　154
8.4.1 简单选择排序　155
8.4.2 堆排序　156
8.5　归并排序　161
8.6　基数排序　162
8.7　内部排序算法的比较　165
8.8　外部排序　166
8.8.1 外部排序算法　166
8.8.2 置换选择排序　167
8.8.3 最佳归并树　169
本章小结　170
习题　170
第9章 查找
9.1　查找的基本概念　172
9.2　静态查找　173
9.2.1 顺序查找　173
9.2.2 有序表查找　174
9.2.3 分块查找　176
9.3　动态查找　177
9.3.1 二叉排序树　177
9.3.2 平衡二叉树　183
9.4　散列表查找　188
9.4.1 散列表查找的基本概念　188
9.4.2 构造散列函数的方法　189
9.4.3 散列冲突的解决方法—开放定址法　190
9.4.4 散列表的查找分析　192
本章小结　193
习题　194