数据结构：从概念到C++实现（第3版 ）

目录第1章绪论1

1.1问题求解与程序设计2

1.1.1程序设计的一般过程2

1.1.2数据结构在程序设计中的作用5

1.1.3算法在程序设计中的作用6

1.1.4本书讨论的主要内容7

1.2数据结构的基本概念9

1.2.1数据结构9

1.2.2抽象数据类型11

1.3算法的基本概念13

1.3.1算法及算法的特性13

1.3.2算法的描述方法14

1.4算法分析16

1.4.1算法的时间复杂度16

1.4.2算法的空间复杂度18

1.4.3算法分析举例18

1.5扩展与提高21

1.5.1从数据到大数据21

1.5.2算法分析的其他渐进符号22

思想火花——概率算法23

习题124

第2章线性表27

2.1引言28

2.2线性表的逻辑结构29

2.2.1线性表的定义29数据结构——从概念到C++实现（第3版）目录2.2.2线性表的抽象数据类型定义30

2.3线性表的顺序存储结构及实现31

2.3.1顺序表的存储结构31

2.3.2顺序表的实现32

2.3.3顺序表的使用37

2.4线性表的链接存储结构及实现38

2.4.1单链表的存储结构38

2.4.2单链表的实现40

2.4.3单链表的使用48

2.4.4双链表49

2.4.5循环链表50

2.5顺序表和链表的比较51

2.6扩展与提高52

2.6.1线性表的静态链表存储52

2.6.2顺序表的动态分配方式54

2.7应用实例56

2.7.1约瑟夫环问题56

2.7.2一元多项式求和59

思想火花——好算法是反复努力和重新修正的结果63

习题264

实验题267

第3章栈和队列69

3.1引言70

3.2栈71

3.2.1栈的逻辑结构71

3.2.2栈的顺序存储结构及实现72

3.2.3栈的链接存储结构及实现75

3.2.4顺序栈和链栈的比较77

3.3队列78

3.3.1队列的逻辑结构78

3.3.2队列的顺序存储结构及实现79

3.3.3队列的链接存储结构及实现83

3.3.4循环队列和链队列的比较86

3.4扩展与提高86

3.4.1两栈共享空间86

3.4.2双端队列88

3.5应用举例89

3.5.1括号匹配问题89

3.5.2表达式求值91

思想火花——好程序要能识别和处理各种输入94

习题395

实验题397

第4章字符串和多维数组99

4.1引言100

4.2字符串101

4.2.1字符串的逻辑结构101

4.2.2字符串的存储结构103

4.2.3模式匹配103

4.3多维数组107

4.3.1数组的逻辑结构107

4.3.2数组的存储结构与寻址108

4.4矩阵的压缩存储109

4.4.1特殊矩阵的压缩存储109

4.4.2稀疏矩阵的压缩存储112

4.5扩展与提高114

4.5.1稀疏矩阵的转置运算114

4.5.2广义表116

4.6应用实例119

4.6.1发纸牌119

4.6.2八皇后问题121

思想火花——用常识性的思维去思考问题124

习题4124

实验题4126

第5章树和二叉树127

5.1引言128

5.2树的逻辑结构129

5.2.1树的定义和基本术语129

5.2.2树的抽象数据类型定义131

5.2.3树的遍历操作131

5.3树的存储结构132

5.3.1双亲表示法132

5.3.2孩子表示法132

5.3.3孩子兄弟表示法133

5.4二叉树的逻辑结构134

5.4.1二叉树的定义134

5.4.2二叉树的基本性质136

5.4.3二叉树的抽象数据类型定义138

5.4.4二叉树的遍历操作139

5.5二叉树的存储结构140

5.5.1顺序存储结构140

5.5.2二叉链表141

5.5.3三叉链表146

5.6森林147

5.6.1森林的逻辑结构147

5.6.2树、森林与二叉树的转换147

5.7最优二叉树149

5.7.1哈夫曼算法149

5.7.2哈夫曼编码152

5.8扩展与提高153

5.8.1二叉树遍历的非递归算法153

5.8.2线索链表157

5.9应用实例161

5.9.1堆与优先队列161

5.9.2并查集164

思想火花——调试程序与魔术表演166

习题5167

实验题5169

第6章图171

6.1引言172

6.2图的逻辑结构173

6.2.1图的定义和基本术语173

6.2.2图的抽象数据类型定义176

6.2.3图的遍历操作176

6.3图的存储结构及实现179

6.3.1邻接矩阵179

6.3.2邻接表182

6.3.3邻接矩阵和邻接表的比较187

6.4最小生成树188

6.4.1Prim算法189

6.4.2Kruskal算法191

6.5最短路径195

6.5.1Dijkstra算法196

6.5.2Floyd算法199

6.6有向无环图及其应用200

6.6.1AOV网与拓扑排序201

6.6.2AOE网与关键路径203

6.7扩展与提高206

6.7.1图的其他存储方法206

6.7.2图的连通性208

6.8应用实例209

6.8.1七巧板涂色问题209

6.8.2医院选址问题211

思想火花——直觉可能是错误的214

习题6214

实验题6218

第7章查找技术219

7.1概述220

7.1.1查找的基本概念220

7.1.2查找算法的性能221

7.2线性表的查找技术221

7.2.1线性表查找结构的类定义221

7.2.2顺序查找222

7.2.3折半查找223

7.3树表的查找技术226

7.3.1二叉排序树226

7.3.2平衡二叉树231

7.3.3B树235

7.4散列表的查找技术239

7.4.1散列查找的基本思想239

7.4.2散列函数的设计241

7.4.3处理冲突的方法242

7.4.4散列查找的性能分析246

7.4.5开散列表与闭散列表的比较247

7.5各种查找方法的比较247

7.6扩展与提高248

7.6.1顺序查找的改进——分块查找248

7.6.2折半查找的改进——插值查找249

7.6.3B树的改进——B+树250

思想火花——把注意力集中于主要因素，不要纠缠于噪声251

习题7251

实验题7254

第8章排序技术255

8.1概述256

8.1.1排序的基本概念256

8.1.2排序算法的性能257

8.1.3排序类的定义257

8.2插入排序258

8.2.1直接插入排序258

8.2.2希尔排序260

8.3交换排序262

8.3.1起泡排序262

8.3.2快速排序264

8.4选择排序267

8.4.1简单选择排序267

8.4.2堆排序269

8.5归并排序274

8.5.1二路归并排序的递归实现274

8.5.2二路归并排序的非递归实现275

8.6各种排序方法的比较277

8.6.1各种排序技术的使用范例277

8.6.2各种排序方法的综合比较278

8.7扩展与提高280

8.7.1排序问题的时间下界280

8.7.2基数排序281

思想火花——学会“盒子以外的思考”283

习题8284

实验题8286

附录A预备知识289

附录BC++语言基本语法293

附录C词汇索引307

参考文献311