Data Structures Through C++ (4th Ed.) (Yashavant Kanetkar) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 6.1 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

(This page has no text content)

📄 Page 3

Data Structures Through C++ 4th Edition Yashavant Kanetkar www.bpbonline.com

📄 Page 4

FIRST EDITION 2019 Fourth Revised & Updated Edition 2022 Copyright © BPB Publications, India ISBN: 978-93-5551-188-1 All Rights Reserved. No part of this publication may be reproduced, distributed or transmitted in any form or by any means or stored in a database or retrieval system, without the prior written permission of the publisher with the exception to the program listings which may be entered, stored and executed in a computer system, but they can not be reproduced by the means of publication, photocopy, recording, or by any electronic and mechanical means. LIMITS OF LIABILITY AND DISCLAIMER OF WARRANTY The information contained in this book is true to correct and the best of author’s and publisher’s knowledge. The author has made every effort to ensure the accuracy of these publications, but publisher cannot be held responsible for any loss or damage arising from any information in this book. All trademarks referred to in the book are acknowledged as properties of their respective owners but BPB Publications cannot guarantee the accuracy of this information. www.bpbonline.com

📄 Page 5

Dedicated to Prabhakar Kanetkar

📄 Page 6

About the Authors Through his books and Quest Video Courseware DVDs on C, C++, Data Structures, VC++, .NET, Embedded Systems, etc. Yashavant Kanetkar has created, moulded and groomed lacs of IT careers in the last two and half decades. Yashavant’s books and Quest DVDs have made a significant contribution in creating top‐notch IT manpower in India and abroad. Yashavant’s books are globally recognized and millions of students / professionals have benefitted from them. Yashavant’s books have been translated into Hindi, Gujarati, Japanese, Korean and Chinese languages. Many of his books are published in India, USA, Japan, Singapore, Korea and China. Yashavant is a much sought‐after speaker in the IT field and has conducted seminars/workshops at TedEx, IITs, RECs and global software companies. Yashavant has been honored with the prestigious “Distinguished Alumnus Award” by IIT Kanpur for his entrepreneurial, professional and academic excellence. This award was given to top 50 alumni of IIT Kanpur who have made significant contribution towards their profession and betterment of society in the last 50 years. In recognition of his immense contribution to IT education in India, he has been awarded the “Best .NET Technical Contributor” and “Most Valuable Professional” awards by Microsoft for 5 successive years. Yashavant holds a BE from VJTI Mumbai and M.Tech. from IIT Kanpur. Yashavant’s current affiliations include being a Director of KICIT Pvt. Ltd. and KSET Pvt. Ltd. He can be reached at kanetkar@kicit.com or through http://www.kicit.com.

📄 Page 7

Acknowledgments Though what matters most in a book are its contents, it is the parts of the whole like cover, internal layout, digital extras, price etc. that make it an attractive proposition. I have been fortunate to get help and cooperation from many individuals involved in this book project. Though the book cover bears only my name, it truly reflects the collective wisdom of numerous students to whom I taught “Data Structures” for several years. I have learnt a lot from them. Many thanks, wherever you are. Writing and testing programs in a book is a monumental task calling for incredible patience. That Vineeta Prasad, Anil Gakhare and Monali Mohadikar had loads of it is chiefly responsible for getting the book in its current form. They also ensured that we chose the right algorithms while implementing the additional programs present in the downloadable DVD. “Experience data structures through animations”—that is the main theme of this book. Neeraj Srivastav took the responsibility of creating excellent animations while following stringent timelines. M.S. Prakash wrote instructions for installing and using the programs on the DVD. Many thanks to both of you. An author needs a lot of support from his publisher. That Manish Jain of BPB provides in abundance in my every book project. Bureaucracy and quiet indifference are the words which do not figure in his dictionary. And lastly many thanks to my wife Seema who cheered me in good times, encouraged me in bad times and understood me at all times. If I ever wear a hat, it would be off to her!!

📄 Page 8

Contents Introduction 1. Analysis of Algorithms Why Analyze Algorithms? Analysis of Algorithms What to Consider, What to Ignore? Rates of Growth Comparison of Growth Rates Asymptotic Notation for Analysis of Algorithms Big O Notation Big Ω Notation Big θ Notation Other Notations Asymptotic Analysis Examples Determining Time Complexity Types of Input to Consider During Analysis Is Asymptotic Analysis Perfect? Types of Algorithms Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 2. Arrays Arrays Two‐Dimensional Arrays Row Major and Column Major Arrangement Common Matrix Operations Multidimensional Arrays Arrays and Polynomials Multiplication of Polynomials Chapter Bullets Check Your Progress

📄 Page 9

Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 3. Linked Lists What is a Linked List? Operations on A Linked List More Linked Lists Reversing the Links A Few More Operations Recursive Operations on Linked List Doubly Linked Lists Function d_append() Function d_addatbeg() Function d_addafter() Function d_delete() Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 4. Sparse Matrices Representation of Sparse Matrix as an Array Common Matrix Operations Transpose of a Sparse Matrix Addition of Sparse Matrices Linked Representation of a Sparse Matrix Other Forms of a Sparse Matrix Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 5. Stacks Stack as an Array

📄 Page 10

Stack as a Linked List Applications of Stacks Infix to Postfix Conversion Postfix to Prefix Conversion Other Inter‐Conversions Evaluation of Postfix Expression Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 6. Queues Queue as an Array Queue as a Linked‐List Circular Queue Deque Priority Queue Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 7. Trees Binary Trees Representation of Binary Trees in Memory Linked Representation of Binary Trees Array Representation of Binary Trees Binary Search Trees Operations on a Binary Search Tree Insertion of a Node Traversal of a BST Searching of a Node Deletion of a Node Reconstruction of a Binary Tree Threaded Binary Tree

📄 Page 11

AVL Trees Binary Heap Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 8. Graphs Definitions and Terminology Adjacent Vertices and Incident Edges Graph Representations Adjacency Matrix Adjacency Lists Adjacency Multi‐lists Graph Traversals Depth First Search Breadth First Search Spanning tree Kruskal’s Algorithm Prim’s Algorithm Shortest Path Dijkstra’s Algorithm Topological Sorting Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise 9. Searching And Sorting Searching Linear Search Binary Search Recursive Binary Search Sorting Internal Sorting

📄 Page 12

External Sorting Internal Sorting Bubble Sort Selection Sort Insertion Sort Quick Sort Binary Tree Sort Merge Sort Heap Sort Chapter Bullets Check Your Progress Sharpen Your Skills Coding Interview Questions Case Scenario Exercise Index

📄 Page 13

Introduction Technical book writing is a simple job. Pick a topic that appeals to you, spend some time understanding it, browse the net for some additional information and then keep writing till the time you do not reach the end. Easier said than done! In fact, nothing can be farther from the truth. For one, choosing the right subject is pretty confusing with so many subjects and technologies taking so big strides in the recent years. Secondly, none of them is so easy to master in a few months and thirdly presenting what you have understood in a simple manner is not everybody’s cup of tea. I have realized all these facts more emphatically while writing this book, because I have been writing this book for last 10 years!! It all began with attempting to write articles that would explain Quick Sort algorithm and Threaded Binary Trees. Once I had a critical mass of written material, I thought of compiling it in the form of a book. I however wanted the book to be a different data structures book. Different in the sense that, it should go beyond merely explaining how typical data structures like stacks, queues and linked lists work. I wanted the readers to experience sorting of an array, traversing of a doubly linked list, construction of a binary tree, etc. I had a hell of a time imagining, understanding and programming these complicated data structures. I wanted that the readers of this book should not be required to undergo that agony. And today I am satisfied that I have been able to achieve this through the downloadable DVD. It lets the reader experience the working of different data structures through carefully prepared animations. I have pinned my hopes that the readers would appreciate this approach. The DVD is available at https://bit.ly/2VjEwiu I have tried to make this book different in one more way. Instead of merely learning how to perform different operations on a linked list, I think one can appreciate it better if one comes to the practical applications of it. There are

📄 Page 14

numerous such examples and I have also tried to provide animations for most of them on the downloadable DVD. Apart from this I have tried to explain all data structures with examples and figures. I have also provided exercises at the end of each chapter to hone your skills. In the 4th edition I have done a major overhaul of the “Analysis of Algorithms” chapter, making it more comprehensible by explaining this difficult topic with numerous examples. I hope the readers would like it. I have also eliminated those algorithms and programs that are not commonly used and are of only academic importance. In this edition you would also find a lot consistency in the style of programming adopted while implementing different algorithms. Yashavant Kanetkar

📄 Page 15

Chapter 01 Analysis of Algorithms Justifying the means

📄 Page 16

Why This Chapter Matters? The dictum “ends justify the means” doesn’t hold good in Computer Science. Just because we got the right answer (end) does not mean that the method (means) that we employed to obtain it was correct. In fact, the efficiency of obtaining the correct answer is largely dependent on the method employed to obtain it. Hence scientific analysis of performance of the method is very important.

📄 Page 17

The method of solving a problem is known as an algorithm. More precisely, an algorithm is a sequence of instructions that act on some input data to produce desired output in a finite number of steps. An algorithm must have the following properties: (a) Input – An algorithm must receive some input data supplied externally. (b) Output – An algorithm must produce at least one output as the result. (c) Finiteness – No matter what the input might be, the algorithm must terminate after a finite number of steps. For example, a procedure which goes on performing a series of steps infinitely is not an algorithm. (d) Definiteness – The steps to be performed in the algorithm must be clear and unambiguous. (e) Effectiveness – One must be able to perform the steps in the algorithm without applying any intelligence. For example, the step—Select three numbers which form a Pythagorean triplet—is not effective. Why Analyze Algorithms? Multiple algorithms may exist for solving a given problem. So, to be able to decide which algorithm to use, we need to analyze algorithms. There can be multiple yardsticks to determine which algorithm is better than the other. These include: (a) Robustness – Is the algorithm robust enough to tackle all types of valid and invalid inputs. (b) Maintainability – Is it easy to alter the algorithm as needs change in future. (c) Scalability – Can the algorithm deal with increase in the number of inputs. (d) Modularity – Can the algorithm be broken down into smaller sections (modules). (e) Security – Can the algorithm deal with malicious attacks. (f) User-friendliness – Is it easy to use the algorithm. (g) Performance (efficiency) – Does the algorithm take less time and memory space when implemented in a program and executed.

📄 Page 18

Of these, the most popular yardstick used to analyze algorithms is performance. This is because it is easy to quantify time and space requirements of an algorithm. Analysis of Algorithms One might feel that with faster computers and increasingly cheaper memory space should we bother about speed and space required by an algorithm anymore. We should. That is because though the computers have become faster and memory cheaper, the size of data has also grown exponentially. Imagine the tasks like searching a popular web page from 30 trillion web pages, match a sequence in genomic data set, etc. So, unless we chose the right algorithm to work on such huge datasets, we would end up spending more time and space while performing these operations. Moreover, analysis of algorithms gives us a scientific basis to determine which algorithm should be chosen to solve the problem. Also, on analyzing algorithms we can communicate to others about the performance or efficiency of an algorithm using a specific notation (discussed later). This analysis is done by comparing the time and/or space required for executing the algorithms. Often, there is a trade-off between time and space. In this chapter we would analyze algorithms on the basis of time. We would carry out space-based analysis in later chapters. While doing time-based analysis of algorithms we do not use conventional time units like seconds or minutes required for executing the algorithms. There are two reasons for this. (a) A worse algorithm may take less time units to execute if we move it to a faster computer, or use a more efficient programming language to implement it. (b) We are interested in relative efficiency of different algorithms rather than the exact time for one. While analyzing an algorithm, it is assumed that all operations take same time units to perform on any computer. So, instead of time units we consider the number of prominent operations that are carried out by the algorithm. For example, in a searching algorithm we would try to determine the number of comparisons that are done to search a value in a list of values. Or in an

📄 Page 19

algorithm to add two matrices, we might determine the number of arithmetic operations it performs. Once we identify the prominent operations in an algorithm, we try to build a function that relates the number of times these operations are performed to the size of the input. Once these functions are formed for algorithms under consideration, we can compare them by comparing the rate at which the functions grow as the input gets larger. This growth rate is critical since there are situations where one algorithm needs fewer operations than the other when the input size is small, but many more when the input size becomes larger. The steps involved in analyzing two algorithms are shown in Figure 1.1. Figure 1-1. Steps involved in analyzing algorithms. What to Consider, What to Ignore?

📄 Page 20

It is very important to decide which operations to consider and which operations to ignore while analyzing an algorithm. For this we must first identify which is the significant time-consuming operation(s) in the algorithm. Once that is decided, we should determine which of these operations are integral to the algorithm and which merely contribute to the overheads. There are two classes of operations that are typically chosen for the significant operation—comparison or arithmetic. For example, in Searching and Sorting algorithms the important task being done is the comparison of two values. While searching, the comparison is done to check if the value in a set matches the one, we are looking for, whereas in sorting the comparison is done to see whether values being compared are out of order. The arithmetic operations fall under two groups—additive and multiplicative. Additive operators include addition, subtraction, increment, and decrement. Multiplicative operators include multiplication, division, and modulus. Let us now see an example to determine which operations we should consider and which we should ignore while analyzing an algorithm. Suppose we wish to count the number of characters in a file. The algorithm to do this is given below. 1: Count = 0 2: While (condition – is there a character available for reading from file) 3: do 4: Increment Count by 1 5: Get the next character 6: End while 7: Print Count If there are 500 characters present in the file, then number of times each step is performed would be as follows: 1: Initialize count – 1 2: Conditional checks – 500 + 1 (+1 is for last check) 4: Increment Count – 500 5: Get next character – 500 7: Print Count – 1 As can be seen from these numbers, conditional checks, the number of increments and get next character and are far too many as compared to number