@ Lecture Notes Data Structures and Applications [18CS33] 1, Introduction Data Structures are the models for organizing the data so that accessing becomes easy. They deal with the study of how data is organized in memory, how it ean be manipulated, how efficiently it can be retrieved, and the possible ways in which different data items are logically related. 1.1 Data Structures Classification The different types of data structures are Y Primitive Data Structures Data structures which can be manipulated directly by machine instructions are called ive data structures. int, float, char ete. Y Non-Primitive Data Structures Data structures which cannot be manipulated directly by machine instructions are called non-primitive data structures. The different types of non-primitive data structures are - Linear Data Structures: The elements here exhibit either physical adjacency or logical adjacency between them. Here the data is arranged in a linear fashion although the way they are stored in memory need not be sequential. EX: Arrays are physically adjacent i. locations. Linked Lists are logically adjacent ie. they are linked by pointers. elements are stored in consecutive memory = Non-Linear Data Structures: They do not exhibit any adjacency between elements but are logically related. Here data is not arranged in a sequential way, EX: Trees, Graphs etc. 1.2 Data Structures Operations “The following are the operations that can be performed on data structures 1, Create - This operation is used to create a data structure, In most of the programming anguages this is usually done using a simple declarations statement, For example, the declaration "int a;" allocates memory for the integer ‘a’ during compilation of the declaration statement. 2. Insertion - Insertion means adding new details or new node into the data structure. 3. Deletion - Deletion means removing the existing details or a node from the data structure. Module 1 1 Scanned with CamScannerLecture Notes Data Structures and Applications [18CS33] 4. Update - Update means changing the existing details or contents of a node in the data structure, 5. Traversal - Traversing means accessing cach node exactly once so that the nodes of a also called as visiting. data structure can be processed. Traversiny 6. Searching - Searching means finding the location of node for a given key value. 7. Sorting - Sorting means arranging the nodes in a particular order. 8. Merging - Merging means combining the nodes from two lists into a single list. Example: An organization contains a membership file for every department in the organization wherein cach record contains the following data for a given member. Name ] Address | Phone Number | Email] Age | DOB 1. Suppose a new person joins the organization, then one would insert his or her record to the file. 2. Suppose a person resigns from the organization, then one would delete his or her record from the file. 3. Suppose a member has moved to a new location and has a new address, then one ‘would update his or her record in the file. 4. Suppose the organization wants to organize a meeting though mailing, then one would traverse the file to obtain the name and email of each member. ‘5. Suppose one wants to find the address for a given name, then one would search the file for the record containing the name. 6. Suppose one wants the list of members in increasing order of their age, then one would sort the file based on age. 7. Suppose one wants a consolidated list of members from 2 different departments, then ‘one would merge the files of 2 different departments into a single file, Dr.MaheshG Mr.Harish G ‘Assoc. Prof. _-Assoe. Prof. eMSITE Mt be 1.3 Data Structures Representation ‘Any data structure can be represented using one of the following two ways. 1, Sequential Representation - A sequential representation maintains the data in continuous memory locations which takes less time to retrieve the data but leads to time complexity during insertion and deletion operations. Because of sequential nature, the elements of the list must be freed, when we want to insert a new element or new data at a particular position of the list. To acquire free space in the list, one must shift the data of the list towards the right side from the position where the data Module 1 2 Scanned with CamScannerSS Qh EO ————————e Lecture Notes Data Structures and Applications [17CS33] has to be inserted. Thus, the time taken by CPU to shift the data will be much higher y in the algorithm. Similarly, than the insertion operation and will lead to complexi while deleting an item from the list, one must shift the data items towards the left side of the list, which may waste CPU time. 2. Linked Representation - Linked representation maintains the list by means of a link between the adjacent elements which need not be stored in continuous memory locations. During insertion and deletion operations, links will be created or removed between which takes less time when compared to the corresponding operations of sequential representation, DrMaheshG Mr.Harish G ‘Assoc. Prof. Assoc. Prof. eusitaM nat 1.4 Algorithm Specification @ Definition: An algorithm is a finite set of instructions that accomplishes a particular task. The eriteria’s that must be satisfied are 1, Input: Zero or more quantities are extemally supplied. 2. Output: At least one quantity is produced. 3. Definiteness: Each instruction must be clear and unambiguous. 4. Finiteness: The algorithm always terminates after a finite number of steps and uses finite sources. 5. Effectiveness: Every instruction must be basic enough to be carried out. Note: In Computational theory a program does not have to satisfy the 4th criterion (Finiteness).Example, an operating system continues in a wait loop until more jobs are @ entered and will not terminate unless the system crashes. Since the programs that we discuss will always terminate, we use algorithm and program interchangeably here after. ‘Methods of specit g an algorithm 1. Using a natural language: a clear description of algorithms is surprisingly difficult because of the inherent ambiguity associated with any natural language. 2. Flowchart: is a method of expressing an algorithm by a collection of geometric shapes containing descriptions of the algorithm's steps. They work well only if the algorithm is small and simple. 3. Pseudo code: is a mixture of a natural language and programming language like constructs(C) giving a semi-formal description of each step to be carried out by the ‘computer. Module 1 3 Scanned with CamScanner———————————— Lecture Notes Data Structures and Applications [ 17833] 2. Pointers 2.1 Memory Organization ich byte (e = Bbits). rence of byte sized locations (1 byt er values that Memory is organized as a sequ unique address. Add integer constant corresponding to in memory is associated with a resses are positive integ range from zero to some positive last location in the memory. [Every object (data or program code) that is loaded i i.e. each variable and each fun addresses from that point onwards into memory is associated with a valid range of addresses, .ction in a program starts at a particular location, and spans across consecutive 1g on the size of the data item. @ Consider the statement int a= I 1. Reserve space in memory to hold a integer value. 2. Associate the name ‘a’ with this memory location. ); This tells the compiler to DrMaheshG MrHarish G ‘Assoc. Prof, Assoc. Prof. aMSiT aM Dea 3. Store the value 10 at this location. ‘This is as shown in the following memory map. a ——> Location Name 10 | —> Value at Location 1004 ____-» Location No. or Address @ 2.2 The Address Operator ( & ) ‘This operator when used as a prefix to a variable name gives the address of that variable. EX: Program to print the address of a variable along with its value. #include void main() { int 0; printf(“The address of ais Youln”, &a); printf(“The value of a is %d\n", a); Here You is used for printing addres 2 printing address values, because memory addresses are unsigned Module t 4 Scanned with CamScannerLL Lecture Notes Data Structures and Applications [17CS33] Consider the declaration, char a; int; ‘Assuming char requires 1 byte and int requires 4 bytes, memory space may be reserved in the following way. Fora |_| 2000 2001 Sd 2002 For‘b’ 3003 2004 @ é : &a= 2000 &b = 2001 i.e. a variables address is the first byte occupied by the variable. 2.3 The Indirection Operator (*) ‘This operator when used as a prefix to the address of a variable gives the value of that variable (contents at that address). EX: Program to print the address of a variable and then print its value using * operator. #include void main( ) { p printf(“The value of a is d\n”, *(&a)); Note: The address and indirection operators are complimentary i.e. when both are applied on a variable, the variable is got back. [ *(&a) =a] 2.4 Pointer Variables or Pointers The address operator (&) returns the address of a variable. This address can be collected or stored in another variable. EX: b= &a; Here the compiler must also reserve space for the variable ‘b’. The memory map for this is as shown. a fe 10 1004 Module 1 1004 2000 5 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] Note that ‘b’ is not a ordinary variable. It is a variable which contains the address of another variable ‘a’, Such type of variable is called a pointer v. Definition: A pointer is a variable that contains the address of another variable, 2.5 Pointer Declaration The syntax for declaring a pointer variable is datatype * Name_of the_Pointer_Variable; Here datatype ean be ¥ Primitive datatypes such as int, float char, ete V_ User defined datatypes Name_of_the_Pointer_Variable is any valid variable name. Note: The datatype of a pointer variable must be same as the type of the variable that it points to. it can hold the address of a integer Y int *P means P is a pointer to an integer variable . Y float *P means P is a pointer to a float i. it can hold the address of a floating point variable, Y char *P means P is a pointer to a character i.e. it can hold the address of a character variable. EX: Valid in *C” [Invalid in*C” int *P; int *P; inta=10; | float a= 3.4: ba; [P= has 2.6 Accessing a Variable through its Pointer We know that by using a pointer variable, we can obtain the address of another gees DrMahesh G MrHarish G EX: Assoc. Pr Ant a,b: ST 1/ Assume ‘a’ is stored at address 1000 P=&a; iP will contain address of a ie. 1000 We know that the value stored at any address can be obtained using the indirection operator (*). EX: The value stored at address 1000 can be obtained by *P [same as *(&a)]. Here P means the address 1000 and *P means the contents at address 1000 which is 10. Module 1 6 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] EX: Program to illustrate the use of indirection operator ‘*” to access the value pointed by a pointer. Hinclude void main( ) int a,b; int *P; a= 10; P= &a: b= sp; printf(“26din". a); printf(“%ed\n", b) printtt%edin", *P) i OUTPUT 10 10 10 2.7 Initialization of Pointer Variables Consider the following variable declaration, where the variable is uninitialized. int a; This declaration tells the compiler to reserve space in memory and associate name ‘a’ to that location, Because it is uninitialized, the value at this location is unknown or some garbage value. This is as shown. a ———> Location Name 2? «{—— Unknown Value The same thing applies to pointer variables also. Uninitialized pointers will have ‘unknown memory addresses or unknown values that will be interpreted as memory locations. int *P; P ———-» Location Name Pointer to an Unknown Location 2+ Uninitialized pointers cause errors which are very difficult to debug. Hence it is always good practice to assign a valid memory address or NULL value to a pointer. EX: int a; int *P = &,; int *Q=NULL; Module 1 ? Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] Note: NULL is a pointer value which when assigned to a pointer variable indicates that the Pointer does not point to any part of the memory. 2.8 Pointers and Funetions EX: Program to swap two numbers #include void main() int a, b, temp; print{(“Enter 2 numbers\n”); scant("%d%a", &a, &b); print{“BEFORE SWAPPING\n"), printi(“Value of a= %d \n",); printf(*Value of b= %d \n”.b); temp =a; a=b; b=temp; printi{“AFTER SWAPPING\n”); printf(*Value of a = %d \n",a); printf(“Value of b = %d \n”,b); } EX: Program to swap two numbers using Functions #include void swap( int *c, int *d) { int temp; temp =* 2 5 eshG Mr.Harish G Assoc. Prof. ASSOC. Prof. MST M Oe AIT void main() { int a, b, temp; printf(“Enter 2 numbers\n"); scanf{“%d%d", &a, &b); printf(“BEFORE SWAPPING\n"); printf(“Value of a = %d \n",a); printf(*"Value of b = %d \n",b); swap(&a, &b); printf(“AFTER SWAPPING\n"); print{(“"Value of a = %d \n".a); printf(“Value of b = %d \n”,b); } Note: ¥ If‘a’ and ‘b’ are passed by value, then the effect of swapping will not be seen in the main function. The variables ‘a’ and ‘b’ will retain their values. ¥ When only one value needs to be sent from the called function to the calling function, we can use the ‘return’ statement. ¥ When more than one value needs to be sent from the called function to the calling function, we have to use call by reference, Module 1 8 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 2.9 Functions returning Pointers EX: Program to find bigger of two numbers #include int* bigger(int *e, int *d) ifte > *d) retum e: else return d; i void main( ) i inta, int *big; print{(“Enter 2 numbers\n”); scani("%d%d", &a, &b); big = bigger(&a, &b); printf(“Bigger of two numbers is %d \n”, *big); } 2.10 Pointer to a Function EX: Program to add two numbers #include int add(int c, int d) { int res; res=c+d; retum res; 3 ‘void main() ‘ { int a, b, res; int (*ptr)(int, int); // declaring pointer to a function pir= add; 1 storing the address of a function in pointer to a function printf(“Enter 2 numbers\n”); seanf{“%d%d", &a, &b); res=(*ptr)(a, b);_//calling the function using pointer printf(“Result of addition is %d \n", res); Module 1 9 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 2.11 Pointer to a Pointer Just as we have pointers to int, float or char, we can also have pointers to pointers. This is because, a pointer is also a variable. Hence, we can always have another variable (pointer) which can contain the address of the pointer variable. EX: a=10; — //integer variable “D: // pointer to an integer **q;_// pointer to a pointer to an integer See Dr.MaheshG Mr.Harish G ‘ Assoc. Prof. ASSOC. Prof This is pictorially as shown below. evs Ora q P a +3000 +1 2000 +10 4000 3000 2000 ‘The above shows a 2-level indirection, however, there is no limit as to how many levels of indirection we can use. Here, Y pis the address of “a’ (2000) ¥ *pis the contents or value at address 2000 i.e. 10 Y qisthe address of p (3000) ¥ *qis the contents or value at address 3000 (2000) ¥ *#q is the contents or value at address 2000 (10) ¥ a=*p=*q Module 1 i. Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 3. Memory Allocation 3.1 Statie Memory Allocation Itis a process where in the memory space is allocated during the compilation time. Here the allocated memory space cannot be expanded or reduced to accommodate more or less data, i.e, the size of the allocated memory space is fixed and it cannot be altered during execution. EX: Consider the declaration int a[10]; During compilation, the compiler will allocate 10 memory locations for the variable ‘a’ and ‘once defined cannot be changed. During execution we cannot have more than 10 data items, and if we use 3 locations, another 7 locations are wasted. Disadvantages: In this type of memory allocation, the data structures require a fixed amount of storage. the amount of storage is fixed, * Ifthe data structure in use, uses only a small amount of memory, rest of the memory is wasted. + If the data structure in use, tries to use more memory than actually allocated for it results in an overflow. Because of these limitations, this type of memory allocation can be used in applications where the data size is fixed and known before processing, 3.2 Dynamic Memory Allocation It is the process of allocating memory space during run time. This type of memory allocation can be used in applications where the storage requirement is unpredictable. ‘The following are the functions using which additional memory space can be allocated or unwanted space can be deleted, thereby optimizing the use of storage space. 1. malloc Deseription: This function allocates and reserves a block of memory, specified in bytes and returns a pointer to the first byte of the allocated space. ‘Syntax: ptr= (datatype *) malloc (size); Where - ptris a pointer of type datatype - datatype can be any of the basic data type or user defined data type. - size is the number of bytes required. Example: ptr= (int * ) malloc ( sizeof (int) ) On successful execution of this statement, a memory space equivalent to size of int is reserved and the address of the first byte of the memory allocated is assigned to the pointer ptr of type int, Return Value ~ On success, it returns a pointer of type void to the newly allocated block of memory. On failure i.e. if the specified size of memory is not available, it returns NULL. Module 1 " Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 2. calloe Description — This function allocates multiple blocks of same size, initializes all locations to zero and returns a pointer to the first byte of allocated space. Syntax: ptr = (datatype *) calloc (n, size); Where = ptrisa pointer of type datatype ~ datatype can be any of the basic data type or user defined data type. + size is the number of bytes required. = nis the number of blocks to be allocated of size bytes. Example: ptr = (int * ) calloc (200, sizeof (int )) On sucessful execution of this statement, a memory space equivalent to size of 200 int (array of 200 integers) is reserved and the address of the first byte of the memory allocated is assigned to the pointer ptr of type int. Return Value — On success, it retums a pointer of type void to the newly allocated block of memory. On failure i. if the specified size of memory is not available, it retums NULL, 3. realloc Description ~ This function is used to alter the size of the previously allocated space which is allocated either by using malloc or calloc function. ‘Syntax: ptr = (datatype *) realloc (ptr, size); Where _ - ptris the starting address of allocated memory obtained previously by calling ‘malloc, calloc, or realloc functions. ~ size is the number of bytes required for reallocation, The size specified may be larger or smaller than the previously allocated memory. Example: If the original allocation is done by the statement Dr.MaheshG Mr.Harish G ptr = malloc(size); Assoc. Prof aM Then reallocation of space may be done by the statement pir = realloc(ptr, newsize) On successful execution of this statement, realloc allocates a new memory space of size newsize to the pointer variable ptr and returns a pointer to the first byte of the new memory block. Return Value — On success, it retums a pointer to the newly allocated block of memory. On failure i.e. ifthe specified size of memory is not available, it returns NULL. Note: = The storage space allocated dynamically has no name and therefore its contents can be accessed only through a pointer, = Itis the responsibility of a programmer to de-allocate memory whenever it not required by the application, * Incase of realloc( ), the contents of the old block will be copied into the newly allocated space and so, this function guarantees that the earlier contents are not lost. Module 1 2 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 4. free Description ~ This function de-allocates (frees) the allocated block of memory which is allocated by using the functions malloc( ), ealloe( ) o realloc( ). Syntax: free(ptr); Where pir is a pointer to a memory block which has already been created by invoking one of the 3 functions malloc( ), calloc( ) or realloc( ). Return Value - None. 3.3 Problems with Dynamic Memory Allocation, 1, Memory Leakage This is a problem where in a part of the memory is reserved but is not accessible to any of the applications. Example: Consider the following program segment. main () it int *a; a= (int *)malloc(sizeof (int) ); = (int *)malloc(sizeof (int) ); *a=20; } Here, memory for the variable ‘a’ is allocated twice. However, ‘a’ contains the address of most recently allocated memory, thereby making the earlier allocated memory inaccessible ice. the memory location where the value 10 is stored is inaccessible to any of the application and is not possible to free so that it can be reused, 2. Dangling Pointer Any pointer pointing to a destroyed object or which does not contain a valid address is called a dangling pointer. int *a ‘a=(int *)malloc(sizeoftint)); +0=20; free(a); Here, if we de-allocate the memory for the variable ‘a’ using free(a), the memory location pointing to by it is returned to the free pool. Now the pointer variable ‘a’ can be used, but the contents pointed by that cannot be used, because the pointer variable ‘a’ does not contain a valid address now and is called a dangling pointer. Module 1 13 Scanned with CamScannerLecture Notes 3.4 Comparison of Malloc and Calloc Data Structures and Applications [17CS33] ‘SI a Mallloe () alloc () Syntax: pir = (datatype*) malloc ( size ) 1] (Takes only one argument which is the size of the block) ‘Syntax pir = (datatype*) calloc (n, size ) (Takes 2 arguments, first is number of blocks to be allocated and second is the size of each block) Allocates_a block of memory of ‘Allocates multiple blocks of memory, each od si block with same 3 [Aes ROTI [Eh yt te asa Hae] ‘Since no initialization takes place, time calloc( ) is computationally more expensive not available contiguously but available at different locations. 4 | efficiency is higher than calloc( ) because of zero filling but, occasionally, more convenient than malloc( ) This function can allocate the required | This function can allocate the required 5 | Size of memory even if the memory is | number of blocks contiguously. If the required memory cannot be allocated contiguously, it retums NULL. 3.5 Comparison of Static and Dynamic Memory Allocation = Static Memory Allocation Dynamic Memory Allocation 1 | Memory is allocated during compilation | Memory is allocated during rim time, time. “The size of the allocated memory space is | The size of the allocated memory space is 2 | fixed and it cannot be altered during | not fixed and it can be altered (increased / execution, decreased) during execution. This type of memory allocation can be | This type of memory allocation can be 3 | used in applications where the data size is | used in applications. where the storage fixed and known before processing. requirement is unpredictable. Execution is faster because memory is | Execution is slower because memory Is 4 already allocated and only data has to be allocated and only then data manipulation is done. manipulation is done. Part of memory allocated is stack memory | Part of memory allocated is heap memory or global/static memory. Ex: arrays Ex Dynami arays, linked Tits Module 1 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 4. Arrays _ Arrays is a collection of items of similar data type, All elements of an array share a common name and each element in the array is identified by using the subscripvindex. 4.1 Representation The elements of an array are stored in consecutive memory locations. For example, consider the array declaration (with initialization), int a[5] = (10, 20, 30, 40, 50}; ‘When the compiler encounters this statement, it allocates 5 consecutive memory locations, each large enough to hold a single integer and assigns the values 10, 20, etc to appropriate locations. The memory map of this is as shown below. ao] [10] 1000 aft] [20] 1004 a(2] 30, 1008 af3] [40] 1012 af] [50] 1016 UB represents the upper bound and is the largest index in the array (for above UB = 4) and LB represents the lower bound and is the smallest index in the array (for above LB = 0). In general the number of elements or the length of the array can be obtained using the formula, Length = UB - LB +1 Example: 4-0+1=5 ‘One way of obtaining the address of each element of an array is by using the ‘& operator. For example, &a[0] gives the address of the first element, &a[!] gives the address of the second element and so on. However, the address of the first clement (also called as the base address) is stored in the name of the array i.e. a= &a[0]. Hence the name of the array ‘a’ can be considered as a pointer, pointing to the first element of the array. ‘A second way of obtaining the address of each element of an array is by using the name of is basically a pointer. For example, ‘a’ gives the address of the first element, Module 1 15 Scanned with CamScannereee Lecture Notes Data Structures and Applications [17CS33] ‘atl" gives the address of the second clement, ‘a+2" gives the address of the third clement and so on. Meaning ‘a’ is same as &a[0}, ‘at1" is same as &a{1] and so on. Note: Adding an integer ‘n’ to a pointer, makes the pointer to point to a value ‘n’ elements away i. ifa" is a pointer and ‘n’ is a integer, a+n =a +n * (sizeof{one element)). EX: In the above memory map ‘a’ = 1000, at3 =a+3 * sizeoftone element Here a= 1000, assuming integer takes 4 bytes, sizeof{one element) = 4 and hence, a43 = 1000 + 3 * 4= 1000 + 12 = 1012 = Address of a[3] ie &a[3] In general, the address of afi] can be obtained as &afi] or ‘ati and the value of afi] can be obtained as afi] or *(a+i). Program to print the elements of an array along with their address using pointers #include void main( ) { int n, i, a[20] ; print{(“Enter the number of elements\n” seanf(“%ed”, &n); printf(“Enter the elements\n"); for(i=0;i void main() { int n, i, 20), sum ; printf(“Enter the number of elements\n"); scanf(“%d", &n); printf(“Enter the elements\n"); for( i=0;i a0] aft] z a2] = The element afii][j] is found by first accessing the pointer in afi). This gives the address of the zeroth element of row ‘i’ of the array. Then by adding ‘j’ to this pointer the address of the j® element of row ‘i’ is found This means, Y The expression *(a + i) + j points to the j” element in the i row ie. *(a + i) +j = Salil] Y The expression *( *(a+ i) +j) gives the value of the element i ic. *(*a+i)+j)=alilbi. i row and j™ column Program to read and print an array of ‘m X n° matrix using pointers Hinclude void main( ) { int m, n, i,j, af20) (20); print{(“Enter the number of rows in the matrix\n”); scanf("%d", &m); Module 1 ” Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] printf{“Enter the number of columns in the matrix\ scanft“%d", &n): print{(“Enter the matrix elements\n”); for i=O;i n || pos <0) { printf("Invalid position \n"); retum ; } for(i =n-1; i >= pos; i) afi+1] = afi; } G Mr.HarishG afpos] = item; S506 Prof. Dear n=ntl; } 4.2.4 Delete void delete_array(int pos) { int i; Module 1 19 Scanned with CamScannerLecture Notes Data Structures and Applications (17CS33] ioas >= nibpos <0) print{("Invalid position \n"); return ; } print(("Item deleted = %d \n",alpos}): for(i = post; i int *a, arraysize, void main() { int item, pos, choice; printf(“To Create an Array\n”); printf(“Enter the maximum size of array\n”); scanf(“%d", &arraysize); print{(“Enter the number of elements to be read initially \n"); scanf(“Yed", &n); create_array( ); Module 1 20 Scanned with CamScanner} CC SSSSISSS= hh TG, Lecture Notes for(;;) { 4.2.6 Search Li jear Search Data Structures and Applications [17CS33] print{(“1.Display 2.Insert 3.Delete 4.Exit\n"); print“Enter your choice\n “%d", &choice); ase 1: display_array( ); break; case 2: printf(“Enter the item to insert\n”); scanf("%d", &item); printf(“Enter the index position to insert\n"); scanf(“%d", &pos); insert_array(item, pos); break; case 3: printf(“Enter the index position to delete\n”); scanf(“%d", &pos); delete_array(pos); break; case 4: free(a); exit(0); Write a *C” program to search for a given ‘key’ element in an array of ‘n’ elements using linear search technique #include void main( ) { int n, i, a[20], key ; printf{“Enter the number of elements\n”); seanf(“%d", &n); printf(“Enter the elements\n"); for(i=O;i void main( ) { int n, a{20), key, low, high, mid ; printf{“Enter the number of elements\n”); scanf(“%d", &n); printf(“Enter the elements\n"); fori=0;i afmid)) low= mid +1; } printf(“UNSUCCESSFUL SEARCH\n” ); Module 1 2 Scanned with CamScannerLecture Notes Structures and Applications [17CS33] 4.2.7 Sort Bubble Sort Write a *C’ program to sort ‘n’ elements of an array using bubble sort technique #include void main( ) int n, i, af20}, j, temp ; print{(“Enter the number of elements\n"); scant", 8 printf(“Enter the elements\n"); for i= O;i = afi+1]) { afi+1] = temp; } printf(“The sorted array elements are\n”); for i=O;i void main( ) int n1, n2, i, j, k, a[20], b[20], [40]; printf(“Enter the number of elements for arrayl\n"); seanft"%d", &n1); Module 1 23 Scanned with CamScannerLecture Notes Data Structures and Applications (17CS33] inter the clements in sorted orderin”); Oi int n, i, * print{(“Enter the number of elements\n”); scanf{"%ad”, &n); a= (int*) malloc(n*sizeoftint)); printf(“Enter the elements\n”); for i= 0;i void main( ) { int n, i, *a, max; printf("Enter the number of elements\n"); seanf{"%d", &n); : a= (int*) malloc(n*sizeoftint)); Module 1 25 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] printf{“Enter the elements\n"); for i=O;i max) { max = *(ati); } } printf{“Maximum element = %d\n”, max); free(a); Program to find the sum of positive and negative numbers out of ‘n’ elements using dynamic arrays #include void main( ) { Module 1 int n, i, Ya, psum, nsum; printf{“Enter the number of elements\n”); scanf(“%od", &n); a= (int*) malloc(n*sizeof{int)); printi(“Enter the elements\n”); for i= 0;i 0) { psum = psum + *(a+i); } else { nsum =nsum + *(a+i); } Yod\n", psum); printf(“Sum of positive element: %edin”, nsum printf(“Sum of negative elemen free(a); 26 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] Program to read and print an of ‘m X n’ matrix using dynamic arrays #include void main( ) int rows, columns, int * printf(“Enter the number of rows in the matrix\n”); scanf("%d", S&rows); Printf(“Enter the number of columns in the matrix\n”); scanf{“%d", &columns); / ALLOCATE MEMORY FOR ROWS a= (int **) malloc(rows * sizeoftint *)); /FOR EACH ROW ALLOCATE MEMORY FOR COLUMNS. for(i = 05 i < rows; i+) { afi] = (int *) malloc(columns * sizeoftint)); a printf(“Enter the for(i=0;i, ¥ Triples are organized so that the row indices are in ascending order, and for any given row, the column indices are also in ascending order. ¥ To perform any operation on a sparse the following needs to be known = Number of rows - Number of columns = Number of nonzero elements We use the following structure to represent a sparse matrix. struct sparsematrix . int row: int col; int value; ‘ struct sparsematrix a{ 100]; EX: The above sparse matrix can be represented as Tow | col | value af] 6 [6] 8 afl] [0 [0 | 15 ay [0 [3 | 22 apy fo 5 | 15 ala} [a [an afs} [1 [2 [3 afo) [2 [3 | 6 a7) | 4 [0 [or as) | 5 [2 | 28 Module 1 29 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] Here, ¥ a[0]. row contains the number of rows. ¥ a{0]. col contains the number of columns. a0]. value contains the total number of nonzero elements. ~The triples are ordered by rows and within rows by column 5.1.2 Transposing a Sparse Matrix Transpose of a matrix can be done by interchanging the rows and columns. This means each element afi}{j] in the original matrix will become bff] in the transposed matrix. Direct interchanging of rows and columns is not correct in case of sparse mattices because the ordering of rows and columns in the representation will be lost. Algorithm for all elements in column j place from original matrix to in the transposed matrix This indicates that we should find all the elements in columns 0 and store them in row 0 of the transpose matrix, then find all elements in column 1 and store them in row 1 etc, EX: Matrix ‘a’ and its transpose ‘b’ is as shown below row | col | value row | col | value ajo| 6 [6] 8 bo|| 6 [6] 8 afi) |-0 [0 [15 bil] |-0 [0 | 1s af] [0 [3 | 22 bE) [0 [4 [91 aB) [0 [5 [Is bp) fa a af4)] 1 [1 [i v4} | 2 [1 | 3 ee tl) bs] |_2 | 5) 28 af] | 2 | 3 | -6 v6) [3 [0 [22 a7) [4 [0 | 1 wi [3 [2 [6 Cafs) 5 [2 | 28 vfs} | 5 [0 | -1s The following is the function for finding the transpose of a sparse matrix. The array ‘a’ holds the original matrix and the array ‘b’ holds the transposed matrix. The structure used in the function is given by struct sparsematrix { int row; int col; int value; ‘ typedef struct sparsematrix MATRIX; 1/ Eunetion to find the transpose of a sparse matrix void transpose(MATRIX af ], MATRIX bf }) { int n; Module 1 30 Scanned with CamScannerLecture Notes. Data Structures and Applications [17CS33] bf0}.row = al0}.col; rows in b= cols ina bl0}.col 1/cols in b = rows ina bfO}.valu 4 number of elements in b = number of elements in a n= al0].value; //total number of elements iffn>0) M4 nonzero matrix { // position to put the next transposed triple in b i #define MAX_TERMS 100 struet polynomial { int coefficient; int exponent; ‘ Dr.MaheshG Mr-Harish G ‘Assoc. Prof. Assoc. Prof. ear struct polynomial a[ MAX_TERMS]; int avail void main( ) int na, nb, i, startA, finishA, startB, finishB, startC, finishC, ne; printf(“Enter the number of terms in Polynomial A\n”); scanf(“%d", &na); startA = avail; printf(“Enter the coefficient and exponents of the Polynomial A\n"); for(i = 0; ina; i+) { printf(“Enter the coefficient \n”); scanf(“%d”, &a{avail]. coefficient); printf(“Enter the corresponding exponent \n"); scanf{"%d", &a[avail].exponent); avail}; } finishA = avail print{(“Enter the number of terms in Polynomial B\n”); scanf{%d", &nb); startB = avail; printf(“Enter the coefficient and exponents of the Polynomial B\n"); for(i = 0; icnb; i+) { print{(“Enter the coefficient \n”); scanf("“%d", &afavail].coefficient); print{(“Enter the corresponding exponent \n”); seanfi“%d", &afavail].exponent); availt++; finishB = avail - 1; Module 1 33 Scanned with CamScannerLecture Notes Data Structures and Applic ne = padd(startA, finish, startB, finishB, &startC, &finishC); print(“Polynomial display(startA, na); printt"Polynomial B i display(startB, nb); print{("Sum of Polynomial A and Polynomial B is"); display(stanC, ne); int padd(int start, int finish, int startB, int finishB, int* startC, int* finishC) t int ne = 0; *startC = avail; while(startA<=finish && startB<=finishB) { switch( compare(afstartA ].exponent, a[startB].exponent )) case -1: // a’s exponent b’s exponent afavail].coefficient = afstartA].coefficient; Module 1 M Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] afavail].exponent = afstartA ].exponent; statA++s avail++; nett; break: } 1/ Add remaining terms of Polynomial A while(startA <= finishA) { afavail] coefficient = a[startA].coetfficient; afavail] exponent = afstartA ] exponent; e ) 1 Add remaining terms of Polynomial B while(startB <= finishB) { afavaill.coefficient = afstartB], coefficient; afavail].exponent = a[startB].exponent; startB avail; nett; } *finishC = avail ~ 1; retum ne; } © oid display(int star, int n) int compare(int x, int y) { t ir iffxsy) icon; +4) retum -1; else iffx = =y) iffa[start}.coefficient > 0) return 0; printi(+"); else printf(“%ad”,a[start} coefficient); return 1; } printh(x 4"); printf(“¥%d",a[start].exponent); start++; } } Module 1 3s Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] 6. Strings A string is any finite sequence of characters (i.e. letters, numerals, symbols and punctuation ‘marks 6.1 Representation In C strings are represented by arrays of characters. The end of the string is marked with a ‘special character, the null character (\0 ). ‘The following declaration and initialization create a string consisting of the word “bmsit”. To hold the null character at the end of the array, the size of the character array containing the string is one more than the number of characters in the word "bmsit” char str{6] = ('b''m.'s, 7", 109}; Ifyou follow the rule of array initialization then you can write the above statement as char str{ ]="bmsit"; The following is the memory representation of the above string Index 0 1 2 3 4 5 String b M s i 1 10 Address 1000 1001_—=«*1002-~—=S=«003.~=«i004~—~=«*'00S The NULL character at the end of the string is automatically placed by the compiler when it initializes the array. 62 Storing Strings Strings are stored in three types of structures 1) Fixed Length Structures - Here each line of print is viewed as a record, where all records have the same length. Example: Consider a the following FORTRAN program, C PROGRAM PRINTING TWO INTEGERS IN INCREASING ORDER READ *.5.K IEQ.LEK) THEN PRINT *, J. K ELSE PRINT. KJ ENDIF sToP END ‘Assuming 200 is the address of the first character of the program, the following is the fixed length structure. Module 1 36 Scanned with CamScannerData Structures and Applications [17CS33] cS = t 200 1 280 Oo Te PLLe iT [HTE[N] t 1 1 360 370 380 ie] LIPRD TTT LIK t 1 t 440 450 460 Pp I e[N oy + t t 840 850 860 Fig. 3.2 Records Stored Sequentially in the Computer PRD INGL ol__—- 1 2 A -L CELL T 3 4 : TER LIELIKDT TAIN aE 9 T ey. KL = eno) T CL Fig. 3.3 Records Stored Using Pointers Advantages © The ease of accessing data from any given record The ease of updating data in any given record (as long as the length of the new data does not exceed the record length) Module 1 7 Scanned with CamScannerLecture Notes Data Structures and Applications [17CS33] Disadvantages © Time is wasted reading an entire record if most of the storage con blank spaces. Certain records may require more spaces than available When the correction consists of more or fewer characters than the original text, changing a misspelled word requires the entire record to be changed. sts of inessential 2) Variable Length Structures with fixed maximums In this method, the strings are stored using one the following ways 4) Using a end marker such as two dollar signs (SS), to signal the end of the string. PROGRAM PRINTING TWO INTEGERS IN INCREASING ORDERSS Read *, J, KSS. W.LE.K) THENSS PRINT, 3, KSS ENDSS (a) Records with sentinels. ‘C_ PROGRAM PRINTING TWO INTEGERS IN INCREASING ORDER READ JK IF(J.LE.K) THEN PRINT *.J.K END Dr.MaheshG Mr.Harish G Assoc. Prof. Assoc. Prof. eM ant Dear (b) Record whose lengtns listed, Advantage : ; * We need not have to read the entire record when the string occupies only the beginning part of the memory location. Disadvantage : ' © This method of storage is usually inefficient when the strings and their lengths are frequently being changed. Module 1 38. Scanned with CamScanner