Data Structures Through C in Depth

✍ Scribed by Suresh Kumar Srivastava, Deepali Srivastava

• Publisher: BPB Publications
• Year: 2004
• Tongue: English
• Leaves: 542
• Category: Library

✦ Synopsis

"Data structures through C in Depth" presents the concepts of data structures in a very clear and understandable manner. It covers data structures syllabus of different undergraduate and post graduate courses and can be useful for both beginners and professional programmers. This book can be used by students for self study as the concepts are explained in step-by-step manner followed by clear and easy to comprehend complete programs. The explanations are illustrated by detailed examples, figures and tables throughout the book. Exercises with solutions are provided which helpin having a better understanding of the text. The CD-Rom contains all the programs given in the book. Some 'demo' programs are included in the CD, which demonstrate the stepwise working of the algorithms.

Suresh Kumar Srivastava has been working in software industry for last 12 years. He has done B level from DOEACC Society. He likes to work on system side and do some creative work for development of software tools. He has authored a book on C language titled "C in Depth". Deepali Srivastava has done M.Sc. in Mathematics and Advanced PGDCA from MJP Rohilkhand University. Her areas of interest are C, C++ and Data Structures, and she has a passion for writing. She has authored a book on C language titled "C in Depth".

✦ Table of Contents

CONTENTS
Chapter 1. Introduction. 1
1.1 Data Type 1
1.2 Abstract data types 1
1.3 Data structures 2
1.3.1 Linear and Non linear data structures 3
1.3.2 Static and dynamic data structures 3
1.4 Algorithms 4
1.4.1 Greedy algorithm 4
1.4.2 Divide and conquer algorithm 4
1.4.3 Backtracking 4
1.4.4 Randomized algorithms 4
1.5 Analysis of algorithms 4
1.5.1 Big O notation 6
1.5.1.1 Rules for O notation 6.
Chapter 2. Arrays, Pointers and Structures 10
1.1 Arrays 10
2.1.1 One Dimensional Array 10
2.1.1.1 Declaration of 1-D Array 10
2.1.1.2 Accessing 1-D Array Elements 11
2.1.1.3 Processing 1-D Arrays 11
2.1.1.4 Initialization of 1-D Array 12
2.1.1.5 1-D Arrays and Functions 14
2.1.1.5.1 Passing Individual Array Elements to a Function 14
2.1.1.5.2 Passing whole 1-D Array to a Function 14
2.1.2 Two Dimensional Arrays 15
2.1.2.1 Declaration and Accessing Individual Elements of a 2-D array 15
2.1.2.2 Processing 2-D Arrays 15
2.1.2.3 Initialization of 2-D Arrays 16
2 Pointers 18
2.2.1 Declaration of a Pointer Variable 18
2.2.2 Assigning Address to a Pointer Variable 19
2.2.3 Dereferencing Pointer Variables 19
2.2.4 Pointer to Pointer 20
2.2.5 Pointers and One Dimensional Arrays 21
2.2.6 Pointers and Functions 23
2.2.7 Returning More Than One Value from a Function 24
2.2.8 Function Returning Pointer 25
2.2.9 Passing a 1-D Array to a Function 26
2.2.10 Array of Pointers 27
3 Dynamic Memory Allocation 27
2.3.1 malloc() 28
2.3.2 calloc() 29
2.3.3 realloc() 29
2.3.4 free() 30
2.4 Structure 31
2.4.1 Defining a Structure 31
2.4.2 Declaring Structure Variables 32
2.4.2.1 With Structure Definition 32
2.4.2.2 Using Structure Tag 32
2.4.3 Initialization of Structure Variables 33
2.4.4 Accessing Members of a Structure 33
2.4.5 Assignment of Structure Variables 34
2.4.6 Array of Structures 34
2.4.7 Arrays within Structures 35
2.4.8 Nested Structures (Structure within Structure) 36
2.4.9 Pointers to Structures 38
2.4.10 Pointers within Structures 39
2.4.11 Structures and Functions 39
2.4.11.1 Passing Structure Members as Arguments 39
2.4.11.2 Passing Structure Variable as Argument 40
2.4.11.3 Passing Pointers to Structures as Arguments 40
2.4.11.4 Returning a Structure Variable from Function 41
2.4.11.5 Returning a Pointer to Structure from a Function 42
2.4.11.6 Passing Array of Structures as Argument 42
2.4.11.7 Self Referential Structures 43
Exercise 43.
Chapter3. Linked Lists 48
3.1 Single Linked list 48
3.1.1 Traversing a Single Linked List 51
3.1.2 Searching in a Single Linked List 53
3.1.3 Insertion in a Single Linked List 53
3.1.3-Hnsertion at the beginning of the list 53
3.1.3.2 Insertion in an empty list 54
3.1.3.3 Insertion at the end of the list 55
3.1.3.4 Insertion in between the list nodes 55
3.1.3.4.1 Insertion after a node 56
3.1.3.4.2 Insertion before a node 57
3.1.3.4.3 Insertion at a given position 58
3.1.4 Creation of a Single Linked List 58
3.1.5 Deletion in a Single Linked List 59
3.1.5.1 Deletion of first node 59
3.1.5.2 Deletion of the only node 59
3.1.5.3 Deletion in between the list nodes 60
3.1.5.4 Deletion at the end of the list 60
3.1.6 Reversing a Single Linked List 61
3.2 Doubly linked list 63
3.2.1 Traversing a doubly linked List 65
3.2.2 Insertion in a doubly linked List 65
3.2.2.1 Insertion at the beginning of the list 65
3.2.2.2 Insertion in an empty list 66
_ 3.2.2.3 Insertion at the end of the list 66
3.2.2.4 Insertion in between the nodes 67
3.2.3 Creation of List 69
- 3.2.4 Deletion from doubly linked list 69
3.2.4.1 Deletion of the first node 69
3.2.4.2 Deletion of the only node 70
3.2.4.3 Deletion in between the nodes 70
3.2.4.4 Deletion at the end of the list 70
3.2.5 Reversing a doubly linked list 72
3.3 Circular linked list 72
3.3.1 Traversal in circular linked list 74
3.3.2 Insertion in a circular Linked List 75
3.3.2.1 Insertion at the beginning of the list 75
3.3.2.2 Insertion in an empty list 75
3.3.2.3 Insertion at the end of the list 76
3.3.2.4 Insertion in between the nodes. 76
3.3.3 Creation of circular linked list 77
3.3.4 Deletion in circular linked list 77
3.3.4.1 Deletion of the first node 77
3.3.4.2 Deletion of the only node 77
3.3.4.3 Deletion in between the nodes 78
3.3.4.4 Deletion at the end of the list “78
3.4 Linked List with Header Node 79
3.5 Sorted linked list 83
3.6 Sorting a Linked List 86
- 3.6.1 Selection Sort by exchanging data 87
3.6.2 Bubble Sort by exchanging data 88
3.6.3 Selection Sort by rearranging links 90
3.6.4 Bubble sort by rearranging links 92
3.7 Merging 93
3.8 Concatenation 97
3.9 Polynomial arithmetic with linked list 98
3.9.1 Creation of polynomial linked list 101
3.9.2 Addition of 2 polynomials 101
3.9.3 Multiplication of 2 polynomials. 103
3.10 Comparison of Array lists and Linked lists 104
3.10.1 Advantages of linked lists 104
3.10.2 Disadvantages of linked lists 105
Exercise 105
Chapter 4. Stacks and Queues 108
4.1 Stack 108
4.1.1 Array Implementation of Stack 109
4.1.2 Linked List Implementation of Stack. 111
4.2 Queue 114
4.2.1 Array Implementation of Queue 114
4.2.2 Linked List implementation of Queue 117
4.3 Circular Queue 122
4.4 Deque 126
4.5 Priority Queue - 130
4.6 Applications of stack 132
4.6.1 Reversal of string 133
4.6.2 Checking validity of an expression containing nested parentheses 133
4.6.3 Function calls 136
4.6.4 Polish Notation 137
4.6.4.1 Converting infix expression to postfix expression using stack 139
4.6.4.2 Evaluation of postfix expression using stack 141
Exercise 145
Chapter 5. Recursion 147
5.1 Writing a recursive function 147
5.2 Flow of control in Recursive functions 148
5.3 Winding and unwinding phase 150
5.4 Examples of Recursion 150
5.4.1 Factorial 150
5.4.2 Summation of numbers from 1 ton 152
5.4.3 Displaying numbers from I to n 152
5.4.4 Display and Summation of series 154
5.4.5 Sum of digits of an integer and displaying an integer as sequence of characters 155
5.4.6 Base conversion 156
5.4.7 Exponentiation of a float by a positive integer 156
5.4.8 Prime Factorization 157
5.4.9 Greatest Common Divisor 158
5.4.10 Fibonacci Series 158
5.4.11 Checking Divisibility by 9 and 11 159
5.4.12 Tower of Hanoi 160
5.5 Recursive Data structures 163
5.5.1 Strings and recursion 163
5.5.2 Linked lists and recursion 164
5.6 Implementation of Recursion 166
5.7 Recursion vs. Iteration 166
5.8 Tail recursion 167
5.9 Indirect and direct Recursion 169
Exercise 169
Chapter 6. Trees 176
6.1 Terminology 176
6.2 Definition of Tree 178
6.3 Binary Tree 178
6.4 Strictly Binary Tree 180
6.5 Extended Binary Tree 181
6.6 Full binary tree 182
6.7 Complete Binary Tree 182
6.8 Representation of Binary Trees in Memory 183
6.8.1 Array Representation of Binary trees 183
6.8.2 Linked Representation of Binary Trees 184
6.9 Traversal in Binary Tree 186
6.9.1 Non recursive traversals for binary tree 188
6.9.1.1 Preorder Traversal 189
6.9.1.2 Inorder Traversal 190
6.9.1.3 Postorder Traversal 192
6.9.2 Level order traversal 194
6.9.3 Creation of binary tree from inorder and preorder traversals 195
6.9.4 Creation of binary tree from inorder and postorder traversals 197
6.10 Height of Binary tree 200
6.11 Expression tree 201
6.12 Binary Search Tree 202
6.12.1 Traversal in Binary Search Tree 203
6.12.2 Searching in a Binary Search Tree 203
6.12.3 Finding nodes with Minimum and Maximum key 205
6.12.4 Insertion in a Binary Search Tree 205
—6.12.5 Deletion in a Binary Search Tree 208
6.13 Threaded Binary Tree 214
6.13.1 Finding inorder successor of a node in in-threaded tree 217
6.13.2 Finding inorder predecessor of a node in in-threaded tree 217
6.13.3 Inorder Traversal of in-threaded binary tree 217
6.13.4 Preorder traversal of in-threaded binary tree 218
6.13.5 Insertion and deletion in threaded binary tree 218
6.13.5.1 Insertion 218
6.13.5.2 Deletion 221
6.13.6 Threaded tree with Header node 324
6.14 AVL Tree 225
6.14.1 Searching and Traversal in AVL tree 227
6.14.2 Tree Rotations 227
6.14.2.1 Right Rotation 227
6.14.2.2 Left Rotation 229
6.14.3 Insertion in an AVL tree 231
6.14.3.1-Insertion in left Subtree 236
6.14.3.2 Insertion in Right Subtree 241
6.14.4 Deletion in AVL tree 247
6.14.4.1 Deletion from Left Subtree 248
6.14.4.2 Deletion from Right Subtree 252
6.15 Red Black Trees 258
6.15.1 Searching 260
6.15.2 Insertion 260
6.15.3 Deletion 264
6.16 Heap 277
6.16,1 Insertion in Heap 279
6.16.2 Deletion 282
6.16.3 Building a heap 284
6.16.4 Selection algorithm 286
6.16.5 Implementation of Priority Queue 286
3.17 Weighted path length 286
9.18 Huffman Tree 287
6.18.1 Application of Huffman tree : Huffman Codes 289
3.19 Gencral Tree 291
5.20 Multiway search tree 292
5.21 B-tree 293
6.21.1 Searching in B-tree 294
6.21.2 Insertion in B-tree 295
6.21.3 Deletion in B-tree 297
6.21.3.1 Deletion from leaf node 297
6.21.3.1.1 If node has more than MIN keys. 297
6.21.3.1.2 If node has MIN keys 298
6.21.3.2 Deletion from non leaf node. 301
6.21.4 Searching 304
6.21.5 Insertion 305
6.21.6 Deletion 311
6.22 B+tree 318
6.22.1 Searching 319.
6.21.2 Insertion 319
6.21.3 Deletion 320
6.22 Digital Search Trees 321
Exercise © 322
Chapter 7. Graphs 326
7.1 Undirected Graph 326
7.2 Directed Graph 326
7.3 Graph Terminology 326
7.4 Connectivity in Undirected Graph 329
7.4.1 Connected Graph 329
7.4.2 Connected Components 330
7.4.3 Bridge 330
7.4.4 Articulation point 330
7.4.5 Biconnected graph 331
7.4.6 Biconnected components 332
7.5 Connectivity in Directed Graphs 332
7.5.1 Strongly connected Graph 332
7.5.2 Strongly connected components 332
7.5.3 Weakly connected 333
7.6 Tree 333
7.7 Forest 334
7.8 Spanning tree 334
7.9 Spanning Forest 334
7.10 Representation of Graph 335
7.10.1 Adjacency Matrix 335
7.10.2 Adjacency List 339
7.10.2.1 Vertex insertion 340
7.10.2.2 Edge insertion 340
7.10.2.3 Edge deletion 341
7.10.2.4 Vertex deletion 341
7.11 Transitive closure of a directed graph and Path Matrix 346
7.11.1 Computing Path matrix from powers of adjacency matrix 346
7.11.2 Warshall’s Algorithm 349
7.12 Traversal 353
7.12.1 Breadth First Search 353
7.12.1.1 Implementation of Breadth First Search using queue 355
7.12.2 Depth First Search 364
7.12.2.1 Implementation of Depth First Search using stack 366
7.12.2.2 Recursive Implementation of Depth First Search 370
7.12.2.3 Classification of Edges in DFS 373
7.12.2.4 Strongly connected graph and strongly connected components 376
7.13 Shortest Path Problem 377
7.13.1 Dijkstra’s Algorithm 378
7.13.2 Bellman Ford Algorithm, 387
7.13.3 Modified Warshall’s Algorithm (Floyd’s Algorithm) 392
7.14 Minimum spanning tree 398
7.14.1 Prim’s Algorithm 398
7.14.2 Kruskal’s Algorithm 405
7.15 Topological Sorting 410
Exercise 414
Chapter 8. Sorting 417
8.1 Sort Order 418
8.2 Types of Sorting 418
8.3 Sort Stability 418
8.4 Sort by Address(Indirect Sort) 419
8.5 In place Sort 420
8.6 Sort pass 420
8.7 Sort Efficiency 421
8.8 Selection Sort 421
8.8.1 Analysis of Selection Sort 423
8.9 Bubble Sort 424
8.9.1 Analysis of Bubble Sort 426
8.9.1.1 Data in sorted order 426
8.9.1.2 Data in reverse sorted order 427
8.9.1.3 Data in random order 427
8.10 Insertion Sort 427
8.10.1 Analysis of Insertion sort 429
8.10.1.1 Data in sorted order 430
8.10.1.2 Data in reverse sorted order 430
8.10.1.3 Data in random order 430
8.11 Shell Sort (Diminishing Increment Sort) 431
8.11.1 Analysis of Shell Sort 434
8.12 Merge Sort 434
8.12.1 Top Down Metge Sort (Recursive) 436
8.12.2 Analysis of Merge Sort 439
8.12.3 Bottom Up Merge. Sort(Iterative) 439
8.12.4 Merge Sort for linked List 441
8.12.5 Natural Merge Sort 444
8.13 Quick Sort (Partition Exchange Sort) 444
8.13.1 Analysis of Quick Sort 449
8.13.2 Choice of pivot in Quick Sort 450
8.13.3 Duplicate elements in quick sort 450
8.14 Binary tree sort 451
8.14.1 Analysis of Binary Tree Sort 454
8.15 Heap Sort 455
8.15.1 Analysis of Heap Sort 458
8.16 Radix Sort. 458
8.16.1 Analysis of Radix Sort 462
8.17 Address Calculation Sort 462
8.17.1 Analysis of Address Calculation Sort 465
Exercise 470
Chapter 9. Searching and Hashing 472
9.1 Sequential Search (Linear search) 472
9.2 Binary Search 473
9.3 Hashing 476
9.3.1 Hash functions 478
9.3.1.1 Truncation (or Extraction) 478
9.3.1.2 Midsquare Method 479
9.3.1.3 Folding Method 479
9.3.1.4 Division Method(Modulo-Divison) 479
9.3.2 Collision Resolution 480
9.3.2.1 Open Addressing (Closed Hashing) 480
9,3.2.1.1 Linear Probing 480
9.3.2.1.2 Quadratic Probing 481
9.3.2.1.3 Double Hashing 482
9,3.2.1.4 Deletion in open addressed tables 484
9.3.2.1.5 Implementation of open Addressed tables 484
9.3.2.2 Separate chaining 487
9.3.3 Bucket Hashing 490
Exercise 49]
Chapter 10. Storage Management 492
10.1 Sequential Fit Methods 493
10.1.1 First Fit 493
10.1.2 Best Fit method 493
10.1.3 Worst Fit Method 493
10.2 Fragmentation 494
10.3 Freeing memory 494
10.4 Boundary tag method 495
10.5 Buddy Systems 498
10.5.1 Binary Buddy System 498
10.5.2 Fibonacci Buddy System 502
10.6 Compaction 506
10.7 Garbage collection 506
10.7:1 Reference counting 506
10.7.2 Mark and Sweep 507
Exercise 507
Solutions 509
Index 522

✦ Subjects

datastructuresth0000sksr