Lecture notes on Data structure using C

DATA STRUCTURE THROUGH C LANGUAGE lecture notes pdf free download
ShawnPacinocal Profile Pic
ShawnPacinocal,United States,Researcher
Published Date:09-07-2017
Your Website URL(Optional)
MCA06 KRISHNA KANTA HANDIQUI STATE OPEN UNIVERSITY Housefed Complex, Dispur, Guwahati - 781 006 Master of Computer Applications DATA STRUCTURE THROUGH C LANGUAGE CONTENTS UNIT 1 : INTRODUCTION TO DATA STRUCTURE UNIT 2 : ALGORITHMS UNIT 3 : LINKED LIST UNIT 4 : STACK UNIT 5 : QUEUE UNIT 6 : SEARCHING UNIT 7 : SORTING UNIT 8 : THREE UNIT 9 : GRAPHUNIT 1 : INTRODUCTION TO DATA STRUCTURE UNIT STRUCTURE 1.1 Learning Objectives 1.2 Introduction 1.3 Data and Information 1.4 Data Structure and Its Types 1.5 Data Structure Operations 1.6 Concept of Data Types 1.7 Dynamic Memory Allocation 1.8 Abstract Data Types 1.9 Let Us Sum Up 1.10 Answers to Check Your Progress 1.11 Further Readings 1.12 Model Questions 1.1 LEARNING OBJECTIVES After going through this unit, you will able to :  distinguish data and information  learn about data structure  define various types of data structures  know different data structure operations  describe about data types in C  define abstract data types 1.2 INTRODUCTION A data structure in Computer Science, is a way of storing and organizing data in a computer’s memory or even disk storage so that it can be used efficiently. It is an organization of mathematical and logical concepts of data. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory Data Structure Through C Language 5Introduction to Data Structure Unit 1 space, as possible. Data structures are implemented by a programming language by the data types and the references and operations provide by that particular language. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases. In the design of many types of computer program, the choice of data structures is a primary design consideration. Experience in building large systems has shown that the difficulty of implementation and the quality and performance of the final result depends heavily on choosing the best data structure. In this unit, we will introduce you to the fundamental concepts of data structure. In this unit, we shall discuss about the data and information and overview of data structure. We will also discuss the types of data structure, data structure operations and basic concept of data types. 1.3 DATA AND INFORMATION The term data comes from its singular form datum, which means a fact. The data is a fact about people, places or some entities. In computers, data is simply the value assigned to a variable. The term variable refers to the name of a memory location that can contain only one data at any point of time. For example, consider the following statements : Vijay is 16 years old. th Vijay is in the 12 standard. Vijay got 80% marks in Mathematics. Let ‘name’, ‘age’, ‘class’, ‘marks’ and ‘subject’ be some defined variables. Now, let us assign a value to each of these variables from the above statements. Name = Vijay Class = 12 Age = 16 Marks = 80 Subject = Mathematics 6 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 In the above example the values assigned to the five different variables are called data. We will now see what is information with respect to computers. Information is defined as a set of processed data that convey the relationship between data considered. Processing means to do some operations or computations on the data of different variables to relate them so that these data, when related, convey some meaning. Thus, information is as group of related data conveying some meaning. In the examples above, when the data of the variables ‘name’ and ‘age’ are related, we get the following information: Vijay is 16 years old. In the same example, when the data of the variables ‘name’ and ‘class’ are related we get another information as Vijay is in the 12th standard. Further, when we relate the data of the variables, ‘name’, ‘marks’, and ‘subject’, we get more information that Vijay got 80% marks in Mathematics. The following figure shows how information can be drawn from data. Methods to Data Process Data Information Fig 1.1 : Relation between data and information 1.4 DATA STRUCTURE AND ITS TYPES The way in which the various data elements are organized in memory with respect to each other is called a data structure. Data structures are the most convenient way to handle data of different types including abstract data type for a known problem. Again problem solving is an essential part of every scientific discipline. To solve a given problem by using a computer, you need to write a program for it. A program consists of two components : algorithm and data structure. Many different algorithms can be used to solve the same problem. Similarly, various types of data structures can be used to represent a problem in a computer. Data Structure Through C Language 7Introduction to Data Structure Unit 1 To solve the problem in an efficient manner, you need to select a combination of algorithms and data structures that provide maximum efficiency. Here, efficiency means that the algorithm should work in minimal time and use minimal memory. In addition to improving the efficiency of an algorithm, the use of appropriate data structures also allows you to overcome some other programming challenges, such as : – simplifying complex problems – creating standard, reusable code components – creating programs that are easy to understand and maintain Data can be organized in many different ways; therefore, you can create as many data structures as you want. However, data structures have been classified in several ways. Basically, data structures are of two types : linear data structure and non linear data structure. Linear data structure : a data structure is said to be linear if the elements form a sequence i.e., while traversing sequentially, we can reach only one element directly from another. For example : Array, Linked list, Queue etc. Non linear data structure : elements in a nonlinear data structure do not form a sequence i.e each item or element may be connected with two or more other items or elements in a non-linear arrangement. Moreover removing one of the links could divide the data structure into two disjoint pieces. For example : Trees and Graphs etc. The following figures shows the linear and nonlinear data structures. Top . . . Stack 8 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 Front Rear Queue Fig 1.2 : Linear data structure Tree Fig 1.3 : Non linear data structure All these data structures are designed to hold a collection of data items. 1.5 DATA STRUCTURE OPERATIONS We come to know that data structure is used for the storage of data in computer so that data can be used efficiently. The data manipulation within the data structures are performed by means of certain operations. In fact, the particular data structure that one chooses for a given situation depends largely on the frequency with which specific operations are performed. The following four operations play a major role on data structures. a) Traversing : accessing each record exactly once so that certain items in the record may be processed. (This accessing and processing is sometimes called “visiting” the record.) Data Structure Through C Language 9Introduction to Data Structure Unit 1 b) Searching : finding the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions. c) Inserting : adding a new record to the structure. d) Deleting : removing a record from the structure. Sometimes two or more of these operations may be used in a given situation. For example, if we want to delete a record with a given key value, at first we willl have need to search for the location of the record and then delete that record. The following two operations are also used in some special situations : i) Sorting : operation of arranging data in some given order, such as increasing or decreasing, with numerical data, or alphabatically, with character data. ii) Merging : combining the records in two different sorted files into a single sorted file. 1.6 CONCEPT OF DATA TYPES We have already familiar with the term ‘data type’. A data type is nothing but a term that refers to the type of data values that may be used for processing and computing. The fundamental data types in C are char, int, float and double. These data types are called built-in data types. There are three categories of data types in C, they are: a) Built-in types, includes char, int, float and double b) Derived data types, includes array and pointers c) User defined types, includes structure, union and enumeration. In this section, we will briefly review about the data types array, pointers and structures. i) Array : An array is a collection of two or more adjacent memory locations containing same types of data. These data are the array elements. The individual data items can be characters, integers, floating-point numbers, etc. However, they must all be of the same type and the same storage class. 10 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 Each array element (i.e., each individual data item) is referred to by specifying the array name followed by one or more subscripts, with each subscript enclosed in square brackets. The syntax for declaration of an array is Storage Class datatype arrayname expression Here, storage class may be auto, static or extern, which you just remember, storage class refers to the permanence of a variable, and its scope within the program, i.e., the portion of the program over which the variable is recognized. If the storage class is not given then the compiler assumes it is an auto storage class. The array can be declared as : int x15; x is an 15 element integer array char name25; name is a 25 element character array In the array x, the array elements are x0, x1, ........., x14 as illustrated in the fig. Fig 1.4 : An array data structure Array can be initialize at the time of the declaration of the array. For example, int marks 5 = 85, 79, 60, 87, 70 ; Then, the marks array can be represented as follows : 85 79 60 87 70 marks 0 marks 1 marks 2 marks 3 marks 4 Fig 1.5 : the marks array after initialization In the case of a character array name we get it as char name 20 = “krishna” K r i s h n a \0 name 0 name 1 name 2 name 3 name 4 name5 name6 name7 Fig 1.6 : name array after initialization Data Structure Through C Language 11Introduction to Data Structure Unit 1 We know that every character string terminated by a null character (\0). Some more declarations of arrays with initial values are given below : char vowels = ‘A’, ‘E’, ‘I’, ‘O’, ‘U’ ; int age = 16, 21, 19, 5, 25 In the above case, compiler assumes that the array size is equal to the number of elements enclosed in the curly braces. Thus, in the above statements, size of array would automatically assumed to be 5. If the number of elements in the initializer list is less than the size of the array, the rest of the elements of the array are initialized to zero. The number of the subscripts determines the dimensionality of the array. For example, marks i, refers to an element in the one dimensional array. Similarly, matrix i j refers to an element in the two dimensional array. Two dimensional arrays are declared the same way that one dimensional arrays. For example, int matrix 3 5 is a two dimensional array consisting of 3 rows and 5 column for a total of 20 elements. Two dimensional array can be initialized in a manner analogous to the one dimensional array : int matrix 3 5 = 10, 5, -3, 9, 2 , 1 , 0, 14, 5, 6 , -1, 7, 4, 9, 2 ; The matrix array can be represented as follows: 12 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 Column1 column2 column3 column4 column5 00 01 02 03 04 row 0 10 5 -3 9 2 10 11 12 13 14 row 1 1 0 14 5 6 20 21 22 23 24 -1 7 4 9 2 row 2 Fig. 1.7 : Matrix array after initialization The above statement can be written as follows : int matrix 3 5 = 10,5,-3,9,2,1,0,14,5,6,-1,7,4,9,2 A statement such as int matrix 3 5 = 10, 5, -3 , 1 , 0, 14 , -1, 7, 4 ; only initializes the first three elements of each row of the two dimensional array matrix. The remaining values are set to 0. A Simple Program Using One - dimensional Array A one dimensional array is used when it is necessary to keep a large number of items in memory and reference all the items in a uniform manner. Let us try to write a program to find average marks obtained by a class of 30 students in a test. includestddio.h includeconio.h void main( ) Data Structure Through C Language 13Introduction to Data Structure Unit 1 int avg, sum = 0 ; int i ; int marks30 ; / array declaration / clrscr( ); for ( i = 0 ; i = 29 ; i++ ) printf ( “\nEnter marks “ ) ; scanf ( “%d”, &marksi ) ; / store data in array / for ( i = 0 ; i = 29 ; i++ ) sum = sum + marksi ; / read data from an array/ avg = sum / 30 ; printf ( “\nAverage marks = %d”, avg ) ; getch( ); A Simple Program Demonstrating the use of Two Dimensional Array : A transpose of a matrix is obtained by interchanging its rows and T columns. If A is a matrix of order m x n then its transpose A will be of order n x m. Let us implement this program using two dimensional array as follows: includestdio.h includeconio.h void main() int matrix1 2020, matrix2 2020, i, j, m, n; clrscr(); printf(“Enter the Rows and Column of matrix \n”); scanf(“%d %d”, &m, &n); printf(“Enter the elements of the Matrix \n”); for( i=1; im+1; i++) for(j=1; jn+1; j++) scanf(“%d”, &matrix1 ij); for(i=1; in+1; i++) for(j=1; jm+1; j++) / stores the elements in matrix2 / matrix2 ij = matrix1 ji; 14 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 printf(“\n \t Transpose of Matrix \n”); for(i=1; in+1; i++) for(j=1; jm+1; j++) printf( “%3d”, matrix2 ij); printf(“\n”); getch(); ii) Pointers : You have already introduced to the concept of pointer. At this moment we will recall some of its properties and applications. A pointer is a variable that represents the location (rather than the value) of a data item, such as a variable or an array element. Suppose we define a variable called sum as follows : int sum = 25; Let us define an another variable, called pt_sum like the following way int pt_sum; It means that pt_sum is a pointer variable pointing to an integer, where is a unary operator, called the indirection operator, that operates only on a pointer variable. We have already used the ‘&’ unary operator as a part of a scanf statement in our C programs. This operator is known as the address operator, that evaluates the address of its operand. Now, let us assign the address of sum to the variable pt_sum such as pt_sum = ∑ Now the variable pt_sum is called a pointer to sum, since it “points” to the location or address where sum is stored in memory. Remember, that pt_sum represents sum’s address, not its value. Thus, pt_sum referred to as a pointer variable. The relationship between pt_sum and sum is illustrated in Fig. Data Structure Through C Language 15Introduction to Data Structure Unit 1 Fig. 1.8 : Relationship between pt_sum and sum The data item represented by sum (i.e., the data item stored in sum’s memory cells) can be accessed by the expression pt_sum. Therefore, pt_sum and sum both represent the same data item i.e. 25. Several typical pointer declarations in C program are shown below int alpha ; char ch ; float s ; Here, alpha, ch and s are declared as pointer variables, i.e. variables capable of holding addresses. Remember that, addresses (location nos.) are always going to be whole numbers, therefore pointers always contain whole numbers. The declaration float s does not mean that s is going to contain a floating-point value. What it means is, s is going to contain the address of a floating-point value. Similarly, char ch means that ch is going to contain the address of a char value. Let us try to write a program that demonstrate the use of a pointer: include stdio.h includeconio.h void main( ) int a = 5; int b; b = &a; clrscr(); printf (“value of a = %d\n”, a); printf (“value of a = %d\n”, (&a)); printf (“value of a = %d\n”, b); printf (“address of a = %u\n”, &a); 16 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 printf (“address of a = %d\n”, b); printf (“address of b = %u\n”, &b); printf (“value of b = address of a = %u”, b); getch(); Suppose address of the variable a = 1024, b = 2048 OUTPUT : value of a = 5 value of a = 5 value of a = 5 address of a = 1024 address of a = 1024 value of b = address of a = 1024 Pointer to Pointer : A pointer to a pointer is a techniques used frequently in more complex programs. To declare a pointer to a pointer, place the variable name after two successive asterisks (). In this case one pointer variable holds the address of the another pointer variable. In the following shows a declaration of pointer to pointer : int x; Following program shows the use of pointer to pointer techniques : include stdio.h includeconio.h void main( ) int a = 5; int b; int c; b = &a; c = &b; Data Structure Through C Language 17Introduction to Data Structure Unit 1 printf (“value of a = %d\n”, a); printf (“value of a = %d\n”, (&a)); printf (“value of a = %d\n”, b); printf (“value of a = %d\n”, c); printf (“value of b = address of a = %u\n”, b); printf (“value of c = address of b = %u\n”, c); printf (“address of a = %u\n”, &a); printf (“address of a = %u\n”, b); printf (“address of a = %u\n”, c); printf (“address of b = %u\n”, &b); printf (“address of b = %u\n”, c); printf (“address of c = %u\n”, &c); getch(); Suppose address of the variable a = 1024, b = 2048 OUTPUT : value of a = 5 value of a = 5 value of a = 5 value of a = 5 value of b = address of a = 1024 value of c = address of b = 2048 address of a = 1024 address of a = 1024 address of a = 1024 address of b = 2048 address of b = 2048 address of c = 4096 18 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 CHECK YOUR PROGRSS Q.1. Describe the array that is defined in each of the following statements. Indicate what values are assigned to the individual array elements. a) char flag5= ‘ T ‘ , ‘ R ‘ , ‘ U ‘ , ‘E’ ; c) int p24 = 1, 3, 5, 7 , 2, 4, 6, 8 ; Q.2. Define a one-dimensional, six-element floating-point array called consts. Assign the following values to the array elements: 0.005, -0.032, 1e-6, 0.167, -0.3e8, 0.015 Q.3. Explain the meaning of each of the following declarations a) float a, b; float pa, pb; b) float a = -0.167; float pa = &a; c) char d4 = “north‘, ‘south”, “east”, “west”; iii) Structure : Structure is the most important user defined data type in C. A structure is a collection of variables under a single name. These variables can be of different types, and each has a name which is used to select it from the structure. But in an array, all the data items are of same type. The individual variables ina structure are called member variables. A structure is a convenient way of grouping several pieces of related information together. Here is an example of a structure definition. Data Structure Through C Language 19Introduction to Data Structure Unit 1 struct student char name25; char course20; int age; int year; ; Declaration of a structure always begins with the key word struct followed by a user given name, here the student. Recall that after the opening brace there will be the member of the structure containing different names of the variables and their data types followed by the closing brace and the semicolon. Graphical representation of the structure student is shown below : Student name course age year Fig. 1.9 : A structure named Student Now let us see how to declare a structure variable. In the following we have declare a variable st_rec of type student : student st_rec100; In this declaration st_rec is a 100 element array of structures. Hence each element of st_rec is a separate structure of type student (i.e. each element of st_rec represents an individual student record.) Having declared the structure type and the structure variables, let us see how the elements of the structure can be accessed. In arrays we can access individual elements of an array using a subscript. Structures 20 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 use a different scheme. They use a dot (.) operator. As an example if we want to access the name of the 10th student (i.e. st_rec9 since the subscript begins with 0) from the above structure then we will have to write st_rec9.name Similarly, course and age of the 10th student can be accessed by writing st_rec9.course and st_rec9.age The members of a structure variable can be assigned initial values in much the same manner as the elements of an array. Example of assigning the values for the 10th student record is shown in the following : struct student st_rec9 = “Arup Deka”, “BCA”, 21, 2008 ; A simple example of using of the structure data type is shown below : includestdio.h includeconio.h void main( ) struct book char name ; float price ; int pages ; ; struct book b1, b2, b3 ; clrscr(); printf ("\nEnter names, prices & no. of pages of 3 books\n" scanf ("%c %f %d", &b1.name, &b1.price, &b1.pages); scanf ("%c %f %d", &b2.name, &b2.price, &b2.pages); scanf ("%c %f %d", &b3.name, &b3.price, &b3.pages); printf ("\nAnd this is what you entered"); printf ("\n%c %f %d", b1.name, b1.price, b1.pages); printf ("\n%c %f %d", b2.name, b2.price, b2.pages); Data Structure Through C Language 21Introduction to Data Structure Unit 1 printf ("\n%c %f %d", b3.name, b3.price, b3.pages); getch(); Self-referencial structure : When a member of a structure is declared as a pointer that points to the same structure (parent structure), then it is called a self-referential structure. It is expressed as shown below: struct node int data; struct node next; ; where ‘node’ is a structure that consists of two members one is the data item and other is a pointer variable holding the memory address of the other node.The pointer variable next contains an address of either the location in memory of the successor node or the special value NULL. Self-referential structures are very useful in applications that involves linked data structures such as linked list and trees. The basic idea of a linked data structure is that each component wiithin the structure includes a pointer indicating where the next component can be found. Therefore, the relative order of the components can easily be changed simply by altering the pointers. In addition, individual components can easily be added or deleted again by altering the pointers. The diagramatic representation of a node is shown below : Fig. 1.10 : A node structure 1.7 DYNAMIC MEMORY ALLOCATION The memory allocation process may be classified as static allocation and dynamic allocation. In static allocation, a fixed size of memory are reserved before loading and execution of a program. If that reserved memory is not sufficient or too large in amount then it may cause failure of the program 22 Data Structure Through C LanguageIntroduction to Data Structure Unit 1 or wastage of memory space. Therefore, C language provides a technique, in which a program can specify an array size at run time. The process of allocating memory at run time is known as dynamic memory allocation. There are three dynamic momory allocation functions and one memory deallocation (releasing the memory) function. These are malloc( ), calloc( ), realloc( ) and free( ). malloc( ) : The function malloc( ) allocates a block of memory. The malloc( ) function reserves a block of memory of specified size and returns a pointer of type void. The reserved block is not initialize to zero. The syntax for usinig malloc( ) function is : ptr = (cast-type ) malloc( byte-size); where ptr is a pointer of type cast-type. The malloc( ) returns a pointer (of cast-type) to an area of memory with size byte-size. Suppose x is a one dimensional integer array having 15 elements. It is possible to define x as a pointer variable rather than an array. Thus, we write, int x; instead of int x15 or define size 15 int xsize; When x is declared as an array, a memory block having the capacity to store 15 elements will be reserved in advance. But in this case, when x is declared as a pointer variable, it will not assigned a memory block automatically. To assign sufficient memory for x, we can make use of the library function malloc, as follows : x = (int ) malloc(15 sizeof (int)); This function reserves a block of memory whose size (in bytes) is equivalent to 15 times the size of an integer. The address of the first byte of the reserved memory block is assigned to the pointer x of type int. Diagammatic representation is shown below : Data Structure Through C Language 23