Algorithms in C++ (Hardcover)
暫譯: C++ 演算法 (精裝版)

Robert Sedgewick

Algorithms in C++ (Hardcover)

買這商品的人也買了...

相關主題

商品描述


Description

This version of Sedgewick's bestselling book provides a comprehensive collection of algorithms implemented in C++. The algorithms included cover a broad range of fundamental and more advanced methods: sorting, searching, string processing, geometric, graph, and mathematical algorithms. Readers will discover-in an object-oriented programming environment-how key algorithms can be implemented, run, debugged, and used in real applications.

FUNDAMENTALS.

1. Introduction.
Algorithms.
Outline of Topics.

2. C++ (AND C) Example: Euclid's Algorithm.
Types of Data.
Input/Output.
Concluding Remarks

3. Elementary Data Structures.
Arrays.
Linked Lists.
Storage Allocation.
Pushdown Stacks.
Queues.
Abstract and Concrete Data Types.

4. Trees.
Glossary.
Properties.
Representing Binary Trees.
Representing Forests.
Traversing Trees.

5. Recursion.
Recurrences.
Divide-and-Conquer.
Recursive Tree Traversal.
Removing Recursion.
Perspective.

6. Analysis of Algorithms.
Selecting an Algorithm.
Empirical Analysis.
Program
Optimization.
Algorithms and Systems

SORTING ALGORITHMS.

7. Elementary Sorting Methods.
Rules of the Game.
Selection Sort.
Insertion Sort.
Digression: Bubble Sort.
Performance Characteristics of Elementary Sorts.
Sorting Files with Large Records.
Shellsort.
Distribution Counting.

8. Quicksort.
The Basic Algorithm.
Performance Characteristics of Quicksort.
Removing Recursion.
Small Subfiles.
Median-of-Three Partitioning.
Selection.

9. Radix Sorting.
Bits.
Radix Exchange Sort.
Straight Radix Sort.
Performance Characteristics of Radix Sorts.
A Linear Sort.

10. Priority Queues.
Elementary Implementations.
Heap Data Structure.
Algorithms on Heaps.
Heapsort.
Indirect Heaps.
Advanced Implementations

11. Mergesort.
Merging.
Mergesort.
Lit Mergesort.
Bottom-Up Mergesort.
Performance Characteristics.
Optimized Implementations.
Recursion Revisited.

12. External Sorting.
Sort-Merge.
Balanced Multiway Merging.
Replacement
Selection.
Practical Considerations.
Polyphase Merging.
An Easier Way

SEARCHING ALGORITHMS.

13. Elementary Searching Methods.
Sequential Searching Methods.
Binary Search.
Binary Tree Search.
Deletion.
Indirect Binary Search Trees.

14. Balanced Trees.
Top-Down 2-3-4 Trees.
Red-Black Trees.
Other Algorithms.

15. Hashing.
Hash Functions.
Separate Chaining.
Linear Probing.
Double Hashing.
Perspective

16. Radix Searching.
Digital Search Trees.
Radix Search Tries.
Multiway Radix Searching.
Patricia.

17. External Searching.
Indexed Sequential Access.
B-Trees.
Extendible Hashing.
Virtual Memory.

STRING PROCESSING.

18. String Searching.
A Short History.
Brute-Force Algorithm.
Knuth-Morris-Pratt Algorithm.
Boyer-Moore Algorithm.
Rabin-Karp Algorithm.
Multiple Searches.

19. Pattern Matching.
Describing Patterns.
Pattern Matching Machines.
Representing the Machine.
Simulating the Machine.

20. Parsing.
Context-Free Grammars.
Top-Down Parsing.
Bottom-Up Parsing.
Compilers.
Compiler-Compilers.

21. File Compression.
Run-Length Encoding.
Variable-Length Encoding.
Building the Huffman Code.
Implementation.

22. Cryptology.
Rules of the Game.
Simple Methods.
Encryption/Decryption Machines.
Public-Key Cryptosystems.

GEOMETRIC ALGORITHMS.

23. Elementary Geometric Methods.
Points, Lines, and Polygons.
Line Segment Intersection.
Simple Closed Path.
Inclusion in a Polygon.
Perspective.

24. Finding the Convex Hull.
Rules of the Game.
Package-Wrapping.
The Graham Scan.
Interior Elimination.
Performance Issues.

25. Range Searching.
Elementary Methods.
Grid Method.
Two-Dimensional Trees.
Multidimensional Range Searching.

26. Geometric Intersection.
Horizontal and Vertical Lines.
Implementation.
General Line Intersection.

27. Closest-Point Problems.
Closest-Pair Problem.
Voronoi Diagrams.

GRAPH ALGORITHMS.

28. Elementary Graph Algorithms.
Glossary.
Representation.
Depth-First Search.
Nonrecursive Depth-First Search.
Breadth-First Search.
Mazes.
Perspective.

29. Connectivity.
Connected Components.
Biconnectivity.
Union-Find Connectivity.

30. Weighted Graphs.
Minimum Spanning Tree.
Priority-First Search.
Kruskal's Method.
Shortest Path.
Minimum Spanning Tree and Shortest Paths in Dense Graphs.
Geometric Problems.

31. Directed Graphs.
Depth-First Search.
Transitive Closure.
All Shortest Paths.
Topological Sorting.
Strongly Connected Components.

32. Network Flow.
The Network Flow Problem.
Ford-Fulkerson Method.
Network Searching.

33. Matching.
Bipartite Graphs.
Stable Marriage Problems.
Advanced Algorithms.

MATHEMATICAL ALGORITHMS.

34. Random Numbers.
Applications.
Linear Congruential Method.
Additive Congruential Method.
Testing Randomness.
Implementational Notes.

35. Arithmetic.
Polynomial Arithmetic.
Polynomial Evaluation and Interpolation.
Polynomial Multiplication.
Arithmetic Operations with Large Integers.
Matrix Arithmetic.

36. Gaussian Elimination.
A Simple Example.
Outline of the Method.
Variations and Extensions.

37. Curve Fittings.
Polynomial Interpolation.
Spline Interpolation.
Method of Least Squares.

38. Integration.
Symbolic Integration.
Simple Quadrature Methods.
Compound Methods.
Adaptive Quadrature.

ADVANCED TOPICS.

39. Parallel Algorithms.
General Approaches.
Perfect Shuffles.
Systolic Arrays.
Perspective.

40. The Fast Fourier Transform.
Evaluate, Multiply, Interpolate.
Complex Roots of Unity.
Evaluation at the Roots of Unity.
Interpolation at the Roots of Unity.
Implementation.

41. Dynamic Programming.
Knapsack Problem.
Matrix Chain Product.
Optimal Binary Search Trees.
Time and Space Requirements.

42. Linear Programming.
Linear Programs.
Geometric Interpretation.
The Simplex Method.
Implementation.

43. Exhaustive Search.
Exhaustive Search in Graphs.
Backtracking.
Digression: Permutation Generation.
Approximation Algorithms.

44. NP-Complete Problems.
Deterministic and Nondeterministic Polynomial-Time Algorithms.
NP-Completeness.
Cook's Theorem.
Some NP-Complete Problems. 0201510596T04062001

CS0701:

Algorithms

Back to Top

商品描述(中文翻譯)

描述

這個版本的 Sedgewick 暢銷書提供了一個全面的 C++ 實現演算法的集合。所包含的演算法涵蓋了廣泛的基本和更高級的方法：排序、搜尋、字串處理、幾何、圖形和數學演算法。讀者將在物件導向程式設計環境中發現，如何實現、運行、除錯和在實際應用中使用關鍵演算法。

基本概念。
1. 介紹。
演算法。
主題大綱。

2. C++（和 C）範例：歐幾里得演算法。
資料類型。
輸入/輸出。
結論。

3. 基本資料結構。
陣列。
鏈結串列。
儲存分配。
推疊。
隊列。
抽象和具體資料類型。

4. 樹。
詞彙表。
屬性。
表示二元樹。
表示森林。
遍歷樹。

5. 遞迴。
遞迴關係。
分治法。
遞迴樹遍歷。
移除遞迴。
觀點。

6. 演算法分析。
選擇演算法。
實證分析。
程式優化。
演算法與系統。

排序演算法。
7. 基本排序方法。
遊戲規則。
選擇排序。
插入排序。
額外：氣泡排序。
基本排序的性能特徵。
大記錄的檔案排序。
Shell 排序。
分佈計數。

8. 快速排序。
基本演算法。
快速排序的性能特徵。
移除遞迴。
小子檔案。
三數中位數分割。
選擇。

9. 基數排序。
位元。
基數交換排序。
直排基數排序。
基數排序的性能特徵。
線性排序。

10. 優先隊列。
基本實現。
堆資料結構。
堆上的演算法。
堆排序。
間接堆。
進階實現。

11. 合併排序。
合併。
合併排序。
輕量合併排序。
自底向上的合併排序。
性能特徵。
優化實現。
再次探討遞迴。

12. 外部排序。
排序-合併。
平衡多路合併。
替換選擇。
實務考量。
多相合併。
更簡單的方法。

搜尋演算法。
13. 基本搜尋方法。
順序搜尋方法。
二元搜尋。
二元樹搜尋。
刪除。
間接二元搜尋樹。

14. 平衡樹。
自上而下的 2-3-4 樹。
紅黑樹。
其他演算法。

15. 雜湊。
雜湊函數。
獨立鏈結。
線性探查。
雙重雜湊。
觀點。

16. 基數搜尋。
數位搜尋樹。
基數搜尋樹。
多路基數搜尋。
Patricia。

17. 外部搜尋。
索引順序存取。
B 樹。
可擴展雜湊。
虛擬記憶體。

字串處理。
18. 字串搜尋。
簡短歷史。
硬暴力演算法。
Knuth-Morris-Pratt 演算法。
Boyer-Moore 演算法。
Rabin-Karp 演算法。
多重搜尋。

19. 模式匹配。
描述模式。
模式匹配機器。
表示機器。
模擬機器。

20. 解析。
無上下文文法。
自上而下解析。
自下而上解析。
編譯器。
編譯器的編譯器。

21. 檔案壓縮。
長度編碼。
可變長度編碼。
建立 Huffman 碼。
實現。

22. 密碼學。
遊戲規則。
簡單方法。
加密/解密機器。
公開金鑰密碼系統。

幾何演算法。
23. 基本幾何方法。
點、線和多邊形。
線段交集。
簡單封閉路徑。
包含於多邊形中。
觀點。

24. 尋找凸包。
遊戲規則。
包裝法。
Graham 掃描。
內部消除。
性能問題。

25. 範圍搜尋。
基本方法。
網格方法。
二維樹。
多維範圍搜尋。

26. 幾何交集。
水平和垂直線。
實現。
一般線交集。

27. 最近點問題。
最近對問題。
Voronoi 圖。

圖形演算法。
28. 基本圖形演算法。
詞彙表。
表示。
深度優先搜尋。
非遞迴深度優先搜尋。
廣度優先搜尋。
迷宮。
觀點。

29. 連通性。
連通分量。
二連通性。
聯合-查找連通性。

30. 加權圖。
最小生成樹。
優先搜尋。
Kruskal 方法。
最短路徑。
密集圖中的最小生成樹和最短路徑。
幾何問題。

31. 有向圖。
深度優先搜尋。
傳遞閉包。
所有最短路徑。
拓撲排序。
強連通分量。

32. 網路流。
網路流問題。
Ford-Fulkerson 方法。
網路搜尋。

33. 匹配。
二分圖。
穩定婚姻問題。
進階演算法。

數學演算法。
34. 隨機數。
應用。
線性同餘法。
加法同餘法。
測試隨機性。
實現注意事項。

35. 算術。
多項式算術。
多項式評估和插值。
多項式乘法。
大整數的算術運算。
矩陣算術。

36. 高斯消去法。
簡單範例。
方法大綱。
變化和擴展。

37. 曲線擬合。
多項式插值。
Spline 插值。
最小二乘法。

38. 積分。
符號積分。
簡單的求積法。
複合方法。
自適應求積。

進階主題。
39. 並行演算法。
一般方法。
完美洗牌。
系統陣列。
觀點。

40. 快速傅立葉變換。
評估、乘法、插值。
複數單位根。
在單位根處的評估。
在單位根處的插值。
實現。

41. 動態規劃。
背包問題。
矩陣鏈乘法。
最佳二元搜尋樹。
時間和空間需求。

42. 線性規劃。
線性程式。
幾何解釋。
單純形法。
實現。

43. 積極搜尋。
圖中的積極搜尋。
回溯法。
額外：排列生成。
近似演算法。

44. NP 完全問題。
確定性和非確定性多項式時間演算法。
NP 完全性。
Cook 定理。
一些 NP 完全問題。

類似商品