第1章 绪论 1
1.1数据结构的概念和学习数据结构的必要性 1
1.2数据结构的基本概念 2
1.2.1数据 2
1.2.2数据元素和数据项 2
1.2.3数据结构 2
1.3抽象数据类型及其实现 4
1.3.1数据类型 4
1.3.2抽象数据类型（Abstract Data Type——ADT） 4
1.3.3 C++的类和对象 4
1.3.4运算符重载 6
1.3.5有关C++的动态存储分配 9
1.3.6 C++的模板（template） 10
1.4算法和算法分析 11
1.4.1算法 11
1.4.2算法分析 12
1.5实用程序软件包 15
1.6深入学习导读 19
1.7习题1 19
第2章 线性表 21
2.1线性表的逻辑结构 21
2.2线性表的顺序存储结构 23
2.3线性表的链式存储结构 31
2.3.1单链表 31
2.3.2循环链表 39
2.3.3双向链表 43
2.3.4在链表结构中保存当前位置和元素个数 46
2.4实例研究：一元多项式的表示 55
2.5深入学习导读 60
2.6习题2 60
第3章 栈和队列 61
3.1栈 61
3.1.1栈的基本概念 61
3.1.2顺序栈 62
3.1.3链式栈 67
3.2队列 74
3.2.1队列的基本概念 74
3.2.2链队列 75
3.2.3循环队列——队列的顺序存储结构 79
3.2.4队列应用——显示二项式（a+b）i的系数 84
3.3实例研究：表达式求值 85
3.4深入学习导读 88
3.5习题3 89
第4章串 90
4.1串类型的定义 90
4.2字符串的实现 91
4.3字符串模式匹配算法 98
4.3.1简单字符串模式匹配算法 98
4.3.2 KMP字符串模式匹配算法 99
4.4实例研究：文本编辑 104
4.5深入学习导读 114
4.6习题4 114
第5章 数组和广义表 115
5.1数组 115
5.1.1数组的基本概念 115
5.1.2数组的顺序表 116
5.1.3数组的类定义 118
5.2矩阵 122
5.2.1矩阵的定义和操作 122
5.2.2特殊矩阵 123
5.2.3稀疏矩阵 128
5.3广义表 139
5.3.1基本概念 139
5.3.2广义表的存储结构 141
5.4深入学习导读 151
5.5习题5 152
第6章 树和二叉树 153
6.1树的基本概念 153
6.1.1树的定义 153
6.1.2基本术语 154
6.2二叉树 155
6.2.1二叉树的定义 155
6.2.2二叉树的性质 157
6.2.3二叉树的存储结构 160
6.3二叉树遍历 168
6.3.1遍历的定义 168
6.3.2遍历算法 169
6.3.3二叉树遍历应用举例 175
6.4线索二叉树 180
6.4.1线索的概念 180
6.4.2线索二叉树的实现 182
6.5树和森林 190
6.5.1树的存储表示 190
6.5.2树的显示 198
6.5.3森林的存储表示 198
6.5.4树和森林的遍历 203
6.5.5树和森林与二叉树的转换 206
6.6哈夫曼树与哈夫曼编码 208
6.6.1哈夫曼树的基本概念 209
6.6.2哈夫曼树构造算法 210
6.6.3哈夫曼编码 210
6.6.4哈夫曼树的实现 212
6.7树的计数 216
6.8实例研究：树与等价关系 218
6.9深入学习导读 222
6.10习题6 222
第7章 图 224
7.1图的定义和术语 224
7.2图的存储表示 228
7.2.1邻接矩阵 228
7.2.2邻接表 234
7.3图的遍历 242
7.3.1深度优先搜索 242
7.3.2广度优先搜索 244
7.4连通无向网的最小代价生成树 246
7.4.1 Prim算法 246
7.4.2 Kruskal算法 249
7.5有向无环图及应用 252
7.5.1拓扑排序 253
7.5.2关键路径 256
7.6最短路径 260
7.6.1单源点最短路径问题 260
7.6.2所有顶点之间的最短路径 263
7.7深入学习导读 265
7.8习题7 265
第8章 查找 267
8.1查找的基本概念 267
8.2静态表的查找 270
8.2.1顺序查找 270
8.2.2有序表的查找 271
8.3动态查找表 274
8.3.1二叉排序树 274
8.3.2二叉平衡树 285
8.3.3 B-树和B+-树 310
8.4散列表 312
8.4.1散列表的概念 312
8.4.2构造散列函数的方法 313
8.4.3处理冲突的方法 313
8.4.4散列表的实现 315
8.5深入学习导读 320
8.6习题8 320
第9章 排序 321
9.1概述 321
9.2插入排序 322
9.2.1直接插入排序 322
9.2.2 Shell排序 324
9.3交换排序 325
9.3.1起泡排序 325
9.3.2快速排序 326
9.4选择排序 329
9.4.1简单选择排序 330
9.4.2堆排序 331
9.5归并排序 334
9.6基数排序 338
9.6.1多关键排序 338
9.6.2基数排序 339
9.7各种内部排序方法讨论 341
9.8外部排序 342
9.8.1外部排序基础 342
9.8.2外部排序的方法 343
9.9实例研究：各种排序算法运行时间测试 344
9.10深入学习导读 347
9.11习题9 347
第10章 文件 349
10.1主存储器和辅助存储器 349
10.2各种常用文件结构 349
10.2.1顺序文件 349
10.2.2索引文件 350
10.2.3散列文件 351
10.2.4 VSAM文件 351
10.2.5多关键字文件 352
10.3深入学习导读 354
10.4习题10 354
第11章 算法设计与分析 355
11.1算法设计 355
11.1.1递归算法 355
11.1.2分治算法 357
11.1.3回溯算法 358
11.2算法分析 361
11.2.1递归分析 361
11.2.2利用生成函数进行分析 362
11.3深入学习导读 363
11.4习题11 364
附录A调和级数 365
附录B课本的软件包 366
附录C实验题目 371
附录D课程设计项目 372
D1算术表达式求值 372
D2简单本文编辑器 372
D3压缩软件 373
D4公园导游系统 373
D5专家系统应用——动物游戏 373
D6词典变位词检索系统 374
附录E实验报告格式 375
附录F课程设计报告格式 376
参考文献 377