数据结构 C++实现 修订版PDF电子书下载

1绪论 1

1.1（算法+数据结构）=程序 1

1.2数据结构的基本概念 2

1.2.1两个简单的数据结构实例 2

1.2.2什么是数据结构 3

1. 3 C++语言基础 4

1. 3.1程序结构 5

1. 3.2数据声明和作用域 6

1. 3.3输入/输出 7

1.3.4函数 9

1.3.5参数传递 10

1.3.6函数名重载 11

1.3.7动态内存分配 11

1.3.8结构与联合 12

1.4算法性能与复杂度 16

1.4.1算法的定义 16

1.4.2算法的性能标准 17

1.4.3算法的复杂度 17

习题1 21

2抽象数据类型和C++类 23

2. 1抽象数据类型 23

2.1.1从数据类型到抽象数据类型 23

2.1.2封装和信息隐藏 24

2. 1.3抽象数据类型描述 25

2.2类与对象的基本概念 26

2.2. 1类与对象 26

2.2.2消息与合作 28

2.2.3多态性 28

2.3面向对象的程序设计方法 28

2.4 C++类与对象 29

2. 5构造函数和析构函数 31

2. 6工具函数 35

2. 7继承 38

2. 8 this指针的使用 41

2. 9虚函数、多态性以及动态联编 42

2.9. 1虚函数和多态性 42

2.9.2动态联编 50

2. 10模板类 52

习题2 54

3线性表 56

3. 1线性表的定义 56

3. 2线性表的顺序表示 57

3.2.1顺序表的类定义 57

3.2.2顺序表插入、删除算法的复杂度分析 60

3. 2.3顺序表的应用 61

3. 3线性表的链表表示 62

3.3. 1单链表 62

3.3. 2单循环链表 73

3.3.3双向循环链表 73

3.3. 4静态链表 79

3.4多项式抽象数据类型 81

3.4. 1多项式表示 81

3.4.2多项式相加 81

习题3 83

4栈、队列和递归 85

4. 1栈 85

4.1.1顺序栈 86

4.1.2链式栈 88

4.1.3表达式的计算 90

4. 2队列 94

4.2.1循环队列 95

4.2.2链队列 98

4.3递归 100

4. 3. 1递归的概念 100

4. 3.2递归过程与递归工作栈 101

4.3. 3消除递归 103

4. 3. 4迷宫问题 107

习题4 109

5串、数组和广义表 112

5.1字符串 112

5.1.1字符串的定义、存储结构 112

5.1. 2串的操作 113

5.1.3常用的C+++字符串函数 114

5.1.4串类及其实现 115

5.1. 5模式匹配算法 121

5. 2数组 125

5. 2. 1 C+++中数组的定义 126

5.2.2数组的抽象数据类型表示 126

5.2.3数组的顺序存储结构 128

5. 3稀疏矩阵 130

5. 3.1三元组顺序表 131

5. 3.2十字链表 133

5.4广义表 135

5.4.1广义表的定义 135

5.4.2广义表的存储结构 136

5. 4. 3 n元多项式的表示 139

5.4.4广义表的递归算法 141

习题5 144

6树和森林 147

6. 1树的概念 147

6.1.1树的定义 148

6. 1. 2树的术语 148

6.1.3树的表示形式 149

6.1.4树的基本操作和抽象数据类型 149

6. 2二叉树 153

6. 2. 1二叉树的定义 153

6. 2. 2二叉树的性质 153

6.2.3二叉树的基本操作和抽象数据类型 155

6.3二叉树的存储结构 158

6.3.1数组表示法 159

6.3.2链表表示法 160

6.3. 3二叉树的二叉链表类声明 160

6.4遍历二叉树 164

6. 4.1前序遍历 164

6.4.2中序遍历 165

6.4.3后序遍历 165

6.4.4层序遍历 166

6.5线索二叉树 168

6. 5.1线索二叉树的定义 168

6.5.2线索二叉树的类定义 170

6.5.3中序线索二叉树 173

6. 6二叉树的应用 177

6.6.1堆 177

6. 6.2哈夫曼树 183

6. 7树和森林 187

6. 7.1树的存储结构 187

6.7.2树、森林和二叉树的转换 190

6.7.3树的遍历 192

6.7.4森林的遍历 193

6. 8等价类及其表示 194

6. 8. 1等价关系与等价类 194

6. 8. 2并查集 195

习题6 199

7图 203

7. 1图的基本概念 203

7. 1.1图的定义 203

7.1.2图的术语 204

7.1.3图的基本操作和抽象数据类型 207

7. 2图的存储结构 209

7.2. 1邻接矩阵 209

7. 2. 2邻接表 212

7.2.3邻接多重表 217

7.2.4十字链表 219

7.3图的遍历与连通性 220

7. 3. 1深度优先遍历 220

7.3. 2广度优先遍历 221

7.3.3连通分量 223

7.4最小生成树 224

7.4. 1克鲁斯卡尔算法 225

7.4.2普里姆算法 228

7.5最短路径 230

7.5.1弧上权值为非负情形的单源点最短路径问题 231

7.5.2弧上权值为任意值的单源点最短路径问题 234

7.5. 3所有顶点之间的最短路径 236

7. 6活动网络 238

7.6.1用顶点表示活动的网络 238

7.6.2用边表示活动的网络 242

习题7 246

8查找 250

8.1基本概念 250

8.2顺序表 251

8.2. 1顺序表的查找 251

8.2.2有序表的折半查找 252

8.3索引顺序表 256

8.3. 1索引顺序表 256

8. 3.2倒排表 258

8.4二叉排序树 260

8.4.1二叉排序树定义 260

8.4.2二叉排序树上的查找 262

8.4.3二叉排序树的插入 263

8. 4.4二叉排序树的删除 265

8.4.5二叉排序树查找的性能分析 266

8.5平衡二叉树 266

8.5.1平衡二叉树的定义 267

8. 5.2平衡旋转 267

8.5.3平衡二叉树的插入和删除 269

8.6 B-树 273

8.6. 1动态的m路查找树 273

8. 6. 2 B-树 274

8.6.3 B-树的插入 274

8.6.4 B-树的删除 276

8.6.5 B+树 278

8.7散列表查找 279

8.7. 1散列表的基本概念 279

8.7. 2散列函数 281

8.7.3处理溢出的闭散列方法 282

8.7.4处理溢出的开散列方法——链地址法 286

8.7.5散列表分析 287

习题8 288

9排序 292

9.1基础知识 292

9.1. 1基本概念 292

9.1.2排序表的抽象数据类型描述和类定义 293

9. 2交换排序 299

9.2. 1冒泡排序 299

9.2. 2快速排序 300

9. 3插入排序 302

9.3.1直接插入排序 302

9. 3. 2折半插入排序 306

9. 3. 3希尔排序 306

9.4选择排序 308

9. 4. 1直接选择排序 308

9.4.2锦标赛排序 310

9. 4.3堆排序 312

9. 5归并排序 314

9.5.1归并 314

9.5.2两路归并排序 315

9. 5. 3递归的归并排序 317

9. 6基数排序 319

9.6.1多关键字排序 319

9. 6. 2链式基数排序 320

9. 7各种排序方法的选择和使用 322

习题9 323

主要参考文献 326