Data Structures and Algorithm Analysis in C, 2/e (Hardcover)
暫譯: C語言資料結構與演算法分析（第二版，精裝本）
Mark A. Weiss
- 出版商: Addison Wesley
- 出版日期: 1996-09-19
- 售價: $1,372
- 語言: 英文
- 頁數: 528
- 裝訂: Paperback
- ISBN: 0201498405
- ISBN-13: 9780201498400
-
相關分類:
Algorithms-data-structures
無法訂購
買這商品的人也買了...
-
$1,029Fundamentals of Data Structures in C++ -
Visual C++ 6 教學手冊 (Beginning Visual C++ 6)$580$458 -
計算機組織與設計--軟硬體界面第二版 (Computer Organization & Design, 2/e)$680$537 -
C++ Primer, 3/e 中文版$980$774 -
Beginning Perl for Bioinformatics (Paperback)$1,330$1,260 -
Digital Image Processing, 2/e(IE)(美國版ISBN:0201180758)$1,150$1,127 -
PhotoImpact 7 帶了就走－大玩影像特效$168$133 -
$1,274Computer Architecture: A Quantitative Approach, 3/e(精裝本) -
演算法導論 (Introduction to Algorithms, 2/e)$860$679 -
The CISSP Prep Guide: Gold Edition$1,600$1,568 -
Visual C#.NET 程式設計經典$650$514 -
鳥哥的 Linux 私房菜$560$476 -
JavaScript 範例活用辭典$450$351 -
Sun Certified Programmer & Developer for Java 2 Study Guide, 2/e$1,760$1,672 -
Java 完美經典優質學習篇$750$638 -
Red Hat Linux 9 實務應用$650$553 -
802.11 無線網路技術通論 (802.11 Wireless Networks: The Definitive Guide)$760$600 -
Dreamweaver MX 互動網站百寶箱 for ASP$580$493 -
ASP.NET 程式設計徹底研究$590$466 -
Borland 傳奇$280$221 -
深入 Linux 建構與管理, 4/e$720$612 -
STRUTS 實作手冊(Struts in Action: Building Web Applications with the Leading Java Framework)$690$538 -
鳥哥的 Linux 私房菜－伺服器架設篇$750$638 -
鳥哥的 Linux 私房菜─基礎學習篇增訂版$560$476 -
軟體工程 (Software Engineering: An Engineering Approach)$780$741
相關主題
商品描述
Description
Mark Allen Weiss' successful book provides a modern approach to algorithms and data structures using the C programming language. The book's conceptual presentation focuses on ADTs and the analysis of algorithms for efficiency, with a particular concentration on performance and running time. The second edition contains a new chapter that examines advanced data structures such as red black trees, top down splay trees, treaps, k-d trees, and pairing heaps among others. All code examples now conform to ANSI C and coverage of the formal proofs underpinning several key data structures has been strengthened.
Table Of Contents
(All chapters, except Chapter 3, conclude with a Summary, Exercises and References.)
1. Introduction.
Mathematics Review.
Exponents.
Logarithms.
Series.
Modular Arithmetic.
The P word.
A Brief Introduction to Recursion.
2. Algorithm Analysis.
Model.
What to Analyze.
Running Time Calculations.
A Simple Example.
General Rules.
Solutions for the Maximum Subsequence Sum Problem.
Logarithms in the Running Time.
Checking Your Analysis.
A Grain of Salt.
3. Lists, Stacks, and Queues.
The List ADT.
Simple Array Implementation of Lists.
Linked Lists.
Programming Details.
Common Errors.
Doubly Linked Lists.
Circularly Linked Lists.
Examples.
Cursor Implementation of Linked Lists.
The Stack ADT.
Stack Model.
Implementation of Stacks.
Applications.
The Queue ADT.
Queue Model.
Array Implementation of Queues.
Applications of Queues.
4. Trees.
Implementation of Trees.
Tree Traversals with an Application.
Binary Trees.
Implementation.
Expression Trees.
The Search Tree ADT—Binary Search Trees.
MakeEmpty.
Find.
FindMin and FindMax.
Insert.
Delete.
Average-Case Analysis.
AVL Trees.
Single Rotation.
Double Rotation.
Splay Trees.
A Simple Idea (That Does Not Work).
Splaying.
Tree Traversals (Revisited).
B-Trees.
5. Hashing.
Hash Function.
Separate Chaining.
Open Addressing.
Linear Probing.
Quadratic Probing.
Double Hashing.
Rehashing.
Extendible Hashing.
6. Priority Queues (Heaps).
Simple Implementations.
Binary Heaps.
Structure Property.
Heap Order Property.
Basic Heap Operations.
Other Heap Operations.
Applications of Priority Queues.
The Selection Problem.
Event Simulation.
d-Heaps.
Leftist Heaps.
Leftist Heap Property.
Leftist Heap Operations.
Skew Heaps.
Binomial Queues.
Binomial Queue Structure.
Binomial Queue Operations.
Implementations of Binomial Queues.
7. Sorting.
Insertion Sort.
The Algorithm.
Analysis of Insertion Sort.
A Lower Bound for Simple Sorting Algorithms.
Shellsort.
Analysis of Insertion Sort.
Heapsort.
Analysis of Heapsort.
Mergesort.
Analysis of Mergesort.
Quicksort.
Picking the Pivot.
Partitioning Strategy.
Small Arrays.
Actual Quicksort Routines.
Analysis of Quicksort.
A Linear-Expected-Time Algorithm for Selection.
Sorting Large Structures.
A General Lower Bound for Sorting.
Decision Trees.
Bucket Sort.
External Sorting.
Why We Need New Algorithms.
Model for External Sorting.
The Simple Algorithm.
Multiway Merge.
Polyphase Merge.
Replacement Selection.
8. The Disjoint Set ADT.
The Dynamic Equivalence Problem.
Basic Data Structure.
Smart Union Algorithms.
Path Compression.
Worst Case for Union-by-Rank and Path Compression.
Analysis of the Union/Find Algorithm.
An Application.
9. Graph Algorithms.
Representation of Graphs.
Topological Sort.
Shortest-Path Algorithms.
Unweighted Shortest Paths.
Dijkstra's Algorithm.
Graphs with Negative Edge Costs.
Acyclic Graphs.
All-Pairs Shortest Path.
Network Flow Problems.
A Simple Maximum-Flow Algorithm.
Minimum Spanning Tree.
Prim's Algorithm.
Kruskal's Algorithm.
Applications of Depth-First Search.
Undirected Graphs.
Biconnectivity.
Euler Circuits.
Directed Graphs.
Finding Strong Components.
Introduction to the NP-Completeness.
Easy vs. Hard.
The Class NP.
NP-Complete Problems.
10. Algorithm Design Techniques.
A Simple Scheduling Problem.
Huffman Codes.
Approximate Bin Packing.
Divide and Conquer.
Running Time of Divide and Conquer Algorithms.
Closest-Points Problem.
The Selection Problem.
Theoretical Improvements for Arithmetic Problems.
Dynamic Programming.
Using a Table Instead of Recursion.
Ordering Matrix Multiplications.
Optimal Binary Search Tree.
All-Pairs Shortest Path.
Randomized Algorithms.
Random Number Generators.
Skip Lists.
Primality Testing.
Backtracking Algorithms.
The Turnpike Reconstruction Problem.
Games.
11. Amortized Analysis.
Binomial Queues.
Skew Heaps.
Fibonacci Heaps.
Cutting Nodes in Leftist Heaps.
Lazy Merging for Binomial Queues.
The Fibonacci Heap Operations.
Proof of the Time Bound.
Splay Trees.
12. Advanced Data Structures and Implementation.
Red Black Trees.
Bottom-Up Insertion.
Top-Down Red Black Trees.
Top-Down Deletion.
Deterministic Skip Lists.
AA-Trees.
Treaps.
k-d Trees.
Pairing Heaps.
Index. 0201498405T04062001
商品描述(中文翻譯)
描述
Mark Allen Weiss 的成功著作提供了一種使用 C 程式語言的現代算法和數據結構方法。該書的概念性呈現專注於抽象數據類型（ADTs）及算法效率分析，特別關注性能和運行時間。第二版包含了一個新章節，探討了如紅黑樹、從上到下的擴展樹、Treaps、k-d 樹和配對堆等高級數據結構。所有代碼示例現在均符合 ANSI C，並加強了對幾個關鍵數據結構的正式證明的覆蓋。
目錄
（所有章節，除了第三章，均以摘要、練習和參考文獻結束。）
1. 介紹。
本書內容概述。
數學回顧。
指數。
對數。
級數。
模運算。
P 字。
遞歸簡介。
2. 算法分析。
數學背景。
模型。
需要分析的內容。
運行時間計算。
一個簡單的例子。
一般規則。
最大子序列和問題的解決方案。
運行時間中的對數。
檢查你的分析。
一絲懷疑。
3. 列表、堆疊和佇列。
抽象數據類型（ADTs）。
列表 ADT。
列表的簡單數組實現。
鏈接列表。
程式設計細節。
常見錯誤。
雙向鏈接列表。
循環鏈接列表。
示例。
鏈接列表的游標實現。
堆疊 ADT。
堆疊模型。
堆疊的實現。
應用。
佇列 ADT。
佇列模型。
佇列的數組實現。
佇列的應用。
4. 樹。
前提。
樹的實現。
樹的遍歷及其應用。
二叉樹。
實現。
表達式樹。
搜索樹 ADT—二叉搜索樹。
MakeEmpty。
Find。
FindMin 和 FindMax。
Insert。
Delete。
平均情況分析。
AVL 樹。
單旋轉。
雙旋轉。
擴展樹。
一個簡單的想法（但不奏效）。
擴展。
樹的遍歷（重訪）。
B 樹。
5. 雜湊。
一般概念。
雜湊函數。
獨立鏈接。
開放定址。
線性探測。
二次探測。
雙重雜湊。
重新雜湊。
可擴展雜湊。
6. 優先佇列（堆）。
模型。
簡單實現。
二叉堆。
結構性質。
堆序性質。
基本堆操作。
其他堆操作。
優先佇列的應用。
選擇問題。
事件模擬。
d-堆。
左式堆。
左式堆性質。
左式堆操作。
偏斜堆。
二項佇列。
二項佇列結構。
二項佇列操作。
二項佇列的實現。
7. 排序。
前提。
插入排序。
算法。
插入排序的分析。
簡單排序算法的下界。
Shellsort。
插入排序的分析。
堆排序。
堆排序的分析。
合併排序。
合併排序的分析。
快速排序。
選擇樞紐。
分區策略。
小數組。
實際的快速排序例程。
快速排序的分析。
一個線性期望時間的選擇算法。
排序大型結構。
排序的一般下界。
決策樹。
桶排序。
外部排序。
為什麼我們需要新算法。
外部排序模型。
簡單算法。
多路合併。
多相合併。
替換選擇。
8. 不相交集 ADT。
等價關係。
動態等價問題。
基本數據結構。
智能聯合算法。
路徑壓縮。
基於排名的聯合和路徑壓縮的最壞情況。
聯合/查找算法的分析。
一個應用。
9. 圖算法。
定義。
圖的表示。
拓撲排序。
最短路徑算法。
無權重最短路徑。
Dijkstra 算法。
具有負邊成本的圖。
無環圖。
所有對最短路徑。
網絡流問題。
一個簡單的最大流算法。
最小生成樹。
Prim 算法。
Kruskal 算法。
深度優先搜索的應用。
無向圖。
二連通性。
歐拉回路。
有向圖。
尋找強連通分量。
NP 完全性簡介。
簡單與困難。
NP 類。
NP 完全問題。
10. 算法設計技術。
貪婪算法。
一個簡單的排程問題。
Huffman 編碼。
近似二進位打包。
分治法。
分治算法的運行時間。
最近點問題。
選擇問題。
算術問題的理論改進。
動態規劃。
使用表格而非遞歸。
矩陣乘法的排序。
最佳二叉搜索樹。
所有對最短路徑。
隨機算法。
隨機數生成器。
跳躍列表。
質數測試。
回溯算法。
收費公路重建問題。
遊戲。
11. 平均分析。
一個無關的謎題。
二項佇列。
偏斜堆。
費波那契堆。
在左式堆中切割節點。
二項佇列的懶合併。
費波那契堆操作。
時間界限的證明。
擴展樹。
12. 高級數據結構與實現。
自上而下的擴展樹。
紅黑樹。
自下而上的插入。
自上而下的紅黑樹。
自上而下的刪除。
確定性跳躍列表。
AA 樹。
Treaps。
k-d 樹。
配對堆。
索引. 0201498405T04062001
