數(shù)據(jù)結(jié)構(gòu)與算法分析

前言

計算機(jī)功能的增強(qiáng)、速度的提高和應(yīng)用的普及，增長了人們對實用算法分析和高效編程實現(xiàn)的需求。在Java語言廣泛使用的今天，希望我們這樣一本兼顧普及和提高的數(shù)據(jù)結(jié)構(gòu)與算法分析教材能夠?qū)V大讀者有所裨益。本書為《Data Structures and Algorithm Analysis in Java》第2版的中譯本。

內(nèi)容概要

　　本書是國外數(shù)據(jù)結(jié)構(gòu)與算法分析方面的經(jīng)典教材，使用卓越的Java編程語言作為實現(xiàn)工具討論了數(shù)據(jù)結(jié)構(gòu)（組織大量數(shù)據(jù)的方法）和算法分析（對算法運(yùn)行時間的估計）。　　隨著計算機(jī)速度的不斷增加和功能的日益強(qiáng)大，人們對有效編程和算法分析的要求也不斷增長。本書把算法分析與最有效率的Java程序的開發(fā)有機(jī)地結(jié)合起來，深入分析每種算法，內(nèi)容全面、縝密嚴(yán)格，并細(xì)致講解精心構(gòu)造程序的方法。

作者簡介

Mark Allen Weiss擁有普林斯頓大學(xué)計算機(jī)科學(xué)博士學(xué)位，現(xiàn)在是佛羅里達(dá)國際大學(xué)計算機(jī)學(xué)院教授。他是著名的計算機(jī)教育專家，在數(shù)據(jù)結(jié)構(gòu)與算法分析方面卓有建樹，著有多部暢銷書籍，其中包括：《Data Structures and Problem Solvin9：Using Java》、《Data Structures an

書籍目錄

出版者的話?譯者序?前言??第1章　引論　1.1　本書討論的內(nèi)容　1.2　數(shù)學(xué)知識復(fù)習(xí)　　1.2.1　指數(shù)　　1.2.2　對數(shù)　　1.2.3　級數(shù)　　1.2.4　模運(yùn)算　　1.2.5　證明的方法　1.3　遞歸簡論　1.4　實現(xiàn)泛型特性構(gòu)件pre-Java5?　　1.4.1　使用Object表示泛型　　1.4.2　基本類型的包裝　　1.4.3　使用接口類型表示泛型　　1.4.4　數(shù)組類型的兼容性　1.5　利用Java5泛性實現(xiàn)泛型特性成分　　1.5.1　簡單的泛型類和接口?　　1.5.2　自動裝箱/拆箱　　1.5.3　帶有限制的通配符　　1.5.4　泛型static方法　　1.5.5　類型限界　　1.5.6　類型擦除　　1.5.7　對于泛型的限制　　1.6　函數(shù)對象　小結(jié)　練習(xí)　參考文獻(xiàn)第2章　算法分析　2.1　數(shù)學(xué)基礎(chǔ)　2.2　模型　2.3　要分析的問題　2.4　運(yùn)行時間計算　　2.4.1　一個簡單的例子　　2.4.2　一般法則　　2.4.3　最大子序列和問題的求解　　2.4.4　運(yùn)行時間中的對數(shù)　　2.4.5　檢驗?zāi)愕姆治觥　?.4.6　分析結(jié)果的準(zhǔn)確性　小結(jié)　練習(xí)　參考文獻(xiàn)第3章　表、棧和隊列　3.1　抽象數(shù)據(jù)類型　3.2　表ADT　　3.2.1　表的簡單數(shù)組實現(xiàn)　　3.2.2　簡單鏈表　3.3　JavaCollectionsAPI中的表　　3.3.1　Collection接口　　3.3.2　Iterator接口　　3.3.3　List接口、ArrayList類和?LinkedList類　　3.3.4　例：remove方法對LinkedList?類的使用　　3.3.5　關(guān)于ListIterator接口　3.4　ArrayList類的實現(xiàn)　　3.4.1　基本類　　3.4.2　迭代器、Java嵌套類和?內(nèi)部類　3.5　LinkedList類的實現(xiàn)　3.6　棧ADT　　3.6.1　棧模型　　3.6.2　棧的實現(xiàn)　　3.6.3　應(yīng)用　3.7　隊列ADT　　3.7.1　隊列模型　　3.7.2　隊列的數(shù)組實現(xiàn)　　3.7.3　隊列的應(yīng)用　小結(jié)　練習(xí)第4章　樹　4.1　預(yù)備知識　　4.1.1　樹的實現(xiàn)　　4.1.2　樹的遍歷及應(yīng)用　4.2　二叉樹　　4.2.1　實現(xiàn)　　4.2.2　例子：表達(dá)式樹　4.3　查找樹ADT——二叉查找樹?　　4.3.1　contains方法　　4.3.2　findMin方法和findMax方法　　4.3.3　insert方法　　4.3.4　remove方法　　4.3.5　平均情況分析　4.4　AVL樹　　4.4.1　單旋轉(zhuǎn)　　4.4.2　雙旋轉(zhuǎn)　4.5　伸展樹　　4.5.1　一個簡單的想法（不能直接使用）　　4.5.2　展開　4.6　樹的遍歷　4.7　B樹　4.8　標(biāo)準(zhǔn)庫中的集合與映射　　4.8.1　關(guān)于Set接口　　4.8.2　關(guān)于Map接口　　4.8.3　TreeSet類和TreeMap類的實現(xiàn)　?4.8.4　使用多個映射的例　小結(jié)　練習(xí)　參考文獻(xiàn)第5章　散列　5.1　一般想法　5.2　散列函數(shù)　5.3　分離鏈接法　5.4　不用鏈表的散列表　　5.4.1　線性探測法　　5.4.2　平方探測法　　5.4.3　雙散列　5.5　再散列　5.6　標(biāo)準(zhǔn)庫中的散列表　5.7　可擴(kuò)散列　小結(jié)　練習(xí)　參考文獻(xiàn)第6章　優(yōu)先隊列（堆）　6.1　模型　6.2　一些簡單的實現(xiàn)　6.3　二叉堆　　6.3.1　結(jié)構(gòu)性質(zhì)　　6.3.2　堆序性質(zhì)　　6.3.3　基本的堆操作　　6.3.4　其他的堆操作　6.4　優(yōu)先隊列的應(yīng)用　　6.4.1　選擇問題　　6.4.2　事件模擬　6.5　d-堆?　6.6　左式堆　　6.6.1　左式堆性質(zhì)　　6.6.2　左式堆操作　6.7　斜堆　6.8　二項隊列　　6.8.1　二項隊列結(jié)構(gòu)　　6.8.2　二項隊列操作　　6.8.3　二項隊列的實現(xiàn)　6.9　標(biāo)準(zhǔn)庫中的優(yōu)先隊列　小結(jié)　練習(xí)　參考文獻(xiàn)第7章　排序　7.1　預(yù)備知識　7.2　插入排序　　7.2.1　算法　　7.2.2　插入排序的分析　7.3　一些簡單排序算法的下界　7.4　希爾排序　7.5　堆排序　7.6　歸并排序　7.7　快速排序　　7.7.1　選取樞紐元　　7.7.2　分割策略　　7.7.3　小數(shù)組　　7.7.4　實際的快速排序例程　　7.7.5　快速排序的分析　　7.7.6　選擇問題的線性期望時間算法　7.8　排序算法的一般下界　7.9　桶式排序　7.10　外部排序　　7.10.1　為什么需要一些新的算法　　7.10.2　外部排序模型　　7.10.3　簡單算法　　7.10.4　多路合并　　7.10.5　多相合并　　7.10.6　替換選擇　小結(jié)　練習(xí)題　參考文獻(xiàn)第8章　不相交集類　8.1　等價關(guān)系　8.2　動態(tài)等價性問題　8.3　基本數(shù)據(jù)結(jié)構(gòu)　8.4　靈巧求并算法　8.5　路徑壓縮　8.6　路徑壓縮和按秩求并的最壞情形　8.7　一個應(yīng)用　小結(jié)　練習(xí)題　參考文獻(xiàn)第9章　圖論算法　9.1　若干定義　9.2　拓?fù)渑判颉?.3　最短路徑算法　　9.3.1　無權(quán)最短路徑　　9.3.2　Dijkstra算法　　9.3.3　具有負(fù)邊值的圖　　9.3.4　無圈圖　　9.3.5　所有點對最短路徑　　9.3.6　最短路徑的例子　9.4　網(wǎng)絡(luò)流問題　9.5　最小生成樹　　9.5.1　Prim算法　　9.5.2　Kruskal算法　9.6　深度優(yōu)先搜索的應(yīng)用　　9.6.1　無向圖　　9.6.2　雙連通性　　9.6.3　歐拉回路　　9.6.4　有向圖　　9.6.5　查找強(qiáng)分支　9.7　NP完全性介紹　　9.7.1　難與易　　9.7.2　NP類　　9.7.3　NP完全問題　小結(jié)　練習(xí)　參考文獻(xiàn)第10章　算法設(shè)計技巧　10.1　貪婪算法　　10.1.1　一個簡單的調(diào)度問題　　10.1.2　哈夫曼編碼　　10.1.3　近似裝箱問題　10.2　分治算法　　10.2.1　分治算法的運(yùn)行時間　　10.2.2　最近點問題　　10.2.3　選擇問題　　10.2.4　一些算術(shù)問題的理論改進(jìn)　10.3　動態(tài)規(guī)劃　　10.3.1　用一個表代替遞歸　　10.3.2　矩陣乘法的順序安排　　10.3.3　最優(yōu)二叉查找樹　　10.3.4　所有點對最短路徑　10.4　隨機(jī)化算法　　10.4.1　隨機(jī)數(shù)發(fā)生器　　10.4.2　跳躍表　　10.4.3　素性測試　10.5　回溯算法　　10.5.1　收費(fèi)公路重建問題　　10.5.2　博弈　小結(jié)　練習(xí)　參考文獻(xiàn)第11章　攤還分析　11.1　一個無關(guān)的智力問題　11.2　二項隊列　11.3　斜堆　11.4　斐波那契堆　　11.4.1　切除左式堆中的節(jié)點　　11.4.2　二項隊列的懶惰合并　　11.4.3　斐波那契堆操作　　11.4.4　時間界的證明　11.5　伸展樹　小結(jié)　練習(xí)　參考文獻(xiàn)第12章　高級數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)　12.1　自頂向下伸展樹　12.2　紅黑樹　　12.2.1　自底向上的插入　　12.2.2　自頂向下紅黑樹　　12.2.3　自頂向下的刪除　12.3　確定性跳躍表　12.4　AA樹　12.5　treap樹　12.6　kd樹?　12.7　配對堆　小結(jié)　練習(xí)　參考文獻(xiàn)索引

章節(jié)摘錄

第1章 引論在這一章，我們闡述本書的目的和目標(biāo)并簡要復(fù)習(xí)離散數(shù)學(xué)以及程序設(shè)計的一些概念。我們將要看到程序?qū)τ诤侠淼拇罅枯斎氲倪\(yùn)行性能與其在適量輸入下運(yùn)行性能的同等重要性。概括為本書其余部分所需要的基本的數(shù)學(xué)基礎(chǔ)。簡要復(fù)習(xí)遞歸。概括用于本書的Java語言的某些重要特點。1.1本書討論的內(nèi)容設(shè)有一組N個數(shù)而要確定其中第k個最大者。我們稱之為選擇問題（selectionproblem）。大多數(shù)學(xué)習(xí)過一兩門程序設(shè)計課程的學(xué)生寫一個解決這種問題的程序不會有什么困難?！懊黠@的”解決方法是相當(dāng)多的。該問題的一種解法就是將這N個數(shù)讀進(jìn)一個數(shù)組中，再通過某種簡單的算法，比如冒泡排序法，以遞減順序?qū)?shù)組排序，然后返回位置k上的元素。稍微好一點的算法可以先把前k個元素讀人數(shù)組并（以遞減的順序）對其排序。接著，將剩下的元素再逐個讀入。當(dāng)新元素被讀到時，如果它小于數(shù)組中的第k個元素則忽略之，否則就將其放到數(shù)組中正確的位置上，同時將數(shù)組中的一個元素擠出數(shù)組。當(dāng)算法終止時，位于第k個位置上的元素作為答案返回。這兩種算法編碼都很簡單，建議讀者試一試。此時我們自然要問：哪個算法更好？哪個算法更重要？還是兩個算法都足夠好？使用一千萬個元素的隨機(jī)文件和k=5000000進(jìn)行模擬將發(fā)現(xiàn)，兩個算法在合理的時間量內(nèi)均不能結(jié)束；每種算法都需要計算機(jī)處理若干天才能算完（雖然最后還是給出了正確的答案）。在第7章將討論另一種算法，該算法將在一秒鐘左右給出問題的解。因此，雖然我們提出的兩個算法都能算出結(jié)果，但是它們不能被認(rèn)為是好的算法，因為對于第三種算法能夠在合理的時間內(nèi)處理的輸入數(shù)據(jù)量而言，這兩種算法是完全不切實際的。第二個問題是解決一個流行的字謎。輸人是由一些字母構(gòu)成的一個二維數(shù)組以及一組單詞組成。目標(biāo)是要找出字謎中的單詞，這些單詞可能是水平、垂直或沿對角線上任何方向放置的。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)與算法分析:Java語言描述(第2版)》的特色如下：全面闡述新的Java 5.0編程語言和Java Collections庫。改進(jìn)內(nèi)部設(shè)計，用圖和實例闡述算法的實施步驟。第3章對表、棧和隊列的討論進(jìn)行了全面修訂。用一章專門討論攤還分析和一些高級數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。每章末尾的大量練習(xí)按照難易程度編排，以增強(qiáng)對關(guān)鍵概念的理解。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu)與算法分析 PDF格式下載

---