數據結構與算法分析:C語言描述(原書第2版)典藏版
作 者: [美]馬克·艾倫·維斯(MarkAllenWeiss) 著 馮舜璽 譯 譯
定 價: 79
出?版?社: 機械工業出版社
出版日期: 2019年04月01日
頁 數: 412
裝 幀: 平裝
ISBN: 9787111621959
●出版者的話譯者序前言章 引論┊11.1 本書討論的內容┊21.2 數學知識復習┊31.2.1 指數┊31.2.2 對數┊31.2.3 級數┊41.2.4 模運算┊51.2.5 證明方法┊51.3 遞歸簡論┊7總結┊10練習┊10參考文獻┊11第2章 算法分析┊132.1 數學基礎┊142.2 模型┊162.3 要分析的問題┊162.4 運行時間計算┊182.4.1 一個簡單的例子┊182.4.2 一般法則┊192.4.3 優選子序列和┊202.4.4 運行時間中的對數┊242.4.5 檢驗你的分析┊272.4.6 分析結果的準確性┊28總結┊28練習┊29參考文獻┊32第3章 表、棧和隊列┊353.1 抽像數據類型┊363.2 表ADT┊363.2.1 表的簡單數組實現┊373.2.2 鏈表┊373.2.3 程序設計細節┊383.2.4 常見的錯誤┊423.2.5 雙鏈表┊433.2.6 循環鏈表┊433.2.7 例子┊433.2.8 鏈表的遊標實現┊473.3 棧ADT┊503.3.1 棧模型┊503.3.2 棧的實現┊513.3.3 應用┊563.4 隊列ADT┊623.4.1 隊列模型┊623.4.2 隊列的數組實現┊623.4.3 隊列的應用┊65總結┊66練習┊66第4章 樹┊714.1 預備知識┊724.1.1 樹的實現┊734.1.2 樹的遍歷及應用┊744.2 二叉樹┊764.2.1 實現┊774.2.2 表達式樹┊774.3 查找樹ADT——二叉查找樹┊804.3.1 MakeEmpty┊804.3.2 Find┊814.3.3 FindMin和FindMax┊814.3.4 Insert┊814.3.5 Delete┊834.3.6 平均情形分析┊844.4 AVL樹┊864.4.1 單旋轉┊884.4.2 雙旋轉┊904.5 伸展樹┊954.5.1 一個簡單的想法┊964.5.2 展開┊974.6 樹的遍歷┊1024.7 B樹┊103總結┊107練習┊108參考文獻┊113第5章 散列┊1175.1 一般想法┊1185.2 散列函數┊1185.3 分離鏈接法┊1205.4 開放定址法┊1235.4.1 線性探測法┊1245.4.2 平方探測法┊1255.4.3 雙散列┊1295.5 再散列┊1305.6 可擴散列┊132總結┊133練習┊134參考文獻┊137第6章 優先隊列(堆)┊1396.1 模型┊1406.2 一些簡單的實現┊1416.3 二叉堆┊1416.3.1 結構性質┊1416.3.2 堆序性質┊1426.3.3 基本的堆操作┊1436.3.4 其他的堆操作┊1466.4 優先隊列的應用┊1496.4.1 選擇問題┊1496.4.2 事件模擬┊1506.5 d-堆┊1516.6 左式堆┊1526.6.1 左式堆的性質┊1526.6.2 左式堆的操作┊1536.7 斜堆┊1586.8 二項隊列┊1596.8.1 二項隊列結構┊1596.8.2 二項隊列操作┊1606.8.3 二項隊列的實現┊162總結┊165練習┊166參考文獻┊169第7章 排序┊1737.1 預備知識┊1747.2 插入排序┊1747.2.1 算法┊1747.2.2 插入排序的分析┊1757.3 一些簡單排序算法的下界┊1757.4 希爾排序┊1767.5 堆排序┊1797.6 歸並排序┊1827.7 快速排序┊1867.7.1 選┊1877.7.2 分割策略┊1887.7.3 小數組┊1907.7.4 實際的快速排序例程┊1907.7.5 快速排序的分析┊1927.7.6 選擇的線性期望時間算法┊1947.8 大型結構的排序┊1957.9 排序的一般下界┊1967.10 桶式排序┊1987.11 外部排序┊1987.11.1 為什麼需要新的算法┊1987.11.2 外部排序模型┊1997.11.3 簡單算法┊1997.11.4 多路合並┊2007.11.5 多相合並┊2017.11.6 替換選擇┊202總結┊203練習┊204參考文獻┊207第8章 不相交集ADT┊2098.1 等價關繫┊2108.2 動態等價性問題┊2108.3 基本數據結構┊2128.4 靈巧求並算法┊2148.5 路徑壓縮┊2168.6 按秩求並和路徑壓縮的最壞情形┊2178.7 一個應用┊221總結┊222練習┊222參考文獻┊223第9章 圖論算法┊2259.1 若干定義┊2269.2 拓撲排序┊2289.3 最短路徑算法┊2309.3.1 無權最短路徑┊2329.3.2 Dijkstra算法┊2359.3.3 具有負邊值的圖┊2409.3.4 無圈圖┊2419.3.5 所有點對最短路徑┊2439.4 網絡流問題┊2439.5 最小生成樹┊2479.5.1 Prim算法┊2489.5.2 Kruskal算法┊2509.6 深度優先搜索的應用┊2519.6.1 無向圖┊2529.6.2 雙連通性┊2539.6.3 歐拉回路┊2569.6.4 有向圖┊2599.6.5 查找強分支┊2609.7 NP-完全性介紹┊2629.7.1 難與易┊2629.7.2 NP類┊2639.7.3 NP-完全問題┊264總結┊266練習┊266參考文獻┊2700章 算法設計技巧┊27310.1 貪婪算法┊27410.1.1 一個簡單的調度問題┊27410.1.2 Huffman編碼┊27610.1.3 近似裝箱問題┊28010.2 分治算法┊28610.2.1 分治算法的運行時間┊28710.2.2 最近點問題┊28910.2.3 選擇問題┊29110.2.4 一些運算問題的理論改進┊29410.3 動態規劃┊29710.3.1 用一個表代替遞歸┊29810.3.2 矩陣乘法的順序安排┊30010.3.3 最優二叉查找樹┊30110.3.4 所有點對最短路徑┊30410.4 隨機化算法┊30610.4.1 隨機數發生器┊30710.4.2 跳躍表┊31010.4.3 素性測試┊31210.5 回溯算法┊31410.5.1 收費公路重建問題┊31410.5.2 博弈┊318總結┊323練習┊323參考文獻┊3291章 攤還分析┊33311.1 一個無關的智力問題┊33411.2 二項隊列┊33511.3 斜堆┊33911.4 斐波那契堆┊34111.4.1 切除左式堆中的節點┊34111.4.2 二項隊列的懶惰合並┊34311.4.3 斐波那契堆操作┊34611.4.4 時間界的證明┊34611.5 伸展樹┊348總結┊351練習┊351參考文獻┊3532章 不錯數據結構及其實現┊35512.1 自頂向下伸展樹┊35612.2 紅黑樹┊36112.2.1 自底向上插入┊36212.2.2 自頂向下紅黑樹┊36312.2.3 自頂向下刪除┊36712.3 確定性跳躍表┊36812.4 AA樹┊37312.5 treap樹┊37812.6 k-d樹┊37912.7 配對堆┊383總結┊387練習┊387參考文獻┊389索引┊391
內容簡介
本書是國外數據結構與算法分析方面的標準教材,介紹了數據結構(大量數據的組織方法)以及算法分析(算法運行時間的估算)。本書的編寫目標是同時講授好的程序設計和算法分析技巧,使讀者可以開發出具有*高效率的程序。本書可作為不錯數據結構課程或研究生一年級算法分析課程的教材,使用本書需具有一些中級程序設計知識,還需要離散數學的一些背景知識。
[美]馬克·艾倫·維斯(MarkAllenWeiss) 著 馮舜璽 譯 譯
【加照片】馬克·艾倫·維斯(Mark Allen Weiss)佛羅裡達靠前大學計算與信息科學學院教授、副院長,本科教育主任和研究生教育主任。他於1987年獲得普林斯頓大學計算機科學博士學位,師從Robert Sedgewick。 他曾經擔任全美AP(Advanced Placement)考試計算機學科委員會的主席(2000-2004)。他的主要研究興趣是數據結構、算法和教育學。他編寫的關於數據結構與算法方面的知名教材還有《Data Structures and Algorithm Analysis : in Java》《Data Structures and Algorithm Analysi......
目的本書討論數據結構和算法分析。數據結構主要研究組織大量數據的方法,而算法分析則是對算法運行時間的評估。隨著計算機的速度越來越快,對於能夠處理大量輸入數據的程序的需求變得日益急切。可是,由於在輸入量很大的時候程序的低效率現像變得非常明顯,因此這又要求對效率問題給予更仔細的關注。通過在實際編程前對算法進行分析,學生可以決定一個特定的解法是否可行。例如,學生在本書中將讀到一些特定的問題並看到精心的實現方法是如何把處理大量數據的時間限制從16年減至不到1秒的。因此,若無運行時間的闡釋,就不會有算法和數據結構的提出。在某些情況下,對於影響算法實現的運行時間的一些微小細節都需要認真探究。一旦確定解法,還必須編寫程序。隨著計算機的日益強大,它們必須解決的問題也變得更加巨大和復雜,這就要求開發更加復雜的程序。本書的目的是教授學生良好的程序設計技巧和提高學生的算法分析能力,使得他們能夠開發出具有最高效率的......
"