數(shù)據(jù)結構與算法

定　價：￥33.00

作　者：	鄧俊輝編著
出版社：	機械工業(yè)出版社
叢編項：	重點大學計算機教材
標　簽：	數(shù)據(jù)結構

購買這本書可以去

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

內容簡介

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

作者簡介

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

圖書目錄

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