Data Structure Using C - PDF

DATA STRUCTURE USING C Presented By Raseena Hydros Dept Of Computer Science MTM College,Veliyancode Chapter 1 Introduction to Data Structure What is Data ⚫ Data is raw facts and figures ⚫ Eg: 12,arun ⚫ Data have very little meanin...

DATA STRUCTURE USING C Presented By Raseena Hydros Dept Of Computer Science MTM College,Veliyancode Chapter 1 Introduction to Data Structure What is Data ⚫ Data is raw facts and figures ⚫ Eg: 12,arun ⚫ Data have very little meaning until they processed ⚫ The result of data process is called information ⚫ Eg:Arun is a student, whose age is 12 ⚫ The data should be arranged in systematic way then it gets a structure and become meaningful What is Data Structure ⚫ A data structure is a particular way of storing and organizing data either in computer’s memory or on the disk storage so that it can be used efficiently. ⚫ Data structures are building blocks of a program. A program built using improper data structures may not work as expected. So as a programmer it is mandatory to choose most appropriate data structures for a program ⚫ Data Structure=Related Data + Allowed Operations ⚫ General data structure types include array,list ,queue, tree etc.  Data Structure Vs. Data Type DATA TYPES DATA STRUCTURES Data Type is the kind or form of a variable Data Structure is the collection of different which is being used throughout the program. It kinds of data. That entire data can be defines that the particular variable will assign represented using an object and can be used the values of the given data type only throughout the entire program. Implementation through Data Types is a form of abstract implementation whose definition is Implementation through Data Structures is provided by different languages in different called concrete implementation ways. Can hold different kind and types of data Can hold values and not data, so it is data less within one single object The data is assigned to the data structure object Values can directly be assigned to the data type using some set of algorithms and operations variables like push, pop and so on. Time complexity comes into play when working No problem of time complexity with data structures Examples: int, float, double,chat Examples: stacks, queues, tree Elementary data structure organization Data: The term data means a value or set of values. It specifies either the value of a variable or a constant For Example, marks of students, name of an employee, address of a customer, value of pi, etc. Elementary data item:a data item that does not have subordinate data items is categorized as an elementary item Group data item:data item composed of one or more subordinate data items is called a group item For example, a student’s name may be divided into three sub-items—first name, middle name, and last name—but his roll number would normally be treated as a single item Elementary data structure organization Record: A record is a collection of data items. For example, the Student_ID Student_name, City,Age and marks obtained are individual data items. But all these data items can be grouped together to form a record File: A file is a collection of related records. For example, if there are 24 students in a class, then there are 24 records of the students. All these related records are stored in a file Primary Key : A value of a certain data item uniquely identifies the record in the file. Such a data item K is called a primary key For example, in a student’s record that contains Student_ID Student_name, City,Age , the field Student_ID is a primary key. Classification of Data Structures Primitive and Non-primitive Data Structures Primitive: Primitive data structures are the fundamental data types which are supported by a programming language. Example: basic data types such as integer, real, character, and Boolean Non Primitive:Non-primitive data structures are those data structures which are created using primitive data structures. Examples of such data structures include linked lists, stacks, trees, and graphs. Linear and Non-linear Structures Non-primitive data structures can further be classified into two categories: linear and non-linear data structures Linear Data Structure :If the elements of a data structure are stored in a linear or sequential order, then it is a linear data structure. Eg: Array,Stack,Queue,Linked list Non-linear Data Structure : If the elements of a data structure are not stored in sequential order, then it is a. non-linear data structure. Eg:Tree,Graph ARRAYS ➔ An array is a collection of similar data elements ➔ which are stored in consecutive memory locations, where each memory location stores one fixed-length data item. Array of 10 Integers a Array of 10 Character b 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 5 6 4 3 7 8 9 2 1 2 m t m c o l l e g e Limitations Arrays are of fixed size. Data elements are stored in contiguous memory locations which may not be always available. Insertion and deletion of elements can be problematic because of shifting of elements from their positions. Linked List ➔ A linked list is a linear data structure consisting of a group of elements (called nodes) which together represent a sequence. ➔ In contrast to using static arrays, a programmer need not worry about how many elements will be stored in the linked list ➔ In a linked list, each node Store An element(data) Link to the next Node(pointer) Advantage: Easier to insert or delete data elements Disadvantage: Slow search operation and requires more memory space  STACK ➔ A stack is a last-in, first-out (LIFO) data structure in which insertion and deletion of elements are done at only one end, which is known as the top of the stack ➔ Stack can be implemented using array or linked list ➔ Three operations on stack *PUSH :adds an element to the top of the stack *POP :deletes an element to the top of the stack *PEEP :operation returns the value of the topmost element of the stack (without deleting it). Advantage: Provides Last In First Out Access Disadvantage: Slow Access to other elements QUEUE ➔ A queue is a first-in, first-out (FIFO) data structure in which the element that is inserted first is the first to be taken out. ➔ The elements in a queue are added at one end called the rear and removed from the other end called the front. Advantage: Provides Last In First Out Access Disadvantage: Slow Access to other elements TREE ➔ A tree is a non-linear data structure which consists of a collection of nodes arranged in a hierarchical tree structure. ➔ The simplest form of a tree is a binary tree ➔ A binary tree consists of a root node and left and right sub-trees Advantage: Provides quick search, insert, and delete operations Disadvantage: Complicated deletion algorithm Graph ➔ A graph is a non-linear data structure which is a collection of vertices (also called nodes) and edges that connect these vertices ➔ A graph is often viewed as a generalization of the tree structure, where instead of a purely parent-to-child relationship between tree nodes, any kind of complex relationships can be represented. ➔ Unlike trees, graphs do not have any root node. Rather, every node in the graph can be connected with any other node in the graph. When two nodes are connected via an edge, the two nodes are known as neighbors. Advantage: Best models real-world situations Disadvantage: Some algorithms are slow and very complex Data Structure operations Data Structure operations ➔ Traversing It means to access each data item exactly once so that it can be processed. ➔ For example, to print the names of all the students in a class. ➔ Searching It is used to find the location of one or more data items that satisfy the given condition.Such a data item may or may not be present in the given collection of data items. ➔ For example,to find the names of all the students who secured 100 marks in mathematics. ➔ Inserting It is used to add new data items to the given list of data items. ➔ For example, to add the details of a new student who has recently joined the course. Data Structure operations ➔ Deleting It means to remove (delete) a particular data item from the given collection of data items. ➔ For example, to delete the name of a student who has left the course. ➔ Sorting Data items can be arranged in some order like ascending order or descending order depending on the type of application. ➔ For example, arranging the names of students in a class in an alphabetical order, or calculating the top three winners by arranging the participants’ scores in descending order and then extracting the top three. ➔ Merging Lists of two sorted data items can be combined to form a single list of sorted data items. Applications of Data Structure ➔ Applications of Array ➔ Applications of Linked List ➔ Applications of Stacks ➔ Applications of Queue ➔ Applications of Tree ➔ Applications of Graph Applications Of Array ➔ Arrays are used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. ➔ Arrays are used to implement other data structures, such as lists, heaps, hash tables, queues and stack ➔ Arrays can be used in various CPU scheduling algorithms. Applications Of Linked list ➔ Linked list are usually a basic dynamic data structure which implements queues,stack and graphs ➔ Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list. ➔ Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list  Applications Of Stack ➔ To reverse a word. You push a given word to stack - letter by letter -and then pop letters from the stack. ➔ An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack. - Undo/Redo stacks in Excel or Word. ➔ Language processing :-compiler's syntax check for matching braces is implemented by using stack. ➔ Support for recursion Applications of Queue ➔ Queue has been used when a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling. ➔ When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.  Applications Of Tree ➔ Files and Folders in Operating System ➔ HTML Document ➔ Network Routing ➔ Syntax Tree in Compiler Applications Of Graph ➔ Facebook: Each user is represented as a vertex and two people are friends when there is an edge between two vertices. Similarly friend suggestion also uses graph theory concept. ➔ Google Maps: Various locations are represented as vertices and the roads are represented as edges and graph theory is used to find shortest path between two nodes. ➔ Recommendations on e-commerce websites: The “Recommendations for you” section on various e-commerce websites uses graph theory to recommend items of similar type to user’s choice. ➔ Graph theory is also used to study molecules in chemistry and physics Algorithm ➔ An algorithm is a finite step by step well defined instructions to solve logical and mathematical problems ➔ An algorithm provides a blueprint to write a program to solve a particular problem. ➔ Algorithms are mainly used to achieve software re-use. Once we have an idea or a blueprint of a solution, we can implement in any high level language like C, C++, Java, so on and so forth. ➔ Example: Write an algorithm to find whether a number is even or odd Step 1: Input the first number as A Step 2: IF A%2 =0 Then Print "EVEN" ELSE PRINT "ODD“ Step 3: END  Complexity of an Algorithm ➔ To analyze an algorithm means determining the amount of resources (such as time and storage) needed to execute it. ➔ Complexity of an algorithm is a measure of the amount of time and/or space required by an algorithm for an input of a given size (n) ➔ Algorithms are generally designed to work with an arbitrary number of inputs, so the efficiency or complexity of an algorithm is stated in terms of time complexity and space complexity Space Complexity ➔ space complexity of an algorithm is the amount of computer memory required during the program execution, as a function of the input size The space needed by a program depends on: ➔ Fixed part, that varies with problem to problem. It includes space needed for storing instructions, constants, variables and structured variables (like arrays, structures) ➔ Variable part, that varies from program to program. It includes space needed for recursion stack, and for structured variables that are allocated space dynamically during the run-time of the program Time complexity ➔ The time Complexity of an algorithm is basically the running time of the program as a function of the input size. ➔ Time complexity of an algorithm depends on the number of machine instructions in which a program executes. This number is primarily dependent on the size of the program's input and the algorithm used. ➔ However, running time requirements are more critical than memory requirements. Worst-case, Average-case, Best-case, and Amortized Time Complexity The best-case complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size n. The worst-case complexity of the algorithm is the function defined by the maximum number of steps taken on any instance of size n. average-case complexity of the algorithm is the function defined by the average number of steps taken on any instance of size n. Amortized running time is roughly the average running time of an algorithm. That is, if you perform an operation many times, what is the average time it takes to complete one of those operations.  Example Best Case : 1 (First Element) Average Case: 5 (Middle Elements) Worst Case :16( Last Element)  Time–Space Trade-off ➔ The best algorithm to solve a particular problem at hand is no doubt the one that requires less memory space and takes less time to complete its execution. ➔ But practically, designing such an ideal algorithm is not a trivial task. There can be more than one algorithm to solve a particular problem. One may require less memory space, while the other may require less CPU time to execute. Thus, it is not uncommon to sacrifice one thing for the other. Hence, there exists a time–space trade-off among algorithms. ➔ So, if space is a big constraint, then one might choose a program that takes less space at the cost of more CPU time. On the contrary, if time is a major constraint, then one might choose a program that takes minimum time to execute at the cost of more space.  Calculating algorithm Complexity ➔ The time and space complexity can be expressed using a function f(n) where n is the input size for a given instance ➔ If a function is linear (without any loops or recursions), the efficiency of that algorithm or the running time of that algorithm can be given as the number of instructions it contains. ➔ If an algorithm contains certain loops or recursive functions then the efficiency of that algorithm may vary depending on the number of loops and the running time of each loop in the algorithm. ➔ If n is the number of elements, then the efficiency can be stated as f(n) = efficiency  Expressing Time-Space Complexity If the Algorithm contains loops, f(n) will be as follows: Instruction Type Example f(n) Linear loops for(i=0;i