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

361 363

362 364

363 365

364 366

365 367

366 368

367 369

368 370

369 371

370 372

371 373

372 374

373 375

374 376

375 377

376 378

377 379

378 380

379 381

380 382

381 383

382 384

383 385

384 386

385 387

386 388

387 389

388 391

389 392

390 393

391 394

392 395

393 397

394 398

395 399

396 400

397 401

Scrivener Publishing100 Cummings Center, Suite 541J Beverly, MA 01915-6106

Publishers at Scrivener Martin Scrivener ( martin@scrivenerpublishing.com) Phillip Carmical ( pcarmical@scrivenerpublishing.com)

Edited by

Sachi Nandan Mohanty

ICFAI Foundation For Higher Education, Hyderabad, India

and

Pabitra Kumar Tripathy

Kalam Institute of Technology, Berhampur, India

This edition first published 2021 by John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA and Scrivener Publishing LLC, 100 Cummings Center, Suite 541J, Beverly, MA 01915, USA © 2021 Scrivener Publishing LLC

For more information about Scrivener publications please visit www.scrivenerpublishing.com.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

Wiley Global Headquarters

111 River Street, Hoboken, NJ 07030, USA

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Limit of Liability/Disclaimer of Warranty

While the publisher and authors have used 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

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 TripathyDecember 2020

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”

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