本書提供了用C語言描述的完整算法源程式，是Sedgewick徹底修訂和重寫的C算法系列的第一本。全書分為四部分，共16章。第一部分“基礎知識”(第1～2章)介紹基本算法分析原理。第二部分“數據結構”(第3～5章)講解算法分析中必須掌握的數據結構知識，主要包括基本數據結構、抽象數據結構、遞歸和樹。第三部分“排序”(第6～11章)按章節順序分別討論基本排序方法(如選擇排序、插入排序、冒泡排序、希爾排序等)、快速排序方法、歸併和歸併排序方法、優先佇列與堆排序方法、基數排序方法以及特殊用途的排序方法，並比較了各種排序方法的性能特徵。第四部分“搜尋”(第12～16章) 在進一步講解符號表、樹等抽象數據類型的基礎上，重點討論散列方法、基數搜尋以及外部搜尋方法。
基本介紹
- 書名：算法：C語言實現（第1～4部分）基礎知識、數據結構、排序及搜尋
- 作者：(美)Robert Sedgewick
- 頁數：456
- 出版社：機械工業出版社
- 出版時間：2009 年10月
- 開本：16
基本信息,內容概要,作者簡介,目錄,譯者序,前言,
基本信息
原書名： Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition) (Pts. 1-4)原出版社： Addison-Wesley Professional
作者：
譯者： 霍紅衛[同譯者作品
出版社：
出版日期：
開本：開頁碼：版次：3-1
內容概要
書中提供了用C語言描述的完整算法源程式，並且配有豐富的插圖和練習，還包含大量簡潔的實現將理論和實踐成功地相結合，這些實現均可用在真實套用上。.本書內容豐富，具有很強的實用價值，適合作為高等院校計算機及相關專業本科生算法課程的教材，也是廣大研究人員的極佳參考讀物。本書是Sedgewick徹底修訂和重寫的C算法系列的第一本。全書分為四部分，共16章。第一部分“基礎知識”(第1～2章)介紹基本算法分析原理。第二部分“數據結構”(第3～5章)講解算法分析中必須掌握的數據結構知識，主要包括基本數據結構、抽象數據結構、遞歸和樹。第三部分“排序”(第6～11章)按章節順序分別討論基本排序方法(如選擇排序、插入排序、冒泡排序、希爾排序等)、快速排序方法、歸併和歸併排序方法、優先佇列與堆排序方法、基數排序方法以及特殊用途的排序方法，並比較了各種排序方法的性能特徵。第四部分“搜尋”(第12～16章) 在進一步講解符號表、樹等抽象數據類型的基礎上，重點討論散列方法、基數搜尋以及外部搜尋方法。..書中提供了用C語言描述的完整算法源程式，並且配有豐富的插圖和練習。作者用簡潔的實現將理論和實踐成功地結合了起來，這些實現均可在真實套用上測試，使得本書自問世以來備受程式設計師的歡迎。本書可作為高等院校計算機相關專業算法與數據結構課程的教材和補充讀物，也可供自學之用。
作者簡介
：
Robed Sedgewick擁有史丹福大學博士學位(導師為Donald E. Knuth)，昔林斯頓大學計算機科學系教授，Adobe Systems公司董事，曾是XeroxPARC的研究人員，還曾就職於美國國防部防禦分析研究所以及INRIA。除本書外，他還與Philippe Flajolet合著了《算法分析導論》一書。...
目錄
出版者的話. 譯者序 前言
第一部分 基礎知識
第1章 引言 1 1.1
算法 1 1.2 典型問題—連通性
2 1.3 合併－查找算法
5 1.4 展望
12 1.5 主題概述 13
第2章 算法分析的原理
15 2.1 實現和經驗分析
15 2.2 算法分析
17 2.3 函式的增長
19 2.4 大O符號
23 2.5 基本遞歸方程
27 2.6 算法分析示例
29 2.7 保證、預測及局限性
33
第二部分 數據結構
第3章 基本數據結構
37 .3.1 構建組件 37 3.2 數組 44 3.3 鍊表 49 3.4 鍊表的基本處理操作 54 3.5 鍊表的記憶體分配 60 3.6 字元串 63 3.7 複合數據結構 66
第4章 抽象數據類型 74 4.1 抽象對象和對象集 76 4.2 下推棧ADT 78 4.3 棧ADT客戶示例 79 4.4 棧ADT的實現 84 4.5 創建一個新ADT 87 4.6 FIFO佇列和廣義佇列 90 4.7 複製和索引項 95 4.8 一級ADT 99 4.9 基於套用的ADT示例 106 4.10 展望 110
第5章 遞歸與樹 111 5.1 遞歸算法 111 5.2 分治法 116 5.3 動態規劃 127 5.4 樹 133 5.5 樹的數學性質 138 5.6 樹的遍歷 140 5.7 遞歸二叉樹算法 145 5.8 圖的遍歷 149 5.9 綜述 155
第三部分 排序
第6章 基本排序方法 157 6.1 遊戲規則 158 6.2 選擇排序 161 6.3 插入排序 162 6.4 冒泡排序 164 6.5 基本排序方法的性能特徵 166 6.6 希爾排序 171 6.7 對其他類型的數據進行排序 177 6.8 索引和指針排序 180 6.9 鍊表排序 185 6.10 關鍵字索引統計 188
第7章 快速排序 191 7.1 基本算法 191 7.2 快速排序算法的性能特徵 195 7.3 棧大小 198 7.4 小的子檔案 201 7.5 三者取中劃分.. 203 7.6 重複關鍵字 206 7.7 字元串和向量 209 7.8 選擇 210
第8章 歸併與歸併排序 213 8.1 兩路歸併 213 8.2 抽象原位歸併 215 8.3 自頂向下的歸併排序 216 8.4 基本算法的改進 219 8.5 自底向上的歸併排序 220 8.6 歸併排序的性能特徵 223 8.7 歸併排序的鍊表實現 225 8.8 改進的遞歸過程 227
第9章 優先佇列和堆排序 229 9.1 基本操作的實現 231 9.2 堆數據結構 233 9.3 基於堆的算法 235 9.4 堆排序 240 9.5 優先佇列ADT 244 9.6 索引數據項的優先佇列 247 9.7 二項佇列 250
第10章 基數排序 258 10.1 位、位元組和字 259 10.2 二進制快速排序 261 10.3 MSD基數排序 265 10.4 三路基數快速排序 271 10.5 LSD基數排序 274 10.6 基數排序的性能特徵 278 10.7 亞線性時間排序 280 第11章 特殊用途的排序方法 284 11.1 Batcher奇偶歸併排序 284 11.2 排序網 289 11.3 外部排序 295 11.4 排序－歸併的實現 299 11.5 並行排序/歸併 303
第四部分 搜尋
第12章 符號表和二叉搜尋樹 307 12.1 符號表抽象數據類型 308 12.2 關鍵字索引搜尋 311 12.3 順序搜尋 313 12.4 二分搜尋 318 12.5 二叉搜尋樹 321 12.6 BST的性能特徵 327 12.7 符號表的索引實現 329 12.8 在BST的根節點插入 332 12.9 其他ADT函式的BST實現 336
第13章 平衡樹 343 13.1 隨機化BST 345 13.2 伸展BST 350 13.3 自頂向下2-3-4樹 355 13.4 紅黑樹 360 13.5 跳躍表 368 13.6 性能特徵 374
第14章 散列 377 14.1 散列函式 377 14.2 鏈地址法 385 14.3 線性探測法 388 14.4 雙重散列表 392 14.5 動態散列表 396 14.6 綜述 399
第15章 基數搜尋 402 15.1 數字搜尋樹 402 15.2 線索 406 15.3 帕氏線索 413 15.4 多路線索和TST 419 15.5 文本字元串索引算法 430
第16章 外部搜尋 434 16.1 遊戲規則 435 16.2 索引順序訪問 436 16.3 B樹 438 16.4 可擴展散列 447 16.5
綜述... 455
譯者序
本書是算法方面的優秀著作之一。它系統地闡述了算法的特徵以及它們可能套用的場合，討論了算法分析與理論計算機科學的關係，並通過實驗數據和分析結果表明選擇何種算法來解決實際問題。書中包含了基本概念、數據結構、排序算法和搜尋算法。.
這本書不僅適合於程式設計師和計算機科學專業的學生，而且也適合於那些想利用計算機並想使它運行更快或是想要解決更大問題的人們。書中的算法代表了過去50年來所研究的知識主體。對於大量套用問題，這些知識主體已經成為有效使用計算機不可缺少的部分。從物理學中的N-體模擬問題到分子生物學中的序列分析問題，在此所描述的基本方法在科學研究中已日顯重要。另外，從資料庫系統到Internet搜尋引擎，這些方法已經成為現代軟體系統的重要組成部分。隨著計算機套用的覆蓋面越來越廣，基本算法的影響也日益顯著。
本書主要內容及特點如下：
擴展介紹了數組、鍊表、串、樹和其他基本數據結構。
為排序、選擇、優先佇列ADT實現和符號表ADT（查找）實現提供了多達100多個算法。
介紹了多路基數排序、隨機BST、伸展樹、跳躍表、多路trie等新的數據結構。..
為算法提供了很多可視化的信息，還有大量實驗研究和基本分析研究，從而為選擇算法解決實際問題提供了依據。
增加了1000多個新練習，從而有助於深入了解算法的特徵。
本書以大量圖例說明算法的工作過程，使得算法更加易於理解和掌握。
適合作為高等院校算法設計課程的教材，同時可作為從事軟體開發和工程設計的專業人員的參考書。
由於時間較緊及譯者水平有限，譯文難免有錯誤及不妥之處，懇請讀者批評指正。...
譯者
於西安電子科技大學計算機學院
2009年4月
前言
寫本書的目的是為了對當今使用最為重要的計算機算法做一綜述，並為需要學習這方面知識的越來越多的讀者提供基礎的技術。本書可以在學生掌握了所需的基本程式設計技巧，熟悉了計算機系統，但還未學過計算機科學或計算機套用高級領域的專業課程的時候，用作計算機科學的第二、第三或第四門課程的教科書。此外，由於本書包含了大量有用算法的實現，以及關於這些算法的性能特徵的詳細信息，因而它還可用於自學，或者作為從事計算機系統或應用程式開發人員的參考手冊。寬廣的視角使得本書成為計算機算法領域最合適的入門讀物。.
對於新的一版，我不僅完全重寫了它的內容，而且還添加了一千多個練習、一百多幅圖表和數十個新程式。我還給所有圖表和程式添加了詳細的注釋。新的素材不僅涵蓋了新的主題，而且還包含對經典算法的更完整解釋。抽象數據類型是這本書的重點，這使得程式套用更廣泛，並且與現代面向對象的程式設計環境更緊密。讀過本書舊版本的人一定會發現，新版本包含了更為豐富的新信息，所有讀者將發現大量的教學資料為掌握基本概念提供了有效途徑。
由於新的素材數量過多，所以我們把新版本分為兩卷（每一卷的容量都大約為舊版本的大小），本書是第一卷。這卷書中包含了基本概念、數據結構、排序算法和搜尋算法；第二卷涵蓋的高級算法及套用是以第一卷的基本抽象概念和方法為基礎的。這個新版中的關於基本原理和數據結構的所有素材幾乎都是新的。
這本書不僅適合於程式設計師和計算機科學專業的學生，而且也適合於想利用計算機並想使它運行更快或是想要解決更大問題的人們。這本書中的算法代表了過去50年來所研究的知識主體。對於大量套用問題，這些知識主體已經成為有效使用計算機的不可缺少的部分。從物理學中的N-體模擬問題到分子生物學中的序列分析問題，在此所描述的基本方法在科學研究中已日顯重要。另外，對於從資料庫系統到Internet搜尋引擎，這些方法已經成為現代軟體系統的重要組成部分。隨著計算機套用的覆蓋面越來越廣，基本算法的影響也日益顯著。本書的目標是要提供一種資源，使廣大學生以及專業人士可以了解並有效利用這些算法解決計算機套用中出現的問題。
本書範圍
本書共有16章，分為四大部分：基礎、數據結構、排序和搜尋。這裡的說明是想使讀者對儘可能多的基本算法有一個了解。本書描述的從二項佇列到帕氏線索這個範圍內的獨創性的方法，都與計算機科學核心的基本范型相關。第二卷由另外四部分組成，涵蓋了字元串算法、幾何算法、圖算法和高級主題。寫這些書的主要意圖是把各個領域中套用的基本方法集合在一起，從而為用計算機求解問題提供最好的方法。
如果你已經學過計算機科學的一兩門課程，如C、Java或C++這樣的高級程式設計語言課程，或者可能還有講授程式設計系統的基本概念的課程，或者具有同等的程式設計經驗，那么一定會非常欣賞本書提供的資料。因此，本書是為那些熟悉現代程式設計語言和現代計算機系統的基本特性的人而編寫的。書中給出的參考文獻會有助於彌補背景知識的不足。
由於用來支持分析結果的大部分數學知識都包含在本書中（或者做出標記不在本書之中），因而儘管具有完備的數學知識肯定會有幫助，但專門對數學知識的準備不是必要的。
教學中的用法
在教學中如何使用本書內容具有很大的靈活性，這取決於教師的偏好以及學生所做的準備。這裡所描述的算法多年以來已經得到廣泛套用，而且無論對於實際的程式設計師還是計算機科學專業的學生，這些算法都代表了基本的知識主體。書中涵蓋了足夠的基本內容可用作數據結構課程的學習，也有足夠詳細的高級主題用於算法課程的學習。有些教師可能希望強調與實現和實踐有關的內容，而另外一些教師則可能把重點放在分析和理論概念上。
教學中使用的電子文檔、程式設計示例作業、為學生提供的互動式練習以及其他課程有關的資料都可在本書的主頁上找到。
關於數據結構和算法的基礎課程可以把重點放在第二部分的基本數據結構及其他們在第三、四部分實現中的套用。關於算法設計與分析的課程可以把重點放在第一部分和第五部分中的基礎內容，然後在第三部分和第四部分研究算法達到良好漸近性能的方法。關於軟體工程的課程可能會省略數學和高級算法的內容，並把重點放在如何把給出的算法實現集成到大的程式或系統中。關於算法的課程則可能進行綜述並引入所有這些領域的概念。
本書的早期版本在近年來為世界各地的學院或大學用作計算機科學的第二或第三門課程的教材或其他課程的補充閱讀材料。在普林斯頓大學，我們的經驗表明這本書內容覆蓋面廣，為主修課程提供計算機科學的導引，並可在後續的算法分析、系統程式設計以及理論計算機科學的課程中對它進行擴充，同時為其他學科的學生提供一整套的技術，使他們能很快學以致用。
這一版中的大多數練習是新添加的，分為幾種類型。一類練習的目的是為了測試對課文中內容的理解，要求讀者能夠完成某個例子或套用課文中描述的概念。另一類練習則涉及實現算法和把算法整理到一起，或者進行實驗研究從而對各種算法進行比較以及了解其性質。還有一類練習則是一些重要信息的知識庫，其詳細程度本身不適合放在正文中。閱讀並思考這些練習，會使每個讀者受益匪淺。
算法的實用性
若希望更有效地使用計算機，可以把這本書用作參考書，或用於自學。具有程式設計經驗的人可以從本書中找到有關某個特殊主題的信息。對於更大範圍的讀者，儘管某些情況下，某一章中的算法使用了前一章中的方法，但你仍可以獨立於本書的其他章節閱讀本書的某個章節。
本書的定位是研究有可能實用的算法。本書提供了算法的詳盡信息，讀者可以放心地實現和調試算法，並使算法能夠用於求解某個問題，或者為某個套用提供相關功能。書中包括了所討論方法的完整實現，並在一系列一致的示例程式中給出了這些操作的描述。由於我們使用了實際代碼，而不是偽代碼，因而在實際中可以很快地使用這些程式。通過訪問本書的主頁可以得到程式的代碼清單。
實際上，書中算法的實際套用會產生數百幅圖表。正是這些圖表提供的立體視覺直觀地發現了許多算法。..
本書詳細討論了算法的特徵以及它們可能套用的場合。儘管並不強調，但是書中論述了算法分析與理論計算機科學的聯繫。在適當的時候，書中都給出了經驗性的數據和分析結果用以說明為什麼選擇使用某些算法。如果有趣，書中還會描述所討論的實際算法與純理論結果之間的關係。關於算法性能特徵和實現的某種信息的綜合、概括和討論都會貫穿本書的始終。
