算法（第4版）

前言

本書(shū)力圖研究當(dāng)今最重要的計(jì)算機(jī)算法并將一些最基礎(chǔ)的技能傳授給廣大求知者。它適合用做計(jì)算機(jī)科學(xué)進(jìn)階教材，面向已經(jīng)熟悉了計(jì)算機(jī)系統(tǒng)并掌握了基本編程技能的學(xué)生。本書(shū)也可用于自學(xué)，或是作為開(kāi)發(fā)人員的參考手冊(cè)，因?yàn)闀?shū)中實(shí)現(xiàn)了許多實(shí)用算法并詳盡分析了它們的性能特點(diǎn)和用途。這本書(shū)取材廣泛，很適合作為該領(lǐng)域的入門(mén)教材。算法和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)是所有計(jì)算機(jī)科學(xué)教學(xué)計(jì)劃的基礎(chǔ)，但它并不只是對(duì)程序員和計(jì)算機(jī)系的學(xué)生有用。任何計(jì)算機(jī)使用者都希望計(jì)算機(jī)能運(yùn)行得更快一些或是能解決更大規(guī)模的問(wèn)題。本書(shū)中的算法代表了近50年來(lái)的大量?jī)?yōu)秀研究成果，是人們工作中必備的知識(shí)。從物理中的N體模擬問(wèn)題到分子生物學(xué)中的基因序列問(wèn)題，我們描述的基本方法對(duì)科學(xué)研究而言已經(jīng)必不可少；從建筑建模系統(tǒng)到模擬飛行器，這些算法已經(jīng)成為工程領(lǐng)域極其重要的工具；從數(shù)據(jù)庫(kù)系統(tǒng)到互聯(lián)網(wǎng)搜索引擎，算法已成為現(xiàn)代軟件系統(tǒng)中不可或缺的一部分。這僅是幾個(gè)例子而已，隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)張，這些基礎(chǔ)方法的影響也會(huì)不斷擴(kuò)大。在開(kāi)始學(xué)習(xí)這些基礎(chǔ)算法之前，我們先要熟悉全書(shū)中都將會(huì)用到的棧、隊(duì)列等低級(jí)抽象的數(shù)據(jù)類(lèi)型。然后依次研究排序、搜索、圖和字符串方面的基礎(chǔ)算法。最后一章將會(huì)從宏觀角度總結(jié)全書(shū)的內(nèi)容。獨(dú)特之處本書(shū)致力于研究有實(shí)用價(jià)值的算法。書(shū)中講解了多種算法和數(shù)據(jù)結(jié)構(gòu)，并提供了大量相關(guān)的信息，讀者應(yīng)該能有信心在各種計(jì)算環(huán)境下實(shí)現(xiàn)、調(diào)試并應(yīng)用它們。本書(shū)的特點(diǎn)涉及以下幾個(gè)方面。算法　書(shū)中均有算法的完整實(shí)現(xiàn)，并討論了程序在多個(gè)樣例上的運(yùn)行狀況。書(shū)中的代碼都是可以運(yùn)行的程序而非偽代碼，因此非常便于投入使用。書(shū)中程序是用Java語(yǔ)言編寫(xiě)的，但其編程風(fēng)格方便讀者使用其他現(xiàn)代編程語(yǔ)言重用其中的大部分代碼來(lái)實(shí)現(xiàn)相同算法。數(shù)據(jù)類(lèi)型我們?cè)跀?shù)據(jù)抽象上采用了現(xiàn)代編程風(fēng)格，將數(shù)據(jù)結(jié)構(gòu)和算法封裝在了一起。應(yīng)用每一章都會(huì)給出所述算法起到關(guān)鍵作用的應(yīng)用場(chǎng)景。這些場(chǎng)景多種多樣，包括物理模擬與分子生物學(xué)、計(jì)算機(jī)與系統(tǒng)工程學(xué)，以及我們熟悉的數(shù)據(jù)壓縮和網(wǎng)絡(luò)搜索等。學(xué)術(shù)性我們非常重視使用數(shù)學(xué)模型來(lái)描述算法的性能。我們用模型預(yù)測(cè)算法的性能，然后在真實(shí)的環(huán)境中運(yùn)行程序來(lái)驗(yàn)證預(yù)測(cè)。廣度本書(shū)討論了基本的抽象數(shù)據(jù)類(lèi)型、排序算法、搜索算法、圖及字符串處理。我們?cè)谒惴ǖ挠懻撝醒芯繑?shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)范式、歸納法和解題模型。這將涵蓋20世紀(jì)60年代以來(lái)的經(jīng)典方法以及近年來(lái)產(chǎn)生的新方法。我們的主要目標(biāo)是將今天最重要的實(shí)用算法介紹給盡可能廣泛的群體。這些算法一般都十分巧妙奇特，20行左右的代碼就足以表達(dá)。它們展現(xiàn)出的問(wèn)題解決能力令人嘆為觀止。沒(méi)有它們，創(chuàng)造計(jì)算智能、解決科學(xué)問(wèn)題、開(kāi)發(fā)商業(yè)軟件都是不可能的。本書(shū)網(wǎng)站本書(shū)的一個(gè)亮點(diǎn)是它的配套網(wǎng)站algs4.cs.princeton.edu。這一網(wǎng)站面向教師、學(xué)生和專(zhuān)業(yè)人士，免費(fèi)提供關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的豐富資料。一份在線(xiàn)大綱　包含了本書(shū)內(nèi)容的結(jié)構(gòu)并提供了鏈接，瀏覽起來(lái)十分方便。全部實(shí)現(xiàn)代碼　書(shū)中所有的代碼均可以在這里找到，且其形式適合用于程序開(kāi)發(fā)。此外，還包括算法的其他實(shí)現(xiàn)，例如高級(jí)的實(shí)現(xiàn)、書(shū)中提及的改進(jìn)的實(shí)現(xiàn)、部分習(xí)題的答案以及多個(gè)應(yīng)用場(chǎng)景的客戶(hù)端代碼。我們的重點(diǎn)是用真實(shí)的應(yīng)用環(huán)境來(lái)測(cè)試算法。習(xí)題與答案　網(wǎng)站還提供了一些附加的選擇題（只需要一次單擊便可獲取答案）、很多算法應(yīng)用的例子、編程練習(xí)和答案以及一些有挑戰(zhàn)性的難題。動(dòng)態(tài)可視化　書(shū)是死的，但網(wǎng)站是活的，在這里我們充分利用圖形類(lèi)演示了算法的應(yīng)用效果。課程資料　網(wǎng)站包含和本書(shū)及網(wǎng)上內(nèi)容對(duì)應(yīng)的一整套幻燈片，以及一系列編程作業(yè)、核對(duì)表、測(cè)試數(shù)據(jù)和備課手冊(cè)。相關(guān)資料鏈接　網(wǎng)站包含大量的鏈接，提供算法應(yīng)用的更多背景知識(shí)以及學(xué)習(xí)算法的其他資源。我們希望這個(gè)站點(diǎn)和本書(shū)互為補(bǔ)充。一般來(lái)說(shuō)，建議讀者在第一次學(xué)習(xí)某種算法或是希望獲得整體概念時(shí)看書(shū)，并把網(wǎng)站作為編程時(shí)的參考或是在線(xiàn)查找更多信息的起點(diǎn)。作為教材本書(shū)為計(jì)算機(jī)科學(xué)專(zhuān)業(yè)進(jìn)階的教材，涵蓋了這門(mén)學(xué)科的核心內(nèi)容，并能讓學(xué)生充分鍛煉編程、定量推理和解決問(wèn)題等方面的能力。一般來(lái)說(shuō)，此前學(xué)過(guò)一門(mén)計(jì)算機(jī)方面的先導(dǎo)課程就足矣，只要熟悉一門(mén)現(xiàn)代編程語(yǔ)言并熟知現(xiàn)代計(jì)算機(jī)系統(tǒng)，就都能夠閱讀本書(shū)。雖然本書(shū)使用Java實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)，但其代碼風(fēng)格使得熟悉其他現(xiàn)代編程語(yǔ)言的人也能看懂。我們充分利用了Java的抽象性（包括泛型），但不會(huì)依賴(lài)這門(mén)語(yǔ)言的獨(dú)門(mén)特性。書(shū)中涉及的多數(shù)數(shù)學(xué)知識(shí)都有完整的講解（少數(shù)會(huì)有延伸閱讀），因此閱讀本書(shū)并不需要準(zhǔn)備太多數(shù)學(xué)知識(shí)，不過(guò)有一定的數(shù)學(xué)基礎(chǔ)當(dāng)然更好。應(yīng)用場(chǎng)景都來(lái)自其他學(xué)科的基礎(chǔ)內(nèi)容，同樣也在書(shū)中有完整介紹。本書(shū)涉及的內(nèi)容是任何準(zhǔn)備主修計(jì)算機(jī)科學(xué)、電氣工程、運(yùn)籌學(xué)等專(zhuān)業(yè)的學(xué)生應(yīng)了解的基礎(chǔ)知識(shí)，并且對(duì)所有對(duì)科學(xué)、數(shù)學(xué)或工程學(xué)感興趣的學(xué)生也十分有價(jià)值。背景介紹這本書(shū)意在接續(xù)我們的一本基礎(chǔ)教材《Java程序設(shè)計(jì)：一種跨學(xué)科的方法》，那本書(shū)對(duì)計(jì)算機(jī)領(lǐng)域做了概括性介紹。這兩本書(shū)合起來(lái)可用做兩到三個(gè)學(xué)期的計(jì)算機(jī)科學(xué)入門(mén)課程教材，為所有學(xué)生在自然科學(xué)、工程學(xué)和社會(huì)科學(xué)中解決計(jì)算問(wèn)題提供必備的基礎(chǔ)知識(shí)。本書(shū)大部分內(nèi)容來(lái)自Sedgewick的算法系列圖書(shū)。本質(zhì)上，本書(shū)和該系列的第1版和第2版最接近，但還包含了作者多年教學(xué)和學(xué)習(xí)的經(jīng)驗(yàn)。Sedgewick的《C算法（第3版）》、《C++算法（第3版）》、《Java算法（第3版）》更適合用做參考書(shū)或是高級(jí)課程的教材，而本書(shū)則是專(zhuān)門(mén)為大學(xué)一、二年級(jí)學(xué)生設(shè)計(jì)的一學(xué)期教材，也是最新的基礎(chǔ)入門(mén)書(shū)或從業(yè)者的參考書(shū)。致謝本書(shū)的編寫(xiě)花了近40年時(shí)間，因此想要一一列出所有參與人是不可能的。本書(shū)的前幾版一共列出了好幾十人，其中包括（按字母順序）Andrew Appel、Trina Avery、Marc Brown、Lyn Dupré、PhilippeFlajolet、Tom Freeman、Dave Hanson、Janet Incerpi、Mike Schidlowsky、Steve Summit和Chris VanWyk。我要感謝他們所有人，盡管其中有些人的貢獻(xiàn)要追溯到幾十年前。至于第4版，我們要感謝試用了本書(shū)樣稿的普林斯頓及其他院校的數(shù)百名學(xué)生，以及通過(guò)本書(shū)網(wǎng)站發(fā)表意見(jiàn)和指出錯(cuò)誤的世界各地的讀者。我們還要感謝普林斯頓大學(xué)對(duì)于高質(zhì)量教學(xué)的堅(jiān)定支持，這是本書(shū)得以面世的基礎(chǔ)。Peter Gordon幾乎從本書(shū)寫(xiě)作之初就提出了很多有用的建議，這一版奉行的“歸本溯源”的指導(dǎo)思想也是他最早提出的。關(guān)于第4版，我們要感謝Barbara Wood認(rèn)真又專(zhuān)業(yè)的編輯工作，Julie Nahil對(duì)生產(chǎn)過(guò)程的管理，以及Pearson出版公司中為本書(shū)的付梓和營(yíng)銷(xiāo)辛勤工作的朋友。所有人都在積極地追趕進(jìn)度，而本書(shū)的質(zhì)量并沒(méi)有受到絲毫影響。

內(nèi)容概要

　　 《算法（第4版）》全面講述算法和數(shù)據(jù)結(jié)構(gòu)的必備知識(shí)，具有以下幾大特色。
　　 1、 算法領(lǐng)域的經(jīng)典參考書(shū)：Sedgewick暢銷(xiāo)著作的最新版，反映了經(jīng)過(guò)幾十年演化而成的算法核心知識(shí)體系
　　 2、內(nèi)容全面：全面論述排序、搜索、圖處理和字符串處理的算法和數(shù)據(jù)結(jié)構(gòu)，涵蓋每位程序員應(yīng)知應(yīng)會(huì)的50種算法
　　 3、全新修訂的代碼：全新的Java實(shí)現(xiàn)代碼，采用模塊化的編程風(fēng)格，所有代碼均可供讀者使用
　　 4、與實(shí)際應(yīng)用相結(jié)合：在重要的科學(xué)、工程和商業(yè)應(yīng)用環(huán)境下探討算法，給出了算法的實(shí)際代碼，而非同類(lèi)著作常用的偽代碼
　　
5、富于智力趣味性：簡(jiǎn)明扼要的內(nèi)容，用豐富的視覺(jué)元素展示的示例，精心設(shè)計(jì)的代碼，詳盡的歷史和科學(xué)背景知識(shí)，各種難度的練習(xí)，這一切都將使讀者手不釋卷
　　 6、科學(xué)的方法：用合適的數(shù)學(xué)模型精確地討論算法性能，這些模型是在真實(shí)環(huán)境中得到驗(yàn)證的
　　
7、與網(wǎng)絡(luò)相結(jié)合：配套網(wǎng)站algs4.cs.princeton.edu提供了本書(shū)內(nèi)容的摘要及相關(guān)的代碼、測(cè)試數(shù)據(jù)、編程練習(xí)、教學(xué)課件等資源

作者簡(jiǎn)介

　　 Robert Sedgewick，斯坦福大學(xué)博士，導(dǎo)師為Donald E.
Knuth，從1985年開(kāi)始一直擔(dān)任普林斯頓大學(xué)計(jì)算機(jī)科學(xué)系教授，曾任該系主任，也是Adobe
Systems公司董事會(huì)成員，曾在Xerox PARC、國(guó)防分析研究所（Institute for Defense
Analyses）和法國(guó)國(guó)家信息與自動(dòng)化研究所（INRIA）從事研究工作。他的研究方向包括解析組合學(xué)、數(shù)據(jù)結(jié)構(gòu)和算法的分析與設(shè)計(jì)、程序可視化等。
　　 Kevin
Wayne，康奈爾大學(xué)博士，普林斯頓大學(xué)計(jì)算機(jī)科學(xué)系高級(jí)講師，研究方向包括算法的設(shè)計(jì)、分析和實(shí)現(xiàn)，特別是圖和離散優(yōu)化。

書(shū)籍目錄

第1章　 基礎(chǔ)
1.1　基礎(chǔ)編程模型
1.1.1　Java程序的基本結(jié)構(gòu)
1.1.2　原始數(shù)據(jù)類(lèi)型與表達(dá)式
1.1.3　 語(yǔ)句
1.1.4　 簡(jiǎn)便記法
1.1.5　 數(shù)組
1.1.6　 靜態(tài)方法
1.1.7　 API
1.1.8　 字符串
1.1.9　 輸入輸出
1.1.10　 二分查找
1.1.11　 展望
1.2　 數(shù)據(jù)抽象
1.2.1　 使用抽象數(shù)據(jù)類(lèi)型
1.2.2　 抽象數(shù)據(jù)類(lèi)型舉例
1.2.3　 抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)
1.2.4　 更多抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)
1.2.5　 數(shù)據(jù)類(lèi)型的設(shè)計(jì)
1.3　 背包、隊(duì)列和棧
1.3.1　 API
1.3.2　 集合類(lèi)數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)
1.3.3　 鏈表
1.3.4　 綜述
1.4　 算法分析
1.4.1　 科學(xué)方法
1.4.2　 觀察
1.4.3　 數(shù)學(xué)模型
1.4.4　 增長(zhǎng)數(shù)量級(jí)的分類(lèi)
1.4.5　 設(shè)計(jì)更快的算法
1.4.6　 倍率實(shí)驗(yàn)
1.4.7　 注意事項(xiàng)
1.4.8　 處理對(duì)于輸入的依賴(lài)
1.4.9　 內(nèi)存
1.4.10　 展望
1.5　 案例研究：union-find算法
1.5.1　 動(dòng)態(tài)連通性
1.5.2　 實(shí)現(xiàn)
1.5.3　 展望
第2章　 排序
2.1　 初級(jí)排序算法
2.1.1　 游戲規(guī)則
2.1.2　 選擇排序
2.1.3　 插入排序
2.1.4　 排序算法的可視化
2.1.5　 比較兩種排序算法
2.1.6　 希爾排序
2.2　 歸并排序
2.2.1　 原地歸并的抽象方法
2.2.2　 自頂向下的歸并排序
2.2.3　 自底向上的歸并排序
2.2.4　 排序算法的復(fù)雜度
2.3　 快速排序
2.3.1　 基本算法
2.3.2　 性能特點(diǎn)
2.3.3　 算法改進(jìn)
2.4　 優(yōu)先隊(duì)列
2.4.1　 API
2.4.2　 初級(jí)實(shí)現(xiàn)
2.4.3　 堆的定義
2.4.4　 堆的算法
2.4.5　 堆排序
2.5　 應(yīng)用
2.5.1　 將各種數(shù)據(jù)排序
2.5.2　 我應(yīng)該使用哪種排序算法
2.5.3　 問(wèn)題的歸約
2.5.4　 排序應(yīng)用一覽
第3章　查找
3.1　符號(hào)表
3.1.1　API
3.1.2　有序符號(hào)表
3.1.3　用例舉例
3.1.4　無(wú)序鏈表中的順序查找
3.1.5　有序數(shù)組中的二分查找
3.1.6　對(duì)二分查找的分析
3.1.7　預(yù)覽
3.2　二叉查找樹(shù)
3.2.1　基本實(shí)現(xiàn)
3.2.2　分析
3.2.3　有序性相關(guān)的方法與刪除操作
3.3　平衡查找樹(shù)
3.3.1　2-3查找樹(shù)
3.3.2　紅黑二叉查找樹(shù)
3.3.3　實(shí)現(xiàn)
3.3.4　刪除操作
3.3.5　紅黑樹(shù)的性質(zhì)
3.4　散列表
3.4.1　散列函數(shù)
3.4.2　基于拉鏈法的散列表
3.4.3　基于線(xiàn)性探測(cè)法的散列表
3.4.4　調(diào)整數(shù)組大小
3.4.5　內(nèi)存使用
3.5　應(yīng)用
3.5.1　我應(yīng)該使用符號(hào)表的哪種實(shí)現(xiàn)
3.5.2　集合的API
3.5.3　字典類(lèi)用例
3.5.4　索引類(lèi)用例
3.5.5　稀疏向量
第4章　 圖
4.1　 無(wú)向圖
4.1.1　 術(shù)語(yǔ)表
4.1.2　 表示無(wú)向圖的數(shù)據(jù)類(lèi)型
4.1.3　 深度優(yōu)先搜索
4.1.4　 尋找路徑
4.1.5　 廣度優(yōu)先搜索
4.1.6　 連通分量
4.1.7　 符號(hào)圖
4.1.8　 總結(jié)
4.2　 有向圖
4.2.1　 術(shù)語(yǔ)
4.2.2　 有向圖的數(shù)據(jù)類(lèi)型
4.2.3　 有向圖中的可達(dá)性
4.2.4　 環(huán)和有向無(wú)環(huán)圖
4.2.5　 有向圖中的強(qiáng)連通性
4.2.6　 總結(jié)
4.3　 最小生成樹(shù)
4.3.1　 原理
4.3.2　 加權(quán)無(wú)向圖的數(shù)據(jù)類(lèi)型
4.3.3　 最小生成樹(shù)的API和測(cè)試用例
4.3.4　 Prim算法
4.3.5　 Prim算法的即時(shí)實(shí)現(xiàn)
4.3.6　 Kruskal算法
4.3.7　 展望
4.4　 最短路徑
4.4.1　 最短路徑的性質(zhì)
4.4.2　 加權(quán)有向圖的數(shù)據(jù)結(jié)構(gòu)
4.4.3　 最短路徑算法的理論基礎(chǔ)
4.4.4　 Dijkstra算法
4.4.5　 無(wú)環(huán)加權(quán)有向圖中的最短路徑算法
4.4.6　 一般加權(quán)有向圖中的最短路徑問(wèn)題
4.4.7　 展望
第5章　 字符串
5.1　 字符串排序
5.1.1　 鍵索引計(jì)數(shù)法
5.1.2　 低位優(yōu)先的字符串排序
5.1.3　 高位優(yōu)先的字符串排序
5.1.4　 三向字符串快速排序
5.1.5　 字符串排序算法的選擇
5.2　 單詞查找樹(shù)
5.2.1　 單詞查找樹(shù)
5.2.2　 單詞查找樹(shù)的性質(zhì)
5.2.3　 三向單詞查找樹(shù)
5.2.4　 三向單詞查找樹(shù)的性質(zhì)
5.2.5　 應(yīng)該使用字符串符號(hào)表的哪種實(shí)現(xiàn)
5.3　 子字符串查找
5.3.1　 歷史簡(jiǎn)介
5.3.2　 暴力子字符串查找算法
5.3.3　 Knuth-Morris-Pratt子字符串查找算法
5.3.4　 Boyer-Moore字符串查找算法
5.3.5　 Rabin-Karp指紋字符串查找算法
5.3.6　 總結(jié)
5.4　 正則表達(dá)式
5.4.1　 使用正則表達(dá)式描述模式
5.4.2　 縮略寫(xiě)法
5.4.3　 正則表達(dá)式的實(shí)際應(yīng)用
5.4.4　 非確定有限狀態(tài)自動(dòng)機(jī)
5.4.5　 模擬NFA的運(yùn)行
5.4.6　 構(gòu)造與正則表達(dá)式對(duì)應(yīng)的
5.5　 數(shù)據(jù)壓縮
5.5.1　 游戲規(guī)則
5.5.2　 讀寫(xiě)二進(jìn)制數(shù)據(jù)
5.5.3　 局限
5.5.4　 熱身運(yùn)動(dòng)：基因組
5.5.5　 游程編碼
5.5.6　 霍夫曼壓縮
第6章　 背景
索引

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   警告：這段類(lèi)型轉(zhuǎn)換的用例代碼和1.3.2.2節(jié)所示的有所不同。你可能會(huì)以為需要使用Object而非Stack。在使用泛型時(shí)，Java會(huì)在編譯時(shí)檢查類(lèi)型的安全性，但會(huì)在運(yùn)行時(shí)拋棄所有這些信息。因此在運(yùn)行時(shí)語(yǔ)句右側(cè)就變成了Stack（）或者只剩下了Stack（），因此我們必須將它們轉(zhuǎn)化為Stack（）。 問(wèn) 在棧為空時(shí)調(diào)用pop（）會(huì)發(fā)生什么？ 答 這取決于實(shí)現(xiàn)。對(duì)于我們?cè)谒惴?.2中給出的實(shí)現(xiàn)，你會(huì)得到一個(gè)NullPointerException異常。對(duì)于我們?cè)诒緯?shū)的網(wǎng)站上給出的實(shí)現(xiàn)，我們會(huì)拋出一個(gè)運(yùn)行時(shí)異常以幫助用戶(hù)定位錯(cuò)誤。一般來(lái)說(shuō)，在應(yīng)用廣泛的代碼中這類(lèi)檢查越多越好。 問(wèn) 既然有了鏈表，為什么還要學(xué)習(xí)如何調(diào)整數(shù)組的大小？ 答 我們還將會(huì)學(xué)習(xí)若干抽象數(shù)據(jù)類(lèi)型的示例實(shí)現(xiàn)，它們需要使用數(shù)組來(lái)實(shí)現(xiàn)一些鏈表難以實(shí)現(xiàn)的操作。ResizingArrayStack是控制它們的內(nèi)存使用的樣板。 問(wèn) 為什么將Node聲明為嵌套類(lèi)？為什么使用private？ 答 將Node聲明為私有的嵌套類(lèi)之后，我們可以將Node的方法和實(shí)例變量的訪(fǎng)問(wèn)范圍限制在包含它的類(lèi)中。私有嵌套類(lèi)的一個(gè)特點(diǎn)是只有包含它的類(lèi)能夠直接訪(fǎng)問(wèn)它的實(shí)例變量，因此無(wú)需將它的實(shí)例變量聲明為public或是private。專(zhuān)業(yè)背景較強(qiáng)的讀者注意：非靜態(tài)的嵌套類(lèi)也被稱(chēng)為內(nèi)部類(lèi)，因此從技術(shù)上來(lái)說(shuō)我們的Node類(lèi)也是內(nèi)部類(lèi)，盡管非泛型的類(lèi)也可以是靜態(tài)的。 問(wèn) 當(dāng)我輸入javac Stack.java運(yùn)行算法1.2和其他程序時(shí)，我發(fā)現(xiàn)了Stack.class和Stack$Node.class兩個(gè)文件。第二個(gè)文件是做什么用的？ 答 第二個(gè)文件是為內(nèi)部類(lèi)Node創(chuàng)建的。Java的命名規(guī)則會(huì)使用$分隔外部類(lèi)和內(nèi)部類(lèi)。 問(wèn) Java標(biāo)準(zhǔn)庫(kù)中有棧和隊(duì)列嗎？ 答 有，也沒(méi)有。Java有一個(gè)內(nèi)置的庫(kù)，叫做java.util.Stack，但你需要棧的時(shí)候請(qǐng)不要使用它。它新增了幾個(gè)一般不屬于棧的方法，例如獲取第i個(gè)元素。它還允許從棧底添加元素（而非棧頂），所以它可以被當(dāng)做隊(duì)列使用！盡管擁有這些額外的操作看起來(lái)可能很有用，但它們其實(shí)是累贅。我們使用某種數(shù)據(jù)類(lèi)型不僅僅是為了獲得我們能夠想象的各種操作，也是為了準(zhǔn)確地指定我們所需要的操作。這么做的主要好處在于系統(tǒng)能夠防止我們執(zhí)行一些意外的操作。java.util.Stack的API是寬接口的一個(gè)典型例子，我們通常會(huì)極力避免出現(xiàn)這種情況。

編輯推薦

Sedgewick之巨著，與高德納TAOCP一脈相承幾十年多次修訂，經(jīng)久不衰的暢銷(xiāo)書(shū)涵蓋所有程序員必須掌握的50種算法

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法（第4版） PDF格式下載

---