第1章 数据结构基础 1
1.1数据结构的基本概念 2
1.1.1数据结构的研究内容 2
1.1.2基本概念和术语 5
1.1.3数据结构课程的内容 8
1.2数据类型和抽象数据类型 9
1.2.1数据类型 9
1.2.2抽象数据类型 9
1.3算法和算法分析 10
1.3.1算法特性 11
1.3.2算法描述 12
1.3.3算法性能分析 12
1.4本章小结 15
习题 16
编程实例 18
第2章 线性表 19
2.1线性表的定义 20
2.1.1线性表的逻辑结构 20
2.1.2线性表的抽象数据类型 20
2.2线性表的顺序存储及实现 22
2.2.1顺序表 22
2.2.2顺序表的基本运算 23
2.3线性表的链式存储及实现 28
2.3.1单链表 29
2.3.2单链表的基本运算 30
2.3.3循环链表 36
2.3.4双向链表 37
2.3.5静态链表 39
2.3.6单链表应用举例 40
2.4顺序表与链表的比较 43
2.5本章小结 44
习题 44
编程实例 46
第3章 栈和队列 48
3.1栈 49
3.1.1栈的定义 49
3.1.2栈的表示和实现 50
3.2栈的应用 55
3.2.1数制转换问题 56
3.2.2括号匹配检验 57
3.2.3表达式求值 58
3.2.4栈与递归 61
3.3队列 64
3.3.1队列的定义 64
3.3.2队列的表示和实现 65
3.4队列的应用 71
3.5本章小结 73
习题 74
编程实例 75
第4章 串 79
4.1串的定义和基本运算 80
4.1.1串的定义 80
4.1.2串的基本操作 81
4.2串的存储结构 82
4.2.1定长顺序存储 82
4.2.2堆存储 83
4.2.3链式存储 85
4.3串的运算实现 86
4.4串的模式匹配 90
4.4.1 BF算法 90
4.4.2 KMP算法 92
4.5本章小结 95
习题 96
编程实例 99
第5章 数组和广义表 103
5.1数组的定义及存储 104
5.1.1数组的定义 104
5.1.2数组的基本操作 105
5.1.3数组的顺序存储 105
5.2特殊矩阵的压缩存储 107
5.2.1对称矩阵 108
5.2.2三角矩阵 109
5.2.3对角矩阵 110
5.3稀疏矩阵 111
5.3.1稀疏矩阵的三元组表存储 111
5.3.2稀疏矩阵的十字链表存储 115
5.4广义表 117
5.4.1广义表的定义 117
5.4.2广义表的存储结构 119
5.4.3广义表的基本操作实现 121
5.5本章小结 122
习题 123
编程实例 124
第6章 树和二叉树 127
6.1树的定义与基本术语 128
6.1.1树的定义 128
6.1.2树的基本术语 131
6.2二叉树 131
6.2.1二叉树的定义 131
6.2.2二叉树的性质 134
6.2.3二叉树的存储实现 136
6.3遍历二叉树 139
6.3.1遍历二叉树的递归实现 139
6.3.2遍历二叉树的非递归实现 141
6.3.3遍历算法的应用 145
6.4线索二叉树 148
6.4.1线索二叉树的基本概念 148
6.4.2线索二叉树的运算实现 150
6.5树和森林 153
6.5.1树的存储结构 153
6.5.2树、森林与二叉树的转换 156
6.5.3树和森林的遍历 158
6.6哈夫曼树及其应用 159
6.6.1哈夫曼树的基本概念 159
6.6.2构造哈夫曼树 161
6.6.3哈夫曼编码 163
6.7本章小结 165
习题 166
编程实例 168
第7章 图 172
7.1图的定义与基本术语 173
7.1.1图的定义 173
7.1.2基本术语 175
7.2图的存储结构 177
7.2.1邻接矩阵 177
7.2.2邻接链表 179
7.2.3十字链表 182
7.2.4邻接多重表 183
7.3图的遍历 184
7.3.1深度优先搜索 185
7.3.2广度优先搜索 187
7.4图的应用 189
7.4.1最小生成树 189
7.4.2最短路径问题 195
7.4.3 AOV网与拓扑排序 200
7.4.4 AOE网与关键路径 203
7.5本章小结 208
习题 209
编程实例 211
第8章 查找 216
8.1查找的基本概念 217
8.2线性表的查找 218
8.2.1顺序查找 218
8.2.2折半查找 219
8.2.3分块查找 222
8.3树表的查找 223
8.3.1二叉排序树 223
8.3.2平衡二叉树 229
8.3.3 B树 234
8.4散列表的查找 241
8.4.1散列表的基本概念 241
8.4.2散列函数的构造方法 242
8.4.3处理冲突的方法 244
8.4.4散列表的查找 247
8.5本章小结 248
习题 249
编程实例 251
第9章 排序 254
9.1排序的基本概念 255
9.1.1什么是排序 255
9.1.2排序的实现 256
9.2插入排序 257
9.2.1直接插入排序 257
9.2.2折半插入排序 259
9.2.3希尔排序 260
9.3交换排序 261
9.3.1冒泡排序 261
9.3.2快速排序 263
9.4选择排序 266
9.4.1简单选择排序 266
9.4.2堆排序 268
9.5归并排序 273
9.6基数排序 275
9.6.1多关键字排序 275
9.6.2链式基数排序 275
9.7本章小结 279
习题 280
编程实例 282