《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》細膩講解計算機算法的C語言實現(xiàn)。全書分為四部分,共16章。包括基本算法分析原理,基本數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)結(jié)構(gòu)、遞歸和樹等數(shù)據(jù)結(jié)構(gòu)知識,選擇排序、插入排序、冒泡排序、希爾排序、快速排序方法、歸并和歸并排序方法、優(yōu)先隊列與堆排序方法、基數(shù)排序方法以及特殊用途的排序方法,并比較了各種排序方法的性能特征,在進一步講解符號表、樹等抽象數(shù)據(jù)類型的基礎上,重點討論散列方法、基數(shù)搜索以及外部搜索方法。書中提供了用C語言描述的完整算法源程序,并且配有豐富的插圖和練習,還包含大量簡潔的實現(xiàn)將理論和實踐成功地相結(jié)合,這些實現(xiàn)均可用在真實應用上。
《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》內(nèi)容豐富,具有很強的實用價值,適合作為高等院校計算機及相關專業(yè)本科生算法課程的教材,也是廣大研究人員的參考讀物。
《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》是Sedgewick徹底修訂和重寫的C算法系列。全書分為四部分,共16章。“基礎知識”(第1~2章)介紹基本算法分析原理。第二部分“數(shù)據(jù)結(jié)構(gòu)”(第3~5章)講解算法分析中必須掌握的數(shù)據(jù)結(jié)構(gòu)知識,主要包括基本數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)結(jié)構(gòu)、遞歸和樹。第三部分“排序”(第6~11章)按章節(jié)順序分別討論基本排序方法(如選擇排序、插入排序、冒泡排序、希爾排序等)、快速排序方法、歸并和歸并排序方法、優(yōu)先隊列與堆排序方法、基數(shù)排序方法以及特殊用途的排序方法,并比較了各種排序方法的性能特征。第四部分“搜索”(第12~16章) 在進一步講解符號表、樹等抽象數(shù)據(jù)類型的基礎上,重點討論散列方法、基數(shù)搜索以及外部搜索方法。
書中提供了用C語言描述的完整算法源程序,并且配有豐富的插圖和練習。作者用簡潔的實現(xiàn)將理論和實踐成功地結(jié)合了起來,這些實現(xiàn)均可在真實應用上測試,使得《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》自問世以來備受程序員的歡迎。
《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》可作為高等院校計算機相關專業(yè)算法與數(shù)據(jù)結(jié)構(gòu)課程的教材和補充讀物,也可供自學之用。
《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》/為程序員提供了《算法:C語言實現(xiàn)(第1-4部分)基礎知識、數(shù)據(jù)結(jié)構(gòu)、排序及搜索(原書第3版)》的源代碼和勘誤表。
寫本書的目的是為了對當今使用最為重要的計算機算法做一綜述,并為需要學習這方面知識的越來越多的讀者提供基礎的技術。本書可以在學生掌握了所需的基本程序設計技巧,熟悉了計算機系統(tǒng),但還未學過計算機科學或計算機應用高級領域的專業(yè)課程的時候,用作計算機科學的第二。第三或第四門課程的教科書。此外,由于本書包含了大量有用算法的實現(xiàn),以及關于這些算法的性能特征的詳細信息,因而它還可用于自學,或者作為從事計算機系統(tǒng)或應用程序開發(fā)人員的參考手冊。寬廣的視角使得本書成為計算機算法領域最合適的入門讀物。
對于新的一版,我不僅完全重寫了它的內(nèi)容,而且還添加了一千多個練習。一百多幅圖表和數(shù)十個新程序。我還給所有圖表和程序添加了詳細的注釋。新的素材不僅涵蓋了新的主題,而且還包含對經(jīng)典算法的更完整解釋。抽象數(shù)據(jù)類型是這本書的重點,這使得程序應用更廣泛,并且與現(xiàn)代面向?qū)ο蟮某绦蛟O計環(huán)境更緊密。讀過本書舊版本的人一定會發(fā)現(xiàn),新版本包含了更為豐富的新信息,所有讀者將發(fā)現(xiàn)大量的教學資料為掌握基本概念提供了有效途徑。
由于新的素材數(shù)量過多,所以我們把新版本分為兩卷(每一卷的容量都大約為舊版本的大。,本書是第一卷。這卷書中包含了基本概念。數(shù)據(jù)結(jié)構(gòu)。排序算法和搜索算法,第二卷涵蓋的高級算法及應用是以第一卷的基本抽象概念和方法為基礎的。這個新版中的關于基本原理和數(shù)據(jù)結(jié)構(gòu)的所有素材幾乎都是新的。
這本書不僅適合于程序員和計算機科學專業(yè)的學生,而且也適合于想利用計算機并想使它運行更快或是想要解決更大問題的人們。這本書中的算法代表了過去50年來所研究的知識主體。對于大量應用問題,這些知識主體已經(jīng)成為有效使用計算機的不可缺少的部分。從物理學中的N-體模擬問題到分子生物學中的序列分析問題,在此所描述的基本方法在科學研究中已日顯重要。另外,對于從數(shù)據(jù)庫系統(tǒng)到Internet搜索引擎,這些方法已經(jīng)成為現(xiàn)代軟件系統(tǒng)的重要組成部分。隨著計算機應用的覆蓋面越來越廣,基本算法的影響也日益顯著。本書的目標是要提供一種資源,使廣大學生以及專業(yè)人士可以了解并有效利用這些算法解決計算機應用中出現(xiàn)的問題。
塞奇威克(Robert Sedgewick),擁有斯坦福大學博士學位(導師為donald E.Knuth),普林斯頓大學計算機科學系教授,Adobe Systems公司董事,曾是Xerox PARC的研究人員,還曾就職于美國國防防御分析研究所以及INRIA。除本書外,他還與Philippe Flajolet合著了《算法分析導論》一書。
出版者的話
譯者序
前言
第一部分 基礎知識
第1章 引言1
1.1 算法1
1.2 典型問題—連通性2
1.3 合并-查找算法5
1.4 展望12
1.5 主題概述13
第2章 算法分析的原理15
2.1 實現(xiàn)和經(jīng)驗分析15
2.2 算法分析17
2.3 函數(shù)的增長19
2.4 大O符號23
2.5 基本遞歸方程27
2.6 算法分析示例29
2.7 保證.預測及局限性33
第二部分 數(shù)據(jù)結(jié)構(gòu)
第3章 基本數(shù)據(jù)結(jié)構(gòu)37
3.1 構(gòu)建組件37
3.2 數(shù)組44
3.3 鏈表49
3.4 鏈表的基本處理操作54
3.5 鏈表的內(nèi)存分配60
3.6 字符串63
3.7 復合數(shù)據(jù)結(jié)構(gòu)66
第4章 抽象數(shù)據(jù)類型74
4.1 抽象對象和對象集76
4.2 下推棧ADT78
4.3 棧ADT客戶示例79
4.4 棧ADT的實現(xiàn)84
4.5 創(chuàng)建一個新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 動態(tài)規(guī)劃127
5.4 樹133
5.5 樹的數(shù)學性質(zhì)138
5.6 樹的遍歷140
5.7 遞歸二叉樹算法145
5.8 圖的遍歷149
5.9 綜述155
第三部分 排序
第6章 基本排序方法157
6.1 游戲規(guī)則158
6.2 選擇排序161
6.3 插入排序162
6.4 冒泡排序164
6.5 基本排序方法的性能特征166
6.6 希爾排序171
6.7 對其他類型的數(shù)據(jù)進行排序177
6.8 索引和指針排序180
6.9 鏈表排序185
6.1 0關鍵字索引統(tǒng)計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 歸并排序的鏈表實現(xiàn)225
8.8 改進的遞歸過程227
第9章 優(yōu)先隊列和堆排序229
9.1 基本操作的實現(xiàn)231
9.2 堆數(shù)據(jù)結(jié)構(gòu)233
9.3 基于堆的算法235
9.4 堆排序240
9.5 優(yōu)先隊列ADT244
9.6 索引數(shù)據(jù)項的優(yōu)先隊列247
9.7 二項隊列250
第10章 基數(shù)排序258
10.1 位.字節(jié)和字259
10.2 二進制快速排序261
10.3 MSD基數(shù)排序265
10.4 三路基數(shù)快速排序271
10.5 LSD基數(shù)排序274
10.6 基數(shù)排序的性能特征278
10.7 亞線性時間排序280
第11章 特殊用途的排序方法284
11.1 Batcher奇偶歸并排序284
11.2 排序網(wǎng)289
11.3 外部排序295
11.4 排序-歸并的實現(xiàn)299
11.5 并行排序/歸并303
第四部分 搜索
第12章 符號表和二叉搜索樹307
12.1 符號表抽象數(shù)據(jù)類型308
12.2 關鍵字索引搜索311
12.3 順序搜索313
12.4 二分搜索318
12.5 二叉搜索樹321
12.6 BST的性能特征327
12.7 符號表的索引實現(xiàn)329
12.8 在BST的根節(jié)點插入332
12.9 其他ADT函數(shù)的BST實現(xiàn)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 散列函數(shù)377
14.2 鏈地址法385
14.3 線性探測法388
14.4 雙重散列表392
14.5 動態(tài)散列表396
14.6 綜述399
第15章 基數(shù)搜索402
15.1 數(shù)字搜索樹402
15.2 線索406
15.3 帕氏線索413
15.4 多路線索和TST419
15.5 文本字符串索引算法430
第16章 外部搜索434
16.1 游戲規(guī)則435
16.2 索引順序訪問436
16.3 B樹438
16.4 可擴展散列447
16.5 綜述455
還有一個例子出現(xiàn)在某種程序設計環(huán)境中,連通性可用來斷言兩個變量名是否等價。問題是在經(jīng)過這樣的斷言序列之后,能夠確定兩個給定的名字是否等價。這個應用激發(fā)了我們打算考慮的幾個算法的研制。它直接將我們的問題與一種簡單抽象關聯(lián)起來,為使算法具有廣泛應用而提供了一種方法。我們即將看到這一點。
像上一段描述的變量名等價問題這樣的應用程序要求我們把每個不同的變量名與一個整數(shù)關聯(lián)起來。這種關聯(lián)關系也隱含在前面描述的網(wǎng)絡連接和電路連接的應用中。在第10章至第16章,我們將會以一種更高效的方法考慮提供這種連接關系的大量算法。因此,不失一般性,本章假設有N個對象,每個都與0一N一1之間的一個整數(shù)名對應。
我們正在尋求完成特定和良定義任務的程序,可能還想要解決其他許多相關的問題。在研制算法時我們面對的首要任務之一是確信我們已經(jīng)以合理的方式指定了問題。我們要求算法的越多,它完成任務所需要的時間和空間越多。不可能量化這個關系,并且我們在發(fā)現(xiàn)一個問題難以求解或是求解代價昂貴,或是在好的情況下,發(fā)現(xiàn)算法可以比原始說明提供更多有用的信息時,我們常常修改這個問題的說明。
例如,我們的連通問題的說明只要求我們的程序知道任意給定對p—q是否是連通的,并不能夠表明連接那個對的任何方式。添加這樣一個說明的要求會使問題更加困難,會涉及其他的算法,我們將在第5章簡略討論,并在第7章詳細討論。
前面這段提到的說明要比原始說明要求更多的信息,我們也可以要求更少的信息。例如,我們可能只想回答這樣的問題:“M個連接足以把Ⅳ個對象都連接起來嗎?”這個問題表明,要研制一個高效的算法,常常需要我們對正在處理的抽象對象進行高級推理。在這種情況下,由圖論基本結(jié)果可以得出所有Ⅳ個對象是連通的,當且僅當連通算法輸出的對的個數(shù)恰好為N一1(見5.4節(jié))。換句話說,連通算法永遠不會輸出多于N一1個對,這是因為一旦它輸出N一1個對,則它從那個時刻遇見的任何對將會是連通的。因此,我們可以修改求解連通問題的程序,增加一個計數(shù)器就可以得到一個回答yes-no問題的程序,而不輸出那些前面不連通的每個對,當計數(shù)器的值為N-1時,程序回答“yes”,否則回答“no”。這個問題只是我們希望回答關于連通性的許多問題中的一個例子。輸入對的集合稱為圖(graph),輸出對的集合稱為圖的生成樹,它連接了所有對象。我們在第七部分考察圖、生成樹以及所有相關算法的性質(zhì)。
……