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