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

　　本書采用程序員最愛用的面向?qū)ο驝++語言來描述數(shù)據(jù)結(jié)構(gòu)和算法，并把數(shù)據(jù)結(jié)構(gòu)原理和算法分析技術(shù)有機(jī)地結(jié)合在一起，系統(tǒng)介紹了各種類型的數(shù)據(jù)結(jié)構(gòu)和排序、檢索的各種方法。作者非常注意對每一種數(shù)據(jù)結(jié)構(gòu)不同存儲方法及有關(guān)算法進(jìn)行分析比較。書中還引入了一些比較高級的數(shù)據(jù)結(jié)構(gòu)與先進(jìn)的算法分析技術(shù)，并介紹了可計(jì)算性理論的一般知識。本版的重要改進(jìn)在于引入了參數(shù)化的模板，從而提高了算法中數(shù)據(jù)類型的通用性，支持高效的代碼重用。本書概念清楚、邏輯性強(qiáng)、內(nèi)容新穎，可作為大專院校計(jì)算機(jī)軟件專業(yè)與計(jì)算機(jī)應(yīng)用專業(yè)學(xué)生的教材和參考書，也可供計(jì)算機(jī)工程技術(shù)人員參考。譯者序數(shù)據(jù)結(jié)構(gòu)與算法分析是一門計(jì)算機(jī)專業(yè)十分重要的基礎(chǔ)課，計(jì)算機(jī)科學(xué)各領(lǐng)域及各種應(yīng)用軟件都要使用相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法。當(dāng)面臨一個(gè)新的設(shè)計(jì)問題時(shí)，設(shè)計(jì)者需要選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)出滿足一定？奔浜涂占湎拗頻撓行惴?。本书作者把数据结官?fù)算法分析又x厝嗪顯諞槐窘灘鬧?，有助釉溋者根据问题的袨?zāi)恃≡窈俠淼氖萁峁?，并对时间空间竻灿性进行必要的控制。?？本書采用當(dāng)前流行的面向?qū)ο蟮腃++語言來描述數(shù)據(jù)結(jié)構(gòu)和算法，因?yàn)镃++語言是程序員最廣泛使用的語言。因此，程序員可以把本書中的許多？惴ㄖ苯佑τ糜誚吹氖導(dǎo)氏钅恐?。尽梗繑?shù)據(jù)結(jié)構(gòu)和算法在設(shè)計(jì)本質(zhì)上還是很底層的東西，并不像軟件工程大型項(xiàng)目設(shè)計(jì)那樣，對面向?qū)ο蠓椒ň哂兄苯拥囊蕾囆裕虼擞腥藭J(rèn)為并不需要采用面向?qū)ο蟮母呒壖夹g(shù)來描述底層的算法，但是采用C++語言能夠更好地體現(xiàn)抽象數(shù)據(jù)類型的概念，從而更本質(zhì)地描述數(shù)據(jù)結(jié)構(gòu)和算法。為了使本書清晰易懂，作者有意回避了C++的某些重要特性。這個(gè)版本的重要改進(jìn)是引入了參數(shù)化的模板，從而提高了算法中數(shù)據(jù)類型的通用性，支持高效的代碼重用。本書包括四大部分內(nèi)容，第一部分是準(zhǔn)備工作，介紹了一些基本概念和術(shù)語，以及基本的數(shù)學(xué)知識。第二部分介紹了最基本的數(shù)據(jù)結(jié)構(gòu)，依次為線性表（包括棧和隊(duì)列）、二叉樹和樹。對每種數(shù)據(jù)結(jié)構(gòu)的講解都從其數(shù)學(xué)特性入手，先介紹抽象數(shù)據(jù)類型，然后再討論不同的存儲方法，并且研究不同存儲方法的可能算法。值得贊賞的是，作者結(jié)合算法分析來討論各種存儲方法和算法的利弊，摒棄那些不適宜的方法，這樣就調(diào)動了讀者思維，使其可從中學(xué)到考慮問題的方法。這種“授人以漁”的策略使讀者在今后設(shè)計(jì)和應(yīng)用數(shù)據(jù)結(jié)構(gòu)時(shí)能夠全面地考慮各種因素，并選擇最佳方案。作為最常用的算法，排序和檢索歷來是數(shù)據(jù)結(jié)構(gòu)討論的重點(diǎn)問題。這在第三部分的第9章和第10章中進(jìn)行了詳盡的討論。排序算法最能體現(xiàn)算法分析的魅力，它的算法速度要求非常高：其中內(nèi)排序主要考慮的是怎樣減少關(guān)鍵碼之間的比較次數(shù)和記錄交換次數(shù)，以提高排序速度；而外排序則考慮外存的特性，盡量減少訪問操作，以提高排序速度。第8章證明了所有基于比較的排序算法的時(shí)間代價(jià)是Θ（nlogn），這也是排序問題的時(shí)間代價(jià)。檢索則考慮怎樣提高檢索速度，這往往與存儲方法有關(guān)。書中介紹了幾種高效的數(shù)據(jù)結(jié)構(gòu)，如自組織線性表、散列表、B樹和B+樹等，都具有極好的檢索性能。第四部分介紹了數(shù)據(jù)結(jié)構(gòu)的應(yīng)用與一些高級主題，其中包括圖、跳躍表、廣義表和稀疏矩陣等更復(fù)雜的線性表結(jié)構(gòu)、還包括Trie結(jié)構(gòu)、AVL樹等復(fù)雜樹結(jié)構(gòu)，以及kd樹、PR四分樹等空間數(shù)據(jù)結(jié)構(gòu)。另外，第四部分還簡單介紹了求和、遞歸關(guān)系分析和均攤分析等高級算法分析技術(shù)，這些技術(shù)對于提高程序員的算法分析能力具有重要作用。本書的前言及第1章至第7章由張銘翻譯，第8章至第15章由劉曉丹翻譯。另外，肖毅、柴雯、肖之屏、劉NFB35、趙培翔、李麗、王蜀安、張海東、劉振飛和李健等人也參加了本書的翻譯工作，在此對他們的辛勤勞動表示感謝。由于水平有限，難免有不妥之處，歡迎批評指正。前言我們研究數(shù)據(jù)結(jié)構(gòu)的目的是為了學(xué)會編寫更高效的程序。既然現(xiàn)在的計(jì)算機(jī)速度一年比一年快，為什么還會需要高效率的程序呢？這是由于人類解決問題的雄心與能力是同步增長的?，F(xiàn)代計(jì)算技術(shù)在計(jì)算能力和存儲容量上的革命，僅僅提供了計(jì)算更復(fù)雜問題的有效工具，而程序的高效性要求永遠(yuǎn)也不會過時(shí)。程序高效性的要求不會，也不應(yīng)該與合理的設(shè)計(jì)和簡明清晰的編碼相矛盾。高效程序的設(shè)計(jì)基于良好的信息組織和優(yōu)秀的算法，而不是基于“編程小伎倆”。如果一個(gè)程序員沒有掌握程序設(shè)計(jì)簡明清晰的基本原理，就不可能編寫出有效的程序。反過來講，簡潔的程序需要合理的數(shù)據(jù)組織和清晰的算法。大多數(shù)計(jì)算機(jī)科學(xué)系的課程設(shè)置都已意識到，要培養(yǎng)良好的程序設(shè)計(jì)技能，首先應(yīng)該強(qiáng)調(diào)基本的軟件工程原理。因此，一旦程序員學(xué)會了程序設(shè)計(jì)和實(shí)現(xiàn)簡明清晰的原理，下一步就應(yīng)該學(xué)習(xí)有效的數(shù)據(jù)組織和算法，以提高程序的效率。途徑本書描述了許多用于表示數(shù)據(jù)的技術(shù)。這些技術(shù)體現(xiàn)在以下的原則中：1.〖ZK（＃〗每一種數(shù)據(jù)結(jié)構(gòu)和每一個(gè)算法都有其時(shí)間、空間的代價(jià)和效率。當(dāng)面臨一個(gè)新的設(shè)計(jì)問題時(shí)，設(shè)計(jì)者要透徹地掌握權(quán)衡時(shí)間、空間代價(jià)和算法有效性的方法，以適應(yīng)問題的需要。這就要懂得算法分析的原理，而且還需要了解所使用的物理介質(zhì)的特性（例如，數(shù)據(jù)存儲在磁盤上與存儲在主存中時(shí)，就有不同的考慮）。2.與代價(jià)和效率有關(guān)的是時(shí)空權(quán)衡。例如，人們通常增加空間代價(jià)來減少運(yùn)行時(shí)間，反之亦然。程序員所面對的時(shí)空權(quán)衡問題普遍存在于軟件設(shè)計(jì)和實(shí)現(xiàn)的各個(gè)階段，因此必須把這個(gè)概念牢記在心。3.程序員應(yīng)該充分了解一些現(xiàn)成的方法，以免進(jìn)行不必要的重復(fù)開發(fā)工作。因此，學(xué)生們需要了解經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法。4.數(shù)據(jù)結(jié)構(gòu)服從于應(yīng)用需求。學(xué)生們必須把分析應(yīng)用需求放在第一位，然后再尋找一種與實(shí)際應(yīng)用相匹配的數(shù)據(jù)結(jié)構(gòu)。要做到這一點(diǎn)，需要應(yīng)用上述三條原則。〖ZK）〗教學(xué)建議數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)的書籍往往囿于下面兩種情形之一〖BFQ〗：〖BF〗一種是教材，一種是百科全書。有些書籍試圖融合這兩種編排，但通常是二者都沒有組織好，而本書是作為教材來編寫的。我相信了解那些用于選擇或設(shè)計(jì)可解決問題的數(shù)據(jù)結(jié)構(gòu)的基本原理十分重要，會比死記硬背書本內(nèi)容重要得多。因此，本書中涵蓋了大多數(shù)（但不是所有的）標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。為了闡述一些重要原理，也包括了某些并非廣泛使用的數(shù)據(jù)結(jié)構(gòu)。？磽?，本蕶┲x菇檣芰？一些相對較新但即將得到廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)。本書可作為本科生一個(gè)學(xué)期的教學(xué)內(nèi)容，也可作為專業(yè)技術(shù)人員的自學(xué)教材。讀者應(yīng)該具備編程經(jīng)驗(yàn)，最好學(xué)過相當(dāng)于兩個(gè)學(xué)期的結(jié)構(gòu)化程序設(shè)計(jì)語言（如Pascal或C語言），并且最好懂得一些C++的基本知識。早已熟悉遞歸的讀者具有一定的？攀啤Ｏ刃尥暌幻藕？的離散數(shù)學(xué)課程對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)也大有裨益。第2章中給出了一些理解本書所必備的數(shù)學(xué)預(yù)備知識。讀者遇到不熟悉的數(shù)學(xué)問題時(shí)，可以查閱這一章中的相關(guān)內(nèi)容。盡管本書應(yīng)該一個(gè)學(xué)期完成，但書中超過了一個(gè)學(xué)期的內(nèi)容，這樣就可以為教師提供一些選擇的余地。二年級學(xué)生的基本數(shù)據(jù)結(jié)構(gòu)和算法分析背景不太多，可以給他們詳細(xì)地講解第1～12章的內(nèi)容，再從第13章中選擇一些專題來講解，我就是這樣來給二年級學(xué)生講課的。背景知識更豐富的學(xué)生，可以先讀第1章，跳過第2章中除“深入學(xué)習(xí)導(dǎo)讀”之外的內(nèi)容，簡要地瀏覽第3章和第4章（請著重閱讀4.1.3小節(jié)和4.2小節(jié)），然后詳細(xì)閱讀其余的章節(jié)。另外，教師可以根據(jù)程序設(shè)計(jì)實(shí)習(xí)的需要，選擇第13章中的某些專題內(nèi)容。第13章是針對進(jìn)行較大的程序設(shè)計(jì)練習(xí)而編寫的。我建議所有選修數(shù)據(jù)結(jié)構(gòu)的學(xué)生，都應(yīng)該做一些高級樹結(jié)構(gòu)或其他較復(fù)雜的動態(tài)數(shù)據(jù)結(jié)構(gòu)的上機(jī)實(shí)習(xí)，如第12章中的跳躍表或稀疏矩陣。所有這些數(shù)據(jù)結(jié)構(gòu)都沒有二叉檢索樹難，學(xué)完第5章的學(xué)生都有能力來實(shí)現(xiàn)它們。本書盡量合理地安排內(nèi)容順序。教師可以根據(jù)需要自由地重新組織內(nèi)容。讀者掌握了第1至第6章后，以下的內(nèi)容就相對獨(dú)立了。顯然，外排序依賴于內(nèi)排序和磁盤文件系統(tǒng)。Kruskal最小支撐樹算法使用了6.2小節(jié)關(guān)于UNION/FIND的算法。9.2小節(jié)的自組織線性表談到了8.3小節(jié)討論的緩沖區(qū)置換技術(shù)。第14章的討論基于本書的例題。15.2小節(jié)依賴于圖論知識。一般情況下，大多數(shù)主題都只依賴于同一章中討論過的內(nèi)容。關(guān)于C++本書中所有示例程序都是用C++來編寫的，但也并不想難倒那些對C++不熟悉的讀者。在努力保持C++優(yōu)點(diǎn)的同時(shí)，我盡量使示例程序簡明、清晰。C++在本書中只是作為闡釋數(shù)據(jù)結(jié)構(gòu)的工具，而且實(shí)際上只用了C++的一個(gè)小子集。特別是書中用到了C++隱蔽實(shí)現(xiàn)細(xì)節(jié)的特性，如類（class）、私有成員（privateclassmember）、構(gòu)造函數(shù)（constructor）、析構(gòu)函數(shù)（destructor）。這些特性支持著一個(gè)關(guān)鍵的概念，即體現(xiàn)于抽象數(shù)據(jù)類型（abstractdatatype）中的邏輯設(shè)計(jì)與體現(xiàn)于數(shù)據(jù)結(jié)構(gòu)中的物理實(shí)現(xiàn)的分離。為了使本書清晰易懂，我完全回避了C++的某些重要特性，并有意排除或盡量少用一些經(jīng)驗(yàn)豐富的C++程序員常用的特性，如類的層次（classhierarchy）、繼承（inheritance）和虛函數(shù)（virtualfunction）。運(yùn)算符和函數(shù)的重載（overloading）也很少使用。C的原始語義比C++所提供的一些類似功能要好一些。當(dāng)然，上述C++的特性在實(shí)際程序中是合理的設(shè)計(jì)基礎(chǔ)，但是它們只能掩蓋而并沒有加強(qiáng)本書中所闡述的原理。例如，類的繼承在避免重復(fù)編碼和降低程序錯(cuò)誤率方面很重要，但是從教育學(xué)的標(biāo)準(zhǔn)觀點(diǎn)來看，類的繼承在若干類中分散了數(shù)據(jù)元素的描述，從而使得程序更難理解。因此，在本書中，當(dāng)類的繼承對闡述觀點(diǎn)有明顯作用時(shí)才使用繼承來定義類（例如第531小節(jié)）。但這并不意味著程序員都應(yīng)該遵從類似的原則，避免代碼重復(fù)和減少錯(cuò)誤是很重要的目標(biāo)，不要把本書中的示例程序直接復(fù)制到你自己的程序中，只把它們看做是對數(shù)據(jù)結(jié)構(gòu)原理的闡釋即可。我需要做出的最痛苦的選擇是：在示例代碼中是否使用模板（t

暫缺《數(shù)據(jù)結(jié)構(gòu)與算法分析：C++版》作者簡介