Data Structure Introduction for Beginners

Data Structure Introduction

1. DATA STRUCTURES Ramanathan G Department of Computer Science (UG) KRISTU JAYANTI COLLEGE

2. Data Data are simply collection of facts and figures. Data are values or set of values. Data Item 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 .

3. In the above example ( ID, Age, Gender, First, Middle, Last, Street, Area ) are elementary data items, whereas (Name, Address ) are group data items.

4. Data Structure Data structure is a method of organizing large amount of data more efficiently so that any operation on that data becomes easy. ☀ Every data structure is used to organize the large amount of data. ☀ Every data structure follows a particular principle ☀ The operations in a data structure should not violate the basic principle of that data structure .

5. 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.

6. Classification of Data Structure Data structure Primitive DS Non-Primitive DS Integer Float Character Pointer Float Integer Float

7. Classification of Data Structure Non-Primitive DS Linear List Non-Linear List Array Link List Stack Queue Graph Trees

8. Based on the organizing method of a data structure, data structures are divided into two types . Primitive Data Structures: If The integers, reals, logical data, character data, pointer and reference are primitive data structures. Data structures that normally are directly operated upon by machine-level instructions are known as primitive data structures . Non – Primitive Data Structures: The data type that are derived from primary data types are known as non-primitive data type. The non-primitive data types are used to store the group of values. The non-primitive data structures emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items.

9. Based on the organizing method of a data structure, data structures are divided into two types. Linear Data Structures: If a data structure is organizing the data in  sequential order , then that data structure is called as Linear Data Structure . Example: Arrays List (Linked List) Stack Queue Non - Linear Data Structures: If a data structure is organizing the data in random order, then that data structure is called as Non-Linear Data Structure.

10. Based on the organizing method of a data structure, data structures are divided into two types. Linear Data Structures: If a data structure is organizing the data in  sequential order , then that data structure is called as Linear Data Structure . Example: Arrays List (Linked List) Stack Queue Non - Linear Data Structures: If a data structure is organizing the data in random order, then that data structure is called as Non-Linear Data Structure.

11. Example: Tree Graph Dictionaries Heaps

12. Differences between primitive and non primitive d ata structures A primitive data structure is generally a basic structure that is usually built into the language, such as an integer, a float. A non-primitive data structure is built out of primitive data structures linked together in meaningful ways, such as a or a linked-list, binary search tree, AVL Tree, graph etc.

13. Homogeneous DS Homogeneous data structures are those data structures that contain only similar type of data e.g. like a data structure containing only integer or float values. The simplest example of such type of data structures is an Array. Non Homogeneous DS The non-homogeneous data structures are the one in which the data elements doesn't belong to the same data type. All the data elements have different data type. For example: classes, Structure, Union etc

14. Static Data Structure The memory allocation of elements in this data structure is done before the program execution (memory size allocated to data which is static). For Example: Arrays. Dynamic Data Structure In the data structure before the usage of the element their memory allocation is done with the use of D.M.A function. For example : Linked Lists

15. Operations on Data structures The most commonly used operation on data structure are broadly categorized into following types : Create : Creation of data . It reserves memory for the program elements. In a programming language, this operation can be performed by the variable declaration statement. For example, int x=10; This causes memory to be allocated for variable ‘x’ and it allows integer value 10 to be stored.

16. Select : Accessing of data with in a data structure . Example: printf (“% d”,a [5]); The array element a[5] is selected for printing . Update : - change data or modify the data in a data structure For example, int x=3; // declaration and initialization of x . . x=10; // Assignment statement Here , initially value 3 is assigned to x. Later value 10 is assigned to x. This modifies the value of x from 3 to 10. Consider x=x+5 ; This expression x=x+5 modifies 10, to the new value 15.

17. DESTROY This operation is used to destroy the data structure. In C programming, destroy operation, can be done using the function free(). This helps in efficient use of memory and prevents memory wastage.

18. 1. Traversing- It is the process of accessing or visiting each element exactly once to perform some operations on it.. 2 . Searching- It is used to find out the location of the data item if it exists in the given collection of data items . 3 . Inserting- It is used to add a new data item in the given collection of data items. 4. Deleting- It is used to delete an existing data item from the given collection of data items. 5. Sorting- It is used to arrange the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data. 6. Merging- It is used to combine the data items of two sorted files into single file in the sorted form.

19. Pointers: Pointers in C language is a variable that stores/points the address of another variable. A Pointer in C is used to allocate memory dynamically i.e. at run time. The pointer variable might be belonging to any of the data type such as int , float, char, double, short etc . Syntax : data_type * var_name ;  Example : int *p;  char *p ; Where, * is used to denote that “p” is pointer variable and not a normal variable.

20. Normal variable stores the value whereas pointer variable stores the address of the variable. The content of the C pointer always be a whole number i.e. address. & symbol is used to get the address of the variable. * symbol is used to get the value of the variable that the pointer is pointing to . Accessing the address of a variable: Any variable when declared and initialized is associated with the following: The memory location or address of the variable The name of the variable Value stored in the variable

21. Consider the statement int n=20;

22. #include < stdio.h > int main() {    int * ptr , q;    q = 50;    /* address of q is assigned to ptr */    ptr = &q;    /* display q's value using ptr variable */    printf ("%d", * ptr );    return 0; }

23. Recursion It is a function that calls itself during execution. It enables the function to repeat itself several times to solve a given problem. The various types of recursion are * Direct Recursion: A recursive function that invokes itself is said to have direct recursion. * Indirect Recursion : A function which contains a call to another function which in turn call another function and so on, and eventually calls the first function

24. For example: int fact( int n) { if(n==0) return 1; return n*fact(n-1); Direct Recursion } Indirect Recursion void f1() void f2() void f3() { { { - - - f2(); f3(); f1(); } } }

25. GCD or Greatest Common Divisor is also known as Highest Common Factor(HCF). It is the largest number that can divide each of the number exactly.     The GCD of two positive integers x and y is defined recursively as follows. Euclid’s Algorithm x if(y==0) GCD ( x, y ) GCD( y, x ) if (y>x) GCD (y, x % y) otherwise   Where x % y is x modulo y, the remainder of dividing x by y

26. #include< stdio.h > void main() { int x,y,res ; printf ("Enter 2 numbers\n"); scanf ("%d % d",&x,&y ); res= gcd ( x,y ); printf ("GCD of %d and %d = %d\n", x,y,res ); }  

27. /*GCD function*/ int gcd ( int x,int y) { if(y ==0) return(x ); else if(y>x) return( gcd ( y,x )); else return( gcd ( y,x%y )); }  

28. GCD (48, 14) m=48 n=14 If (14 ==0) no Else gcd (14, 48%14) gcd (14,6) If (6==0) no Else gcd (6, 14%6) gcd (6,2) If (2==0) no Else gcd (2, 6%2)= gcd (2,0) If (0==0) return 2 Value =2

29. Algorithm Step1: Start Step2: Accept two numbers a and b Step3: Call the function res= gcd ( a,b ) Step4: Print res Step5: Stop Algorithm for gcd ( a,b ) Step1: If a==b return (a) else if(a>b) return( gcd (a- b,b ) else return ( gcd ( a,b -a) End if  

30. //Program to find GCD of two numbers using recursion . #include< stdio.h > void main() { int a,b,res ; clrscr (); printf ("\ nGreatest Common Divisor\n"); printf ("Enter the value for a : "); scanf ("% d",&a ); printf ("Enter the value for b : "); scanf ("% d",&b ); res= gcd ( a,b ); printf ("The Greatest Common Divisor of %d and %d is %d", a,b,res ); getch (); }

31. int gcd ( int a,int b) { if(a==b) { return(a); } else {   if(a>b) return( gcd (a- b,b )); else return( gcd ( a,b -a)); } }  

32. GCD (20, 12) a=20 b=12 If (20>12) return( gcd (20-12,12) Gcd (8,12) If ( 8 >12 ) return no Else return ( gcd (8,12-8) Gcd ( 8,4) If(8>4) return gcd (8-4,4) Gcd (4,4) If (4==4) Return (4)

33. Algorithm Step1: Start Step2: Accept two numbers n and r Step3: If n<r Print “Invalid input” Else result=fact(n)/(fact(r)*fact(n-r)) Print result End if Stop

34. Algorithm for Fact(x) Step1: If x=0 return 1 Else return x*fact(x-1) End if

35. //Program to find Binomial Coefficient #include< stdio.h > void main() { int n,r ; int fact( int ); clrscr (); printf ("\ nEnter the value for n:"); scanf ("% d",&n ); printf ("\ nEnter the value for r:"); scanf ("% d",&r ); if(n<r) printf ("Invalid Input\n");

36. else printf ("\ nBinomial Coefficient nCr is % d",fact (n)/(fact(n-r)*fact(r))); getch (); } int fact( int x) { if(x==0||x==1) return 1; else return(x*(fact(x-1))); }

37. If(x==0 ||x=1) return 1 Return(4*fact(4-1)) (4*fact(3)) (4*(3*fact(3-1)) (4*3*(2*fact(2)) 4*3*2*fact(2-1)) 4*3*2*fact(1)) 4*3*2*1

38. Direct Computation Method Fibonacci numbers : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... where each number is the sum of the preceding two. Recursive definition: F(0) = 0; F(1) = 1; F(number) = F(number-1)+ F(number-2);

39. /*Program to print the Fibonacci sequence*/ #include < stdio.h > int fib( int n); void main() { int i,n ; printf ("\ nEnter a number\n"); scanf ("% d",&n ); printf (“Fibonacci sequence:\n”); for( i =0;i< n;i ++) printf ("%d \ t",fib ( i )); }

40. /*Program to print the Fibonacci sequence*/ /* fibonnacci function*/ int fib( int n) { if((n==0)||(n==1)) return(n); else return(fib(n-1)+fib(n-2)); }

41. Trace a Fibonacci Number Assume the input number is 4, that is, num=4: fib(4): 4 == 0 ? No; 4 == 1? No. fib(4) = fib(3) + fib(2) fib(3): 3 == 0 ? No; 3 == 1? No. fib(3) = fib(2) + fib(1) fib(2): 2 == 0? No; 2==1? No. fib(2) = fib(1)+fib(0) fib(1): 1== 0 ? No; 1 == 1? Yes. fib(1) = 1; return fib(1) ; int fib( int num ) { if ( num == 0) return 0; if ( num == 1) return 1; return (fib(num-1)+fib(num-2)); }

42. Trace a Fibonacci Number fib(0): 0 == 0 ? Yes. fib(0) = 0; return fib(0); fib(2) = 1 + 0 = 1; return fib(2); fib(3) = 1 + fib(1) fib(1): 1 == 0 ? No; 1 == 1? Yes fib (1) = 1; return fib (1) ; fib(3) = 1 + 1 = 2; return fib(3)

43. Trace a Fibonacci Number fib(2): 2 == 0 ? No; 2 == 1? No. fib(2) = fib(1) + fib(0) fib(1): 1== 0 ? No; 1 == 1? Yes. fib(1) = 1; return fib(1); fib(0): 0 == 0 ? Yes. fib(0) = 0; return fib(0); fib(2) = 1 + 0 = 1; return fib(2); fib(4) = fib(3) + fib(2) = 2 + 1 = 3; return fib(4);

44. TOWER OF HANOI

45. ++-

46. Memory allocation is the process of setting aside sections of memory in a program to be used to store variables, and instances of structures and classes. Memory allocation has two core types; Static Memory Allocation: The program is allocated memory at compile time . Static memory allocation means we reserve a certain amount of memory by default, inside our program to use for variables. It is fixed in size. It need not grow or shrink in size. The standard method of creating an array of 10 integers on the stack is: int arr [10]; This means 10 memory locations are allocated to hold 10 integers. Memory is said to be allocated statically .

47. Dynamic Memory Allocation: The programs are allocated with memory at run time . Dynamic memory allocation allows your program to obtain more memory space while running, or to release it if it's not required. In simple terms, Dynamic memory allocation allows you to manually handle memory space for your program.

48. malloc () The name malloc stands for "memory allocation". The function  malloc () reserves a block of memory of specified size and return a  pointer  of type void which can be casted into pointer of any form. Syntax of malloc () ptr = (cast-type*) malloc (byte-size ) Here ,  ptr  is pointer of cast-type. The  malloc () function returns a pointer to an area of memory with size of byte size. If the space is insufficient, allocation fails and returns NULL pointer. ptr = ( int *) malloc (100 * sizeof ( int )); This statement will allocate either 200 or 400 according to size of  int  2 or 4 bytes respectively and the pointer points to the address of first byte of memory .

49. C  calloc () The name calloc stands for "contiguous allocation". The only difference between malloc () and calloc () is that, malloc () allocates single block of memory whereas calloc () allocates multiple blocks of memory each of same size and sets all bytes to zero. Syntax of calloc () ptr = (cast-type*) calloc (n, element-size ); This statement will allocate contiguous space in memory for an array of  n  elements . For example: ptr = (float*) calloc (25, sizeof (float));This statement allocates contiguous space in memory for an array of 25 elements each of size of float, i.e , 4 bytes.

50. free() Dynamically allocated memory created with either calloc () or malloc () doesn't get freed on its own. You must explicitly use free() to release the space. syntax of free() free( ptr ); This statement frees the space allocated in the memory pointed by  ptr . realloc () If the previously allocated memory is insufficient or more than required, you can change the previously allocated memory size using realloc (). Syntax of realloc () ptr = realloc ( ptr , newsize ); Here ,  ptr  is reallocated with size of newsize .

51. #include< stdio.h > # include< string.h > # include< stdlib.h > int main() { char * mem_alloc ; /* memory allocated dynamically */ mem_alloc = malloc ( 15 * sizeof (char) ); if( mem_alloc == NULL ) { printf ("Couldn't able to allocate requested memory\n"); } else { strcpy ( mem_alloc,"w3schools.in"); } printf ("Dynamically allocated memory content : %s\n", mem_alloc ); free( mem_alloc ); }

52. #include< stdio.h > #include< string.h > #include< stdlib.h > int main() { char * mem_alloc ; mem_alloc = calloc ( 15, sizeof (char ));/*memory allocated dynamically*/ if( mem_alloc == NULL ) { printf ("Couldn't able to allocate requested memory\n "); } else { strcpy ( mem_alloc,"w3schools.in"); } printf ("Dynamically allocated memory content : %s\n", mem_alloc ); free( mem_alloc ); }

53. #include < stdio.h > #include < string.h > #include < stdlib.h > int main() { char * mem_allocation ; /*memory is allocated dynamically */ mem_allocation = malloc ( 20 * sizeof (char) ); if( mem_allocation == NULL ) { printf ("Couldn't able to allocate requested memory\n"); } else { strcpy ( mem_allocation,"fresh2refresh.com "); } printf ("Dynamically allocated memory content : " \ "%s\n", mem_allocation );

54. mem_allocation = realloc (mem_allocation,100* sizeof (char )); if( mem_allocation == NULL ) { printf ("Couldn't able to allocate requested memory\n"); } else { strcpy ( mem_allocation,"space is extended upto " \ "100 characters"); } printf ("Resized memory : %s\n", mem_allocation ); free( mem_allocation ); }