译者序
前　言
致　谢
第1章　编程基础1
1.1　变量1
1.2　数据类型1
1.3　数据结构2
1.4　抽象数据类型3
1.5　内存与变量3
1.6　指针4
1.6.1　指针的声明4
1.6.2　指针的使用5
1.6.3　指针的操纵6
1.6.4　数组与指针7
1.6.5　动态内存分配7
1.6.6　函数指针7
1.7　参数传递的方式8
1.7.1　实际参数与形式参数8
1.7.2　参数传递的语义8
1.7.3　各种编程语言所支持的参数传递方式9
1.7.4　按值传递9
1.7.5　按结果传递10
1.7.6　有可能发生的参数冲突10
1.7.7　按值-结果传递11
1.7.8　按引用传递（别名机制）11
1.7.9　按名称传递12
1.8　绑定12
1.8.1　静态绑定（前期绑定）13
1.8.2　动态绑定（后期绑定）13
1.9　作用域13
1.9.1　静态作用域13
1.9.2　动态作用域14
1.10　存储类别15
1.10.1　存储类别为auto的变量15
1.10.2　存储类别为extern的变量16
1.10.3　存储类别为register的变量18
1.10.4　存储类别为static的变量19
1.11　存储空间的安排19
1.12　编程方式22
1.12.1　无结构的编程22
1.12.2　过程式的编程22
1.12.3　模块式的编程22
1.12.4　面向对象的编程23
1.13　面向对象编程的基本概念23
1.13.1　类与对象24
1.13.2　封装24
1.13.3　抽象25
1.13.4　数据隐藏25
1.13.5　多态25
1.13.6　继承26
1.13.7　继承的类型26
1.13.8　动态绑定27
1.13.9　消息传递28
第2章　脚本语言83
2.1　解释器与编译器83
2.1.1　编译器83
2.1.2　解释器84
2.1.3　编译器与解释器的区别84
2.2　什么是脚本语言84
2.3　shell脚本编程85
2.3.1　命令的重定向与管道85
2.3.2　变量86
2.3.3　命令行参数87
2.3.4　命令替换88
2.3.5　算术扩展88
2.3.6　控制结构88
2.3.7　函数92
2.4　Perl94
2.4.1　从“Hello world!”程序开始94
2.4.2　Perl的命令行参数95
2.4.3　Perl的数据类型与变量95
2.4.4　引用98
2.4.5　声明变量98
2.4.6　变量的作用域99
2.4.7　字符串字面量99
2.4.8　Perl的标准输入端100
2.4.9　Perl语言的运算符101
2.4.10　条件语句110
2.4.11　循环113
2.4.12　子例程115
2.4.13　字符串操作117
2.4.14　包/模块118
2.5　Python118
2.5.1　什么是Python118
2.5.2　布尔类型119
2.5.3　整数119
2.5.4　字符串119
2.5.5　列表与元组121
2.5.6　函数122
2.5.7　把代码包装成模块123
第3章　与设计有关的面试题124
3.1　术语介绍124
3.2　技巧125
3.3　可供练习的其他设计问题179
第4章　操作系统的概念180
4.1　术语介绍180
4.2　与操作系统概念有关的问题183
第5章　计算机网络的基础知识188
5.1　介绍188
5.2　局域网与广域网188
5.3　数据包分割与多路复用189
5.4　终端设备190
5.5　中介设备190
5.6　集线器、交换机与路由器的定义191
5.7　介质192
5.8　端对端网络与客户端/服务器网络192
5.9　互联网是如何运作的193
5.10　OSI模型与TCP/IP模型的区别196
5.11　客户端/服务器结构与互联网197
5.12　ARP与RARP198
5.13　子网199
5.14　路由器的工作原理200
5.15　单播、广播、多播201
5.16　tracert/traceroute及ping命令的工作原理202
5.17　什么是QoS203
第6章　数据库概念204
6.1　术语介绍204
6.2　与数据库概念有关的问题206
第7章　智力题213
7.1　智力题213
第8章　算法介绍217
8.1　什么是算法217
8.2　为什么要做算法分析218
8.3　算法分析的目标218
8.4　什么是运行时间分析218
8.5　怎样对比不同的算法218
8.6　什么是增长率219
8.7　几种常见的增长形式219
8.8　算法分析的类型220
8.9　渐近表示法221
8.10　大O表示法221
8.11　大Ω表示法222
8.12　大Θ表示法223
8.13　算法分析为什么又叫渐近分析225
8.14　渐近分析指南225
8.15　三种表示法的性质227
8.16　常用的对数公式与求和公式227
8.17　分治算法的主定理227
8.18　与分治算法的主定理有关的问题228
8.19　递减式递推（减而治之）算法的主定理229
8.20　另一种递减式递推（减而治之）算法的主定理229
8.21　与算法分析有关的问题230
第9章　递归与回溯240
9.1　介绍240
9.2　什么是递归240
9.3　为什么要用递归的办法解决问题240
9.4　递归函数的格式241
9.5　演示递归调用时的内存占用情况241
9.6　递归与迭代242
9.7　运用递归时的注意事项243
9.8　递归算法举例243
9.9　与递归有关的问题243
9.10　什么是回溯245
9.11　回溯算法举例245
9.12　与回溯有关的问题245
第10章　链表248
10.1　什么是链表248
10.2　将链表用作抽象的数据类型248
10.3　为什么要用链表249
10.4　数组概述249
10.5　比较链表、数组与动态数组250
10.6　单链表251
10.7　双链表256
10.8　循环链表261
10.9　节省内存的双链表266
10.10　松散链表268
10.11　跳跃链表273
10.12　与链表有关的问题276
第11章　栈295
11.1　什么是栈295
11.2　怎样使用栈296
11.3　将栈用作抽象数据类型296
11.4　栈的运用296
11.5　实现297
11.6　对比各种实现方式302
11.7　与栈有关的问题303
第12章　队列324
12.1　什么是队列324
12.2　如何使用队列324
12.3　将队列用作抽象数据类型325
12.4　异常325
12.5　运用325
12.6　实现326
12.7　与队列有关的问题331
第13章　树337
13.1　什么是树337
13.2　术语表337
13.3　二叉树339
13.4　二叉树的类型339
13.5　二叉树的性质340
13.6　遍历二叉树342
13.7　泛化树（N叉树）362
13.8　通过线索二叉树来遍历369
13.9　表达式树376
13.10　异或树379
13.11　二叉搜索树380
13.12　平衡二叉搜索树395
13.13　AVL树396
13.14　其他形式的树413
13.14.1　红黑树413
13.14.2　伸展树414
13.14.3　扩充树（增强树）414
13.14.4　区间树（区段树）415
13.14.5　替罪羊树416
第14章　优先级队列与堆418
14.1　什么是优先级队列418
14.2　将优先级队列用作抽象数据结构418
14.3　运用419
14.4　实现419
14.5　堆与二叉堆420
14.6　二叉堆421
14.7　与优先级队列和堆有关的问题428
第15章　图算法442
15.1　介绍442
15.2　术语表442
15.3　图的运用446
15.4　将图用作抽象的数据结构446
15.4.1　邻接矩阵446
15.4.2　邻接列表447
15.4.3　邻接集合449
15.4.4　表示图的方法的对比449
15.5　图的遍历449
15.5.1　深度优先搜索（DFS）450
15.5.2　广度优先搜索（BFS）454
15.5.3　对比DFS与BFS456
15.6　拓扑排序457
15.7　最短路径算法458
15.8　最小生成树465
15.9　与图算法有关的问题469
第16章　排序475
16.1　什么是排序475
16.2　为什么要排序475
16.3　排序算法的分类方式475
16.3.1　按照比较的次数来分类475
16.3.2　按照交换操作的次数来分类476
16.3.3　按照内存使用量来分类476
16.3.4　按照是否递归来分类476
16.3.5　按照是否稳定来分类476
16.3.6　按照适应性来分类476
16.4　其他的分类方式476
16.5　冒泡排序477
16.6　选择排序478
16.7　插入排序479
16.8　希尔排序481
16.9　归并排序483
16.10　堆排序485
16.11　快速排序485
16.12　树排序488
16.13　线性时间的排序算法489
16.14　计数排序489
16.15　桶排序490
16.16　基数排序490
16.17　拓扑排序491
16.18　外部排序491
16.19　与排序有关的问题492
第17章　搜索500
17.1　什么是搜索500
17.2　为什么要搜索500
17.3　各种类型的搜索500
17.4　在无序的数据中执行线性搜索501
17.5　在已经排好序/有序的数组中执行线性搜索501
17.6　二分搜索501
17.7　对比几种基本的搜索算法502
17.8　符号表与哈希502
17.9　字符串搜索算法502
17.10　与搜索有关的问题503
第18章　选择算法530
18.1　什么是选择算法530
18.2　通过排序来选择530
18.3　基于分区的选择算法531
18.4　线性选择算法—中位数的中位数算法531
18.5　把最小的k个元素找出来531
18.6　与选择算法有关的问题531
第19章　符号表541
19.1　介绍541
19.2　什么是符号表541
19.3　实现符号表542
19.4　比较实现符号表的各种方式543
第20章　哈希544
20.1　什么是哈希544
20.2　为什么要使用哈希544
20.3　将哈希表用作抽象数据结构544
20.4　哈希技术的原理545
20.5　哈希技术的组成要素546
20.6　哈希表546
20.7　哈希函数547
20.8　负载因子547
20.9　冲突547
20.10　冲突解决技术548
20.11　单独链接法548
20.12　开放定址548
20.12.1　线性探测548
20.12.2　二次探测549
20.12.3　二次哈希550
20.13　比较各种冲突解决技术550
20.14　哈希技术如何把复杂度降为O(1)551
20.15　哈希技术551
20.16　哪些问题不适合用哈希表解决551
20.17　Bloom过滤器552
20.17.1　工作原理552
20.17.2　选择合适的哈希函数553
20.17.3　设置长度合适的位向量553
20.17.4　空间方面的优势553
20.17.5　时间方面的优势554
20.17.6　实现554
20.18　与哈希有关的问题554
第21章　字符串算法565
21.1　介绍565
21.2　字符串匹配算法565
21.3　蛮力法566
21.4　Rabin-Karp字符串匹配算法566
21.5　用有限状态机来实现字符串匹配算法567
21.5.1　状态机的运作过程568
21.5.2　构建有限状态机时的注意事项568
21.5.3　匹配算法568
21.6　KMP算法569
21.6.1　前缀表569
21.6.2　匹配算法571
21.7　Boyce-Moore算法573
21.8　适合用来保存字符串的数据结构573
21.9　用哈希表来保存字符串574
21.10　用二叉搜索树来存放字符串574
21.11　前缀树574
21.11.1　什么是前缀树574
21.11.2　为什么要使用前缀树575
21.11.3　声明前缀树575
21.11.4　向前缀树中插入字符串576
21.11.5　在前缀树中查找字符串576
21.11.6　用前缀树来表示字符串有什么缺点577
21.12　三元搜索树577
21.12.1　声明三元搜索树577
21.12.2　向三元搜索树中插入字符串578
21.12.3　在三元搜索树中查找字符串580
21.12.4　显示三元搜索树中的全部字符串580
21.12.5　在三元搜索树中查找最长的字符串581
21.13　比较二叉搜索树、前缀树及三元搜索树581
21.14　后缀树581
21.14.1　前缀与后缀582
21.14.2　规律582
21.14.3　什么是后缀树582
21.14.4　构建后缀树582
21.14.5　运用后缀树585
21.15　与字符串有关的问题585
第22章　算法设计技巧591
22.1　介绍591
22.2　分类591
22.3　按实现方式分类591
22.3.1　递归算法与迭代算法591
22.3.2　过程式算法与声明式（非过程式）算法592
22.3.3　串行算法、并行算法、分布式算法592
22.3.4　确定性的算法与非确定性的算法592
22.3.5　精确算法与近似算法592
22.4　按设计方式分类592
22.4.1　贪婪算法592
22.4.2　分治算法593
22.4.3　动态规划算法593
22.4.4　线性规划算法593
22.4.5　归约（转化并治理）算法593
22.5　其他分类方式594
22.5.1　按研究领域划分594
22.5.2　按复杂程度划分594
22.5.3　随机化的算法594
22.5.4　分支定界与回溯594
第23章　贪婪算法595
23.1　介绍595
23.2　贪婪算法的策略595
23.3　哪些问题适合用贪婪算法求解595
23.4　贪婪算法是否能应对所有的问题596
23.5　贪婪算法的优点与缺点596
23.6　可以运用贪婪算法的场合596
23.7　理解贪婪算法596
23.8　与贪婪算法有关的问题599
第24章　分治算法606
24.1　介绍606
24.2　什么是分治策略606
24.3　分治技术是否能用来解决所有的问题606
24.4　用示意图来说明分治技术607
24.5　理解分治技术607
24.6　分治技术的优点608
24.7　分治技术的缺点608
24.8　分治算法的主定理609
24.9　分治算法的适用场合609
24.10　与分治技术有关的问题609
第25章　动态规划623
25.1　介绍623
25.2　什么是动态规划策略623
25.3　什么样的问题适合用动态规划来解决624
25.4　动态规划技术能否应对所有的问题624
25.5　动态规划的方式624
25.5.1　自下而上的动态规划624
25.5.2　自上而下的动态规划624
25.5.3　两种规划方向的对比624
25.6　动态规划算法示例625
25.7　理解动态规划625
25.7.1　斐波那契数列625
25.7.2　求某数的阶乘627
25.7.3　最长的公共子序列628
25.8　与动态规划有关的问题631
第26章　复杂度类668
26.1　介绍668
26.2　多项式时间/指数时间669
26.3　什么是判定性问题669
26.4　判定过程669
26.5　什么是复杂度类669
26.6　复杂度类的类型669
26.6.1　P类669
26.6.2　NP类670
26.6.3　反NP类670
26.6.4　P、NP与反NP之间的关系670
26.6.5　NP困难类670
26.6.6　NP完全类671
26.6.7　P、NP、反NP、NP困难与NP完全之间的关系671
26.6.8　P是否等于NP671
26.7　归约672
第27章　其他概念675
27.1　介绍675
27.2　与位运算有关的技巧675
27.2.1　按位与675
27.2.2　按位或675
27.2.3　按位异或676
27.2.4　左移位676
27.2.5　右移位676
27.2.6　按位取反676
27.2.7　判断第K个二进制位有没有设置（或者说是不是1）676
27.2.8　设置第K个二进制位（也就是将其设为1）677
27.2.9　清除第K个二进制位（也就是将其设为0）677
27.2.10　切换第K个二进制位677
27.2.11　把值为1且最靠右的二进制位设置成0677
27.2.12　把值为1且最靠右的二进制位标出来677
27.2.13　把值为0且最靠右的二进制位标出来678
27.2.14　判断某数是不是2的幂678
27.2.15　与2的幂相乘678
27.2.16　与2的幂相除678
27.2.17　求出与2的幂相除的余数678
27.2.18　将二进制表示形式反转678
27.2.19　统计值为1的二进制位个数679
27.2.20　创建掩码，以便将尾部连续出现的0标注出来680
27.2.21　把奇数位置上的二进制位与偶数位置上的二进制位互换680
27.2.22　用不做除法的方式来求平均值680
27.3　其他编程问题680
第28章　非技术问题686
28.1　面试技巧686
28.2　非技术问题举例688