編程珠璣(第2版 修訂版)pdf

2019年6月16日23:27:30 評論 54
摘要

在書中,作者選取許多具有典型意義的復雜編程和算法問題,生動描繪了歷史上眾大師們在探索解決方案中發生的軼事、走過的彎路和不斷精益求精的歷程,引導讀者像真正的程序員和軟件工程師那樣富于創新性地思考,并透徹闡述和總結了許多獨特而精妙的設計原則、思考和解決問題的方法以及實用程序設計技巧。解決方案的代碼均以C/C++語言編寫,不僅有趣,而且有很大的實戰示范意義。每章后所附習題極具挑戰性和啟發性,書末給出了簡潔的解答。

編程珠璣(第2版 修訂版) 內容簡介

《編程珠璣(第2版·修訂版)》是計算機科學方面的經典名著。書的內容圍繞程序設計人員面對的一系列實際問題展開。作者JonBentley以其獨有的洞察力和創造力,引導讀者理解這些問題并學會解決方法,而這些正是程序員實際編程生涯中至關重要的。本書的特色是通過一些精心設計的有趣而又頗具指導意義的程序,對實用程序設計技巧及基本設計原則進行了透徹而睿智的描述,為復雜的編程問題提供了清晰而完備的解決思路。《編程珠璣(第2版·修訂版)》對各個層次的程序員都具有很高的閱讀價值。

編程珠璣(第2版 修訂版) 目錄

第一部分 基礎

第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++類

部分習題提示

部分習題答案

索引

編程珠璣(第2版 修訂版) 精彩文摘

這一部分的5章回顧程序設計的基礎知識。第1章介紹一個問題的歷史,我們把仔細的問題定義和直接的程序設計技術結合起來,得到優美的解決方案。這一章揭示了本書的中心思想:對實例研究的深入思考不僅很有趣,而且可以獲得實際的益處。

第2章討論3個問題,其中重點強調了如何由算法的融會貫通獲得簡單而高效的代碼。第3章總結數據結構在軟件設計中所起到的關鍵作用。

第4章介紹一個編寫正確代碼的工具——程序驗證。在第9章、第11章和第14章中生成復雜(且快速)的函數時,大量使用了程序驗證技術。第5章講述如何把這些抽象的程序變成實際代碼:使用腳手架程序來探測函數,用測試用例來測試函數并度量函數的性能。

本部分內容

第1章 開篇

第2章 啊哈!算法

第3章 數據決定程序結構

第4章 編寫正確的程序

第5章 編程小事

一位程序員曾問我一個很簡單的問題:“怎樣給一個磁盤文件排序?”想當年我是一上來就犯了錯誤,現在,在講這個故事之前,先給大家一個機會,看看能否比我當年做得更好。你會怎樣回答上述問題呢?

我錯就錯在馬上回答了這個問題。我告訴他一些有關如何在磁盤上實現歸并排序的簡要思路。我建議他深入研究算法教材,他似乎不太感冒。他更關心如何解決這個問題,而不是深入學習。于是我告訴他在一本流行的程序設計書里有磁盤排序的程序。那個程序有大約200行代碼和十幾個函數,我估計他很多需要一周時間來實現和測試該代碼。

我以為已經解決了他的問題,但是他的躊躇使我返回到了正確的軌道上。其后就有了下面的對話,楷體部分是我的問題。

為什么非要自己編寫排序程序呢?為什么不用系統提供的排序功能呢?

我需要在一個大系統中排序。由于不明的技術原因,我不能使用系統中的文件排序程序。

需要排序的內容是什么?文件中有多少條記錄?每條記錄的格式是什么?

文件很多包含1千萬條記錄,每條記錄都是7位的整數。

等一下,既然文件這么小,何必非要在磁盤上進行排序呢?為什么不在內存里進行排序呢?

盡管機器有許多兆字節的內存,但排序功能只是大系統中的一部分,所以,估計到時只有1 MB的內存可用。

你還能告訴我其他一些與記錄相關的信息嗎?

每條記錄都是7位的正整數,再無其他相關數據。每個整數很多只出現一次。

這番對話讓問題更明確了。在美國,電話號碼由3位“區號”后再跟7位數字組成。撥打含“免費”區號800(當時只有這一個號碼)的電話是不收費的。實際的免費電話號碼數據庫包含大量的信息:免費電話號碼、呼叫實際中轉到的號碼(有時是幾個號碼,這時需要一些規則來決定哪些呼叫在什么時間中轉到哪里)、主叫用戶的姓名和地址等。

這位程序員正在開發這類數據庫的處理系統的一小部分,需要排序的整數就是免費電話號碼。輸入文件是電話號碼的列表(已刪除所有其他信息),號碼重復出現算出錯。期望的輸出文件是以升序排列的電話號碼列表。應用背景同時定義了相應的性能需求。當與系統的會話時間較長時,用戶大約每小時請求一次有序文件,并且在排序未完成之前什么都干不了。因此,排序很多只允許執行幾分鐘,10秒鐘是比較理想的運行時間。

對程序員來說,這些需求加起來就是:“如何給磁盤文件排序?”在試圖解決這個問題之前,先將已知條件組織成一種更客觀、更易用的形式。

輸入:一個很多包含 n 個正整數的文件,每個數都小于 n,其中 n=107。如果在輸入文件中有任何整數重復出現就是致命錯誤。沒有其他數據與該整數相關聯。

輸出:按升序排列的輸入整數的列表。

約束:很多有(大約)1 MB的內存空間可用,有充足的磁盤存儲空間可用。運行時間很多幾分鐘,運行時間為10秒就不需要進一步優化了。

請花上一分鐘思考一下該問題的規范說明。現在你打算給程序員什么樣的建議呢?

顯而易見的方法是以一般的基于磁盤的歸并排序程序為起點,但是要對其進行調整,因為我們是對整數進行排序。這樣就可以將原來的200行程序減少為幾十行,同時也使得程序運行得更快,但是完成程序并使之運行可能仍然需要幾天的時間。

另一種解決方案更多地利用了該排序問題的特殊性。如果每個號碼都使用7個字節來存儲,那么在可用的1 MB存儲空間里大約可以存143 000個號碼。如果每個號碼都使用32位整數來表示的話,在1 MB存儲空間里就可以存儲250 000個號碼。因此,可以使用遍歷輸入文件40趟的程序來完成排序。在第一趟遍歷中,將0至249 999之間的任何整數都讀入內存,并對這(很多)250 000 個整數進行排序,然后寫到輸出文件中。第二趟遍歷排序250 000至499 999之間的整數,依此類推,到第40趟遍歷的時候對9 750 000至9 999 999之間的整數進行排序。對內存中的排序來說,快速排序會相當高效,而且僅僅需要20 行代碼(見第11章)。于是,整個程序就可以通過一兩頁紙的代碼實現。該程序擁有所期望的特性——不必考慮使用中間磁盤文件;但是,為此所付出的代價是要讀取輸入文件40次。

歸并排序讀入輸入文件一次,然后在工作文件的幫助下完成排序并寫入輸出文件一次。工作文件需要多次讀寫。

40趟算法讀入輸入文件多次,寫輸出文件僅一次,不使用中間文件。

圖書網:編程珠璣(第2版 修訂版)pdf

  • 我的微信
  • 掃一掃加好友
  • weinxin
  • 微信公眾號
  • 掃一掃關注
  • weinxin

發表評論

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: