第1章 绪论 1
1.1数据结构的发展简史 1
1.2基本概念和术语 3
1.2.1数据 3
1.2.2数据的逻辑结构 3
1.2.3数据的存储结构 3
1.2.4数据结构 4
1.2.5数据类型 5
1.2.6抽象数据类型与类 5
1.3算法 6
1.3.1算法的时间复杂度 7
1.3.2算法的空间复杂度 9
本章小结 9
习题 10
第2章C++类 13
2.1类的定义 13
2.2模板类 17
2.3基类和派生类 17
2.4对象的定义 19
2.5构造函数、析构函数和拷贝初始化构造函数 21
2.6运算符的重载 22
2.6.1运算符重载为类的函数成员 22
2.6.2运算符重载为非函数成员 23
本章小结 24
习题 24
第3章 线性表 25
3.1线性表的抽象数据类型 25
3.1.1线性表的逻辑结构 25
3.1.2线性表的操作 25
3.1.3线性表的存储结构 25
3.2顺序表 26
3.2.1顺序表的存储结构 26
3.2.2顺序表的操作 27
3.2.3顺序表类C++语言定义 30
3.2.4顺序表的应用——并交差运算 38
3.3非循环单链表 41
3.3.1非循环单链表的存储结构 41
3.3.2非循环单链表的操作 42
3.3.3非循环单链表类C++语言定义 46
3.3.4非循环单链表的应用——多项式的加减运算 58
3.4循环单链表 69
3.4.1循环单链表的存储结构 69
3.4.2循环单链表的操作 70
3.4.3循环单链表类C++语言定义 71
3.4.4循环单链表的应用——约瑟夫环出列 77
3.5循环双链表 78
3.5.1循环双链表的存储结构 79
3.5.2循环双链表的操作 79
3.5.3循环双链表类C++语言定义 82
3.6线性表顺序存储和链式存储结构比较 92
本章小结 93
习题 93
第4章栈 95
4.1栈的抽象数据类型 95
4.1.1栈的逻辑结构 95
4.1.2栈的操作 95
4.1.3栈的存储结构 95
4.2顺序栈 96
4.2.1顺序栈的存储结构 96
4.2.2顺序栈的操作 96
4.2.3顺序栈类C++语言定义 98
4.2.4顺序栈的应用——表达式求解 103
4.3链栈 112
4.3.1链栈的存储结构 112
4.3.2链栈的操作 112
4.3.3链栈类C++语言定义 114
本章小结 120
习题 120
第5章 队列 121
5.1队列的抽象数据类型 121
5.1.1队列的逻辑结构 121
5.1.2队列的操作 121
5.1.3队列的存储结构 121
5.2循环顺序队列 122
5.2.1循环顺序队列的存储结构 122
5.2.2循环顺序队列的操作 122
5.2.3循环顺序队列类C++语言定义 125
5.2.4循环顺序队列的应用 130
5.3非循环链队 140
5.3.1非循环链队的存储结构 140
5.3.2非循环链队的操作 140
5.3.3非循环链队类C++语言定义 142
本章小结 148
习题 148
第6章串 150
6.1串的抽象数据类型 150
6.1.1串的逻辑结构 150
6.1.2串的操作 151
6.1.3串的存储结构 151
6.2顺序串 151
6.2.1顺序串的存储结构 151
6.2.2顺序串的操作 151
6.2.3顺序串类C++语言定义 156
6.3链串 169
本章小结 169
习题 170
第7章 多维数组 171
7.1数组 171
7.2特殊矩阵 172
7.2.1对称矩阵 173
7.2.2三角矩阵 174
7.2.3对角矩阵 175
7.3稀疏矩阵（采用三元组表顺序存储） 176
7.3.1稀疏矩阵的存储结构 176
7.3.2稀疏矩阵的操作 177
7.3.3稀疏矩阵类C++语言定义 181
7.4稀疏矩阵（采用十字链表存储） 196
7.4.1稀疏矩阵的存储结构 196
7.4.2稀疏矩阵的操作 197
7.4.3稀疏矩阵类C++语言定义 198
本章小结 209
习题 210
第8章 广义表 211
8.1广义表的逻辑结构 211
8.2广义表的存储结构 212
8.3广义表的操作 213
8.4广义表类C++语言定义 216
本章小结 228
习题 229
第9章树 230
9.1树的抽象数据类型 230
9.1.1树的逻辑结构 232
9.1.2树的操作 232
9.1.3树的存储结构 232
9.2二叉树 232
9.2.1二叉树的逻辑结构 232
9.2.2二叉树的重要性质 233
9.2.3二叉树的存储结构 234
9.3二叉树（采用顺序存储） 234
9.3.1二叉树的存储结构 234
9.3.2二叉树的操作 236
9.3.3二叉树类C++语言定义 236
9.4二叉树（采用链式存储） 240
9.4.1二叉树的存储结构 240
9.4.2二叉树的操作 241
9.4.3二叉树类C++语言定义 247
9.5中序穿线二叉树 262
9.5.1中序穿线二叉树的存储结构 262
9.5.2中序穿线二叉树的操作 263
9.5.3中序穿线二叉树类C++语言定义 265
9.6树/森林 279
9.6.1树的存储结构 279
9.6.2树/森林与二叉树之间的转换 282
9.6.3树/森林与对应二叉树的遍历关系 283
9.7哈夫曼树——二叉树的应用 284
9.7.1哈夫曼树的概念 284
9.7.2哈夫曼树的存储结构 285
9.7.3哈夫曼树的操作 286
9.7.4哈夫曼树类C++语言定义 288
本章小结 299
习题 300
第10章图 302
10.1图的基本概念 302
10.1.1无向图 302
10.1.2有向图 305
10.2图的操作 307
10.2.1最小生成树 307
10.2.2最短路径 309
10.2.3图的遍历 311
10.2.4拓扑序列 312
10.2.5关键路径 313
10.3图的存储结构 316
10.4图（采用邻接矩阵存储） 316
10.4.1图的存储结构 316
10.4.2图的基本操作 317
10.4.3图类C++语言定义 322
10.5图（采用邻接表存储） 332
10.5.1图的存储结构 332
10.5.2图的基本操作 334
10.5.3图类C++语言定义 337
本章小结 349
习题 351
第11章 排序 354
11.1排序的基本概念 354
11.2插入排序 355
11.2.1直接插入排序 355
11.2.2折半插入排序 356
11.2.3静态链表插入排序 357
11.2.4希尔排序 359
11.3交换排序 360
11.3.1冒泡排序 360
11.3.2快速排序 362
11.4选择排序 364
11.4.1直接选择排序 364
11.4.2堆排序 365
11.5归并排序 368
11.6分配排序 369
11.6.1箱排序 369
11.6.2基数排序 370
11.7各种排序方法的比较 372
11.8各种排序方法C++语言实现 373
本章小结 387
习题 387
第12章 查找 389
12.1静态查找表 389
12.1.1顺序查找 389
12.1.2折半查找 390
12.1.3索引顺序查找 392
12.1.4静态查找表类C++语言定义 393
12.2动态查找表 398
12.2.1二叉排序树 398
12.2.2平衡二叉排序树 409
12.2.3 B-树 427
12.2.4哈希表 440
本章小结 451
习题 452
参考文献 454