Data Structures and Program Design Using C++ (Dheeraj Malhotra Neha Malhotra [Malhotra etc.) (Z-Library)

📄 File Format: PDF

💾 File Size: 27.4 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Data StructureS anD Program DeSign uSing c++

📄 Page 3

LICENSE, DISCLAIMER OF LIABILITY, AND LIMITED WARRANTY By purchasing or using this book (the “Work”), you agree that this license grants permission to use the contents contained herein, but does not give you the right of ownership to any of the textual content in the book or ownership to any of the information or products contained in it. This license does not permit uploading of the Work onto the Internet or on a network (of any kind) without the written consent of the Publisher. Duplication or dissemination of any text, code, simulations, images, etc. contained herein is limited to and subject to licensing terms for the respective products, and permission must be obtained from the Publisher or the owner of the content, etc., in order to reproduce or network any portion of the textual material (in any media) that is contained in the Work. Mercury Learning and inforMation (“MLI” or “the Publisher”) and anyone involved in the creation, writing, production, accompanying algorithms, code, or computer pro- grams (“the software”), and any accompanying Web site or software of the Work, can- not and do not warrant the performance or results that might be obtained by using the contents of the Work. The author, developers, and the Publisher have used their best efforts to insure the accuracy and functionality of the textual material and/or pro- grams contained in this package; we, however, make no warranty of any kind, express or implied, regarding the performance of these contents or programs. The Work is sold “as is” without warranty (except for defective materials used in manufacturing the book or due to faulty workmanship). The author, developers, and the publisher of any accompanying content, and anyone involved in the composition, production, and manufacturing of this work will not be liable for damages of any kind arising out of the use of (or the inability to use) the algo- rithms, source code, computer programs, or textual material contained in this publica- tion. This includes, but is not limited to, loss of revenue or profit, or other incidental, physical, or consequential damages arising out of the use of this Work. The sole remedy in the event of a claim of any kind is expressly limited to replacement of the book and only at the discretion of the Publisher. The use of “implied warranty” and certain “exclusions” vary from state to state, and might not apply to the purchaser of this product.

📄 Page 4

Data StructureS anD Program DeSign uSing c++ MERCURY LEARNING AND INFORMATION Dulles, Virginia Boston, Massachusetts New Delhi A Self-Teaching Introduction Dheeraj Malhotra Neha Malhotra

📄 Page 5

Copyright © 2019 by Mercury Learning and inforMation LLC. All rights reserved. This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher. Publisher: David Pallai Mercury Learning and inforMation 22841 Quicksilver Drive Dulles, VA 20166 info@merclearning.com www.merclearning.com (800) 232-0223 D. Malhotra and N. Malhotra. Data Structures and Program Design Using C++. ISBN: 978-1-68392-370-1 The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others. Library of Congress Control Number: 2018913035 181920321 Printed on acid-free paper in the United States of America. Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc. For additional information, please contact the Customer Service Dept. at (800) 232-0223(toll free). Digital versions of our titles are available at: www.authorcloudware.com and other electronic vendors. The sole obligation of Mercury Learning and inforMation to the purchaser is to replace the book and/or disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product. Dedicated to our loving parents and beloved students.

📄 Page 6

Dedicated to our loving parents and beloved students.

📄 Page 7

(This page has no text content)

📄 Page 8

Preface xv Acknowledgments xvii 1 Introduction to Data Structures 1 1.1 Introduction 1 1.2 Types of Data Structures 3 1.2.1 Linear and Non-linear Data Structures 3 1.2.2 Static and Dynamic Data Structures 3 1.2.3 Homogeneous and Non-homogeneous Data Structures 4 1.2.4 Primitive and Non-Primitive Data Structures 4 1.2.5 Arrays 5 1.2.6 Queues 6 1.2.7 Stacks 7 1.2.8 Linked List 8 1.2.9 Trees 9 1.2.10 Graphs 11 1.3 Operations on Data Structures 12 1.4 Algorithms 13 1.4.1 Developing an Algorithm 14 1.5 Approaches for Designing an Algorithm 14 1.6 Analyzing an Algorithm 15 1.6.1 Time-Space Trade-off 17 1.7 Abstract Data Types 17 1.8 Big O Notation 18 1.9 Summary 18 1.10 Exercises 20 1.11 Multiple Choice Questions 21 CONTENTS

📄 Page 9

viii • Contents 2 Introduction to the C++ Language 25 2.1 Introduction 26 2.2 C++ and Its Characteristics 26 2.3 Features of Object-Oriented Programming 27 2.4 Character Set Used in C++ 34 2.5 C++ Tokens 34 2.6 Data Types in C++ 36 2.7 Structure of a C++ Program 37 2.7.1 Structure of a C++ Program without Classes 37 2.7.2 Structure of a C++ Program with Classes 37 2.8 Operators in C++ 39 2.9 Decision Control Statements in C++ 45 2.10 Looping Statements in C++ 55 2.11 Break and Continue Statements 61 2.12 Functions in C++ 64 2.12.1 Passing Arguments to Functions 66 2.13 Structures in C++ 68 2.14 Reference Variables in C++ 69 2.15 Pointers 70 2.16 Arrays and Pointers 70 2.17 Summary 72 2.18 Exercises 75 2.18.1 Theory Questions 75 2.18.2 Programming Questions 77 2.18.3 Multiple Choice Questions 78 3 Arrays 81 3.1 Introduction 82 3.2 Definition of an Array 82 3.3 Array Declaration 83 3.4 Array Initialization 84 3.5 Calculating the Address of Array Elements 85 3.6 Operations on Arrays 86 3.7 2-D Arrays/ Two-Dimensional Arrays 110 3.8 Declaration of Two-Dimensional Arrays 110 3.9 Operations on 2-D Arrays 113 3.10 Multidimensional Arrays/ N-Dimensional Arrays 118 3.11 Calculating the Address of 3-D Arrays 118 3.12 Arrays and Pointers 121 3.13 Array of Pointers 122 3.14 Arrays and their Applications 123 3.15 Sparse Matrices 124

📄 Page 10

Contents • ix 3.16 Types of Sparse Matrices 124 3.17 Representation of Sparse Matrices 125 3.18 Summary 127 3.19 Exercises 129 3.19.1 Theory Questions 129 3.19.2 Programming Questions 130 3.19.3 Multiple Choice Questions 131 4 Linked Lists 135 4.1 Introduction 135 4.2 Definition of a Linked List 136 4.3 Memory Allocation in a Linked List 138 4.4 Types of Linked Lists 139 4.4.1 Singly Linked List 139 4.4.2 Operations on a Singly Linked List 140 4.4.3 Circular Linked Lists 159 4.4.4 Operations on a Circular Linked List 160 4.4.5 Doubly Linked List 173 4.4.6 Operations on a Doubly Linked List 174 4.5 Header Linked Lists 192 4.6 Applications of Linked Lists 207 4.7 Polynomial Representation 207 4.8 Summary 207 4.9 Exercises 208 4.9.1 Theory Questions 208 4.9.2 Programming Questions 209 4.9.3 Multiple Choice Questions 209 5 Queues 213 5.1 Introduction 213 5.2 Definition of a Queue 214 5.3 Implementation of a Queue 214 5.3.1 Implementation of Queues Using Arrays 214 5.3.2 Implementation of Queues Using Linked Lists 215 5.3.2.1 Insertion in Linked Queues 215 5.3.2.2 Deletion in Linked Queues 217 5.4 Operations on Queues 222 5.4.1 Insertion 222 5.4.2 Deletion 223 5.5 Types of Queues 227 5.5.1 Circular Queue 227 5.5.1.1 Limitation of Linear Queues 228

📄 Page 11

x • Contents 5.5.1.2 Inserting an Element in a Circular Queue 230 5.5.1.3 Deleting an Element from a Circular Queue 232 5.5.2 Priority Queue 237 5.5.2.1 Implementation of a Priority Queue 239 5.5.2.2 Insertion in a Linked Priority Queue 241 5.5.2.3 Deletion in a Linked Priority Queue 242 5.5.3 De-queues (Double-Ended Queues) 246 5.6 Applications of Queues 252 5.7 Summary 252 5.8 Exercises 253 5.8.1 Theory Questions 253 5.8.2 Programming Questions 253 5.8.3 Multiple Choice Questions 254 6 Searching and Sorting 257 6.1 Introduction to Searching 257 6.2 Linear Search or Sequential Search 258 6.2.1 Drawbacks of a Linear Search 261 6.3 Binary Search 263 6.3.1 Binary Search Algorithm 263 6.3.2 Complexity of a Binary Search Algorithm 266 6.3.3 Drawbacks of a Binary Search 266 6.4 Interpolation Search 269 6.4.1 Working of the Interpolation Search Algorithm 269 6.4.2 Complexity of the Interpolation Search Algorithm 271 6.5 Introduction to Sorting 273 6.5.1 Types of Sorting Methods 274 6.6 External Sorting 299 6.7 Summary 300 6.8 Exercises 301 6.8.1 Theory Questions 301 6.8.2 Programming Questions 302 6.8.3 Multiple Choice Questions 303 7 Stacks 305 7.1 Introduction 305 7.2 Definition of a Stack 306 7.3 Overflow and Underflow in Stacks 307 7.4 Operations on Stacks 308 7.5 Implementation of Stacks 314 7.5.1 Implementation of Stacks Using Arrays 314 7.5.2 Implementation of Stacks Using Linked Lists 315

📄 Page 12

Contents • xi 7.5.2.1 Push Operation in Linked Stacks 315 7.5.2.2 Pop Operation in Linked Stacks 316 7.6 Applications of Stacks 320 7.6.1 Polish and Reverse Polish Notations and Their Need 321 7.6.2 Conversion from Infix Expression to Postfix Expression 321 7.6.3 Conversion from Infix Expression to Prefix Expression 329 7.6.4 Evaluation of a Postfix Expression 335 7.6.5 Evaluation of a Prefix Expression 340 7.6.6 Parenthesis Balancing 344 7.7 Summary 348 7.8 Exercises 348 7.8.1 Theory Questions 348 7.8.2 Programming Questions 350 7.8.3 Multiple Choice Questions 350 8 Trees 353 8.1 Introduction 353 8.2 Definitions 355 8.3 Binary Tree 357 8.3.1 Types of Binary Trees 358 8.3.2 Memory Representation of Binary Trees 359 8.4 Binary Search Tree 362 8.4.1 Operations on Binary Search Trees 363 8.4.2 Binary Tree Traversal Methods 379 8.4.3 Creating a Binary Tree Using Traversal Methods 387 8.5 AVL Trees 391 8.5.1 Need of Height-Balanced Trees 392 8.5.2 Operations on an AVL Tree 393 8.6 Summary 404 8.7 Exercises 406 8.7.1 Theory Questions 406 8.7.2 Programming Questions 409 8.7.3 Multiple Choice Questions 410 9 Multi-Way Search Trees 415 9.1 Introduction 415 9.2 B-Trees 416 9.3 Operations on a B-Tree 417 9.3.1 Insertion in a B-Tree 418 9.3.2 Deletion in a B-Tree 420 9.4 Application of a B-Tree 426

📄 Page 13

xii • Contents 9.5 B+ Trees 426 9.6 Summary 428 9.7 Exercises 428 9.7.1 Review Questions 428 9.7.2 Multiple Choice Questions 429 10 Hashing 433 10.1 Introduction 433 10.1.1 Difference between Hashing and Direct Addressing 435 10.1.2 Hash Tables 436 10.1.3 Hash Functions 437 10.1.4 Collision 440 10.1.5 Collision Resolution Techniques 440 10.1.5.1 Chaining Method 440 10.1.5.2 Open Addressing Method 446 10.2 Summary 462 10.3 Exercises 463 10.3.1 Review Questions 463 10.3.2 Multiple Choice Questions 464 11 Files 467 11.1 Introduction 467 11.2 Terminologies 468 11.3 File Operations 468 11.4 File Classification 469 11.5 C vs C++ File Handling 470 11.6 File Organization 471 11.7 Sequence File Organization 471 11.8 Indexed Sequence File Organization 473 11.9 Relative File Organization 474 11.10 Inverted File Organization 475 11.11 Summary 475 11.12 Exercises 476 11.12.1 Review Questions 476 11.12.2 Multiple Choice Questions 477 12 Graphs 479 12.1 Introduction 479 12.2 Definitions 481 12.3 Graph Representation 486 12.3.1 Adjacency Matrix Representation 486 12.3.2 Adjacency List Representation 489

📄 Page 14

Contents • xiii 12.4 Graph Traversal Techniques 492 12.4.1 Breadth First Search 492 12.4.2 Depth First Search 496 12.5 Topological Sort 500 12.6 Minimum Spanning Tree 504 12.6.1 Prim’s Algorithm 505 12.6.2 Kruskal’s Algorithm 508 12.7 Summary 512 12.8 Exercises 513 12.8.1 Theory Questions 513 12.8.2 Programming Questions 516 12.8.3 Multiple Choice Questions 517 Appendix A 519 Answers to Selected Exercises 519 Appendix B 525 References/ Books/ Webliography 525 Index 533

📄 Page 15

(This page has no text content)

📄 Page 16

Data structures are the building blocks of computer science. The objective of this text is to emphasize the fundamentals of data structures as an introductory subject. It is designed for beginners who would like to learn the basics of data structures and their implementation using the C++ programming language. With this focus in mind, we present various fundamentals of the subject, well sup- ported with real-world analogies to enable a quick understanding of the technical concepts and to help in identifying appropriate data structures to solve specific, practical problems. This book will serve the purpose of a text/reference book and will be of immense help especially to undergraduate or graduate students of vari- ous courses in information technology, engineering, computer applications, and information sciences. Key Features: • Practical Applications: Real world analogies as practical applications are given throughout the text to quickly understand and connect the fundamentals of data structures with day to day, real-world scenarios. This approach, in turn, will assist the reader in developing the capability to identify the most appropriate and efficient data structure for solving a specific, real-world problem. • Frequently Asked Questions: Frequently asked theoretical/practical questions are integrated throughout the content of the book, within related topics to assist readers in grasping the subject. • Algorithms and Programs: To better understand the fundamentals of data structures at a generic level-followed by its object-oriented implementation PREFACE

📄 Page 17

xvi • PReFACe in C++, syntax independent algorithms, as well as implemented programs in C++, are discussed throughout the book. This presentation will assist the reader in getting both algorithms and their corresponding implementation within a single book. • Numerical and Conceptual Exercises: To assist the reader in developing a strong foundation of the subject, various numerical and conceptual problems are included throughout the text. • Multiple Choice Questions: To assist students for placement-oriented exams in various IT fields, several exercises are suitably chosen and are given in an MCQ format. Dheeraj Malhotra Neha Malhotra November 2018

📄 Page 18

ACKNOWLEDGMENTS It is our pleasure to take this opportunity to sincerely thank the people who have extended their kind help and support to us throughout this project. We are indeed grateful to Chairman VIPS- Dr. S.C. Vats, respected management, faculty and staff members of Vivekananda Institute of Professional Studies (GGS IP University). They are always a source of inspiration for us, and we feel honored because of their faith in us. We also take this opportunity to extend our gratitude to our mentors Dr. O.P. Rishi (University of Kota), Dr. Jatinder Singh (IKG Punjab Technical University) and Dr. Udyan Ghose (GGS IP University) for their motivation to execute this project. We are profoundly thankful to Mr. Deepanshu Gupta (VIPS, GGSIPU) for helping us in compiling the codes in this manuscript. It is not possible to complete a book without the support of a publisher. We are thankful to David Pallai and Jennifer Blaney of Mercury Learning and Information for their enthusiastic involvement throughout the tenure of this project. Our heartfelt regards to our parents, siblings and family members who cheered us in good times and encouraged us in bad times. Lastly, we have always felt inspired by our students. Their questioning minds enriched our knowledge, which we have presented in this book. Dheeraj Malhotra Neha Malhotra November 2018

📄 Page 19

(This page has no text content)

📄 Page 20

C H A P T E R1 INTRODUCTION TO DATA STRUCTURES In This Chapter l Introduction l Types of data structures l Operations on data structures l Algorithms l Approaches for designing an algorithm l Analyzing an algorithm l Abstract data types l Big O notation l Summary 1.1 Introduction A data structure is an efficient way of storing and organizing the data elements in the computer memory. Data means a value or a collec- tion of values. Structure refers to a method of organizing the data. The mathematical or logical representation of data in the memory is referred as a data structure. The objective of a data structure is to store, retrieve, and update the data efficiently. A data structure can be referred to as