Data Structures, Algorithms, And Applications In C++
Edition: 2 edition
Publisher: Silicon Press
Published: August 31, 2004
Language: eng
Format: Paperback
Number of pages: 792
ISBN-13: 9780929306322
Subjects: Data structures (Computer science); Programming Languages - General; Computers; Computer Bks - Languages / Programming; Computers - Languages / Programming; Disaster Recovery; Computer Books: General; Development; Data structures (Computer scie; C++ (Computer program language); Application software; C++ (Computer program language; Computer algorithms
Table of contents: label: Part I
title: Preliminaries; label: 1
title: C++ Review
pagenum: 1; label: 1.1
title: Introduction
pagenum: 3; label: 1.2
title: Functions and Parameters
pagenum: 3; label: 1.2.1
title: Value Parameters
pagenum: 3; label: 1.2.2
title: Template Functions
pagenum: 1; label: 1.2.3
title: Reference Parameters
pagenum: 5; label: 1.2.4
title: Const Reference Parameters
pagenum: 6; label: 1.2.5
title: Return Values
pagenum: 6; label: 1.2.6
title: Overloaded Functions
pagenum: 7; label: 1.3
title: Exceptions
pagenum: 9; label: 1.3.1
title: Throwing an Exception
pagenum: 9; label: 1.3.2
title: Handling Exceptions
pagenum: 10; label: 1.4
title: Dynamic Memory Allocation
pagenum: 12; label: 1.4.1
title: The operator new
pagenum: 12; label: 1.4.2
title: One-Dimensional Arrays
pagenum: 13; label: 1.4.3
title: Exception Handling
pagenum: 13; label: 1.4.4
title: The operator delete
pagenum: 13; label: 1.4.5
title: Two-Dimensional Arrays
pagenum: 14; label: 1.5
title: Your Very Own Data Type
pagenum: 17; label: 1.5.1
title: The class currency
pagenum: 17; label: 1.5.2
title: Using a Different Representation
pagenum: 24; label: 1.5.3
title: Operator Overloading
pagenum: 26; label: 1.5.4
title: Friends and Protected Class Members
pagenum: 28; label: 1.5.5
title: Addition of #ifndef, #define, and #endif Statements
pagenum: 30; label: 1.6
title: The Exception Class illegalParameterValue
pagenum: 33; label: 1.7
title: Recursion
pagenum: 33; label: 1.7.1
title: Recursive Mathematical Functions
pagenum: 35; label: 1.7.2
title: Induction
pagenum: 36; label: 1.7.3
title: Recursive C++ Functions
pagenum: 37; label: 1.8
title: The Standard Templates Library
pagenum: 43; label: 1.9
title: Testing and Debugging
pagenum: 47; label: 1.9.1
title: What Is Testing?
pagenum: 47; label: 1.9.2
title: Designing Test Data
pagenum: 50; label: 1.9.3
title: Debugging
pagenum: 53; label: 1.10
title: References and Selected Readings
pagenum: 54; label: 2
title: Performance Analysis
pagenum: 55; label: 2.1
title: What Is Performance?
pagenum: 57; label: 2.2
title: Space Complexity
pagenum: 58; label: 2.2.1
title: Components of Space Complexity
pagenum: 58; label: 2.2.2
title: Examples
pagenum: 63; label: 2.3
title: Time Complexity
pagenum: 66; label: 2.3.1
title: Components of Time Complexity
pagenum: 66; label: 2.3.2
title: Operation Counts
pagenum: 67; label: 2.3.3
title: Best, Worst, and Average Operation Counts
pagenum: 73; label: 2.3.4
title: Step Counts
pagenum: 80; label: 3
title: Asymptotic Notation
pagenum: 95; label: 3.1
title: Introduction
pagenum: 96; label: 3.2
title: Asymptotic Notation
pagenum: 99; label: 3.2.1
title: Big Oh Notation (O)
pagenum: 99; label: 3.2.2
title: Omega (Ω) and Theta (Θ) Notations
pagenum: 102; label: 3.3
title: Asymptotic Mathematics (Optional)
pagenum: 104; label: 3.3.1
title: Big Oh Notation (O)
pagenum: 104; label: 3.3.2
title: Omega Notation (Ω)
pagenum: 107; label: 3.3.3
title: Theta Notation (Θ)
pagenum: 109; label: 3.3.4
title: Little Oh Notation (o)
pagenum: 111; label: 3.3.5
title: Properties
pagenum: 111; label: 3.4
title: Complexity Analysis Examples
pagenum: 114; label: 3.5
title: Practical Complexities
pagenum: 117; label: 3.6
title: References and Selected Readings
pagenum: 120; label: 4
title: Performance Measurement
pagenum: 121; label: 4.1
title: Introduction
pagenum: 122; label: 4.2
title: Choosing Instance Size
pagenum: 123; label: 4.3
title: Developing the Test Data
pagenum: 123; label: 4.4
title: Setting Up the Experiment
pagenum: 124; label: 4.5
title: Your Cache and You
pagenum: 131; label: 4.5.1
title: A Simple Computer Model
pagenum: 131; label: 4.5.2
title: Effect of Cache Misses on Run Time
pagenum: 132; label: 4.5.3
title: Matrix Multiplication
pagenum: 133; label: 4.6
title: References and Selected Readings
pagenum: 136; label: Part II
title: Data Structures; label: 5
title: Linear Lists—Array Representation
pagenum: 137; label: 5.1
title: Data Objects and Structures
pagenum: 139; label: 5.2
title: The Linear List Data Structure
pagenum: 140; label: 5.2.1
title: The Abstract Data Type linearList
pagenum: 141; label: 5.2.2
title: The Abstract Class LinearList
pagenum: 142; label: 5.3
title: Array Representation
pagenum: 143; label: 5.3.1
title: The Representation
pagenum: 143; label: 5.3.2
title: Changing the Length of a One-Dimensional Array
pagenum: 145; label: 5.3.3
title: The Class arrayList
pagenum: 146; label: 5.3.4
title: Iterators in C++
pagenum: 153; label: 5.3.5
title: An Iterator for arrayList
pagenum: 155; label: 5.4
title: Vector Representation
pagenum: 161; label: 5.5
title: Multiple Lists in a Single Array
pagenum: 163; label: 5.6
title: Performance Measurement
pagenum: 166; label: 5.7
title: References and Selected Readings
pagenum: 169; label: 6
title: Linear Lists—Linked Representation
pagenum: 170; label: 6.1
title: Singly Linked Lists and Chains
pagenum: 172; label: 6.1.1
title: The Representation
pagenum: 172; label: 6.1.2
title: The Struct chainNode
pagenum: 174; label: 6.1.3
title: The Class chain
pagenum: 174; label: 6.1.4
title: Extensions to the ADT linearList
pagenum: 181; label: 6.1.5
title: The Class extendedChain
pagenum: 182; label: 6.1.6
title: Performance Measurement
pagenum: 183; label: 6.2
title: Circular Lists and Header Nodes
pagenum: 192; label: 6.3
title: Doubly Linked Lists
pagenum: 195; label: 6.4
title: Glossary of Linked List Terms
pagenum: 197; label: 6.5
title: Applications
pagenum: 197; label: 6.5.1
title: Bin Sort
pagenum: 197; label: 6.5.2
title: Radix Sort
pagenum: 202; label: 6.5.3
title: Convex Hull
pagenum: 205; label: 6.5.4
title: Union-Find Problem
pagenum: 209; label: 7
title: Arrays and Matrices
pagenum: 222; label: 7.1
title: Arrays
pagenum: 223; label: 7.1.1
title: The Abstract Data Type
pagenum: 223; label: 7.1.2
title: Indexing a C++ Array
pagenum: 224; label: 7.1.3
title: Row- and Column-Major Mappings
pagenum: 224; label: 7.1.4
title: Array of Arrays Representation
pagenum: 227; label: 7.1.5
title: Row-Major and Column-Major Representation
pagenum: 227; label: 7.1.6
title: Irregular Two-Dimensional Arrays
pagenum: 228; label: 7.2
title: Matrices
pagenum: 230; label: 7.2.1
title: Definitions and Operations
pagenum: 230; label: 7.2.2
title: The Class matrix
pagenum: 233; label: 7.3
title: Special Matrices
pagenum: 239; label: 7.3.1
title: Definitions and Applications
pagenum: 239; label: 7.3.2
title: Diagonal Matrices
pagenum: 242; label: 7.3.3
title: Tridiagonal Matrix
pagenum: 244; label: 7.3.4
title: Triangular Matrices
pagenum: 245; label: 7.3.5
title: Symmetric Matrices
pagenum: 246; label: 7.4
title: Sparse Matrices
pagenum: 252; label: 7.4.1
title: Motivation
pagenum: 252; label: 7.4.2
title: Representation Using a Single Linear List
pagenum: 252; label: 7.4.3
title: Representation Using Many Linear Lists
pagenum: 258; label: 7.4.4
title: Performance Measurement
pagenum: 262; label: 8
title: Stacks
pagenum: 269; label: 8.1
title: Definition and Applications
pagenum: 271; label: 8.2
title: The Abstract Data Type
pagenum: 274; label: 8.3
title: Array Representation
pagenum: 274; label: 8.3.1
title: Implementation as a Derived Class
pagenum: 274; label: 8.3.2
title: The Class arrayStack
pagenum: 277; label: 8.3.3
title: Performance Measurement
pagenum: 277; label: 8.4
title: Linked Representation
pagenum: 282; label: 8.4.1
title: The Class derivedLinkedStack
pagenum: 282; label: 8.4.2
title: The Class linkedStack
pagenum: 282; label: 8.4.3
title: Performance Measurement
pagenum: 282; label: 8.5
title: Applications
pagenum: 284; label: 8.5.1
title: Parenthesis Matching
pagenum: 284; label: 8.5.2
title: Towers of Hanoi
pagenum: 285; label: 8.5.3
title: Rearranging Railroad Cars
pagenum: 289; label: 8.5.4
title: Switch Box Routing
pagenum: 294; label: 8.5.5
title: Offline Equivalence Class Problem
pagenum: 297; label: 8.5.6
title: Rat in a Maze
pagenum: 300; label: 8.6
title: References and Selected Readings
pagenum: 316; label: 9
title: Queues
pagenum: 317; label: 9.1
title: Definition and Applications
pagenum: 319; label: 9.2
title: The Abstract Data Type
pagenum: 320; label: 9.3
title: Array Representation
pagenum: 322; label: 9.3.1
title: The Representation
pagenum: 322; label: 9.3.2
title: The Class arrayQueue
pagenum: 325; label: 9.4
title: Linked Representation
pagenum: 330; label: 9.5
title: Applications
pagenum: 333; label: 9.5.1
title: Railroad Car Rearrangement
pagenum: 333; label: 9.5.2
title: Wire Routing
pagenum: 336; label: 9.5.3
title: Image-Component Labeling
pagenum: 341; label: 9.5.4
title: Machine Shop Simulation
pagenum: 344; label: 9.6
title: References and Selected Readings
pagenum: 361; label: 10
title: Skip Lists and Hashing
pagenum: 362; label: 10.1
title: Dictionaries
pagenum: 364; label: 10.2
title: The Abstract Data Type
pagenum: 366; label: 10.3
title: Linear List Representation
pagenum: 367; label: 10.4
title: Skip List Representation (Optional)
pagenum: 368; label: 10.4.1
title: The Ideal Case
pagenum: 368; label: 10.4.2
title: Insertions and Deletions
pagenum: 372; label: 10.4.3
title: Assigning Levels
pagenum: 373; label: 10.4.4
title: The Struct skipNode
pagenum: 374; label: 10.4.5
title: The Class skipList
pagenum: 374; label: 10.4.6
title: Complexity of skipList Methods
pagenum: 378; label: 10.5
title: Hash Table Representation
pagenum: 381; label: 10.5.1
title: Ideal Hashing
pagenum: 381; label: 10.5.2
title: Hash Functions and Tables
pagenum: 382; label: 10.5.3
title: Linear Probing
pagenum: 387; label: 10.5.4
title: Hashing with Chains
pagenum: 394; label: 10.6
title: An Application—Text Compression
pagenum: 402; label: 10.6.1
title: LZW Compression
pagenum: 403; label: 10.6.2
title: Implementation of LZW Compression
pagenum: 403; label: 10.6.3
title: LZW Decompression
pagenum: 409; label: 10.6.4
title: Implementation of LZW Decompression
pagenum: 411; label: 10.6.5
title: Performance Evaluation
pagenum: 413; label: 10.7
title: References and Selected Readings
pagenum: 116; label: 11
title: Binary and Other Trees
pagenum: 418; label: 11.1
title: Trees
pagenum: 420; label: 11.2
title: Binary Trees
pagenum: 425; label: 11.3
title: Properties of Binary Trees
pagenum: 426; label: 11.4
title: Representation of Binary Trees
pagenum: 429; label: 11.4.1
title: Array-Based Representation
pagenum: 429; label: 11.4.2
title: Linked Representation
pagenum: 430; label: 11.5
title: Common Binary Tree Operations
pagenum: 432; label: 11.6
title: Binary Tree Traversal
pagenum: 432; label: 11.7
title: The ADT Binary Tree
pagenum: 439; label: 11.8
title: The Class linkedBinaryTree
pagenum: 439; label: 11.9
title: Applications
pagenum: 443; label: 11.9.1
title: Placement of Signal Boosters
pagenum: 443; label: 11.9.2
title: Union-Find Problem
pagenum: 450; label: 11.10
title: References and Selected Readings
pagenum: 463; label: 12
title: Priority Queues
pagenum: 464; label: 12.1
title: Definition and Applications
pagenum: 466; label: 12.2
title: The Abstract Data Type
pagenum: 467; label: 12.3
title: Linear Lists
pagenum: 468; label: 12.4
title: Heaps
pagenum: 469; label: 12.4.1
title: Definitions
pagenum: 469; label: 12.4.2
title: Insertion into a Max Heap
pagenum: 470; label: 12.4.3
title: Deletion from a Max Heap
pagenum: 471; label: 12.4.4
title: Max Heap Initialization
pagenum: 472; label: 12.4.5
title: The Class maxHeap
pagenum: 474; label: 12.4.6
title: Heaps and the STL
pagenum: 478; label: 12.5
title: Leftist Trees
pagenum: 479; label: 12.5.1
title: Height- and Weight-Biased Min and Max Leftist Trees
pagenum: 479; label: 12.5.2
title: Insertion into a Max HBLT
pagenum: 482; label: 12.5.3
title: Deletion from a Max HBLT
pagenum: 482; label: 12.5.4
title: Melding Two Max HBLTs
pagenum: 482; label: 12.5.5
title: Initialization
pagenum: 485; label: 12.5.6
title: The Class maxHblt
pagenum: 185; label: 12.6
title: Applications
pagenum: 491; label: 12.6.1
title: Heap Sort
pagenum: 491; label: 12.6.2
title: Machine Scheduling
pagenum: 493; label: 12.6.3
title: Huffman Codes
pagenum: 497; label: 12.7
title: References and Selected Readings
pagenum: 504; label: 13
title: Tournament Trees
pagenum: 505; label: 13.1
title: Winner Trees and Applications
pagenum: 506; label: 13.2
title: The ADT Winner Tree
pagenum: 511; label: 13.3
title: Winner Tree Implementation
pagenum: 511; label: 13.3.1
title: Representation
pagenum: 511; label: 13.3.2
title: Initializing a Winner Tree
pagenum: 513; label: 13.3.3
title: Replaying Matches
pagenum: 514; label: 13.3.4
title: The Class completeWinnerTree
pagenum: 514; label: 13.4
title: Loser Trees
pagenum: 515; label: 13.5
title: Applications
pagenum: 518; label: 13.5.1
title: Bin Packing Using First Fit
pagenum: 518; label: 13.5.2
title: Bin Packing Using Next Fit
pagenum: 524; label: 13.6
title: References and Selected Readings
pagenum: 528; label: 14
title: Binary Search Trees
pagenum: 529; label: 14.1
title: Definitions
pagenum: 531; label: 14.1.1
title: Binary Search Trees
pagenum: 531; label: 14.1.2
title: Indexed Binary Search Trees
pagenum: 532; label: 14.2
title: Abstract Data Types
pagenum: 533; label: 14.3
title: Binary Search Tree Operations and Implementation
pagenum: 535; label: 14.3.1
title: The Class binarySearchTree
pagenum: 535; label: 14.3.2
title: Searching
pagenum: 536; label: 14.3.3
title: Inserting an Element
pagenum: 536; label: 14.3.4
title: Deleting an Element
pagenum: 536; label: 14.3.5
title: Height of a Binary Search Tree
pagenum: 540; label: 14.4
title: Binary Search Trees with Duplicates
pagenum: 544; label: 14.5
title: Indexed Binary Search Trees
pagenum: 545; label: 14.6
title: Applications
pagenum: 548; label: 14.6.1
title: Histogramming
pagenum: 548; label: 14.6.2
title: Best-Fit Bin Packing
pagenum: 550; label: 14.6.3
title: Crossing Distribution
pagenum: 553; label: 15
title: Balanced Search Trees
pagenum: 563; label: 15.1
title: AVL Trees
pagenum: 566; label: 15.1.1
title: Definition
pagenum: 566; label: 15.1.2
title: Height of an AVL Tree
pagenum: 567; label: 15.1.3
title: Representation of an AVL Tree
pagenum: 567; label: 15.1.4
title: Searching an AVL Search Tree
pagenum: 567; label: 15.1.5
title: Inserting into an AVL Search Tree
pagenum: 567; label: 15.1.6
title: Deletion from an AVL Search Tree
pagenum: 572; label: 15.2
title: Red-Black Trees
pagenum: 577; label: 15.2.1
title: Definition
pagenum: 577; label: 15.2.2
title: Representation of a Red-Black Tree
pagenum: 579; label: 15.2.3
title: Searching a Red-Black Tree
pagenum: 579; label: 15.2.4
title: Inserting into a Red-Black Tree
pagenum: 579; label: 15.2.5
title: Deletion from a Red-Black Tree
pagenum: 584; label: 15.2.6
title: Implementation Considerations and Complexity
pagenum: 588; label: 15.3
title: Splay Trees
pagenum: 592; label: 15.3.1
title: Introduction
pagenum: 592; label: 15.3.2
title: The Splay Operation
pagenum: 593; label: 15.3.3
title: Amortized Complexity
pagenum: 595; label: 15.4
title: B-Trees
pagenum: 598; label: 15.4.1
title: Indexed Sequential Access Method (ISAM)
pagenum: 598; label: 15.4.2
title: m-Way Search Trees
pagenum: 599; label: 15.4.3
title: B-Trees of Order m
pagenum: 602; label: 15.4.4
title: Height of a B-Tree
pagenum: 603; label: 15.4.5
title: Searching a B-Tree
pagenum: 604; label: 15.4.6
title: Inserting into a B-Tree
pagenum: 604; label: 15.4.7
title: Deletion from a B-Tree
pagenum: 607; label: 15.4.8
title: Node Structure
pagenum: 612; label: 15.5
title: References and Selected Readings
pagenum: 614; label: 16
title: Graphs
pagenum: 615; label: 16.1
title: Definitions
pagenum: 616; label: 16.2
title: Applications and More Definitions
pagenum: 617; label: 16.3
title: Properties
pagenum: 622; label: 16.4
title: The ADT graph
pagenum: 625; label: 16.5
title: Representation of Unweighted Graphs
pagenum: 627; label: 16.5.1
title: Adjacency Matrix
pagenum: 627; label: 16.5.2
title: Linked Adjacency Lists
pagenum: 629; label: 16.5.3
title: Array Adjacency Lists
pagenum: 629; label: 16.6
title: Representation of Weighted Graphs
pagenum: 632; label: 16.7
title: Class Implementations
pagenum: 634; label: 16.7.1
title: The Different Classes
pagenum: 634; label: 16.7.2
title: Adjacency-Matrix Classes
pagenum: 635; label: 16.7.3
title: An Extension to the Class chain
pagenum: 640; label: 16.7.4
title: Linked-List Classes
pagenum: 640; label: 16.8
title: Graph Search Methods
pagenum: 644; label: 16.8.1
title: Breadth-First Search
pagenum: 644; label: 16.8.2
title: Implementation of Breadth-First Search
pagenum: 646; label: 16.8.3
title: Complexity Analysis of graph::bfs
pagenum: 646; label: 16.8.4
title: Depth-First Search
pagenum: 647; label: 16.8.5
title: Implementation of Depth-First Search
pagenum: 650; label: 16.8.6
title: Complexity Analysis of graph::dfs
pagenum: 651; label: 16.9
title: Applications Revisited
pagenum: 652; label: 16.9.1
title: Finding a Path
pagenum: 652; label: 16.9.2
title: Connected Graphs and Components
pagenum: 652; label: 16.9.3
title: Spanning Trees
pagenum: 655; label: Part III
title: Algorithm-Design Methods; label: 17
title: The Greedy Method
pagenum: 660; label: 17.1
title: Optimization Problems
pagenum: 662; label: 17.2
title: The Greedy Method
pagenum: 663; label: 17.3
title: Applications
pagenum: 668; label: 17.3.1
title: Container Loading
pagenum: 668; label: 17.3.2
title: 0/1 Knapsack Problem
pagenum: 669; label: 17.3.3
title: Topological Sorting
pagenum: 673; label: 17.3.4
title: Bipartite Cover
pagenum: 678; label: 17.3.5
title: Single-Source Shortest Paths
pagenum: 682; label: 17.3.6
title: Minimum-Cost Spanning Trees
pagenum: 687; label: 17.4
title: References and Selected Readings
pagenum: 703; label: 18
title: Divide and Conquer
pagenum: 704; label: 18.1
title: The Method
pagenum: 705; label: 18.2
title: Applications
pagenum: 715; label: 18.2.1
title: Defective Chessboard
pagenum: 715; label: 18.2.2
title: Merge Sort
pagenum: 719; label: 18.2.3
title: Quick Sort
pagenum: 726; label: 18.2.4
title: Selection
pagenum: 733; label: 18.2.5
title: Closest Pair of Points
pagenum: 737; label: 18.3
title: Solving Recurrence Equations
pagenum: 749; label: 18.4
title: Lower Bounds on Complexity
pagenum: 751; label: 18.4.1
title: Lower Bound for the Minmax Problem
pagenum: 752; label: 18.4.2
title: Lower Bound for Sorting
pagenum: 754; label: 19
title: Dynamic Programming
pagenum: 757; label: 19.1
title: The Method
pagenum: 758; label: 19.2
title: Applications
pagenum: 761; label: 19.2.1
title: 0/1 Knapsack Problem
pagenum: 761; label: 19.2.2
title: Matrix Multiplication Chains
pagenum: 766; label: 19.2.3
title: All-Pairs Shortest Paths
pagenum: 773; label: 19.2.4
title: Single-Source Shortest Paths with Negative Costs
pagenum: 776; label: 19.2.5
title: Noncrossing Subset of Nets
pagenum: 784; label: 19.3
title: References and Selected Readings
pagenum: 792; label: 20
title: Backtracking (On the Web)
pagenum: 793; label: 20.1
title: The Method
pagenum: 795; label: 20.2
title: Applications
pagenum: 802; label: 20.2.1
title: Container Loading
pagenum: 802; label: 20.2.2
title: 0/1 Knapsack Problem
pagenum: 809; label: 20.2.3
title: Max Clique
pagenum: 812; label: 20.2.4
title: Traveling Salesperson
pagenum: 817; label: 20.2.5
title: Board Permutation
pagenum: 821; label: 21
title: Branch and Bound (On the Web)
pagenum: 829; label: 21.1
title: The Method
pagenum: 830; label: 21.2
title: Applications
pagenum: 834; label: 21.2.1
title: Container Loading
pagenum: 834; label: 21.2.2
title: 0/1 Knapsack Problem
pagenum: 842; label: 21.2.3
title: Max Clique
pagenum: 844; label: 21.2.4
title: Traveling Salesperson
pagenum: 848; label: 21.2.5
title: Board Permutation
pagenum: 853; title: Index
pagenum: I-1