Java軟件結(jié)構與數(shù)據(jù)結(jié)構

前言

　　本書可用作數(shù)據(jù)結(jié)構與算法課程的教材。數(shù)據(jù)結(jié)構與算法課程常常稱為CS2課程，因為它通常作為計算機專業(yè)的第二門課程。本書涵蓋了計算機專業(yè)課程設置2001（Computing Curricula 2001，CC2001）的宗旨?！　慕虒W的角度看，本書遵循了一流的CS1教材“Java Software Solutions：Foundations of Program Design”（作者John Lewis與William Loftus）一書的風格和方法。本書使用了在該書中受到很高評價的一些特色，比如關鍵概念框和完整代碼示例。作為計算機專業(yè)學生的兩門或者三門導論課程，這兩本書提供了一個堅實而系統(tǒng)的教學方案。也就是說，本書不要求學生在以前的課程中已經(jīng)使用過Java Software Solutions一書。　　在CS1和CS2課程中出現(xiàn)的內(nèi)容（比如遞歸或排序），本書也同樣進行了闡述。本書還給出了一些有用的參考材料，介紹了面向?qū)ο蟮母拍钜约叭绾卧贘ava中實現(xiàn)。　　我們知道，數(shù)據(jù)結(jié)構與算法在計算機專業(yè)課程中起著關鍵的作用，我們認為，本書能較好地滿足該課程的要求。　　本書第3版　　在第3版中，我們對本書進行了一些重要的修改，以適應教學需要。最重要的修改是，對本書的基本結(jié)構進行了重新設計，以使得這些內(nèi)容之間的脈絡更加清晰。本版不是用一大章來復習面向?qū)ο蟮母拍?，而是把這些內(nèi)容作為一個附錄以供參考。然后在全書需要的地方對這些概念進行復習，并介紹其實現(xiàn)策略的上下文，引用適當?shù)膮⒖疾牧?。這不僅可以適時地把這些內(nèi)容鏈接起來，而且還演示了特定語言結(jié)構的使用。　　本版對算法分析的討論進行了擴展，并把算法分析作為了單獨的一章。但是，這些討論也只是停留在恰當?shù)碾y度上。本書的策略是，只對算法分析的基本概念進行介紹，而不是進行很深入的討論。　　另一個重要的結(jié)構變化是，對集合的介紹使用了一個棧作為基本示例。在本書的上一版本中，我們以一種抽象的方法來介紹集合，即把它與核心數(shù)據(jù)結(jié)構分開，使用諸如背包或組集之類的示例。這種方法凸顯這樣一個事實：從概念上來說，棧是很簡單的。使用它作為第一個示例，可以增進把集合作為一個整體的理解。　　本書的上一版本用了幾個章節(jié)來介紹幾個大型案例研究，這些案例研究使用集合來求解實際問題。很多教師覺得這些很有用，但他們同時覺得這會打斷對核心內(nèi)容的介紹。因此，在這一版本中，我們把這些案例研究章節(jié)從書中刪除了，并把它們作為輔助材料放在本書配套的網(wǎng)站上。我們鼓勵教師去下載這些材料，并以他們認為適合的方式使用這些　 材料?！　∽詈螅覀儗Ρ景孢M行了重新審閱，并改進了一些討論。我們擴展了對圖的討論，把“圖”與“散列”兩章的順序進行了調(diào)換，使得脈絡更清晰。本版還添加了一章來專門討論Set與Map集合?！　∥覀冋J為，以上這些修改，都是建立在使用以前版本教學的基礎上，為教師提供更多的機會和更好的靈活性來介紹本書的內(nèi)容。　　本書的寫作風格　　這種類型的圖書在整體寫作方法上的差別相當大。本書的寫作方法是建立在一些我們強烈推薦的重要原則之上的。首先，我們以一種連貫敘述的方式介紹在本書中將要考察的各種集合。其次，我們強調(diào)完美軟件設計技巧的重要性。第三，我們對本書結(jié)構加以組織以支持和強化本書的重要目標：即數(shù)據(jù)結(jié)構與算法的學習。我們將更深入地考察這些原則?！　∵B 貫 敘 述　　當考察某種類型的集合時，將按照以下順序仔細解決每一問題?！　?. 概念：我們會從概念上討論集合，并構建它所提供的服務（其接口）?！　?. 用途：我們將介紹一些示例，闡述在求解問題時，集合的特定屬性是如何派上用場的（不用管集合是如何被實現(xiàn)的）?！　?. 實現(xiàn)：我們將考察集合的各種實現(xiàn)?！　?. 分析：我們對各種實現(xiàn)進行了比較和區(qū)分。　　在恰當?shù)臅r候，我們將討論Java Collections API。如果有必要討論API中某個特定集合類型，那么我們將討論該集合及其實現(xiàn)。因此，我們歡迎API，但并不完全局限于它。并且，我們會毫不猶豫地指出其缺陷。　　分析步驟是一個較高的層次。在第2章介紹的大O記法的概念將全書中應用，但這更多地是直覺上而不是數(shù)學上的分析?！　⊥昝赖某绦蛟O計　　全書始終將完美的軟件工程實踐置于一個高度優(yōu)先的地位。我們對集合實現(xiàn)的設計以及對使用它們的程序的設計都將遵循一致和恰當?shù)臉藴??！　⒓系慕涌谂c其底層實現(xiàn)分隔開，是非常重要的。某一集合提供的服務，通常在Java接口中有著正式定義。為了強化該集合為一個抽象的思想，只要合適，我們都將接口名稱用作該集合的類型指定?！　〕藢嵺`堅實的設計原則外，我們還在全書的論述中對其進行了強調(diào)。我們努力嘗試既通過示例又通過不斷強化的方式來進行教學?！　∏逦慕M織結(jié)構　　我們對本書內(nèi)容進行了精心組織，以將偏離主題帶來的干擾降到最低，并對本書的總體目標進行強化。本書的組織使得本書既可以用作數(shù)據(jù)結(jié)構與算法的教學用書，又可以作為一本頗有價值的參考用書。　　本書的內(nèi)容可以劃分為多個部分：第一部分包括前兩章，介紹了集合的概念和算法分析。第二部分包括隨后的4章，介紹了數(shù)據(jù)結(jié)構與算法以及影響它們的基本問題，并介紹線性集合（棧、隊列和列表）。第三部分介紹了遞歸、排序和查找的概念。第四部分介紹了線性集合（樹、堆、散列和圖）。除樹之外的每一個集合類型都自成一章。有關樹的內(nèi)容分布于一系列的章節(jié)中，用于考察其各個方面和各種作用?！　≌?節(jié) 劃 分　　第1章（概述）討論了軟件質(zhì)量涉及的各個方面，并對軟件開發(fā)問題進行了一個全面概述。本章用于在著手數(shù)據(jù)結(jié)構和算法設計的細節(jié)之前，建立一套正確的開發(fā)思想。　　第2章（算法分析）介紹了確定算法效率的基礎知識，并闡述了一個重要的標準，使得開發(fā)人員可以以正確的方式將一種算法與另一種算法進行比較。本章的重點是理解重要的概念，而不是陷入數(shù)學或公式的漩渦?！　〉?章（集合）建立了集合的概念，強調(diào)了將接口和實現(xiàn)區(qū)分開來的必要性。本章還從概念上介紹了棧，然后闡述了基于數(shù)組的棧的實現(xiàn)?！　〉?章（鏈式結(jié)構）討論了使用引用來創(chuàng)建鏈式數(shù)據(jù)結(jié)構。本章考察了有關鏈表管理的基本問題，然后使用基本鏈式數(shù)據(jù)結(jié)構（在第3章中已介紹），定義棧的另一種實現(xiàn)方法。　　第5章（隊列）考察了先進先出隊列的概念和實現(xiàn)。本章通過一個高效使用隊列的示例來討論基數(shù)排序。本章所介紹的實現(xiàn)包括基本鏈表以及定長和環(huán)形數(shù)組?！　〉?章（列表）論述了3種類型的列表：有序表、無序表和索引表。通過討論這3種類型列表所共有的及各自獨有的操作來對它們進行比較和區(qū)分。在各種類型的列表設計中，我們將恰當?shù)厥褂美^承，且通過基于數(shù)組的和鏈式的表示兩種方式實現(xiàn)這些列表。　　第7章（遞歸）概要介紹了遞歸的概念，以及遞歸解決方案為什么是優(yōu)美的。本章還探討了遞歸的實現(xiàn)細節(jié)，并討論了遞歸算法分析的基本思想。　　第8章（排序與查找）討論了線性查找和二分查找算法，以及若干排序的算法（如選擇排序、插入排序、冒泡排序、快速排序以及歸并排序）。本章著重討論與查找和排序相關的編程問題，比如將Comparable接口用作對象比較的基礎。以特定數(shù)據(jù)結(jié)構為基礎的查找與排序（如堆排序）將在本書后面的適當章節(jié)討論。　　第9章（樹）對樹進行了概述，并構建了關鍵的術語和概念。本章討論了各種實現(xiàn)方式，并通過一個二叉樹來表示和評估某一算數(shù)表達式?！　〉?0章（二叉查找樹）利用第9章構建的基本概念，定義了一個經(jīng)典的二叉查找樹。本章先考察了一個二叉查找樹的鏈式實現(xiàn)，然后討論了樹結(jié)點的平衡如何對其性能起到關鍵作用。這就引出了AVL和二叉查找樹的紅/黑實現(xiàn)的介紹。　　第11章（優(yōu)先隊列與堆）探討了堆的概念、使用和實現(xiàn)，尤其是與優(yōu)先隊列的關系。我們通過一個堆排序來舉例說明其用途。本章還介紹了鏈式實現(xiàn)和基于數(shù)組的實現(xiàn)?！　〉?2章（多路查找樹）是前面章節(jié)的自然延伸。本章討論了2-3樹、2-4樹以及廣義B樹的概念，還討論了各種實現(xiàn)。　　第13章（圖）探討了無向圖和有向圖的概念，并構建了一些重要的術語。本章考察了若干常用圖的算法，并討論了各種實現(xiàn)，包括鄰接矩陣?！　〉?4章（散列）包括散列的概念及其相關問題，比如散列函數(shù)及沖突。本章討論了散列的各種Java Collections API。　　第15章（Set與Map集合）介紹了這兩者類型的集合及其對Java Collections API的重要性。　　附錄A（UML）概述了統(tǒng)一建模語言。UML是表示面向?qū)ο笙到y(tǒng)的事實標準表示法?！　「戒汢（面向?qū)ο笤O計）為任何需要回顧面向?qū)ο蟮幕靖拍罴捌湓贘ava中如何實現(xiàn)等內(nèi)容的讀者提供參考。該章包含的概念包括抽象、類、封裝、繼承、多態(tài)性以及許多相關的Java語言結(jié)構，比如接口?！　〗?輔 資 料　　本書的所有讀者都可以在www.aw.com/cssupport網(wǎng)址上獲得以下教輔資料。　　* 本書中出現(xiàn)的所有程序的源代碼?！　? 完整的案例研究程序，包括Black Jack Game、Calculator、Family Tree Program和Web Crawler程序?！　≡赑earson Education的教師資源中心（網(wǎng)址是http：//www.pearsonhighered.com/irc）里的以下教輔資料僅限于滿足條件的教師。請訪問該網(wǎng)址，與你當?shù)氐腜earson Education銷售代表聯(lián)系，或者發(fā)送電子郵件至computing@pearson.com，咨詢有關資料獲取的信息。　　* 本書中的部分練習題和編程項目的答案?！　? 測試題庫，含有測驗用的問題?！　? 講解本書內(nèi)容的PowerPoint幻燈片。

內(nèi)容概要

本書是著名作者John Lewis與Joseph Chase作為其一流的CSI教材“Java Software Solutions：Foundations of Program Design”的姊妹篇。盡管《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》的英文名為“Java Software Structures：Designing and Using Data Structures”，但正如作者在前言中所說的那樣，《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》其實是一本可作為“數(shù)據(jù)結(jié)構與算法”課程的教材。根據(jù)使用了前兩版的教師和學生的反饋，作者在第3版中進行了重大修改，以適應教學的需要。最重要的修改包括這樣幾個方面：    （1）對《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》的基本結(jié)構進行了重新設計，以使得這些內(nèi)容之間的脈絡更加清晰；    （2）第3版把對面向?qū)ο蟾拍畹膹土曌鳛橐粋€附錄以供參考；    （3）上一版給出了幾個完整的Java程序設計案例和源代碼，在第3版中進行了刪除，并把這幾個程序案例源代碼放在了網(wǎng)上供讀者下載。譯者認為，這不僅壓縮了不少篇幅，而且使得《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》更像是一本數(shù)據(jù)結(jié)構與算法的教材，而不是Java程序設計的教材；    （4）第3版擴展了對圖的討論，把“圖”與“散列”兩章的順序進行了調(diào)換，使得脈絡更清晰。本版還添加了一章來專門討論Set與Map集合。    總之，這些修改都是建立在使用以前版本教學的基礎上，為教師提供更多的機會和更好的靈活性來使用《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》。

書籍目錄

第1章 概述  1.1 軟件質(zhì)量    1.1.1 正確性    1.1.2 可靠性    1.1.3 健壯性    1.1.4 可用性    1.1.5 可維護性    1.1.6 可重用性    1.1.7 可移植性     1.1.8 運行效率    1.1.9 質(zhì)量問題  1.2 數(shù)據(jù)結(jié)構    1.2.1 一個物理示例    1.2.2 以集裝箱作為對象  關鍵概念小結(jié)  自測題  練習題  自測題答案第2章 算法分析  2.1 算法效率分析  2.2 增長函數(shù)與大O記法   2.3 增長函數(shù)的比較   2.4 時間復雜度分析     2.4.1 循環(huán)運行的復雜度分析     2.4.2 嵌套循環(huán)的復雜度分析     2.4.3 方法調(diào)用的復雜度分析   關鍵概念小結(jié)   自測題   練習題   自測題答案   參考文獻 第3章 集合   3.1 概述     3.1.1 抽象數(shù)據(jù)類型     3.1.2 Java集合API   3.2 棧集合   3.3 主要的面向?qū)ο蟾拍?    3.3.1 繼承     3.3.2 類層次    3.3.3 Object類     3.3.4 多態(tài)性     3.3.5 引用與類層次     3.3.6 泛型   3.4 棧ADT     接口   3.5 使用棧計算后綴表達式  3.6 異常     3.6.1 異常消息     3.6.2 try語句     3.6.3 異常傳播   3.7 用數(shù)組實現(xiàn)棧     管理容量   3.8 ArrayStack類     3.8.1 構造函數(shù)     3.8.2 push操作     3.8.3 pop操作     3.8.4 peek操作     3.8.5 其他操作   關鍵概念小結(jié)   自測題   練習題   程序設計項目   自測題答案 第4章 鏈式結(jié)構   4.1 鏈接作為引用   4.2 管理鏈表     4.2.1 訪問元素     4.2.2 插入結(jié)點     4.2.3 刪除結(jié)點     4.2.4 啞結(jié)點   4.3 無鏈接的元素     雙向鏈表   4.4 用鏈表實現(xiàn)棧     4.4.1 LinkedStack類     4.4.2 push操作     4.4.3 pop操作     4.4.4 其他操作   4.5 使用棧來穿越迷宮   4.6 java.util.Stack類實現(xiàn)棧     4.6.1 獨有的操作     4.6.2 繼承與實現(xiàn)  關鍵概念小結(jié)   自測題   練習題   程序設計項目   自測題答案 第5章 隊列第6章 列表第7章 遞歸第8章 排序與查找第9章 樹第10章 二叉查找樹第11章 優(yōu)先隊列與堆第12章 多路查找樹第13章 圖第14章 散列第15章 Set與Map集合附錄A UML附錄B 面向?qū)ο笤O計

章節(jié)摘錄

　　但是，在這種情景下，如果要創(chuàng)建一個為Map集合的有序列表，就要創(chuàng)建一個表示每個員工的名字的類，以及一個指向第二個類的引用。第二個類含有員工數(shù)據(jù)的其他所有信息。我們?nèi)缓笥糜行蛄斜聿僮靼训谝粋€類加載到我們的列表中，而第二個類的對象存在于內(nèi)存中。這里第一個類稱為關鍵字，而第二個類稱為數(shù)據(jù)?！　∮眠@種方式，當我們操作列表的元素時，只需處理關鍵字、名稱和引用，與需要操作和員工有關的所有數(shù)據(jù)相比，此時需要的內(nèi)存要少得多。這里還有一個優(yōu)點，那就是當相同的員工數(shù)據(jù)被多個Map引用時，無須使用多個副本。因此，如果一個應用程序用棧來表示員工信息，而另一個應用程序則用有序列表來表示，那么我們就可以把關鍵字加載到棧中，把匹配的關鍵字加載到有序列表，此時實際的數(shù)據(jù)只有一個實例。與處理別名（即多個指向相同對象的引用）的情況一樣，因為對象只有一個實例，因此，當需要通過一個引用來修改某個對象時，由于該對象同時被其他引用所引用，因此必須非常小心?！　≡诘?0章中，我們討論了TreeSet和TreeMap的Java集合API實現(xiàn)。在第14章中，我們討論了使用散列的Java集合API實現(xiàn)。注意，這些Set實現(xiàn)違反了Set集合的代數(shù)表示。該Set集合的元素是無序的。除此之外，還有一些其他類實現(xiàn)了java.util.Set或java.util.Map接口。這就是為什么Java語言的設計者在很多情況下使用Set和Map集合，而不是我們本書中所介紹的傳統(tǒng)數(shù)據(jù)結(jié)構。簡單地說，Java語言不是教學語言，而是用于快速而高效地解決工業(yè)問題的語言。因此，很多Java解決方案很適用但不那么優(yōu)美?！　‘斎唬瑢α⒌膯栴}也同樣重要。既然Java語言的設計者選擇使用Set和Map，而不是本書所介紹的傳統(tǒng)數(shù)據(jù)結(jié)構，那么我們?yōu)槭裁椿ㄟ@么多的時間來介紹傳統(tǒng)數(shù)據(jù)結(jié)構呢？對這個問題有很多很好的答案，但這里有一個答案可以超越其他所有答案。盡管Java是一種很好的語言，但它并不是你的職業(yè)生涯中將遇到的唯一語言。在我們短暫的職業(yè)生涯中，語言來來去去很多次，但數(shù)據(jù)結(jié)構的基本原則仍保持不變。因此，我們學習這些基本原則很重要，這樣我們就不會重復犯過去的錯誤。關鍵概念小結(jié)　　·Set是一種非線性集合。在該集合中的元素之間基本上沒有任何組織結(jié)構。

編輯推薦

　　《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》的寫作方法是建立在一些我們強烈推薦的重要原則之上的。首先，我們以一種連貫敘述的方式介紹在《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》中將要考察的各種集合。其次，我們強調(diào)完美軟件設計技巧的重要性。第三，我們對《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》結(jié)構加以組織以支持和強化《Java軟件結(jié)構與數(shù)據(jù)結(jié)構(第3版)》的重要目標：即數(shù)據(jù)結(jié)構與算法的學習。我們將更深入地考察這些原則。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    Java軟件結(jié)構與數(shù)據(jù)結(jié)構 PDF格式下載

---