NOTES SUBJECT: DATA STRUCTURES USING C SUBJECT CODE: NCS-301 BRANCH: CSE SEM: 3rd SESSION: 2014-15 Evaluation Scheme Subject Code Name of Subject Periods Evaluation Scheme Subject Total Credit L T P CT TA TOTAL ESE NCS-301 Data Structures Using C 3 1 0 30 20 50 100 150 4 Asst. Prof. Swimpy Pahuja & Priyanka Gupta CSE Department, AKGEC Ghaziabad CONTENTS UNIT-1 INTRODUCTION 1.1 BASIC TERMINOLOGY: ELEMENTARY DATA ORGANIZATION 1.1.1 Data and Data Item 1.1.2 Data Type 1.1.3 Variable 1.1.4 Record 1.1.5 Program 1.1.6 Entity 1.1.7 Entity Set 1.1.8 Field 1.1.9 File 1.1.10 Key 1.2 ALGORITHM 1.3 EFFICIENCY OF AN ALGORITHM 1.4 TIME AND SPACE COMPLEXITY 1.5 ASYMPTOTIC NOTATIONS 1.5.1 Asymptotic 1.5.2 Asymptotic Notations 1.5.2.1 Big-Oh Notation (O) 1.5.2.2 Big-Omega Notation (Ω) 1.5.2.3 Big-Theta Notation (Θ) 1.5.3 Time Space Trade-off 1.6 ABSTRACT DATA TYPE 1.7 DATA STRUCTURE 1.7.1 Need of data structure 1.7.2 Selecting a data structure 1.7.3 Type of data structure 1.7.3.1 Static data structure 1.7.3.2 Dynamic data structure 1.7.3.3 Linear Data Structure 1.7.3.4 Non-linear Data Structure 1.8 A BRIEF DESCRIPTION OF DATA STRUCTURES 1.8.1 Array 1.8.2 Linked List 1.8.3 Tree 1.8.4 Graph 1.8.5 Queue 1.8.6 Stack 1.9 DATA STRUCTURES OPERATIONS 1.10 ARRAYS: DEFINITION 1.10.1 Representation of One-Dimensional Array 1.10.2 Two-Dimensional Arrays 1.10.3 Representation of Three& Four Dimensional Array 1.10.4 Operations on array 1.10.5 Applications of array 1.10.6 Sparse matrix 1.11 STATIC AND DYNAMIC MEMORY ALLOCATION 1.12 LINKED LIST 1.12.1 Representation of Linked list in memory 1.12.2 Types of linked lists 1.12.3 The Operations on the Linear Lists 1.12.4 Comparison of Linked List and Array 1.12.5 Advantages 1.12.6 Operations on Linked List 1.12.7 Doubly Linked Lists 1.12.8 Circular Linked List 1.12.9 Polynomial representation and addition 1.13 GENERALIZED LINKED LIST UNIT-2 STACKS 2.1 STACKS 2.2 PRIMITIVE STACK OPERATIONS 2.3 ARRAY AND LINKED IMPLEMENTATION OF STACK IN C 2.4 APPLICATION OF THE STACK (ARITHMETIC EXPRESSIONS) 2.5 EVALUATION OF POSTFIX EXPRESSION 2.6 RECURSION 2.6.1 Simulation of Recursion 2.6.1.1 Tower of Hanoi Problem 2.6.2 Tail recursion 2.7 QUEUES 2.8 DEQUEUE (OR) DEQUE (DOUBLE ENDED QUEUE) 2.9 PRIORITY QUEUE UNIT-3 TREES 3.1 TREES TERMINOLOGY 3.2 BINARY TREE 3.3 TRAVERSALS 3.4 BINARY SEARCH TREES 3.4.1 Non-Recursive Traversals 3.4.2 Array Representation of Complete Binary Trees 3.4.3 Heaps 3.5 DYNAMIC REPRESENTATION OF BINARY TREE 3.6 COMPLETE BINARY TREE 3.6.1 Algebraic Expressions 3.6.2 Extended Binary Tree: 2-Trees 3.7 TREE TRAVERSAL ALGORITHMS 3.8 THREADED BINARY TREE 3.9 HUFFMAN CODE UNIT-4 GRAPHS 4.1 INTRODUCTION 4.2 TERMINOLOGY 4.3 GRAPH REPRESENTATIONS 4.3.1 Sequential representation of graphs 4.3.2 Linked List representation of graphs 4.4 GRAPH TRAVERSAL 4.5 CONNECTED COMPONENT 4.6 SPANNING TREE 4.6.1 Kruskal’s Algorithm 4.6.2Prim’s Algorithm 4.7 TRANSITIVE CLOSURE AND SHORTEST PATH ALGORITHM 4.6.1 Dijikstra’s Algorithm 4.6.2Warshall’s Algorithm 4.8 INTRODUCTION TO ACTIVITY NETWORKS UNIT-5 SEARCHING 5.1 SEARCHING 5.1.1 Linear Search or Sequential Search 5.1.2 Binary Search 5.2 INTRODUCTION TO SORTING 5.3 TYPES OF SORTING 5.3.1 Insertion sort 5.3.2 Selection Sort 5.3.3 Bubble Sort 5.3.4 Quick Sort 5.3.5 Merge Sort 5.3.6 Heap Sort 5.3.7 Radix Sort 5.4 PRACTICAL CONSIDERATION FOR INTERNAL SORTING 5.5 SEARCH TREES 5.5.1 Binary Search Trees 5.5.2 AVL Trees 5.5.3 M-WAY Search Trees 5.5.4 B Trees 5.5.5 B+ Trees 5.6 HASHING 5.6.1 Hash Function 5.6.2 Collision Resolution Techniques 5.7 STORAGE MANGMENT 5.7.1 Garbage Collection 5.7.2Compaction AJAY KUMAR GARG ENGINEERING COLLEGE GHAZIABAD DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING COURSE: B.Tech. SEMESTER: III SUBJECT CODE: NCS-301 L: 3 T: 1 P: 0 NCS-301: DATA STRUCTURES USING C Prerequisite: Students should be familiar with procedural language like C and concepts of mathematics Objective: To make students understand specification, representation, and implementation of data types and data structures, basic techniques of algorithm analysis, recursive methods, applications of Data Structures. Unit - I Introduction: Basic Terminology, Elementary Data Organization, Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big-Oh, Time-Space trade-off. Abstract Data Types (ADT) Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Application of arrays, Sparse Matrices and their representations. Linked lists: Array Implementation and Dynamic Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition, Generalized Linked List. Unit – II Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Recursion, Tower of Hanoi Problem, Simulating Recursion, Principles of recursion, Tail recursion, Removal of recursion Queues, Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue. Unit – III Trees: Basic terminology, Binary Trees, Binary Tree Representation: Array Representation and Dynamic Representation, Complete Binary Tree, Algebraic Expressions, Extended Binary Trees, Array and Linked Representation of Binary trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Threaded Binary trees, Traversing Threaded Binary trees, Huffman algorithm. Unit – IV Unit- IV Graphs: Terminology, Sequential and linked Representations of Graphs: Adjacency Matrices, Adjacency List, Adjacency Multi list, Graph Traversal : Depth First Search and Breadth First Search, Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transistive Closure and Shortest Path algorithm: Warshal Algorithm and Dijikstra Algorithm, Introduction to Activity Networks. Unit – V Searching : Sequential search, Binary Search, Comparison and Analysis Internal Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Two Way Merge Sort, Heap Sort, Radix Sort, Practical consideration for Internal Sorting. Search Trees: Binary Search Trees(BST), Insertion and Deletion in BST, Complexity of Search Algorithm, AVL trees, Introduction to m-way Search Trees, B Trees & B+ Trees . Hashing: Hash Function, Collision Resolution Strategies Storage Management: Garbage Collection and Compaction. References: 1. Aaron M. Tenenbaum,YedidyahLangsam and Moshe J. Augenstein “Data Structures Using C and C++”, PHI Learning Private Limited, Delhi India. 2. Horowitz and Sahani, “Fundamentals of Data Structures”, Galgotia Publications Pvt Ltd Delhi India. 3. A.K. Sharma ,Data Structure Using C, Pearson Education India. 4. Rajesh K. Shukla, “Data Structure Using C and C++” Wiley Dreamtech Publication. 5. Lipschutz, “Data Structures” Schaum’s Outline Series, Tata Mcgraw-hill Education (India) Pvt. Ltd . 6. Michael T. Goodrich, Roberto Tamassia, David M. Mount “Data Structures and Algorithms in C++”, Wiley India. 7. P.S. Deshpandey, “C and Datastructure”, Wiley Dreamtech Publication. 8. R. Kruse etal, “Data Structures and Program Design in C”, Pearson Education 9. Berztiss, A.T.: Data structures, Theory and Practice :, Academic Press. 10. Jean Paul Trembley and Paul G. Sorenson, “An Introduction to Data Structures with applications”, McGraw Hill. UNIT-1 1.1 BASIC TERMINOLOGY: ELEMENTARY DATA ORGANIZATION 1.1.1 Data and Data Item Data are simply collection of facts and figures. Data are values or set of values. A data item refers to a single unit of values. Data items that are divided into sub items are group items; those that are not are called elementary items. For example, a student’s name may be divided into three sub items – [first name, middle name and last name] but the ID of a student would normally be treated as a single item. In the above example ( ID, Age, Gender, First, Middle, Last, Street, Area ) are elementary data items, whereas (Name, Address ) are group data items. 1.1.2 Data Type Data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; and the way values of that type can be stored. It is of two types: Primitive and non-primitive data type. Primitive data type is the basic data type that is provided by the programming language with built-in support. This data type is native to the language and is supported by machine directly while non-primitive data type is derived from primitive data type. For example- array, structure etc. 1.1.3 Variable It is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents. A variable name in computer source code is usually associated with a data storage location and thus also its contents and these may change during the course of program execution. 1.1.4 Record Collection of related data items is known as record. The elements of records are usually called fields or members. Records are distinguished from arrays by the fact that their number of fields is typically fixed, each field has a name, and that each field may have a different type. 1.1.5 Program A sequence of instructions that a computer can interpret and execute is termed as program. 1.1.6 Entity An entity is something that has certain attributes or properties which may be assigned some values. The values themselves may be either numeric or non-numeric. Example: 1.1.7 Entity Set An entity set is a group of or set of similar entities. For example, employees of an organization, students of a class etc. Each attribute of an entity set has a range of values, the set of all possible values that could be assigned to the particular attribute. The term “information” is sometimes used for data with given attributes, of, in other words meaningful or processed data. 1.1.8 Field A field is a single elementary unit of information representing an attribute of an entity, a record is the collection of field values of a given entity and a file is the collection of records of the entities in a given entity set. 1.1.9 File File is a collection of records of the entities in a given entity set. For example, file containing records of students of a particular class. 1.1.10 Key A key is one or more field(s) in a record that take(s) unique values and can be used to distinguish one record from the others. 1.2 ALGORITHM A well-defined computational procedure that takes some value, or a set of values, as input and produces some value, or a set of values, as output. It can also be defined as sequence of computational steps that transform the input into the output. An algorithm can be expressed in three ways:- (i) in any natural language such as English, called pseudo code. (ii) in a programming language or (iii) in the form of a flowchart. 1.3 EFFICIENCY OF AN ALGORITHM In computer science, algorithmic efficiency are the properties of an algorithm which relate to the amount of resources used by the algorithm. An algorithm must be analyzed to determine its resource usage. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process. For maximum efficiency we wish to minimize resource usage. However, the various resources (e.g. time, space) can not be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is being considered as the most important, e.g. is the requirement for high speed, or for minimum memory usage, or for some other measure. It can be of various types: • Worst case efficiency: It is the maximum number of steps that an algorithm can take for any collection of data values. • Best case efficiency: It is the minimum number of steps that an algorithm can take any collection of data values. • Average case efficiency: It can be defined as - the efficiency averaged on all possible inputs - must assume a distribution of the input - We normally assume uniform distribution (all keys are equally probable) If the input has size n, efficiency will be a function of n 1.4 TIME AND SPACE COMPLEXITY Complexity of algorithm is a function of size of input of a given problem instance which determines how much running time/memory space is needed by the algorithm in order to run to completion. Time Complexity: Time complexity of an algorithm is the amount of time it needs in order to run to completion. Space Complexity: Space Complexity of an algorithm is the amount of space it needs in order to run to completion. There are two points which we should consider about computer programming:- (i) An appropriate data structure and (ii) An appropriate algorithm. 1.5 ASYMPTOTIC NOTATIONS 1.5.1 Asymptotic It means a line that continually approaches a given curve but does not meet it at any finite distance. Example x is asymptotic with x + 1 as shown in graph. Asymptotic may also be defined as a way to describe the behavior of functions in the limit or without bounds. Let f(x) and g(x) be functions from the set of real numbers to the set of real numbers. We say that f and g are asymptotic and write f(x) ≈ g(x) if f(x) / g(x) = c (constant) 1.5.2 Asymptotic Notations 1.7.2.1 Big-Oh Notation (O) It provides possibly asymptotically tight upper bound for f(n) and it does not give best case complexity but can give worst case complexity. Let f be a nonnegative function. Then we define the three most common asymptotic bounds as follows. We say that f(n) is Big-O of g(n), written as f(n) = O(g(n)), iff there are positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0 If f(n) = O(g(n)), we say that g(n) is an upper bound on f(n). Example - n2 + 50n = O(n2) 0 ≤ h(n) ≤ cg(n) 0 ≤ n2 + 50n ≤ cn2 0/n2 ≤ n2/n2 + 50n/n2 ≤ cn2/n2 Divide by n2 0 ≤ 1 + 50/n ≤ c Note that 50/n → 0 as n → ∞ Pick n = 50 0 ≤ 1 + 50/50 = 2 ≤ c = 2 With c=2 0 ≤ 1 + 50/n0 ≤ 2 Find n0 -1 ≤ 50/n0 ≤ 1 -20n0 ≤ 50 ≤ n0 = 50 n0=50 0 ≤ n2 + 50n ≤ 2n2 ∀ n ≥ n0=50, c=2 1.7.2.2 Big-Omega Notation (Ω) It provides possibly asymptotically tight lower bound for f(n) and it does not give worst case complexity but can give best case complexity f(n) is said to be Big-Omega of g(n), written as f(n) = Ω(g(n)), iff there are positive constants c and n0 such that 0 ≤ c g(n) ≤ f(n) for all n ≥ n0 If f(n) = Ω(g(n)), we say that g(n) is a lower bound on f(n). Example - n3 = Ω(n2) with c=1 and n0=1 0 ≤ cg(n) ≤ h(n) 0 ≤ 1*12 = 1 ≤ 1 = 13 0 ≤ cg(n) ≤ h(n) 0 ≤ cn2 ≤ n3 0/n2 ≤ cn2/n2 ≤ n3/n2 0 ≤ c ≤ n 0 ≤ 1 ≤ 1 with c=1 and n0=1 since n increases. n = ∞ 1.7.2.3 Big-Theta Notation (Θ) • We say that f(n) is Big-Theta of g(n), written as f(n) = Θ(g(n)), iff there are positive constants c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0 Equivalently, f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). If f(n) = Θ(g(n)), we say that g(n) is a tight bound on f(n). Example - n2/2-2n = Θ(n2) c1g(n) ≤ h(n) ≤ c2g(n) c1n2 ≤ n2/2-2n ≤ c2n2 c1n2/n2 ≤ n2/2n2-2n/n2 ≤ c2n2/n2 Divide by n2 c1 ≤ 1/2-2/n ≤ c2 O Determine c2 = ½ ½-2/n ≤ c2 = ½ ½-2/n = ½ maximum of ½-2/n Ω Determine c1 = 1/10 0 < c1 ≤ ½-2/n 0 < c1 minimum when n=5 0 < c1 ≤ ½-2/5 0 < c1 ≤ 5/10-4/10 = 1/10 n0 Determine n0 = 5 c1 ≤ ½-2/n0 ≤ c2 1/10 ≤ ½-2/n0 ≤ ½ 1/10-½ ≤ -2/n0 ≤ 0 Subtract ½ -4/10 ≤ -2/n0 ≤ 0 -4/10 n0 ≤ -2 ≤ 0 Multiply by n0 -n0 ≤ -2*10/4 ≤ 0 Multiply by 10/4 n0 ≥ 2*10/4 ≥ 0 Multiply by -1 n0 ≥ 5 ≥ 0 n0 ≥ 5 n0 = 5 satisfies Θ 0 < c1n2 ≤ n2/2-2n ≤ c2n2 ∀n ≥ n0 with c1=1/10, c2=½ and n0=5 1.5.3 Time Space Trade-off The best algorithm to solve a given problem is one that requires less memory space and less time to run to completion. But in practice, it is not always possible to obtain both of these objectives. One algorithm may require less memory space but may take more time to complete its execution. On the other hand, the other algorithm may require more memory space but may take less time to run to completion. Thus, we have to sacrifice one at the cost of other. In other words, there is Space-Time trade-off between algorithms. If we need an algorithm that requires less memory space, then we choose the first algorithm at the cost of more execution time. On the other hand if we need an algorithm that requires less time for execution, then we choose the second algorithm at the cost of more memory space. 1.6 ABSTRACT DATA TYPE It can be defined as a collection of data items together with the operations on the data. The word “abstract” refers to the fact that the data and the basic operations defined on it are being studied independently of how they are implemented. It involves what can be done with the data, not how has to be done. For ex, in the below figure the user would be involved in checking that what can be done with the data collected not how it has to be done. An implementation of ADT consists of storage structures to store the data items and algorithms for basic operation. All the data structures i.e. array, linked list, stack, queue etc are examples of ADT. 1.7 DATA STRUCTURE In computer science, a data structure is a particular way of storing and organizing data in a computer’s memory so that it can be used efficiently. Data may be organized in many different ways; the logical or mathematical model of a particular organization of data is called a data structure. The choice of a particular data model depends on the two considerations first; it must be rich enough in structure to mirror the actual relationships of the data in the real world. On the other hand, the structure should be simple enough that one can effectively process the data whenever necessary. 1.7.1 Need of data structure • It gives different level of organization data. • It tells how data can be stored and accessed in its elementary level. • Provide operation on group of data, such as adding an item, looking up highest priority item. • Provide a means to manage huge amount of data efficiently. • Provide fast searching and sorting of data. 1.7.2 Selecting a data structure Selection of suitable data structure involve following steps – • Analyze the problem to determine the resource constraints a solution must meet. • Determine basic operation that must be supported. Quantify resource constraint for each operation • Select the data structure that best meets these requirements. • Each data structure has cost and benefits. Rarely is one data structure better than other in all situations. A data structure require : � Space for each item it stores � Time to perform each basic operation � Programming effort. Each problem has constraints on available time and space. Best data structure for the task requires careful analysis of problem characteristics. 1.7.3 Type of data structure 1.7.3.1 Static data structure A data structure whose organizational characteristics are invariant throughout its lifetime. Such structures are well supported by high-level languages and familiar examples are arrays and records. The prime features of static structures are (a) None of the structural information need be stored explicitly within the elements – it is often held in a distinct logical/physical header; (b) The elements of an allocated structure are physically contiguous, held in a single segment of memory; (c) All descriptive information, other than the physical location of the allocated structure, is determined by the structure definition; (d) Relationships between elements do not change during the lifetime of the structure. 1.7.3.2 Dynamic data structure A data structure whose organizational characteristics may change during its lifetime. The adaptability afforded by such structures, e.g. linked lists, is often at the expense of decreased efficiency in accessing elements of the structure. Two main features distinguish dynamic structures from static data structures. Firstly, it is no longer possible to infer all structural information from a header; each data element will have to contain information relating it logically to other elements of the structure. Secondly, using a single block of contiguous storage is often not appropriate, and hence it is necessary to provide some storage management scheme at run-time. 1.7.3.3 Linear Data Structure A data structure is said to be linear if its elements form any sequence. There are basically two ways of representing such linear structure in memory. a) One way is to have the linear relationships between the elements represented by means of sequential memory location. These linear structures are called arrays.