数据结构C++语言描述PDF电子书下载

第1章 绪论 1

1.1数据结构的发展简史 1

1.2基本概念和术语 3

1.2.1数据 3

1.2.2数据的逻辑结构 3

1.2.3数据的存储结构 3

1.2.4数据结构 4

1.2.5数据类型 5

1.2.6抽象数据类型与类 5

1.3算法 6

1.3.1算法的时间复杂度 7

1.3.2算法的空间复杂度 9

本章小结 9

习题 10

第2章C++类 13

2.1类的定义 13

2.2模板类 17

2.3基类和派生类 17

2.4对象的定义 19

2.5构造函数、析构函数和拷贝初始化构造函数 21

2.6运算符的重载 22

2.6.1运算符重载为类的函数成员 22

2.6.2运算符重载为非函数成员 23

本章小结 24

习题 24

第3章 线性表 25

3.1线性表的抽象数据类型 25

3.1.1线性表的逻辑结构 25

3.1.2线性表的操作 25

3.1.3线性表的存储结构 25

3.2顺序表 26

3.2.1顺序表的存储结构 26

3.2.2顺序表的操作 27

3.2.3顺序表类C++语言定义 30

3.2.4顺序表的应用——并交差运算 38

3.3非循环单链表 41

3.3.1非循环单链表的存储结构 41

3.3.2非循环单链表的操作 42

3.3.3非循环单链表类C++语言定义 46

3.3.4非循环单链表的应用——多项式的加减运算 58

3.4循环单链表 69

3.4.1循环单链表的存储结构 69

3.4.2循环单链表的操作 70

3.4.3循环单链表类C++语言定义 71

3.4.4循环单链表的应用——约瑟夫环出列 77

3.5循环双链表 78

3.5.1循环双链表的存储结构 79

3.5.2循环双链表的操作 79

3.5.3循环双链表类C++语言定义 82

3.6线性表顺序存储和链式存储结构比较 92

本章小结 93

习题 93

第4章栈 95

4.1栈的抽象数据类型 95

4.1.1栈的逻辑结构 95

4.1.2栈的操作 95

4.1.3栈的存储结构 95

4.2顺序栈 96

4.2.1顺序栈的存储结构 96

4.2.2顺序栈的操作 96

4.2.3顺序栈类C++语言定义 98

4.2.4顺序栈的应用——表达式求解 103

4.3链栈 112

4.3.1链栈的存储结构 112

4.3.2链栈的操作 112

4.3.3链栈类C++语言定义 114

本章小结 120

习题 120

第5章 队列 121

5.1队列的抽象数据类型 121

5.1.1队列的逻辑结构 121

5.1.2队列的操作 121

5.1.3队列的存储结构 121

5.2循环顺序队列 122

5.2.1循环顺序队列的存储结构 122

5.2.2循环顺序队列的操作 122

5.2.3循环顺序队列类C++语言定义 125

5.2.4循环顺序队列的应用 130

5.3非循环链队 140

5.3.1非循环链队的存储结构 140

5.3.2非循环链队的操作 140

5.3.3非循环链队类C++语言定义 142

本章小结 148

习题 148

第6章串 150

6.1串的抽象数据类型 150

6.1.1串的逻辑结构 150

6.1.2串的操作 151

6.1.3串的存储结构 151

6.2顺序串 151

6.2.1顺序串的存储结构 151

6.2.2顺序串的操作 151

6.2.3顺序串类C++语言定义 156

6.3链串 169

本章小结 169

习题 170

第7章 多维数组 171

7.1数组 171

7.2特殊矩阵 172

7.2.1对称矩阵 173

7.2.2三角矩阵 174

7.2.3对角矩阵 175

7.3稀疏矩阵（采用三元组表顺序存储） 176

7.3.1稀疏矩阵的存储结构 176

7.3.2稀疏矩阵的操作 177

7.3.3稀疏矩阵类C++语言定义 181

7.4稀疏矩阵（采用十字链表存储） 196

7.4.1稀疏矩阵的存储结构 196

7.4.2稀疏矩阵的操作 197

7.4.3稀疏矩阵类C++语言定义 198

本章小结 209

习题 210

第8章 广义表 211

8.1广义表的逻辑结构 211

8.2广义表的存储结构 212

8.3广义表的操作 213

8.4广义表类C++语言定义 216

本章小结 228

习题 229

第9章树 230

9.1树的抽象数据类型 230

9.1.1树的逻辑结构 232

9.1.2树的操作 232

9.1.3树的存储结构 232

9.2二叉树 232

9.2.1二叉树的逻辑结构 232

9.2.2二叉树的重要性质 233

9.2.3二叉树的存储结构 234

9.3二叉树（采用顺序存储） 234

9.3.1二叉树的存储结构 234

9.3.2二叉树的操作 236

9.3.3二叉树类C++语言定义 236

9.4二叉树（采用链式存储） 240

9.4.1二叉树的存储结构 240

9.4.2二叉树的操作 241

9.4.3二叉树类C++语言定义 247

9.5中序穿线二叉树 262

9.5.1中序穿线二叉树的存储结构 262

9.5.2中序穿线二叉树的操作 263

9.5.3中序穿线二叉树类C++语言定义 265

9.6树/森林 279

9.6.1树的存储结构 279

9.6.2树/森林与二叉树之间的转换 282

9.6.3树/森林与对应二叉树的遍历关系 283

9.7哈夫曼树——二叉树的应用 284

9.7.1哈夫曼树的概念 284

9.7.2哈夫曼树的存储结构 285

9.7.3哈夫曼树的操作 286

9.7.4哈夫曼树类C++语言定义 288

本章小结 299

习题 300

第10章图 302

10.1图的基本概念 302

10.1.1无向图 302

10.1.2有向图 305

10.2图的操作 307

10.2.1最小生成树 307

10.2.2最短路径 309

10.2.3图的遍历 311

10.2.4拓扑序列 312

10.2.5关键路径 313

10.3图的存储结构 316

10.4图（采用邻接矩阵存储） 316

10.4.1图的存储结构 316

10.4.2图的基本操作 317

10.4.3图类C++语言定义 322

10.5图（采用邻接表存储） 332

10.5.1图的存储结构 332

10.5.2图的基本操作 334

10.5.3图类C++语言定义 337

本章小结 349

习题 351

第11章 排序 354

11.1排序的基本概念 354

11.2插入排序 355

11.2.1直接插入排序 355

11.2.2折半插入排序 356

11.2.3静态链表插入排序 357

11.2.4希尔排序 359

11.3交换排序 360

11.3.1冒泡排序 360

11.3.2快速排序 362

11.4选择排序 364

11.4.1直接选择排序 364

11.4.2堆排序 365

11.5归并排序 368

11.6分配排序 369

11.6.1箱排序 369

11.6.2基数排序 370

11.7各种排序方法的比较 372

11.8各种排序方法C++语言实现 373

本章小结 387

习题 387

第12章 查找 389

12.1静态查找表 389

12.1.1顺序查找 389

12.1.2折半查找 390

12.1.3索引顺序查找 392

12.1.4静态查找表类C++语言定义 393

12.2动态查找表 398

12.2.1二叉排序树 398

12.2.2平衡二叉排序树 409

12.2.3 B-树 427

12.2.4哈希表 440

本章小结 451

习题 452

参考文献 454