Data Structure and Algorithms Using C++. Sachi Nandan Mohanty

their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials, or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read.

       Library of Congress Cataloging-in-Publication Data

      ISBN 978-1-119-75054-3

      Cover image: Pixabay.Com

      Cover design by Russell Richardson

      Set in size of 11pt and Minion Pro by Manila Typesetting Company, Makati, Philippines

      Printed in the USA

      10 9 8 7 6 5 4 3 2 1

      Preface

      Welcome to the first edition of Data Structures Using and Algorithms C++. A data structure is the logical or mathematical arrangement of data in memory. To be effective, data has to be organized in a manner that adds to the efficiency of an algorithm and also describe the relationships between these data items and the operations that can be performed on these items. The choice of appropriate data structures and algorithms forms the fundamental step in the design of an efficient program. Thus, a deep understanding of data structure concepts is essential for students who wish to work on the design and implementation of system software written in C++, an object-oriented programming language that has gained popularity in both academia and industry. Therefore, this book was developed to provide comprehensive and logical coverage of data structures like stacks, queues, linked lists, trees and graphs, which makes it an excellent choice for learning data structures. The objective of the book is to introduce the concepts of data structures and apply these concepts in real-life problem solving. Most of the examples presented resulted from student interaction in the classroom. This book utilizes a systematic approach wherein the design of each of the data structures is followed by algorithms of different operations that can be performed on them and the analysis of these algorithms in terms of their running times.

      This book was designed to serve as a textbook for undergraduate engineering students across all disciplines and postgraduate level courses in computer applications. Young researchers working on efficient data storage and related applications will also find it to be a helpful reference source to guide them in the newly established techniques of this rapidly growing research field.

      Dr. Sachi Nandan Mohanty and Prof. Pabitra Kumar Tripathy December 2020

      1

      Introduction to Data Structure

      1.1 Definition and Use of Data Structure

      Data structure is the representation of the logical relationship existing between individual elements of data. In other words the data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.

      Data structure specifies

       Organization of data

       Accessing methods

       Degree of associativity

       Processing alternatives for information

      The data structures are the building blocks of a program and hence the selection of a particular data structure stresses on

       The data structures must be rich enough in structure to reflect the relationship existing between the data, and

       The structure should be simple so that we can process data effectively whenever required.

      In mathematically Algorithm + Data Structure = Program

      Finally we can also define the data structure as the “Logical and mathematical model of a particular organization of data”

1.2 Types of Data Structure

      Data structure can be broadly classified into two categories as Linear and Non-Linear

       Linear Data Structures

      In linear data structures, values are arranged in linear fashion. Arrays, linked lists, stacks, and queues are the examples of linear data structures in which values are stored in a sequence.

       Non-Linear Data Structure

      This type is opposite to linear. The data values in this structure are not arranged in order. Tree, graph, table, and sets are the examples of nonlinear data structure.

       Operations Performed in Data Structure

      In data structure we can perform the operations like

       Traversing

       Insertion

       Deletion

       Merging

       Sorting

       Searching

1.3 Algorithm

      The step by step procedure to solve a problem is known as the ALGORITHM. An algorithm is a well-organized, pre-arranged, and defined computational module that receives some values or set of values as input and provides a single or set of values as out put. These well-defined computational steps are arranged in sequence, which processes the given input into output.

      An algorithm is said to be accurate and truthful only when it provides the exact wanted output.

      The efficiency of an algorithm depends on the time and space complexities. The complexity of an algorithm is the function which gives the running time and/or space in terms of the input size.

       Steps Required to Develop an Algorithm

       Finding a method for solving a problem. Every step of an algorithm should be defined in a precise and in a clear manner. Pseudo code is also used to describe an algorithm.

       The next step is to validate the algorithm. This step includes all the steps in our algorithm and should be done manually by giving the required input, perform the required steps including in our algorithm and should get the required amount of output in a finite amount of time.

       Finally implement the algorithm in terms of programming language.

       Mathematical Notations and Functions

       ❖ Floor and Ceiling