Data_Structures_Algorithms_Tutorial.pdf - Tutorialspoint PDF Free Download

2y ago

59 Views

1 Downloads

837.24 KB

19 Pages

Report/dmca

Download PDF

Transcription

Data Structures & AlgorithmsAbout the TutorialData Structures are the programmatic way of storing data so that data can be usedefficiently. Almost every enterprise application uses various types of data structures in oneor the other way.This tutorial will give you a great understanding on Data Structures needed tounderstand the complexity of enterprise level applications and need of algorithms,and data structures.AudienceThis tutorial is designed for Computer Science graduates as well as Software Professionalswho are willing to learn data structures and algorithm programming in simple and easysteps.After completing this tutorial you will be at intermediate level of expertise from where youcan take yourself to higher level of expertise.PrerequisitesBefore proceeding with this tutorial, you should have a basic understanding of Cprogramming language, text editor, and execution of programs, etc.Copyright and Disclaimer Copyright 2016 by Tutorials Point (I) Pvt. Ltd.All the content and graphics published in this e-book are the property of Tutorials Point (I)Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republishany contents or a part of contents of this e-book in any manner without written consentof the publisher.We strive to update the contents of our website and tutorials as timely and as precisely aspossible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt.Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of ourwebsite or its contents including this tutorial. If you discover any errors on our website orin this tutorial, please notify us at contact@tutorialspoint.comi

Data Structures & AlgorithmsCompile & Execute OnlineFor most of the examples given in this tutorial you will find Try it option, so just make useof this option to execute your programs on the spot and enjoy your learning.Try the following example using the Try it option available at the top right corner of thefollowing sample code box #include stdio.h int main(){/* My first program in C */printf("Hello, World! \n");return 0;}ii

Data Structures & AlgorithmsTable of ContentsAbout the Tutorial . iAudience. iPrerequisites. iCopyright and Disclaimer .iCompile & Execute Online . iiTable of Contents . iiiBASICS.11.Overview .2Characteristics of a Data Structure. 2Need for Data Structure . 2Execution Time Cases . 3Basic Terminology . 32.Environment Setup .4Try it Option Online . 4Local Environment Setup. 4Installation on UNIX/Linux. 5Installation on Mac OS. 5Installation on Windows. 6ALGORITHM.73.Algorithms Basics .8Characteristics of an Algorithm . 8How to Write an Algorithm? . 9Algorithm Analysis. 10Algorithm Complexity. 11Space Complexity . 11Time Complexity . 114.Asymptotic Analysis.12Asymptotic Notations . 12Common Asymptotic Notations . 155.Greedy Algorithms .16Counting Coins. 166.Divide & Conquer.18Divide/Break . 18Conquer/Solve . 18Merge/Combine . 197.Dynamic Programming.20iii

Data Structures & AlgorithmsDATA STRUCTURES .218.Basic Concepts .22Data Definition . 22Data Object. 22Data Type. 22Basic Operations. 239.Arrays .24Array Representation . 24Basic Operations. 25Insertion Operation . 25Array Insertions . 27Insertion at the Beginning of an Array . 28Insertion at the Given Index of an Array . 30Insertion After the Given Index of an Array . 32Insertion Before the Given Index of an Array. 34Deletion Operation . 36Search Operation. 37Update Operation. 39LINKED LIST.4110. Linked List Basics.42Linked List Representation . 42Types of Linked List . 42Basic Operations. 43Insertion Operation . 43Deletion Operation . 44Reverse Operation. 45Linked List Program in C . 4611. Doubly Linked List.55Doubly Linked List Representation . 55Basic Operations. 55Insertion Operation . 56Deletion Operation . 57Insertion at the End of an Operation. 57Doubly Linked List Program in C . 5812. Circular Linked List .67Singly Linked List as Circular . 67Doubly Linked List as Circular . 67Basic Operations. 67Insertion Operation . 68Deletion Operation . 68Display List Operation. 69Circular Linked List Program in C . 69iv

Data Structures & AlgorithmsSTACK & QUEUE.7413. Stack .75Stack Representation. 75Basic Operations. 76peek(). 76isfull(). 77isempty(). 77Push Operation. 78Pop Operation . 79Stack Program in C. 8114. Expression Parsing .84Infix Notation. 84Prefix Notation . 84Postfix Notation. 84Parsing Expressions . 85Postfix Evaluation Algorithm . 86Expression Parsing Using Stack. 8615. Queue .92Queue Representation . 92Basic Operations. 92peek(). 93isfull(). 93isempty(). 94Enqueue Operation . 95Dequeue Operation . 96Queue Program in C . 98SEARCHING TECHNIQUES.10216. Linear Search .103Linear Search Program in C . 10417. Binary Search .107How Binary Search Works? . 107Binary Search Program in C . 11018. Interpolation Search .113Positioning in Binary Search . 113Position Probing in Interpolation Search. 114Interpolation Search Program in C . 11619. Hash Table .118Hashing . 118Linear Probing. 119Basic Operations. 120Data Item . 120v

Data Structures & AlgorithmsHash Method . 120Search Operation. 120Insert Operation . 121Delete Operation . 122Hash Table Program in C . 123SORTING TECHNIQUES.12820. Sorting Algorithm.129In-place Sorting and Not-in-place Sorting . 129Stable and Not Stable Sorting. 129Adaptive and Non-Adaptive Sorting Algorithm . 130Important Terms. 13021. Bubble Sort Algorithm .132How Bubble Sort Works?. 132Bubble Sort Program in C . 13622. Insertion Sort .140How Insertion Sort Works? . 140Insertion Sort Program in C . 14323. Selection Sort.147How Selection Sort Works? . 147Selection Sort Program in C . 15024. Merge Sort Algorithm .153How Merge Sort Works? . 153Merge Sort Program in C . 15625. Shell Sort .158How Shell Sort Works? . 158Shell Sort Program in C . 16226. Quick Sort .166Partition in Quick Sort . 166Quick Sort Pivot Algorithm . 166Quick Sort Pivot Pseudocode . 167Quick Sort Algorithm . 167Quick Sort Pseudocode. 168Quick Sort Program in C . 168GRAPH DATA STRUCTURE .17227. Graphs .173Graph Data Structure . 173Basic Operations. 175vi

Data Structures & Algorithms28. Depth First Traversal.176Depth First Traversal in C . 17929. Breadth First Traversal.184Breadth First Traversal in C . 186TREE DATA STRUCTURE .19230. Tree .193Important Terms. 193Binary Search Tree Representation . 194Tree Node . 194BST Basic Operations . 195Insert Operation . 195Search Operation. 197Tree Traversal in C . 19831. Tree Traversal .204In-order Traversal . 204Pre-order Traversal. 205Post-order Traversal . 206Tree Traversal in C . 20732. Binary Search Tree .213Representation . 213Basic Operations. 214Node . 214Search Operation.