Anand Classes

Data Structure Using C/C++ Download E-Content Lecture Notes Books pdf Study Material Online|Anand Classes|Neeraj K Anand

Data Structure Using C/C++ Download E-Content Lecture Notes Books pdf Study Material Online|Anand Classes|Neeraj K Anand

Data Structure Using C/C++ Download E-Content Lecture Notes Books pdf Study Material Online|Anand Classes|Neeraj K Anand

Author’s Words

 I strongly believe that the Almighty God alone plans every thing that happens in the world. So, I sincerely thanks the Almighty God for showering his blessings upon me and using me to write this book.

I wish to express my deep sense of gratitude to my colleagues and students whom encouragement and co-operation have been source of great inspiration to me. I am thankful to my father Sh. Om Prakash Anand, my son Param Anand and my dear wife Neetu Anand for bringing me out this book. I hope that this edition of the book will prove to be more useful to the Science and Engineering students. Any suggestions for further improvement of the book will be gratefully acknowledged by the both author and publisher. Finally, we would like to thank my colleagues in the various Institutes whom have encouraged and assisted us to make our best efforts in bringing out this book.                                                               

                                                                                                                          NIT – Warangal, Telangana

                                                                                                                          Neeraj K. Anand

                                                                                                                         November 2021

Dedication

In The Everlasting Memory of My Mother

Late Smt. Nirmal Anand

About The Book

This introduction to the fundamentals of data structures explores abstract concepts, considers how those concepts are useful in problem solving, explains how the abstractions can be made concrete by using a programming language, and shows how to use the C language for advanced programming and how to develop the advanced features of C++. It features a wealth of tested and debugged working programs in C and C++. The purpose of this book is to give breadth and depth to C++ programmers’ existing experience of the language by representing a large number of algorithms, most of them implemented as ready-to-run (and standalone) programs. The programs are as readable as possible without sacrificing too great a degree of efficiency, generality, portability and robustness. Both the classes and programs are designed to demonstrate major programming principles. There is coverage of two key language features – templates and exception handling – apart from which the reader is assumed to have working knowledge of C++. Besides traditional subjects, such as quicksort and binary trees, this book also covers some less well-known topics, including multi-precision arithmetic, route planning and external sorting. Demonstration programs for these and many other exciting applications are based on C++ classes which you can also use in programs of your own.

Book Contents

CHAPTER – 1

INTRODUCTION TO DATA STRUCTURES

BASIC TERMINOLOGY OF DATA ORGANIZATION            9

An Introduction to Data Structures 13

CLASSIFICATION OF DATA STRUCTURES  14

Graph TERMINOLOGY                                26

Operations on data structures        26

Algorithms                                                 27

STRUCTURED PROGRAMMING CONSTRUCTS       29

Algorithm complexity                          34

SPACE COMPLEXITY                                     35

time COMPLEXITY                                       35

EXACT MEASUREMENT OF ALGORITHM’S TIME COMPLEXITY 40

BIG-Oh NOTATION                                         43

Simple Rules for O-Notation               45

Categories of Time complexity          46

LIMITATIONs OF BIG “Oh” NOTATION        47

OTHER ASYMPTOTIC NOTATIONS              48

BIG OMEGA NOTATION                                48

BIG-THETA NOTATION                                 48

BEST, AVERAGE AND WORST CASE           49

TIME-SPACE TRADE OFF                              52

AMSTRONG COMPLEXITY                           52

General-Purpose Data Structures   52

CHAPTER – 2

STRING PROCESSING

STORING STRINGS                                        56

Record-Oriented, Fixed-Length Storage         56

Variable Length Storage with Fixed Maximum       56

Linked Storage                                         56

Declaring and Initializing Strings  57

Inputting multiword string               59

Inputting multiline string                  60

Standard Library String Functions                 60

CHAPTER – 3

ARRAY PROCESSING

Linear Array                                             67

Memory Representation OF ARRAYS  68

Various Operations Associated with Arrays      69

traversing an Array                             69

insertion into and deletion from an ARRAY        72

DELETION operation                                 76

Bubble Sort                                                79

linear search                                            86

Algorithm details of Linear Search 87

binary search                                           89

Algorithm detail of Binary Search 90

complexity of Binary Search             95

Comparing complexity of linear Search and binary search           95

Multidimensional Arrays                    96

TWO – DIMENSIONAL ARRAYS                    96

Row Major Ordering                               98

column Major Ordering                       99

General Multidimensional Arrays 101

POINTER ARRAYS AND JAGGED ARRAY  108

SPARSE MATRICES                                          110

 

CHAPTER – 4

LINKED LISTS

LINKED LISTS                                              116

ADVANTAGES AND DISADVANTAGES of A linked list          117

LINKED LIST V/S ARRAYS                          119

OPERATIONs ON A LINKED LIST               118

array representation of linked list in memory            119

Available List                                         121

Another Case of linked list              122

Traversing a linked list                     123

Problems with array representation        125

Searching a linked list                       125

SEARCHING IN AN UNSORTED LINKED LIST 125

SEARCHING IN A SORTED LINKED LIST   127

Memory Allocation                              129

OVERFLOW AND UNDERFLOW                  129

garbage collection                             130

Insertion into a linked list               131

Insertion Algorithms                           132

Inserting at the Beginning of a List 133

Insertion after a Given Node            135

Inserting at the End of the List       136

Insertion into a Sorted Linked List 138

DELETION FROM A LINKED LIST               142

Deletion Algorithms                            144

Deleting the Node Following a Given Node         145

Deleting the Node with a Given ITEM of Information   146

Header Linked Lists                               153

CIRCULAR LINKED LISTS                           154

Searching in A circular header list 155

delete the node which contains ITEM 156

TWO-WAY LISTS                                          160

Two-Way Header Lists                          162

Operations on Two-Way Lists            162

Polynomial manipulation                  166

ADDITION OF POLYNOMIALS                    167

POLYNOMIAL OF MULTIPLE VARIABLES 170

MULTILINKED LIST                                     172

APPLICATIONS OF LINKED LISTS            174

 

CHAPTER – 5

STACKS

Stack Implementation using array 176

OPERATIONS PERFORMED ON STACK      177

POP (STACK, TOP, ITEM)                             179

Efficiency of Stacks                             180

APPLICATIONS OF STACK                          190

REVERSING DATA                                       191

arithmetic expressions : polish notation 181

Precedence of Operators                   182

Reverse Polish Notation                     182

converting Infix to postfix expression     184

algorithm Evaluation of a Postfix Expression  185

Algorithm evaluation Infix into Postfix Expressions 188

QUICK SORT                                                 192

quicksort technique using stack   194

Complexity of the Quicksort Algorithm  198

The Towers of Hanoi                             205

 

CHAPTER – 6

RECURSION

advantages and disadvantages of recursion   209

Recursion vs. Iteration                        209

 

CHAPTER – 7

QUEUES

BASIC QUEUE OPERATIONS                       212

ENQUEUE                                                     212

DEQUEUE                                                     212

FRONTPEEK                                                  213

rearPEEK                                                    213

Representation of Queues                  214

ARRAY REPRESENTATION of QUEUE      214

ENQUEUE operation                                214

deQUEUE operation                                216

CIRCULAR QUEUE                                       218

LINKED REPRESENTATION OF A QUEUE  223

DEQUES                                                        227

Priority Queues                                       229

ARRAY REPRESENTATION OF PRIORITY QUEUE  231

MULTI-LEVEL PRIORITY QUEUE               232

One-Way List Representation of a Priority Queue         234

Efficiency of Priority Queues           236

 

CHAPTER – 8

TREES

Tree Terminology                                  238

Definition of a Tree                               241

Binary Tree                                               242

PROPERTIES OF BINARY TREES                 244

BINARY TREE REPRESENTATION              245

ARRAY REPRESENTATION of Binary Trees      245

Linked Representation of Binary Trees     247

Traversing the Tree                             248

Inorder Traversal                                249

Algorithm : INORDER Traversal of binary tree  250

recursive algorithm                            253

preorder Traversal                             254

Algorithm : PRE-ORDER Traversal of binary tree          255

recursive algorithm                            258

postorder Traversal                           259

Binary tree construction                 266

Types of binary trees                           269

Expression Trees                                     269

binary search tree (BST)                     273

Traversal on BST                                   274

SEARCHING FOR A TARGET KEY IN A BINARY SEARCH TREE   275

Inserting a Node into a binary search tree        276

Complexity of the Searching Algorithm  280

deletion a Node from a binary search tree        280

DELETION algorithms                            282

Heaps – Priority Queues                        287

ARRAY REPRESENTATION OF HEAP TREE 288

OPERATIONS ON HEAP TREES                   289

Heapsort – application of heap         293

heapsort algorithm                             295

Complexity of Heapsort                      296

THREADED BINARY TREES                        297

ADVANTAGES OF THREADED BINARY TREES      299

disADVANTAGES OF THREADED BINARY TREES            300

WEIGHTED BINARY TREE : HUFFMAN TREE 300

m-WAYTREE                                                 306

implementing priority queue using heap tree    308

Avl tree                                                     309

AVL ROTATION                                               310

 

CHAPTER – 9

GRAPHS

Graph TERMINOLOGY                               319

SIMPLE GRAPH                                            319

multiGRAPHs                                             320

Finite Graphs, Trivial Graph              320

Degree                                                        321

THE HANDSHAKING THEOREM                 322

DEGREE SEQUENCE                                    324

ADJACENCY MATRIX OF A GRAPH           324

INCIDENCE MATRIX OF A SIMPLE GRAPH 326

DIRECTED GRAPH                                       327

Subgraphs                                                 328

Directed graph terminology            328

COMPLETE GRAPH                                      330

CONNECTED GRAPH                                   330

WEIGHTED GRAPH                                      331

ADJACENCY MATRIX OF A directed GRAPH     332

Path Matrix                                              334

WARSHALL’S ALGORITHMs : SHORTEST PATHS  335

Shortest- path Algorithm                  339

linked Representation of graphs   348

OPERATIONS ON GRAPHS                          351

Inserting a node in a Graph               351

Procedure : inserts the node in the graph G.       352

Searching in a Graph                            353

the first node containing ITEM        353

Inserting an edge in a Graph             354

deletion a node from a Graph          355

DELETING AN EDGE FROM THE GRAPH   356

DELETING A node FROM THE GRAPH whose address is loc           357

TRAVERSING A GRAPH                               358

Depth-first Search (DFS)                      358

breadth-first Search (BFS)                 362

DijKSTRA SHORTEST PATH ALGORITHM  366

 

CHAPTER – 10

SORTING AND SEARCHING

Insertion Sort                                         375

Complexity of Insertion Sort           378

SELECTION Sort                                         379

Merging Two Sorted Arrays             381

Complexity of the Merging Algorithm      384

merge-sort                                               384

radix/Bucket sort                                 389

CHAPTER – 11

HASHING TECHNIQUES

HASH FUNCTIONs                                       395

DIRECT METHOD                                         396

DIVISION METHOD                                      397

Mid Square Method                               398

folding Method                                      398

HASH collision                                         399

Open Addressing                                     400

Chaining                                                         403

 

CHAPTER – 12

FILE ORGANIZATION

BASIC FILE TERMINOLOGY                        406

ATTRIBUTES OF A FILE                               407

Classification of Files                         408

OPERATIONS AN FILES                               409

BUFFERING OF BLOCKS                             410

RECORD BLOCKING                                    412

RECORD BLOCKING                                    414

FILE ORGANIZATIONS                                415

Sequential Files                                     416

DIRECT OR RANDOM FILE ORGANIZATION 420

INDEXED sequential FILE ORGANIZATION       422

Tags :

Data Structure GNDU PU PTU LPU EBook Lecture Notes Study Material BSc Computer Science IT BCA Download pdf by Anand Technical Publishers Neeraj K Anand, GNDU PU PTU LPU Data Structure Free eBook Download PDF, PU PTU LPU GNDU Data Structure Pdf Free Download B.Tech Lecture Notes, PU PTU LPU GNDU Data Structure By  Neeraj K Anand E-book PDF download free, Data Structure textbook pdf download by Anand Technical Publishers, Data Structure book pdf diploma, Data Structure book by Neeraj K Anand pdf,Introduction to Data Structure pdf download, Data Structure Anand Technical Publishers book pdf, Data Structure book pdf, Data Structure by Neeraj K Anand pdf, Data Structure books for beginners,Free Data Structure PDF eBook,Learn Data Structure Basics To Advanced, Data Structure Guide books,Buy GNDU Data Structure Online Books at amazon, Buy Data Structure for GNDU BSc Computer Science IT BCA at Anand Technical Publishers by Neeraj K Anand, Download LECTURE NOTES PU PTU LPU GNDU Data Structure, Best Data Structure ebooks lecture notes pdf ebook download for Free, Download PU PTU LPU GNDU Data Structure Solved Previous Years Question Papers Examination Master, GNDU PU PTU LPU Data Structure MIS Books Study Material Lecture Notes Download

Scroll to Top