第1章 结构和类 1
1.1结构 1
1.2类的基本概念 6
1.3类的实现 9
1.4类的测试 17
1.5将函数定义放在类定义中 18
1.6类的注释 20
1.7结构和类之间的区别 21
1.8小结 21
1.9练习 22
第2章 重载运算符、类模板和抽象 25
2.1重载运算符 25
2.2在Checkbook类中使用Check结构 31
2.3类模板 34
2.4类和抽象 42
2.5小结 45
2.6练习 45
第3章 类的更多内容 51
3.1 const限定符 51
3.2构造函数 53
3.3类的修改 57
3.4修改Checkbook类保存支票历史记录 57
3.5小结 67
3.6练习 68
第4章 指针和动态数组 69
4.1指针 69
4.2[]运算符 75
4.3动态分配内存 77
4.4动态数组 79
4.5 delete操作符 80
4.6对象指针 83
4.7堆内存耗尽 84
4.8可调数组 86
4.9小结 88
4.10练习 89
第5章 Array类 93
5.1 Array类模板 93
5.2使用Array类 103
5.3析构函数 106
5.4复制构造函数 107
5.5重载赋值运算符函数 113
5.6示例 118
5.7 Array类的优缺点 121
5.8标准模板库 122
5.9小结 122
5.10练习 123
第6章 面向对象编程简介 125
6.1组合 125
6.2继承 129
6.3多态 137
6.4小结 144
6.5练习 144
第7章 生成数据结构的方法 147
7.1在数据结构中使用数组 147
7.2链式结构简介 151
7.3链表编码 153
7.3.1链表代码基础 153
7.3.2在链表中搜索一个肯定存在的值 154
7.3.3在链表中搜索可能不存在的值 157
7.3.4在链表的表头插入一个结点 159
7.3.5在链表中间插入一个结点 161
7.3.6从链表中删除一个包含链表中某个值的结点 164
7.3.7使用header结点简化代码 166
7.3.8删除找到包含某值的结点 166
7.4数组和链表的对比 167
7.4.1数组和链表在速度上的比较 167
7.4.2数组和链表在内存浪费上的比较 168
7.4.3浪费内存分析 171
7.5小结 174
7.6练习 175
第8章 栈和队列 177
8.1栈ADT 177
8.2栈的数组实现 178
8.3栈的链表实现 184
8.4队列ADT 184
8.5队列的链表实现 184
8.6队列的其他链表实现 193
8.7队列的数组实现 194
8.8小结 202
8.9练习 202
第9章 时间复杂度简介 211
9.1时间复杂度基础 213
9.2常量阶时间复杂度 222
9.3大O表示法 223
9.4对数阶时间复杂度 224
9.5折半搜索算法 227
9.6计算机速度:它来源于什么地方 231
9.7数据结构函数的时间复杂度 232
9.8数组扩展和收缩的平摊分析 232
9.9小结 236
9.10练习 237
第10章 链表作为数据结构 239
10.1列表ADT 239
10.2在信息记录中使用关键码值 240
10.3链表实现 240
10.3.1链表说明文件 241
10.3.2链表实现文件 244
10.4其他实现 255
10.5小结 259
10.6练习 260
第11章 散列表 263
11.1散列表ADT 263
11.2散列函数和散列表设计 263
11.3散列表的实现问题 269
11.4函数指针 271
11.5散列表实现 272
11.6使用散列表实现 277
11.7双向链表的散列表实现 279
11.7.1实现问题 283
11.7.2 DoublyLinkedList类的说明文件 284
11.7.3 DoublyLinkedList类的实现文件 287
11.8小结 297
11.9练习 297
第12章 优先级队列、树和堆 299
12.1优先级队列ADT 299
12.2优先级队列设计 299
12.3树 301
12.4堆 306
12.5使用单赋值交换 314
12.6优先级队列的堆实现(基于数组) 316
12.7链(内嵌)堆设计 324
12.8优先级队列的链(内嵌)堆实现 329
12.9小结 336
12.10练习 337
第13章 递归 339
13.1递归阶乘函数 339
13.2递归函数编写原则 344
13.3在链式结构上使用递归 345
13.4递归函数的时间复杂度 348
13.5小结 348
13.6练习 349
第14章 排序算法简介 351
14.1堆排序 351
14.2插入排序 353
14.3快速排序 358
14.4统计排序 361
14.5链表排序 364
14.6小结 366
14.7练习 367
第15章 其他数据结构 369
15.1二叉搜索树 369
15.2 BST和其他数据结构的对比 380
15.3图 382
15.4邻接矩阵和邻接表之间的对比 391
15.5小结 393
15.6练习 394
附录A 如何编译及使用多文件程序 397
A.1 Microsoft Visual Studio 2005 C++编译器 397
A.2编译和运行使用类的代码(不是类模板) 397
A.3编译和运行使用类模板的代码 398
A.4使用Microsoft Visual Studio 2005编写代码 399
A.5在Microsoft Visual Studio 2005中打开一个已创建的项目 400
A.6何种情况下事情会变乱 400
A.7 UNIX编译器 401