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

定　價(jià)：￥33.00

作　者：	鄧俊輝編著
出版社：	機(jī)械工業(yè)出版社
叢編項(xiàng)：	重點(diǎn)大學(xué)計(jì)算機(jī)教材
標(biāo)　簽：	數(shù)據(jù)結(jié)構(gòu)

購買這本書可以去

ISBN：	9787111182047	出版時(shí)間：	2006-02-01	包裝：	膠版紙
開本：	小16開	頁數(shù)：	309	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書充分展示了面向?qū)ο蠹夹g(shù)在現(xiàn)代數(shù)據(jù)結(jié)構(gòu)理論中的應(yīng)用，普遍采用了抽象、封裝及繼承等技術(shù)。本書既介紹了基本的數(shù)據(jù)結(jié)構(gòu)，包括棧、隊(duì)列、向量、列表結(jié)構(gòu)；也介紹了若干高級(jí)數(shù)據(jù)結(jié)構(gòu)，包括優(yōu)先隊(duì)列結(jié)構(gòu)、映射和詞典結(jié)構(gòu)、查找樹結(jié)構(gòu)等。并結(jié)合具體問題介紹了算法的應(yīng)用、實(shí)現(xiàn)及其分析方法，涉及的算法包括堆結(jié)構(gòu)的生成及調(diào)整算法、Huffman編碼樹算法、平衡查找樹的生成、插入和刪除算法，并著重介紹了串匹配的KMP和BM算法。本書還通過遍歷算法框架將各種圖算法統(tǒng)一起來，并基于遍歷算法模板加以實(shí)現(xiàn)，在同類教材中獨(dú)樹一幟。.本書圖文并茂，循序漸進(jìn)。書中代碼都配有詳盡而簡(jiǎn)潔的注釋。書中還結(jié)合各部分的具體內(nèi)容穿插了大量問題，以激發(fā)讀者的求知欲，培養(yǎng)良好的自學(xué)習(xí)慣和自學(xué)能力。本書適合用作計(jì)算機(jī)專業(yè)本科生教材或參考書。本書作者力圖突破此類教材多年來形成的定式，在很多方面都做了大膽嘗試。..在體例方面，作者結(jié)合多年教學(xué)實(shí)踐，對(duì)知識(shí)點(diǎn)進(jìn)行了重新整理編排，許多處理方法在同類教材中獨(dú)樹一幟，旨在將讀者引向更高層次，使讀者形成對(duì)數(shù)據(jù)結(jié)構(gòu)的宏觀認(rèn)識(shí)。在內(nèi)容方面，本書并未對(duì)各種數(shù)據(jù)結(jié)構(gòu)面面俱到，而是按照CC2001標(biāo)準(zhǔn)對(duì)必要知識(shí)點(diǎn)和技能要求精心加以裁剪，通過系統(tǒng)分類和啟發(fā)式講解，在基本數(shù)據(jù)結(jié)構(gòu)與高級(jí)數(shù)據(jù)結(jié)構(gòu)之間架起一座橋梁。在算法方面，本書不僅強(qiáng)調(diào)對(duì)復(fù)雜度等基本概念的把握，同時(shí)結(jié)合具體問題介紹算法復(fù)雜度的各種分析方法，尤其是分?jǐn)偡治龅雀呒?jí)技巧。而且所有數(shù)據(jù)結(jié)構(gòu)仍然構(gòu)成一個(gè)完整的體系，幫助讀者養(yǎng)成面向?qū)嶋H應(yīng)用的意識(shí)，并掌握構(gòu)建實(shí)際應(yīng)用的基本能力。...

作者簡(jiǎn)介

　　MichaelSpivak微分幾何方面世界知名的數(shù)學(xué)家，Publish-or-Perish出版社的創(chuàng)始人，1964年獲得普林斯頓大學(xué)博士學(xué)位，指導(dǎo)老師為菲爾茲獎(jiǎng)和沃爾夫獎(jiǎng)得主JohnMilnor。除本書外Spivak還著有五卷本AComprehensiveIntroductiontoDifferentialGeometry和Calculus等名著。

圖書目錄

前言
第1章算法及其復(fù)雜度.
1.1計(jì)算機(jī)與算法
1.1.1過指定垂足的直角邊
1.1.2三等分線段
1.1.3排序
1.1.4算法的定義
1.2算法性能的分析與評(píng)價(jià)
1.2.1三個(gè)層次
1.2.2時(shí)間復(fù)雜度及其度量
1.2.3空間復(fù)雜度
1.3算法復(fù)雜度及其分析
1.3.1O(1)——取非極端元素
1.3.2O(logn)——進(jìn)制轉(zhuǎn)換
1.3.3O(n)——數(shù)組求和
1.3.4O(n2)——起泡排序
1.3.5O(2r)——冪函數(shù)
1.4計(jì)算模型
1.4.1可解性
1.4.2有效町解
1.4.3下界
1.5遞歸
1.5.1線性遞歸
1.5.2遞歸算法的復(fù)雜度分析
1.5.3二分遞歸
1.5.4多分支遞歸
第2章棧與隊(duì)列
2.1棧
2.1.1棧ADT
2.1.2基于數(shù)組的簡(jiǎn)單實(shí)現(xiàn)
2.1.3Java虛擬機(jī)中的棧
2.1.4棧應(yīng)用實(shí)例
2.2隊(duì)列
2.2.1隊(duì)列ADT
2.2.2基于數(shù)組的實(shí)現(xiàn)
2.2.3隊(duì)列應(yīng)用實(shí)例
2.3鏈表
2.3.1單鏈表
2.3.2基于單鏈表實(shí)現(xiàn)棧
2.3.3基于單鏈表實(shí)現(xiàn)隊(duì)列
2.4位置
2.4.1位置ADT
2.4.2位置接口
2.5雙端隊(duì)列
2.5.1雙端隊(duì)列ADT
2.5.2雙端隊(duì)列接口
2.5.3雙向鏈表
2.5.4基于雙向鏈表實(shí)現(xiàn)的雙端隊(duì)列
第3章向量.列表與序列
3.1向量與數(shù)組
3.1.1向量ADT
3.1.2基于數(shù)組的簡(jiǎn)單實(shí)現(xiàn)
3.1.3基于可擴(kuò)充數(shù)組的實(shí)現(xiàn)
3.1.4java.util,ArrayList類和java.util.Vector類
3.2列表
3.2.1基于節(jié)點(diǎn)的操作
3.2.2由秩到位置
3.2.3列表ADT
3.2.4基于雙向鏈表實(shí)現(xiàn)的列表
3.3序列
3.3.1序列ADT
3.3.2基于雙向鏈表實(shí)現(xiàn)序列
3.3.3基于數(shù)組實(shí)現(xiàn)序列
3.4迭代器
3.4.1迭代器ADT
3.4.2迭代器接口
3.4.3迭代器的實(shí)現(xiàn)
3.4.4Java中的列表及迭代器
第4章樹
4.1術(shù)語及性質(zhì)
4.1.1節(jié)點(diǎn)的深度.樹的深度與高度
4.1.2節(jié)點(diǎn)的度與內(nèi)部節(jié)點(diǎn).外部節(jié)點(diǎn)
4.1.3路徑
4.1.4祖先.后代.子樹和節(jié)點(diǎn)的高度
4.1.5共同祖先及最低共同祖先
4.1.6有序樹.m叉樹
4.1.7二叉樹
4.1.8滿二叉樹與完全二叉樹
4.2樹ADT及其實(shí)現(xiàn)
4.2.1“父親-長(zhǎng)子-弟弟”模型
4.2.2樹ADT
4.2.3樹的Java接口
4.2.4基于鏈表實(shí)現(xiàn)樹
4.3樹的基本算法
4.3.1getSize()——統(tǒng)計(jì)(子)樹的規(guī)模
4.3.2getHeight()——計(jì)算節(jié)點(diǎn)的高度
4.3.3getDepth()——計(jì)算節(jié)點(diǎn)的深度
4.3.4前序.后序遍歷
4.3.5層次遍歷
4.3.6樹迭代器
4.4二叉樹ADT及其實(shí)現(xiàn)
4.4.1二叉樹ADT
4.4.2二叉樹的Java接口
4.4.3二叉樹類的實(shí)現(xiàn)
4.5二叉樹的基本算法
4.5.1getSize().getHeiglit()和getDepth()
4.5.2updateSize()
4.5.3updateHeight()
4.5.4updateDepth()
4.5.5secede()
4.5.6attachL()和attachR()
4.5.7二叉樹的遍歷
4.5.8直接前驅(qū).直接后繼的定位算法
4.6完全二叉樹的Java買現(xiàn)
4.6.1完全二叉樹的Java接口
4.6.2基于向量的實(shí)現(xiàn)
第5章優(yōu)先隊(duì)列
5.1優(yōu)先級(jí).關(guān)鍵碼.全序關(guān)系與優(yōu)先隊(duì)列
5.2條目與比較器
5.2.1條目
5.2.2比較器
5.2.3Comparator接口及其實(shí)現(xiàn)
5.3優(yōu)先隊(duì)列ADT及其Java接口
5.3.1優(yōu)先隊(duì)列的ADT描述
5.3.2優(yōu)先隊(duì)列的Java接口
5.3.3基于優(yōu)先隊(duì)列的排序器
5.4用向量實(shí)現(xiàn)優(yōu)先隊(duì)列
5.5用列表實(shí)現(xiàn)優(yōu)先隊(duì)列
5.5.1基于無序列表的實(shí)現(xiàn)及分析
5.5.2基于有序列表的實(shí)現(xiàn)及分析
5.6選擇排序與插入排序
5.6.1選擇排序
5.6.2插入排序
5.6.3效率比較
5.7堆的定義及性質(zhì)
5.7.1堆結(jié)構(gòu)
5.7.2完全性
5.8用堆實(shí)現(xiàn)優(yōu)先隊(duì)列
5.8.1基于堆的優(yōu)先隊(duì)列及其實(shí)現(xiàn)
5.8.2插入與上濾
5.8.3刪除與下濾
5.8.4改變?nèi)我夤?jié)點(diǎn)的關(guān)鍵碼
5.8.5建堆
5.9堆排序
5.9.1直接堆排序
5.9.2就地堆排序
5.10Huffman編碼樹
5.10.1二叉編碼樹
5.10.2最優(yōu)編碼樹
5.10.3Huffman編碼與Huffman編碼樹
5.10.4Huffman編碼樹的構(gòu)造算法
5.10.5基于優(yōu)先隊(duì)列的Huffman編碼樹構(gòu)造算法
第6章映射與詞典
6.1映射..
6.1.1映射的ADT描述
6.1.2映射的Java接口
6.1.3判等器
6.1.4java.util包中的映射類
6.1.5基于列表實(shí)現(xiàn)映射類
6.2散列表
6.2.1桶及桶數(shù)組
6.2.2散列函數(shù)
6.2.3散列碼
6.2.4壓縮函數(shù)
6.2.5沖突的普遍性
6.2.6解決沖突
6.2.?基于散列表實(shí)現(xiàn)映射類
6.2.8裝填因子與重散列
6.3無序詞典
6.3.1無序詞典的ADT描述
6.3.2無序詞典的Java接口
6.3.3列表式無序詞典及其實(shí)現(xiàn)
6.3.4散列表式無序詞典及其實(shí)現(xiàn)
6.4有序詞典
6.4.1全序關(guān)系與有序查找表
6.4.2二分查找
6.4.3有序詞典的ADT描述
6.4.4有序詞典的Java接口
6.4.5基于有序查找表實(shí)現(xiàn)有序
詞典
第7章查找樹
7.1二分查找樹
7.1.1定義
7.1.2查找算法
7.1.3完全查找算法
7.1.4插入算法
7.1.5刪除算法
7.1.6二分查找樹節(jié)點(diǎn)類的實(shí)現(xiàn)
7.1.?二分查找樹類的實(shí)現(xiàn)
7.1.8二分查找樹的平均性能
7.2AVL樹
7.2.1平衡二分查找樹
7.2.2等價(jià)二分查找樹
7.2.3等價(jià)變換
7.2.4AVL樹
7.2.5插入節(jié)點(diǎn)后的重平衡
7.2.6節(jié)點(diǎn)刪除后的重平衡
7.2.7AVL樹的Java實(shí)現(xiàn)
7.3伸展樹
7.3.1數(shù)據(jù)局部性
7.3.2逐層伸展
7.3.3雙層伸展
7.3.4分?jǐn)倧?fù)雜度
7.3.5伸展樹的Java實(shí)現(xiàn)
7.3.6插入
7.3.7刪除
7.4B-樹
7.4.1分級(jí)存儲(chǔ)
7.4.2B-樹的定義
7.4.3關(guān)鍵碼的查找
7.4.4性能分析
7.4.5上溢節(jié)點(diǎn)的處理
7.4.6關(guān)鍵碼的插入
7.4.7下溢節(jié)點(diǎn)的處理
7.4.8關(guān)鍵碼的刪除
第8章排序
8.1歸并排序
8.1.1分治策略
8.1.2時(shí)間復(fù)雜度
8.1.3歸并算法
8.1.4Mergesort的Java實(shí)現(xiàn)
8.2快速排序
8.2.1分治策略
8.2.2軸點(diǎn)
8.2.3劃分算法
8.2.4Quicksort的Java實(shí)現(xiàn)
8.2.5時(shí)間復(fù)雜度
8.3復(fù)雜度下界
8.3.1比較樹與基于比較的算法
8.3.2下界
第9章串
9.1串及其ADT描述
9.2串模式匹配
9.2.1概念與記號(hào)
9.2.2問題
9.2.3算法效率的測(cè)試與評(píng)價(jià)
9.3蠻力算法
9.3.1算法描述
9.3.2算法實(shí)現(xiàn)
9.3.3算法分析
9.4KMP算法
9.4.1蠻力算法的改進(jìn)
9.4.2next[]表的定義及含義
9.4.3KMP算法描述
9.4.4next[]表的特殊情況
9.4.5next[]表的構(gòu)造
9.4.6next[]表的改進(jìn)
9.4.7KMP算法的Java實(shí)現(xiàn)
9.4.8性能分析
9.5BM算法
9.5.1壞字符策略
9.5.2好后綴策略
9.5.3BM算法
9.5.4BM算法的Java實(shí)現(xiàn)
9.5.5性能
第10章圖
10.1概述
10.1.1無向圖.混合圖及有向圖
10.1.2度
10.1.3簡(jiǎn)單圖
10.1.4圖的復(fù)雜度
10.1.5子圖.生成子圖與限制子圖
10.1.6通路.環(huán)路及可達(dá)分量
10.1.7連通性.等價(jià)類與連通分量
10.1.日森林.樹以及無向圖的生成樹
10.1.9有向圖的生成樹
10.1.10帶權(quán)網(wǎng)絡(luò)
10.2抽象數(shù)據(jù)類型
10.2.1圖
10.2.2頂點(diǎn)
10.2.3邊
10.3鄰接矩陣
10.3.1表示方法
10.3.2時(shí)間性能
10.3.3空間性能
10.4鄰接表
10.4.1頂點(diǎn)表和邊表
10.4.2頂點(diǎn)與鄰接邊表
10.4.3邊
lo.4.4基于鄰接表實(shí)現(xiàn)圖結(jié)構(gòu)
10.5圖遍歷及其算法模板
10.6深度優(yōu)先遍歷
10.6.1深度優(yōu)先遍歷算法
10.6.2邊分類
10.6.3可達(dá)分量與DFS樹
10.6.4深度優(yōu)先遍歷算法模板
10.6.5可達(dá)分量算法
10.6.6單強(qiáng)連通分量算法
10.6.7強(qiáng)連通分量分解算法
10.6.8濃縮圖與弱連通性
10.7廣度優(yōu)先遍歷
10.7.1廣度優(yōu)先遍歷算法
10.7.2邊分類
10.7.3可達(dá)分量與BFS樹
10.7.4廣度優(yōu)先遍歷算法模板
10.7.5最短距離算法
10.8最佳優(yōu)先遍歷
10.8.1最佳優(yōu)先遍歷算法
10.8.2最佳優(yōu)先遍歷算法模板
10.8.3最短路徑
10.8.4最短路徑序列
10.8.5Dijkstra算法
10.8.6最小生成樹
10.8.7Prim-Jarnik算法
DSA類關(guān)系圖...