産品特色

內容簡介

本書是國外數據結構與算法分析方麵的經典教材，使用卓越的Java編程語言作為實現工具，討論數據結構（組織大量數據的方法）和算法分析（對算法運行時間的估計）。
隨著計算機速度的不斷增加和功能的日益強大，人們對有效編程和算法分析的要求也不斷增長。本書將算法分析與*有效率的Java程序的開發有機結閤起來，深入分析每種算法，並細緻講解精心構造程序的方法，內容全麵，縝密嚴格。

第3版的主要更新如下：
第4章包含AVL樹刪除算法的實現。
第5章進行瞭全麵修訂和擴充，現在包含兩種較新的算法——布榖鳥散列和跳房子散列。
第7章包含基數排序的相關內容，並給齣瞭下界證明。
第12章增加瞭後綴樹和後綴數組的相關材料，包括Karkkainen和Sanders的綫性時間後綴數組構造算法。
更新書中的代碼，使用瞭Java 7中的菱形運算符。

作者簡介

　　馬剋·艾倫·維斯(MarkAllenWeiss)佛羅裏達國際大學計算與信息科學學院教授、副院長，本科教育主任和研究生教育主任。他於1987年獲得普林斯頓大學計算機科學博士學位，師從BobSedgewick。他曾經擔任全美AP(AdvancedPlacement)考試計算機學科委員會的主席(2000-2004)。他的主要研究興趣是數據結構、算法和教育學。

目錄

齣版者的話
前言
第1章　引論1
1.1　本書討論的內容1
1.2　數學知識復習2
1.2.1　指數2
1.2.2　對數2
1.2.3　級數2
1.2.4　模運算4
1.2.5　證明的方法4
1.3　遞歸簡論5
1.4　實現泛型構件pre-Java 57
1.4.1　使用Object錶示泛型8
1.4.2　基本類型的包裝9
1.4.3　使用接口類型錶示泛型9
1.4.4　數組類型的兼容性10
1.5　利用Java 5泛型特性實現泛型構件11
1.5.1　簡單的泛型類和接口11
1.5.2　自動裝箱/拆箱11
1.5.3　菱形運算符12
1.5.4　帶有限製的通配符12
1.5.5　泛型static方法14
1.5.6　類型限界14
1.5.7　類型擦除15
1.5.8　對於泛型的限製15
1.6　函數對象16
小結18
練習18
參考文獻19
第2章　算法分析20
2.1　數學基礎20
2.2　模型22
2.3　要分析的問題22
2.4　運行時間計算24
2.4.1　一個簡單的例子24
2.4.2　一般法則24
2.4.3　最大子序列和問題的求解26
2.4.4　運行時間中的對數31
2.4.5　分析結果的準確性33
小結33
練習34
參考文獻37
第3章　錶、棧和隊列39
3.1　抽象數據類型39
3.2　錶ADT39
3.2.1　錶的簡單數組實現40
3.2.2　簡單鏈錶40
3.3　Java Collections API中的錶41
3.3.1　Collection接口41
3.3.2　Iterator接口42
3.3.3　List接口、ArrayList類和LinkedList類43
3.3.4　例子：remove方法對LinkedList類的使用44
3.3.5　關於ListIterator接口46
3.4　ArrayList類的實現46
3.4.1　基本類46
3.4.2　迭代器、Java嵌套類和內部類49
3.5　LinkedList類的實現52
3.6　棧ADT58
3.6.1　棧模型58
3.6.2　棧的實現59
3.6.3　應用59
3.7　隊列ADT65
3.7.1　隊列模型65
3.7.2　隊列的數組實現65
3.7.3　隊列的應用66
小結67
練習67
第4章　樹71
4.1　預備知識71
4.1.1　樹的實現72
4.1.2　樹的遍曆及應用72
4.2　二叉樹75
4.2.1　實現76
4.2.2　例子：錶達式樹76
4.3　查找樹ADT——二叉查找樹78
4.3.1　contains方法79
4.3.2　findMin方法和findMax方法80
4.3.3　insert方法80
4.3.4　remove方法82
4.3.5　平均情況分析83
4.4　AVL樹86
4.4.1　單鏇轉87
4.4.2　雙鏇轉89
4.5　伸展樹94
4.5.1　一個簡單的想法（不能直接使用）95
4.5.2　展開96
4.6　再探樹的遍曆100
4.7　B樹101
4.8　標準庫中的集閤與映射105
4.8.1　關於Set接口105
4.8.2　關於Map接口105
4.8.3　TreeSet類和TreeMap類的實現106
4.8.4　使用多個映射的實例106
小結111
練習111
參考文獻115
第5章　散列117
5.1　一般想法117
5.2　散列函數117
5.3　分離鏈接法119
5.4　不用鏈錶的散列錶123
5.4.1　綫性探測法123
5.4.2　平方探測法124
5.4.3　雙散列129
5.5　再散列130
5.6　標準庫中的散列錶132
5.7　最壞情形下O(1)訪問的散列錶 133
5.7.1　完美散列133
5.7.2　布榖鳥散列135
5.7.3　跳房子散列143
5.8　通用散列法146
5.9　可擴散列148
小結149
練習150
參考文獻153
第6章　優先隊列（堆）156
6.1　模型156
6.2　一些簡單的實現156
6.3　二叉堆157
6.3.1　結構性質157
6.3.2　堆序性質157
6.3.3　基本的堆操作158
6.3.4　其他的堆操作162
6.4　優先隊列的應用164
6.4.1　選擇問題164
6.4.2　事件模擬165
6.5　d-堆166
6.6　左式堆167
6.6.1　左式堆性質167
6.6.2　左式堆操作168
6.7　斜堆172
6.8　二項隊列173
6.8.1　二項隊列結構174
6.8.2　二項隊列操作174
6.8.3　二項隊列的實現176
6.9　標準庫中的優先隊列180
小結180
練習181
參考文獻184
第7章　排序186
7.1　預備知識186
7.2　插入排序186
7.2.1　算法186
7.2.2　插入排序的分析187
7.3　一些簡單排序算法的下界187
7.4　希爾排序188
7.5　堆排序191
7.6　歸並排序193
7.7　快速排序198
7.7.1　選取樞紐元199
7.7.2　分割策略200
7.7.3　小數組202
7.7.4　實際的快速排序例程202
7.7.5　快速排序的分析203
7.7.6　選擇問題的綫性期望時間算法206
7.8　排序算法的一般下界207
7.9　選擇問題的決策樹下界209
7.10　對手下界210
7.11　綫性時間的排序：桶排序和基數排序212
7.12　外部排序216
7.12.1　為什麼需要一些新的算法217
7.12.2　外部排序模型217
7.12.3　簡單算法217
7.12.4　多路閤並218
7.12.5　多相閤並219
7.12.6　替換選擇219
小結220
練習221
參考文獻225
第8章　不相交集類227
8.1　等價關係227
8.2　動態等價性問題227
8.3　基本數據結構229
8.4　靈巧求並算法231
8.5　路徑壓縮233
8.6　路徑壓縮和按秩求並的最壞情形234
8.6.1　緩慢增長的函數235
8.6.2　利用遞歸分解的分析235
8.6.3　O(M log*N)界240
8.6.4　O(Mα(M,N))界240
8.7　一個應用241
小結243
練習243
參考文獻244
第9章　圖論算法246
9.1　若乾定義246
9.2　拓撲排序248
9.3　最短路徑算法250
9.3.1　無權最短路徑251
9.3.2　Dijkstra算法254
9.3.3　具有負邊值的圖258
9.3.4　無圈圖259
9.3.5　所有點對最短路徑261
9.3.6　最短路徑的例子261
9.4　網絡流問題262
9.5　最小生成樹267
9.5.1　Prim算法267
9.5.2　Kruskal算法269
9.6　深度優先搜索的應用270
9.6.1　無嚮圖270
9.6.2　雙連通性271
9.6.3　歐拉迴路273
9.6.4　有嚮圖275
9.6.5　查找強分支276
9.7　NP-完全性介紹277
9.7.1　難與易278
9.7.2　NP類278
9.7.3　NP-完全問題279
小結280
練習280
參考文獻284
第10章　算法設計技巧288
10.1　貪婪算法288
10.1.1　一個簡單的調度問題288
10.1.2　哈夫曼編碼290
10.1.3　近似裝箱問題293
10.2　分治算法298
10.2.1　分治算法的運行時間298
10.2.2　最近點問題300
10.2.3　選擇問題302
10.2.4　一些算術問題的理論改進304
10.3　動態規劃307
10.3.1　用一個錶代替遞歸307
10.3.2　矩陣乘法的順序安排309
10.3.3　最優二叉查找樹311
10.3.4　所有點對最短路徑312
10.4　隨機化算法314
10.4.1　隨機數發生器315
10.4.2　跳躍錶319
10.4.3　素性測試320
10.5　迴溯算法322
10.5.1　收費公路重建問題323
10.5.2　博弈326
小結331
練習331
參考文獻336
第11章　攤還分析340
11.1　一個無關的智力問題340
11.2　二項隊列340
11.3　斜堆344
11.4　斐波那契堆345
11.4.1　切除左式堆中的節點346
11.4.2　二項隊列的懶惰閤並347
11.4.3　斐波那契堆操作349
11.4.4　時間界的證明350
11.5　伸展樹351
小結354
練習354
參考文獻355
第12章　高級數據結構及其實現356
12.1　自頂嚮下伸展樹356
12.2　紅黑樹362
12.2.1　自底嚮上的插入362
12.2.2　自頂嚮下紅黑樹363
12.2.3　自頂嚮下的刪除367
12.3　treap樹368
12.4　後綴數組與後綴樹370
12.4.1　後綴數組371
12.4.2　後綴樹373
12.4.3　綫性時間的後綴數組和後綴樹的構建375
12.5　k-d樹385
12.6　配對堆387
小結392
練習393
參考文獻396
索引399

前言/序言

　　本書目標本書新的Java版論述數據結構——組織大量數據的方法，以及算法分析——算法運行時間的估計。隨著計算機的速度越來越快，對於能夠處理大量輸入數據的程序的需求變得日益迫切。可是，由於在輸入量很大的時候程序的低效率變得非常明顯，因此這又要求對效率問題給予更仔細的關注。通過在實際編程之前對算法的分析，我們可以確定某個特定的解法是否可行。例如，查閱本書中一些特定的問題，可以看到我們如何通過巧妙的實現，將其處理大量數據的時間限製從幾個世紀減至不到1秒。因此，我們在提齣所有算法和數據結構時都會闡釋其運行時間。在某些情況下，對於影響實現的運行時間的一些微小細節都需要認真探究。
　　一旦確定瞭解法，接著就要編寫程序。隨著計算機功能的日益強大，它們必須解決的問題也變得更加龐大和復雜，這就要求我們開發更加復雜的程序。本書的目的是同時教授學生良好的程序設計技巧和算法分析能力，使得他們能夠以最高的效率開發齣這種程序。
　　本書適用於高級數據結構（CS7）課程或是第一年研究生的算法分析課程。學生應該掌握一些中級編程知識，包括基於對象的程序設計和遞歸等內容，並具備一些離散數學的背景。
　　第3版中最顯著的變化第3版訂正瞭大量的錯誤，也修改瞭很多地方，以使內容更加清晰。此外還有以下修訂：
　　●第4章包括瞭AVL樹的刪除算法——這也是讀者經常需要的內容。
　　●第5章進行瞭大量修改和擴充，現在包含兩種新算法：布榖鳥散列（cuckoohashing）和跳房子散列（hopscotchhashing）。此外還增加瞭一節討論通用散列法。
　　●第7章現在包含瞭基數排序的內容，並且增加瞭一節討論下界的證明。
　　●第8章用到Seidel和Sharir提齣的新的並查集分析，並且證明瞭O(Mα(M,N))界，而不是前一版中比較弱的O(Mlog*N)界。
　　●第12章增加瞭後綴樹和後綴數組的內容，包括Karkkainen和Sanders提齣的構造後綴數組的綫性時間算法（附帶實現）。關於確定性跳躍錶和AA樹的章節被刪除。
　　●通篇代碼已做更新，使用瞭Java7的菱形運算符。
　　處理方法雖然本書的內容大部分都與語言無關，但是，程序設計還是需要使用某種特定的語言。正如書名所示，我們為本書選擇瞭Java。
　　人們常常將Java和C++比較。Java具有許多優點，程序員常常把Java看成是一種比C++更安全、更具有可移植性並且更容易使用的語言。因此，這使得它成為討論和實現基礎數據結構的一種優秀的核心語言。Java的其他重要的方麵，諸如綫程和GUI（圖形用戶界麵），雖然很重要，但是本書並不需要，因此也就不再討論。
　　完整的Java和C++版數據結構均在互聯網上提供。我們采用相似的編碼約定以使得這兩種語言之間的對等性更加明顯。
　　內容概述第1章包含離散數學和遞歸的一些復習材料。我相信熟練掌握遞歸的唯一辦法是反復不斷地研讀一些好的用法。因此，除第5章外，遞歸遍及本書每一章的例子之中。第1章還介紹瞭一些相關內容，作為對Java中“繼承”的復習，包括對Java泛型的討論。
　　第2章討論算法分析，闡述漸近分析及其主要缺點，提供瞭許多例子，包括對對數級運行時間的深入分析。我們通過直觀地把遞歸程序轉變成迭代程序，對一些簡單遞歸程序進行瞭分析。更復雜的分治程序也在此介紹，不過有些分析（求解遞推關係）要推遲到第7章再進行詳細討論。
　　第3章介紹錶、棧和隊列。包括對CollectionsAPIArrayList類和LinkedList類的討論，提供瞭CollectionsAPIArrayList類和LinkedList類的一個重要子集的若乾實現。
　　.第4章討論樹，重點是查找樹，包括外部查找樹（B-樹）。UNIX文件係統和錶達式樹是作為例子來介紹的。這一章還介紹瞭AVL樹和伸展樹。查找樹實現細節的更仔細的處理可在第12章找到。樹的另外一些內容（如文件壓縮和博弈樹）推遲到第10章討論。外部介質上的數據結構作為若乾章中的最後論題來考慮。對於CollectionsAPITreeSet類和TreeMap類的討論，則通過一個重要的例子來展示三種單獨的映射在求解同一個問題中的使用。
　　第5章討論散列錶，既包括經典算法，如分離鏈接法和綫性及平方探測法，同時也包括幾個新算法，如布榖鳥散列和跳房子散列。本章還討論瞭通用散列法，並且在章末討論瞭可擴散列。
　　第6章是關於優先隊列的。二叉堆也在這裏講授，還有些附加的材料論述優先隊列某些理論上有趣的實現方法。斐波那契堆在第11章討論，配對堆在第12章討論。
　　第7章論述排序。這一章特彆關注編程細節和分析。所有重要的通用排序算法均在該章進行瞭討論和比較。此外，還對四種排序算法做瞭詳細的分析，它們是插入排序、希爾排序、堆排序以及快速排序。這一版新增的是基數排序以及對選擇類問題的下界的證明。本章末尾討論瞭外部排序。
　　第8章討論不相交集算法並證明其運行時間。分析部分是新的。這是簡短且特殊的一章，如果不討論Kruskal算法則可跳過該章。
　　第9章講授圖論算法。圖論算法之所以有趣，不僅因為它們在實踐中經常齣現，而且還因為它們的運行時間強烈地依賴於數據結構的恰當使用。實際上，所有標準算法都和適用的數據結構、僞代碼以及運行時間的分析一起介紹。為瞭恰當地理解這些問題，我們對復雜性理論（包括NP-完全性和不可判定性）進行瞭簡短的討論。
　　第10章通過考察一般性的問題求解技術來介紹算法設計。本章通過大量的例子來增強理解。這一章及後麵各章使用的僞代碼使得讀者在理解例子時不會被實現的細節所睏擾。
　　第11章處理攤還分析，主要分析三種數據結構，它們分彆在第4章、第6章以及本章（斐波那契堆）介紹。
　　第12章討論查找樹算法、後綴樹和數組、k-d樹和配對堆。不同於其他各章，本章給齣瞭查找樹和配對堆完整且仔細的實現。材料的安排使得教師可以把一些內容納入其他各章的討論之中。例如，第12章中的自頂嚮下紅黑樹可以和（第4章的）AVL樹一起討論。
　　第1~9章為大多數一學期的數據結構課程提供瞭足夠的材料。如果時間允許，那麼第10章也可以包括進來。研究生的算法分析課程可以使用第7~11章的內容。第11章所分析的高級數據結構可以很容易地被前麵各章所提及。第9章裏所討論的NP-完全性太過簡短，不適用於這樣的課程。另外再用一部NP-完全性方麵的著作作為本教材的補充可能是比較有益的。
　　練習每章末尾提供的練習與正文中所述內容的順序相一緻。最後的一些練習是對應整章而不是針對特定的某一節的。難度較大的練習標有一個星號，更具挑戰的練習標有兩個星號。
　　參考文獻參考文獻列於每章的最後。通常，這些參考文獻或者是具有曆史意義的、給齣書中材料的原始齣處，或者闡述對書中給齣的結果的擴展和改進。有些文獻為一些練習提供瞭解法。
　　補充材料下麵的補充材料在www.pearsonhighered.com/cssupport對所有讀者公開：
　　●例子程序的源代碼此外，下述材料僅提供給經培生教師資源中心（Pearson’sInstructorResourceCenter，IRC）(www.pearsonhighered.com/irc)認可的教師。有意者請訪問IRC或聯係培生的校園代錶以獲得訪問權限。�」賾詒臼榻談ㄗ試矗�用書教師可嚮培生教育齣版集團北京代錶處申請，電話：010-57355169/57355171，電子郵件：service.cn@pearson.com。——編輯注�　癲糠至廢暗慕獯稹窶醋員臼櫚囊恍└酵賈灤輝詒臼櫚淖急腹�程中，我得到瞭許多人的幫助，有些已在本書的其他版本中列齣，感謝大傢。
　　一如既往地，培生的專傢們的努力使得本書的寫作過程更加輕鬆。我願在此感謝我的編輯MichaelHirsch以及製作編輯PatBrown。我還要感謝AbinayaRajendran和她在IntegraSoftwareServices的同事，感謝他們使最後的散稿成書的齣色工作。賢妻Jill所做的每一件事情都值得我特彆感謝。
數據結構與算法分析：Java語言描述（原書第3版） 下載 mobi epub pdf txt 電子書

搞活動買的，以前本來有一本，但是被蟑螂咬瞭，搞得很髒，丟瞭重新買一本，紙張質量看起來還不錯。

正版無誤，包裝買迴來第一時間就拆掉瞭，上學那會同學買的80多，這搞活動，幾乎四摺，很優惠瞭

商品不錯 價格適中 配送速度快 比商場裏麵劃算

買的書很好用，對學習很有幫助，看印刷效果是正品，發貨送貨速度快，滿意！

書很厚，看起來也挺好的，也很便宜618湊單真的很便宜啊。。。

包裝完整，內容經典也無需多說，京東物流就是快

到底是貴的書，包裝過得去。比發的三本動物書包裝好多瞭。

很棒的一批書，6.18促銷力度很大，就買瞭很多心儀的書，感覺很棒，給京東一個贊

啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦