《数据结构：C++语言描述》

第1章概论1

1.1问题求解方法1

1.1.1 问题和问题求解1

1.1.2 问题求解过程1

1.1.3 计算机求解问题的过程2

1.2什么是数据结构2

1.2.1 算法与数据结构2

1.2.2 数据结构基本概念3

1.2.3 数据的逻辑结构4

1.2.4 数据的存储表示5

1.2.5 数据结构的操作6

1.3数据抽象和抽象数据类型7

1.3.1 数据抽象和过程抽象7

1.3.2 模块化、封装与信息隐蔽7

1.3.3 数据类型和抽象数据类型8

1.4面向对象方法10

1.4.1 面向对象方法的由来10

1.4.2 面向对象方法的基本思想10

1.4.3 面向对象方法的基本要素11

1.4.4 抽象数据类型和面向对象方法12

1.4.5 C＋＋语言对抽象数据类型的支持13

1.5描述数据结构和算法13

1.5.1 数据结构的规范13

1.5.2 实现数据结构14

1.6算法分析的基本方法15

1.6.1 算法及其性能标准15

1.6.2 算法的时间复杂度16

1.6.3 渐近时间复杂度18

1.6.4 最好、最坏和平均情况时间复杂度19

1.6.5 算法按时间复杂度分类19

1.6.6 算法的空间复杂度19

本章小结20

习题120

第2章数组和链表22

2.1 两种基本的存储表示方式22

2.2结构和类22

2.2.1 结构22

2.2.2 结构表示元素23

2.3指针和动态存储分配24

2.3.1 指针24

2.3.2 动态存储分配25

2.3.3 静态变量和动态变量26

2.4数组26

2.4.1 一维数组26

2.4.2 二维数组27

2.4.3 多维数组28

2.4.4 数组和指针28

2.4.5 固定长度数组和可变长度数组28

2.5链表29

2.5.1 指向结构的指针30

2.5.2 单链表30

2.5.3 带表头结点的单链表33

2.5.4 单循环链表33

2.5.5 双向链表33

2.6采用模拟指针的链表35

2.6.1 结点结构35

2.6.2 可用空间表35

2.7 异常处理37

本章小结38

习题238

第3章栈和队列40

3.1栈40

3.1.1 栈ADT40

3.1.2 栈的顺序表示41

3.1.3 栈的链接表示44

3.2队列47

3.2.1 队列ADT47

3.2.2 队列的顺序表示48

3.2.3 队列的链接表示51

3.3表达式计算51

3.3.1 表达式51

3.3.2 中缀表达式转换为后缀表达式52

3.3.3 计算后缀表达式的值55

3.4 演示与测试58

本章小结61

习题361

第4章递归63

4.1递归和递归算法63

4.1.1 递归的概念63

4.1.2 递归算法示例64

4.2 归纳证明66

4.3 递推关系67

4.4实现递归67

4.4.1 函数调用和系统栈68

4.4.2 递归函数的性能69

4.4.3 尾递归69

4.4.4 消去递归70

本章小结70

习题470

第5章线性表和串72

5.1线性表72

5.1.1 线性表ADT72

5.1.2 线性表的顺序表示73

5.1.3 线性表的链接表示76

5.1.4 两种存储表示的比较79

5.2一元多项式算术运算80

5.2.1 多项式ADT80

5.2.2 多项式的链接表示80

5.2.3 项结点类81

5.2.4 多项式类82

5.2.5 多项式的输入和输出83

5.2.6 多项式相加84

5.2.7 多项式相乘85

5.2.8 重载运算符86

5.3串86

5.3.1 串ADT86

5.3.2 串的存储表示87

5.3.3 串运算的实现88

5.3.4 简单模式匹配算法89

5.3.5 KMP算法91

本章小结95

习题595

第6章数组和广义表97

6.1数组作为抽象数据类型97

6.1.1 数组ADT97

6.1.2 一维数组的C＋＋类98

6.2矩阵99

6.2.1 矩阵的概念99

6.2.2 矩阵ADT99

6.2.3 矩阵的二维数组表示100

6.3特殊矩阵101

6.3.1 对称矩阵101

6.3.2 带状矩阵102

6.4稀疏矩阵103

6.4.1 稀疏矩阵的三元组表103

6.4.2 稀疏矩阵转置105

6.4.3 稀疏矩阵相加107

6.4.4 稀疏矩阵相乘108

6.5稀疏矩阵的正交链表109

6.5.1 正交链表结构109

6.5.2 正交链表结点类110

6.5.3 正交链表类111

6.5.4 建立正交链表111

6.5.5 输出正交链表113

6.6广义表113

6.6.1 广义表的概念113

6.6.2 广义表ADT114

6.6.3 广义表的存储表示115

6.6.4 广义表算法116

本章小结116

习题6117

第7章树118

7.1树的基本概念118

7.1.1 树的定义118

7.1.2 基本术语119

7.2二叉树120

7.2.1 二叉树的定义120

7.2.2 二叉树的性质121

7.2.3 二叉树ADT122

7.2.4 二叉树的存储表示123

7.2.5 二叉树类123

7.2.6 实现二叉树的基本操作124

7.3二叉树的遍历126

7.3.1 二叉树遍历算法126

7.3.2 二叉树遍历的递归算法128

7.3.3 二叉树遍历的应用实例129

7.4二叉树遍历的非递归算法131

7.4.1 遍历器类131

7.4.2 中序遍历器类132

7.4.3 后序遍历器类134

7.5二叉线索树136

7.5.1 二叉线索树的定义136

7.5.2 构造中序线索树137

7.5.3 遍历中序线索树138

7.6树和森林139

7.6.1 森林与二叉树的转换139

7.6.2 树和森林的存储表示141

7.6.3 树和森林的遍历142

本章小结143

习题7143

第8章树的应用145

8.1堆145

8.1.1 堆的定义145

8.1.2 堆的顺序表示145

8.1.3 向下调整和建堆操作145

8.2优先权队列147

8.2.1 优先权队列ADT147

8.2.2 优先权队列类148

8.2.3 实现优先权队列148

8.3哈夫曼树和哈夫曼编码150

8.3.1 树的路径长度151

8.3.2 哈夫曼算法152

8.3.3 哈夫曼树类152

8.3.4 构造哈夫曼树153

8.3.5 哈夫曼编码155

8.3.6 哈夫曼编码算法156

8.4并查集和等价关系156

8.4.1 并查集ADT157

8.4.2 并查集的存储表示157

8.4.3 并查集类158

8.4.4 Union和Find函数159

8.4.5 改进的Union和Find函数159

8.4.6 按等价关系分组160

本章小结161

习题8161

第9章字典和查找162

9.1字典及其表示162

9.1.1 字典162

9.1.2 字典查找163

9.1.3 字典ADT163

9.1.4 字典的存储表示164

9.2顺序查找165

9.2.1 无序表的顺序查找165

9.2.2 有序表的顺序查找165

9.2.3 平均查找长度166

9.2.4 自组织表166

9.3二分查找167

9.3.1 二分查找算法167

9.3.2 对半查找算法168

9.3.3 二叉判定树169

9.3.4 斐波那契查找算法170

9.3.5 插值查找172

9.4 分块查找172

9.5 查找算法的时间复杂度下界173

本章小结174

习题9174

第10章二叉查找树175

10.1二叉查找树表示字典175

10.1.1 二叉查找树的定义175

10.1.2 二叉查找树的查找操作176

10.1.3 二叉查找树的插入操作177

10.1.4 二叉查找树的删除操作178

10.1.5 二叉查找树的高度179

10.2二叉平衡树179

10.2.1 二叉平衡树的定义179

10.2.2 二叉平衡树类180

10.2.3 二叉平衡树的平衡旋转181

10.2.4 二叉平衡树的插入操作185

10.2.5 二叉平衡树的删除操作187

10.2.6 二叉平衡树的高度189

10.3伸展树190

10.3.1 自调节树和伸展树190

10.3.2 伸展树的伸展操作191

10.3.3 伸展树类193

10.3.4 旋转的实现193

10.3.5 伸展树的插入操作194

10.3.6 分摊时间分析195

10.4红黑树195

10.4.1 红黑树的定义195

10.4.2 红黑树的查找操作196

10.4.3 红黑树的插入操作196

10.4.4 红黑树的删除操作199

10.4.5 红黑树的高度199

本章小结199

习题10199

第11章多叉查找树201

11.1 m叉查找树201

11.2Bˉ树202

11.2.1 Bˉ树的定义203

11.2.2 Bˉ树的高度203

11.2.3 Bˉ树的查找操作203

11.2.4 Bˉ树的插入操作204

11.2.5 Bˉ树的删除操作206

11.2.6 Bˉ树类207

11.2.7 Bˉ树的查找函数208

11.2.8 Bˉ树的插入函数209

11.2.9 Bˉ树的删除函数210

11.3键树212

11.3.1 键树的定义212

11.3.2 双链树213

11.3.3 Trie树214

11.3.4 Trie树的查找操作216

11.3.5 Trie树的插入操作216

11.3.6 Trie树的删除操作217

11.3.7 Trie树性能分析218

本章小结218

习题11218

第12章跳表和散列表219

12.1跳表219

12.1.1 跳表的概念219

12.1.2 跳表类221

12.1.3 跳表的查找函数222

12.1.4 跳表的插入函数223

12.1.5 跳表的删除函数224

12.1.6 跳表性能分析224

12.2散列表224

12.2.1 散列技术225

12.2.2 散列函数226

12.2.3 拉链法227

12.2.4 开地址法228

12.2.5 线性探查法228

12.2.6 其他开地址法231

12.2.7 散列表性能分析233

本章小结233

习题12233

第13章图235

13.1图的基本概念235

13.1.1 图的定义与术语235

13.1.2 图的抽象数据类型237

13.2图的存储结构238

13.2.1 图的矩阵表示238

13.2.2 图的邻接矩阵实现239

13.2.3 图的邻接表表示241

13.2.4 图的邻接表实现242

13.2.5 有向图的正交链表表示245

13.2.6 无向图的邻接多重表表示245

13.3图的遍历246

13.3.1 扩充的图类246

13.3.2 深度优先遍历247

13.3.3 广度优先遍历248

13.3.4 基本遍历方法249

13.4拓扑排序250

13.4.1 AOV网络250

13.4.2 拓扑排序算法252

13.4.3 拓扑排序算法实现252

13.5关键路径254

13.5.1 AOE网254

13.5.2 关键路径算法255

13.5.3 关键路径算法实现257

13.6最小代价生成树258

13.6.1 基本概念258

13.6.2 普里姆算法258

13.6.3 克鲁斯卡尔算法260

13.6.4 算法正确性262

13.7单源最短路径262

13.7.1 最短路径问题262

13.7.2 迪杰斯特拉算法263

13.7.3 数据结构选择263

13.7.4 迪杰斯特拉算法实现264

13.8所有顶点之间的最短路径266

13.8.1 弗洛伊德算法266

13.8.2 弗洛伊德算法实现267

本章小结268

习题13268

第14章内排序270

14.1 基本概念270

14.2插入排序271

14.2.1 直接插入排序271

14.2.2 顺序表的直接插入排序272

14.2.3 单链表的直接插入排序273

14.2.4 希尔排序274

14.2.5 对半插入排序276

14.3选择排序276

14.3.1 简单选择排序276

14.3.2 堆排序277

14.4交换排序278

14.4.1 冒泡排序278

14.4.2 快速排序280

14.4.3 快速排序性能分析281

14.5两路合并排序283

14.5.1 合并两个有序序列284

14.5.2 两路合并排序迭代算法284

14.5.3 两路合并排序递归算法285

14.5.4 单链表两路合并排序285

14.6 排序算法的时间复杂度下界287

14.7基数排序288

14.7.1 分配排序289

14.7.2 基数排序算法289

14.7.3 基数排序实现290

本章小结292

习题14292

第15章文件和外排序294

15.1辅助存储器简介294

15.1.1 主存储器和辅助存储器294

15.1.2 磁盘存储器294

15.2文件295

15.2.1 文件的基本概念295

15.2.2 文件的组织方式296

15.3文件的索引结构298

15.3.1 静态索引结构298

15.3.2 动态索引结构299

15.4外排序300

15.4.1 外排序的基本过程300

15.4.2 初始游程的生成300

15.4.3 多路合并302

15.4.4 最佳合并树304

本章小结304

习题15305

第16章实习指导和实习题306

16.1 实习目的、要求和步骤306

16.2 面向对象表示法307

16.3实习报告和范例308

16.3.1 实习报告308

16.3.2 实习题范例309

16.3.3 实习报告范例309

16.4实习题312

实习1 C＋＋语言的类及模板的使用312

实习2 数组和链表操作313

实习3 栈、队列及表达式计算313

实习4 线性表的操作及应用314

实习5 一元多项式的相加和相乘314

实习6 对称矩阵和稀疏矩阵的压缩存储315

实习7 串操作和文本处理315

实习8 二叉树操作和哈夫曼编码315

实习9 有序表查找316

实习10 Bˉ树检索317

实习11 散列表查找317

实习12 图的操作及应用318

实习13 内排序算法及其性能比较318

实习14 置换选择和K路合并的外排序算法318

附录A程序测试和调试319

A.1 面向对象程序测试319

A.2 程序测试步骤319

A.3 测试方法320

A.4 程序调试321

附录B2019年计算机考研大纲与教材内容对照323

B.1 2019年计算机考研大纲323

B.2 教材内容对2019年计算机考研大纲的适应性324

参考文献326