-- 會員 / 註冊 --  
 帳號:
 密碼:
  | 註冊 | 忘記密碼
3/26 新書到! 3/19 新書到! 3/14 新書到! 12/12 新書到!
購書流程Q & A站務留言版客服信箱
3ds MaxMayaRhinoAfter EffectsSketchUpZBrushPainterUnity
PhotoShopAutoCadMasterCamSolidWorksCreoUGRevitNuke
C#CC++Java遊戲程式Linux嵌入式PLCFPGAMatlab
駭客資料庫搜索引擎影像處理FluentVR+ARANSYS深度學習
單晶片AVROpenGLArduinoRaspberry Pi電路設計CadenceProtel
HadoopPythonStm32CortexLabview手機程式AndroidiPhone
可查書名,作者,ISBN,3dwoo書號
詳細書籍分類

數據結構與抽象(Java版)(第三版)

( 簡體 字)
作者:張引 等類別:1. -> 程式設計 -> JAVA -> Java
譯者:
出版社:電子工業出版社數據結構與抽象(Java版)(第三版) 3dWoo書號: 45435
詢問書籍請說出此書號!

缺書
NT售價: 445

出版日:10/1/2016
頁數:632
光碟數:0
站長推薦:
印刷:黑白印刷語系: ( 簡體 版 )
加入購物車 加到我的最愛
(請先登入會員)
ISBN:9787121276163
作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 
(簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證)
作者序:

譯者序:

前言:

作者的話
歡迎大家閱讀《數據結構與抽象(Java版)(第三版)》。這是一本針對數據結構入門課程(通常被稱為CS-2)而編寫的書, 它可以作為我寫的另外一本書Imagine!Java的續篇。
無論是一名教師還是一位學生, 我想告訴你, 這本書的撰寫是基于我執教本科計算機科學課程30余年的經驗。我希望這本書具有很好的讀者友好性, 使學生可以毫不費力地學, 教師可以事半功倍地教。為了達到這個目標, 你會發現學習材料是以小塊——我稱之為“小節”——的形式組織的, 這樣易于消化學習內容, 促進學習。本書用大量模擬現實世界問題的例子作為新素材, 幫助學生更好地學習和掌握抽象概念。并使用大量簡單的圖表闡明、 厘清了復雜的思想。
我希望你喜歡讀這本書。像很多已經讀過此書的讀者一樣, 可以有效且不斷地學習或者講授數據結構。
本書所包含的主題涉及各種數據組織方法的處理, 可以使應用程序高效地訪問和操作數據。這些主題是以后學習計算機科學的基礎, 因為它們提供了創建復雜和可靠的軟件所需要的基礎知識。無論是對設計電子游戲感興趣還是喜歡開發機器人控制手術的軟件, 數據結構的學習對成功而言都至關重要。即使現在不打算學習本書中的所有主題, 以后也有可能會接觸到它們。衷心希望大家喜歡閱讀本書, 并希望它成為未來課程學習的有用參考工具。
在看完這個前言之后, 讀者應該閱讀一下引言。這樣就可以快速地了解它的主要內容, 以及在開始學習前所需要了解的相關Java的知識。附錄A到附錄G回顧了Java的基礎知識、 類、 繼承、 異常、 文件和javadoc風格的注釋。請注意, 在本書的最后還給出了Java的保留字、 基本數據類型、 運算符的優先級和Unicode字符的列表。
另外, 請一定要瀏覽此前言的剩余部分, 從而了解本書將對你的學習有幫助的特色之處。
組織結構
本書主題的組織、 順序的安排和內容展開的幅度都更易于學習和教學。它使讀者一次專注于一個概念, 為讀者提供主題學習順序的靈活性, 并清晰地區分抽象數據類型(ADT)的說明和具體實現。為了達到這些目標, 本書將內容組織成30章, 每章都由一些短小的編了號的小節組成, 每個小節講解一個概念。每一章或是講述一個ADT的說明, 或是講述它的實現。讀者可以選擇在了解一個ADT的說明后緊接著學習它的實現, 也可以選擇在考慮任何實現問題之前先探討若干個ADT的說明和使用。本書的組織結構可以使讀者方便地選擇自己喜歡的主題順序進行閱讀。
內容一覽表
下面的各章名稱列表顯示了本書內容的整體組成情況。下面將會更進一步地描述各個章節的主要內容。
第1章 袋子
第2章 用數組實現袋子
第3章 用鏈表實現袋子
第4章 算法的效率
第5章 棧
第6章 棧的實現
第7章 遞歸
第8章 排序引論
第9章 快速排序方法
第10章 隊列、 雙端隊列和優先隊列
第11章 隊列、 雙端隊列和優先隊列的實現
第12章 線性表
第13章 用數組實現線性表
第14章 用鏈表實現線性表
第15章 迭代器
第16章 有序表
第17章 繼承及線性表
第18章 查找
第19章 詞典
第20章 詞典的實現
第21章 散列概述
第22章 用散列實現詞典
第23章 樹
第24章 樹的實現
第25章 二叉查找樹的實現
第26章 堆的實現
第27章 平衡查找樹
第28章 圖
第29章 圖的實現
第30章 可變的、 不可變的和可復制的對象
附錄
A.Java基礎
B.Java類
C.由已有類創建新類
D.類的設計
E.異常處理
F.文件輸入與輸出
G.文檔與程序設計風格
第3版的新內容
根據讀者和審稿人的意見, 對部分素材進行了重新組織。很多學生對棧和隊列已經相當熟悉了, 所以對這些數據組織方式的內容出現在這一版較靠前的章節中。而且, 重新組織以后, 學生可以更好地理解鏈接數據的難點。在鏈表中添加或者刪除頭節點是最簡單的操作。在介紹袋子的過程中, 本書使用這些簡單的鏈表操作來實現袋子。在袋子之后介紹的是棧, 棧是一個更加有用的組織方式, 它的一種實現也是基于相同的簡單鏈表。隊列的實現為討論對鏈表尾節點進行添加和刪除提供了機會。最后, 本書對線性表的處理中關注了對鏈表中間節點進行添加和刪除的操作。
讀者將注意到相對于前一版本, 算法的效率(包括提升動機)、 遞歸和排序等內容也出現在此版本的靠前章節中。為了保持對數據結構的關注, 將原來的前三章——Java類、 由已有類創建新類和類的設計移到了附錄部分。現在引言之后直接就開始介紹第一個數據合集——袋子。不過, 對于在開始學習本書主題之前需要學習Java類的讀者, 仍然可以在附錄中找到原來這些章節的完整內容。
最后, 這一版增加了一些新的特色。本書以“問題解決”的形式展示了大量的例子。在這種方式下, 首先提出一個問題, 然后討論它的解決方案并進行實現。偶爾會出現的“設計決策”會探討一個解決方案的多種設計選擇。這兩個新的特色幫助學生思考程序設計的重要方面, 也讓他們在特定的場景下思考概念。上一個版本中已有的注釋、 編程小貼士和自測問題(含答案)在本版中均進行了保留。此外, 讀者將發現Deque接口、 ArrayDeque類的介紹以及其他的項目實踐題目。
下面是本書新內容的總結:
● 較早介紹抽象數據類型、 可變大小數組和鏈接數據。
● 對鏈接數據的循序漸進的講解。
● 較早介紹算法效率、 棧、 遞歸、 排序和隊列等內容。
● 有需要較好的算法效率的動力。
● 第1章至第3章——袋子、 用數組實現袋子和用鏈表實現袋子——介紹和實現ADT袋子。
● 新元素包括問題解決和設計決策。
● 第二版中出現在開頭章節的對Java類的回顧內容現在移到了附錄中。
● 標準接口Deque和類ArrayDeque的涵蓋。
● 附加的實踐項目。
● 自測問題的答案出現在每章的最后而不是附錄中。
促進學習的特色之處
首先, 每章一開始都給出了內容列表, 學生需要閱讀的預備章節和附錄列表, 以及本章知識的學習目標。其次, 貫穿本書還出現了如下所示的其他教學元素:
注 以楷體字印刷的段落對重要的思想進行描述或者總結, 且需要和上下文一起閱讀。
編程小貼士 在相關之處給出的改進或者有助于編程的建議。
示例 闡明新概念的大量例子。
解決問題 以“解決問題”的形式給出的大型例子, 其中首先提出問題, 然后對其解決方案進行討論、 設計和實現。
設計決策 在制定解決方案的時候, 為讀者可能做出的設計選擇進行探討。“設計決策”這一元素列出這樣的設計選項, 并給出為特定例子所做出的最終選擇的依據。這些討論經常出現在解決問題例子的上下文中。
自測問題答案 在每一章中都會提出一些自測問題, 融合在章節的文字中, 來鞏固剛剛提出的概念。這些“自我檢測”問題幫助讀者理解這些知識, 因為回答這些問題需要停頓和反思。這些問題的答案在每一章的最后給出。練習題和實踐項目 可以通過解決每一章最后的練習題和實踐項目來進行更深入的實踐。遺憾的是, 盡管不是課堂授課, 我們也不能給讀者提供這些練習題和實踐項目的答案。只有采用本書進行教學的教師才可從出版商那里獲取選中的答案。如果需要獲得這些練習題和實踐項目的幫助, 讀者需要聯系你的指導老師。
本書的讀者應當已經修完一門編程課程, 最好是Java編程。附錄部分覆蓋了假定讀者要了解的Java基礎知識。大家可以將附錄作為復習內容, 或者作為從其他編程語言向Java過渡的基礎。這本書本身就以引言開頭, 為我們將要學習的數據組織做好了鋪墊。
● 第1章至第3章: 介紹袋子這種抽象數據類型(ADT)。通過將這部分內容劃分為幾個章節, 清晰明了地將袋子的說明、 使用和實現區分開來。例如, 第1章詳細說明袋子并提供了若干使用的例子。第2章涵蓋了基于數組和向量的具體實現, 而第3章則介紹了鏈表并使用鏈表對袋子類進行定義。
同樣, 在整本書中, 當討論多種多樣的其他類型的ADT的時候, 也將它們的說明和實現進行了分離。讀者可以選擇先學習對ADT進行說明和使用的章節, 以后再學習具體實現的章節; 也可以選擇按照書中的順序, 在學習說明和使用之后馬上實現這些ADT。各章預備知識的列表將在這個前言的后面部分給出, 以幫助大家規劃自己學習整本書的路線。
第2章不僅僅是簡單地實現ADT袋子, 也展示了如何通過在開始只關注核心方法來實現一個類的方法。在實現類的時候, 一種大有益處的常見做法是首先實現和測試核心方法, 以后再去定義其他的方法。
● 第4章: 介紹了算法的復雜度。我們將這一主題融入到后面的章節中。
● 第5章和第6章: 第5章討論棧, 給出了棧的使用實例。第6章通過使用數組、 向量和鏈表來實現棧。
● 第7章至第9章: 接下來, 介紹遞歸這種問題解決工具以及它和棧的關系。遞歸和算法的效率一樣, 是一個在整本書中不斷涉及的主題。例如, 在第8章和第9章討論各種各樣的排序技術和它們的相對復雜度時, 我們考慮這些算法的迭代版本, 也考慮其遞歸版本。
● 第10章和第11章: 第10章討論隊列、 雙端隊列和優先隊列, 第11章考慮它們的實現。在第11章中, 介紹了循環鏈表和雙向鏈表。
● 第12章、 第13章和第14章: 接下來的這三章介紹ADT線性表。我們在抽象層次上討論了這種合集, 然后分別使用數組、 向量和鏈表對它進行了實現。
● 第15章: 然后, 基于線性表的講解討論迭代器。這一章考慮和實現了Java的迭代器接口Iterator和ListIteraror。本章還介紹了Iterable接口。
● 第16章和第17章: 第16章繼續討論線性表, 介紹了有序表, 關注有序表的兩種可能的實現及其效率。第17章說明如何將線性表作為有序表的超類, 并且討論了超類的一般設計。
● 第18章: 在線性表和有序表的背景下, 考察查找數組和鏈表的一些策略。這些討論是后續章節的堅實基礎。
● 第19章至第22章: 第19章涵蓋了ADT詞典的說明和使用。第20章介紹詞典的基于鏈表的實現和基于數組的實現。第21章介紹散列, 而第22章則利用散列實現了詞典。
● 第23章至第27章: 第23章討論了樹及其可能的用法。在給出樹的一些例子的同時, 本章介紹了二叉查找樹和堆。第24章考慮二叉樹和一般樹的實現, 而第25章則關注二叉查找樹的實現。第26章說明如何使用數組來實現堆。第27章介紹平衡查找樹。這一章包括AVL樹、 2-3樹、 2-4樹、 紅黑樹和B樹。
● 第28章至第29章: 接著討論圖, 并且著眼于它的幾種應用和兩種具體實現。
● 第30章: 最后一章詳細闡述可變對象和不可變對象的概念, 介紹了克隆。在數據是可變的情況下, 如果客戶程序維護一個ADT內部數據的引用, 那么它就可以改變這個數據, 而不用使用類的公有方法。我們考慮對客戶程序如此操作進行預防的步驟。
● 附錄A至附錄G: 附錄提供關于Java的補充知識。如前所述, 附錄A回顧了到類之前(不包括類)的基礎知識。不過, 該附錄也涵蓋了Scanner類、 枚舉類型、 裝箱和拆箱以及for-each循環。附錄B討論Java類, 附錄C進一步擴展這一主題, 著眼于組合和繼承, 附錄D關注類的設計。附錄E涵蓋異常處理, 附錄F討論文件。附錄G考慮程序設計風格和注釋, 介紹了javadoc注釋風格并且定義了我們在本書中所使用的標簽。
致謝
在此, 衷心地感謝下列審稿人員。正因為他們認真閱讀了上一版本, 提出了中肯的意見和建議, 才使本書的質量和水平得到極大地提高。
Steven Andrianoff—St. Bonaventure University
Brent Baas—LeTourneau University
Timothy Henry—University of Rhode Island
Ken Martin—University of North Florida
Bill Siever—Northwest Missouri State University
Lydia Sinapova—Simpson College
Lubomir Stanchev—Indiana University
Judy Walters—North Central College
Xiaohui Yuan—University of North Texas
特別感謝在這本書漫長的修訂過程中支持我的搭檔們。我的編輯Tracy Dunkelberger給予我持續不斷的熱情、 鼓勵、 智慧和指導。Melinda Haggerty和Allison Michael使審閱工作井井有條。Stephanie Sellinge見證了本書及其增補內容的發展。與我長期合作的文字編輯Rebecca Pepper, 確保我的表述清晰無誤, 語法正確。Jeff Holcomb、 Bob Engelhardt和Louise Capulli 指導了這本書的出版。每當我需要他們的時候, 這支隊伍一直與我攜手同行。非常感謝他們!
對前面諸位的感謝并不能削減我對許多其他幫助者的感激之情。再次感謝本書前兩個版本的審稿人:
第二版的審稿人:
Harold Anderson—Marist College
Razvan Andonie—Central Washington University
Tom Blough—Rensselaer Polytechnic Institute
Chris Brooks—University of San Francisco
Adrienne Decker—University at Buffalo, SUNY
Henry Etlinger—Rochester Institute of Technology
Derek Harter—Texas A&M University
Timothy Henry—University of Rhode Island
Robert Holloway—University of Wisconsin, Madison
Charles Hoot—Oklahoma City University
Teresa Leyk—Texas A&M University
Robert McGlinn—Southern Illinois University, Carbondale
Edward Medvid—Marymount University
Charles Metzler—City College of San Francisco
Daniel Zeng—University of Arizona
第一版的審稿人:
David Boyd—Valdosta State University
Dennis Brylow—Purdue University
Michael Croswell—Industry trainer/consultant
Matthew Dickerson—Middlebury College
Robert Holloway—University of Wisconsin, Madison
John Motil—California State University, Northridge
Bina Ramamurthy—University at Buffalo, SUNY
David Surma—Valparaiso University
還要感謝很多其他為舊版本提供幫助的人。他們是Alan Apt,James Blanding, Lianne Dunn, Mike Giacobbe, Toni Holm, Charles Hoot, Brian Jepson, Rose Kernan, ChristiannaLee, Patrick Lindner, John Lovell, Vince O’Brien, Patty Roy, Walt Savitch, Ben Schomp, HeatherScott, Carole Snyder, Chirag Thakkar, Camille Trentacoste, Nate Walker, and Xiaohong Zhu。
最后, 我想感謝我的家人和朋友——Doug, Ted, Vandee, Nancy, Sue, Tom, Maybeth, Marge和Lorraine——給了我一個遠離電腦的生活。
感謝大家, 感謝你們的專業支持和鼓勵。Frank M. Carrano
各章的預備知識
本書的每一章和每一個附錄都假定讀者已經在前期學習了一些知識。下面的表格列出了這些預備知識, 其中的數字代表了章節的編號, 字母指明了參考的附錄。讀者可以根據這些信息來規劃自己的學習路徑。


引 言
如果稍稍留意周圍的人或事, 就會意識到人們可能采取不同的組織方式去處理日常的事務。例如, 今天早晨去商店買東西, 在收銀結算時將到付費隊伍的最后面去排隊。大家自覺地按照時間先后的順序排隊, 排在最前面的人肯定第一個享受結算服務且最早離開隊伍。最終, 將輪到你排到隊伍的最前面, 付費后拿著裝有所購買物品的袋子心滿意足地離開。這時, 購物袋里的物品是沒有什么順序之分的, 有些還可能是相同的商品。
看到放在書桌上的一摞書或者一疊紙了嗎?對這樣的一摞東西(即棧), 我們很容易查看或者取走放在最上面的物品, 也很容易繼續在最上面添加新的物品。一摞東西中的物品也是按照時間先后的順序組織的, 即最后添加的物品放在最上面, 而最先添加的物品放在最下面。
再看看放在桌上的那張事務處理列表吧。對你而言, 這張表中每一項書寫的位置或許重要或許不重要。但是, 還是有可能在寫的時候考慮過是按照事務的重要程度排列, 還是按照它們的字母順序來排列。其實, 書寫的順序是你自己確定的, 事務處理列表只不過列出了所有待處理的事務條目而已。
字典是單詞和它們的定義根據字母順序組織的列表。我們往往需要查找某個單詞, 查看它的定義。如果字典是紙質印刷的, 這種按照字母順序的組織方式將有助于快速地找到單詞。如果字典是計算機化的, 雖然表面上看不到它內部按字母順序的組織方式, 但是該方式仍然提高了檢索單詞的速度。
既然提到了計算機, 那么就讓我們看一下文件的組織方式——它們被組織到文件夾或目錄中, 即每個文件夾包含若干其他的文件夾或文件。這種類型的組織方式是層次型的。如果對此組織方式畫一張圖的話, 可以看到它與家族樹或公司的內部部門圖有相似之處。確實, 這些數據的組織方式是相似的, 稱為樹。
最后, 注意一下為周末出游所設計的路線圖。這張含有道路和城鎮信息的圖指示了如何從一個地方到達另一個地方, 往往其中有多條可選的線路。例如, 有一條路線可能是距離較短的, 而另一條可能是更快到達的。這種路線圖具有的數據組織方式稱為圖。

除了前面這些日常例子之外, 計算機程序也需要組織其數據。也就是說, 程序可以使用列表、 棧、 字典等數據組織方式。這些數據組織方式被表示為多個抽象數據類型。一個抽象數據類型(Abstract Data Type, ADT)是一份規格說明書, 描述了一個數據集及其數據上的操作, 即每個ADT詳細說明該存儲什么樣的數據, 以及對這些數據要進行哪些操作。不過, ADT并沒有明確說明如何存儲數據或者如何實現操作, 因此對這些ADT的討論可以不依賴于任何程序設計語言。相對ADT而言, 一個數據結構是某個ADT在一種程序設計語言中的實現。
一個合集(collection)是更廣的術語, 是指一個包含一組對象的ADT。一些合集允許重復的項, 而另一些不允許。一些合集按照某種順序組織它們的內容, 而另一些則無序地組織。一個容器(container)是實現合集的一個類。大家以后可能看到, 有些人對術語“容器”和“合集”會不加區別地進行使用。
我們可以創建一個ADT袋子(bag), 它由一個允許重復元素的無序合集構成, 很像是一個食品雜貨袋, 一個午餐袋或者是一個裝滿薯片的袋子。假設從薯片袋子中取出一片薯片, 這時你不會知道這片薯片是何時放進袋子中的, 也不可能知道袋子中是否還有一片與剛取出的薯片形狀完全相同的薯片。但是, 實際上并不需要關心這些。如果確實在意, 就不會將薯片存放在一個袋子中。
袋子不會將其內容排序, 但是有時候需要對物品進行排序的。各種各樣的ADT使用不同的方式對它們所包含的元素進行排序。例如, ADT線性表(list)將它所含的項簡單地進行編號。因此, 一個線性表有第一項、 第二項, 以此類推。盡管可以向線性表的末尾添加項, 實際上也可以在線性表開頭或者線性表的某兩項之間插入項。這么做會導致新項之后的項的重新編號。此外, 可以在線性表中刪除某特定位置的項。因此, 線性表中項的位置并不一定表明它被添加的時間。請注意, 線性表并不決定項的存放位置, 而是由編程人員決定。
相比之下, ADT棧(stack)和隊列(queue)則以時間順序來組織它們的項。當從棧中刪除一項時候, 所刪除的是最近被添加的那一項。當刪除隊列中的一項的時候, 所刪除的是最早被添加進隊列中的那一項。因此, 棧就像一摞書。可以取走最上面的書或者將另一本書添加到這摞書的最上面。而隊列就像是人排隊的隊伍, 人們從隊首離開, 從隊尾加入。
如果項是可比的, 一些ADT中的條目始終保持有序的狀態。例如, 字符串可以按照字母順序進行組織。當向ADT有序表(sorted list)中添加一項的時候, ADT決定要把該項放入哪個位置。不能像對待ADT線性表那樣為待添加項指定一個位置。
ADT字典(dictionary)包含成對的項, 這一點非常像一本包含單詞及其定義的語言類字典。在這個例子中, 單詞充當的是關鍵字的角色, 它可以定位詞條的位置。一些字典會將詞條排序, 另一些則不會。
ADT樹(tree)根據某種層次結構來組織它的條目。例如, 在家族樹中, 人們與他們的孩子和父母相聯系。ADT二叉查找樹(binary search tree)使用層次化的有序結構, 這使得定位其中的條目更加簡單。
ADT圖(graph)是ADT樹的一般化。ADT圖關注的是條目之間的關系, 而非層次化的組織。例如, 一張路線圖是一個顯示了城鎮間道路和距離的圖。
本書向大家介紹如何使用和實現這些數據組織方式。在開始學習之前, 需要了解Java。附錄A回顧了Java中的基本語句。附錄B討論類和方法的基本構造。可以選擇簡單瀏覽這些材料, 或是認真閱讀, 也可以在需要的時候進行查看。附錄C和附錄D介紹Java的內容, 有可能某些部分或者全部的內容對你而言是全新的。附錄C涵蓋了技術性內容, 包括組合和繼承, 其目的是為了從已有的類構建新的類。附錄D討論如何設計類, 定義方法和編寫Java接口。使用接口和書寫說明方法的注釋對描述ADT至關重要。附錄E介紹如何處理異常, 附錄F展示了對外部文件的讀寫, 附錄G則概述了如何書寫適合javadoc的注釋本書共有7個附錄(附錄A至附錄G)。
內容簡介:

本書是為數據結構入門課程而編寫的教材。作者Frank Carrano在編寫過程自始至終特別考慮到了Java與對象,為教師和學生提供了一種精心設計并經過教學實驗的方式借助Java講授ADT和對象。本書獨特的設計將內容組織為相對較短的章。這種方式使學習更容易,并留出了教學的機動性。本書教給學生如何使用線性表、詞典、棧、隊列等等來組織數據。利用這些數據組織方式,學生們將學到算法設計的相關技術。

目錄:

第1章 袋子
袋子
袋子的行為
袋子的規格說明
接口
ADT袋子的使用
像使用自動售貨機一樣使用ADT
Java類庫: 接口Set
第2章 使用數組實現袋子
使用固定大小的數組實現ADT袋子
一個類比
一組核心方法
核心方法的實現
核心方法的測試
更多方法的實現
刪除物品的方法
使用可變大小的數組實現ADT袋子
調整數組的大小
袋子的一種新的實現
使用數組實現ADT袋子的優缺點
第3章 使用鏈表實現袋子
鏈表
通過添加節點到表頭來創建鏈表
ADT袋子的鏈表實現
私有的類Node
類LinkedBag的概要
一些核心方法的定義
核心方法的測試
方法getFrequencyOf
方法contains
從鏈表中刪除物品
方法remove和clear
具有方法set和get的類Node
使用鏈表實現ADT袋子的優缺點
第4章 算法的效率
動機
算法效率的度量
基本操作次數的統計
最好、 最壞和平均情況
大O表示法
程序結構的復雜度
效率的圖形化表示
ADT袋子不同實現的效率
基于數組的實現
基于鏈表的實現
兩種實現方法的比較
第5章 棧
ADT棧的規格說明
利用棧處理代數表達式
應用問題: 中綴代數表達式中括號平衡的
檢查
應用問題: 中綴表達式向后綴表達式的
轉換
應用問題: 后綴表達式的求值
應用問題: 中綴表達式的求值
程序棧
Java類庫: 類Stack
第6章 棧的實現
基于鏈表的實現
基于數組的實現
基于向量的實現
Java類庫: Vector類
使用向量實現ADT棧
第7章 遞歸
什么是遞歸
跟蹤一個遞歸方法
有返回值的遞歸方法
遞歸地處理一個數組
遞歸地處理一個鏈表
遞歸方法的時間效率
countDown的時間效率
計算xn的時間效率
一個復雜問題的簡單解決方案
一個簡單問題的拙劣解決方案
尾遞歸
間接遞歸
使用棧代替遞歸
第8章 排序引論
組織Java對數組排序的方法
選擇排序
迭代選擇排序
遞歸選擇排序
選擇排序的效率
插入排序
迭代插入排序
遞歸插入排序
插入排序的效率
鏈表的插入排序
希爾排序
Java代碼
希爾排序的效率
算法比較
第9章 快速排序方法
歸并排序
數組的歸并
遞歸的歸并排序
歸并排序的效率
迭代的歸并排序
Java類庫中的歸并排序
快速排序
快速排序的效率
創建劃分
快速排序的Java代碼
Java類庫中的快速排序
基數排序
基數排序的偽代碼
基數排序的效率
算法比較
第10章 隊列、 雙端隊列和優先隊列
ADT隊列
解決問題: 模擬排隊
解決問題: 計算出售股票時的資本
增益(一)
Java類庫: 接口Queue
ADT雙端隊列
解決問題: 計算出售股票時的資本
增益(二)
Java類庫: 接口Deque
Java類庫: ArrayDeque類
ADT優先隊列
解決問題: 跟蹤你的作業
Java類庫: 類PriorityQueue
第11章 隊列、 雙端隊列和優先隊列的
實現
基于鏈表隊列的實現
基于數組隊列的實現
循環數組
有一個未使用存儲單元的循環數組
基于向量隊列的實現
基于循環鏈表隊列的實現
由兩部分構成的循環鏈表
Java類庫: 類AbstractQueue
基于雙向鏈表雙端隊列的實現
實現優先隊列的可用方法
第12章 線性表
ADT線性表的規格說明
使用ADT線性表
Java類庫: List接口
Jave類庫: ArraryList類
第13章 用數組實現線性表
用數組實現ADT線性表
一個類比
Java實現
用數組實現ADT線性表的效率
用Vector實現ADT線性表
第14章 用鏈表實現線性表
操作鏈表節點
在多種位置加入節點
在多種位置刪除節點
私有方法getNodeAt
開始實現
數據域和構造函數
在列表結尾加入
在列表給定位置加入
方法isEmpty和toArray
測試核心方法
繼續實現
一個更好的實現
尾引用
用鏈表實現ADT列表的效率
Java類庫: 類LinkedList
第15章 迭代器
迭代器是什么
Iterator接口
使用Iterator接口
獨立類迭代器
內部類迭代器
基于鏈表實現
基于數組實現
為什么迭代器方法在它們自己的
類中
ListIterator接口
使用ListIterator接口
ListIterator接口基于數組的實現
內部類
Java類庫: Iterable接口
Iterable和for-each循環
修改版接口List
第16章 有序表
ADT有序表的規格說明
使用ADT有序表
鏈表實現
方法add
鏈表實現的效率
使用ADT線性表的實現
效率問題
第17章 繼承及線性表
使用繼承實現有序表
設計一個基類
創建一個抽象基類
有序表的一種高效實現
方法add
第18章 查找
問題引入
查找無序數組
無序數組的迭代式順序查找
無序數組的遞歸式順序查找
順序查找數組的效率
查找有序數組
有序數組的順序查找
有序數組的二分查找
Java類庫: 方法binarySearch
二分查找數組的效率
查找無序鏈表
無序鏈表的迭代式順序查找
無序鏈表的遞歸式順序查找
順序查找鏈表的效率
查找有序鏈表
有序鏈表的順序查找
二分查找有序鏈表
查找方法的選擇
第19章 詞典
ADT詞典規格說明
Java接口
迭代器
使用ADT詞典
問題解決: 電話號碼本
問題解決: 詞頻
問題解決: 詞的索引
Java類庫: Map接口
第20章 詞典的實現
基于數組的實現
一個無序數組詞典
一個有序數組詞典
基于向量的實例
鏈式實例
一個無序鏈式詞典
一個有序鏈式詞典
第21章 散列概述
散列是什么
散列函數
計算散列碼
將散列碼壓縮成散列表的索引
處理沖突
用線性探測實現開放定址
用二次探測實現開放定址
用雙重散列實現開放定址
開放定址的潛在問題
鏈地址
第22章 用散列實現詞典
散列的效率
容載分析
開放定址消耗分析
鏈地址消耗分析
再散列
不同沖突解決方案的對比
用散列實現詞典的實例
散列表中的條目
數據域和構造函數
getValue, remove和add方法
迭代器
Java類庫: HashMap類
Java類庫: HashSet類
第23章 樹
樹的概念
層次化的數據組織
樹的術語
樹的遍歷
遍歷二叉樹
一般樹的遍歷
樹的Java接口
樹的通用接口
二叉樹的接口
二叉樹的例子
表達式樹
決策樹
二叉查找樹

一般樹的例子
語法分析樹
游戲樹
第24章 樹的實現
二叉樹的節點
節點的接口
二叉樹節點的實現
ADT二叉樹的實現
創建基本二叉樹
privateSetTree方法
訪問器與更改器方法
計算高度和節點數
遍歷
表達式樹的實現
一般樹
一般樹的節點
用二叉樹表示一般樹
第25章 二叉查找樹的實現
開始
二叉查找樹接口
重復的條目
開始類定義
查找和檢索
遍歷
添加條目
遞歸實現
迭代實現
刪除條目
刪除一個葉子節點的條目
刪除節點有一個孩子的條目
刪除節點有兩個孩子的條目
刪除為根的條目
遞歸實現
迭代實現
操作的效率
平衡的重要性
節點添加的順序
ADT詞典實現
第26章 堆的實現
再論ADT堆
用數組表示堆
插入條目
刪除根
創建堆
堆排序
第27章 平衡查找樹
AVL樹
單旋轉
雙旋轉
實現細節
2-3樹
查找2-3樹
添加條目至2-3樹
添加時分裂節點
2-4樹
添加條目至2-4樹
比較AVL, 2-3和2-4樹
紅黑樹
紅黑樹的性質
添加條目到紅黑樹
Java類庫: TreeMap類
B樹
第28章 圖
一些示例和術語
公路線路圖
航空線路圖
迷宮

遍歷
廣度優先遍歷
深度優先遍歷
拓撲排序
路徑
尋找路徑
無權圖的最短路徑算法
加權圖中的最短路徑
ADT圖的Java接口
第29章 圖的實現
兩種實現的概述
鄰接矩陣
鄰接表
頂點和邊
類Vertex的規格說明
內部類Edge
實現Vertex類
ADT圖的實現
基本操作
圖算法在 線 部 分
第30章 可變的、 不可變的和可復制的對象(英文版本)
附錄A Java基礎
附錄B Java類
附錄C 從已有類創建新類
附錄D 類的設計
附錄E 異常處理
附錄F 文件輸入與輸出
附錄G 文檔與程序設計風格
序: