目录

第1章绪论1

1.1引言2

1.2问题求解与程序设计3

1.2.1程序设计的一般过程3

1.2.2数据结构在程序设计中的作用6

1.2.3算法在程序设计中的作用7

1.2.4本书讨论的主要内容8

1.3数据结构的基本概念10

1.3.1数据结构10

1.3.2抽象数据类型12

1.4算法的基本概念14

1.4.1算法及算法的特性14

1.4.2算法的描述方法15

1.5算法分析16

1.5.1算法的时间复杂度16

1.5.2算法的空间复杂度17

1.5.3算法分析实例18

1.6扩展与提高20

1.6.1概率算法20

1.6.2算法分析的其他渐进符号21

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

习题122

考研真题125第2章线性表27

2.1引言28

2.2线性表的逻辑结构29

2.2.1线性表的定义29

2.2.2线性表的抽象数据类型定义29

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

2.3.1顺序表的存储结构31

2.3.2顺序表的实现31

2.4线性表的链式存储结构及实现36

2.4.1单链表的存储结构36

2.4.2单链表的实现38

2.4.3双链表46

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

目录

2.4.4循环链表47

2.5扩展与提高48

2.5.1线性表的静态链表存储48

2.5.2顺序表的动态分配方式50

2.5.3顺序表和链表的比较52

2.6上机实验53

2.6.1顺序表的上机实现53

2.6.2单链表的上机实现53

2.6.3提纯线性表54

2.6.4约瑟夫环问题55

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

习题257

考研真题261第3章栈、队列和数组63

3.1引言64

3.2栈65

3.2.1栈的逻辑结构65

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

3.2.3栈的链式存储结构及实现68

3.2.4顺序栈和链栈的比较70

3.2.5栈的应用70

3.3队列72

3.3.1队列的逻辑结构72

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

3.3.3队列的链式存储结构及实现76

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

3.3.5队列的应用79

3.4多维数组79

3.4.1数组的逻辑结构79

3.4.2数组的存储结构与寻址80

3.5矩阵的压缩存储81

3.5.1特殊矩阵的压缩存储82

3.5.2稀疏矩阵的压缩存储84

3.6扩展与提高86

3.6.1两栈共享空间86

3.6.2双端队列87

3.6.3广义表88

3.7上机实验92

3.7.1顺序栈的上机实现92

3.7.2链队列的上机实现92

3.7.3括号匹配问题93

3.7.4机器翻译94

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

习题396

考研真题399第4章树和二叉树102

4.1引言103

4.2树的逻辑结构104

4.2.1树的定义和基本术语104

4.2.2树的抽象数据类型定义105

4.2.3树的遍历操作106

4.3树的存储结构107

4.3.1双亲表示法107

4.3.2孩子表示法107

4.3.3孩子兄弟表示法108

4.4二叉树的逻辑结构109

4.4.1二叉树的定义109

4.4.2二叉树的基本性质110

4.4.3二叉树的抽象数据类型定义112

4.4.4二叉树的遍历操作113

4.4.5二叉树的构造114

4.5二叉树的存储结构115

4.5.1顺序存储结构116

4.5.2二叉链表116

4.5.3三叉链表121

4.6森林122

4.6.1森林的逻辑结构122

4.6.2树、森林与二叉树的转换122

4.7最优二叉树124

4.7.1哈夫曼算法124

4.7.2哈夫曼编码127

4.8扩展与提高128

4.8.1二叉树遍历的非递归算法128

4.8.2线索链表131

4.8.3堆与优先队列135

4.8.4并查集138

4.9上机实验140

4.9.1二叉链表的上机实现140

4.9.2孩子兄弟链表的上机实现140

4.9.3最近共同祖先141

4.9.4镜像对称二叉树142

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

习题4145

考研真题4148第5章图151

5.1引言152

5.2图的逻辑结构153

5.2.1图的定义和基本术语153

5.2.2图的抽象数据类型定义155

5.2.3图的遍历操作156

5.3图的存储结构及实现158

5.3.1邻接矩阵158

5.3.2邻接表161

5.3.3邻接矩阵和邻接表的比较165

5.4最小生成树166

5.4.1Prim算法167

5.4.2Kruskal算法169

5.5最短路径173

5.5.1Dijkstra算法174

5.5.2Floyd算法176

5.6有向无环图及其应用178

5.6.1AOV网与拓扑排序178

5.6.2AOE网与关键路径181

5.7扩展与提高183

5.7.1图的其他存储方法183

5.7.2图的连通性185

5.8上机实验186

5.8.1邻接矩阵的上机实现186

5.8.2邻接表的上机实现187

5.8.3农夫抓牛187

5.8.4研发卡车189

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

习题5191

考研真题5195第6章查找技术198

6.1概述199

6.1.1查找的基本概念199

6.1.2查找算法的性能199

6.2线性表的查找技术200

6.2.1线性表查找结构的类定义200

6.2.2顺序查找201

6.2.3折半查找201

6.3树表的查找技术204

6.3.1二叉搜索树204

6.3.2平衡二叉树209

6.3.3B树213

6.4散列表的查找技术217

6.4.1散列查找的基本思想217

6.4.2散列函数的设计218

6.4.3处理冲突的方法220

6.4.4散列查找的性能分析224

6.4.5开散列表与闭散列表的比较225

6.5模式匹配225

6.5.1BF算法225

6.5.2KMP算法227

6.6扩展与提高229

6.6.1顺序查找的改进——分块查找229

6.6.2折半查找的改进——插值查找229

6.6.3平衡二叉树的改进——红黑树230

6.6.4B树的改进——B+树235

6.6.5各种查找方法的比较236

6.7上机实验237

6.7.1折半查找算法的上机实现237

6.7.2散列查找算法的上机实现237

6.7.3团队合照238

6.7.4独一无二的雪花239

思想火花——把注意力集中于主要因素241

习题6242

考研真题6245第7章排序技术248

7.1概述249

7.1.1排序的基本概念249

7.1.2排序算法的性能250

7.1.3排序类的定义250

7.2插入排序251

7.2.1直接插入排序251

7.2.2希尔排序253

7.3交换排序255

7.3.1起泡排序255

7.3.2快速排序256

7.4选择排序259

7.4.1简单选择排序259

7.4.2堆排序261

7.5归并排序266

7.5.1二路归并排序的递归实现266

7.5.2二路归并排序的非递归实现267

7.6外部排序269

7.6.1外部排序的基本思想269

7.6.2置换选择排序270

7.6.3败者树272

7.7各种排序算法的比较273

7.7.1各种排序算法的使用范例273

7.7.2各种排序算法的综合比较273

7.8扩展与提高275

7.8.1排序问题的时间下界275

7.8.2基数排序277

7.9上机实验279

7.9.1插入排序的上机实现279

7.9.2交换排序的上机实现279

7.9.3车厢重排280

7.9.4topK问题281

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

习题7283

考研真题7286附录A考研真题参考答案288附录B实验报告的一般格式293参考文献294