編程珠璣

第一部分 基礎
第1章 開篇
1.1 一次友好的對話
1.2 準確的問題描述
1.3 程序設計
1.4 實現概要
1.5 原理
1.6 習題
1.7 深入閱讀
第2章 啊哈！算法
2.1 三個問題
2.2 無處不在的二分搜索
2.3 基本操作的威力
2.4 排序
2.5 原理
2.6 習題
2.7 深入閱讀
2.8 變位詞程序的實現（邊欄）
第3章 數據決定程序結構
3.1 一個調查程序
3.2 格式信函編程
3.3 一組示例
3.4 結構化數據
3.5 用于特殊數據的強大工具
3.6 原理
3.7 習題
3.8 深入閱讀
第4章 編寫正確的程序
4.1 二分搜索的挑戰
4.2 編寫程序
4.3 理解程序
4.4 原理
4.5 程序驗證的角色
4.6 習題
4.7 深入閱讀
第5章 編程小事
5.1 從偽代碼到C程序
5.2 測試工具
5.3 斷言的藝術
5.4 自動測試
5.5 計時
5.6 完整的程序
5.7 原理
5.8 習題
5.9 深入閱讀
5.10 調試（邊欄）
第二部分 性能
第6章 程序性能分析
6.1 實例研究
6.2 設計層面
6.3 原理
6.4 習題
6.5 深入閱讀
第7章 粗略估算
7.1 基本技巧
7.2 性能估計
7.3 安全系數
7.4 Little定律
7.5 原理
7.6 習題
7.7 深入閱讀
7.8 日常生活中的速算（邊欄）
第8章 算法設計技術
8.1 問題及簡單算法
8.2 兩個平方算法
8.3 分治算法
8.4 掃描算法
8.5 實際運行時間
8.6 原理
8.7 習題
8.8 深入閱讀
第9章 代碼調優
9.1 典型的故事
9.2 急救方案集錦
9.3 大手術——二分搜索
9.4 原理
9.5 習題
9.6 深入閱讀
第10章 節省空間
10.1 關鍵在于簡單
10.2 示例問題
10.3 數據空間技術
10.4 代碼空間技術
10.5 原理
10.6 習題
10.7 深入閱讀
10.8 巨大的節省（邊欄）
第三部分 應用
第11章 排序
11.1 插入排序
11.2 一種簡單的快速排序
11.3 更好的幾種快速排序
11.4 原理
11.5 習題
11.6 深入閱讀
第12章 取樣問題
12.1 問題
12.2 一種解決方案
12.3 設計空間
12.4 原理
12.5 習題
12.6 深入閱讀
第13章 搜索
13.1 接口
13.2 線性結構
13.3 二分搜索樹
13.4 用于整數的結構
13.5 原理
13.6 習題
13.7 深入閱讀
13.8 一個實際搜索問題（邊欄）
第14章 堆
14.1 數據結構
14.2 兩個關鍵函數
14.3 優先級隊列
14.4 一種排序算法
14.5 原理
14.6 習題
14.7 深入閱讀
第15章 字符串
15.1 單詞
15.2 短語
15.3 生成文本
15.4 原理
15.5 習題
15.6 深入閱讀
第1版跋
第2版跋
附錄A 算法分類
附錄B 估算測試
附錄C 時空開銷模型
附錄D 代碼調優法則
附錄E 用于搜索的C++類
部分習題提示
部分習題答案
索引

本書作者Jon Bentley是美國著名的程序員和計算機科學家，他于20世紀70年代前後在很有影響力的《ACM通訊》（Communications of the ACM）上以專欄的形式連續發表了一系列短文，成功地總結和提煉了自己在長期的計算機程序設計實踐中積累下來的寶貴經驗。這些短文充滿了真知灼見，而且文筆生動、可讀性強，對于提高職業程序員的專業技能很有幫助，因此該專欄大受讀者歡迎，成為當時該學術期刊的王牌欄目之一。可以想象當時的情形頗似早年金庸先生在《明報》上連載其武俠小說的盛況。後來在ACM的鼓勵下，作者經過仔細修訂和補充整理，對各篇文章的先後次序做了精心編排，分別在1986年和1988年結集出版了Programming Pearls（《編程珠璣》）和More Programming Pearls（《編程珠璣Ⅱ》）這兩本書，二者均成為該領域的名著。《編程珠璣（第2版）》在2000年問世，書中的例子都改用C語言書寫，並多處提到如何用C++和Java中的類來實現。《編程珠璣Ⅱ》雖未再版，例子多以Awk語言寫成，但其語法與C相近，容易看懂。

作者博覽群書，旁征博引，無論是計算機科學的專業名著，如《計箅機程序設計藝術》，還是普通的科普名著，如《啊哈！靈機一動》，都在作者筆下信手拈來、娓娓道出，更不用說隨處可見的作者自己的真知灼見了。如果說《計算機程序設計藝術》這樣的巨著代表了程序員們使用的“坦克和大炮”一類的重型武器，這兩本書則在某種程度上類似于魯迅先生所說的“匕首與投槍”一類的輕型武器，更能滿足職業程序員的日常需要。或者說前者是武俠小說中提高內力修為的根本秘籍，後者是點撥臨陣招數的速成寶典，二者同樣都是克敵制勝的法寶，缺一不可。在無止境地追求精湛技藝這一點上，程序員、數學家和武俠們其實是相通的。

在美國，這兩本書不僅被用作大學低年級數據結構與算法課程的教材，還用作高年級算法課程的輔助教材。例如，美國著名大學麻省理工學院的電氣工程與計算機科學開放式核心課程算法導論就將這兩本書列為推薦讀物。這兩本書覆蓋了大學算法課程和數據結構課程的大部分內容，但是與普通教材的側重點又不一樣，不強調單純從數學上來進行分析的技巧，而是強調結合實際問題來進行分析、應用和實現的技巧，因此可作為大學計算機專業的算法、數據結構、軟件工程等課程的教師參考用書和優秀課外讀物。書中有許多真實的歷史案例和許多極好的練習題以及部分練習題的提示與解答，非常適合自學。正如作者所建議的那樣，閱讀這兩本書時，讀者需要備有紙和筆，最好還有一台計算機在手邊，邊讀邊想、邊想邊做，這樣才能將閱讀這兩本書的收益最大化。

人民郵電出版社引進版權，同時翻譯出版了《編程珠璣（第2版）》和《編程珠璣Ⅱ》，使這兩個中譯本珠聯璧合，相信這不僅能極大地滿足廣大程序員讀者的需求，還有助于提高國內相關課程的授課質量和學生的學習興趣。

本書主要由黃倩和錢麗艷翻譯，劉田審校，翻譯過程中得到了張懷勇先生的幫助，在此表示感謝。由于本書內容深刻，語言精妙，而譯者的水平和時間都比較有限，錯誤和不當之處在所難免，敬請廣大讀者批評指正。