第1章 绪论 1
1．1数据与数据结构 2
1．1．1数据及其类型 2
1．1．2数据结构简介 4
1．2算法 6
1．2．1算法的概念 6
1．2．2算法的分析 8
1．2．3算法的设计 12
1．3 C＋＋语言简介 18
1．3．1 C＋＋的产生与发展 18
1．3．2 C＋＋与面向对象思想 20
1．3．3 C＋＋中的类和对象 23
1．4本章小结 28
第2章 C＋＋编程基础 29
2．1开始C＋＋编程 30
2．1．1输入输出 30
2．1．2预处理 38
2．1．3名字空间 44
2．2深入的类编程 50
2．2．1访问控制 50
2．2．2初始化与清除 53
2．2．3动态创建对象 57
2．2．4友元函数 60
2．2．5拷贝构造函数 61
2．3丰富的C＋＋特性 65
2．3．1常量 65
2．3．2函数重载 68
2．3．3运算符重载 71
2．3．4异常处理 77
2．4代码重用机制 79
2．4．1继承 80
2．4．2多态 87
2．4．3模板 90
2．5标准模板库 93
2．5．1 STL简介 94
2．5．2 STL构成 95
2．5．3 STL的不同版本 97
2．6本章小结 98
第3章 指针、数组与字符串 99
3．1指针 100
3．1．1指针的概念 100
3．1．2指针的语法 102
3．1．3函数与参数传递 103
3．2数组 108
3．2．1数组定义与初始化 109
3．2．2数组与指针 113
3．2．3数组的抽象数据类型 116
3．2．4大整数乘法问题 120
3．2．5荷兰国旗问题 121
3．3字符串 124
3．3．1 C＋＋中的字符串 124
3．3．2字符串抽象数据类型 126
3．3．3字符串的匹配算法 128
3．3．4字符串指数问题 141
3．4动态内存管理 142
3．4．1关键词new和delete 143
3．4．2避免内存错误 146
3．5本章小结 152
第4章 链表 153
4．1单向链表 154
4．1．1单向链表的结构 154
4．1．2单向链表类的实现 155
4．1．3有序链表的合并 162
4．1．4多项式加法问题 163
4．2单向循环链表 164
4．2．1单向循环链表的结构 164
4．2．2单向循环链表类的实现 166
4．2．3约瑟夫问题 169
4．2．4魔术师发牌问题 170
4．2．5拉丁方阵问题 172
4．3双向循环链表 173
4．3．1双向循环链表的结构 173
4．3．2双向循环链表类的实现 174
4．3．3 Vigenere加密问题 182
4．3．4选美比赛问题 184
4．4游标类的设计与实现 186
4．4．1游标类的结构 186
4．4．2游标类的实现 187
4．5 STL与链表 191
4．5．1 STL中链表类的接口 191
4．5．2遍历 194
4．5．3元素的插入与删除 196
4．6本章小结 196
第5章 栈与队列 197
5．1栈 198
5．1．1栈的结构 198
5．1．2栈的实现 199
5．1．3括号匹配问题 203
5．1．4停车场模拟问题 204
5．2队列 208
5．2．1队列的结构 208
5．2．2队列的实现 210
5．2．3舞伴问题 214
5．2．4杨辉三角形问题 215
5．2．5游程编码问题 216
5．3优先级队列 218
5．3．1优先级队列的结构 218
5．3．2优先级队列的实现 220
5．4 STL中的栈与队列 222
5．4．1 STL中的stack 222
5．4．2 STL中的queue 224
5．4．3 STL中的priority_queue 226
5．5本章小结 229
第6章 递归 231
6．1递归的概念 232
6．1．1递归的定义 232
6．1．2应用递归的原则 235
6．1．3递归和非递归的转化 240
6．2分治法 243
6．2．1分治法简述 243
6．2．2汉诺塔问题 244
6．2．3传染病问题 246
6．3回溯法 250
6．3．1回溯法简述 251
6．3．2迷宫问题 251
6．3．3八皇后问题 255
6．3．4骑士周游问题 258
6．4本章小结 265
第7章 树 267
7．1树的概念 268
7．1．1树的定义 268
7．1．2树的术语 271
7．1．3树的抽象数据类型 272
7．2二叉树 273
7．2．1二叉树的定义 273
7．2．2二叉树的性质 275
7．2．3二叉树的实现 276
7．2．4二叉树的遍历 285
7．2．5二叉树的线索化 289
7．3树与森林 291
7．3．1树的存储表示 291
7．3．2树的实现 294
7．3．3树与森林的遍历 298
7．3．4森林与二叉树的转换 300
7．4霍夫曼树 304
7．4．1霍夫曼树的概念 304
7．4．2霍夫曼树的构造方法 305
7．4．3霍夫曼编码及其实现 307
7．5堆 313
7．5．1堆的概念 314
7．5．2堆的建立 314
7．5．3堆的操作 316
7．6基于STL实现树结构 317
7．6．1 STL中的vector 317
7．6．2 STL中的map 321
7．7医院建模问题 323
7．8本章小结 328
第8章 图 329
8．1图的基本概念 330
8．1．1图的定义 330
8．1．2图的术语 331
8．1．3图的运算 334
8．1．4图的抽象数据类型 336
8．2图的存储与表示 337
8．2．1图的邻接矩阵表示 337
8．2．2图的邻接表表示 339
8．2．3两种表示法的比较 342
8．3图的遍历 342
8．3．1欧拉路径与欧拉回路 343
8．3．2哈密尔顿路径与哈密尔顿回路 345
8．3．3广度优先遍历 346
8．3．4深度优先遍历 349
8．4最短路径问题 353
8．4．1固定起点最短路问题 353
8．4．2非固定起点最短路问题 355
8．4．3最短路径的动态规划解法 358
8．4．4旅游交通路线问题 364
8．5最小生成树 372
8．5．1最小生成树的定义 372
8．5．2克鲁斯卡尔算法 373
8．5．3普里姆算法 375
8．6经典问题举例 379
8．6．1文字游戏问题 380
8．6．2道路修建问题 382
8．6．3回家路线问题 385
8．6．4水塘计算问题 387
8．6．5棍子还原问题 389
8．7本章小结 392
第9章 树形搜索结构 393
9．1二叉搜索树 394
9．1．1二叉搜索树的概念 394
9．1．2二叉搜索树的操作 395
9．1．3二叉搜索树的实现 397
9．1．4二叉搜索树的分析 400
9．2 AVL树 403
9．2．1 AVL树的概念 404
9．2．2 AVL树的旋转 405
9．2．3 AVL树的实现 410
9．3红黑树 418
9．3．1红黑树的概念 418
9．3．2红黑树的操作 421
9．3．3红黑树的实现 428
9．4 Trie树 433
9．4．1 Trie树的概念 433
9．4．2 Trie树的表示 434
9．4．3 Trie树的实现 435
9．5本章小结 439
第10章 集合与字典 441
10．1集合论基础 442
10．1．1集合的概念 442
10．1．2集合的运算 444
10．2集合的实现 445
10．2．1位向量集合 445
10．2．2链表集合 451
10．3字典 460
10．3．1字典的概念 461
10．3．2搜索运算 463
10．4散列 467
10．4．1散列的概念 467
10．4．2散列函数 469
10．4．3处理散列冲突 471
10．4．4散列的应用 475
10．5经典问题举例 476
10．5．1拼写检查问题 476
10．5．2无线网络问题 485
10．5．3第K个数问题 488
10．6 STL中的set 490
10．7本章小结 493
第11章 排序 495
11．1排序问题概述 496
11．1．1基本概念和定义 496
11．1．2排序算法的分类 497
11．1．3排序算法分析与选择 497
11．2插入排序 498
11．2．1直接插入排序 498
11．2．2二分法插入排序 501
11．2．3希尔排序 503
11．3选择排序 506
11．3．1直接选择排序 506
11．3．2堆排序 508
11．4交换排序 512
11．4．1冒泡法排序 512
11．4．2 Shaker排序 514
11．4．3快速排序 517
11．5归并排序 522
11．6计数排序 526
11．7本章小结 531
参考文献 532