《計算機科學叢書：算法：C語言實現》是2009年機械工業出版社出版的圖書，作者是塞奇威克(Robert Sedgewick)。
基本介紹
- 中文名：計算機科學叢書：算法：C語言實現
- 外文名：Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, Third Edition
- 作者：塞奇威克(Robert Sedgewick)
- 類型：計算機與網際網路
- 出版日期：2009年10月1日
- 語種：簡體中文
- ISBN：9787111275718
- 譯者：霍紅衛
- 出版社：機械工業出版社
- 頁數：456頁
- 開本：16
- 品牌：機械工業出版社
內容簡介,作者簡介,圖書目錄,媒體推薦,序言,
內容簡介
《算法:C語言實現(第1-4部分)基礎知識、數據結構、排序及搜尋(原書第3版)》細膩講解計算機算法的C語言實現。全書分為四部分，共16章。包括基本算法分析原理，基本數據結構、抽象數據結構、遞歸和樹等數據結構知識，選擇排序、插入排序、冒泡排序、希爾排序、快速排序方法、歸併和歸併排序方法、優先佇列與堆排序方法、基數排序方法以及特殊用途的排序方法，並比較了各種排序方法的性能特徵，在進一步講解符號表、樹等抽象數據類型的基礎上，重點討論散列方法、基數搜尋以及外部搜尋方法。書中提供了用C語言描述的完整算法源程式，並且配有豐富的插圖和練習，還包含大量簡潔的實現將理論和實踐成功地相結合，這些實現均可用在真實套用上。《算法:C語言實現(第1-4部分)基礎知識、數據結構、排序及搜尋(原書第3版)》內容豐富，具有很強的實用價值，適合作為高等院校計算機及相關專業本科生算法課程的教材，也是廣大研究人員的極佳參考讀物。
作者簡介
作者：(美國)塞奇威克(Robert Sedgewick) 譯者：霍紅衛
Robed Sedgewick擁有史丹福大學博士學位(導師為Donald E. Knuth)，昔林斯頓大學計算機科學系教授，Adobe Systems公司董事，曾是XeroxPARC的研究人員，還曾就職於美國國防部防禦分析研究所以及INRIA。除本書外，他還與Philippe Flajolet合著了《算法分析導論》一書。
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 下推棧ADT78
4．3 棧ADT客戶示例79
4．4 棧ADT的實現84
4．5 創建一個新ADT87
4．6 FIFO佇列和廣義佇列90
4．7 複製和索引項95
4．8 一級ADT99
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．1 0關鍵字索引統計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 優先佇列ADT244
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 隨機化BST345
13．2 伸展BST350
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 多路線索和TST419
15．5 文本字元串索引算法430
第16章 外部搜尋434
16．1 遊戲規則435
16．2 索引順序訪問436
16．3 B樹438
16．4 可擴展散列447
16．5 綜述455
譯者序
前言
第一部分 基礎知識
第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 下推棧ADT78
4．3 棧ADT客戶示例79
4．4 棧ADT的實現84
4．5 創建一個新ADT87
4．6 FIFO佇列和廣義佇列90
4．7 複製和索引項95
4．8 一級ADT99
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．1 0關鍵字索引統計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 優先佇列ADT244
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 隨機化BST345
13．2 伸展BST350
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 多路線索和TST419
15．5 文本字元串索引算法430
第16章 外部搜尋434
16．1 遊戲規則435
16．2 索引順序訪問436
16．3 B樹438
16．4 可擴展散列447
16．5 綜述455
媒體推薦
對於在數學分析方面不算熟練且需要留意理論算法的普通程式設計師來說，本書是一本可讀性很強的優秀讀本。他們應該會從中獲益良多。
——Steve Summit，《C Programming FAQs》的作者
Sedgewick有一種真正的天賦，可以用易於理解的方式來解釋概念。書中採用了一些易懂的實戰程式，其篇幅僅有一頁左右，這更是錦上添花。而書中大量採用的圖、程式、表格也會極大幫助讀者的學習和理解，這使本書更顯得與眾不同。
——William A. Ward，南阿拉巴馬大學
——Steve Summit，《C Programming FAQs》的作者
Sedgewick有一種真正的天賦，可以用易於理解的方式來解釋概念。書中採用了一些易懂的實戰程式，其篇幅僅有一頁左右，這更是錦上添花。而書中大量採用的圖、程式、表格也會極大幫助讀者的學習和理解，這使本書更顯得與眾不同。
——William A. Ward，南阿拉巴馬大學
序言
寫本書的目的是為了對當今使用最為重要的計算機算法做一綜述，並為需要學習這方面知識的越來越多的讀者提供基礎的技術。本書可以在學生掌握了所需的基本程式設計技巧，熟悉了計算機系統，但還未學過計算機科學或計算機套用高級領域的專業課程的時候，用作計算機科學的第二。第三或第四門課程的教科書。此外，由於本書包含了大量有用算法的實現，以及關於這些算法的性能特徵的詳細信息，因而它還可用於自學，或者作為從事計算機系統或應用程式開發人員的參考手冊。寬廣的視角使得本書成為計算機算法領域最合適的入門讀物。
對於新的一版，我不僅完全重寫了它的內容，而且還添加了一千多個練習。一百多幅圖表和數十個新程式。我還給所有圖表和程式添加了詳細的注釋。新的素材不僅涵蓋了新的主題，而且還包含對經典算法的更完整解釋。抽象數據類型是這本書的重點，這使得程式套用更廣泛，並且與現代面向對象的程式設計環境更緊密。讀過本書舊版本的人一定會發現，新版本包含了更為豐富的新信息，所有讀者將發現大量的教學資料為掌握基本概念提供了有效途徑。
由於新的素材數量過多，所以我們把新版本分為兩卷（每一卷的容量都大約為舊版本的大小），本書是第一卷。這卷書中包含了基本概念。數據結構。排序算法和搜尋算法，第二卷涵蓋的高級算法及套用是以第一卷的基本抽象概念和方法為基礎的。這個新版中的關於基本原理和數據結構的所有素材幾乎都是新的。
這本書不僅適合於程式設計師和計算機科學專業的學生，而且也適合於想利用計算機並想使它運行更快或是想要解決更大問題的人們。這本書中的算法代表了過去50年來所研究的知識主體。對於大量套用問題，這些知識主體已經成為有效使用計算機的不可缺少的部分。從物理學中的N-體模擬問題到分子生物學中的序列分析問題，在此所描述的基本方法在科學研究中已日顯重要。另外，對於從資料庫系統到Internet搜尋引擎，這些方法已經成為現代軟體系統的重要組成部分。隨著計算機套用的覆蓋面越來越廣，基本算法的影響也日益顯著。本書的目標是要提供一種資源，使廣大學生以及專業人士可以了解並有效利用這些算法解決計算機套用中出現的問題。
對於新的一版，我不僅完全重寫了它的內容，而且還添加了一千多個練習。一百多幅圖表和數十個新程式。我還給所有圖表和程式添加了詳細的注釋。新的素材不僅涵蓋了新的主題，而且還包含對經典算法的更完整解釋。抽象數據類型是這本書的重點，這使得程式套用更廣泛，並且與現代面向對象的程式設計環境更緊密。讀過本書舊版本的人一定會發現，新版本包含了更為豐富的新信息，所有讀者將發現大量的教學資料為掌握基本概念提供了有效途徑。
由於新的素材數量過多，所以我們把新版本分為兩卷（每一卷的容量都大約為舊版本的大小），本書是第一卷。這卷書中包含了基本概念。數據結構。排序算法和搜尋算法，第二卷涵蓋的高級算法及套用是以第一卷的基本抽象概念和方法為基礎的。這個新版中的關於基本原理和數據結構的所有素材幾乎都是新的。
這本書不僅適合於程式設計師和計算機科學專業的學生，而且也適合於想利用計算機並想使它運行更快或是想要解決更大問題的人們。這本書中的算法代表了過去50年來所研究的知識主體。對於大量套用問題，這些知識主體已經成為有效使用計算機的不可缺少的部分。從物理學中的N-體模擬問題到分子生物學中的序列分析問題，在此所描述的基本方法在科學研究中已日顯重要。另外，對於從資料庫系統到Internet搜尋引擎，這些方法已經成為現代軟體系統的重要組成部分。隨著計算機套用的覆蓋面越來越廣，基本算法的影響也日益顯著。本書的目標是要提供一種資源，使廣大學生以及專業人士可以了解並有效利用這些算法解決計算機套用中出現的問題。
