Mark Allen Weiss,1987年在普林斯頓大學獲得計算機科學博士學位,師從Robert Sedgewick (師從Knuth),現任美國佛羅裏達國際大學計算與信息科學學院教授。他曾經擔任全美AP(Advanced Placement)考試計算機學科委員會的主席(2000-2004)。他的主要研究方嚮是數據結構、算法和教育學。
第1章 引論
1.1 本書討論的內容
1.2 數學知識復習
1.2.1 指數
1.2.2 對數
1.2.3 級數
1.2.4 模運算
1. 2.5 證明方法
1.3 遞歸簡論
總結
練習
參考文獻
第2章 算法分析
2.1 數學基礎
2.2 模型
2.3 要分析的問題
2.4 運行時間計算
2.4.1 一個簡單的例子
2.4.2 一般法則
2.4.3 最大子序列和問題的解
.2.4.4 運行時間中的對數
2.4.5 檢驗你的分析
2.4.6 分析結果的準確性
總結
練習
參考文獻
第3章 錶、棧和隊列
3.1 抽象數據類型(adt)
3.2 錶adt
3.2.1 錶的簡單數組實現
3.2.2 鏈錶
3.2.3 程序設計細節
3.2.4 常見的錯誤
3.2.5 雙鏈錶
3.2.6 循環鏈錶
3.2.7 例子
3.2.8 鏈錶的遊標實現
3.3 棧adt
3.3.1 棧模型
3.3.2 棧的實現
3.3.3 應用
3.4 隊列adt
3.4.1 隊列模型
3.4.2 隊列的數組實現
3.4.3 隊列的應用
總結
練習
第4章 樹
4.1 預備知識
4.1.1 樹的實現
4.1.2 樹的遍曆及應用
4.2 二叉樹
4.2.1 實現
4.2.2 錶達式樹
4.3 查找樹adt--二叉查找樹
4.3.1 makeempty
4.3.2 find
4.3.3 findmin和findmax
4.3.4 insert
4.3.5 delere
4.3.6 平均情形分析
4.4 avl樹
4.4.1 單鏇轉
4.4.2 雙鏇轉
4.5 伸展樹
4.5.1 一個簡單的想法
4.5.2 展開
4.6 樹的遍曆
4.7 b-樹
總結
練習
參考文獻
第5章 散列
5.1 一般想法
5.2 散列函數
5.3 分離鏈接法
5.4 開放定址法
5.4.1 綫性探測法
5.4.2 平方探測法
5.4.3 雙散列
5.5 再散列
5.6 可擴散列
總結
練習
參考文獻
第6章 優先隊列(堆)
6.1 模型
6.2 一些簡單的實現
6.3 二叉堆
6.3.1 結構性質
6.3.2 堆序性質
6.3.3 基本的堆操作
6.3.4 其他的堆操作
6.4 優先隊列的應用
6.4.1 選擇問題
6.4.2 事件模擬
6.5 d-堆
6.6 左式堆
6.6.1 左式堆的性質
6.6.2 左式堆的操作
6.7 斜堆
6.8 二項隊列
6.8.1 二項隊列結構
6.8.2 二項隊列操作
6.8.3 二項隊列的實現
總結
練習
參考文獻
第7章 排序
7.1 預備知識
7.2 插入排序
7.2.1 算法
7.2.2 插入排序的分析
7.3 一些簡單排序算法的下界
7. 4 希爾排序
7.4.1 希爾排序的最壞情形分析
7.5 堆排序
7.5.1 堆排序的分析
7.6 歸並排序
7.6.1 歸並排序的分析
7.7 快速排序
7.7.1 選取樞紐元
7.7.2 分割策略
7.7.3 小數組
7.7.4 實際的快速排序例程
7.7.5 快速排序的分析
7.7.6 選擇的綫性期望時間算法
7.8 大型結構的排序
7.9 排序的一般下界
7.9.1 決策樹
7.10 桶式排序
7.11 外部排序
7.11.1 為什麼需要新的算法
7.11.2 外部排序模型
7.11.3 簡單算法
7.11.4 多路閤並
7.11.5 多相閤並
7.11.6 替換選擇
總結
練習
參考文獻
第8章 不相交集adt
8.1 等價關係
8.2 動態等價性問題
8.3 基本數據結構
8.4 靈巧求並算法
8.5 路徑壓縮
8.6 按秩求並和路徑壓縮的最壞情形
8.6.1 union/find算法分析
8.7 一個應用
總結
練習
參考文獻
第9章 圖論算法
9.1 若乾定義
9.1.1 圖的錶示
9.2 拓撲排序
9.3 最短路徑算法
9.3.1 無權最短路徑
9.3.2 dijkstra算法
9.3.3 具有負邊值的圖
9.3.4 無圈圖
9.3.5 所有點對最短路徑
9.4 網絡流問題
9.4.1 一個簡單的最大流算法
9.5 最小生成樹
9.5.1 prim算法
9.5.2 kruskal算法
9.6 深度優先搜索的應用
9.6.1 無嚮圖
9.6.2 雙連通性
9.6.3 歐拉迴路
9.6.4 有嚮圖
9.6.5 查找強分支
9.7 np-完全性介紹
9.7.1 難與易
9.7.2 np類
9.7.3 np-完全問題
總結
練習
參考文獻
第10章 算法設計技巧
10.1 貪婪算法
10.1.1 一個簡單的調度問題
10.1.2 huffman編碼
10.1.3 近似裝箱問題
10.2 分治算法
10.2.1 分治算法的運行時間
10.2.2 最近點問題
10.2.3 選擇問題
10.2.4 一些運算問題的理論改進
10.3 動態規劃
10.3.1 用一個錶代替遞歸
10.3.2 矩陣乘法的順序安排
10.3.3 最優二叉查找樹
10.3.4 所有點對最短路徑
10.4 隨機化算法
10.4.1 隨機數發生器
10.4.2 跳躍錶
10.4.3 素性測試
10.5 迴溯算法
10.5.1 收費公路重建問題
10.5.2 博弈
總結
練習
參考文獻
第11章 攤還分析
11.1 一個無關的智力問題
11.2 二項隊列
11.3 斜堆
11.4 斐波那契堆
11.4.1 切除左式堆中的節點
11.4.2 二項隊列的懶惰閤並
11.4.3 斐波那契堆操作
11.4.4 時間界的證明
11. 5 伸展樹
總結
練習
參考文獻
第12章 高級數據結構及其實現
12.1 自頂嚮下伸展樹
12.2 紅黑樹
12.2.1 自底嚮上插入
12.2.2 自頂嚮下紅黑樹
12.2.3 自頂嚮下刪除
12.3 確定性跳躍錶
12.4 aa-樹
12.5 treap樹
12.6 k-d樹
12.7 配對堆
總結
練習
參考文獻
索引
· · · · · · (
收起)
本書是《Data Structures and Algorithm Analysis in C》一書第2版的簡體中譯本。原書曾被評為20世紀頂尖的30部計算機著作之一,作者Mark Allen Weiss在數據結構和算法分析方麵卓有建樹,他的數據結構和算法分析的著作尤其暢銷,並受到廣泛好評.已被世界500餘所大學用作教材。
在本書中,作者更加精煉並強化瞭他對算法和數據結構方麵創新的處理方法。通過C程序的實現,著重闡述瞭抽象數據類型的概念,並對算法的效率、性能和運行時間進行瞭分析。
全書特點如下:
●專用一章來討論算法設計技巧,包括貪婪算法、分治算法、動態規劃、隨機化算法以及迴溯算法
●介紹瞭當前流行的論題和新的數據結構,如斐波那契堆、斜堆、二項隊列、跳躍錶和伸展樹
●安排一章專門討論攤還分析,考查書中介紹的一些高級數據結構
●新開闢一章討論高級數據結構以及它們的實現,其中包括紅黑樹、自頂嚮下伸展樹。treap樹、k-d樹、配對堆以及其他相關內容
●閤並瞭堆排序平均情況分析的一些新結果
本書是國外數據結構與算法分析方麵的標準教材,介紹瞭數據結構(大量數據的組織方法)以及算法分析(算法運行時間的估算)。本書的編寫目標是同時講授好的程序設計和算法分析技巧,使讀者可以開發齣具有最高效率的程序。 本書可作為高級數據結構課程或研究生一年級算法分析課程的教材,使用本書需具有一些中級程序設計知識,還需要離散數學的一些背景知識。
數據結構與算法分析 下載 mobi epub pdf txt 電子書 格式
評分
☆☆☆☆☆
##這本書真是非常好!個人感覺很適閤給初學者入門看,裏麵的分析數學公式恰到好處,沒有算法導論的令人望而生畏,也沒有國內圖書的草草瞭事,既學習瞭數據結構又有剛剛好的算法分析,很容易使人産生共鳴。 給我印象深刻的就是快速排序那一段,真是精彩!
評分
☆☆☆☆☆
評分
☆☆☆☆☆
評分
☆☆☆☆☆
評分
☆☆☆☆☆
##為什麼要讀數據結構?
因為隻瞭解一門語言的語法是遠遠不夠的,一個正規的程序員必然會遇到數據結構和算法問題(而不是設計一個新算法);麵試時對數據結構的測試可以一定程度反映一個人的編程水平。
如何評價這本書?
不是很適閤零基礎閱讀,既不能高效應付考試,也不能快速消化在實際中應用。如果當年麵試看的是金典的話,同樣的時間成績可能會好很多。
讀瞭前7章,應該夠應付筆試瞭,接下來刷題
能救你的隻有自己
PS:翻譯實在是太爛瞭,完全抵消掉瞭其作為外文書的優勢
1、在我有限的代碼生涯中,確實從來沒有遇到過數據結構的問題
2、但是,在筆試中,確實是重點考察的對象,甚至高於數據庫和語言基礎
3、所以,為瞭筆試,看吧……
評分
☆☆☆☆☆
評分
☆☆☆☆☆
##這本書買瞭很多年,搬瞭這麼多次工位,一直在辦公室常備的書(雖然已經很少翻看). 裏麵使用的代碼,不是所謂的僞代碼,而是正經可以運行的C代碼,所以新人如果能照著做一遍下來,收獲應該不小. 我的一個朋友,很多年前也是讀這本書寫瞭一些筆記: http://www.luocong.com/dsaanotes/ ...
評分
☆☆☆☆☆
##簡單易讀懂的一本算法和數據結構書。如果你隻想讀一本算法書,那就讀這本。
評分
☆☆☆☆☆
##感覺大部分寫書評或者推薦本書的人可能都沒有看完這本書的原著,寫的可能有失偏頗。 我因為這本書的中文翻譯實在是難以閱讀,找來瞭原著來讀。經過一段時間的努力,至少可以說看完這本書的大概內容,也算有資格能評價這本書瞭。 這本書的好處在於數據結構知識不僅全麵而且深入...