計算機程序設(shè)計藝術(shù)-卷1：基本算法（第3版）

第1章基本概念1 1.1算法.1 1.2數(shù)學(xué)準(zhǔn)備.8 1.2.1數(shù)學(xué)歸納法.8 1.2.2數(shù)、冪和對數(shù)16 1.2.3和與積.21 1.2.4整數(shù)函數(shù)與初等數(shù)論30 1.2.5排列與階乘.35 1.2.6二項式系數(shù).41 1.2.7調(diào)和數(shù).59 1.2.8斐波那契數(shù).62 1.2.9生成函數(shù)69 1.2.10典型算法分析76 *1.2.11漸近表示85 *1.2.11.1大O記號85 *1.2.11.2歐拉求和公式.88 *1.2.11.3若干漸近計算式92 1.3MIX99 1.3.1MIX的描述99 1.3.2MIX匯編語言.116 1.3.3排列的應(yīng)用.131 1.4若干基本程序設(shè)計技術(shù)150 1.4.1子程序.150 1.4.2協(xié)同程序155 1.4.3解釋程序161 1.4.3.1MIX模擬程序.162 *1.4.3.2追蹤程序171 1.4.4輸入與輸出.173 1.4.5歷史和參考文獻.184 第2章信息結(jié)構(gòu)187 2.1引論.187 2.2線性表191 2.2.1棧、隊列和雙端隊列191 2.2.2順序分配195 2.2.3鏈接分配203 2.2.4循環(huán)鏈表217 2.2.5雙鏈表.222 2.2.6數(shù)組與正交表237 2.3樹245 2.3.1遍歷二叉樹.253 2.3.2樹的二叉樹表示.265 2.3.3樹的其他表示276 2.3.4樹的基本數(shù)學(xué)性質(zhì).287 2.3.4.1自由樹.287 2.3.4.2定向樹.294 *2.3.4.3無限性引理.301 *2.3.4.4樹的枚舉304 2.3.4.5路徑長度314 *2.3.4.6歷史和參考文獻320 2.3.5表和垃圾回收322 2.4多鏈結(jié)構(gòu).333 2.5動態(tài)存儲分配.342 2.6歷史和參考文獻358 習(xí)題答案.364 附錄A數(shù)值表494 附錄B記號索引.498 附錄C算法和定理索引.502 人名索引.503 索引.508