數(shù)據(jù)結(jié)構(gòu)與算法

內(nèi)容概要

　　《國(guó)外計(jì)算機(jī)科學(xué)經(jīng)典教材·數(shù)據(jù)結(jié)構(gòu)與算法：C++版（第3版）》全面系統(tǒng)地介紹了計(jì)算機(jī)科學(xué)教育中的一個(gè)重要組成部分——數(shù)據(jù)結(jié)構(gòu)，并以C++語(yǔ)言實(shí)現(xiàn)相關(guān)的算法。書(shū)中主要強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu)和算法之間的聯(lián)系，使用面向?qū)ο蟮姆椒ń榻B數(shù)據(jù)結(jié)構(gòu)，其內(nèi)容包括算法的復(fù)雜度分析、鏈表、棧隊(duì)列、遞歸技術(shù)、二叉樹(shù)、圖、排序以及散列。《國(guó)外計(jì)算機(jī)科學(xué)經(jīng)典教材·數(shù)據(jù)結(jié)構(gòu)與算法：C++版（第3版）》還清晰地闡述了同類教材中較少提到的內(nèi)存管理、數(shù)據(jù)壓縮和字符串匹配主題。書(shū)中包含大量的示例分析和圖形，便于讀者進(jìn)一步理解和鞏固所學(xué)的知識(shí)?！　　秶?guó)外計(jì)算機(jī)科學(xué)經(jīng)典教材·數(shù)據(jù)結(jié)構(gòu)與算法：C++版（第3版）》適用于計(jì)算機(jī)科學(xué)及其他相關(guān)專業(yè)的師生。對(duì)于需要參加計(jì)算機(jī)考試，或者希望自學(xué)計(jì)算機(jī)軟件開(kāi)發(fā)的人員也大有裨益。

作者簡(jiǎn)介

　　Adam Drozdek，畢業(yè)于美國(guó)萊特州立大學(xué)，現(xiàn)任迪尤肯大學(xué)計(jì)算機(jī)科學(xué)系副教授，曾出版暢銷教材，包括Data Structures and Algorlthms;n Java和Elements of Data Compression等。

書(shū)籍目錄

第1章 C++面向?qū)ο蟪绦蛟O(shè)計(jì)1.1 抽象數(shù)據(jù)類型1.2 封裝1.3 繼承1.4 指針1.4.1 指針和數(shù)組1.4.2 指針和復(fù)制構(gòu)造函數(shù)1.4.3 指針和析構(gòu)函數(shù)1.4.4 指針和引用變量1.4.5 函數(shù)指針1.5 多態(tài)性1.6 C++和面向?qū)ο蟪绦蛟O(shè)計(jì)1.7 標(biāo)準(zhǔn)模板庫(kù)1.7.1 容器1.7.2 迭代器1.7.3 算法1.7.4 函數(shù)對(duì)象1.8 標(biāo)準(zhǔn)模板庫(kù)中的向量1.9 數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο缶幊?.10 案例分析：隨機(jī)訪問(wèn)文件1.11 習(xí)題1.12 程序設(shè)計(jì)作業(yè)第2章 復(fù)雜度分析2.1 計(jì)算復(fù)雜度和漸近復(fù)雜度2.2 大O符號(hào)2.3 大O符號(hào)的性質(zhì)2.4 Q符號(hào)與@符號(hào)2.5 可能的問(wèn)題2.6 復(fù)雜度舉例2.7 確定漸近復(fù)雜度舉例2.8 最好、平均和最壞情況2.9 阻尼復(fù)雜度2.10 NP完整性2.11 習(xí)題第3章 鏈表3.1 單鏈表3.1.1 插入3.1.2 刪除3.1.3 查找3.2 雙鏈表3.3 循環(huán)鏈表3.4 跳躍鏈表3.5 自組織鏈表3.6 稀疏表3.7 標(biāo)準(zhǔn)模板庫(kù)中的鏈表3.8 標(biāo)準(zhǔn)模板庫(kù)中的雙端隊(duì)列3.9 小結(jié)3.10 案例分析：圖書(shū)館3.11 習(xí)題3.12 程序設(shè)計(jì)作業(yè)第4章 棧與隊(duì)列4.1 棧4.2 隊(duì)列4.3 優(yōu)先隊(duì)列4.4 標(biāo)準(zhǔn)模板庫(kù)中的棧4.5 標(biāo)準(zhǔn)模板庫(kù)中的隊(duì)列4.6 標(biāo)準(zhǔn)模板庫(kù)中的優(yōu)先隊(duì)列4.7 案例分析：迷宮問(wèn)題4.8 習(xí)題4.9 程序設(shè)計(jì)作業(yè)第5章 遞歸5.1 遞歸定義5.2 函數(shù)調(diào)用與遞歸實(shí)現(xiàn)5.3 遞歸調(diào)用的剖析5.4 尾部遞歸5.5 非尾部遞歸5.6 間接遞歸5.7 嵌套遞歸5.8 不合理遞歸5.9 回溯5.10 小結(jié)5.11 案例分析：遞歸下降解釋器5.12 習(xí)題5.13 程序設(shè)計(jì)作業(yè)第6章 二叉樹(shù)6.1 樹(shù)、二叉樹(shù)和二叉搜索樹(shù)6.2 二叉樹(shù)的實(shí)現(xiàn)6.3 二叉搜索樹(shù)的查找6.4 樹(shù)的遍歷6.4.1 廣度優(yōu)先遍歷6.4.2 深度優(yōu)先遍歷6.4.3 不用棧實(shí)現(xiàn)的深度優(yōu)先遍歷6.5 插入6.6 刪除6.6.1 合并刪除6.6.2 通過(guò)復(fù)制進(jìn)行刪除6.7 樹(shù)的平衡6.7.1 DSW算法6.7.2 AVL樹(shù)6.8 自調(diào)整樹(shù)6.8.1 自重新構(gòu)造樹(shù)6.8.2 “張開(kāi)”策略6.9 堆6.9.1 將堆作為優(yōu)先隊(duì)列6.9.2 將數(shù)組組織為堆6.10 波蘭記號(hào)和表達(dá)式樹(shù)6.11 案例分析：計(jì)算單詞出現(xiàn)的頻率6.12 習(xí)題6.13 程序設(shè)計(jì)作業(yè)第7章 多叉樹(shù)7.1 B樹(shù)家族7.1.1 B樹(shù)7.1.2 B*樹(shù)7.1.3 B+樹(shù)7.1.4 前綴B+樹(shù)7.1.5 位樹(shù)7.1.6 R樹(shù)7.1.7 2-4樹(shù)7.1.8 標(biāo)準(zhǔn)模板庫(kù)中的集和多集7.1.9 標(biāo)準(zhǔn)模板庫(kù)中的映射和多映射7.2 trie7.3 小結(jié)7.4 案例分析：拼寫(xiě)檢查器7.5 習(xí)題7.6 程序設(shè)計(jì)作業(yè)第8章 圖8.1 圖的表示法8.2 圖的遍歷8.3 最短路徑8.4 環(huán)的檢測(cè)8.5 生成樹(shù)8.6 連通性8.6.1 無(wú)向圖中的連通性8.6.2 有向圖中的連通性8.7 拓?fù)渑判?.8 網(wǎng)絡(luò)8.8.1 最大流8.8.2 成本最低的最大流8.9 匹配8.9.1 穩(wěn)定匹配問(wèn)題8.9.2 分配問(wèn)題8.9.3 非二分圖中的匹配集合8.10 歐拉（Eulerian）圖與漢密爾頓（Hamil tonian）圖8.10.1 歐拉圖8.10.2 漢密爾頓圖8.11 給圖加上顏色8.12 圖理論中的NP完整性問(wèn)題8.12.1 派系問(wèn)題8.12.2 三色問(wèn)題8.12.3 頂點(diǎn)覆蓋問(wèn)題8.12.4 漢密爾頓環(huán)問(wèn)題8.13 案例分析：唯一代表8.14 習(xí)題8.15 程序設(shè)計(jì)作業(yè)第9章 排序第10章 散列第11章 數(shù)據(jù)壓縮第12章 內(nèi)存管理第13章 字符串匹配附錄A 計(jì)算大O附錄B 標(biāo)準(zhǔn)模板庫(kù)中的算法附錄C NP完整性

章節(jié)摘錄

　　5.10 小結(jié)　　在了解了所有的例子（后面還有一個(gè)例子）之后，對(duì)作為編程工具的遞歸有什么認(rèn)識(shí)呢？與數(shù)據(jù)結(jié)構(gòu)中的其他問(wèn)題一樣，應(yīng)該在作出正確判斷的基礎(chǔ)上使用遞歸。什么時(shí)候使用遞歸、什么時(shí)候不使用遞歸，沒(méi)有通用的規(guī)則，應(yīng)當(dāng)視情況而定。遞歸的效率常常比與它等價(jià)的迭代形式低。但是如果遞歸程序花費(fèi)的時(shí)間為100毫秒（ms），而迭代程序花費(fèi)的時(shí)間為10ms，盡管后者的速度比前者快十倍，但其中的差別很難察覺(jué)到。另外遞歸程序的代碼具有清晰性、可讀性和簡(jiǎn)單性的特點(diǎn)，所以運(yùn)行時(shí)間上的差距可以不考慮。遞歸方法比迭代方法一般要簡(jiǎn)單一些，和原始算法在邏輯上的一致性較好。階乘函數(shù)和冪函數(shù)就是這樣的例子，本章的后面還會(huì)看到一些更有趣的例子?！　”M管每個(gè)遞歸過(guò)程都可以轉(zhuǎn)化為迭代形式，但轉(zhuǎn)化并不總是一件輕而易舉的事情。特別是轉(zhuǎn)化過(guò)程可能包括對(duì)棧的顯式操作。這時(shí)“時(shí)空交換”（time-space trade-off）就發(fā)揮作用了：使用迭代方法常常需要用一種新的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)棧的功能，而使用遞歸方法則減輕了程序員的工作量，即將工作轉(zhuǎn)交給系統(tǒng)完成。無(wú)論使用哪種方法，如果其中包括了非尾部循環(huán)，棧的維護(hù)常常需要由程序員或者系統(tǒng)完成。但是程序員可以決定讓誰(shuí)來(lái)完成這項(xiàng)工作?！　∮袃煞N場(chǎng)合，使用非遞歸的實(shí)現(xiàn)方式更為可取，盡管遞歸方法更自然一些。第一種情況是在所謂的實(shí)時(shí)系統(tǒng)中，快速響應(yīng)對(duì)程序正常發(fā)揮作用至關(guān)重要。例如在軍事環(huán)境中，在航天器中，或者在某些類型的科學(xué)實(shí)驗(yàn)中，響應(yīng)時(shí)間是10ms還是100ms有很大的差別。第二種情況是鼓勵(lì)程序員在執(zhí)行好幾百次的程序中避免使用遞歸，這種程序的最佳例子是編譯器?！　〔贿^(guò)不要太死板地看待這些規(guī)則，因?yàn)橛袝r(shí)遞歸實(shí)現(xiàn)比非遞歸實(shí)現(xiàn)的速度還快。硬件可能會(huì)帶有內(nèi)置的棧操作，顯著提高了對(duì)運(yùn)行時(shí)棧進(jìn)行操作的函數(shù)的速度，比如遞歸函數(shù)。運(yùn)行一個(gè)簡(jiǎn)單的程序，分別采用遞歸方式和迭代方式，并對(duì)兩者的運(yùn)行時(shí)間進(jìn)行比較，這樣會(huì)有助于決定是否應(yīng)該采用遞歸方式——實(shí)際上，遞歸可以比迭代方式執(zhí)行得更快。如果使用了尾部遞歸，這樣的測(cè)試就特別重要。不過(guò)，如果在迭代方式中還要使用棧，則推薦使用遞歸方式，因?yàn)檫@兩種方式的運(yùn)行時(shí)間的差距不明顯——一般不會(huì)相差10倍?！　　?/pre>




編輯推薦
　　《國(guó)外計(jì)算機(jī)科學(xué)經(jīng)典教材·數(shù)據(jù)結(jié)構(gòu)與算法：C++版（第3版）》的示例分析貫穿全文，便于學(xué)生在真實(shí)的環(huán)境下了解數(shù)據(jù)結(jié)構(gòu)的概念。　　《國(guó)外計(jì)算機(jī)科學(xué)經(jīng)典教材·數(shù)據(jù)結(jié)構(gòu)與算法：C++版（第3版）》每章最后都提供了程序設(shè)計(jì)作業(yè)，給學(xué)生提供大量的實(shí)踐機(jī)會(huì)，鞏固所學(xué)內(nèi)容?！　　秶?guó)外計(jì)算機(jī)科學(xué)經(jīng)典教材·數(shù)據(jù)結(jié)構(gòu)與算法：C++版（第3版）》配以豐富的圖示，便于學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)有直觀的理解。





圖書(shū)封面



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




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



還沒(méi)讀過(guò)(28)
勉強(qiáng)可看(203)
一般般(347)
內(nèi)容豐富(1441)
強(qiáng)力推薦(118)


 


    數(shù)據(jù)結(jié)構(gòu)與算法 PDF格式下載