Data structures
Subtitle: a pseudocode approach with C++
By: Richard F. Gilberg, Behrouz A. Forouzan
Contributors: Forouzan, Behrouz A
Publisher: Brooks/Cole
Published: 2001
Place of publication: Pacific Grove, CA
Language: eng
Number of pages: 754
Subjects: C++ (Computer program language); Data structures (Computer science)
Notes: Includes index
Table of contents: label: 1
title: Introduction
pagenum: 1; label: 1-1
title: Pseudocode
pagenum: 2; title: Algorithm Header
pagenum: 2; title: Purpose, Conditions, and Return
pagenum: 3; title: Statement Numbers
pagenum: 4; title: Variables
pagenum: 4; title: Algorithm Analysis
pagenum: 5; title: Statement Constructs
pagenum: 5; title: Pseudocode Example
pagenum: 6; label: 1-2
title: The Abstract Data Type
pagenum: 7; title: Atomic and Composite Data
pagenum: 8; title: Data Structure
pagenum: 8; title: Abstract Data Type
pagenum: 9; label: 1-3
title: A Model for an Abstract Data Type
pagenum: 11; title: ADT Operations
pagenum: 11; title: ADT Data Structure
pagenum: 12; title: ADT Class Templates
pagenum: 13; label: 1-4
title: Algorithm Efficiency
pagenum: 14; title: Linear Loops
pagenum: 15; title: Logarithmic Loops
pagenum: 16; title: Nested Loops
pagenum: 17; title: Big-O Notation
pagenum: 19; title: Standard Measures of Efficiency
pagenum: 20; title: Big-O Analysis Examples
pagenum: 21; label: 1-5
title: Summary
pagenum: 24; label: 1-6
title: Practice Sets
pagenum: 25; title: Exercises
pagenum: 25; title: Problems
pagenum: 27; title: Projects
pagenum: 27; label: 2
title: Searching
pagenum: 29; label: 2-1
title: List Searches
pagenum: 30; title: Sequential Search
pagenum: 30; title: Variations on Sequential Searches
pagenum: 33; title: Binary Search
pagenum: 37; title: Binary Search Algorithm
pagenum: 40; title: Analyzing Search Algorithms
pagenum: 41; label: 2-2
title: C++ Search Algorithms
pagenum: 43; title: Sequential Search in C++
pagenum: 43; title: Binary Search in C++
pagenum: 44; title: Search Example
pagenum: 46; label: 2-3
title: Hashed List Searches
pagenum: 49; title: Basic Concepts
pagenum: 50; title: Hashing Methods
pagenum: 52; title: Hashing Algorithm
pagenum: 57; label: 2-4
title: Collision Resolution
pagenum: 59; title: Open Addressing
pagenum: 61; title: Linked List Resolution
pagenum: 65; title: Bucket Hashing
pagenum: 66; title: Combination Approaches
pagenum: 67; title: Hash List Example
pagenum: 68; label: 2-5
title: Summary
pagenum: 72; label: 2-6
title: Practice Sets
pagenum: 74; title: Exercises
pagenum: 74; title: Problems
pagenum: 75; title: Projects
pagenum: 75; label: 3
title: Linked Lists
pagenum: 77; label: 3-1
title: Linear List Concepts
pagenum: 78; title: Insertion
pagenum: 79; title: Deletion
pagenum: 80; title: Retrieval
pagenum: 80; title: Traversal
pagenum: 80; label: 3-2
title: Linked List Concepts
pagenum: 81; title: Nodes
pagenum: 81; title: Linked List Data Structure
pagenum: 82; title: Pointers to Linked Lists
pagenum: 84; label: 3-3
title: Linked List Algorithms
pagenum: 84; title: Create List
pagenum: 84; title: Insert Node
pagenum: 85; title: Delete Node
pagenum: 90; title: Search List
pagenum: 93; title: Unordered List Search
pagenum: 96; title: Retrieve Node
pagenum: 97; title: Empty List
pagenum: 97; title: Full List
pagenum: 98; title: List Count
pagenum: 98; title: Traverse List
pagenum: 99; title: Destroy List
pagenum: 101; label: 3-4
title: Processing a Linked List
pagenum: 102; title: Add Node
pagenum: 104; title: Remove Node
pagenum: 105; title: Print List
pagenum: 106; title: Testing Insert and Delete Logic
pagenum: 107; label: 3-5
title: List Applications
pagenum: 108; title: Append Lists
pagenum: 108; title: Array of Lists
pagenum: 110; label: 3-6
title: Complex Linked List Structures
pagenum: 113; title: Circularly Linked Lists
pagenum: 113; title: Doubly Linked Lists
pagenum: 113; title: Multilinked Lists
pagenum: 119; title: Multilinked List Insert
pagenum: 121; title: Multilinked List Delete
pagenum: 122; label: 3-7
title: Building a Linked List — C++ Implementation
pagenum: 122; title: Data Structure
pagenum: 122; title: Application Functions
pagenum: 123; label: 3-8
title: List Abstract Data Type — Linked List Implementation
pagenum: 129; title: List ADT Declaration
pagenum: 131; label: 3-9
title: Summary
pagenum: 143; label: 3-10
title: Practice Sets
pagenum: 144; title: Exercises
pagenum: 144; title: Problems
pagenum: 147; title: Projects
pagenum: 148; label: 4
title: Stacks
pagenum: 156; label: 4-1
title: Basic Stack Operations
pagenum: 157; title: Push
pagenum: 157; title: Pop
pagenum: 157; title: Stack Top
pagenum: 158; label: 4-2
title: Stack Linked List Implementation
pagenum: 160; title: Data Structure
pagenum: 160; title: Stack Algorithms
pagenum: 161; label: 4-3
title: Stack Applications
pagenum: 168; title: Reversing Data
pagenum: 169; title: Reverse a List
pagenum: 169; title: Convert Decimal to Binary
pagenum: 170; title: Parsing
pagenum: 171; title: Postponement
pagenum: 173; title: Backtracking
pagenum: 181; label: 4-4
title: Eight Queens Problem — C++ Implementation
pagenum: 188; title: Main Line Logic
pagenum: 189; title: Get Board Size
pagenum: 190; label: 4-5
title: Stack Abstract Data Type — Implementation
pagenum: 195; title: Data Structure
pagenum: 195; title: Stack ADT Implementation
pagenum: 196; label: 4-6
title: Stack ADT — Array Implementation
pagenum: 202; title: Array Data Structure
pagenum: 203; title: Create Stack Array
pagenum: 204; title: Push Stack Array
pagenum: 205; title: Pop Stack Array
pagenum: 206; title: Stack Top Array
pagenum: 207; title: Empty Stack Array
pagenum: 208; title: Full Stack Array
pagenum: 208; title: Stack Count Array
pagenum: 208; title: Destroy Stack Array
pagenum: 209; label: 4-7
title: Summary
pagenum: 209; label: 4-8
title: Practice Sets
pagenum: 210; title: Exercises
pagenum: 210; title: Problems
pagenum: 211; title: Projects
pagenum: 213; label: 5
title: Queues
pagenum: 217; label: 5-1
title: Queue Operations
pagenum: 218; title: Enqueue
pagenum: 218; title: Dequeue
pagenum: 218; title: Queue Front
pagenum: 219; title: Queue Rear
pagenum: 220; title: Queue Example
pagenum: 220; label: 5-2
title: Queue Linked List Design
pagenum: 220; title: Data Structure
pagenum: 220; title: Queue Algorithms
pagenum: 222; title: Create Queue
pagenum: 224; title: Enqueue
pagenum: 224; title: Dequeue
pagenum: 225; title: Retrieving Queue Data
pagenum: 227; title: Empty Queue
pagenum: 228; title: Full Queue
pagenum: 228; title: Queue Count
pagenum: 228; title: Destroy Queue
pagenum: 229; label: 5-3
title: Queuing Theory
pagenum: 229; label: 5-4
title: Queue Applications
pagenum: 231; title: Queue Simulation
pagenum: 231; title: Categorizing Data
pagenum: 239; label: 5-5
title: Categorizing Data — C++
pagenum: 241; title: Implementation
pagenum: 241; title: Main Line Logic
pagenum: 241; title: Fill Queues
pagenum: 242; title: Print Queues
pagenum: 244; title: Print One Queue
pagenum: 244; label: 5-6
title: Queue ADT — Linked List Implementation
pagenum: 246; title: Queue Structure
pagenum: 246; title: Queue ADT Implementation
pagenum: 247; label: 5-7
title: Queue ADT — Array Implementation
pagenum: 253; title: Array Queues Implementation
pagenum: 254; label: 5-8
title: Summary
pagenum: 261; label: 5-9
title: Practice Sets
pagenum: 262; title: Exercises
pagenum: 262; title: Problems
pagenum: 265; title: Projects
pagenum: 266; label: 6
title: Recursion
pagenum: 271; label: 6-1
title: Factorial — A Case Study
pagenum: 272; title: Recursion Defined
pagenum: 272; title: Iterative Solution
pagenum: 273; title: Recursive Solution
pagenum: 273; label: 6-2
title: How Recursion Works
pagenum: 275; label: 6-3
title: Designing Recursive Algorithms
pagenum: 277; title: The Design Methodology
pagenum: 278; title: Limitations of Recursion
pagenum: 279; title: Design Implementation — Reverse a Linked List
pagenum: 279; label: 6-4
title: Another Case Study — Fibonacci Numbers
pagenum: 281; label: 6-5
title: The Towers of Hanoi
pagenum: 285; title: Recursive Towers of Hanoi
pagenum: 286; label: 6-6
title: C++ Implementations of Recursion
pagenum: 290; title: Fibonacci Numbers
pagenum: 290; title: Prefix to Postfix Conversion
pagenum: 291; title: Towers of Hanoi
pagenum: 297; label: 6-7
title: Summary
pagenum: 299; label: 6-8
title: Practice Sets
pagenum: 300; title: Exercises
pagenum: 300; title: Problems
pagenum: 302; title: Projects
pagenum: 303; label: 7
title: Introduction to Trees
pagenum: 305; label: 7-1
title: Basic Tree Concepts
pagenum: 306; title: Terminology
pagenum: 306; title: Tree Representation
pagenum: 308; label: 7-2
title: Binary Trees
pagenum: 310; title: Properties
pagenum: 312; label: 7-3
title: Binary Tree Traversals
pagenum: 313; title: Depth-First Traversals
pagenum: 314; title: Breadth-First Traversals
pagenum: 320; label: 7-4
title: Expression Trees
pagenum: 322; title: Infix Traversal
pagenum: 322; title: Postfix Traversal
pagenum: 324; title: Prefix Traversal
pagenum: 324; label: 7-5
title: General Trees
pagenum: 324; title: Changing General Tree to Binary Tree
pagenum: 325; title: Insertions into General Trees
pagenum: 326; title: General Tree Deletions
pagenum: 327; label: 7-6
title: Huffman Code
pagenum: 327; label: 7-7
title: Summary
pagenum: 332; label: 7-8
title: Practice Sets
pagenum: 333; title: Exercises
pagenum: 333; title: Problems
pagenum: 337; title: Projects
pagenum: 337; label: 8
title: Search Trees
pagenum: 338; label: 8-1
title: Binary Search Trees
pagenum: 339; title: Definition
pagenum: 339; title: Operations on Binary Search Trees
pagenum: 341; title: Binary Search Tree Search Algorithms
pagenum: 342; label: 8-2
title: AVL Trees
pagenum: 353; title: AVL Balance Factor
pagenum: 354; title: Balancing Trees
pagenum: 355; title: AVL Node Structure
pagenum: 360; title: AVL Delete Algorithm
pagenum: 367; title: Adjusting the Balance Factors
pagenum: 372; label: 8-3
title: AVL Tree Implementation
pagenum: 372; title: Data Structure
pagenum: 372; title: Program Design
pagenum: 373; title: Count Words; title: Summary
pagenum: 377; label: 8-4
title: AVL Abstract Data Type
pagenum: 378; title: AVL Tree Data Structures
pagenum: 379; title: AVL Tree Functions
pagenum: 380; title: AVL Tree Data Processing
pagenum: 392; title: AVL Tree Utility Functions
pagenum: 395; label: 8-5
title: Summary
pagenum: 398; label: 8-6
title: Practice Sets
pagenum: 399; title: Exercises
pagenum: 399; title: Problems
pagenum: 403; title: Projects
pagenum: 403; label: 9
title: Heaps
pagenum: 406; label: 9-1
title: Heap Definition
pagenum: 407; label: 9-2
title: Heap Structure
pagenum: 407; label: 9-3
title: Basic Heap Algorithms
pagenum: 408; title: ReheapUp
pagenum: 409; title: ReheapDown
pagenum: 411; label: 9-4
title: Heap Data Structure
pagenum: 412; label: 9-5
title: Heap Algorithms
pagenum: 414; title: ReheapUp
pagenum: 414; title: ReheapDown
pagenum: 415; title: BuildHeap
pagenum: 416; title: InsertHeap
pagenum: 418; title: DeleteHeap
pagenum: 419; label: 9-6
title: Heap Applications
pagenum: 421; title: Selection Algorithms
pagenum: 421; title: Priority Queues
pagenum: 423; label: 9-7
title: A Heap Program
pagenum: 424; title: Heap Program Design
pagenum: 425; title: Heap Functions
pagenum: 430; label: 9-8
title: Summary
pagenum: 433; label: 9-9
title: Practice Sets
pagenum: 434; title: Exercises
pagenum: 436; title: Problems
pagenum: 436; title: Projects
pagenum: 436; label: 10
title: Multiway Trees
pagenum: 439; label: 10-1
title: m-Way Search Trees
pagenum: 440; label: 10-2
title: B-Trees
pagenum: 442; title: B-Tree Insertion
pagenum: 443; title: B-Tree Insert Design
pagenum: 444; title: B-Tree Insert Node
pagenum: 446; title: B-Tree Deletion
pagenum: 454; title: Traverse B-Tree
pagenum: 467; title: B-Tree Search
pagenum: 470; label: 10-3
title: Simplified B-Trees
pagenum: 471; title: 2-3 Tree
pagenum: 471; title: 2-3-4 Tree
pagenum: 472; label: 10-4
title: B-Tree Variations
pagenum: 472; title: B*Tree
pagenum: 473; title: B+Tree
pagenum: 474; label: 10-5
title: Lexical Search Tree
pagenum: 474; title: Tries
pagenum: 475; title: Trie Structure
pagenum: 476; label: 10-6
title: B-Tree Abstract Data Type
pagenum: 478; title: Header File
pagenum: 479; title: Utility Functions
pagenum: 481; title: Insert Algorithms
pagenum: 485; title: Delete Algoirthms
pagenum: 491; label: 10-7
title: Summary
pagenum: 499; label: 10-8
title: Practice Sets
pagenum: 499; title: Exercises
pagenum: 499; title: Problems
pagenum: 500; title: Projects
pagenum: 501; label: 11
title: Advanced Sorting Concepts
pagenum: 502; label: 11-1
title: General Sort Concepts
pagenum: 503; title: Sort Order
pagenum: 503; title: Sort Stability
pagenum: 504; title: Sort Efficiency
pagenum: 504; title: Passes
pagenum: 505; label: 11-2
title: Insertion Sorts
pagenum: 505; title: Straight Insertion Sort
pagenum: 505; title: Shell Sort
pagenum: 508; title: Insertion Sort Algorithms
pagenum: 513; title: Insertion Sort Implementation
pagenum: 515; label: 11-3
title: Selection Sorts
pagenum: 517; title: Straight Selection Sort
pagenum: 517; title: Selection Sort Algorithms
pagenum: 522; title: Selection Sort Implementation
pagenum: 524; label: 11-4
title: Exchange Sorts
pagenum: 526; title: Bubble Sort
pagenum: 526; title: Bubble Sort Algorithm
pagenum: 527; title: Quick Sort
pagenum: 529; title: Exchange Sort Algorithms
pagenum: 536; label: 11-5
title: Summary
pagenum: 538; label: 11-6
title: External Sorts
pagenum: 542; title: Merging Ordered Files
pagenum: 543; title: Merging Unordered Files
pagenum: 544; title: The Sorting Process
pagenum: 546; title: Sort Phase Revisited
pagenum: 551; label: 11-7
title: Summary
pagenum: 553; label: 11-8
title: Practice Sets
pagenum: 554; title: Exercises
pagenum: 554; title: Problems
pagenum: 556; title: Projects
pagenum: 556; label: 12
title: Graphs
pagenum: 560; label: 12-1
title: Terminology
pagenum: 561; label: 12-2
title: Operations
pagenum: 563; title: Add Vertex
pagenum: 563; title: Delete Vertex
pagenum: 563; title: Add Edge
pagenum: 563; title: Delete Edge
pagenum: 564; title: Find Vertex
pagenum: 564; title: Traverse Graph
pagenum: 564; label: 12-3
title: Graph Storage Structures
pagenum: 568; title: Adjacency Matrix
pagenum: 568; title: Adjacency List
pagenum: 569; label: 12-4
title: Graph Algorithms
pagenum: 570; title: Create Graph
pagenum: 571; title: Insert Vertex
pagenum: 572; title: Delete Vertex
pagenum: 573; title: Insert Arc
pagenum: 575; title: Delete Arc
pagenum: 577; title: Retrieve Vertex
pagenum: 578; title: First Arc
pagenum: 579; title: Depth-First Traversal
pagenum: 581; title: Breadth-First Traversal
pagenum: 583; label: 12-5
title: Networks
pagenum: 585; title: Minimum Spanning Tree
pagenum: 585; title: Shortest Path Algorithm
pagenum: 591; label: 12-6
title: Abstract Data Type
pagenum: 596; title: Insert Vertex
pagenum: 598; title: Delete Vertex
pagenum: 599; title: Insert Arc
pagenum: 600; title: Delete Arc
pagenum: 602; title: Depth-First Traversal
pagenum: 604; title: Breadth-First Traversal
pagenum: 605; label: 12-7
title: Summary
pagenum: 607; label: 12-8
title: Practice Sets
pagenum: 608; title: Exercises
pagenum: 608; title: Problems
pagenum: 610; title: Projects
pagenum: 611; title: Appendixes; label: A
title: ASCII Tables
pagenum: 615; label: B
title: Structure Charts
pagenum: 620; label: C
title: Program Standards and Styles
pagenum: 627; label: D
title: Random Numbers
pagenum: 633; label: E
title: Standard C++ Libraries
pagenum: 639; label: F
title: C++ Function Prototypes
pagenum: 641; label: G
title: Classes Related to Input and Output
pagenum: 650; label: H
title: The String Class
pagenum: 655; label: I
title: Pointers to Functions
pagenum: 666; label: J
title: Inheritance
pagenum: 670; label: K
title: C++ Templates
pagenum: 685; label: L
title: Standard Template Library
pagenum: 692; title: Solutions to Selected Exercises
pagenum: 712; title: Glossary
pagenum: 735; title: Index
pagenum: 747