计算机程序设计艺术 卷1:基本算法(英文版·第3版)

目录

第 1章 基本概念 1
1．1算法 1
1．2数学准备 10
1．2．1数学归纳法 11
1．2．2数、幂和对数 21
1．2．3和与积 27
1．2．4整数函数与初等数论 39
1．2．5排列与阶乘 45
1．2．6二项式系数 52
1．2．7调和数 75
1．2．8斐波那契数 79
1．2．9生成函数 87
1．2．10典型算法分析 96
*1．2．11渐近表示 107
*1．2．11．1大O记号 107
*1．2．11．2欧拉求和公式 111
*1．2．11．3若干渐近计算式 116
1．3 MIX 124
1．3．1 MIX的描述 124
1．3．2 MIX汇编语言 144
1．3．3排列的应用 164
1．4若干基本程序设计技术 186
1．4．1子程序 186
1．4．2协同程序 193
1．4．3解释程序 200
1．4．3．1 MIX模拟程序 202
*1．4．3．2追踪程序 212
1．4．4输入与输出 215
1．4．5历史和参考文献 229
第 2章 信息结构 232
2．1引论 232
2．2线性表 238
2．2．1栈、队列和双端队列 238
2．2．2顺序分配 244
2．2．3链接分配 254
2．2．4循环链表 273
2．2．5双向链表 280
2．2．6数组与正交表 298
2．3树 208
2．3．1遍历二叉树 318
2．3．2树的二叉树表示 334
2．3．3树的其他表示 348
2．3．4树的基本数学性质 362
2．3．4．1自由树 363
2．3．4．2定向树 372
*2．3．4．3无限性引理 382
*2．3．4．4树的枚举 386
2．3．4．5路径长度 399
*2．3．4．6历史和参考文献 406
2．3．5表和垃圾回收 408
2．4多链结构 424
2．5动态存储分配 435
2．6历史和参考文献 457
习题答案 466
附录A数值表 619
附录B记号索引 623
附录C算法和定理索引 628


CONTENTS

Chapter 1　Basic Concepts　1
1．1　Algorithms　1
1．2　Mathematical Preliminaries　10
1．2．1　Mathematical Induction　11
1．2．2　Numbers， Powers， and Logarithms　21
1．2．3　Sums and Products　27
1．2．4　Integer Functions and Elementary Number Theory　39
1．2．5　Permutations and Factorials　45
1．2．6　Binomial Coefficients　52
1．2．7　Harmonic Numbers　75
1．2．8　Fibonacci Numbers　79
1．2．9　Generating Functions　87
1．2．10　Analysis of an Algorithm　96
*1．2．11　Asymptotic Representations　107
*1．2．11．1　The O-notation　107
*1．2．11．2　Euler's summation formula　111
*1．2．11．3　Some asymptotic calculations　116
1．3　MIX　124
1．3．1　Description of MIX　124
1．3．2　The NIX Assembly Language　144
1．3．3　Applications to Permutations　164
1．4　Some Fundamental Programming Techniques　180
1．4．1　Subroutines　180
1．4．2　Coroutines　193
1．4．3　Interpretive Routines　200
1．4．3．1　A NIX simulator　202
*1．4．3．2　Trace routines　212
1．4．4　Input and Output　215
1．4．5　History and Bibliography　229

Chapter 2　Information Structures　232
2．1　Introduction　232
2．2　Linear Lists　238
2．2．1　Stacks， Queues， and Deques　238
2．2．2　Sequential Allocation　244
2．2．3　Linked Allocation　254
2．2．4　Circular Lists　273
2．2．5　Doubly Linked Lists　280
2．2．6　Arrays and Orthogonal Lists　298
2．3　Trees　308
2．3．1　Traversing Binary Trees　318
2．3．2　Binary Tree Representation of Trees　334
2．3．3　Other Representations of Trees　348
2．3．4　Basic Mathematical Properties of Trees　362
2．3．4．1　Free trees　363
2．3．4．2　Oriented trees　372
*2．3．4．3　The "infinity lemma"　382
*2．3．4．4　Enumeration of trees　386
2．3．4．5　Path length　399
*2．3．4．6　History and bibliography　406
2．3．5　Lists and Garbage Collection　408
2．4　Multilinked Structures　424
2．5　Dynamic Storage Allocation　435
2．6　History and Bibliography　457

Answers to Exercises　466

Appendix A　Tables of Numerical Quantities　619
1． Fundamental Constants (decimal)　619
2． Fundamental Constants (octal)　620
3． Harmonic Numbers， Bernoulli Numbers， Fibonacci Numbers　621

Appendix B　Index to Notations　623

Index and Glossary　628