Data Structures Using C++

Description

Data Structures Using C++ is designed to serve as a textbook for undergraduate engineering students of computer science and information technology as well as postgraduate students of computer applications. The book aims to provide a comprehensive coverage of all the topics related to data structures. The book begins with a discussion on the fundamentals of data structures and algorithms, and moves on to the concepts of linear data structures, stacks, recursion, queues, and searching and sorting. All the elements of data structures, such as linked lists, trees, graphs, hashing, heaps, and indexing, are covered in separate chapters in detail. The chapter on files explains file management and organization using C++ and the chapter on the standard template library provides detailed coverage of entities such as containers and iterators. A chapter on algorithm analysis and design is provided towards the end that discusses the various algorithmic strategies required to solve a problem effectively and efficiently. Written in a simple manner with strong pedagogy including numerous multiple choice and review questions, the book also provides programming problems at the end of every chapter. Front Matter Dedication Preface Table of Contents 1. Fundamental Concepts 1.1 Introduction to Programming 1.2 Object-Oriented Programming 1.3 Introduction to Data Structures 1.3.1 Data 1.3.1.1 Atomic and Composite Data 1.3.2 Data Type 1.3.2.1 Built-in Data Types 1.3.2.2 User-Defined Data Types 1.3.3 Data Object 1.3.4 Data Structure 1.3.5 Abstract Data Type 1.4 Types of Data Structures 1.4.1 Primitive and Non-Primitive Data Structures 1.4.2 Linear and Non-Linear Data Structures 1.4.3 Static and Dynamic Data Structures 1.4.4 Persistent and Ephemeral Data Structures 1.4.5 Sequential Access and Direct Access Data Structures 1.5 Introduction to Algorithms 1.5.1 Characteristics of Algorithms 1.5.2 Algorithmics 1.5.3 Algorithm Design Tools: Pseudocode and Flowchart 1.6 Pseudocode 1.6.1 Pseudocode Notations 1.6.2 Algorithm Header 1.6.3 Purpose 1.6.4 Condition and Return Statements 1.6.5 Statement Numbers 1.6.6 Variables 1.6.7 Statement Constructs 1.6.7.1 Sequence 1.6.7.2 Decision 1.6.7.3 Repetition 1.6.8 Subalgorithms 1.7 Relationship among Data, Data Structures, and Algorithms 1.8 Implementation of Data Structures 1.9 Flowcharts 1.10 Analysis of Algorithms 1.10.1 Complexity of Algorithms 1.10.2 Space Complexity 1.10.2.1 Compile Time Space Complexity 1.10.2.2 Run-Time Space Complexity 1.10.3 Time Complexity 1.10.3.1 Best, Worst, and Average Cases 1.10.4 Computing Time Complexity of an Algorithm 1.10.5 Big-O Notation 1.11 From Problem to Program 1.12 Software Engineering 1.12.1 Analysis Phase 1.12.2 Design Phase 1.12.3 Implementation Phase 1.12.4 Testing Phase 1.12.5 Verification Phase Recapitulation Key Terms Exercises 2. Linear Data Structure Using Arrays 2.1 Sequential Organization 2.2 Linear Data Structure Using Sequential Organization: Arrays 2.3 Array as an Abstract Data Type 2.4 Memory Representation and Address Calculation 2.5 Class Array 2.5.1 Inserting an Element into an Array 2.5.2 Deleting an Element 2.6 Arrays Using Template 2.7 Multidimensional Arrays 2.7.1 Two-Dimensional Arrays 2.7.1.1 Memory Representation of Two-Dimensional Arrays 2.7.1.2 Row-Major Representation 2.7.1.3 Column-Major Representation 2.7.2 n-Dimensional Arrays 2.7.2.1 Address Calculation for Multidimensional Array 2.7.2.2 Address Calculation for One-Dimensional Array 2.7.2.3 Address Calculation for Two-Dimensional Array 2.7.2.4 Address Calculation for Three-Dimensional Array 2.8 Concept of Ordered List 2.9 Single Variable Polynomial 2.9.1 Representation Using Arrays 2.9.2 Polynomial as Array of Structure 2.9.3 Polynomial Evaluation 2.9.4 Polynomial Addition 2.9.5 Polynomial Multiplication 2.10 Array for Frequency Count 2.11 Sparse Matrix 2.11.1 Sparse Matrix Representation 2.11.2 Sparse Matrix Addition 2.11.3 Transpose of Sparse Matrix 2.11.3.1 Simple Transpose 2.11.3.2 Fast Transpose 2.11.3.3 Time and Space Complexity Analysis of Fast Transpose 2.12 String Manipulation Using Array 2.13 Pros and Cons of Arrays 2.13.1 Characteristics 2.13.2 Advantages 2.13.3 Disadvantages 2.13.4 Applications of Arrays Recapitulation Key Terms Exercises 3. Stacks 3.1 Concept of Stacks and Queues 3.2 Stacks 3.2.1 Primitive Operations 3.2.1.1 Push 3.2.1.2 Pop 3.2.1.3 GetTop 3.3 Stack Abstract Data Type 3.4 Representation of Stacks Using Sequential Organization Arrays 3.4.1 Create 3.4.2 Empty 3.4.3 GetTop 3.4.4 Push 3.4.5 Pop 3.5 Stacks Using Template 3.6 Multiple Stacks 3.7 Applications of Stack 3.8 Expression Evaluation and Conversion 3.8.1 Polish Notation and Expression Conversion 3.8.2 Need for Prefix and Postfix Expressions 3.8.3 Postfix Expression Evaluation 3.8.3.1 Infix to Postfix Conversion 3.8.3.2 Infix to Prefix Conversion 3.8.3.3 Postfix to Infix Conversion 3.8.3.4 Postfix to Prefix Conversion 3.8.3.5 Prefix to Infix Conversion 3.8.3.6 Prefix to Postfix Conversion 3.9 Processing of Function Calls 3.10 Reversing a String with a Stack 3.11 Checking Correctness of Well-Formed Parentheses 3.12 Recursion 3.13 Parsing Computer Programs 3.14 Backtracking Algorithms 3.15 Converting Decimal Numbers to Binary Recapitulation Key Terms Exercises 4. Recursion 4.1 Introduction 4.2 Recurrence 4.3 Use of Stack in Recursion 4.4 Variants of Recursion 4.4.1 Direct Recursion 4.4.2 Indirect Recursion 4.4.3 Tail Recursion 4.4.4 Linear Recursion 4.4.5 Tree Recursion 4.5 Execution of Recursive Calls 4.6 Recursive Functions 4.6.1 Writing Recursive Code 4.6.2 Tower of Hanoi: An Example of Recursion 4.6.3 Checking for Correctness 4.6.4 Things to Remember 4.7 Iteration versus Recursion 4.7.1 Demerits of Recursive Algorithms 4.7.2 Demerits of Iterative Methods 4.8 Simulating Recursion Using Stack Eliminating Recursion 4.9 Applications of Recursion Recapitulation Key Terms Exercises 5. Queues 5.1 Concept of Queues 5.2 Queue as Abstract Data Type 5.3 Realization of Queues Using Arrays 5.4 Circular Queue 5.4.1 Advantages of Using Circular Queues 5.5 Multi-Queues 5.6 Deque 5.7 Priority Queue 5.7.1 Array Implementation of Priority Queue 5.8 Applications of Queues 5.8.1 Josephus Problem 5.8.2 Job Scheduling 5.8.3 Simulation 5.9 Queues Using Template Recapitulation Key Terms Exercises 6. Linked Lists 6.1 Introduction 6.2 Linked List 6.2.1 Comparison of Sequential and Linked Organizations 6.2.2 Linked List Terminology 6.2.3 Primitive Operations 6.3 Realization of Linked Lists 6.3.1 Realization of Linked List Using Arrays 6.3.2 Linked List Using Dynamic Memory Management 6.3.2.1 Empty Linked List 6.4 Dynamic Memory Management 6.4.1 Dynamic Memory Management in C++ with new and delete Operators 6.4.1.1 The new Operator 6.4.1.2 Syntax 6.4.1.3 The Null Pointer 6.4.1.4 The delete Operator 6.5 Linked List Abstract Data Type 6.5.1 Data Structure of Node 6.5.2 Insertion of a Node 6.5.2.1 Insertion of a Node at a Middle Position 6.5.2.2 Insertion of a Node at the First Position 6.5.2.3 Insertion of a Node at the End 6.5.2.4 Generalized Insert Routine 6.5.3 Linked List Traversal 6.5.3.1 Non-Recursive Method 6.5.3.2 Recursive Traversal Method 6.5.4 Deletion of a Node 6.5.4.1 Deleting the First Node 6.5.4.2 Deleting a Middle Node 6.6 Linked List Variants 6.6.1 Head Pointer and Header Node 6.6.2 Types of Linked List 6.6.2.1 Singly Linked List 6.6.2.2 Doubly Linked List 6.6.3 Linear and Circular Linked Lists 6.6.3.1 Linear Linked List 6.6.3.2 Circular Linked List 6.7 Doubly Linked List 6.7.1 Creation of Doubly Linked List 6.7.2 Deletion of a Node from a Doubly Linked List 6.7.3 Insertion of a Node in a Doubly Linked List 6.7.4 Traversal of DLL 6.8 Circular Linked List 6.8.1 Singly Circular Linked List 6.8.2 Circular Linked List with Header Node 6.8.3 Doubly Circular Linked List 6.9 Polynomial Manipulations 6.9.1 Polynomial Evaluation 6.9.2 Polynomial Addition 6.9.2.1 Paper-Pencil Method 6.9.2.2 Polynomial Addition Algorithm 6.9.3 Polynomial Multiplication 6.10 Representation of Sparse Matrix Using Linked List 6.11 Linked Stack 6.11.1 Class for Linked Stack 6.11.2 Operations on Linked Stack 6.12 Linked Queue 6.12.1 Erasing a Linked Queue 6.13 Generalized Linked List 6.13.1 Definition 6.13.2 Applications 6.13.3 Representation of Polynomials Using Generalized Linked List 6.13.4 Representation of Sets Using Generalized Linked List 6.13.4.1 Printing Generalized Linked Lists 6.14 More on Linked Lists 6.14.1 Copying a Linked List 6.14.2 Computing the Length of a Linked List 6.14.2.1 Calling Length 6.14.3 Reversing Singly Linked List without Temporary Storage 6.14.4 Concatenating Two Linked Lists 6.14.5 Erasing the Linked List 6.15 Application of Linked List - Garbage Collection Recapitulation Key Terms Exercises 7. Trees 7.1 Introduction 7.1.1 Basic Terminology 7.1.1.1 Adjacent Nodes 7.1.1.2 Directed and Undirected Graphs 7.1.1.3 Parallel Edges and Multigraph 7.1.1.4 Weighted Graph 7.1.1.5 Null Graph and Isolated Vertex 7.1.1.6 Degree of Vertex 7.1.1.7 Paths and Circuits 7.1.1.8 Connectivity 7.1.1.9 Acyclic Graph 7.1.1.10 Trees 7.1.1.11 Forest and Trees 7.1.2 General Tree 7.1.3 Representation of a General Tree 7.2 Types of Trees 7.3 Binary Tree 7.3.1 Properties of a Binary Tree 7.3.1.1 Property 1 7.3.1.2 Property 2 7.3.1.3 Property 3 7.3.1.4 Other Properties 7.3.1.5 Relation between Number of Leaf Nodes and Degree-2 Nodes 7.3.1.6 Binary Tree with n Nodes Having n + 1 External Nodes 7.4 Binary Tree Abstract Data Type 7.5 Realization of a Binary Tree 7.5.1 Array Implementation of Binary Trees 7.5.2 Linked Implementation of Binary Trees 7.6 Insertion of a Node in Binary Tree 7.7 Binary Tree Traversal 7.7.1 Preorder Traversal 7.7.1.1 Preorder DLR Algorithm 7.7.2 Inorder Traversal 7.7.2.1 Inorder LDR Algorithm 7.7.3 Postorder Traversal 7.7.3.1 Postorder LRD Algorithm 7.7.4 Non-Recursive Implementation of Traversals 7.7.4.1 Non-Recursive Preorder Algorithm 7.7.4.2 Non-Recursive Inorder Algorithm 7.7.4.3 Non-Recursive Postorder Algorithm 7.7.5 Formation of Binary Tree from its Traversals 7.7.6 Breadth- and Depth-First Traversals 7.7.6.1 Depth-First Traversal 7.7.6.2 Breadth-First Traversal 7.8 Other Tree Operations 7.8.1 Counting Nodes 7.8.2 Counting Leaf Nodes 7.8.3 Computing Height of Binary Tree 7.8.4 Getting Mirror, Replica, or Tree Interchange of Binary Tree 7.8.5 Copying Binary Tree 7.8.6 Equality Test 7.9 Conversion of General Tree to Binary Tree 7.10 Binary Search Tree 7.10.1 Inserting a Node 7.10.2 Searching for a Key 7.10.3 Deleting a Node 7.10.4 Binary Tree and Binary Search Tree 7.11 Threaded Binary Tree 7.11.1 Threading a Binary Tree 7.11.1.1 Sample Run 7.11.2 Right-Threaded Binary Tree 7.11.3 Inorder Traversal 7.11.4 Preorder Traversal 7.11.5 Insert to Right of a Node 7.11.6 Deleting a Node 7.11.7 Pros and Cons 7.12 Applications of Binary Trees 7.12.1 Expression Tree 7.12.1.1 Construction of Expression Tree 7.12.2 Decision Tree 7.12.3 Huffman's Coding 7.12.4 Game Trees Recapitulation Key Terms Exercises 8. Graphs 8.1 Introduction 8.2 Graph Abstract Data Type 8.3 Representation of Graphs 8.3.1 Adjacency Matrix 8.3.2 Adjacency List 8.3.3 Adjacency Multilist 8.3.4 Inverse Adjacency List 8.3.5 Comparison of Sequential and Linked Representations 8.4 Graph Traversal 8.4.1 Depth-First Search 8.4.2 Breadth-First Search 8.5 Spanning Tree 8.5.1 Connected Components 8.5.2 Prim's Algorithm 8.5.3 Kruskal's Algorithm 8.5.4 Biconnected Components 8.5.5 Disjoint Set Operations 8.6 Shortest Path Algorithm Recapitulation Key Terms Exercises 9. Searching and Sorting 9.1 Searching 9.2 Search Techniques 9.2.1 Sequential Search 9.2.1.1 Pros and Cons of Sequential Search 9.2.1.2 Variations of Sequential Search 9.2.2 Binary Search 9.2.2.1 Time Complexity Analysis 9.2.2.2 Pros and Cons of Binary Search 9.2.3 Fibonacci Search 9.2.3.1 Time Complexity of Fibonacci Search 9.2.4 Indexed Sequential Search 9.2.5 Hashed Search 9.3 Sorting 9.3.1 Types of Sorting 9.3.1.1 Internal Sorting 9.3.1.2 External Sorting 9.3.2 General Sort Concepts 9.3.2.1 Sort Order 9.3.2.2 Sort Stability 9.3.2.3 Sort Efficiency 9.3.2.4 Passes 9.3.3 Bubble Sort 9.3.3.1 Analysis of Bubble Sort 9.3.4 Insertion Sort 9.3.4.1 Analysis of Insertion Sort 9.3.5 Selection Sort 9.3.5.1 Analysis of Selection Sort 9.3.6 Quick Sort 9.3.6.1 Analysis of Quick Sort 9.3.7 Heap Sort 9.3.8 Shell Sort 9.3.9 Bucket Sort 9.3.10 Radix Sort 9.3.11 File Sort 9.3.12 Merge Sort 9.3.12.1 Time Complexity 9.4 Multiway Merge and Polyphase Merge 9.4.1 Comparison of Ordinary Merge Sort and Polyphase Sort 9.4.1.1 Perfect Three-File Polyphase Merge Sort 9.4.1.2 Two-Phase, Multiway Merge Sort 9.5 Comparison of All Sorting Methods Recapitulation Key Terms Exercises 10. Search Trees 10.1 Symbol Table 10.1.1 Representation of Symbol Table 10.1.1.1 Static Tree Tables 10.1.1.2 Dynamic Tree Tables 10.2 Optimal Binary Search Tree 10.3 AVL Tree Height-Balanced Tree 10.3.1 Implementation of AVL Technique 10.3.2 Insertions and Deletions in AVL Tree Recapitulation Key Terms Exercises 11. Hashing 11.1 Introduction 11.2 Key Terms and Issues 11.3 Hash Functions 11.3.1 Good Hash Function 11.3.1.1 Features of a Good Hashing Function 11.3.2 Division Method 11.3.3 Multiplication Method 11.3.4 Extraction Method 11.3.5 Mid-Square Hashing 11.3.6 Folding Technique 11.3.7 Rotation 11.3.8 Universal Hashing 11.4 Collision Resolution Strategies 11.4.1 Open Addressing 11.4.1.1 Linear Probing 11.4.1.2 Quadratic Probing 11.4.1.3 Double Hashing 11.4.1.4 Rehashing 11.4.2 Chaining 11.5 Hash Table Overflow 11.5.1 Open Addressing for Overflow Handling 11.5.2 Overflow Handling by Chaining 11.6 Extendible Hashing 11.7 Dictionary 11.8 Skip List 11.9 Comparison of Hashing and Skip Lists Recapitulation Key Terms Exercises 12. Heaps 12.1 Basic Concepts 12.1.1 Min-Heap and Max-Heap 12.1.1.1 Min-Heap 12.1.1.2 Max-Heap 12.2 Implementation of Heap 12.3 Heap as Abstract Data Type 12.3.1 Operations on Heaps 12.3.1.1 ReheapUp 12.3.1.2 ReheapDown 12.3.1.3 Insert 12.3.1.4 Delete 12.3.1.5 Creating a Heap 12.4 Heap Applications 12.5 Heap Sort 12.6 Binomial Trees and Heaps 12.6.1 Binomial Trees 12.6.2 Binomial Heap 12.6.3 Representation of Binomial Heap 12.6.4 Operations on Binomial Heaps 12.7 Fibonacci Heap 12.7.1 Representation of Fibonacci Heap 12.7.2 Operations on Fibonacci Heaps Recapitulation Key Terms Exercises 13. Indexing and Multiway Trees 13.1 Introduction 13.2 Indexing 13.2.1 Indexing Techniques 13.2.1.1 Cylinder-Surface Indexing 13.2.1.2 Hashed Indexing 13.3 Types of Search Trees 13.3.1 Multiway Search Tree 13.3.2 B-Tree 13.3.2.1 B-Tree Definition 13.3.2.2 Operations on B-Tree 13.3.2.3 B-Tree as Abstract Data Type 13.3.3 B+ Tree 13.3.3.1 B+ Tree Structure 13.3.3.2 Nodes of B+ Tree 13.3.3.3 Advantages of B+ Trees over Indexed Sequential Access Method 13.3.4 Trie Tree 13.3.4.1 Declaration for Trie Tree 13.3.5 Splay Tree 13.3.6 Red-Black Tree 13.3.7 K-Dimensional Tree 13.3.8 AA Tree 13.3.8.1 Advantages of AA Trees 13.3.8.2 Representing Balance Information in AA Tree Recapitulation Key Terms Exercises 14. Files 14.1 Introduction 14.2 External Storage Devices 14.2.1 Magnetic Tape 14.2.2 Magnetic Drum 14.2.3 Magnetic Disk 14.3 File Organization 14.3.1 Schemes of File Organization 14.3.2 Factors Affecting File Organization 14.3.3 Factors Involved in Selecting File Organization 14.4 Files Using C++ 14.4.1 File I/O Classes 14.4.2 Primitive Functions 14.4.3 Binary and Text Files 14.5 Sequential File Organization 14.5.1 Primitive Operations 14.5.1.1 Add 14.5.1.2 Search 14.5.1.3 Delete 14.5.1.4 Updation Modification 14.5.2 Advantages 14.5.3 Drawbacks 14.6 Direct Access File Organization 14.6.1 Primitive Operations 14.7 Indexed Sequential File Organization 14.7.1 Types of Indices 14.7.2 Structure of Indexed Sequential File 14.7.3 Characteristics of Indexed Sequential File 14.8 Linked Organization 14.8.1 Multilist Files 14.8.2 Coral Rings 14.8.3 Inverted Files 14.8.4 Cellular Partitions Recapitulation Key Terms Exercises 15. Standard Template Library 15.1 Abstract Data Type 15.1.1 Abstract Data Type and Data Structures 15.1.2 Creating Abstract Data Types 15.1.3 Stack Abstract Data Type 15.2 Survey of Programming Techniques 15.3 Standard Template Library 15.3.1 Containers 15.3.1.1 Sequence Containers 15.3.1.2 Associative Containers 15.3.2 Algorithms 15.3.3 Iterators 15.3.3.1 Input Iterator 15.3.3.2 Output Iterator 15.3.3.3 Forward Iterator 15.3.3.4 Bidirectional Iterator 15.3.3.5 Random Access Iterator 15.3.3.6 Operators Supported by Iterators 15.3.3.7 Pros and Cons of Standard Template Library 15.3.4 Function Objects Recapitulation Key Terms Exercises 16. Algorithm Analysis and Design 16.1 Introduction 16.1.1 Algorithm Analysis 16.1.2 Asymptotic Notations Omega, theta, O 16.1.2.1 Big O or Oh 16.1.2.2 Big Omega Omega 16.1.2.3 Big Theta Theta 16.2 Divide-and-Conquer 16.2.1 Unique Characteristics and Use 16.2.2 General Method 16.2.3 Binary Search 16.2.4 Merge Sort 16.2.4.1 Analysis of Merge Sort 16.2.5 Quick Sort 16.2.5.1 Analysis of Quicksort 16.2.6 Strassen's Algorithm for Matrix Multiplication 16.3 Greedy Method 16.3.1 General Greedy Method 16.3.1.1 Elements of Greedy Strategy 16.3.2 Knapsack Problem 16.4 Dynamic Programming 16.4.1 General Method of Dynamic Programming 16.4.2 Elements of Dynamic Programming 16.4.2.1 Optimal Substructure 16.4.2.2 Overlapping Subproblems 16.4.2.3 Memorization 16.4.3 Principle of Optimality 16.4.3.1 Difference between Greedy Method and Dynamic Programming 16.4.4 Limitations of Dynamic Programming 16.4.5 Knapsack Problem 16.5 Pattern Matching 16.5.1 Brute-Force Approach 16.5.2 Boyer-Moore Algorithm 16.5.3 Knuth-Morris-Pratt Algorithm 16.5.3.1 Prefix Function pi 16.5.3.2 KMP Matcher 16.6 Tries 16.6.1 Standard Tries 16.6.2 Compressed Tries 16.6.3 Suffix Tries Recapitulation Key Terms Exercises Features of the Book Appendix: Overview of C++ Programming A.1 Abstract Data Type A.2 Introduction to C++ A.2.1 Sample C++ Program A.2.2 C++ Statements and Operators A.2.3 Comments in C++ A.2.4 Input/Output in C++ A.3 Functions in C++ A.3.1 Inline Function A.4 C++ Class and Abstract Data Type A.4.1 Class A.4.1.1 Scope Resolution Operator :: A.4.2 Class Members: Public and Private A.4.3 Objects A.5 Static Class Members A.5.1 Static Data Members A.5.2 Static Member Functions A.6 Object as Function Parameter A.6.1 Passing Objects to Functions A.6.2 Returning Objects from Functions A.6.3 Arrays of Objects A.6.4 Pointers to Objects A.7 'this' Pointer A.8 Function Overloading A.8.1 Types of Polymorphism A.9 Constructors and Destructors A.9.1 Constructors A.9.2 Destructors A.9.3 Constructor with Default Arguments A.10 Inheritance A.10.1 Types of Inheritance A.10.2 Multiple Inheritance A.11 Abstract Classes A.11.1 Pure Virtual Functions A.12 Operator Overloading A.12.1 Comparing Function Overriding and Overloading A.13 Friend Function A.14 Generic Programming: Templates Acknowledgements Index A B C D E F G H I J K L M N O P Q R S T V W