Fundamentals of data structures in C
By: Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed.
Contributors: Sahni, Sartaj.; Anderson-Freed, Susan.
Edition: 2nd ed.
Publisher: Silicon Press
Published: 2007
Place of publication: Summit, NJ
Language: eng
Number of pages: 617
ISBN-13: 9780929306407
Subjects: C (Computer program language); Data structures (Computer science)
Table of contents: label: Chapter 1
title: Basic Concepts
pagenum: 1; label: 1.1
title: Overview: System Life Cycle
pagenum: 1; label: 1.2
title: Pointers and Dynamic Memory Allocation
pagenum: 4; label: 1.2.1
title: Pointers
pagenum: 4; label: 1.2.2
title: Dynamic Memory Allocation
pagenum: 5; label: 1.2.3
title: Pointers Can Be Dangerous
pagenum: 7; label: 1.3
title: Algorithm Specification
pagenum: 8; label: 1.3.1
title: Introduction
pagenum: 8; label: 1.3.2
title: Recursive Algorithms
pagenum: 14; label: 1.4
title: Data Abstraction
pagenum: 18; label: 1.5
title: Performance Analysis
pagenum: 22; label: 1.5.1
title: Space Complexity
pagenum: 22; label: 1.5.2
title: Time Complexity
pagenum: 25; label: 1.5.3
title: Asymptotic Notation
pagenum: 33; label: 1.5.4
title: Practical Complexities
pagenum: 41; label: 1.6
title: Performance Measurement
pagenum: 44; label: 1.6.1
title: Clocking
pagenum: 44; label: 1.6.2
title: Generating Test Data
pagenum: 48; label: 1.7
title: References and Selected Readings
pagenum: 50; label: Chapter 2
title: Arrays and Structures
pagenum: 51; label: 2.1
title: Arrays
pagenum: 51; label: 2.1.1
title: The Abstract Data Type
pagenum: 51; label: 2.1.2
title: Arrays in C
pagenum: 52; label: 2.2
title: Dynamically Allocated Arrays
pagenum: 55; label: 2.2.1
title: One-dimensional Arrays
pagenum: 55; label: 2.2.2
title: Two-dimensional Arrays
pagenum: 56; label: 2.3
title: Structures and Unions
pagenum: 59; label: 2.3.1
title: Structures
pagenum: 59; label: 2.3.2
title: Unions
pagenum: 62; label: 2.3.3
title: Internal Representation of Structures
pagenum: 63; label: 2.3.4
title: Self-referential Structures
pagenum: 63; label: 2.4
title: Polynomials
pagenum: 64; label: 2.4.1
title: The Abstract Data Type
pagenum: 64; label: 2.4.2
title: Polynomial Representation
pagenum: 66; label: 2.4.3
title: Polynomial Addition
pagenum: 69; label: 2.5
title: Sparse Matrices
pagenum: 72; label: 2.5.1
title: The Abstract Data Type
pagenum: 72; label: 2.5.2
title: Sparse Matrix Representation
pagenum: 74; label: 2.5.3
title: Transposing a Matrix
pagenum: 76; label: 2.5.4
title: Matrix Multiplication
pagenum: 79; label: 2.6
title: Representation of Multidimensional Arrays
pagenum: 85; label: 2.7
title: Strings
pagenum: 87; label: 2.7.1
title: The Abstract Data Type
pagenum: 87; label: 2.7.2
title: Strings in C
pagenum: 87; label: 2.7.3
title: Pattern Matching
pagenum: 90; label: 2.8
title: References and Selected Readings
pagenum: 98; label: 2.9
title: Additional Exercises
pagenum: 99; label: Chapter 3
title: Stacks and Queues
pagenum: 107; label: 3.1
title: Stacks
pagenum: 107; label: 3.2
title: Stacks Using Dynamic Arrays
pagenum: 112; label: 3.3
title: Queues
pagenum: 114; label: 3.4
title: Circular Queues Using Dynamic Arrays
pagenum: 119; label: 3.5
title: A Mazing Problem
pagenum: 120; label: 3.6
title: Evaluation of Expressions
pagenum: 127; label: 3.6.1
title: Expressions
pagenum: 127; label: 3.6.2
title: Evaluating Postfix Expressions
pagenum: 129; label: 3.6.3
title: Infix to Postfix
pagenum: 132; label: 3.7
title: Multiple Stacks and Queues
pagenum: 139; label: 3.8
title: Additional Exercises
pagenum: 142; label: Chapter 4
title: Linked Lists
pagenum: 145; label: 4.1
title: Singly Linked Lists and Chains
pagenum: 145; label: 4.2
title: Representing Chains in C
pagenum: 149; label: 4.3
title: Linked Stacks and Queues
pagenum: 156; label: 4.4
title: Polynomials
pagenum: 160; label: 4.4.1
title: Polynomial Representation
pagenum: 160; label: 4.4.2
title: Adding Polynomials
pagenum: 161; label: 4.4.3
title: Erasing Polynomials
pagenum: 165; label: 4.4.4
title: Circular List Representation of Polynomials
pagenum: 166; label: 4.4.5
title: Summary
pagenum: 168; label: 4.5
title: Additional List Operations
pagenum: 171; label: 4.5.1
title: Operations for Chains
pagenum: 171; label: 4.5.2
title: Operations for Circularly Linked Lists
pagenum: 172; label: 4.6
title: Equivalence Classes
pagenum: 174; label: 4.7
title: Sparse Matrices
pagenum: 178; label: 4.7.1
title: Sparse Matrix Representation
pagenum: 178; label: 4.7.2
title: Sparse Matrix Input
pagenum: 181; label: 4.7.3
title: Sparse Matrix Output
pagenum: 184; label: 4.7.4
title: Erasing a Sparse Matrix
pagenum: 185; label: 4.8
title: Doubly Linked Lists
pagenum: 186; label: Chapter 5
title: Trees
pagenum: 191; label: 5.1
title: Introduction
pagenum: 191; label: 5.1.1
title: Terminology
pagenum: 191; label: 5.1.2
title: Representation of Trees
pagenum: 194; label: 5.2
title: Binary Trees
pagenum: 197; label: 5.2.1
title: The Abstract Data Type
pagenum: 197; label: 5.2.2
title: Properties of Binary Trees
pagenum: 199; label: 5.2.3
title: Binary Tree Representations
pagenum: 202; label: 5.3
title: Binary Tree Traversals
pagenum: 205; label: 5.3.1
title: Inorder Traversal
pagenum: 206; label: 5.3.2
title: Preorder Traversal
pagenum: 208; label: 5.3.3
title: Postorder Traversal
pagenum: 208; label: 5.3.4
title: Iterative Inorder Traversal
pagenum: 209; label: 5.3.5
title: Level-Order Traversal
pagenum: 209; label: 5.3.6
title: Traversal Without a Stack
pagenum: 210; label: 5.4
title: Additional Binary Tree Operations
pagenum: 212; label: 5.4.1
title: Copying Binary Trees
pagenum: 212; label: 5.4.2
title: Testing Equality
pagenum: 212; label: 5.4.3
title: The Satisfiability Problem
pagenum: 213; label: 5.5
title: Threaded Binary Trees
pagenum: 216; label: 5.5.1
title: Threads
pagenum: 216; label: 5.5.2
title: Inorder Traversal of a Threaded Binary Tree
pagenum: 220; label: 5.5.3
title: Inserting a Node into a Threaded Binary Tree
pagenum: 220; label: 5.6
title: Heaps
pagenum: 222; label: 5.6.1
title: Priority Queues
pagenum: 222; label: 5.6.2
title: Definition of a Max Heap
pagenum: 224; label: 5.6.3
title: Insertion into a Max Heap
pagenum: 225; label: 5.6.4
title: Deletion from a Max Heap
pagenum: 228; label: 5.7
title: Binary Search Trees
pagenum: 231; label: 5.7.1
title: Definition
pagenum: 231; label: 5.7.2
title: Searching a Binary Search Tree
pagenum: 232; label: 5.7.3
title: Insertion into a Binary Search Tree
pagenum: 234; label: 5.7.4
title: Deletion from a Binary Search Tree
pagenum: 235; label: 5.7.5
title: Joining and Splitting Binary Search Trees
pagenum: 236; label: 5.7.6
title: Height of a Binary Search Tree
pagenum: 237; label: 5.8
title: Selection Trees
pagenum: 240; label: 5.8.1
title: Introduction
pagenum: 240; label: 5.8.2
title: Winner Trees
pagenum: 241; label: 5.8.3
title: Loser Trees
pagenum: 243; label: 5.9
title: Forests
pagenum: 244; label: 5.9.1
title: Transforming a Forest into a Binary Tree
pagenum: 245; label: 5.9.2
title: Forest Traversals
pagenum: 246; label: 5.10
title: Representation of Disjoint Sets
pagenum: 247; label: 5.10.1
title: Introduction
pagenum: 247; label: 5.10.2
title: Union and Find Operations
pagenum: 248; label: 5.10.3
title: Application to Equivalence Classes
pagenum: 256; label: 5.11
title: Counting Binary Trees
pagenum: 259; label: 5.11.1
title: Distinct Binary Trees
pagenum: 259; label: 5.11.2
title: Stack Permutations
pagenum: 259; label: 5.11.3
title: Matrix Multiplication
pagenum: 262; label: 5.11.4
title: Number of Distinct Binary Trees
pagenum: 263; label: 5.12
title: References and Selected Readings
pagenum: 264; label: Chapter 6
title: Graphs
pagenum: 265; label: 6.1
title: The Graph Abstract Data Type
pagenum: 265; label: 6.1.1
title: Introduction
pagenum: 265; label: 6.1.2
title: Definitions
pagenum: 267; label: 6.1.3
title: Graph Representations
pagenum: 272; label: 6.2
title: Elementary Graph Operations
pagenum: 279; label: 6.2.1
title: Depth First Search
pagenum: 279; label: 6.2.2
title: Breadth First Search
pagenum: 281; label: 6.2.3
title: Connected Components
pagenum: 283; label: 6.2.4
title: Spanning Trees
pagenum: 284; label: 6.2.5
title: Biconnected Components
pagenum: 286; label: 6.3
title: Minimum Cost Spanning Trees
pagenum: 292; label: 6.3.1
title: Kruskal's Algorithm
pagenum: 292; label: 6.3.2
title: Prim's Algorithm
pagenum: 296; label: 6.3.3
title: Sollin's Algorithm
pagenum: 297; label: 6.4
title: Shortest Paths and Transitive Closure
pagenum: 299; label: 6.4.1
title: Single Source/All Destination: Nonnegative Edge Costs
pagenum: 300; label: 6.4.2
title: Single Source/All Destination: General Weights
pagenum: 303; label: 6.4.3
title: All Pairs Shortest Paths
pagenum: 307; label: 6.4.4
title: Transitive Closure
pagenum: 310; label: 6.5
title: Activity Networks
pagenum: 315; label: 6.5.1
title: Activity-on-Vertex (AOV) Networks
pagenum: 315; label: 6.5.2
title: Activity-on-Edge (AOE) Networks
pagenum: 320; label: 6.6
title: References and Selected Readings
pagenum: 330; label: 6.7
title: Additional Exercises
pagenum: 331; label: Chapter 7
title: Sorting
pagenum: 333; label: 7.1
title: Motivation
pagenum: 333; label: 7.2
title: Insertion Sort
pagenum: 337; label: 7.3
title: Quick Sort
pagenum: 340; label: 7.4
title: How Fast Can We Sort?
pagenum: 343; label: 7.5
title: Merge Sort
pagenum: 346; label: 7.5.1
title: Merging
pagenum: 346; label: 7.5.2
title: Iterative Merge Sort
pagenum: 347; label: 7.5.3
title: Recursive Merge Sort
pagenum: 349; label: 7.6
title: Heap Sort
pagenum: 352; label: 7.7
title: Sorting on Several Keys
pagenum: 356; label: 7.8
title: List and Table Sorts
pagenum: 361; label: 7.9
title: Summary of Internal Sorting
pagenum: 370; label: 7.10
title: External Sorting
pagenum: 376; label: 7.10.1
title: Introduction
pagenum: 376; label: 7.10.2
title: k-way Merging
pagenum: 379; label: 7.10.3
title: Buffer Handling for Parallel Operation
pagenum: 381; label: 7.10.4
title: Run Generation
pagenum: 387; label: 7.10.5
title: Optimal Merging of Runs
pagenum: 388; label: 7.11
title: References and Selected Readings
pagenum: 394; label: Chapter 8
title: Hashing
pagenum: 395; label: 8.1
title: Introduction
pagenum: 395; label: 8.2
title: Static Hashing
pagenum: 396; label: 8.2.1
title: Hash Tables
pagenum: 396; label: 8.2.2
title: Hash Functions
pagenum: 398; label: 8.2.3
title: Overflow Handling
pagenum: 401; label: 8.2.4
title: Theoretical Evaluation of Overflow Techniques
pagenum: 407; label: 8.3
title: Dynamic Hashing
pagenum: 410; label: 8.3.1
title: Motivation for Dynamic Hashing
pagenum: 410; label: 8.3.2
title: Dynamic Hashing using Directories
pagenum: 411; label: 8.3.3
title: Directoryless Dynamic Hashing
pagenum: 414; label: 8.4
title: Bloom Filters
pagenum: 416; label: 8.4.1
title: An Application -- Differential Files
pagenum: 416; label: 8.4.2
title: Bloom Filter Design
pagenum: 418; label: 8.5
title: References and Selected Readings
pagenum: 420; label: Chapter 9
title: Priority Queues
pagenum: 422; label: 9.1
title: Single- and Double-Ended Priority Queues
pagenum: 422; label: 9.2
title: Leftist Trees
pagenum: 424; label: 9.2.1
title: Height-Biased Leftist Trees
pagenum: 424; label: 9.2.2
title: Weight-Biased Leftist Trees
pagenum: 428; label: 9.3
title: Binomial Heaps
pagenum: 433; label: 9.3.1
title: Cost Amortization
pagenum: 433; label: 9.3.2
title: Definition of Binomial Heaps
pagenum: 435; label: 9.3.3
title: Insertion into a Binomial Heap
pagenum: 436; label: 9.3.4
title: Melding Two Binomial Heaps
pagenum: 436; label: 9.3.5
title: Deletion of Min Element
pagenum: 436; label: 9.3.6
title: Analysis
pagenum: 439; label: 9.4
title: Fibonacci Heaps
pagenum: 442; label: 9.4.1
title: Definition
pagenum: 442; label: 9.4.2
title: Deletion from an F-heap
pagenum: 442; label: 9.4.3
title: Decrease Key
pagenum: 443; label: 9.4.4
title: Cascading Cut
pagenum: 444; label: 9.4.5
title: Analysis
pagenum: 445; label: 9.4.6
title: Application to the Shortest Paths Problem
pagenum: 447; label: 9.5
title: Pairing Heaps
pagenum: 450; label: 9.5.1
title: Definition
pagenum: 450; label: 9.5.2
title: Meld and Insert
pagenum: 451; label: 9.5.3
title: Decrease Key
pagenum: 452; label: 9.5.4
title: Delete Min
pagenum: 453; label: 9.5.5
title: Arbitrary Delete
pagenum: 456; label: 9.5.6
title: Implementation Considerations
pagenum: 457; label: 9.5.7
title: Complexity
pagenum: 457; label: 9.6
title: Symmetric Min-Max Heaps
pagenum: 458; label: 9.6.1
title: Definition and Properties
pagenum: 458; label: 9.6.2
title: SMMH Representation
pagenum: 460; label: 9.6.3
title: Inserting into an SMMH
pagenum: 460; label: 9.6.4
title: Deleting from an SMMH
pagenum: 465; label: 9.7
title: Interval Heaps
pagenum: 469; label: 9.7.1
title: Definition and Properties
pagenum: 469; label: 9.7.2
title: Inserting into an Interval Heap
pagenum: 471; label: 9.7.3
title: Deleting the Min Element
pagenum: 473; label: 9.7.4
title: Initializing an Interval Heap
pagenum: 475; label: 9.7.5
title: Complexity of Interval Heap Operations
pagenum: 475; label: 9.7.6
title: The Complementary Range Search Problem
pagenum: 475; label: 9.8
title: References and Selected Readings
pagenum: 478; label: Chapter 10
title: Efficient Binary Search Trees
pagenum: 481; label: 10.1
title: Optimal Binary Search Trees
pagenum: 481; label: 10.2
title: AVL Trees
pagenum: 491; label: 10.3
title: Red-Black Trees
pagenum: 506; label: 10.3.1
title: Definition
pagenum: 506; label: 10.3.2
title: Representation of a Red-Black Tree
pagenum: 508; label: 10.3.3
title: Searching a Red-Black Tree
pagenum: 508; label: 10.3.4
title: Inserting into a Red-Black Tree
pagenum: 508; label: 10.3.5
title: Deletion from a Red-Black Tree
pagenum: 514; label: 10.3.6
title: Joining Red-Black Trees
pagenum: 514; label: 10.3.7
title: Splitting a Red-Black Tree
pagenum: 515; label: 10.4
title: Splay Trees
pagenum: 518; label: 10.4.1
title: Bottom-Up Splay Trees
pagenum: 518; label: 10.4.2
title: Top-Down Splay Trees
pagenum: 524; label: 10.5
title: References and Selected Readings
pagenum: 531; label: Chapter 11
title: Multiway Search Trees
pagenum: 532; label: 11.1
title: m-way Search Trees
pagenum: 532; label: 11.1.1
title: Definition and Properties
pagenum: 532; label: 11.1.2
title: Searching an m-way Search Tree
pagenum: 534; label: 11.2
title: B-Trees
pagenum: 535; label: 11.2.1
title: Definition and Properties
pagenum: 535; label: 11.2.2
title: Number of Elements in a B-Tree
pagenum: 536; label: 11.2.3
title: Insertion into a B-Tree
pagenum: 538; label: 11.2.4
title: Deletion from a B-Tree
pagenum: 542; label: 11.3
title: B+-Trees
pagenum: 551; label: 11.3.1
title: Definition
pagenum: 551; label: 11.3.2
title: Searching a B+-Tree
pagenum: 552; label: 11.3.3
title: Insertion into a B+-Tree
pagenum: 553; label: 11.3.4
title: Deletion from a B+-Tree
pagenum: 554; label: 11.4
title: References and Selected Readings
pagenum: 560; label: Chapter 12
title: Digital Search Structures
pagenum: 561; label: 12.1
title: Digital Search Trees
pagenum: 561; label: 12.1.1
title: Definition
pagenum: 561; label: 12.1.2
title: Search, Insert and Delete
pagenum: 562; label: 12.2
title: Binary Tries and Patricia
pagenum: 563; label: 12.2.1
title: Binary Tries
pagenum: 563; label: 12.2.2
title: Compressed Binary Tries
pagenum: 564; label: 12.2.3
title: Patricia
pagenum: 564; label: 12.3
title: Multiway Tries
pagenum: 571; label: 12.3.1
title: Definition
pagenum: 571; label: 12.3.2
title: Searching a Trie
pagenum: 574; label: 12.3.3
title: Sampling Strategies
pagenum: 574; label: 12.3.4
title: Insertion into a Trie
pagenum: 577; label: 12.3.5
title: Deletion from a Trie
pagenum: 577; label: 12.3.6
title: Keys with Different Length
pagenum: 578; label: 12.3.7
title: Height of a Trie
pagenum: 578; label: 12.3.8
title: Space Required and Alternative Node Structures
pagenum: 579; label: 12.3.9
title: Prefix Search and Applications
pagenum: 582; label: 12.3.10
title: Compressed Tries
pagenum: 584; label: 12.3.11
title: Compressed Tries with Skip Fields
pagenum: 587; label: 12.3.12
title: Compressed Tries with Labeled Edges
pagenum: 588; label: 12.3.13
title: Space Required by a Compressed Trie
pagenum: 592; label: 12.4
title: Suffix Trees
pagenum: 593; label: 12.4.1
title: Have You Seen This String?
pagenum: 593; label: 12.4.2
title: The Suffix Tree Data Structure
pagenum: 594; label: 12.4.3
title: Let's Find That Substring (Searching a Suffix Tree)
pagenum: 597; label: 12.4.4
title: Other Nifty Things You Can Do with a Suffix Tree
pagenum: 598; label: 12.5
title: Tries and Internet Packet Forwarding
pagenum: 600; label: 12.5.1
title: IP Routing
pagenum: 600; label: 12.5.2
title: 1-Bit Tries
pagenum: 601; label: 12.5.3
title: Fixed-Stride Tries
pagenum: 602; label: 12.5.4
title: Variable-Stride Tries
pagenum: 605; label: 12.6
title: References and Selected Readings
pagenum: 608; title: Index
pagenum: 610