C++数据结构导引PDF|Epub|txt|kindle电子书版本网盘下载

C++数据结构导引PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

目录1

第1章　软件开发1

1.1 问题分析和需求规格说明1

1.2　设计3

1.2.1 对象3

1.2.2　操作4

1.2.3　算法5

1.2.4　函数YearSum（）的设计5

1.2.5　函数DisplayTable（）的设计6

1.2.6　关于算法的一些最后说明7

1.3　编码10

1.4　测试、执行和调试14

1.5　维护18

1.5.1 小测验18

1.5.2　练习19

第2章　数据结构入门和抽象数据类型——C风格类型21

2.1 数据结构、抽象数据类型和实现21

2.2　简单数据类型24

2.2.1 Boolean数据24

2.2.2 Character数据25

2.2.3　整型数据26

2.2.4　实数数据28

2.2.5 小结30

2.2.7　练习31

2.2.6　小测验31

2.3　数组32

2.3.1 一维数组33

2.3.2　下标运算35

2.3.3　数组作为形参35

2.3.4　越界错误37

2.3.5　数组的问题37

2.3.6　多维数组38

2.3.7　小测验44

2.3.8　练习45

2.4.1　为什么需要结构46

2.4　结构46

2.4.2 C风格结构47

2.4.3　结构的运算49

2.4.4　联合50

2.4.5　内存中的结构52

2.4.6　小测验53

2.4.7　练习53

2.5　过程式编程55

2.5.1　例子：一个时间数据类型55

2.5.2 PP对OOP59

第3章　数据结构和抽象数据结构进阶——C++类型64

3.1　类64

3.1.2　类声明65

3.1.1 “传统的”（C）结构，OOP（C++）结构以及类之间的区别65

3.1.3　例子：C++标准I/O类66

3.2　用户定义类型的例子：一个Time类67

3.2.1 实现一个类68

3.2.2　一些现象70

3.2.3　类构造函数72

3.2.4　复制操作——初始化和赋值76

3.2.5　访问函数77

3.2.6　输入／输出——重载运算符——友元函数78

3.2.7　其他操作：关系操作和前进83

3.2.8　总结以及其他一些细节85

3.2.10　练习87

3.2.9　小测验87

3.3　作为ADT的串88

3.3.1 串的C风格实现89

3.3.2　一个串类90

3.3.3　练习93

3.4 C++串类型93

3.4.1　定义和构造函数94

3.4.2　存储94

3.4.3　输入／输出94

3.4.4 string流96

3.4.5　修改符97

3.4.6　复制符97

3.4.8　查找操作98

3.4.7　访问单独的字符98

3.4.9 比较99

3.4.10 string和C风格串100

3.4.11 小测验100

3.4.12　练习101

3.5　一个例子：文本编辑101

3.5.1　对象102

3.5.2　操作102

3.5.3　文本编辑算法102

3.6　数据加密（可选）105

3.6.1　数据加密标准107

3.6.2　公共密钥加密110

3.6.3　练习113

3.7　模式匹配（可选）114

第4章　栈128

4.1　栈的介绍128

4.2　设计和创建一个Stack类132

4.2.1　设计一个Stack类132

4.2.2　实现一个栈类132

4.2.3　选择数据成员133

4.2.4　函数成员135

4.2.5　前瞻142

4.2.6　小测验142

4.2.7　练习143

4.3.1　在函数调用中使用栈144

4.3　栈的两个应用：函数调用，逆波兰表示144

4.3.2　逆波兰表示中栈的应用145

4.3.3　小测验153

4.3.4　练习153

第5章　队列158

5.1 队列入门158

5.1.1　例子：训练和实践问题159

5.1.2　调度队列的例子163

5.2　基于数组的队列实现165

5.2.1　小测验168

5.2.2　练习169

5.3 队列的应用：信息中心仿真170

5.3.1 问题分析和需求规格说明171

5.3.2　设计171

5.3.3　编码和执行174

第6章 改进ADT——第1部分：模板和标准容器181

6.1　介绍：可重用性和通用性的发展181

6.1.1　从算法到算法182

6.1.2　从数据到容器183

6.2　函数通用性——重载和模板183

6.2.1　重载184

6.2.2　函数模板186

6.2.3　例子：显示一个数组189

6.3.2　类模板190

6.3.1 Typedef有什么错190

6.3　类通用性——模板190

6.3.3　一个Stack类模板192

6.3.4 Stack类模板的另一个版本196

6.3.5　标准C++的容器类模板197

6.3.6　小测验198

6.3.7　练习198

6.4 vector容器198

6.4.1 定义vector对象199

6.4.2　一些vector操作200

6.4.3　例子：登录计数204

6.4.4 内部实现一瞥——增加容量207

6.4.5　对迭代器的第一次探讨209

6.4.7　综合比较：vector对数组212

6.4.6　一些涉及到迭代器的vector函数成员212

6.4.8　小测验213

6.4.9　练习214

6.5　多维向量215

6.5.1　二维vector对象216

6.5.2　二维vector操作216

6.5.3　练习218

6.6　其他标准容器——deque、stack和queue218

6.6.1 STL的deque类模板219

6.6.2 Stack类模板的一个新（但是非必需的）版本221

6.6.3 STL的stack适配器222

6.7.1 bitset对象的声明224

6.7 bitsets（可选）224

6.6.4 STL的queue适配器224

6.6.5 小测验224

6.7.2 bitset操作225

6.7.3　使用bitset实现集合226

6.7.4　例子：使用埃拉托色尼（Eratoshenes）筛寻找素数228

6.7.5　练习230

6.8 valarrays（可选）230

6.8.1 valarray对象的声明231

6.8.2 valarray操作231

6.8.3 slices、masks以及间接数组232

6.8.4　练习233

7.1.1　例子：递归的求幂和求阶乘函数238

7.1　递归238

第7章　改进ADT——第2部分：递归，算法分析，以及标准算法238

7.1.2　糟糕递归的例子：Fibonacci数字242

7.1.3　例子：折半搜索245

7.1.4　例子：回文检查程序246

7.1.5　小测验248

7.1.6　练习248

7.2　递归的例子：Hanoi塔；分析251

7.2.1 Hanoi塔251

7.2.2　分析253

7.2.3　练习258

7.3　实现递归259

7.4　算法效率261

7.4.1　小测验271

7.4.2　练习271

7.5 C++中的标准算法272

7.5.1　例子：STL的sort算法272

7.5.2 STL算法的例子275

7.5.3 〈numeric〉库中的算法276

7.5.4　例子：花样滑冰评判277

7.5.5　小测验278

7.6　算法正确性证明278

7.6.1　例子：计算平均值278

7.6.3　总结280

7.6.2　例子：递归求幂函数280

7.6.4　练习281

第8章　列表287

8.1　列表的顺序存储实现287

8.1.1　存储结构287

8.1.2　操作的实现288

8.1.3　小测验290

8.1.4　练习290

8.2　对链表的介绍290

8.2.1　它们是什么291

8.2.2　实现基本列表操作291

8.2.3 小结294

8.2.5　练习295

8.2.4　小测验295

8.3　基于数组的链表实现296

8.3.1　节点结构296

8.3.2　存储池管理298

8.3.3　练习300

8.4 C++中的指针301

8.4.1 指针301

8.4.2　基本指针操作303

8.4.3　指针的其他用法309

8.4.4　小测验310

8.4.5　练习310

8.5 运行时分配和释放311

8.5.1 New操作——运行时数组312

8.5.2 delete操作314

8.5.3　类中的运行时分配——析构函数、复制构造函数和赋值操作符317

8.5.4 最后一点325

8.5.5　小测验327

8.5.6　练习328

8.6　在C++中基于指针来实现链表328

8.6.1 节点结构329

8.6.2 LinkedList的数据成员330

8.6.3 LinkedList的函数成员330

8.6.4　练习331

8.7.3　基本list操作334

8.7.2　迭代器334

8.7　标准list类模板334

8.7.1 List 其他容器类的比较334

8.7.4　例子：互联网地址338

8.7.5 小测验340

8.7.6　练习340

第9章　其他链表结构346

9.1　单向链表的某些变种346

9.1.1　链式栈和链式队列346

9.1.2　带头节点或尾节点的链表347

9.1.3　循环链表348

9.1.5　练习350

9.1.4　小测验350

9.2　稀疏矩阵的链式实现351

练习355

9.3 哈希表356

9.3.1 哈希函数356

9.3.2 冲突处理策略356

9.3.3 改进357

9.3.4　小测验358

9.3.5　练习359

9.4　双向链表和标准的C++链表359

9.4.1　双向链表359

9.4.2　对C++中列表的内部一瞥360

9.4.3　应用：长整数运算363

9.4.4　练习367

9.5　其他多链列表368

9.5.1 多序列表368

9.5.2　稀疏矩阵368

9.5.3　广义表370

9.5.4　练习372

第10章　二叉树377

10.1 线性查找和折半查找的复习377

10.1.1　线性查找377

10.1.2　折半查找378

10.1.3　练习380

10.2.1　树的定义和例子381

10.2　二叉树的介绍381

10.2.2　二叉树的数组表示382

10.2.3　二叉树的链表表示383

10.3　二叉查找树385

10.3.1　对BST的查找385

10.3.2　在BST中插入项386

10.3.3　例子：计算机登录验证388

10.3.4　不平衡（Lopsidedness）问题391

10.3.5　小测验392

10.3.6　练习392

10.4　作为递归数据结构的二叉树392

10.4.1 遍历393

10.4.2　递归查找396

10.4.4　删除397

10.4.3 递归插入397

10.4.5　小测验402

10.4.6　练习402

10.5　二叉树的应用：哈夫曼编码404

10.5.1　变长码404

10.5.2　立刻可解码性405

10.5.3　哈夫曼编码405

10.5.4　练习412

11.1　某些计算时间为O（n2）的排序方法417

11.1.1　选择排序417

第11章　排序417

11.1.2　交换排序419

11.1.3　排序算法的性能比较423

11.1.4　间接排序424

11.1.5 小测验424

11.1.6　练习424

11.2　堆和堆排序426

11.2.1　堆426

11.2.2　堆的基本操作427

11.2.3 STL中的堆算法430

11.2.4　堆和优先级队列432

11.2.5 小测验434

11.2.6　练习434

11.3.1 拆分操作436

11.3　快速排序436

11.3.2　快速排序438

11.3.3 改进441

11.3.4　小测验441

11.3.5　练习441

11.4　归并排序442

11.4.1 归并列表443

11.4.2　折半归并排序444

11.4.3　自然归并排序445

11.4.4　小测验447

11.4.5　练习448

12.1.1　封装性452

第12章　OOP和ADT452

12.1 OOP和ADTs的简要历史和概览452

12.1.2　继承性453

12.1.3　多态性和动态联编453

12.1.4　小测验454

12.2　继承和面向对象设计454

12.2.1　从OCD到OOD454

12.2.2 OOD的第1个例子：许可证455

12.2.3　类之间的is-a、has-a和uses-a关系459

12.2.4 OOD的第2个例子：工资461

12.2.5　派生类中的操作463

12.2.6　派生类中的构造函数463

12.2.7 OOD的第3个例子：有限栈465

12.2.8 OOD的第4个例子：scrolls468

12.2.9　小测验469

12.2.1　0练习469

12.3 多态性、虚拟函数和ADTs470

12.3.1　联编问题470

12.3.2　虚拟函数和动态联编472

12.3.3　例子：栈、有限栈和Scroll473

12.3.4　纯虚拟函数和抽象类476

12.3.5　小测验478

12.3.6　练习478

12.4　异构数据结构478

12.4.1　构建异构数据结构479

12.4.2　虚拟函数的必要性480

第13章　树483

13.1　线索化二叉查找树483

13.1.1　小测验485

13.1.2　练习486

13.2　平衡树：AVL树486

13.2.1 例子：州简称的BST487

13.2.2　基本的重新平衡旋转操作491

13.2.3　小测验493

13.2.4　练习494

13.3 2-3-4树、红—黑树、B-树和其他树494

13.3.1 2-3-4树495

13.3.2 红—黑树498

13.3.3　B-树501

13.3.4　用二叉树来表示树和森林502

13.3.5　小测验503

13.3.6　练习503

13.4 STL中的关联容器——map（可选）504

小测验507

第14章　图和有向图509

14.1 有向图509

14.1.1　邻接矩阵表示510

14.1.2　邻接表表示511

14.1.3　小测验512

14.1.4　练习513

14.2　搜索和遍历有向图515

14.2.1　深度优先搜索516

14.2.2　广度优先搜索516

14.2.3　遍历和最短路径问题517

14.2.4 NP完全性问题523

14.2.5　小测验524

14.2.6　练习524

14.3　图525

14.3.1　邻接矩阵和邻接表表示526

14.3.2　边列表表示526

14.3.3　连通性527

14.3.4　小测验531

14.3.5　练习532

附录A ASCII字符集536

附录B　数制系统538

练习539

附录C 基本C++542

C1 C++程序结构542

C2　编译器命令542

C3　标准库543

C4　注释545

C5　标识符和关键字545

C6　基本数据类型547

C7　常量548

C8　声明548

C9　运算符和表达式548

C10　控制结构552

C11　函数556

C12　对象的生命周期、作用域和名字空间560

C13　文件562

附录D　其他C++特性566

D1　数组、结构和联合566

D2　流操作567

D3　串操作570

D4　异常575

D5　关于函数模板的更多信息577

D6　指针的其他应用578

附录E　小测验答案583

索引594