书籍详情
数据结构与算法分析C++描述（第2版，影印版，英文版）
作者：（ ）Mark Allen Weiss著
出版社：清华大学出版社
出版时间：2002-09-01
ISBN：9787302057024
定价：¥54.00
购买这本书可以去
内容简介
（数据结构与算法分析C++描述第2版）MarkAllenWeiss著此书是作者1996年出版的“Algorithm，DataStructures，andProblemSolvingwithC++”的缩编本，原书正文807页，作者对内容包括算法重新作了编排，本书正文575页共分12章，其内容依次为C++简介，算法分析；表、栈与队列；树；散列；优先队列（堆）；排序；并查集；图；算法设计技术；缓冲分析；高级数据结构和实现。附录中给出类设计的模板。本书内容基本符合目前《数据结构与算法》大纲的要求，比较适合当前的教学需要。内容编排上较为合理，篇幅较小，叙述清楚，适合于本科高年级和研究生使用。
作者简介
暂缺《数据结构与算法分析C++描述（第2版，影印版，英文版）》作者简介
目录
Chapter l Introduction
l.l. What''s the Book Aboat
l.2. Mathematics Review
l.2.l. Exponents
l.2.2. Logarithms
l.2.3. Series
l.2.4. Modular Arithmetic
l.2.5. The P Word
l.3. A Brief Introduction to Recursion
l.4. C
Classes
l.4.l. Basic class Syntax
l.4.2. Extra Constractor Syntax and Accessors
l.4.3. Separation of Interface and Implementation
l.4.4. vector and string
l.5. C
Details
l.5.l. Pointers
1.5.2. Parameter Passing
l.5.3. Return Passing
l.5.4. Reference Variables
l.5.5. The Big Three: Destructor, Copy Constructor, operator=
l.5.6. The World of C
l.6. Templates
l.6.l. Function Templates
l.6.2. Class Templates
l.6.3. Object, Comparable, and an Example
1.7. Using Matrices
l.7.l. The Data Members, Constructor, and Basic Accessors
l.7.2. operator[]
l.7.3. Destructor, Copy Assignment, Copy Constructor Summary
Exercises
References
Chapter 2 Algorithm Analysis
2.l. Mathematical Background
2.2. Model
2.3. What to Analyze
2.4. Running Time Calculations
2.4.l. A Simple Example
2.4.2. General Rules
2.4.3. Solutions for the Maximum Subsequence Sum Problem
2.4.4. Logarithms in the Running Time
2.4.5. Checking Your Analysis
2.4.6. A GraLin of SaLlt
Summary
Exercises
References
Chapter 3 Lists, Stacks, and Queues
3.1. Abstract Data Types AOTS
3.2. The List ADT
3.2.1 . Simple Array Implementation of Lists
3.2.2. Linked Lists
3.2.3. Programming Details
3.2.4. Memory Reclamation and the Big Three
3.2.5. Doubly Linked Lists
3.2.6. Circular Linked Lists
3.2.7. Examples
3.2.8. Cursor Implementation of Linked Lists
3.3. The Stack ADT
3.3.l. Stack Model
3.3.2. Implementation of Stacks
3.3.3. Applications
3.4. The Queue ADT
3.4.l. Queue Model
3.4.2. Array Implementation of Queues
3.4.3. Applications of Queues
Summary
Exercises
Chapter 4 Trees
4.l. Preliminaries
4.1.l. Implementation of Trees
4.l.2. Tree Traversals with an Application
4.2. Binary Trees
4.2.l. Implementation
4.2.2. An Example: Expression Trees
4.3. The Search Tree ADT-Binary Search Trees
4.3.l. find
4.3.2. findMin and findMax
4.3.3. insert
4.3.4. remove
4.3.5. Destructor and Copy Assignment Operator
4.3.6. Average-Case Analysis
4.4. AVL Trees
4.4.l. Single Rotation
4.4.2. Double Rotation
4.5. Splay Trees
4.5.l. A Simple Idea That Does Not Work
4.5.2. Splaying
4.6. Tree Traversals Revisited
4.7. B-Trees
Summary
Exercises
References
Chapter 5 Hashing
5.l. General Idea
5.2. Hash Function
5.3. Separate Chaining
5.4. Open Addressing
5.4.l. Linear Probing
5.4.2. Quadratic Probing
5.4.3. Double Hashing
5.5. Rehashing
5.6. Extendible Hashing
Summary
Eexercises
References
Chapter 6 Priority Queues Heaps
6.l. Model
6.2. Simple Implementations
6.3. Binary Heap
6.3.l . Structure Property
6.3.2. Heap-Order Property
6.3.3. Basic Heap Operations
6.3.4. Other Heap Operations
6.4. Applications of Priority Queues
6.4.l. The Selection Problem
6.4.2. Event Simulation
6.5. d-Heaps
6.6. Leftist Heaps
6.6.l. Leftist Heap Property
6.6.2. Leftist Heap Operations
6.7. Skew Heaps
6.8. Binomial Queues
6.8.l. Binomial Queue Structure
6.8.2. Binomial Queue Operations
6.8.3. Implementation of Binomial Queues
Summary
Exercises
References
Chapter 7 Sorting
7.l. Preliminaries
7.2. Insertion Son
7.2.l. The Algorithm
7.2.2. Analysis of Insenion SOH
7.3. A Lower Bound for Simple Soning Algorithms
7.4. Shellson
7.4.1 . Worst-Case Analysis of Shellsort
7.5. Heapsort
7.5.l . Analysis of Heapson
7.6. MergesoH
7.6. l . Analysis of Mergesort
7.7. QoicksoH
7.7.l. Picking the Pivot
7.7.2. Partitioning Strategy
7.7.3. Small Arrays
7.7.4. Actual Quickson Routines
7.7.5. Analysis of Quickson
7.7.6. A Linear-Expected-Time Algorithm for Seleaion
7.8. Indirect Sorting
7.8.l. vector<Comparable ''> Does Not Work
7.8.2. Sman Pointer Class
7.8.3. Overloading operator<
7.8.4. Dereferencing a Pointer with
7.8.5. Overloading the Type Conversion Operator
7.8.6. Implicit Type Conversions Are Everywhere
7.8.7. Daal-Direction Implicit Conversions Can Cause Ambiguities
7.8.8. Pointer Subtraction Is Legal
7.9. A General Lower Bound for Soning
7.9.l. Decision Trees
7.1O. Bucket Sort 288
7.l1 . External Soaing
7.ll.I. Whv We Need New Algorithms
7.ll.2. Model for External SoHing
7.Il.3. The Simple Algorithm
7.ll.4. Multiway Merge
7.1l.5. Polyphase Merge
7.ll.6. Replacement Selection
Summary
Exercises
References
Chapter 8 The Disioint Set ADT
8.l. Equivalence Relations
8.2. The Dynamic Equivalence Problem
8.3. Basic Data Structure
8.4. Smart Union Algorithms
8.5. Path Compression
8.6. Worst Case for Union-by-Rank and Path Compression
8.6. l . Analysis of the Union/Find Algorithm
8.7. An Application
Summary
Exercises
References
Chapter 9 Graph Algorithms
9.l. Definitions
9.l .l . Representation of Graphs
9.2. Topological Sort
9.3. Shortest-Path Algorithms
9.3.l . Unweighted Shortest Paths
9.3.2. Diikstra''s Algorithm
9.3.3. Graphs with Negative Edge Costs
9.3.4. Acyclic Graphs
9.3.5. AII-Pairs Shortest Path
9.4. Network Flow Problems
9.4.l . A Simple Maximum-Flow Algorithm
9.5. Minimum Spanning Tree
9.5.l. Prim''s Algorithm
9.5.2. Kruskal''s Algorithm
9.6. Applications of Depth-First Search
9.6.I . Undirected Graphs
9.6.2. Biconnectivity
9.6.3. Euler Circuits
9.6.4. Directed Graphs
9.6.5. Finding Strong Components
9.7. Introduction to NP-Completeness
9.7.l. Easy vs. Hard
9.7.2. The Class NP
9.7.3. NP-Complete Problems
Summary
Exercises
References
Chapter 1O Algorithm Design Techniques
1O. l . Greedy Algorithms
1O.l.l. A Simple Scheduling Problem
1O.l.2. Huffman Codes
1O.l.3. Approximate Bin Packing
1O.2. Divide and Conquer
1O.2.l. Running Time of Divide and Conquer Algorithms
1O.2.2. Closest-Points Problem
1O.2.3. The Selection Problem
1O.2.4. Theoretical Improvements for Arithmetic Problems
1O.3. Dynamic Programming
1O.3.l. Using a Table Instead of Recursion
1O.3.2. Ordering Matrix Multiplications .
1O.3.3. Optimal Binary Search Tree
1O.3.4. AII-Pairs Shortest Path
1O.4. Randomized Algorithms
1O.4.l. Random Number Generators
1O.4.2. Skip Lists
10.4.3. Primality Testing
l0.5. packtracking Algorithms
1O.5. l . The Turnpike Reconstruction Problem
1O.5.2. Games
Summary
l.l. What''s the Book Aboat
l.2. Mathematics Review
l.2.l. Exponents
l.2.2. Logarithms
l.2.3. Series
l.2.4. Modular Arithmetic
l.2.5. The P Word
l.3. A Brief Introduction to Recursion
l.4. C
Classes
l.4.l. Basic class Syntax
l.4.2. Extra Constractor Syntax and Accessors
l.4.3. Separation of Interface and Implementation
l.4.4. vector and string
l.5. C
Details
l.5.l. Pointers
1.5.2. Parameter Passing
l.5.3. Return Passing
l.5.4. Reference Variables
l.5.5. The Big Three: Destructor, Copy Constructor, operator=
l.5.6. The World of C
l.6. Templates
l.6.l. Function Templates
l.6.2. Class Templates
l.6.3. Object, Comparable, and an Example
1.7. Using Matrices
l.7.l. The Data Members, Constructor, and Basic Accessors
l.7.2. operator[]
l.7.3. Destructor, Copy Assignment, Copy Constructor Summary
Exercises
References
Chapter 2 Algorithm Analysis
2.l. Mathematical Background
2.2. Model
2.3. What to Analyze
2.4. Running Time Calculations
2.4.l. A Simple Example
2.4.2. General Rules
2.4.3. Solutions for the Maximum Subsequence Sum Problem
2.4.4. Logarithms in the Running Time
2.4.5. Checking Your Analysis
2.4.6. A GraLin of SaLlt
Summary
Exercises
References
Chapter 3 Lists, Stacks, and Queues
3.1. Abstract Data Types AOTS
3.2. The List ADT
3.2.1 . Simple Array Implementation of Lists
3.2.2. Linked Lists
3.2.3. Programming Details
3.2.4. Memory Reclamation and the Big Three
3.2.5. Doubly Linked Lists
3.2.6. Circular Linked Lists
3.2.7. Examples
3.2.8. Cursor Implementation of Linked Lists
3.3. The Stack ADT
3.3.l. Stack Model
3.3.2. Implementation of Stacks
3.3.3. Applications
3.4. The Queue ADT
3.4.l. Queue Model
3.4.2. Array Implementation of Queues
3.4.3. Applications of Queues
Summary
Exercises
Chapter 4 Trees
4.l. Preliminaries
4.1.l. Implementation of Trees
4.l.2. Tree Traversals with an Application
4.2. Binary Trees
4.2.l. Implementation
4.2.2. An Example: Expression Trees
4.3. The Search Tree ADT-Binary Search Trees
4.3.l. find
4.3.2. findMin and findMax
4.3.3. insert
4.3.4. remove
4.3.5. Destructor and Copy Assignment Operator
4.3.6. Average-Case Analysis
4.4. AVL Trees
4.4.l. Single Rotation
4.4.2. Double Rotation
4.5. Splay Trees
4.5.l. A Simple Idea That Does Not Work
4.5.2. Splaying
4.6. Tree Traversals Revisited
4.7. B-Trees
Summary
Exercises
References
Chapter 5 Hashing
5.l. General Idea
5.2. Hash Function
5.3. Separate Chaining
5.4. Open Addressing
5.4.l. Linear Probing
5.4.2. Quadratic Probing
5.4.3. Double Hashing
5.5. Rehashing
5.6. Extendible Hashing
Summary
Eexercises
References
Chapter 6 Priority Queues Heaps
6.l. Model
6.2. Simple Implementations
6.3. Binary Heap
6.3.l . Structure Property
6.3.2. Heap-Order Property
6.3.3. Basic Heap Operations
6.3.4. Other Heap Operations
6.4. Applications of Priority Queues
6.4.l. The Selection Problem
6.4.2. Event Simulation
6.5. d-Heaps
6.6. Leftist Heaps
6.6.l. Leftist Heap Property
6.6.2. Leftist Heap Operations
6.7. Skew Heaps
6.8. Binomial Queues
6.8.l. Binomial Queue Structure
6.8.2. Binomial Queue Operations
6.8.3. Implementation of Binomial Queues
Summary
Exercises
References
Chapter 7 Sorting
7.l. Preliminaries
7.2. Insertion Son
7.2.l. The Algorithm
7.2.2. Analysis of Insenion SOH
7.3. A Lower Bound for Simple Soning Algorithms
7.4. Shellson
7.4.1 . Worst-Case Analysis of Shellsort
7.5. Heapsort
7.5.l . Analysis of Heapson
7.6. MergesoH
7.6. l . Analysis of Mergesort
7.7. QoicksoH
7.7.l. Picking the Pivot
7.7.2. Partitioning Strategy
7.7.3. Small Arrays
7.7.4. Actual Quickson Routines
7.7.5. Analysis of Quickson
7.7.6. A Linear-Expected-Time Algorithm for Seleaion
7.8. Indirect Sorting
7.8.l. vector<Comparable ''> Does Not Work
7.8.2. Sman Pointer Class
7.8.3. Overloading operator<
7.8.4. Dereferencing a Pointer with
7.8.5. Overloading the Type Conversion Operator
7.8.6. Implicit Type Conversions Are Everywhere
7.8.7. Daal-Direction Implicit Conversions Can Cause Ambiguities
7.8.8. Pointer Subtraction Is Legal
7.9. A General Lower Bound for Soning
7.9.l. Decision Trees
7.1O. Bucket Sort 288
7.l1 . External Soaing
7.ll.I. Whv We Need New Algorithms
7.ll.2. Model for External SoHing
7.Il.3. The Simple Algorithm
7.ll.4. Multiway Merge
7.1l.5. Polyphase Merge
7.ll.6. Replacement Selection
Summary
Exercises
References
Chapter 8 The Disioint Set ADT
8.l. Equivalence Relations
8.2. The Dynamic Equivalence Problem
8.3. Basic Data Structure
8.4. Smart Union Algorithms
8.5. Path Compression
8.6. Worst Case for Union-by-Rank and Path Compression
8.6. l . Analysis of the Union/Find Algorithm
8.7. An Application
Summary
Exercises
References
Chapter 9 Graph Algorithms
9.l. Definitions
9.l .l . Representation of Graphs
9.2. Topological Sort
9.3. Shortest-Path Algorithms
9.3.l . Unweighted Shortest Paths
9.3.2. Diikstra''s Algorithm
9.3.3. Graphs with Negative Edge Costs
9.3.4. Acyclic Graphs
9.3.5. AII-Pairs Shortest Path
9.4. Network Flow Problems
9.4.l . A Simple Maximum-Flow Algorithm
9.5. Minimum Spanning Tree
9.5.l. Prim''s Algorithm
9.5.2. Kruskal''s Algorithm
9.6. Applications of Depth-First Search
9.6.I . Undirected Graphs
9.6.2. Biconnectivity
9.6.3. Euler Circuits
9.6.4. Directed Graphs
9.6.5. Finding Strong Components
9.7. Introduction to NP-Completeness
9.7.l. Easy vs. Hard
9.7.2. The Class NP
9.7.3. NP-Complete Problems
Summary
Exercises
References
Chapter 1O Algorithm Design Techniques
1O. l . Greedy Algorithms
1O.l.l. A Simple Scheduling Problem
1O.l.2. Huffman Codes
1O.l.3. Approximate Bin Packing
1O.2. Divide and Conquer
1O.2.l. Running Time of Divide and Conquer Algorithms
1O.2.2. Closest-Points Problem
1O.2.3. The Selection Problem
1O.2.4. Theoretical Improvements for Arithmetic Problems
1O.3. Dynamic Programming
1O.3.l. Using a Table Instead of Recursion
1O.3.2. Ordering Matrix Multiplications .
1O.3.3. Optimal Binary Search Tree
1O.3.4. AII-Pairs Shortest Path
1O.4. Randomized Algorithms
1O.4.l. Random Number Generators
1O.4.2. Skip Lists
10.4.3. Primality Testing
l0.5. packtracking Algorithms
1O.5. l . The Turnpike Reconstruction Problem
1O.5.2. Games
Summary
猜您喜欢
