C\C++与数据结构(第5版)

第1章对象和运算符1

1.1**个C语言程序1

1.1.1什么是程序1

1.1.2对象1

1.1.3表达式2

1.1.4**个C语言程序4

1.1.5集成开发环境6

1.2循环结构7

1.2.1while语句8

1.2.2for语句11

1.3标准输入函数12

1.4分而治之16

1.5选择结构(ifelse语句)17

1.6关系运算和逻辑运算19

1.7条件表达式和复合赋值表达式20

1.8输入验证21

1.8.1break和continue语句22

1.8.2前哨24

练习26

第2章函数30

2.1函数的定义和调用30

2.2函数声明35

2.3自设头文件36

2.4应用函数设计举例38

2.4.1阶乘38

2.4.2质数41

2.4.3*大公约数43

2.4.4斐波那契数列44

2.4.5π的近似值46

2.5函数和对象的存储类别48

2.5.1局部对象49

2.5.2静态局部对象49

2.5.3外部对象50

2.5.4寄存器对象50

2.5.5动态对象51

练习51

C/C++与数据结构(第5版)目录第3章指针和数组52

3.1指针和地址传递52

3.1.1地址和指针52

3.1.2两种参数传递54

3.1.3对象值交换57

3.2数组和线性表60

3.3指针和数组的关系63

3.3.1指针和数组的统一63

3.3.2数组求和66

3.3.3数组逆置68

3.4const限定符71

3.5数组应用75

3.5.1*大元素75

3.5.2选择排序78

3.5.3顺序搜索和二分搜索81

3.5.4平均值84

3.6类型转换85

3.7动态数组86

3.7.1内存分配函数86

3.7.2*近平均值89

3.8指针与索引91

3.9函数指针93

练习94

第4章顺序表98

4.1数组求和分析98

4.2动态数组应用100

4.3结构初步101

4.4typedef名字103

4.5准构造和准析构105

4.6尾插108

4.7读取110

4.8删除113

4.9基本函数补充115

4.10参数合法性检验116

4.11顺序表的意义和局限性117

4.12顺序表头文件119

练习121

第5章结构、联合、枚举123

5.1结构123

5.1.1结构与对象123

5.1.2结构Date126

5.1.3结构与数组129

5.2联合131

5.3枚举常量和switchcase语句134

练习139

第6章字符串141

6.1字符型141

6.2字符串特点144

6.3字符串基本操作147

6.3.1字符串输入输出147

6.3.2字符串求长148

6.3.3字符串复制148

6.3.4字符串连接149

6.3.5字符串大小写150

6.3.6字符串比较151

6.3.7字符查找151

6.3.8字符串匹配152

6.4自设计字符串基本操作153

6.4.1设计字符串输入和输出153

6.4.2设计字符串求长154

6.4.3设计字符串复制155

6.4.4设计字符串连接156

6.4.5设计字符串大小写157

6.4.6设计字符串比较158

6.4.7设计字符查找159

6.4.8字符串头文件161

6.5函数返回指针165

练习166

第7章文件168

7.1文件指针168

7.2文件打开与关闭168

7.3文件的读写171

7.3.1字符的读写171

7.3.2字符串的读写174

7.3.3格式读写175

7.3.4无格式读写177

练习181

第8章链表183

8.1链表设计183

8.1.1链表结点183

8.1.2链表雏形186

8.1.3链表边界读取188

8.1.4链表插入188

8.1.5链表删除191

8.1.6链表头文件193

8.2链表逆置194

8.3Josephus问题196

练习199

第9章二维数组和指针200

9.1二维数组200

9.1.1二维数组定义200

9.1.2二维数组初始化200

9.1.3二维数组和指针202

9.2二维数组和一维数组205

9.2.1二维数组作为一维数组205

9.2.2马鞍点206

9.2.3一维数组作为二维数组208

9.3指针数组和二级指针209

9.4二级指针和二维数组210

练习212

第10章C++语言初步215

10.1对象和结构对象的定义215

10.2提取符和插入符216

10.3运算符重载217

10.4函数重载219

10.5引用220

10.5.1引用概念的由来220

10.5.2引用声明225

10.5.3引用传递和返回引用225

10.6默认参数和默认函数228

练习229

第11章顺序表类230

11.1顺序表类230

11.1.1从C顺序表到C++顺序表类变换232

11.1.2复制赋值和复制构造238

11.1.3修饰词explicit和初始化表241

11.1.4默认构造函数与零元242

11.1.5索引运算符重载243

11.1.6顺序表类头文件245

11.2函数模板247

11.3类模板248

11.4函数模板实例化中的问题252

练习253

第12章String类254

12.1String类雏形254

12.2连接258

12.3插入261

12.4删除263

12.5取子串265

12.6比较267

12.7索引运算符重载268

12.8查找269

12.9String类头文件272

练习276

第13章Date类和面向对象设计277

13.1Date类277

13.1.1雏形277

13.1.2转换赋值278

13.1.3成员转换278

13.1.4提取符和插入符重载279

13.1.5自增自减280

13.1.6取值和赋值282

13.2继承282

13.3多态性和虚函数284

13.4虚析构函数286

13.5纯虚函数和抽象类286

练习289

第14章向量类模板292

14.1迭代器292

14.2向量类模板293

14.3函数对象296

练习299

第15章链表类模板300

15.1链表类模板设计300

15.1.1雏形300

15.1.2迭代器301

15.1.3插入304

15.1.4删除307

15.1.5复制赋值与复制构造310

15.1.6数据首尾元素引用313

15.1.7链表类头文件314

15.2链表逆置318

15.3Josephus问题320

15.4适配器322

15.4.1链栈322

15.4.2链队列323

15.4.3优先级链队列325

15.5事件驱动模拟326

练习336

第16章C++流与文件337

16.1格式化输入输出337

16.1.1标志字337

16.1.2格式化输出函数338

16.1.3操作算子340

16.2文件的读写342

16.2.1字符读写函数343

16.2.2字符串读写函数345

16.2.3格式读写347

16.2.4无格式读写函数348

练习352

第17章命名空间353

17.1命名空间的定义353

17.2using namespace语句354

17.3命名空间的成员355

17.4命名空间的别名357

练习357

第18章二叉树359

18.1二叉树的基本概念359

18.2二叉树的性质360

18.3二叉树的存储361

18.3.1二叉树的顺序存储361

18.3.2二叉树的链式存储361

18.4层次遍历362

18.4.1层次遍历迭代算法362

18.4.2垂直输出二叉树364

18.4.3由顺序存储生成二叉链式存储367

18.5前序遍历368

18.5.1前序遍历递归算法369

18.5.2前序遍历迭代算法374

18.5.3快速排序376

18.6中序遍历380

18.6.1中序遍历递归算法380

18.6.2中序遍历迭代算法386

18.6.3n阶汉诺塔389

18.7后序遍历391

18.7.1后序遍历递归算法391

18.7.2后序遍历迭代算法399

18.7.3复制二叉链表的递归算法403

18.7.4计算二叉树高度403

18.7.5删除二叉链表的递归算法403

18.7.6生成二叉链表的递归算法404

18.8二叉链表头文件405

练习412

第19章堆415

19.1堆类415

19.1.1堆类声明415

19.1.2堆插入416

19.1.3堆删取419

19.1.4堆类头文件423

19.2堆排序425

19.2.1对数组堆排序425

19.2.2堆排序头文件428

19.3哈夫曼树430

19.3.1哈夫曼树定义和算法430

19.3.2哈夫曼结构431

19.3.3哈夫曼编码432

19.3.4哈夫曼译码435

19.3.5哈夫曼结构头文件437

练习440

第20章二叉搜索树441

20.1二叉搜索链表类441

20.1.1类声明441

20.1.2插入442

20.1.3删除444

20.1.4查找和修改447

20.1.5中序迭代器452

20.1.6频率统计455

20.2二叉搜索链表类头文件457

练习463

第21章平衡二叉搜索树464

21.1动态平衡方法464

21.1.1左单旋转型调整464

21.1.2右单旋转型调整466

21.1.3先右后左双旋转型调整467

21.1.4先左后右双旋转型调整469

21.2平衡二叉搜索链表类470

21.2.1类声明470

21.2.2插入471

21.2.3删除474

21.2.4查找和修改477

21.2.5中序迭代器479

21.3平衡二叉搜索链表类头文件479

练习487

第22章树489

22.1树的基本概念和存储489

22.2树类的雏形491

22.3树的广度优先遍历495

22.4树的深度优先遍历497

22.5八皇后499

22.6树类头文件502

练习506

第23章图507

23.1图的基本概念和存储507

23.2图类的雏形509

23.3图的遍历514

23.3.1广度优先遍历514

23.3.2深度优先遍历516

23.4*小生成树518

23.4.1普里姆算法519

23.4.2克鲁斯卡尔算法523

23.5*短路径527

23.6拓扑序列533

23.7关键路径537

23.8迷宫542

23.9图类头文件546

练习559

第24章B树560

24.1线性索引560

24.2静态m路搜索树561

24.3B树562

24.4B+树566

练习567

第25章散列568

25.1散列表568

25.2散列函数569

25.2.1平方取中法569

25.2.2除留余数法570

25.2.3折叠法570

25.2.4数字分析法570

25.3分离链接法571

25.4开放定址法574

25.4.1线性探查法574

25.4.2平方探查法575

25.4.3双散列函数探查法575

第26章性能分析和排序576

26.1性能分析576

26.1.1时间复杂性分析576

26.1.2空间复杂性分析577

26.2插入排序578

26.2.1直接插入排序578

26.2.2折半插入排序580

26.3交换排序581

26.3.1冒泡排序581

26.3.2快速排序583

26.4选择排序584

26.4.1直接选择排序584

26.4.2堆排序585

练习586

附录A命名规则587

附录B基本类型588

B.1整型588

B.2实型589

B.3字符型590

附录C编译预处理592

C.1无参宏指令592

C.2带参宏指令593

C.3条件编译指令594

附录D辗转相除法求*大公约数的证明595

参考文献596