Fundamentals of data structure in C
Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed
- 2nd ed.
- Kolkata University press 2023
- xvii,617p. P.B.
CHAPTER 1 BASIC CONCEPTS 1.1 Overview: System Life Cycle 1.2 Pointers and Dynamic Memory Allocation 1.2.1 Pointers 1.2.2 Dynamic Memory Allocation 1.2.3 Pointers Can Be Dangerous 1.3 Algorithm Specification 1.3.1 Introduction 1.3.2 Recursive Algorithms 1.4 Data Abstraction 1.5 Performance Analysis 1.5.1 Space Complexity 1.5.2 Time Complexity 1.5.3 Asymptotic Notation 1.5.4 Practical Complexities 1.6 Performance Measurement 1.6.1 Clocking 1.6.2 Generating Test Data 1.7 Referenes And Selected Readings
CHAPTER 2 ARRAYS AND STRUCTURES 2.1 Arrays 2.1.1 The Abstract Data Type 2.1.2 Arrays in C 2.2 Dynamically Allocated Arrays 2.2.1 One-dimensional Arrays 2.2.2 Two-dimensional Arrays 2.3 Structures and Unions 2.3.1 Strctures 2.3.2 Unions 2.3.3 Internal Representation of Structures 2.3.4 Self-referential Structures 2.4 Polynomials 2.4.1 The Abstract Data Type 2.4.2 Polynomial Representation 2.4.3 Polynomial Addition 2.5 Sparse Matrices 2.5.1 The Abstract Data Type 2.5.2 Sparse Matrix Representation 2.5.3 Transposing a Matrix 2.5.4 Matrix Multiplication 2.6 Representation of Multidimensional Arrays 2.7 Strings 2.7.1 The Abstract Data Type 2.7.2 Strings in C 2.7.3 Pattern Matching 2.8 References and Selected Readings 2.9 Additional Exercises
CHAPTER 3 STACKS AND QUEUES 3.1 Stacks 3.2 Stacks Using Dynamic Arrays 3.3 Queues 3.4 Circular Queues Using Dynamic Arrays 3.5 A Mazing Problem 3.6 Evaluation of Expressions 3.6.1 Expressions 3.6.2 Evaluating Postfix Expressions 3.7 Multiple Stacks and Queues
3.7 Additional Exercises
CHAPTER 4 LINKED LISTS 4.1 Singly Linked Lists and Chains 4.2 Representing Chains in C 4.3 Linked Stacks and Queues 4.4 Polynomials 4.4.1 Polynomial Representation 4.4.2 Adding Polynomials 4.4.3 Erasing Polynomials 4.4.4 Circular List Representation of Polynomials 4.4.5 Summary 4.5 Additional List Operations 4.5.1 Operations for Chains 4.5.2 Operations for Circularly Linked Lists 4.6 Equivalence Classes 4.7 Sparse Matrices 4.7.1 Sparse Matrix Representation 4.7.2 Sparse Matrix Input 4.7.3 Sparse Matrix Output 4.7.4 Erasing a Sparse Matrix 4.8 Doubly Linked Lists
CHAPTER 5 TREES 5.1 Introduction 5.1.1 Terminology 5.1.2 Representation of Trees 5.2 Binary Trees 5.2.1 The Abstract Data Type 5.2.2 Properties of Binary Trees 5.2.3 Binary Tree Representations 5.3 Binary Tree Traversals
5.3.1 Inorder Traversal
5.3.2 Preorder Traversal 5.3.3Postorder Traversal 5.3.4 Iterative Inorder Traversal 5.3.5 Level-Order Traversal 5.3.6 Traversal Without a Stack 5.4 Additional Binary Tree Operations 5.4.1 Copying Binary Trees 5.4.2 Testing Equality 5.4.3 The Satisfiability Problem 5.5 Threaded Binary Trees 5.5.1 Threads 5.5.2 Inorder Traversal of a Threaded Binary Tree 5.5.3 Inserting a Node into a Threaded Binary Tree 5.6 Heaps 5.6.1 Priority Ques 5.6.2 Definition of a Max Heap 5.6.3 Insertion into a Max Heap 5.6.4 Deletion from a Max Heap 5.7 Binary Search Trees 5.7.1 Definition 5.7.2 Searching a Binary Search Tree 5.7.3 Insertion into a Binary Search Tree 5.7.4 Deletion from a Binary Search Tree 5.7.5 Joining and Splitting Binary Search Trees 5.7.6 Height of a Binary Search Tree 5.8 Selection Trees
5.8.1 Introduction
5.8.2 Winner Trees 5.8.3 Loser Trees 5.9 Forests
5.9.1 Transforming a Forest into a Binary Tree 5.9.2 Forest Traversals 5.10 Representation of Disjoint Sets
5.10.1 Introduction
5.10.2 Union and find Operations 5.10.3 Application to Equivalence Classes 5.11 Counting Binary Trees 5.11.1 Distinct Binary Trees 5.11.2 Stack Permutations 5.11.3 Matrix Multiplication 5.11.4 Number of Distinct Binary Trees 5.12 References and Selected Readings
CHAPTER 6 GRAPHS 6.1 The Graph Abstract Data Type 6.1.1 Introduction 6.1.2 Definitions 6.1.3 Graph Representations 6.2 Elementary Graph Operations 6.2.1 Depth First Search 6.2.2 Breadth First Search 6.2.3 Connected Components 6.2.4 Spanning Trees 6.2.5 Biconnected Components 6.3 Minimum Cost Spanning Trees 6.3.1 Kruskal’s Algorithm 6.3.2 Prim’s Algorithm 6.3.3 Sollin’s Algorithm 6.4 Shortest Paths and Transitive Closure 6.4.1 Single Source/All Destination: Nonnegative Edge Costs 6.4.2 Single Source/all Destination: General Weights 6.4.3 All Pairs Shortest Paths 6.4.4 Transitive Closure 6.5 Activity Networks 6.5.1 Activity-on-Vertex (AOV) Networks 6.5.2 Activity-on-Edge (AOE) Networks 6.6 References and Selected Readings 6.7 Additional Exercises
CHAPTER 7 SORTING 7.1 Motivation 7.2 Insertion Sort 7.3 Quick Sort 7.4 How Fast Can We Sort? 7.5 Merge Sort 7.5.1 Merging 7.5.2 Interative Merge Sort 7.5.3 Recursive Merge Sort 7.6 Heap Sort 7.7 Sorting on Several Keys 7.8 List and Table Sorts 7.9 Summary of Internal Sorting 7.10 External Sorting 7.10.1 Introduction 7.10.2 k-way Merging 7.10.3 Buffer Handling for Parallel Operation 7.10.4 Run Generation 7.10.5 Optimal Merging of Runs 7.11 References and Selected Readings
CHAPTER 9 PRIORITY QUEUES 9.1 Single- and Double-Ended Priority Queues 9.2 Leftist Trees 9.2.1 Height-Biased Leftist Trees 9.2.2 Weight-Biased Leftist Trees 9.3 Binomial Heaps 9.3.1 Cost Amortization 9.3.2 Definition of Binomial Heaps 9.3.3 Insertion into a Binomial Heap 9.3.4 Melding Two Binomial Heaps 9.3.5 Deletion of Min Element 9.3.6 Analysis 9.4 Fibonacci Heaps 9.4.1 Definition 9.4.2 Deletion from an f-heap 9.4.3 Decrease Key 9.4.4 Cascading Cut 9.4.5 Analysis 9.4.6 Application to The Shortest Paths Problem 9.5 Pairing Heaps 9.5.1 Definition 9.5.2 Meld and Insert 9.5.3 Decrease Key 9.5.4 Delete Min 9.5.5 Arbitrary Delete 9.5.6 Implementation Considerations 9.5.7 Complexity 9.6 Symmetric Min-Max Heaps 9.6.1 Definition and Properties 9.6.2 SMMH Representation 9.6.3 Inserting into an SMMH 9.6.4 Deleting from an SMMH 9.7 Interval Heaps 9.7.1 Definition and Properties 9.7.2 Inserting into an Interval Heap 9.7.3 Deleting the Min Element 9.7.4 Initializing an Interval Heap 9.7.5 Complexity of Interval Heap Operations 9.7.6 The Complementary Range Search Problem 9.8 References and Selected Readings
CHAPTER 10 EFFICIENT BINARY SEARCH TREES 10.1 Optimal Binary Search Trees 10.2 AVL Trees 10.3 Red-Black Trees 10.3.1 Definition 10.3.2 Representation of a Red-Black Tree 10.3.3 Searching a Red-Black Tree 10.3.4 Inserting to a Red-Black Tree 10.3.5 Deletion from a Red-Black Tree 10.3.6 Joining Red-Black Trees 10.3.7 Splitting a Red-Black Tree 10.4 Splay Trees 10.4.1 Bottom-Up Splay Trees 10.4.2 Top-Down Splay Trees 10.5 References and Selected Readings
CHAPTER 11 MULTIWAY SEARCH TREES 11.1 m-way Search Trees 11.1.1 Definition and Properties 11.1.2 Searching an m-way Search Tree 11.2 B-Trees 11.2.1 Definition and Properties 11.2.2 Number of Elements in a B-Tree 11.2.3 Insertion into a B-tree 11.2.4 Deletion from a B-tree 11.3 B-Trees 11.3.1 Definition 11.3.2 Searching a B____________Tree 11.3.3 Insertion into a B____________Tree 11.3.4 Deletion from a B____________Tree 11.4 References and Selected Readings
CHAPTER 12 DIGITAL SEARCH STRUCTURES 12.1 Digital Search Trees
12.1.1 Definition
12.1.2 Search, Insert and Delete 12.2 Binary Tries and Patricia 12.2.1 Binary Tries 12.2.2 Compressed Binary Tries 12.2.3 Patricia 12.3 Multiway Tries 12.3.1 Definition 12.3.2 Searching a Trie 12.3.3 Sampling Strategies 12.3.4 Insertion into a Trie 12.3.5 Deletion from a Trie 12.3.6 Keys with Different Length 12.3.7 Height of a Trie 12.3.8 Space Required and Alternative Node Structures 12.3.9 Prefix Search and Applications 12.3.10 Compressed Tries 12.3.11 Compressed Tries with Skip Fields 12.3.12 Compressed Tries with Labeled Edges 12.3.13 Space Required by a Compressed Trie 12.4 Suffix Trees 12.4.1 Have you Seen this String? 12.4.2 The Suffix Tree Data Structure 12.4.3 Let’s Find That Substring (Searching a Suffix Tree) 12.4.4 Other Nifty Things You Can Do with a Suffix Tree 12.5 Tries and Internet Packet Forwarding 12.5.1 IP Routing 12.5.2 I-Bit Tries 12.5.3 Fixed-Stride Tries 12.5.4 Variable-Stride Tries 12.6 References and Selected Readings