Data Structures and Program Design Using C++: A Self-Teaching Introduction

✍ Scribed by D. Malhotra and N. Malhotra

• Publisher: Mercury Learning and Information
• Year: 2020
• Tongue: English
• Leaves: 569
• Category: Library

✦ Synopsis

Data structures provide a means to managing large amounts of information such as large databases, using SEO effectively, and creating Internet/Web indexing services. This book is designed to present fundamentals of data structures for beginners using the C++ programming language in a friendly, self-teaching, format. Practical analogies using real world applications are integrated throughout the text to explain technical concepts. The book includes a variety of end-of-chapter practice exercises, e.g., programming, theoretical, and multiple-choice.

Features:

• Covers data structure fundamentals using C++
• Numerous tips, analogies, and practical applications enhance understanding of subjects under discussion
• “Frequently Asked Questions” integrated throughout the text clarify and explain concepts
• Includes a variety of end-of-chapter exercises, e.g., programming, theoretical, and multiple choice

✦ Table of Contents

Cover
DATA STRUCTURES AND PROGRAM DESIGN USING C++
CONTENTS
PREFACE
ACKNOWLEDGMENTS
CHAPTER 1 INTRODUCTION TO DATA STRUCTURES
1.1 Introduction
1.2 Types of Data Structures
1.2.1 Linear and Non-Linear Data Structures
1.2.2 Static and Dynamic Data Structures
1.2.3 Homogeneous and Non-Homogeneous Data Structures
1.2.4 Primitive and Non-Primitive Data Structures
1.2.5 Arrays
1.2.6 Queues
1.2.7 Stacks
1.2.8 Linked List
1.2.9 Trees
1.2.10 Graphs
1.3 Operations on Data Structures
1.4 Algorithms
1.4.1 Developing an Algorithm
1.5 Approaches for Designing an Algorithm
1.6 Analyzing an Algorithm
1.6.1 Time-Space Trade-Off
1.7 Abstract Data Types
1.8 Big O Notation
1.9 Summary
1.10 Exercises
1.11 Multiple Choice Questions
CHAPTER 2 INTRODUCTION TO THE
C++ LANGUAGE
2.1 Introduction
2.2 C++ and Its Characteristics
2.3 Features of Object-Oriented Programming
2.4 Character Set Used in C++
2.5 C++ Tokens
2.6 Data Types in C++
2.7 Structure of a C++ Program
2.7.1 Structure of a C++ Program without Classes
2.7.2 Structure of a C++ Program with Classes
2.8 Operators in C++
2.9 Decision Control Statements in C++
2.10 Looping Statements in C++
2.11 Break and Continue Statements
2.12 Functions in C++
2.12.1 Passing Arguments to Functions
2.13 Structures in C++
2.14 Reference Variables in C++
2.15 Pointers
2.16 Arrays and Pointers
2.17 Summary
2.18 Exercises
2.18.1 Theory Questions
2.18.2 Programming Questions
2.18.3 Multiple Choice Questions
CHAPTER 3 ARRAYS
3.1 Introduction
3.2 Definition of an Array
3.3 Array Declaration
3.4 Array Initialization
3.5 Calculating the Address of Array Elements
3.6 Operations on Arrays
3.7 2-D Arrays/Two-Dimensional Arrays
3.8 Declaration of Two-Dimensional Arrays
3.9 Operations on 2-D Arrays
3.10 Multidimensional Arrays/ N-Dimensional Arrays
3.11 Calculating the Address of 3-D Arrays
3.12 Arrays and Pointers
3.13 Array of Pointers
3.14 Arrays and Their Applications
3.15 Sparse Matrices
3.16 Types of Sparse Matrices
3.17 Representation of Sparse Matrices
3.18 Summary
3.19 Exercises
3.19.1 Theory Questions
3.19.2 Programming Questions
3.19.3 Multiple Choice Questions
CHAPTER 4 LINKED LISTS
4.1 Introduction
4.2 Definition of a Linked List
4.3 Memory Allocation in a Linked List
4.4 Types of Linked Lists
4.4.1 Singly Linked List
4.4.2 Operations on a Singly Linked List
4.4.3 Circular Linked Lists
4.4.4 Operations on a Circular Linked List
4.4.5 Doubly Linked List
4.4.6 Operations on a Doubly Linked List
4.5 Header Linked Lists
4.6 Applications of Linked Lists
4.7 Polynomial Representation
4.8 Summary
4.9 Exercises
4.9.1 Theory Questions
4.9.2 Programming Questions
4.9.3 Multiple Choice Questions
CHAPTER 5 QUEUES
5.1 Introduction
5.2 Definition of a Queue
5.3 Implementation of a Queue
5.3.1 Implementation of Queues Using Arrays
5.3.2 Implementation of Queues Using Linked Lists
5.3.2.1 Insertion in Linked Queues
5.3.2.2 Deletion in Linked Queues
5.4 Operations on Queues
5.4.1 Insertion
5.4.2 Deletion
5.5 Types of Queues
5.5.1 Circular Queue
5.5.1.1 Limitation of Linear Queues
5.5.1.2 Inserting an Element in a Circular Queue
5.5.1.3 Deleting an Element from a Circular Queue
5.5.2 Priority Queue
5.5.2.1 Implementation of a Priority Queue
5.5.2.2 Insertion in a Linked Priority Queue
5.5.2.3 Deletion in a Linked Priority Queue
5.5.3 De-queues (Double-Ended Queues)
5.6 Applications of Queues
5.7 Summary
5.8 Exercises
5.8.1 Theory Questions
5.8.2 Programming Questions
5.8.3 Multiple Choice Questions
CHAPTER 6 SEARCHING AND SORTING
6.1 Introduction to Searching
6.2 Linear Search or Sequential Search
6.2.1 Drawbacks of a Linear Search
6.3 Binary Search
6.3.1 Binary Search Algorithm
6.3.2 Complexity of a Binary Search Algorithm
6.3.3 Drawbacks of a Binary Search
6.4 Interpolation Search
6.4.1 Working of the Interpolation Search Algorithm
6.4.2 Complexity of the Interpolation Search Algorithm
6.5 Introduction to Sorting
6.5.1 Types of Sorting Methods
6.6 External Sorting
6.7 Summary
6.8 Exercises
6.8.1 Theory Questions
6.8.2 Programming Questions
6.8.3 Multiple Choice Questions
CHAPTER 7 STACKS
7.1 Introduction
7.2 Definition of a Stack
7.3 Overflow and Underflow in Stacks
7.4 Operations on Stacks
7.5 Implementation of Stacks
7.5.1 Implementation of Stacks Using Arrays
7.5.2 Implementation of Stacks Using Linked Lists
7.5.2.1 Push Operation in Linked Stacks
7.5.2.2 Pop Operation in Linked Stacks
7.6 Applications of Stacks
7.6.1 Polish and Reverse Polish Notations and Their Need
7.6.2 Conversion from Infix Expression to Postfix Expression
7.6.3 Conversion from Infix Expression to Prefix Expression
7.6.4 Evaluation of a Postfix Expression
7.6.5 Evaluation of a Prefix Expression
7.6.6 Parenthesis Balancing
7.7 Summary
7.8 Exercises
7.8.1 Theory Questions
7.8.2 Programming Questions
7.8.3 Multiple Choice Questions
CHAPTER 8 TREES
8.1 Introduction
8.2 Definitions
8.3 Binary Tree
8.3.1 Types of Binary Trees
8.3.2 Memory Representation of Binary Trees
8.4 Binary Search Tree
8.4.1 Operations on Binary Search Trees
8.4.2 Binary Tree Traversal Methods
8.4.3 Creating a Binary Tree Using Traversal Methods
8.5 AVL Trees
8.5.1 Need of Height-Balanced Trees
8.5.2 Operations on an AVL Tree
8.6 Summary
8.7 Exercises
8.7.1 Theory Questions
8.7.2 Programming Questions
8.7.3 Multiple Choice Questions
CHAPTER 9 MULTI-WAY SEARCH TREES
9.1 Introduction
9.2 B–Trees
9.3 Operations on a B-Tree
9.3.1 Insertion in a B-Tree
9.3.2 Deletion in a B-Tree
9.4 Application of a B-Tree
9.5 B+ Trees
9.6 Summary
9.7 Exercises
9.7.1 Review Questions
9.7.2 Multiple Choice Questions
CHAPTER 10 HASHING
10.1 Introduction
10.1.1 Difference between Hashing and Direct Addressing
10.1.2 Hash Tables
10.1.3 Hash Functions
10.1.4 Collision
10.1.5 Collision Resolution Techniques
10.1.5.1 Chaining Method
10.1.5.2 Open Addressing Method
10.2 Summary
10.3 Exercises
10.3.1 Review Questions
10.3.2 Multiple Choice Questions
CHAPTER 11 FILES
11.1 Introduction
11.2 Terminologies
11.3 File Operations
11.4 File Classification
11.5 C vs C++ File Handling
11.6 File Organization
11.7 Sequence File Organization
11.8 Indexed Sequence File Organization
11.9 Relative File Organization
11.10 Inverted File Organization
11.11 Summary
11.12 Exercises
11.12.1 Review Questions
11.12.2 Multiple Choice Questions
CHAPTER 12 GRAPHS
12.1 Introduction
12.2 Definitions
12.3 Graph Representation
12.3.1 Adjacency Matrix Representation
12.3.2 Adjacency List Representation
12.4 Graph Traversal Techniques
12.4.1 Breadth First Search
12.4.2 Depth First Search
12.5 Topological Sort
12.6 Minimum Spanning Tree
12.6.1 Prim’s Algorithm
12.6.2 Kruskal’s Algorithm
12.7 Summary
12.8 Exercises
12.8.1 Theory Questions
12.8.2 Programming Questions
12.8.3 Multiple Choice Questions
APPENDIX A ANSWERS TO SELECTED EXERCISES
Chapter 1: Introduction to Data Structures
Chapter 2: Introduction to the C++ Language
Chapter 3: Arrays
Chapter 4: Linked Lists
Chapter 5: Queues
Chapter 6: Searching and Sorting
Chapter 7: Stacks
Chapter 8: Trees
Chapter 9: –Multi-Way Search Trees
Chapter 10: Hashing
Chapter 11: Files
Chapter 12: Graphs
APPENDIX B REFERENCES/ BOOKS/ WEBLIOGRAPHY
Book
INDEX