Fundamentals of data structures in C
By: Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed
Contributors: Sahni, Sartaj; Anderson-Freed, Susan
Edition: 2nd ed.
Publisher: University Press
Published: 2008
Place of publication: Hyderabad
Language: eng
Number of pages: 617
ISBN-13: 9788173716058
Subjects: C (Computer program language); Data structures (Computer science); C (Langage de programmation); Structures de données (Informatique)
Description: The classic data structure textbook provides a comprehensive and technically rigorous introduction to data structures such as arrays, stacks, queues, linked lists, trees and graphs, and techniques such as sorting hashing that form the basis of all software. In addition, it presents advanced of specialized data structures such as priority queues, efficient binary search trees, multiway search trees and digital search structures. The book now discusses topics such as weight biased leftist trees, pairing heaps, symmetric min-max heaps, interval heaps, top-down splay trees, B+ trees and suffix trees. Red-black trees have been made more accessible. The section on multiway tries has been significantly expanded and several trie variations and their application to Interner packet forwarding have been disused.
Notes: Includes bibliographical references and index.
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: Amazing 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