關(guān)于我們
書單推薦
新書推薦
|
數(shù)據(jù)結(jié)構(gòu)與算法分析——C++語言描述(第四版)
本書是數(shù)據(jù)結(jié)構(gòu)和算法分析的經(jīng)典教材,書中使用主流的程序設(shè)計語言C++作為具體的實現(xiàn)語言。書中內(nèi)容包括表、棧、隊列、樹、散列表、優(yōu)先隊列、排序、不相交集算法、圖論算法、算法分析、算法設(shè)計、攤還分析、查找樹算法、k-d樹和配對堆等。本書把算法分析與C++程序的開發(fā)有機地結(jié)合起來,深入分析每種算法,內(nèi)容全面、縝密嚴(yán)格,并細致講解精心構(gòu)造程序的方法。
本版特色如下:
*書中的闡述和算法均用C++新標(biāo)準(zhǔn)C++11的代碼實現(xiàn)。 *unordered_map兩個類模板的簡要討論。 *增加了基數(shù)排序和與選擇相關(guān)問題下界的證明。增加了對AVL樹刪除算法的實現(xiàn)。使用新的union/find分析同時改進此前各版的較弱的O(Mlog*N)界。
?目的/目標(biāo)
本書是《數(shù)據(jù)結(jié)構(gòu)與算法分析——C++語言描述》的第四版,論述組織大量數(shù)據(jù)的方法——數(shù)據(jù)結(jié)構(gòu),以及算法運行時間的估計——算法分析。隨著計算機的速度越來越快,對于能夠處理大量輸入數(shù)據(jù)的程序需求變得日益急迫?墒,由于在輸入量很大時程序的低效率顯得非常突出,因此又要求對效率問題給予更加嚴(yán)密的關(guān)注。通過在實際編程之前對算法進行分析,學(xué)生們可以確定一個特定的解決方案是否可行。例如,在本書中學(xué)生可查閱一些特定的問題并看到精心的實現(xiàn)怎樣能夠把處理大量數(shù)據(jù)的時間限制從若干個世紀(jì)減至不到一秒。因此,若無運行時間的闡釋,就不會有算法和數(shù)據(jù)結(jié)構(gòu)的提出。在某些情況下,對于影響實現(xiàn)的運行時間的一些微小細節(jié)都需要認真的探究。 一旦解法被確定,接著就要編寫程序。隨著計算機功能的日益強大,它們必須解決的問題就變得更加龐大和復(fù)雜,這就要求開發(fā)更加復(fù)雜的程序。本書的目標(biāo)是同時教授學(xué)生良好的程序設(shè)計技巧和算法分析能力,使他們開發(fā)的程序能夠具有最高的效率。 本書適合于高等數(shù)據(jù)結(jié)構(gòu)課程或是算法分析第一年的研究生課程。學(xué)生應(yīng)該具有中等程度的程序設(shè)計知識,包括指針、遞歸以及面向?qū)ο蟪绦蛟O(shè)計這樣一些內(nèi)容,此外還要具有一些離散數(shù)學(xué)的基礎(chǔ)。 處理方法 雖然本書的內(nèi)容大部分都與語言無關(guān),但是,程序設(shè)計還是需要使用某種特定的語言。正如書名指出的,我們?yōu)楸緯x擇了C++。 C++已經(jīng)成為主流系統(tǒng)編程語言。除修復(fù)C語言的許多語法漏洞之外,C++還提供一些直接結(jié)構(gòu)(類和模板)來實現(xiàn)作為抽象數(shù)據(jù)類型的泛型數(shù)據(jù)結(jié)構(gòu)。 編寫本書最困難的部分是決定C++所占的篇幅。使用太多C++的特性將使本書難以理解,使用太少又會使讀者得不到比支持類的C語言教材更多的收獲。 我們所采取的做法是以一種基于對象的處理方式展示書中的內(nèi)容。這樣,本書幾乎不存在對繼承的使用。書中以類模板描述泛型數(shù)據(jù)結(jié)構(gòu)。一般我們避免深奧的C++特性,但是使用了vector類和string類,如今它們已是C++標(biāo)準(zhǔn)的一部分。本書以前各版通過把類模板接口從其實現(xiàn)中分離出來已經(jīng)做到了對類模板的實現(xiàn)。雖然這是有爭議的首選方式,但它揭示出編譯器使讀者難以具體使用代碼的一些問題。因此,這一版中聯(lián)機代碼把類模板作為一個獨立的單元來介紹,無需接口與實現(xiàn)的分離。第1章提供了用于全書的C++特性的綜述,并描述了我們對類模板的處理方式。附錄A闡述如何能夠重寫類模板以使用分離式編譯。 以C++和Java二者描述的數(shù)據(jù)結(jié)構(gòu)的完全版可在互聯(lián)網(wǎng)上獲得。我們使用類似的編碼約定以使得這兩種語言間平行的結(jié)構(gòu)表現(xiàn)得更加明顯。 第四版最重要的變化概述 本書第四版吸收了大量對錯誤的修正,書中許多部分經(jīng)過修訂以增加表述的清晰度。此外: 第4章包含AVL樹刪除算法的實現(xiàn),它是一個常常被讀者提出的論題。 第5章已被廣泛修訂和擴展,現(xiàn)已包含兩個更新的算法:杜鵑散列和跳房子散列。此外,還添加了論述通用散列的新的一節(jié)。對C++中引入的unordered_set和unordered_ map兩個類模板的簡要討論也是新加的內(nèi)容。 第6章基本沒有變化,不過,二叉堆的實現(xiàn)用到了C++11版引入的移動操作(move operation)。 現(xiàn)在的第7章增加了基數(shù)排序的內(nèi)容,并添加了新的一節(jié),論述下界的證明。排序的程序用到C++11版中引入的移動操作。 第8章使用由Seidel和Sharir所作的新的union/find分析,并證明了O(M?(M, N))的界以代替前面各版較弱的O(M log*N)界。 第12章添加了論述后綴樹和后綴數(shù)組的材料,包括Karkkainen和Sanders的后綴數(shù)組線性時間構(gòu)建算法(及其實現(xiàn))。刪除了討論確定性跳躍表和AA樹的兩節(jié)。 全書所出現(xiàn)的代碼均用C++11作了更新。值得注意的是,這意味著C++11新特性的使用,包括auto關(guān)鍵字、范圍for循環(huán)、移動構(gòu)造和賦值,以及統(tǒng)一初始化(uniform initialization)。 內(nèi)容提要 第1章包含離散數(shù)學(xué)和遞歸的一些復(fù)習(xí)材料。我相信熟練處置遞歸唯一的辦法是反復(fù)不斷地研讀一些好的用法。因此,除第5章外,遞歸遍及本書每一章的例子之中。另外,第1章還介紹了一些材料,作為對基本C++的回顧,包括在C++類設(shè)計中對模板和一些重要結(jié)構(gòu)的討論。 第2章處理算法分析。這一章闡述漸近分析和它的主要弱點。這里提供了許多例子,包括對對數(shù)運行時間的深入解釋。通過直觀地把一些簡單遞歸程序轉(zhuǎn)變成迭代程序而對它們進行分析。介紹了更復(fù)雜的分治程序,不過有些分析(求解遞推關(guān)系)將推遲到第7章再詳細闡述。 第3章包括表、棧和隊列。這一章包括對STL中vector類和list類的討論,其中涉及到迭代器的一些材料,并提供對STL中vector類和list類的重要子集的實現(xiàn)。 第4章討論樹,重點在查找樹,包括外部查找樹(B樹)。UNIX文件系統(tǒng)和表達式樹是作為例子來使用的。本章還介紹了AVL樹和伸展樹。關(guān)于查找樹實現(xiàn)細節(jié)的更詳細的處理放在第12章介紹。樹的另外一些內(nèi)容,如文件壓縮和博弈樹,推遲至第10章討論。外部媒體上的數(shù)據(jù)結(jié)構(gòu)作為幾章中的最后論題來考慮。STL中set類和map類的討論也在本章進行,其中包括一個重要的例子,該例使用3個分離的映射高效地解決一個問題。 第5章討論散列表,包括諸如分離鏈接法以及線性探測法和平方探測法這樣一些經(jīng)典算法,此外還有幾個新算法,即杜鵑散列和跳房子散列。通用散列也在這里討論,而對可擴散列的討論則放在本章末尾進行。 第6章是關(guān)于優(yōu)先隊列的。二叉堆也安排在這里,還有些額外的材料論述優(yōu)先隊列某些理論上有趣的實現(xiàn)。斐波那契堆在第11章討論,配對堆在第12章討論。 第7章是排序。它是關(guān)于編程細節(jié)和分析的非常特殊的一章。所有重要的通用排序算法均被討論并進行了比較。詳細分析了4種算法:插入排序,希爾排序,堆排序,以及快速排序。本版新增加了基數(shù)排序和一些與選擇相關(guān)問題的下界證明。外部排序的討論安排在本章的末尾進行。 第8章討論不相交集算法并證明其運行時間。這是短小且特殊的一章,如果不討論Kruskal算法則該章可以跳過。 第9章講授圖論算法。圖論算法的趣味性不僅因為它們在實踐中經(jīng)常發(fā)生,而且還因為它們的運行時間強烈地依賴于數(shù)據(jù)結(jié)構(gòu)的恰當(dāng)使用。實際上,所有標(biāo)準(zhǔn)算法都是和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)、偽代碼以及運行時間的分析一起介紹的。為把這些問題放在一個適當(dāng)?shù)纳舷挛沫h(huán)境下,本章對復(fù)雜性理論(包括NP完全性和不可判定性)進行了簡要的討論。 第10章通過考查一些常見問題的求解技巧來討論算法設(shè)計。這一章通過大量實例而得到強化。這里及后面各章使用的偽代碼使得學(xué)生對一個算法實例的理解不至于被實現(xiàn)的細節(jié)所困擾。 第11章處理攤還分析。對來自第4章和第6章的3種數(shù)據(jù)結(jié)構(gòu)以及本章介紹的斐波那契堆進行了分析。 第12章討論查找樹算法、后綴樹和后綴數(shù)組、k-d樹、配對堆。不同于其他各章,本章為查找樹和配對堆提供了完全和審慎的實現(xiàn)。材料的安排使得教師可以把一些內(nèi)容整合到其他各章的討論中。例如,第12章中的自頂向下紅黑樹可以和AVL樹(第4章的)一起討論。 第1章~第9章為大多數(shù)一學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程提供了足夠的材料。如果時間允許,那么第10章也可以包括進來。研究生的算法分析課程可以使用第7章~第11章的內(nèi)容。在第11章所分析的高級數(shù)據(jù)結(jié)構(gòu)可以容易地在前面各章中查到。第9章中對NP完全性的討論太過簡單,以至于不足以用于這樣的一門算法分析課程。讀者將會發(fā)現(xiàn),參閱一些論述NP完全性的著述對深化本書內(nèi)容大有裨益。 練習(xí) 在每章末尾提供的練習(xí)與正文中講授內(nèi)容的順序相匹配。最后的一些練習(xí)是把一章作為一個整體來處理而不是針對特定的某一節(jié)來考慮的。難做的練習(xí)標(biāo)以一個星號,更難的練習(xí)標(biāo)注兩個星號。 參考文獻 參考文獻列于每章的最后。一般說來,這些參考文獻或者是歷史性質(zhì)的,代表著書中材料的原始來源,或者闡述對正文中給出結(jié)果的擴展和改進。有些文獻提供一些練習(xí)的解法。 補充材料 所有讀者均可從網(wǎng)站上獲取下列補充資料: 例子程序的源代碼 勘誤表 此外,下列材料只提供給Pearson Instructor Resource Center 上有資格的教師。如欲獲取這些資料,可訪問IRC或你的Pearson Education銷售代表。 書中挑選的一些練習(xí)的解答 本書中的一些圖示 勘誤表 致謝 在該叢書幾部著作的準(zhǔn)備過程中作者得到了許許多多朋友的幫助,有些人在本書的其他版本中列出。謝謝所有諸位。 如同往常一樣,Pearson專家們的努力使得本書的寫作過程更加輕松。我愿意借此機會感謝我的編輯Tracy Johnson,以及制作編輯Marilyn Lloyd。賢妻Jill因其所做的每一件工作應(yīng)該得到我特別的感謝。 最后,我還要感謝廣大的讀者,他們發(fā)送E-mail信息并指出較早各版的錯誤和矛盾之處。我的網(wǎng)站www.cis.fiu.edu/~weiss也將包含更新后(C++和Java)的源代碼,一個勘誤表,以及到提交問題報告的一個鏈接。 M.A.W. Miami,F(xiàn)lorida
馮舜璽,天津師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院退休教授,曾任天津市計算數(shù)學(xué)學(xué)會常務(wù)理事,主要教學(xué)及研究方向為數(shù)值代數(shù),組合數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu)與算法分析。 Mark Allen Weiss,佛羅里達國際大學(xué)計算與信息科學(xué)學(xué)院教授、副院長,本科教育主任和研究生教育主任。他于1987年獲得普林斯頓大學(xué)計算機科學(xué)博士學(xué)位,師從Bob Sedgewick。他曾經(jīng)擔(dān)任全美AP(Advanced Placement)考試計算機學(xué)科委員會的主席(2000-2004)。Weiss教授在數(shù)據(jù)結(jié)構(gòu)和算法分析方面卓有建樹,他的數(shù)據(jù)結(jié)構(gòu)和算法分析的著作尤其暢銷,并受到廣泛好評.已被世界500余所大學(xué)用作教材。
第1章 程序設(shè)計:綜述 1
1.1 本書討論的內(nèi)容 1 1.2 數(shù)學(xué)知識復(fù)習(xí) 2 1.2.1 指數(shù)(exponent) 2 1.2.2 對數(shù)(logarithm) 2 1.2.3 級數(shù)(series) 3 1.2.4 模運算(modular arithmetic) 4 1.2.5 證明方法 5 1.3 遞歸簡論 7 1.4 C++類 10 1.4.1 基本的class語法 10 1.4.2 構(gòu)造函數(shù)的附加語法和訪問 函數(shù) 11 1.4.3 接口與實現(xiàn)的分離 13 1.4.4 vector類和string類 16 1.5 C++細節(jié) 17 1.5.1 指針(pointer) 18 1.5.2 左值、右值和引用 19 1.5.3 參數(shù)傳遞 21 1.5.4 返回值傳遞 23 1.5.5 std::swap和std::move 25 1.5.6 五大函數(shù):析構(gòu)函數(shù),拷貝構(gòu)造 函數(shù),移動構(gòu)造函數(shù),拷貝賦值 operator=,移動賦值operator= 26 1.5.7 C風(fēng)格數(shù)組和字符串 30 1.6 模板 31 1.6.1 函數(shù)模板 31 1.6.2 類模板 32 1.6.3 Object、Comparable和一個 例子 33 1.6.4 函數(shù)對象 34 1.6.5 類模板的分離式編譯 37 1.7 使用矩陣 37 1.7.1 數(shù)據(jù)成員、構(gòu)造函數(shù)和基本訪問 函數(shù) 38 1.7.2 operator[] 38 1.7.3 五大函數(shù) 39 小結(jié) 39 練習(xí) 39 參考文獻 41 第2章 算法分析 42 2.1 數(shù)學(xué)基礎(chǔ) 42 2.2 模型 44 2.3 要分析的問題 44 2.4 運行時間計算 47 2.4.1 一個簡單的例子 47 2.4.2 一般法則 47 2.4.3 最大子序列和問題的求解 49 2.4.4 運行時間中的對數(shù) 54 2.4.5 最壞情形分析的局限性 57 小結(jié) 58 練習(xí) 58 參考文獻 63 第3章 表、棧和隊列 64 3.1 抽象數(shù)據(jù)類型(ADT) 64 3.2 表ADT 64 3.2.1 表的簡單數(shù)組實現(xiàn) 65 3.2.2 簡單鏈表 65 3.3 STL中的vector和list 67 3.3.1 迭代器 68 3.3.2 例子:對表使用erase 69 3.3.3 const_iterators 70 3.4 vector的實現(xiàn) 72 3.5 list的實現(xiàn) 76 3.6 棧ADT 86 3.6.1 棧模型 86 3.6.2 棧的實現(xiàn) 86 3.6.3 應(yīng)用 87 3.7 隊列ADT 93 3.7.1 隊列模型 93 3.7.2 隊列的數(shù)組實現(xiàn) 93 3.7.3 隊列的應(yīng)用 95 小結(jié) 96 練習(xí) 96 第4章 樹 100 4.1 預(yù)備知識 100 4.1.1 樹的實現(xiàn) 101 4.1.2 樹的遍歷及應(yīng)用 102 4.2 二叉樹 105 4.2.1 實現(xiàn) 105 4.2.2 一個例子――表達式樹 105 4.3 查找樹ADT――二叉查找樹 108 4.3.1 contains 110 4.3.2 findMin和findMax 111 4.3.3 insert 112 4.3.4 remove 113 4.3.5 析構(gòu)函數(shù)和拷貝構(gòu)造函數(shù) 115 4.3.6 平均情況分析 115 4.4 AVL樹 118 4.4.1 單旋轉(zhuǎn) 119 4.4.2 雙旋轉(zhuǎn) 121 4.5 伸展樹 128 4.5.1 一個簡單的想法(不能直接 使用) 128 4.5.2 展開 130 4.6 樹的遍歷 134 4.7 B樹 135 4.8 標(biāo)準(zhǔn)庫中的集合與映射 140 4.8.1 集合(set) 140 4.8.2 映射(map) 141 4.8.3 set和map的實現(xiàn) 142 4.8.4 使用多個映射(map)的例 142 小結(jié) 147 練習(xí) 147 參考文獻 153 第5章 散列 155 5.1 一般想法 155 5.2 散列函數(shù) 155 5.3 分離鏈接法 157 5.4 不用鏈表的散列表 161 5.4.1 線性探測法 161 5.4.2 平方探測法 163 5.4.3 雙散列 166 5.5 再散列 167 5.6 標(biāo)準(zhǔn)庫中的散列表 169 5.7 以最壞情形O(1)訪問的散列表 170 5.7.1 完美散列 170 5.7.2 杜鵑散列 172 5.7.3 跳房子散列 181 5.8 通用散列 184 5.9 可擴散列 186 小結(jié) 188 練習(xí) 189 參考文獻 193 第6章 優(yōu)先隊列(堆) 196 6.1 模型 196 6.2 一些簡單的實現(xiàn) 197 6.3 二叉堆 197 6.3.1 結(jié)構(gòu)性質(zhì) 197 6.3.2 堆序性質(zhì) 198 6.3.3 基本的堆操作 199 6.3.4 其他的堆操作 203 6.4 優(yōu)先隊列的應(yīng)用 206 6.4.1 選擇問題 206 6.4.2 事件模擬 207 6.5 d堆 208 6.6 左式堆 209 6.6.1 左式堆的性質(zhì) 209 6.6.2 左式堆操作 210 6.7 斜堆 215 6.8 二項隊列 216 6.8.1 二項隊列構(gòu)建 216 6.8.2 二項隊列操作 217 6.8.3 二項隊列的實現(xiàn) 219 6.9 標(biāo)準(zhǔn)庫中的優(yōu)先隊列 224 小結(jié) 225 練習(xí) 225 參考文獻 229 第7章 排序 232 7.1 預(yù)備知識 232 7.2 插入排序 233 7.2.1 算法 233 7.2.2 插入排序的STL實現(xiàn) 233 7.2.3 插入排序的分析 235 7.3 一些簡單排序算法的下界 235 7.4 希爾排序 236 7.4.1 希爾排序的最壞情形分析 237 7.5 堆排序 239 7.5.1 堆排序的分析 241 7.6 歸并排序 242 7.6.1 歸并排序的分析 245 7.7 快速排序 247 7.7.1 選取樞紐元 249 7.7.2 分割策略 250 7.7.3 小數(shù)組 252 7.7.4 實際的快速排序例程 252 7.7.5 快速排序的分析 254 7.7.6 選擇問題的線性期望時間 算法 256 7.8 排序算法的一般下界 258 7.8.1 決策樹 258 7.9 選擇問題的決策樹下界 260 7.10 對手下界(adversary lower bounds) 262 7.11 線性時間排序:桶式排序和 基數(shù)排序 265 7.12 外部排序 269 7.12.1 為什么需要一些新的算法 269 7.12.2 外部排序模型 269 7.12.3 簡單算法 269 7.12.4 多路合并 270 7.12.5 多相合并 271 7.12.6 替換選擇 272 小結(jié) 273 練習(xí)題 273 參考文獻 278 第8章 不相交集類 281 8.1 等價關(guān)系 281 8.2 動態(tài)等價性問題 281 8.3 基本數(shù)據(jù)結(jié)構(gòu) 283 8.4 靈巧求并算法 286 8.5 路徑壓縮 288 8.6 按秩求并和路徑壓縮的最壞 情形 289 8.6.1 緩慢增長的函數(shù) 289 8.6.2 通過遞歸分解進行的分析 290 8.6.3 一個O(M log*N)界 295 8.6.4 一個O(Mα(M, N))界 296 8.7 一個應(yīng)用 297 小結(jié) 299 練習(xí) 299 參考文獻 301 第9章 圖論算法 303 9.1 若干定義 303 9.1.1 圖的表示 304 9.2 拓撲排序 305 9.3 最短路徑算法 308 9.3.1 無權(quán)最短路徑 309 9.3.2 Dijkstra算法 312 9.3.3 具有負邊值的圖 317 9.3.4 無圈圖 318 9.3.5 所有頂點對間的最短路徑 320 9.3.6 最短路徑的例 320 9.4 網(wǎng)絡(luò)流問題 322 9.4.1 一個簡單的最大流算法 323 9.5 最小生成樹 326 9.5.1 Prim算法 327 9.5.2 Kruskal算法 329 9.6 深度優(yōu)先搜索的應(yīng)用 330 9.6.1 無向圖 331 9.6.2 雙連通性 332 9.6.3 歐拉回路 335 9.6.4 有向圖 338 9.6.5 查找強分支 339 9.7 NP完全性介紹 340 9.7.1 難與易 341 9.7.2 NP類 341 9.7.3 NP完全問題 342 小結(jié) 344 練習(xí) 344 參考文獻 350 第10章 算法設(shè)計技巧 353 10.1 貪婪算法 353 10.1.1 一個簡單的調(diào)度問題 354 10.1.2 哈夫曼編碼 355 10.1.3 近似裝箱問題 359 10.2 分治算法 366 10.2.1 分治算法的運行時間 367 10.2.2 最近點問題 369 10.2.3 選擇問題 371 10.2.4 一些算術(shù)問題的理論改進 374 10.3 動態(tài)規(guī)劃 377 10.3.1 用表代替遞歸 377 10.3.2 矩陣乘法的順序安排 379 10.3.3 最優(yōu)二叉查找樹 382 10.3.4 所有點對最短路徑 384 10.4 隨機化算法 386 10.4.1 隨機數(shù)發(fā)生器 387 10.4.2 跳躍表 392 10.4.3 素性測試 393 10.5 回溯算法 396 10.5.1 收費公路重建問題 396 10.5.2 博弈 400 小結(jié) 405 練習(xí) 406 參考文獻 413 第11章 攤還分析 418 11.1 一個無關(guān)的智力問題 418 11.2 二項隊列 419 11.3 斜堆 423 11.4 斐波那契堆 425 11.4.1 切除左式堆中的節(jié)點 425 11.4.2 二項隊列的懶惰合并 427 11.4.3 斐波那契堆操作 429 11.4.4 時間界的證明 430 11.5 伸展樹 432 小結(jié) 436 練習(xí) 436 參考文獻 437 第12章 高級數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn) 439 12.1 自頂向下伸展樹 439 12.2 紅黑樹 445 12.2.1 自底向上的插入 446 12.2.2 自頂向下紅黑樹 447 12.2.3 自頂向下刪除 452 12.3 treap樹 453 12.4 后綴數(shù)組和后綴樹 456 12.4.1 后綴數(shù)組 456 12.4.2 后綴樹 458 12.4.3 后綴數(shù)組和后綴樹的線性 時間構(gòu)建 461 12.5 k-d樹 471 12.6 配對堆 474 小結(jié) 479 練習(xí) 479 參考文獻 483 附錄A 類模板的分離式編譯 486 索引 489
你還可能感興趣
我要評論
|