LECTURE NOTES ON DATA STRUCTURES USING C

1 LECTURE NOTES ON DATA STRUCTURES USING C Revision 1 December, 2014 L. V. NARASIMHA PRASAD Professor Department of Computer Science and Engineering E. KRISHNA RAO PATRO Associate Professor Department of Computer Science and Engineering INSTITUTE OF AERONAUTICAL ENGINEERING DUNDIGAL 500 043, HYDERABAD 2014-2015 CONTENTS CHAPTER 1 BASIC CONCEPTS Introduction to Data STRUCTURES Data STRUCTURES : organizations of data Abstract Data Type (ADT) Selecting a data structure to match the operation Algorithm Practical Algorithm design issues Performance of a program Classification of Algorithms Complexity of Algorithms Rate of Growth Analyzing Algorithms Exercises Multiple Choice Questions CHAPTER 2 RECURSION Introduction to Recursion Differences between recursion and iteration Factorial of a given number The Towers of Hanoi Fibonacci Sequence Problem Program USING recursion to calculate the NCR of a given number Program to calculate the least common multiple of a given number Program to calculate the greatest common divisor Exercises Multiple Choice Questions CHAPTER 3 LINKED LISTS Linked List Concepts Types of Linked Lists Single Linked List Source Code for the Implementation of Single Linked List USING a header node Array based linked lists Double Linked List A Complete Source Code

2 For the Implementation of Double Linked List Circular Single Linked List Source Code for Circular Single Linked List Circular Double Linked List Source Code for Circular Double Linked List Comparison of Linked List Variations Polynomials Source code for polynomial creation with help of linked list Addition of Polynomials Source code for polynomial addition with help of linked list: Exercise Multiple Choice Questions ICHAPTER 4 STACK AND QUEUE Stack Representation of Stack Program to demonstrate a stack, USING array Program to demonstrate a stack, USING linked list Algebraic Expressions Converting expressions USING Stack Conversion from infix to postfix Program to convert an infix to postfix expression Conversion from infix to prefix Program to convert an infix to prefix expression Conversion from postfix to infix Program to convert postfix to infix expression Conversion from postfix to prefix Program to convert postfix to prefix expression Conversion from prefix to infix Program to convert prefix to infix expression Conversion from prefix to postfix Program to convert prefix to postfix expression Evaluation of postfix expression Applications of stacks Queue Representation of Queue Program to demonstrate a Queue USING array Program to demonstrate a Queue USING linked list Applications of Queue Circular Queue Representation of Circular Queue Deque Priority Queue Exercises Multiple

3 Choice Questions CHAPTER 5 BINARY TREES Trees Binary tree Binary tree Traversal Techniques Recursive Traversal Algorithms Building Binary tree from Traversal Pairs Binary tree Creation and Traversal USING Arrays Binary tree Creation and Traversal USING Pointers Non Recursive Traversal Algorithms Expression Trees Converting expressions with expression trees Threaded Binary tree Binary Search tree General Trees (m-ary tree ) Converting a m-ary tree (general tree ) to a binary tree Search and Traversal Techniques for m-ary trees Depth first search Breadth first search Sparse Matrices Exercises Multiple Choice Questions IICHAPTER 6 GRAPHS Introduction to Graphs Representation of Graphs minimum spanning tree Kruskal s Algorithm Prim s Algorithm Reachability Matrix Traversing a Graph Breadth first search and traversal Depth first search and traversal Exercises Multiple Choice Questions CHAPTER 7 SEARCHING AND SORTING Linear Search A non-recursive program for Linear Search A Recursive program for linear search Binary Search A non-recursive program for binary search A recursive program for binary search Bubble Sort Program for Bubble Sort Selection Sort Non-recursive Program for selection sort Recursive Program for selection sort Quick Sort

4 Recursive program for Quick Sort Priority Queue and Heap and Heap Sort Max and Min Heap data STRUCTURES Representation of Heap tree Operations on heap tree Merging two heap trees Application of heap tree Heap Sort Program for Heap Sort Priority queue implementation USING heap tree Exercises Multiple Choice Questions References and Selected Readings Index IIIC hapter 1 Basic Concepts The term data structure is used to describe the way data is stored, and the term algorithm is used to describe the way data is processed. Data STRUCTURES and algorithms are interrelated. Choosing a data structure affects the kind of algorithm you might use, and choosing an algorithm affects the data STRUCTURES we use. An Algorithm is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.

5 No matter what the input values may be, an algorithm terminates after executing a finite number of instructions. Introduction to Data STRUCTURES : Data structure is a representation of logical relationship existing between individual elements of data. In other words, a data structure defines a way of organizing all data items that considers not only the elements stored but also their relationship to each other. The term data structure is used to describe the way data is stored. To develop a program of an algorithm we should select an appropriate data structure for that algorithm. Therefore, data structure is represented as: Algorithm + Data structure = Program A data structure is said to be linear if its elements form a sequence or a linear list. The linear data STRUCTURES like an array, stacks, queues and linked lists organize data in linear order. A data structure is said to be non linear if its elements form a hierarchical classification where, data items appear at various levels.

6 Trees and Graphs are widely used non-linear data STRUCTURES . tree and graph STRUCTURES represents hierarchial relationship between individual data elements. Graphs are nothing but trees with certain restrictions removed. Data STRUCTURES are divided into two types: Primitive data STRUCTURES . Non-primitive data STRUCTURES . Primitive Data STRUCTURES are the basic data STRUCTURES that directly operate upon the machine instructions. They have different representations on different computers. Integers, floating point numbers, character constants, string constants and pointers come under this category. Non-primitive data STRUCTURES are more complicated data STRUCTURES and are derived from primitive data STRUCTURES . They emphasize on grouping same or different data items with relationship between each data item. Arrays, lists and files come under this category.

7 Figure shows the classification of data STRUCTURES . LECTURE NOTES Dept. of Information Technology 1 Dat a STRUCTURES Primit ive Dat a STRUCTURES Non- Pri mit iv e Da t a Struc ture s Integer Float Char Pointers Arrays Lists Files Non-Linear Lists Linear Lists Trees Graphs Queues Stacks Figure Classification of Data STRUCTURES Data STRUCTURES : Organization of data The collection of data you work with in a program have some kind of structure or organization. No matte how complex your data STRUCTURES are they can be broken down into two fundamental types: Contiguous Non-Contiguous. In contiguous STRUCTURES , terms of data are kept together in memory (either RAM or in a file). An array is an example of a contiguous structure. Since each element in the array is located next to one or two other elements. In contrast, items in a non-contiguous structure and scattered in memory, but we linked to each other in some way.

8 A linked list is an example of a non-contiguous data structure. Here, the nodes of the list are linked together USING pointers stored in each node. Figure below illustrates the difference between contiguous and non-contiguous STRUCTURES . 1 2 3 3 2 1 (a) Contiguous (b) non-contiguous Figure Contiguous and Non-contiguous STRUCTURES compared Contiguous STRUCTURES : Contiguous STRUCTURES can be broken drawn further into two kinds: those that contain data items of all the same size, and those where the size may differ. Figure shows example of each kind. The first kind is called the array. Figure (a) shows an example of an array of numbers. In an array, each element is of the same type, and thus has the same size. The second kind of contiguous structure is called structure, figure (b) shows a simple structure consisting of a person s name and age.

9 In a struct, elements may be of different data types and thus may have different sizes. LECTURE NOTES Dept. of Information Technology 2 For example, a person s age can be represented with a simple integer that occupies two bytes of memory. But his or her name, represented as a string of characters, may require many bytes and may even be of varying length. Couples with the atomic types (that is, the single data-item built-in types such as integer, float and pointers), arrays and structs provide all the mortar you need to built more exotic form of data structure, including the non-contiguous forms. int arr[3] = {1, 2, 3}; struct cust_data { int age; char name[20]; }; cust_data bill= {21, bill the student }; 1 2 3 (a) Array 21 bill the student (b) struct Figure Examples of contiguous STRUCTURES . Non-contiguous STRUCTURES : Non-contiguous STRUCTURES are implemented as a collection of data-items, called nodes, where each node can point to one or more other nodes in the collection.

10 The simplest kind of non-contiguous structure is linked list. A linked list represents a linear, one-dimension type of non-contiguous structure, where there is only the notation of backwards and forwards. A tree such as shown in figure (b) is an example of a two-dimensional non-contiguous structure. Here, there is the notion of up and down and left and right. In a tree each node has only one link that leads into the node and links can only go down the tree . The most general type of non-contiguous structure, called a graph has no such restrictions. Figure (c) is an example of a graph. A B C (a) Linked List A B C D G E F A B C D E F G (b) tree (c) graph Figure Examples of non-contiguous STRUCTURES LECTURE NOTES Dept. of Information Technology 3 Hybrid STRUCTURES : If two basic types of STRUCTURES are mixed then it is a hybrid form.