An edition of Data structures and algorithm analysis in C (1993)

Data structures and algorithm analysis in C++

3rd ed.

by

  • ★★★ ★ 3.7 (3 ratings)
  • 39 Want to read
  • 7 Currently reading
  • 4 Have read
Cover of: Data structures and algorithm analysis in C++ by Mark Allen Weiss, Mark Allen Weiss
Preview Only

My Reading Lists:

Create a new list
Notes
  • ★★★ ★ 3.7 (3 ratings)
  • 39 Want to read
  • 7 Currently reading
  • 4 Have read
Notes

Check nearby libraries

Buy this book

Last edited by Drini
September 13, 2025 | History
Edit
An edition of Data structures and algorithm analysis in C (1993)

Data structures and algorithm analysis in C++

3rd ed.

by

  • ★★★ ★ 3.7 (3 ratings)
  • 39 Want to read
  • 7 Currently reading
  • 4 Have read

xv, 511 p. : 24 cm

Publish Date
Publisher
Pearson Addison-Wesley
Language
English
Pages
608

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Data structures (Computer science), Computer algorithms, C++ (Computer program language), C (Computer program language), C plus plus (computer program language), Algoritmus (számítógépes), Programozási nyelv, Data structures, Adatszerkezetek (számítógéptudomány), C++, Algorithms (Computer science), C (Computer program language), Computers & the internet, Programming
Edition Availability
Cover of: Data structures and algorithm analysis in C++
Data structures and algorithm analysis in C++
2005, Pearson Addison-Wesley
in English - 3rd ed.
Cover of: Data structures & algorithm analysis in C++
Data structures & algorithm analysis in C++
1999, Addison Wesley
in English - 2nd ed.
Cover of: Data structures and algorithm analysis in C
Data structures and algorithm analysis in C
1997, Addison-Wesley, Addison Wesley
in English - 2nd ed.
Cover of: Data structures and algorithm analysis in C
Data structures and algorithm analysis in C
1997, Addison-Wesley
in English - 2nd ed., international edition.
Cover of: Data structures and algorithm analysis in C++
Data structures and algorithm analysis in C++
1994, Benjamin/Cummings Pub. Co.
in English
Cover of: Data structures and algorithm analysis in C [plus plus]
Data structures and algorithm analysis in C [plus plus]
1994, Benjamin/Cummings
in English
Cover of: Data structures and algorithm analysis in C
Data structures and algorithm analysis in C
1993, Benjamin/Cummings Pub. Co.
in English

Add another edition?

Book Details

Table of Contents

Preface
Page xv
Chapter 1. Introduction
Page 1
What's the Book About?
Page 1
Mathematics Review
Page 2
Exponents
Page 3
Logarithms
Page 3
Series
Modular Arithmetic
Page 5
The P Word
Page 6
A Brief Introduction to Recursion
Page 7
C++ Classes
Page 11
Basic Class Syntax
Page 12
Extra Constructor Syntax and Accessors
Page 12
Separation of Interface and Implementation
Page 15
vector and string
Page 17
C++ Details
Page 19
Pointers
Page 19
Parameter Passing
Page 21
Return Passing
Page 22
Reference Variables
Page 23
The Big Three: Destructor, Copy Constructor, operator=
Page 23
C-style Arrays and Strings
Page 26
Templates
Page 29
Function Templates
Page 29
Class Templates
Page 30
Object, Comparable, and an Example
Page 32
Function Objects
Page 34
Separate Compilation of Class Templates
Page 35
Using Matrices
Page 37
The Data Members, Constructor, and Basic Accessors
Page 37
operator[]
Page 37
Destructor, Copy Assignment, Copy Constructor
Page 39
Summary
Page 39
Exercises
Page 39
References
Page 41
Chapter 2. Algorithm Analysis
Page 43
Mathematical Background
Page 43
Model
Page 46
What to Analyze
Page 46
Running Time Calculations
Page 49
A Simple Example
Page 49
General Rules
Page 50
Solutions for the Maximum Subsequence Sum Problem
Page 52
Logarithms in the Running Time
Page 58
Checking Your Analysis
Page 62
A Grain of Salt
Page 63
Summary
Page 63
Exercises
Page 64
References
Page 69
Chapter 3. Lists, Stacks, and Queues
Page 71
Abstract Data Types (ADTs)
Page 71
The List ADT
Page 72
Simple Array Implementation of Lists
Page 72
Simple Linked Lists
Page 73
vector and list in the STL
Page 74
Iterators
Page 75
Example: Using erase on a List
Page 77
const_iterators
Page 77
Implementation of vector
Page 79
Implementation of list
Page 83
The Stack ADT
Page 94
Stack Model
Page 94
Implementation of Stacks
Page 95
Applications
Page 96
The Queue ADT
Page 104
Queue Model
Page 104
Array Implementation of Queues
Page 104
Applications of Queues
Page 106
Summary
Page 107
Exercises
Page 108
Chapter 4. Trees
Page 113
Preliminaries
Page 113
Implementation of Trees
Page 114
Tree Traversals with an Application
Page 115
Binary Trees
Page 119
Implementation
Page 120
An Example: Expression Trees
Page 121
The Search Tree ADT - Binary Search Trees
Page 124
contains
Page 125
findMin and findMax
Page 125
insert
Page 129
remove
Page 130
Destructor and Copy Assignment Operator
Page 132
Average-Case Analysis
Page 133
AVL Trees
Page 136
Single Rotation
Page 139
Double Rotation
Page 142
Splay Trees
Page 149
A Simple Idea (That Does Not Work)
Page 150
Splaying
Page 152
Tree Traversals (Revisited)
Page 158
B-Trees
Page 159
Sets and Maps in the Standard Library
Page 165
Sets
Page 165
Maps
Page 166
Implementation of set and map
Page 167
An Example That Uses Several Maps
Page 168
Summary
Page 174
Exercises
Page 174
References
Page 181
Chapter 5. Hashing
Page 185
General Idea
Page 185
Hash Function
Page 186
Separate Chaining
Page 188
Hash Tables Without Linked Lists
Page 192
Linear Probing
Page 193
Quadratic Probing
Page 195
Double Hashing
Page 199
Rehashing
Page 200
Hash Tables in the Standard Library
Page 204
Extendible Hashing
Page 204
Summary
Page 207
Exercises
Page 208
References
Page 211
Chapter 6. Priority Queues (Heaps)
Page 213
Model
Page 213
Simple Implementations
Page 214
Binary Heap
Page 215
Structure Property
Page 215
Heap-Order Property
Page 216
Basic Heap Operations
Page 217
Other Heap Operations
Page 220
Applications of Priority Queues
Page 225
The Selection Problem
Page 226
Event Simulation
Page 227
d-Heaps
Page 228
Leftist Heaps
Page 229
Leftist Heap Property
Page 229
Leftist Heap Operations
Page 230
Skew Heaps
Page 235
Binomial Queues
Page 239
Binomial Queue Structure
Page 240
Binomial Queue Operations
Page 241
Implementation of Binomial Queues
Page 244
Priority Queues in the Standard Library
Page 251
Summary
Page 251
Exercises
Page 251
References
Page 257
Chapter 7. Sorting
Page 261
Preliminaries
Page 261
Insertion Sort
Page 262
The Algorithm
Page 262
STL Implementation of Insertion Sort
Page 263
Analysis of Insertion Sort
Page 264
A Lower Bound for Simple Sorting Algorithms
Page 265
Shellsort
Page 266
Worst-Case Analysis of Shellsort
Page 268
Heapsort
Page 270
Analysis of Heapsort
Page 272
Mergesort
Page 274
Analysis of Mergesort
Page 276
Quicksort
Page 279
Picking the Pivot
Page 280
Partitioning Strategy
Page 282
Small Arrays
Page 284
Actual Quicksort Routines
Page 284
Analysis of Quicksort
Page 287
A Linear-Expected-Time Algorithm for Selection
Page 290
Indirect Sorting
Page 292
vector<Comparable*> Does Not Work
Page 295
Smart Pointer Class
Page 295
Overloading operator<
Page 295
Dereferencing a Pointer with *
Page 295
Overloading the Type Conversion Operator
Page 295
Implicit Type Conversions Are Everywhere
Page 296
Dual-Direction Implicit Conversions Can Cause Ambiguities
Page 296
Pointer Subtraction Is Legal
Page 297
A General Lower Bound for Sorting
Page 297
Decision Trees
Page 297
Bucket Sort
Page 299
External Sorting
Page 300
Why We Need New Algorithms
Page 300
Model for External Sorting
Page 300
The Simple Algorithm
Page 301
Multiway Merge
Page 302
Polyphase Merge
Page 303
Replacement Selection
Page 304
Summary
Page 305
Exercises
Page 306
References
Page 311
Chapter 8. The Disjoint Set Class
Page 315
Equivalence Relations
Page 315
The Dynamic Equivalence Problem
Page 316
Basic Data Structure
Page 317
Smart Union Algorithms
Page 321
Path Compression
Page 324
Worst Case for Union-by-Rank and Path Compression
Page 325
Analysis of the Union/Find Algorithm
Page 326
An Application
Page 331
Summary
Page 334
Exercises
Page 335
References
Page 336
Chapter 9. Graph Algorithms
Page 339
Definitions
Page 339
Representation of Graphs
Page 340
Topological Sort
Page 342
Shortest-Path Algorithms
Page 345
Unweighted Shortest Paths
Page 347
Dijkstra's Algorithm
Page 351
Graphs with Negative Edge Costs
Page 360
Acyclic Graphs
Page 360
All-Pairs Shortest Path
Page 364
Shortest Path Example
Page 365
Network Flow Problems
Page 367
A Simple Maximum-Flow Algorithm
Page 367
Minimum Spanning Tree
Page 371
Prim's Algorithm
Page 373
Kruskal's Algorithm
Page 376
Applications of Depth-First Search
Page 378
Undirected Graphs
Page 379
Biconnectivity
Page 381
Euler Circuits
Page 385
Directed Graphs
Page 388
Finding Strong Components
Page 390
Introduction to NP-Completeness
Page 392
Easy vs. Hard
Page 392
The Class NP
Page 393
NP-Complete Problems
Page 394
Summary
Page 396
Exercises
Page 396
References
Page 404
Chapter 10. Algorithm Design Techniques
Page 409
Greedy Algorithms
Page 409
A Simple Scheduling Problem
Page 410
Huffman Codes
Page 413
Approximate Bin Packing
Page 419
Divide and Conquer
Page 427
Running Time of Divide and Conquer Algorithms
Page 428
Closest-Points Problem
Page 430
The Selection Problem
Page 435
Theoretical Improvements for Arithmetic Problems
Page 438
Dynamic Programming
Page 442
Using a Table Instead of Recursion
Page 442
Ordering Matrix Multiplications
Page 444
Optimal Binary Search Tree
Page 447
All-Pairs Shortest Path
Page 451
Randomized Algorithms
Page 454
Random Number Generators
Page 455
Skip Lists
Page 459
Primality Testing
Page 461
Backtracking Algorithms
Page 464
The Turnpike Reconstruction Problem
Page 465
Games
Page 469
Summary
Page 475
Exercises
Page 475
References
Page 485
Chapter 11. Amortized Analysis
Page 491
An Unrelated Puzzle
Page 492
Binomial Queues
Page 492
Skew Heaps
Page 497
Fibonacci Heaps
Page 499
Cutting Nodes in Leftist Heaps
Page 500
Lazy Merging for Binomial Queues
Page 502
The Fibonacci Heap Operations
Page 506
Proof of the Time Bound
Page 506
Splay Trees
Page 509
Summary
Page 513
Exercises
Page 513
References
Page 515
Chapter 12. Advanced Data Structures and Implementation
Page 517
Top-Down Splay Trees
Page 517
Red-Black Trees
Page 525
Bottom-Up Insertion
Page 526
Top-Down Red-Black Trees
Page 527
Top-Down Deletion
Page 531
Deterministic Skip Lists
Page 535
AA-Trees
Page 540
Treaps
Page 547
k-d Trees
Page 549
Pairing Heaps
Page 553
Summary
Page 558
Exercises
Page 558
References
Page 563
Appendix A. Separate Compilation of Class Templates
Page 567
Everything in the Header
Page 568
Explicit Instantiation
Page 568
The export Directive
Page 570
Index
Page 571

Edition Notes

Includes bibliographical references and index.

Published in
Boston

Classifications

Dewey Decimal Class
005.13/3
Library of Congress
QA76.73.C153 W46 2005, QA76.73.C153 W46 2006, QA76.73.C153W46 2005

The Physical Object

Pagination
p. cm.
Number of pages
608

Edition Identifiers

Open Library
OL3407713M
ISBN 10
0321375319
LCCN
2005023534
OCLC/WorldCat
61278554
LibraryThing
9163518
Goodreads
3782208

Work Identifiers

Work ID
OL1958940W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
September 13, 2025 Edited by Drini Add TOC from Tocky
January 31, 2025 Edited by MARC Bot import existing book
December 19, 2023 Edited by ImportBot import existing book
January 14, 2023 Edited by ImportBot import existing book
April 1, 2008 Created by an anonymous user Imported from Scriblio MARC record