高效數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與分析，長(zhǎng)期以來(lái)一直被認(rèn)為是計(jì)算領(lǐng)域的一個(gè)重要主題，同時(shí)也是計(jì)算機(jī)科學(xué)與計(jì)算機(jī)工程本科教學(xué)中的核心課程。本書介紹數(shù)據(jù)結(jié)構(gòu)和算法，包括其設(shè)計(jì)、分析和實(shí)現(xiàn)，可在初級(jí)數(shù)據(jù)結(jié)構(gòu)或中級(jí)算法導(dǎo)論課程中使用。我們隨后會(huì)更詳細(xì)地討論如何在這些課程中使用本書。
為了提高軟件開發(fā)的健壯性和可重用性，我們?cè)诒緯�中采取一致的面向�(qū)ο蟮囊暯�。面向�(qū)ο蠓椒ǖ囊粋�(gè)主要思想是數(shù)據(jù)應(yīng)該被封裝，然后提供訪問(wèn)和修改它們的方法。我們不能簡(jiǎn)單地將數(shù)據(jù)看作字節(jié)和地址的集合，數(shù)據(jù)對(duì)象是抽象數(shù)據(jù)類型（Abstract Data Type，ADT）的實(shí)例，其中包括可在這種類型的數(shù)據(jù)對(duì)象上執(zhí)行的操作方法的集合。我們強(qiáng)調(diào)的是對(duì)于一個(gè)特定的ADT可能有幾種不同的實(shí)現(xiàn)策略，并探討這些選擇的優(yōu)點(diǎn)和缺點(diǎn)。我們幾乎為書中的所有數(shù)據(jù)結(jié)構(gòu)和算法都提供了完整的Python實(shí)現(xiàn)，并介紹了將這些實(shí)現(xiàn)組織為可重用的組件所需的重要的面向?qū)ο笤O(shè)計(jì)模式。
通過(guò)閱讀本書，讀者可以：
對(duì)常見數(shù)據(jù)集合的抽象有一定了解（如棧、隊(duì)列、表、樹、圖）。
理解生成常用數(shù)據(jù)結(jié)構(gòu)的高效實(shí)現(xiàn)的算法策略。
通過(guò)理論方法和實(shí)驗(yàn)方法分析算法的性能，并了解競(jìng)爭(zhēng)策略之間的權(quán)衡。
明智地利用編程語(yǔ)言庫(kù)中已有的數(shù)據(jù)結(jié)構(gòu)和算法。
擁有大多數(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法的具體實(shí)現(xiàn)經(jīng)驗(yàn)。
應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法來(lái)解決復(fù)雜的問(wèn)題。
為了達(dá)到最后一個(gè)目標(biāo)，我們?cè)跁�中提供了�?shù)據(jù)結(jié)構(gòu)的很多應(yīng)用實(shí)例，包括：文本處理系統(tǒng)，結(jié)構(gòu)化格式（如HTML）的標(biāo)簽匹配，簡(jiǎn)單的密碼技術(shù)，文字頻率分析，自動(dòng)幾何布局，霍夫曼編碼，DNA序列比對(duì)，以及搜索引擎索引。
本書特色
本書主要基于由Goodrich和Tamassia所著的《Data Structures and Algorithms in Java》，以及由Goodrich、Tamassia和Mount所著的《Data Structures and Algorithms in C++》編寫而成。然而，我們并不是簡(jiǎn)單地用Python語(yǔ)言實(shí)現(xiàn)以上書籍的內(nèi)容。為了充實(shí)內(nèi)容，我們重新設(shè)計(jì)了本書：
對(duì)全部代碼進(jìn)行了重新設(shè)計(jì)，以充分利用Python的優(yōu)勢(shì)，如使用生成器迭代集合的元素。
在Java和C++版本中，我們提供了很多偽代碼，而本書則提供了Python實(shí)現(xiàn)的完整代碼。
在一般情況下，ADT被定義為與Python內(nèi)建數(shù)據(jù)類型和Python的collections模塊具有一致的接口。
第5章深入探討了Python中基于動(dòng)態(tài)數(shù)組的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，如list、tuple和str類。新增的附錄A提供了關(guān)于str類功能的進(jìn)一步講解。
重新繪制或修改了超過(guò)450幅插圖。
經(jīng)過(guò)新增和修訂，練習(xí)的總數(shù)達(dá)到750個(gè)。
在線資源
本書提供一系列豐富的在線資源，可訪問(wèn)以下網(wǎng)站獲取：
www.wiley.com/college/goodrich
鼓勵(lì)學(xué)生在學(xué)習(xí)本書時(shí)使用這個(gè)網(wǎng)址，以更有效地進(jìn)行練習(xí)并提高對(duì)所學(xué)知識(shí)的認(rèn)識(shí)。也歡迎教師使用本網(wǎng)站來(lái)幫助規(guī)劃、組織和展示他們的課程材料。對(duì)于教師和學(xué)生而言，網(wǎng)站中包含一系列與本書主題相關(guān)的教學(xué)資源，由于它們是有附加價(jià)值的，所以一些網(wǎng)上資源受密碼保護(hù)。
對(duì)于所有的讀者，尤其是學(xué)生，我們有以下資源：
書中所有Python程序的源代碼。
提供給教師的PDF講義版PPT（每頁(yè)四張）。
保存所有練習(xí)提示的數(shù)據(jù)庫(kù)，以練習(xí)的編號(hào)為索引。
對(duì)于使用本書的教師，我們有以下額外的教學(xué)輔助資源：
本書練習(xí)的答案。
書中所有圖形和插圖的彩色版本。
PPT和PDF版本的幻燈片，其中PDF版本為每頁(yè)一張。
PPT是完全可編輯的，教師可根據(jù)自己的課程需求進(jìn)行修改。在教師使用本書作為教材時(shí)，所有的在線資源不收取額外費(fèi)用。
內(nèi)容和組織
書中各章節(jié)的內(nèi)容循序漸進(jìn)，適于教學(xué)。從Python編程和面向?qū)ο笤O(shè)計(jì)的基礎(chǔ)開始，然后逐漸增加如算法分析和遞歸之類的基礎(chǔ)技術(shù)。在本書的主體部分中，我們展示了基本的數(shù)據(jù)結(jié)構(gòu)和算法，并且包括對(duì)內(nèi)存管理的討論（也是數(shù)據(jù)結(jié)構(gòu)的架構(gòu)基礎(chǔ)）。本書的章節(jié)安排如下：
第1章　Python入門
第2章　面向?qū)ο缶幊?
第3章　算法分析
第4章　遞歸
第5章　基于數(shù)組的序列
第6章　棧、隊(duì)列和雙端隊(duì)列
第7章　鏈表
第8章　樹
第9章　優(yōu)先級(jí)隊(duì)列
第10章　映射、哈希表和跳躍表
第11章　搜索樹
第12章　排序與選擇
第13章　文本處理
第14章　圖算法
第15章　內(nèi)存管理和B樹
附錄A　Python中的字符串
附錄B　有用的數(shù)學(xué)定理
預(yù)備知識(shí)
我們假設(shè)讀者至少接觸過(guò)一種高級(jí)語(yǔ)言，如C、C++、Python或Java，可以理解相關(guān)高級(jí)語(yǔ)言的主要概念，包括：
變量和表達(dá)式。
決策結(jié)構(gòu)（if語(yǔ)句和switch語(yǔ)句）。
迭代結(jié)構(gòu)（for循環(huán)和while循環(huán)）。
函數(shù)（無(wú)論是過(guò)程式方法還是面向?qū)ο蠓椒ǎ��?
對(duì)于已經(jīng)熟悉這些概念但還不清楚如何在Python中應(yīng)用的讀者，我們建議將第1章作為Python語(yǔ)言的入門。這本書主要討論數(shù)據(jù)結(jié)構(gòu)，而不是講解Python，因此并沒(méi)有詳盡介紹Python。
直到第2章才開始使用Python中的面向?qū)ο缶幊蹋�這一章對(duì)于那些Python新手以及熟悉Python但不熟悉面向?qū)ο缶幊痰娜硕际怯杏玫摹?
就數(shù)學(xué)背景而言，我們假定讀者多少熟悉些高中數(shù)學(xué)知識(shí)。即便如此，在第3章中，我們先討論了算法分析的7個(gè)最重要的功能。若所涉及的內(nèi)容超出了這7個(gè)功能，則作為可選章節(jié)，用星號(hào)（*）標(biāo)記。附錄B對(duì)其他有用的數(shù)學(xué)定理做了總結(jié)，包括初等概率等。
計(jì)算機(jī)科學(xué)課程的設(shè)計(jì)
為了幫助教師在IEEE/ACM 2013的框架下設(shè)計(jì)教學(xué)課程，下表描述了本書涵蓋的知識(shí)要點(diǎn)。
知識(shí)要點(diǎn) 相關(guān)章節(jié)
AL/基本分析 第3章，4.2節(jié)，12.2.4節(jié)
AL/算法策略 12.2.1節(jié)，13.2.1節(jié)，13.3節(jié)，13.4.2節(jié)
AL/基本數(shù)據(jù)結(jié)構(gòu)與算法 4.1.3節(jié)，5.5.2節(jié)，9.4.1節(jié)，9.3節(jié)，10.2節(jié)，11.1節(jié)，13.2節(jié)，第12章，第14章的大部分內(nèi)容
AL/高級(jí)數(shù)據(jù)結(jié)構(gòu) 5.3節(jié)，10.4節(jié)，11.2～11.6節(jié)，12.3.1節(jié)，13.5節(jié)，14.5節(jié)，15.3節(jié)
AR/內(nèi)存系統(tǒng)組織和架構(gòu) 第15章
DS/集合、關(guān)系和功能 10.5.1節(jié)，10.5.2節(jié)，9.4節(jié)
DS/證明技巧 3.4節(jié)，4.2節(jié)，5.3.2節(jié)，9.3.6節(jié)，12.4.1節(jié)
DS/基礎(chǔ)計(jì)數(shù) 2.4.2節(jié)，6.2.2節(jié)，12.2.4節(jié)，8.2.2節(jié)，附錄B
DS/圖和樹 第8章和第14章的大部分內(nèi)容
DS/離散概率 1.11節(jié)，10.2節(jié)，10.4.2節(jié)，12.3.1節(jié)
PL/面向?qū)ο缶幊?本書的大部分內(nèi)容，特別是第2章以及7.4節(jié)、9.5.1節(jié)、10.1.3節(jié)和11.2節(jié)
PL/函數(shù)式編程 1.10節(jié)
SDF/算法和設(shè)計(jì) 2.1節(jié)，3.3節(jié)，12.2.1節(jié)
SDF/基本編程概念 第1章，第4章
SDF/基本數(shù)據(jù)結(jié)構(gòu) 第6章，第7章，附錄A，1.2.1節(jié)，5.2節(jié)，5.4節(jié)，9.1節(jié)，10.1節(jié)
SDF/開發(fā)方法 1.7節(jié)，2.2節(jié)
SE/軟件設(shè)計(jì) 2.1節(jié)，2.1.3節(jié)