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

第一部分 面向对象的C＋＋程序设计基础 1

第1章　面向对象的设计方法 1

1.1 面向对象的思想 1

1.1.1　面向对象的程序设计 2

1.1.2　面向对象的语言 2

1.2　面向对象的基本概念 2

1.2.1　对象 2

1.2.2　消息 3

1.2.3　类 4

1.3　面向对象的基本特性 4

1.3.1　封装性 4

1.3.2　继承性 5

1.3.3　多态性 5

1.4 C＋＋的初步知识 5

1.4.1　从C到C＋＋ 6

1.4.2 最简单的C＋＋程序 8

1.4.3　C＋＋程序的构成和书写形式 11

1.4.4　C＋＋程序的编写和实现 12

习题一 14

第2章　C＋＋类及其对象的封装性 15

2.1 类的声明和对象的定义 15

2.1.1　类和对象的关系 15

2.1.2　声明类类型 16

2.1.3　定义对象的方法 18

2.1.4　类和结构体类型的异同 20

2.2　类的成员函数 22

2.2.1　成员函数的性质 22

2.2.2　在类外定义成员函数 22

2.2.3　inline成员函数 23

2.2.4　成员函数的存储方式 24

2.3.1　通过对象名和成员运算符访问对象中的成员 26

2.3.2　通过指向对象的指针访问对象中的成员 26

2.3 对象成员的引用 26

2.4　类的封装性和信息隐蔽 28

2.4.1　公共接口和私有实现的分离 28

2.4.2　类声明和成员函数定义的分离 29

2.5　构造函数 32

2.5.1　对象的初始化 32

2.5.2　构造函数的作用 33

2.5.3　带参数的构造函数 35

2.5.4　用参数初始化表对数据成员初始化 36

2.5.5　构造函数的重载 36

2.5.6　使用默认参数的构造函数 38

2.6　析构函数 42

2.7　调用构造函数和析构函数的顺序 44

2.8　对象指针 45

2.8.1　指向对象的指针 45

2.8.2　指向对象成员的指针 46

2.8.3　this指针 49

2.9　动态存储 50

2.10　C＋＋中的对象 51

习题二 53

第3章　友元、重载和引用 55

3.1　友元 55

3.1.1　友元的定义 55

3.1.2　友元函数 56

3.1.3　友元成员 57

3.1.4　友元类 60

3.2　重载 62

3.2.1　函数重载 62

3.2.2　运算符重载 66

3.3 引用 80

3.3.1　引用的概念 80

3.3.2　引用的应用 82

3.3.3　引用作为函数参数 83

习题三 89

第4章　继承与派生 91

4.1　继承与派生的概念 91

4.2　派生类的声明方式 92

4.3　派生类的构成 93

4.4　派生类成员函数的访问属性 95

4.4.1　公有继承 95

4.4.2　私有继承 97

4.4.3　保护成员和保护继承 99

4.4.4　多级派生时的访问属性 103

4.5　派生类的构造函数和析构函数 110

4.5.1　简单的派生类的构造函数 110

4.5.2　有子对象的派生类的构造函数 112

4.5.3　多级派生时的构造函数 114

4.5.4　派生类构造函数的特殊形式 116

4.5.5　派生类的析构造函数 116

4.6　多继承 117

4.6.1　声明多继承的方法 118

4.6.2　多继承派生类的构造函数 118

4.6.3　多继承的析构函数 120

4.6.4　多继承引起的二义性问题 121

4.7　虚基类 124

4.7.1　虚基类的概念 124

4.7.2　虚基类的初始化 126

习题四 129

第5章　多态性与虚函数 133

5.1 多态性 133

5.1.1　多态性的概念 133

5.1.2　编译时的多态性 133

5.1.3　运行时的多态性 135

5.2　虚函数 137

5.2.1　虚函数的作用 137

5.2.2　虚函数的声明 138

5.2.3　虚析构函数 141

5.3　纯虚函数与抽象类 142

5.3.1　纯虚函数 142

5.3.2　抽象类 144

5.3.3　应用实例 146

习题五 151

第6章　模板 154

6.1　模板的概念 154

6.2　函数模板 155

6.2.1　函数模板和模板函数 155

6.2.2　重载模板函数 160

6.3　类模板 161

6.3.1　类模板和模板类的概念 161

6.3.2　类模板的派生 164

习题六 165

7.1　数据结构的基本概念 166

第7章　绪论 166

第二部分　数据结构——用面向对象方法与C＋＋描述 166

7.2　抽象数据类型及面向对象概念 168

7.2.1　数据类型 168

7.2.2　数据抽象与抽象数据类型 168

7.3　算法和算法分析 169

7.3.1　算法 169

7.3.2　算法设计的要求 169

7.3.3　算法效率的度量 170

7.4　数据结构的抽象层次 172

习题七 173

第8章　线性表 174

8.1　线性表的定义 174

8.1.1　线性表的逻辑结构 174

8.1.2　线性表的存储表示 174

8.2　抽象链表类 176

8.2.1　线性链表的特点 176

8.2.2　抽象链表类的定义 177

8.2.3　抽象链表中各成员函数的实现 178

8.3　单链表 180

8.3.1　单链表的定义 180

8.3.2　单链表类的定义 180

8.3.3　单链表的常用成员函数的实现 181

8.3.4　单链表举例——一元多项式加法 185

8.4.1　循环链表的定义 188

8.4.2　循环链表类的定义 188

8.4　循环链表 188

8.4.3　循环链表常用函数的实现 189

8.4.4　循环链表举例——约瑟夫（Josephu）问题 194

8.5　双向链表 195

8.5.1　双向链表的定义 195

8.5.2　双向链表类的定义 196

8.5.3　双向链表的常用成员函数的实现 196

习题八 201

9.1.2　数组的存储结构 203

9.1.1　数组的逻辑结构 203

第9章　数组 203

9.1　数组的定义 203

9.1.3　数组的常用操作 204

9.2　数组类的定义及实现 204

9.2.1　数组类的定义 204

9.2.2　数组类常用函数的实现 206

9.2.3　数组类的应用举例——一元多项式加法 212

习题九 215

第10章　串 217

10.1 串的概念 217

10.1.1　串的定义 217

10.1.2　串的基本术语 217

10.1.3　串的存储表示和实现 218

10.1.4　串的基本运算 218

10.2.1　字符串类的定义 219

10.2　字符串类的定义及实现 219

10.2.2　字符串类中常用成员函数的实现 220

习题十 232

第11章　堆栈与队列 233

11.1　堆栈的概念及其运算 233

11.2　栈的抽象类定义 234

11.3　栈的定义及其实现 235

11.3.1　顺序栈的定义 235

11.3.2　顺序栈类的定义及典型成员函数的实现 235

11.3.3　多栈共享空间问题 238

11.3.4　链栈的定义 240

11.3.5　链式栈类的定义及典型成员函数的实现 241

11.4　堆栈的应用举例 244

11.4.1　数制转换 244

11.4.2　一个趣味游戏——迷宫问题 245

11.6　抽象队列类的定义 250

11.5 队列的概念及其运算 250

11.7　队列的定义及其实现 251

11.7.1 队列的顺序存储结构 251

11.7.2　循环队列的定义 253

11.7.3　顺序循环队列类的定义及常用成员函数的实现 254

11.7.4　链式队列的定义 256

11.7.5　链式队列类的定义及常用成员函数的实现 257

11.7.6　链式队列的应用举例 260

11.7.8　优先级队列类的定义及常用成员函数的实现 262

11.7.7　优先级队列的定义 262

习题十一 266

第12章　树 268

12.1 树、二叉树与森林的基本概念 268

12.1.1　树 268

12.1.2　二叉树 269

12.1.3　树与森林的存储结构 275

12.2.1　二叉树的抽象类 279

12.2　二叉树的抽象类和树的抽象类 279

12.2.2　树的抽象类 286

12.3　二叉树的遍历和树的遍历 293

12.3.1　二叉树的遍历 293

12.3.2　树的遍历 300

12.4　二叉排序树 303

12.5　二叉树的计数 308

12.6　赫夫曼树及其应用 310

12.6.1　最优二叉树（赫夫曼树） 310

12.6.2　赫夫曼编码 312

习题十二 314

第13章　图 316

13.1 图的基本概念 316

13.1.1　图的定义 316

13.1.2　图的术语 317

13.1.3　图的基本操作 319

13.1.4　图的存储表示 320

13.2　图的抽象类 325

13.2.1 图的邻接矩阵类 325

13.2.2　图的邻接表类 331

13.3 图的遍历 339

13.3.1 深度优先搜索DFS 340

13.3.2　广度（或宽度）优先搜索BFS 341

13.4　图的连通性与最小生成树 342

13.4.1　无向图的连通分量和生成树 342

13.4.2　最小生成树 342

13.4.3　关节点和重连通分量 349

13.5　最短路径 352

13.5.1 图结点的可达性 352

13.5.2　从某个源点到其余各顶点的最短路径 353

13.5.3　每一对顶点之间的最短路径 355

13.6　活动网络 357

13.6.1 用顶点表示活动的网络（AOV网络） 358

13.6.2　用边表示活动的网络（AOE网络） 359

习题十三 361

第14章　查找与散列结构 364

14.1　静态查找表 365

14.1.1　顺序表的查找 365

14.1.2　有序表的查找 367

14.1.3　索引顺序表的查找 369

14.2　动态查找表 370

14.3　哈希表及其查找 376

14.3.1 哈希表 376

14.3.2　哈希函数的构造方法 378

14.3.3　处理冲突的方法 381

14.3.4　哈希表的查找及其分析 382

习题十四 385

第15章　排序 387

15.1　排序的基本概念 387

15.2.1　直接插入排序 389

15.2　插入排序 389

15.2.2　其他插入排序 391

15.2.3　希尔排序 394

15.3　快速排序 396

15.4　选择排序 399

15.4.1　简单选择排序 399

15.4.2　锦标赛排序 400

15.4.3　堆排序 404

15.5 归并排序 410

15.5.1 归并 410

15.5.2　迭代的归并排序算法 411

15.6　基数排序 413

15.6.1　多关键字排序 413

15.6.2　链式基数排序 414

习题十五 417

参考文献 418