数据结构学习指导与习题解答 C++语言版PDF电子书下载

第1章　C＋＋复习 1

1.1 标准C＋＋程序设计语言 1

1.2　条件语句 3

1.3　运算符 5

1.4　迭代 8

1.5 函数 10

1.6　字符串 12

1.7　文件 14

复习题 15

练习题 16

复习题答案 18

练习题答案 20

第2章　指针与数组 32

2.1 指针 32

2.2　派生类型 34

2.3 引用 35

2.4　按引用传递 35

2.5　空指针异常 37

2.6　new和delete运算符 38

2.7　数组 39

2.8　动态数组 40

2.9　把数组传递给函数 41

2.10　多维数组 42

复习题 43

练习题 44

复习题答案 46

练习题答案 47

第3章　类 60

3.1　Point类 60

3.2　实例、隐式形参和this指针 63

3.3　编译类及其客户程序 64

3.4　友元函数 68

3.5　Line类 68

3.6　用于随机数的类 71

3.7　静态成员 73

3.8　复合 75

3.9　继承 78

复习题 81

练习题 82

复习题答案 85

练习题答案 87

第4章　递归 98

4.1 阶乘函数 98

4.2　跟踪递归调用 99

4.3　斐波纳契数列 99

4.4　二项式系数 101

4.5　欧几里得算法 102

4.6　正确性的归纳证明 103

4.7　递归算法的复杂度分析 104

4.8　动态程序设计 105

4.9　汉诺塔 105

4.10　相互递归 107

复习题 108

练习题 108

复习题答案 110

练习题答案 111

第5章　栈 119

5.1　stack接口 119

5.2　使用stack对象 119

5.3　栈的应用 121

5.4　消除递归 124

5.5　连续实现 126

5.6　链表实现 129

复习题 133

练习题 134

复习题答案 135

练习题答案 136

第6章　队列 142

6.1 queue接口 142

6.2　使用queue对象 142

6.3 队列的应用 144

6.4　连续实现 149

6.5 链表实现 153

复习题 155

练习题 156

复习题答案 157

练习题答案 157

第7章　链表 164

7.1　list接口 164

7.2　使用list对象 165

7.3　迭代器 166

7.4　应用 168

7.5　循环链表 173

7.6　有序链表 176

7.7　不受限制的Integer类 177

7.8　List类的实现 183

复习题 188

练习题 189

复习题答案 191

练习题答案 192

第8章　表 200

8.1　标准的pair类型 200

8.2　使用map类模板的应用 202

8.3　散列表 207

8.4　散列函数 212

8.5　单独串接 215

复习题 219

练习题 219

复习题答案 219

练习题答案 220

第9章　树 224

9.1　树的术语 224

9.2　决策树和转换图 226

9.3　树遍历算法 230

9.4　Tree类的接口 231

9.5　Tree类的实现 234

复习题 238

练习题 240

复习题答案 244

练习题答案 245

第10章　二叉树 259

10.1　定义 259

10.2　统计二叉树 261

10.3　完整二叉树 262

10.4　恒等、相等和同构 263

10.5　完全二叉树 264

10.6　树遍历 266

10.7　表达式树 268

10.8　森林 270

10.9　BinaryTree类的接口 271

10.10　BinaryTree类的实现 274

复习题 278

练习题 279

复习题答案 282

练习题答案 283

第11章　查找树 291

11.1　二叉查找树 291

11.2　二叉查找树的实现 293

11.3　二叉查找树的性能特征 296

11.4　AVL树 297

复习题 300

练习题 300

复习题答案 301

练习题答案 301

第12章　堆和优先级队列 305

12.1 堆 305

12.2 自然映射 305

12.3　插入到堆中 307

12.4　从堆中删除 308

12.5　优先级队列 309

12.6　使用priority_queue对象 309

12.7　使用堆实现PriorityQueue类模板 311

12.8　优先级队列的实现 313

复习题 318

练习题 318

复习题答案 319

练习题答案 319

第13章　排序 322

13.1　基础知识 322

13.2　冒泡排序 323

13.3　选择排序 324

13.4　插入排序 325

13.5　归并排序 327

13.6　快速排序 330

13.7　堆 331

13.8　堆排序 332

13.9　希尔排序 337

13.10　比较排序的速度限制 338

复习题 338

练习题 338

复习题答案 340

练习题答案 340

附录A　参考资料 344

附录B　必要的数学知识 353

B.1 下取整函数和上取整函数 353

B.2　对数 353

B.3　数学归纳法的第一定律 354

B.4　数学归纳法的第二定律 355

B.5　几何级数 356

B.6　求和公式 357

B.7　渐近复杂度等级 357

B.8　调和数 358

B.9　斯特灵公式 360

B.10　斐波纳契数字 361

B.11 黄金分割率 361

B.12　欧几里得算法 363

附录C　标准容器类 365

C.1 vector类模板 365

C.2　deque类模板 372

C.3　stack类模板 372

C.4　queue类模板 372

C.5　priority_queue类模板 373

C.6　list类模板 374

C.7　map类模板 377

C.8　set类模板 379

附录D　泛型算法 382

附录E　示例类 417

E.1 BinaryTree类 417

E.2　BinarySearchTree类 425

E.3　Card类 427

E.4　Concordance类 430

E.5　Date类 432

E.6　Deck类 440

E.7　Hand类 441

E.8　Hash函数结构模板 442

E.9　HashTable类模板 442

E.10　Line类 445

E.11　List类模板 447

E.12　Matrix类模板 454

E.13　OrderedList类 456

E.14　Person类 456

E.15　Point类 460

E.16　Polynomial类 463

E.17　PriorityQueue类模板 470

E.18　Purse类 472

E.19　Queue类 474

E.20　Random类 476

E.21　RandomLine类 477

E.22　RandomPoint类 477

E.23　Ratio类 478

E.24　Rational类 481

E.25　SelfOrganizingList类 484

E.26　Stack类模板 484

E.27　Tree类 486