数据结构 C++版PDF电子书下载

第1章 绪论 1

1.1数据结构在程序设计中的作用 1

1.2本书讨论的主要内容 3

1.3数据结构的基本概念 5

1.3.1数据结构 5

1.3.2抽象数据类型 7

1.4算法及算法分析 9

1.4.1算法及其描述方法 9

1.4.2算法分析 12

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

习题1 17

思考题1 19

第2章 线性表 21

2.1线性表的逻辑结构 21

2.1.1线性表的定义 21

2.1.2线性表的抽象数据类型定义 22

2.2线性表的顺序存储结构及实现 24

2.2.1线性表的顺序存储结构——顺序表 24

2.2.2顺序表的实现 25

2.3线性表的链接存储结构及实现 30

2.3.1单链表 30

2.3.2循环链表 40

2.3.3双链表 40

2.4顺序表和链表的比较 42

2.4.1时间性能比较 42

2.4.2空间性能比较 43

2.5线性表的其他存储方法 43

2.5.1静态链表 43

2.5.2间接寻址 45

2.6应用举例 45

2.6.1顺序表的应用举例——大整数求和 45

2.6.2单链表的应用举例——一元多项式求和 47

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

习题2 50

思考题2 53

第3章 栈和队列 55

3.1栈 55

3.1.1栈的逻辑结构 55

3.1.2栈的顺序存储结构及实现 57

3.1.3栈的链接存储结构及实现 61

3.1.4顺序栈和链栈的比较 63

3.2队列 64

3.2.1队列的逻辑结构 64

3.2.2队列的顺序存储结构及实现 65

3.2.3队列的链接存储结构及实现 68

3.2.4循环队列和链队列的比较 71

3.3应用举例 71

3.3.1栈的应用举例——表达式求值 71

3.3.2队列的应用举例——火车车厢重排 73

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

习题3 75

思考题3 77

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

4.1字符串 79

4.1.1字符串的定义 79

4.1.2字符串的存储结构 80

4.1.3模式匹配 81

4.2多维数组 85

4.2.1数组的定义 85

4.2.2数组的存储结构与寻址 86

4.3矩阵的压缩存储 87

4.3.1对称矩阵的压缩存储 87

4.3.2三角矩阵的压缩存储 88

4.3.3对角矩阵的压缩存储 89

4.3.4稀疏矩阵的压缩存储 90

4.4应用举例 92

4.4.1字符串的应用举例——凯撒密码 92

4.4.2数组的应用举例——幻方 93

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

习题4 94

思考题4 96

第5章 树和二叉树 99

5.1树的逻辑结构 99

5.1.1树的定义和基本术语 99

5.1.2树的抽象数据类型定义 101

5.1.3树的遍历操作 102

5.2树的存储结构 103

5.2.1双亲表示法 103

5.2.2孩子表示法 104

5.2.3双亲孩子表示法 106

5.2.4孩子兄弟表示法 107

5.3二叉树的逻辑结构 107

5.3.1二叉树的定义 108

5.3.2二叉树的基本性质 109

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

5.3.4二叉树的遍历操作 113

5.4二叉树的存储结构及实现 114

5.4.1顺序存储结构 114

5.4.2二叉链表 115

5.4.3三叉链表 120

5.4.4线索链表 120

5.5二叉树遍历的非递归算法 125

5.5.1前序遍历非递归算法 125

5.5.2中序遍历非递归算法 126

5.5.3后序遍历非递归算法 127

5.6树、森林与二叉树的转换 128

5.7应用举例 131

5.7.1二叉树的应用举例——哈夫曼树及哈夫曼编码 131

5.7.2树的应用举例——八枚硬币问题 136

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

习题5 138

思考题5 140

第6章 图 143

6.1图的逻辑结构 143

6.1.1图的定义和基本术语 143

6.1.2图的抽象数据类型定义 147

6.1.3图的遍历操作 148

6.2图的存储结构及实现 151

6.2.1邻接矩阵 152

6.2.2邻接表 155

6.2.3十字链表 159

6.2.4邻接多重表 159

6.2.5邻接矩阵和邻接表的比较 160

6.3最小生成树 161

6.3.1 MST性质 161

6.3.2 Prim算法 162

6.3.3 Kruskal算法 165

6.4最短路径 168

6.4.1 Dijkstra算法 169

6.4.2 Floyd算法 171

6.5有向无环图及其应用 173

6.5.1 AOV网与拓扑排序 173

6.5.2 AOE网与关键路径 176

6.6应用举例 179

6.6.1图的应用举例1——七桥问题 179

6.6.2图的应用举例2——七巧板涂色 180

思想火花——数据模型在问题求解中的作用 181

习题6 181

思考题6 185

第7章 查找技术 187

7.1概述 187

7.1.1查找的基本概念 187

7.1.2查找算法的性能 188

7.2线性表的查找技术 189

7.2.1顺序查找 189

7.2.2折半查找 191

7.3树表的查找技术 195

7.3.1二叉排序树 195

7.3.2平衡二叉树 201

7.4散列表的查找技术 206

7.4.1概述 206

7.4.2散列函数的设计 207

7.4.3处理冲突的方法 210

7.4.4散列查找的性能分析 213

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

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

习题7 215

思考题7 218

第8章 排序技术 219

8.1概述 219

8.1.1排序的基本概念 219

8.1.2排序算法的性能 220

8.2插入排序 221

8.2.1直接插入排序 221

8.2.2希尔排序 223

8.3交换排序 225

8.3.1起泡排序 225

8.3.2快速排序 228

8.4选择排序 231

8.4.1简单选择排序 231

8.4.2堆排序 233

8.5归并排序 238

8.5.1二路归并排序的非递归实现 238

8.5.2二路归并排序的递归实现 241

8.6分配排序 242

8.6.1桶式排序 242

8.6.2基数排序 244

8.7各种排序方法的比较 247

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

习题8 250

思考题8 253

第9章 索引技术 255

9.1索引的基本概念 255

9.2线性索引技术 256

9.2.1稠密索引 256

9.2.2分块索引 257

9.2.3多重表 258

9.2.4倒排表 258

9.3树形索引 259

9.3.1 2-3树 259

9.3.2 B-树 262

9.3.3 B+树 266

思想火花——随处可见的索引 267

习题9 268

附录A预备知识 271

A.1数学术语 271

A.2级数求和 271

A.3集合 272

A.4关系 273

附录B C++语言基本语法 275

B.1程序结构 275

B.2数据类型 276

B.3控制语句 278

B.4输入与输出 279

B.5动态存储分配 280

B.6函数 281

B.7类与对象 284

B.8模板 287

B.9异常处理 288

附录C词汇索引 289

参考文献 294