Fundamentals of data structures in C++
By: Ellis Horowitz, Sartaj Sahni, Dinesh Mehta.
Contributors: Sahni, Sartaj.; Mehta, Dinesh P.
Publisher: Computer Science Press
Published: 1995
Place of publication: New York
Language: eng
Number of pages: 653
Subjects: C++ (Computer program language); Data structures (Computer science)
Other titles: Data structures C++
Notes: Includes bibliographical references and index.
Table of contents: title: Preface
pagenum: xv; label: Chapter 1
title: Basic Concepts
pagenum: 1; label: 1.1
title: Overview: System Life Cycle
pagenum: 1; label: 1.2
title: Object-Oriented Design
pagenum: 4; label: 1.2.1
title: Algorithmic Decomposition versus OO Decomposition
pagenum: 4; label: 1.2.2
title: Fundamental Definitions and Concepts of OO Programming
pagenum: 5; label: 1.2.3
title: Evolution of Programming Languages and History of C++
pagenum: 5; label: 1.3
title: Data Abstraction and Encapsulation
pagenum: 6; label: 1.4
title: Basics of C++
pagenum: 11; label: 1.4.1
title: Program Organization in C++
pagenum: 11; label: 1.4.2
title: Scope in C++
pagenum: 12; label: 1.4.3
title: C++ Statements and Operators
pagenum: 13; label: 1.4.4
title: Data Declarations in C++
pagenum: 14; label: 1.4.5
title: Comments in C++
pagenum: 15; label: 1.4.6
title: Input/Output in C++
pagenum: 15; label: 1.4.7
title: Functions in C++
pagenum: 17; label: 1.4.8
title: Parameter Passing in C++
pagenum: 18; label: 1.4.9
title: Function Name Overloading in C++
pagenum: 19; label: 1.4.10
title: Inline Functions
pagenum: 19; label: 1.4.11
title: Dynamic Memory Allocation in C++
pagenum: 20; label: 1.5
title: Algorithm Specification
pagenum: 20; label: 1.5.1
title: Introduction
pagenum: 20; label: 1.5.2
title: Recursive Algorithms
pagenum: 25; label: 1.6
title: Performance Analysis And Measurement
pagenum: 30; label: 1.6.1
title: Performance Analysis
pagenum: 30; label: 1.6.2
title: Performance Measurement
pagenum: 51; label: 1.6.3
title: Generating Test Data
pagenum: 60; label: 1.7
title: References And Selected Readings
pagenum: 64; label: Chapter 2
title: Arrays
pagenum: 66; label: 2.1
title: Abstract Data Types and the C++ Class
pagenum: 66; label: 2.1.1
title: An Introduction to the C++ Class
pagenum: 66; label: 2.1.2
title: Data Abstraction and Encapsulation in C++
pagenum: 67; label: 2.1.3
title: Declaring Class Objects and Invoking Member Functions
pagenum: 68; label: 2.1.4
title: Special Class Operations
pagenum: 68; label: 2.1.5
title: Miscellaneous Topics
pagenum: 73; label: 2.1.6
title: ADTs and C++ Classes
pagenum: 73; label: 2.2
title: The Array as an Abstract Data Type
pagenum: 75; label: 2.3
title: The Polynomial Abstract Data Type
pagenum: 77; label: 2.3.1
title: Polynomial Representation
pagenum: 80; label: 2.3.2
title: Polynomial Addition
pagenum: 82; label: 2.3.3
title: Disadvantages of Representing Polynomials by Arrays
pagenum: 84; label: 2.4
title: Sparse Matrices
pagenum: 87; label: 2.4.1
title: Introduction
pagenum: 87; label: 2.4.2
title: Sparse Matrix Representation
pagenum: 88; label: 2.4.3
title: Transposing a Matrix
pagenum: 89; label: 2.4.4
title: Matrix Multiplication
pagenum: 93; label: 2.4.5
title: Disadvantages of Representing Sparse Matrices by Arrays
pagenum: 98; label: 2.5
title: Representation of Arrays
pagenum: 100; label: 2.6
title: The String Abstract Data Type
pagenum: 104; label: 2.6.1
title: String Pattern Matching: A Simple Algorithm
pagenum: 105; label: 2.6.2
title: String Pattern Matching: The KMP Algorithm
pagenum: 106; label: 2.7
title: References and Selected Readings
pagenum: 111; label: 2.8
title: Additional Exercises
pagenum: 111; label: Chapter 3
title: Stacks and Queues
pagenum: 119; label: 3.1
title: Templates in C++
pagenum: 119; label: 3.1.1
title: Template Functions
pagenum: 119; label: 3.1.2
title: Using Templates to Represent Container Classes
pagenum: 121; label: 3.2
title: The Stack Abstract Data Type
pagenum: 124; label: 3.3
title: The Queue Abstract Data Type
pagenum: 131; label: 3.4
title: Subtyping and Inheritance in C++
pagenum: 137; label: 3.5
title: A Mazing Problem
pagenum: 140; label: 3.6
title: Evaluation of Expressions
pagenum: 147; label: 3.6.1
title: Expressions
pagenum: 147; label: 3.6.2
title: Postfix Notation
pagenum: 148; label: 3.6.3
title: Infix to Postfix
pagenum: 150; label: 3.7
title: Multiple Stacks And Queues
pagenum: 154; label: 3.8
title: Selected Readings And References
pagenum: 158; label: 3.9
title: Additional Exercises
pagenum: 158; label: Chapter 4
title: Linked Lists
pagenum: 161; label: 4.1
title: Singly Linked Lists
pagenum: 161; label: 4.2
title: Representing Lists in C++
pagenum: 165; label: 4.2.1
title: Defining a List Node in C++
pagenum: 165; label: 4.2.2
title: Designing a List in C++
pagenum: 166; label: 4.2.3
title: Pointer Manipulation in C++
pagenum: 170; label: 4.2.4
title: List Manipulation Operations
pagenum: 171; label: 4.3
title: A Reusable Linked List Class
pagenum: 174; label: 4.3.1
title: Implementing Linked Lists with Templates
pagenum: 175; label: 4.3.2
title: Linked List Iterators
pagenum: 176; label: 4.3.3
title: Linked List Operations
pagenum: 179; label: 4.3.4
title: Reusing a Class
pagenum: 182; label: 4.4
title: Circular Lists
pagenum: 183; label: 4.5
title: Linked Stacks and Queues
pagenum: 186; label: 4.6
title: Polynomials
pagenum: 190; label: 4.6.1
title: Polynomial Representation
pagenum: 190; label: 4.6.2
title: Adding Polynomials
pagenum: 190; label: 4.6.3
title: Erasing Polynomials
pagenum: 194; label: 4.6.4
title: Circular List Representation of Polynomials
pagenum: 195; label: 4.6.5
title: Summary
pagenum: 199; label: 4.7
title: Equivalence Classes
pagenum: 202; label: 4.8
title: Sparse Matrices
pagenum: 207; label: 4.8.1
title: Sparse Matrix Representation
pagenum: 207; label: 4.8.2
title: Sparse Matrix Input
pagenum: 209; label: 4.8.3
title: Erasing a Sparse Matrix
pagenum: 213; label: 4.9
title: Doubly Linked Lists
pagenum: 217; label: 4.10
title: Generalized Lists
pagenum: 221; label: 4.10.1
title: Representation of Generalized Lists
pagenum: 221; label: 4.10.2
title: Recursive Algorithms for Lists
pagenum: 225; label: 4.10.3
title: Reference Counts, Shared and Recursive Lists
pagenum: 230; label: 4.11
title: Virtual Functions and Dynamic Binding in C++
pagenum: 237; label: 4.12
title: Heterogeneous Lists
pagenum: 241; label: 4.13
title: References and Selected Readings
pagenum: 245; label: Chapter 5
title: Trees
pagenum: 246; label: 5.1
title: Introduction
pagenum: 246; label: 5.1.1
title: Terminology
pagenum: 246; label: 5.1.2
title: Representation of Trees
pagenum: 249; label: 5.2
title: Binary Trees
pagenum: 252; label: 5.2.1
title: The Abstract Data Type
pagenum: 252; label: 5.2.2
title: Properties of Binary Trees
pagenum: 255; label: 5.2.3
title: Binary Tree Representations
pagenum: 257; label: 5.3
title: Binary Tree Traversal and Tree Iterators
pagenum: 261; label: 5.3.1
title: Introduction
pagenum: 261; label: 5.3.2
title: Inorder Traversal
pagenum: 262; label: 5.3.3
title: Preorder Traversal
pagenum: 263; label: 5.3.4
title: Postorder Traversal
pagenum: 263; label: 5.3.5
title: Iterative Inorder Traversal
pagenum: 265; label: 5.3.6
title: Level-Order Traversal
pagenum: 268; label: 5.3.7
title: Traversal Without a Stack
pagenum: 269; label: 5.4
title: Additional Binary Tree Operations
pagenum: 27; label: 5.4.1
title: Copying Binary Trees
pagenum: 271; label: 5.4.2
title: Testing Equality
pagenum: 271; label: 5.4.3
title: The Satisfiability Problem
pagenum: 272; label: 5.5
title: Threaded Binary Trees
pagenum: 277; label: 5.5.1
title: Threads
pagenum: 277; label: 5.5.2
title: Inorder Traversal of a Threaded Binary Tree
pagenum: 278; label: 5.5.3
title: Inserting a Node into a Threaded Binary Tree
pagenum: 281; label: 5.6
title: Heaps
pagenum: 283; label: 5.6.1
title: Priority Queues
pagenum: 283; label: 5.6.2
title: Definition of a Max Heap
pagenum: 285; label: 5.6.3
title: Insertion into a Max Heap
pagenum: 286; label: 5.6.4
title: Deletion from a Max Heap
pagenum: 288; label: 5.7
title: Binary Search Trees
pagenum: 291; label: 5.7.1
title: Definition
pagenum: 291; label: 5.7.2
title: Searching a Binary Search Tree
pagenum: 292; label: 5.7.3
title: Insertion into a Binary Search Tree
pagenum: 293; label: 5.7.4
title: Deletion from a Binary Search Tree
pagenum: 294; label: 5.7.5
title: Joining and Splitting Binary Search Trees
pagenum: 295; label: 5.7.6
title: Height of a Binary Search Tree
pagenum: 298; label: 5.8
title: Selection Trees
pagenum: 300; label: 5.8.1
title: Introduction
pagenum: 300; label: 5.8.2
title: Winner Trees
pagenum: 300; label: 5.8.3
title: Loser Trees
pagenum: 301; label: 5.9
title: Forests
pagenum: 304; label: 5.9.1
title: Transforming a Forest into a Binary Search Tree
pagenum: 304; label: 5.9.2
title: Forest Traversals
pagenum: 305; label: 5.10
title: Set Representation
pagenum: 307; label: 5.10.1
title: Introduction
pagenum: 307; label: 5.10.2
title: Union and Find Operations
pagenum: 307; label: 5.10.3
title: Application to Equivalence Classes
pagenum: 316; label: 5.11
title: An Object-Oriented System of Tree Data Structures
pagenum: 319; label: 5.12
title: Counting Binary Trees
pagenum: 321; label: 5.12.1
title: Distinct Binary Trees
pagenum: 322; label: 5.12.2
title: Stack Permutations
pagenum: 323; label: 5.12.3
title: Matrix Multiplication
pagenum: 326; label: 5.12.4
title: Number of Distinct Binary Trees
pagenum: 327; label: 5.13
title: References and Selected Readings
pagenum: 328; label: Chapter 6
title: Graphs
pagenum: 330; label: 6.1
title: The Graph Abstract Data Type
pagenum: 330; label: 6.1.1
title: Introduction
pagenum: 330; label: 6.1.2
title: Definitions
pagenum: 332; label: 6.1.3
title: Graph Representations
pagenum: 336; label: 6.2
title: Elementary Graph Operations
pagenum: 345; label: 6.2.1
title: Depth First Search
pagenum: 345; label: 6.2.2
title: Breadth First Search
pagenum: 347; label: 6.2.3
title: Connected Components
pagenum: 348; label: 6.2.4
title: Spanning Trees
pagenum: 348; label: 6.2.5
title: Biconnected Components
pagenum: 350; label: 6.3
title: Minimum Cost Spanning Trees
pagenum: 356; label: 6.3.1
title: Kruskal's Algorithm
pagenum: 357; label: 6.3.2
title: Prim's Algorithm
pagenum: 361; label: 6.3.3
title: Sollin's Algorithm
pagenum: 361; label: 6.4
title: Shortest Paths and Transitive Closure
pagenum: 364; label: 6.4.1
title: Single Source/All Destination: Nonnegative Edge Costs
pagenum: 364; label: 6.4.2
title: Single Source/All Destination: General Weights
pagenum: 367; label: 6.4.3
title: All-Pairs Shortest Paths
pagenum: 371; label: 6.4.4
title: Transitive Closure
pagenum: 373; label: 6.5
title: Activity Networks
pagenum: 378; label: 6.5.1
title: Activity on Vertex (AOV) Networks
pagenum: 378; label: 6.5.2
title: Activity on Edge (AOE) Networks
pagenum: 383; label: 6.6
title: References and Selected Readings
pagenum: 393; label: 6.7
title: Additional Exercises
pagenum: 394; label: Chapter 7
title: Sorting
pagenum: 397; label: 7.1
title: Motivation
pagenum: 397; label: 7.2
title: Insertion Sort
pagenum: 402; label: 7.3
title: Quick Sort
pagenum: 405; label: 7.4
title: How Fast Can We Sort?
pagenum: 408; label: 7.5
title: Merge Sort
pagenum: 410; label: 7.5.1
title: Merging
pagenum: 410; label: 7.5.2
title: Iterative Merge Sort
pagenum: 416; label: 7.5.3
title: Recursive Merge Sort
pagenum: 418; label: 7.6
title: Heap Sort
pagenum: 423; label: 7.7
title: Sorting on Several Keys
pagenum: 425; label: 7.8
title: List and Table Sorts
pagenum: 431; label: 7.9
title: Summary of Internal Sorting
pagenum: 439; label: 7.10
title: External Sorting
pagenum: 445; label: 7.10.1
title: Introduction
pagenum: 445; label: 7.10.2
title: k-way Merging
pagenum: 448; label: 7.10.3
title: Buffer Handling for Parallel Operation
pagenum: 450; label: 7.10.4
title: Run Generation
pagenum: 456; label: 7.10.5
title: Optimal Merging of Runs
pagenum: 458; label: 7.11
title: References and Selected Readings
pagenum: 463; label: Chapter 8
title: Hashing
pagenum: 464; label: 8.1
title: The Symbol Table Abstract Data Type
pagenum: 464; label: 8.2
title: Static Hashing
pagenum: 466; label: 8.2.1
title: Hash Tables
pagenum: 466; label: 8.2.2
title: Hashing Functions
pagenum: 468; label: 8.2.3
title: Overflow Handling
pagenum: 471; label: 8.2.4
title: Theoretical Evaluation of Overflow Techniques
pagenum: 478; label: 8.3
title: Dynamic Hashing
pagenum: 482; label: 8.3.1
title: Motivation for Dynamic Hashing
pagenum: 482; label: 8.3.2
title: Dynamic Hashing using Directories
pagenum: 483; label: 8.3.3
title: Analysis of Directory-Based Dynamic Hashing
pagenum: 489; label: 8.3.4
title: Directoryless Dynamic Hashing
pagenum: 491; label: 8.4
title: References and Selected Readings
pagenum: 496; label: Chapter 9
title: Heap Structures
pagenum: 497; label: 9.1
title: Min-Max Heaps
pagenum: 497; label: 9.1.1
title: Definitions
pagenum: 497; label: 9.1.2
title: Insertion into a Min-Max Heap
pagenum: 499; label: 9.1.3
title: Deletion of the Min Element
pagenum: 502; label: 9.2
title: Deaps
pagenum: 507; label: 9.2.1
title: Definition
pagenum: 50; label: 9.2.2
title: Insertion into a Deap
pagenum: 508; label: 9.2.3
title: Deletion of the Min Element
pagenum: 511; label: 9.3
title: Leftist Trees
pagenum: 515; label: 9.4
title: Binomial Heaps
pagenum: 522; label: 9.4.1
title: Cost Amortization
pagenum: 522; label: 9.4.2
title: Definition of Binomial Heaps
pagenum: 523; label: 9.4.3
title: Insertion into a Binomial Heap
pagenum: 524; label: 9.4.4
title: Combining Two Binomial Heaps
pagenum: 524; label: 9.4.5
title: Deletion of Min Element
pagenum: 525; label: 9.4.6
title: Analysis
pagenum: 529; label: 9.5
title: Fibonacci Heaps
pagenum: 531; label: 9.5.1
title: Definition
pagenum: 531; label: 9.5.2
title: Deletion from an F-heap
pagenum: 532; label: 9.5.3
title: Decrease Key
pagenum: 532; label: 9.5.4
title: Cascading Cut
pagenum: 533; label: 9.5.5
title: Analysis
pagenum: 534; label: 9.5.6
title: Application to the Shortest Paths Problem
pagenum: 536; label: 9.6
title: References and Selected Readings
pagenum: 539; label: 9.7
title: Additional Exercise
pagenum: 539; label: Chapter 10
title: Search Structures
pagenum: 541; label: 10.1
title: Optimal Binary Search Trees
pagenum: 541; label: 10.2
title: AVL Trees
pagenum: 551; label: 10.3
title: 2-3 Trees
pagenum: 567; label: 10.3.1
title: Definition and Properties
pagenum: 567; label: 10.3.2
title: Searching a 2-3 Tree
pagenum: 569; label: 10.3.3
title: Insertion into a 2-3 Tree
pagenum: 569; label: 10.3.4
title: Deletion from a 2-3 Tree
pagenum: 573; label: 10.4
title: 2-3-4 Trees
pagenum: 580; label: 10.4.1
title: Definition and Properties
pagenum: 580; label: 10.4.2
title: Top-Down Insertion
pagenum: 582; label: 10.4.3
title: Top-Down Deletion
pagenum: 586; label: 10.5
title: Red-Black Trees
pagenum: 589; label: 10.5.1
title: Definition and Properties
pagenum: 589; label: 10.5.2
title: Searching a Red-Black Tree
pagenum: 592; label: 10.5.3
title: Top-Down Insertion
pagenum: 592; label: 10.5.4
title: Bottom-Up Insertion
pagenum: 594; label: 10.5.5
title: Deletion from a Red-Black Tree
pagenum: 598; label: 10.5.6
title: Joining and Splitting Red-Black Trees
pagenum: 598; label: 10.6
title: B-Trees
pagenum: 602; label: 10.6.1
title: Definition of m-way Search Trees
pagenum: 602; label: 10.6.2
title: Searching an m-way Search Tree
pagenum: 603; label: 10.6.3
title: Definition and Properties Of A B-tree
pagenum: 604; label: 10.6.4
title: Insertion into a B-tree
pagenum: 609; label: 10.6.5
title: Deletion from a B-tree
pagenum: 611; label: 10.6.6
title: Variable Size Key Values
pagenum: 614; label: 10.7
title: Splay Trees
pagenum: 618; label: 10.8
title: Digital Search Trees
pagenum: 624; label: 10.8.1
title: Definition
pagenum: 624; label: 10.8.2
title: Binary Tries
pagenum: 625; label: 10.8.3
title: Patricia
pagenum: 627; label: 10.9
title: Tries
pagenum: 630; label: 10.9.1
title: Definition
pagenum: 630; label: 10.9.2
title: Searching a Trie
pagenum: 633; label: 10.9.3
title: Sampling Strategies
pagenum: 635; label: 10.9.4
title: Insertion into a Trie
pagenum: 636; label: 10.9.5
title: Deletion from a Trie
pagenum: 637; label: 10.9.6
title: Node Structure
pagenum: 637; label: 10.10
title: Differential Files
pagenum: 639; label: 10.10.1
title: The Concept
pagenum: 639; label: 10.10.2
title: Bloom Filters
pagenum: 642; label: 10.11
title: References and Selected Readings
pagenum: 644; title: Index
pagenum: 646