Data Structures and Algorithm Analysis in C++, 2/e (精裝)
暫譯: C++ 資料結構與演算法分析 (第二版)

Mark Allen Weiss

Data Structures and Algorithm Analysis in C++, 2/e (精裝)

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

相關主題

商品描述


Description

In this second edition of his successful book, experienced teacher and author Mark Allen Weiss continues to refine and enhance his innovative approach to algorithms and data structures. Written for the advanced data structures course, this text highlights theoretical topics like abstract data types and the efficiency of algorithms, as well as performance and running time. Before covering algorithms and data structures, the author provides a brief introduction to C++ for programmers unfamiliar with the language. All of the source code will be available over the Internet. Dr. Weiss also distinguishes the book with his clear, friendly writing style, logical organization of topics, and extensive use of figures and examples that show the successive stages of an algorithm.

Back to Top


Features

  • All code has been updated and tested on multiple platforms and conforms to the ANSI standard.
  • Provides chapter on advanced structures and their implementation covering red black trees, top down splay trees, treaps, k-d trees, pairing heaps, and more.
  • Includes a chapter on algorithm and design techniques that covers greedy algorithms, divide and conquer algorithms, dynamic programming, randomized algorithms, and backtracking.
Back to Top


Table Of Contents

1. Introduction.
What's the Book About?
Mathematics Review.
Exponents.
Logarithms.
Series.
Modular Arithmetic.
The P Word.

A Brief Introduction to Recursion
C++ Classes.
Basic class Syntax.
Extra Constructor Syntax and Accessors
Separation of Interface and Implementation.
vector and string.

C++ Details.
Pointers.
Parameter Passing.
Return Passing
Reference Variables.
The Big Three: Destructor, Copy Constructor, operator=.
The World of C.

Templates.
Function Templates.
Class Templates.
Object, Comparable, and an Example.

Using Matrices.
The Data Members, Constructor, and Basic Accessors.
operator .
Destructor, Copy Assignment, Copy Constructor.

Summary.
Exercises.
References.

2. Algorithm Analysis.
Mathematical Background.
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.

Summary.
Exercises.
References.

3. Lists, Stacks, and Queues.
Abstract Data Types (ADTs).
The List ADT.
Simple Array Implementation of Lists.
Linked Lists.
Programming Details.
Memory Reclamation and the Big Three.
Doubly Linked Lists.
Circular 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.

Summary.
Exercises.

4. Trees.
Preliminaries.
Implementation of Trees.
Tree Traversals with an Application.

Binary Trees.
Implementation.
An Example: Expression Trees.

The Search Tree ADT-Binary Search Trees.
find.
findMin and findMax.
insert.
remove.
Destructor and Copy Assignment Operator.
Average-Case Analysis.

AVL Trees.
Single Rotation.
Double Rotation.

Splay Trees.
A Simple Idea (That Does Not Work).
Splaying.

Tree Traversals (Revisited).
B-Trees.
Summary.
Exercises.
References.

5. Hashing.
General Idea.
Hash Function.
Separate Chaining.
Open Addressing.
Linear Probing.
Quadratic Probing.
Double Hashing.

Rehashing.
Extendible Hashing.
Summary.
Exercises.
References.

6. Priority Queues (Heaps).
Model.
Simple Implementations.
Binary Heap.
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.
Implementation of Binomial Queues.

Summary.
Exercises.
References.

7. Sorting.
Preliminaries.
Insertion Sort.
The Algorithm.
Analysis of Insertion Sort.

A Lower Bound for Simple Sorting Algorithms.
Shellsort.
Worst-Case Analysis of Shellsort

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.

Indirect Sorting.
vector Does Not Work.
Smart Pointer Class.
Overloading operator<
Dereferencing a Pointer with *.
Overloading the Type Conversion Operator
Implicit Type Conversions Are Everywhere.
Dual-Direction Implicit Conversions Can Cause Ambiguities.
Pointer Subtraction Is Legal.

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.
Summary.
Exercises.
References.

8. The Disjoint Set ADT.
Equivalence Relations.
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.
Summary.
Exercises.
References.

9. Graph Algorithms.
Definitions.
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 NP-Completeness.
Easy vs. Hard.
The Class NP.
NP-Complete Problems.

Summary.
Exercises.
References.

10. Algorithm Design Techniques.
Greedy Algorithms.
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.

Summary.
Exercises.
References.

11. Amortized Analysis.
An Unrelated Puzzle.
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.
Summary.
Exercises.
References.

12. Advanced Data Structures and Implementation.
Top-Down Splay Trees.
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.
Summary.
Exercises.
References.

Appendix A. The Standard Template Library.
Introduction
Basic STL Concepts.
Header Files and the using Directive
Containers.
iterator.
Pairs.
Function Objects.

Unordered Sequences: vector and list.
vector versus list.
Stacks and Queues.

Sets.
Maps.
Example: Generating a Concordance.
STL Version.
Version without Using the STL

Example: Shortest-Path Calculation.
STL Implementation.
Version without Using the STL.

Other STL Features.

Appendix B. vector and string Classes.
First-Class versus Second-Class Objects.
vector Class.
string Class.

Index. 0201361221T04062001


Back to Top

商品描述(中文翻譯)

描述
在這本成功書籍的第二版中，經驗豐富的教師和作者 Mark Allen Weiss 繼續精煉和增強他對演算法和資料結構的創新方法。本書是為進階資料結構課程而寫，重點強調抽象資料類型和演算法效率等理論主題，以及性能和執行時間。在介紹演算法和資料結構之前，作者為不熟悉 C++ 語言的程式設計師提供了簡要的 C++ 介紹。所有的原始碼將在互聯網上提供。Dr. Weiss 以其清晰、友好的寫作風格、邏輯性強的主題組織以及廣泛使用的圖示和範例來區分本書，這些圖示和範例展示了演算法的各個階段。

特點
- 所有程式碼均已更新並在多個平台上測試，符合 ANSI 標準。
- 提供有關進階結構及其實現的章節，涵蓋紅黑樹、從上到下的擴展樹、treaps、k-d 樹、配對堆等。
- 包含一章有關演算法和設計技術，涵蓋貪婪演算法、分治演算法、動態規劃、隨機演算法和回溯法。

目錄
1. 介紹
本書的內容是什麼？
數學回顧
指數
對數
級數
模運算
P 字
簡介遞迴
C++ 類別
基本類別語法
額外建構子語法和存取器
介面與實現的分離
vector 和 string
C++ 詳細資訊
指標
參數傳遞
返回傳遞
參考變數
三大要素：解構子、複製建構子、operator=
C 的世界
模板
函數模板
類模板
物件、可比較性及範例
使用矩陣
資料成員、建構子和基本存取器
operator .
解構子、複製賦值、複製建構子
總結
練習
參考文獻

2. 演算法分析
數學背景
模型
什麼需要分析
執行時間計算
簡單範例
一般規則
最大子序列和問題的解決方案
執行時間中的對數
檢查你的分析
一絲懷疑
總結
練習
參考文獻

3. 列表、堆疊和佇列
抽象資料類型 (ADTs)
列表 ADT
列表的簡單陣列實現
鏈結列表
程式設計細節
記憶體回收和三大要素
雙向鏈結列表
循環鏈結列表
範例
鏈結列表的游標實現
堆疊 ADT
堆疊模型
堆疊的實現
應用
佇列 ADT
佇列模型
佇列的陣列實現
佇列的應用
總結
練習

4. 樹
預備知識
樹的實現
樹的遍歷及其應用
二元樹
實現
範例：表達式樹
搜索樹 ADT - 二元搜索樹
find
findMin 和 findMax
insert
remove
解構子和複製賦值運算子
平均情況分析
AVL 樹
單旋轉
雙旋轉
擴展樹
一個簡單的想法（不奏效）
擴展
樹的遍歷（重溫）
B 樹
總結
練習
參考文獻

5. 雜湊
一般概念
雜湊函數
獨立鏈接
開放定址
線性探測
二次探測
雙重雜湊
重新雜湊
可擴展雜湊
總結
練習
參考文獻

6. 優先佇列（堆）
模型
簡單實現
二元堆
結構性質
堆序性質
基本堆操作
其他堆操作
優先佇列的應用
選擇問題
事件模擬
d-堆
左派堆
左派堆性質
左派堆操作
偏斜堆
二項佇列
二項佇列結構
二項佇列操作
二項佇列的實現
總結
練習
參考文獻

7. 排序
預備知識
插入排序
演算法
插入排序的分析
簡單排序演算法的下界
Shellsort
Shellsort 的最壞情況分析
Heapsort
Heapsort 的分析
Mergesort
Mergesort 的分析
Quicksort
選擇樞紐
分區策略
小陣列
實際 Quicksort 程式
Quicksort 的分析
選擇的線性期望時間演算法
間接排序
vector 不可行
智能指標類
重載 operator<
使用 * 解引用指標
重載類型轉換運算子
隱式類型轉換無處不在
雙向隱式轉換可能導致歧義
指標減法是合法的
排序的一般下界
決策樹
桶排序
外部排序
為什麼我們需要新演算法
外部排序模型
簡單演算法
多路合併
多相合併
替換選擇
總結
練習
參考文獻

8. 不相交集合 ADT
等價關係
動態等價問題
基本資料結構
智能聯合演算法
路徑壓縮
聯合按秩和路徑壓縮的最壞情況
聯合/查找演算法的分析
一個應用
總結
練習
參考文獻

9. 圖演算法
定義
圖的表示
拓撲排序
最短路徑演算法
無權重最短路徑
Dijkstra 演算法
帶有負邊成本的圖
無環圖
所有對最短路徑
網路流問題
一個簡單的最大流演算法
最小生成樹
Prim 演算法
Kruskal 演算法
深度優先搜索的應用
無向圖
二連通性
歐拉回路
有向圖
尋找強連通分量
NP 完全性介紹
簡單與困難
NP 類
NP 完全問題
總結
練習
參考文獻

10. 演算法設計技術
貪婪演算法
一個簡單的排程問題
Huffman 編碼
近似二進位打包
分治法
分治演算法的執行時間
最近點問題
選擇問題
算術問題的理論改進
動態規劃
使用表格而非遞迴
矩陣乘法的排序
最佳二元搜索樹
所有對最短路徑
隨機演算法
隨機數生成器
跳躍列表
質數測試
回溯演算法
收費公路重建問題
遊戲
總結
練習
參考文獻

11. 平均分析
一個無關的謎題
二項佇列
偏斜堆
費波那契堆
在左派堆中切割節點
二項佇列的懶合併
費波那契堆操作
時間界限的證明
擴展樹
總結
練習
參考文獻

12. 進階資料結構與實現
自上而下的擴展樹
紅黑樹
自下而上的插入
自上而下的紅黑樹
自上而下的刪除
確定性跳躍列表
AA 樹
Treaps
k-d 樹
配對堆
總結
練習
參考文獻

附錄 A. 標準模板庫
介紹
基本 STL 概念
標頭檔和 using 指令
容器
iterator
配對
函數物件
無序序列：vector 和 list
vector 與 list
堆疊和佇列
集合
地圖
範例：生成索引
STL 版本
不使用 STL 的版本
範例：最短路徑計算
STL 實現
不使用 STL 的版本
其他 STL 特性

附錄 B. vector 和 string 類別

類似商品

最後瀏覽商品 (16)