Data Structures Through C in Depth (S. K. Srivastava, Deepali Srivastava) (Z-Library)

📄 File Format: PDF

💾 File Size: 2.5 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Table of Contents About the Tutorial ………………………………………………………………………………………………………………………….. i Audience……………………………………………………………………………………………………………………………………….. i Prerequisites………………………………………………………………………………………………………………………………….. i Copyright and Disclaimer ………………………………………………………………………………………………………………… i Compile & Execute Online ………………………………………………………………………………………………………………. ii Table of Contents …………………………………………………………………………………………………………………………. iii BASICS………………………………………………………………………………………………………………………..1 1. Overview ………………………………………………………………………………………………………………………………..2 Characteristics of a Data Structure…………………………………………………………………………………………………… 2 Need for Data Structure …………………………………………………………………………………………………………………. 2 Execution Time Cases …………………………………………………………………………………………………………………….. 3 Basic Terminology …………………………………………………………………………………………………………………………. 3 2. Environment Setup …………………………………………………………………………………………………………………..4 Try it Option Online ……………………………………………………………………………………………………………………….. 4 Local Environment Setup………………………………………………………………………………………………………………… 4 Installation on UNIX/Linux………………………………………………………………………………………………………………. 5 Installation on Mac OS…………………………………………………………………………………………………………………….

📄 Page 3

5 Installation on Windows…………………………………………………………………………………………………………………. 6 ALGORITHM………………………………………………………………………………………………………………..7 3. Algorithms ─ Basics …………………………………………………………………………………………………………………..8 Characteristics of an Algorithm ……………………………………………………………………………………………………….. 8 How to Write an Algorithm? …………………………………………………………………………………………………………… 9 Algorithm Analysis……………………………………………………………………………………………………………………….. 10 Algorithm Complexity…………………………………………………………………………………………………………………… 11 Space Complexity ………………………………………………………………………………………………………………………… 11 Time Complexity………………………………………………………………………………………………………………………….. 11 4. Asymptotic Analysis………………………………………………………………………………………………………………..12 Asymptotic Notations…………………………………………………………………………………………………………………… 12 Common Asymptotic Notations …………………………………………………………………………………………………….. 15 5. Greedy Algorithms ………………………………………………………………………………………………………………….16 Counting Coins…………………………………………………………………………………………………………………………….. 16 6. Divide & Conquer…………………………………………………………………………………………………………………… 18 Divide/Break ………………………………………………………………………………………………………………………………..

📄 Page 4

18 Conquer/Solve…………………………………………………………………………………………………………………………….. 18 Merge/Combine ………………………………………………………………………………………………………………………….. 19 7. Dynamic Programming…………………………………………………………………………………………………………….20 iii DATA STRUCTURES …………………………………………………………………………………………………….21 8. Basic Concepts ……………………………………………………………………………………………………………………….22 Data Definition ……………………………………………………………………………………………………………………………. 22 Data Object…………………………………………………………………………………………………………………………………. 22 Data Type……………………………………………………………………………………………………………………………………. 22 Basic Operations………………………………………………………………………………………………………………………….. 23 9. Arrays …………………………………………………………………………………………………………………………………..24 Array Representation …………………………………………………………………………………………………………………… 24 Basic Operations………………………………………………………………………………………………………………………….. 25 Insertion Operation ……………………………………………………………………………………………………………………… 25 Array Insertions …………………………………………………………………………………………………………………………… 27 Insertion at the Beginning of an Array ……………………………………………………………………………………………. 28 Insertion at the Given Index of an Array

📄 Page 5

…………………………………………………………………………………………. 30 Insertion After the Given Index of an Array …………………………………………………………………………………….. 32 Insertion Before the Given Index of an Array…………………………………………………………………………………… 34 Deletion Operation………………………………………………………………………………………………………………………. 36 Search Operation…………………………………………………………………………………………………………………………. 37 Update Operation………………………………………………………………………………………………………………………… 39 LINKED LIST……………………………………………………………………………………………………………….41 10. Linked List ─ Basics………………………………………………………………………………………………………………….42 Linked List Representation ……………………………………………………………………………………………………………. 42 Types of Linked List ……………………………………………………………………………………………………………………… 42 Basic Operations………………………………………………………………………………………………………………………….. 43 Insertion Operation ……………………………………………………………………………………………………………………… 43 Deletion Operation………………………………………………………………………………………………………………………. 44 Reverse Operation……………………………………………………………………………………………………………………….. 45 Linked List Program in C ……………………………………………………………………………………………………………….. 46 11. Doubly Linked List …………………………………………………………………………………………………………………..55 Doubly Linked List Representation ………………………………………………………………………………………………….

📄 Page 6

55 Basic Operations………………………………………………………………………………………………………………………….. 55 Insertion Operation ……………………………………………………………………………………………………………………… 56 Deletion Operation………………………………………………………………………………………………………………………. 57 Insertion at the End of an Operation………………………………………………………………………………………………. 57 Doubly Linked List Program in C …………………………………………………………………………………………………….. 58 12. Circular Linked List ………………………………………………………………………………………………………………….67 Singly Linked List as Circular ………………………………………………………………………………………………………….. 67 Doubly Linked List as Circular ………………………………………………………………………………………………………… 67 Basic Operations………………………………………………………………………………………………………………………….. 67 Insertion Operation ……………………………………………………………………………………………………………………… 68 Deletion Operation………………………………………………………………………………………………………………………. 68 Display List Operation…………………………………………………………………………………………………………………… 69 Circular Linked List Program in C ……………………………………………………………………………………………………. 69 STACK & QUEUE………………………………………………………………………………………………………… 74 13. Stack

📄 Page 7

…………………………………………………………………………………………………………………………………….75 Stack Representation……………………………………………………………………………………………………………………. 75 Basic Operations………………………………………………………………………………………………………………………….. 76 peek() …………………………………………………………………………………………………………………………………………. 76 isfull() …………………………………………………………………………………………………………………………………………. 77 isempty() …………………………………………………………………………………………………………………………………….. 77 Push Operation……………………………………………………………………………………………………………………………. 78 Pop Operation …………………………………………………………………………………………………………………………….. 79 Stack Program in C……………………………………………………………………………………………………………………….. 81 14. Expression Parsing ………………………………………………………………………………………………………………….84 Infix Notation………………………………………………………………………………………………………………………………. 84 Prefix Notation ……………………………………………………………………………………………………………………………. 84 Postfix Notation…………………………………………………………………………………………………………………………… 84 Parsing Expressions ……………………………………………………………………………………………………………………… 85 Postfix Evaluation Algorithm …………………………………………………………………………………………………………. 86 Expression Parsing Using Stack………………………………………………………………………………………………………. 86

📄 Page 8

15. Queue …………………………………………………………………………………………………………………………………..92 Queue Representation …………………………………………………………………………………………………………………. 92 Basic Operations………………………………………………………………………………………………………………………….. 92 peek() …………………………………………………………………………………………………………………………………………. 93 isfull() …………………………………………………………………………………………………………………………………………. 93 isempty() …………………………………………………………………………………………………………………………………….. 94 Enqueue Operation ……………………………………………………………………………………………………………………… 95 Dequeue Operation ……………………………………………………………………………………………………………………… 96 Queue Program in C …………………………………………………………………………………………………………………….. 98 SEARCHING TECHNIQUES…………………………………………………………………………………………..102 16. Linear Search ……………………………………………………………………………………………………………………….103 Linear Search Program in C …………………………………………………………………………………………………………. 104 17. Binary Search ……………………………………………………………………………………………………………………….107 How Binary Search Works? …………………………………………………………………………………………………………. 107 Binary Search Program in C …………………………………………………………………………………………………………. 110 18. Interpolation Search ……………………………………………………………………………………………………………..113

📄 Page 9

Positioning in Binary Search ………………………………………………………………………………………………………… 113 Position Probing in Interpolation Search……………………………………………………………………………………….. 114 Interpolation Search Program in C ……………………………………………………………………………………………….. 116 19. Hash Table …………………………………………………………………………………………………………………………..118 Hashing …………………………………………………………………………………………………………………………………….. 118 Linear Probing……………………………………………………………………………………………………………………………. 119 Basic Operations………………………………………………………………………………………………………………………… 120 Data Item………………………………………………………………………………………………………………………………….. 120 v Hash Method …………………………………………………………………………………………………………………………….. 120 Search Operation……………………………………………………………………………………………………………………….. 120 Insert Operation ………………………………………………………………………………………………………………………… 121 Delete Operation ……………………………………………………………………………………………………………………….. 122 Hash Table Program in C …………………………………………………………………………………………………………….. 123 SORTING TECHNIQUES……………………………………………………………………………………………… 128 20. Sorting Algorithm………………………………………………………………………………………………………………….129

📄 Page 10

In-place Sorting and Not-in-place Sorting ……………………………………………………………………………………… 129 Stable and Not Stable Sorting………………………………………………………………………………………………………. 129 Adaptive and Non-Adaptive Sorting Algorithm ………………………………………………………………………………. 130 Important Terms………………………………………………………………………………………………………………………… 130 21. Bubble Sort Algorithm …………………………………………………………………………………………………………..132 How Bubble Sort Works? …………………………………………………………………………………………………………….. 132 Bubble Sort Program in C ……………………………………………………………………………………………………………. 136 22. Insertion Sort ……………………………………………………………………………………………………………………….140 How Insertion Sort Works? …………………………………………………………………………………………………………. 140 Insertion Sort Program in C …………………………………………………………………………………………………………. 143 23. Selection Sort……………………………………………………………………………………………………………………….147 How Selection Sort Works? …………………………………………………………………………………………………………. 147 Selection Sort Program in C …………………………………………………………………………………………………………. 150 24. Merge Sort Algorithm …………………………………………………………………………………………………………… 153 How Merge Sort Works? …………………………………………………………………………………………………………….. 153 Merge Sort Program in C …………………………………………………………………………………………………………….. 156 25. Shell Sort

📄 Page 11

…………………………………………………………………………………………………………………………….158 How Shell Sort Works? ……………………………………………………………………………………………………………….. 158 Shell Sort Program in C ……………………………………………………………………………………………………………….. 162 26. Quick Sort …………………………………………………………………………………………………………………………… 166 Partition in Quick Sort ………………………………………………………………………………………………………………… 166 Quick Sort Pivot Algorithm ………………………………………………………………………………………………………….. 166 Quick Sort Pivot Pseudocode ………………………………………………………………………………………………………. 167 Quick Sort Algorithm ………………………………………………………………………………………………………………….. 167 Quick Sort Pseudocode……………………………………………………………………………………………………………….. 168 Quick Sort Program in C ……………………………………………………………………………………………………………… 168 GRAPH DATA STRUCTURE ………………………………………………………………………………………….172 27. Graphs ………………………………………………………………………………………………………………………………..173 Graph Data Structure …………………………………………………………………………………………………………………. 173 Basic Operations………………………………………………………………………………………………………………………… 175 28. Depth First Traversal……………………………………………………………………………………………………………..176 Depth First Traversal in C ……………………………………………………………………………………………………………. 179

📄 Page 12

29. Breadth First Traversal…………………………………………………………………………………………………………..184 Breadth First Traversal in C …………………………………………………………………………………………………………. 186 TREE DATA STRUCTURE …………………………………………………………………………………………….192 30. Tree …………………………………………………………………………………………………………………………………… 193 Important Terms………………………………………………………………………………………………………………………… 193 Binary Search Tree Representation ………………………………………………………………………………………………. 194 Tree Node …………………………………………………………………………………………………………………………………. 194 BST Basic Operations ………………………………………………………………………………………………………………….. 195 Insert Operation ………………………………………………………………………………………………………………………… 195 Search Operation……………………………………………………………………………………………………………………….. 197 Tree Traversal in C ……………………………………………………………………………………………………………………… 198 31. Tree Traversal ……………………………………………………………………………………………………………………… 204 In-order Traversal ………………………………………………………………………………………………………………………. 204 Pre-order Traversal…………………………………………………………………………………………………………………….. 205 Post-order Traversal …………………………………………………………………………………………………………………… 206

📄 Page 13

Tree Traversal in C ……………………………………………………………………………………………………………………… 207 32. Binary Search Tree ………………………………………………………………………………………………………………..213 Representation ………………………………………………………………………………………………………………………….. 213 Basic Operations………………………………………………………………………………………………………………………… 214 Node ………………………………………………………………………………………………………………………………………… 214 Search Operation……………………………………………………………………………………………………………………….. 214 Insert Operation ………………………………………………………………………………………………………………………… 215 33. AVL Trees …………………………………………………………………………………………………………………………….217 AVL Rotations ……………………………………………………………………………………………………………………………. 218 34. Spanning Tree ……………………………………………………………………………………………………………………… 222 General Properties of Spanning Tree ……………………………………………………………………………………………. 222 Mathematical Properties of Spanning Tree……………………………………………………………………………………. 223 Application of Spanning Tree ………………………………………………………………………………………………………. 223 Minimum Spanning Tree (MST) ……………………………………………………………………………………………………. 223 Minimum Spanning-Tree Algorithm ……………………………………………………………………………………………… 223 Kruskal’s Spanning Tree Algorithm……………………………………………………………………………………………….. 224

📄 Page 14

Prim’s Spanning Tree Algorithm …………………………………………………………………………………………………… 227 35. Heaps………………………………………………………………………………………………………………………………….231 Max Heap Construction Algorithm ……………………………………………………………………………………………….. 232 Max Heap Deletion Algorithm ……………………………………………………………………………………………………… 233 RECURSION……………………………………………………………………………………………………………..234 vii 36. Recursion ─ Basics………………………………………………………………………………………………………………… 235 Properties …………………………………………………………………………………………………………………………………. 235 Implementation…………………………………………………………………………………………………………………………. 236 Analysis of Recursion………………………………………………………………………………………………………………….. 236 Time Complexity………………………………………………………………………………………………………………………… 236 Space Complexity ………………………………………………………………………………………………………………………. 237 37. Tower of Hanoi …………………………………………………………………………………………………………………….238 Rules ………………………………………………………………………………………………………………………………………… 238 Algorithm………………………………………………………………………………………………………………………………….. 242 Tower of Hanoi in C ……………………………………………………………………………………………………………………. 245 38. Fibonacci Series ……………………………………………………………………………………………………………………

📄 Page 15

249 Fibonacci Iterative Algorithm ………………………………………………………………………………………………………. 250 Fibonacci Interactive Program in C……………………………………………………………………………………………….. 250 Fibonacci Recursive Algorithm …………………………………………………………………………………………………….. 252 Fibonacci Recursive Program in C…………………………………………………………………………………………………. 252 viii

📄 Page 16

Basics 1. Overview Data Structures & Algorithms Data Structure is a systematic way to organize data in order to use it efficiently. Following terms are the foundation terms of a data structure. Interface − Each data structure has an interface. Interface represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations. Implementation − Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.

📄 Page 17

Characteristics ofa Data Structure Correctness − Data structure implementation should implement its interface correctly. Time Complexity − Running time or the execution time of operations of data structure must be as small as possible. Space Complexity − Memory usage of a data structure operation should be as little as possible.

📄 Page 18

Need for Data Structure As applications are getting complex and data rich, there are three common problems that applications face now-a-days. Data Search − Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower. Processor Speed − Processor speed although being very high, falls limited if the data grows to billion records. Multiple Requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data. To solve the above-mentioned problems, data structures come to rescue. Data can be organized in a data structure in such a way that all items may not be required to be searched, and the required data can be searched almost instantly.

📄 Page 19

ExecutionTimeCases There are three cases which are usually used to compare various data structure’s execution time in a relative manner. Worst Case − This is the scenario where a particular data structure operation takes maximum time it can take. If an operation’s worst case time is ƒ(n) then this operation will not take more than ƒ(n) time, where ƒ(n) represents function of n. Average Case − This is the scenario depicting the average execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then m operations will take mƒ(n) time. Best Case − This is the scenario depicting the least possible execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n).

📄 Page 20

Basic Terminology Data − Data are values or set of values. Data Item − Data item refers to single unit of values. Group Items − Data items that are divided into sub items are called as Group Items. Elementary Items − Data items that cannot be divided are called as Elementary Items. Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned values. Entity Set − Entities of similar attributes form an entity set. Field − Field is a single elementary unit of information representing an attribute of an entity. Record − Record is a collection of field values of a given entity. File − File is a collection of records of the entities in a given entity set.