《數據結構與算法分析：C語言描述》是2004年1月1日機械工業出版社出版的圖書，作者是Mark Allen Weiss (維斯) 。
基本介紹
- 書名：數據結構與算法分析：C語言描述
- 作者：Mark Allen Weiss (維斯)
- 譯者：馮舜璽
- ISBN： 9787111127482
- 頁數：391
- 定價：35
- 出版社： 機械工業出版社
- 出版時間：2004年1月1日
- 裝幀：平裝
內容簡介,本書特點,作者簡介,目錄,書評,
內容簡介
《數據結構與算法分析:C語言描述(原書第2版)》內容簡介：書中詳細介紹了當前流行的論題和新的變化，討論了算法設計技巧，並在研究算法的性能、效率以及對運行時間分析的基礎上考查了一些高級數據結構，從歷史的角度和近年的進展對數據結構的活躍領域進行了簡要的概括。由於《數據結構與算法分析:C語言描述(原書第2版)》選材新穎，方法實用，題例豐富，取捨得當。《數據結構與算法分析:C語言描述(原書第2版)》的目的是培養學生良好的程式設計技巧和熟練的算法分析能力，使得他們能夠開發出高效率的程式。從服務於實踐又鍛鍊學生實際能力出發，書中提供了大部算法的C程式和偽碼例程，但並不是全部。一些程式可從網際網路上獲得。
《數據結構與算法分析:C語言描述(原書第2版)》是《Data Structures and Algorithm Analysis in C》一書第2版的簡體中譯本。原書曾被評為20世紀頂尖的30部計算機著作之一，作者Mark Allen Weiss在數據結構和算法分析方面卓有建樹，他的數據結構和算法分析的著作尤其暢銷，並受到廣泛好評．已被世界500餘所大學用作教材。
在《數據結構與算法分析:C語言描述(原書第2版)》中，作者更加精煉並強化了他對算法和數據結構方面創新的處理方法。通過C程式的實現，著重闡述了抽象數據類型的概念，並對算法的效率、性能和運行時間進行了分析。
本書特點
●專用一章來討論算法設計技巧，包括貪婪算法、分治算法、動態規劃、隨機化算法以及回溯算法
●介紹了當前流行的論題和新的數據結構，如斐波那契堆、斜堆、二項佇列、跳躍表和伸展樹
●安排一章專門討論攤還分析，考查書中介紹的一些高級數據結構
●新開闢一章討論高級數據結構以及它們的實現，其中包括紅黑樹、自頂向下伸展樹。treap樹、k-d樹、配對堆以及其他相關內容
●合併了堆排序平均情況分析的一些新結果
《數據結構與算法分析:C語言描述(原書第2版)》是國外數據結構與算法分析方面的標準教材，介紹了數據結構(大量數據的組織方法)以及算法分析(算法運行時間的估算)。《數據結構與算法分析:C語言描述(原書第2版)》的編寫目標是同時講授好的程式設計和算法分析技巧，使讀者可以開發出具有最高效率的程式。 《數據結構與算法分析:C語言描述(原書第2版)》可作為高級數據結構課程或研究生一年級算法分析課程的教材，使用《數據結構與算法分析:C語言描述(原書第2版)》需具有一些中級程式設計知識，還需要離散數學的一些背景知識。
作者簡介
作者：(美國)維斯 譯者：馮舜璽
Mark Allen Weiss是佛羅里達國際大學計算機學院教授，普林斯頓大學計算機科學博士。除本書外，他編寫的關於數據結構與算法方面的知名教材還有：Data Structures and Algorithm Analysis：in Java, Data Structures and Algonthm Analysis：in C++以及Data Structures and Problem Solving：Using Jave、Data Struchures and Problem Solving：Using C++等。他目前是AP考試計算機學科委員會的主席。現任美國佛羅里達國際大學計算與信息科學學院教授。他曾經擔任全美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 配對堆
總結
練習
參考文獻
索引
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 配對堆
總結
練習
參考文獻
索引
書評
現在的程式設計師總是用著別人封裝好的函式、類、庫、API，滿滿的，我們就會覺得編程不過是這么回事，搭積木而已，別人都把材料提供好了，至於材料是怎么做的，不用理會。
真的是這樣嗎？說數據結構和算法沒用的人，那是因為他用不到。為什麼用不到？他的層次決定了他不會接觸到編程最關鍵最核心的部分——算法。
先不說那些反應算法的力量的似乎變態的問題，也不說2006年第4期《程式設計師》的專題，只說，當我們遇到一個問題時，如何搭建數學模型？當我們在有限的硬體條件下要完成高速的數據處理，如何設計？當我們為客戶開發完一套軟體後，能不能保證未來幾年內數據猛增不會帶來計算量的指數級增長？當我們需要升級伺服器記憶體和硬碟是，能不能修改幾個函式就避免硬體的投資？
這些問題的答案，請在這本書中尋找。
表、棧、佇列、樹、圖等基本數據結構作者並未花大力氣描述，而是重在後面的對這些數據結構的套用上，每一個結論都給出了詳盡的數學證明，閱讀過程中，我們可以感受到蘊含在其中的匠心獨運的邏輯思維之美。借用GOOGLE黑板報的一個專題，算法體現了——“數學之美”。
並不是說本書就很完美了，有些章節講得太過籠統，讀起來跳躍感太強，比如第九章的網路流問題，介紹的太過簡單，推導過程中省略了不少步驟，對增廣路徑算法講的太粗，至於預流推進算法（Push-Relabel）則根本未提，不能不說是一個小小缺憾。
真的是這樣嗎？說數據結構和算法沒用的人，那是因為他用不到。為什麼用不到？他的層次決定了他不會接觸到編程最關鍵最核心的部分——算法。
先不說那些反應算法的力量的似乎變態的問題，也不說2006年第4期《程式設計師》的專題，只說，當我們遇到一個問題時，如何搭建數學模型？當我們在有限的硬體條件下要完成高速的數據處理，如何設計？當我們為客戶開發完一套軟體後，能不能保證未來幾年內數據猛增不會帶來計算量的指數級增長？當我們需要升級伺服器記憶體和硬碟是，能不能修改幾個函式就避免硬體的投資？
這些問題的答案，請在這本書中尋找。
表、棧、佇列、樹、圖等基本數據結構作者並未花大力氣描述，而是重在後面的對這些數據結構的套用上，每一個結論都給出了詳盡的數學證明，閱讀過程中，我們可以感受到蘊含在其中的匠心獨運的邏輯思維之美。借用GOOGLE黑板報的一個專題，算法體現了——“數學之美”。
並不是說本書就很完美了，有些章節講得太過籠統，讀起來跳躍感太強，比如第九章的網路流問題，介紹的太過簡單，推導過程中省略了不少步驟，對增廣路徑算法講的太粗，至於預流推進算法（Push-Relabel）則根本未提，不能不說是一個小小缺憾。
