TABLE OF CONTENTS Chapter - 1 Introduction to C Programming (1 - 1) to (1 - 41) 1.1 C Fundamentals : Constants, Variables and Keywords inC...1-1 1,2 Operators... 1.3 ‘Bitwise Operations . 1.4. Decision Control and Looping Statements... 1.5 Arrays and String Manipulation... 1.6 Functions... 1,7 Recursive Functions... 1.8 Pointers... 1.9 Structures and Union.. 1.10 Enumeration... 1.11 MACROS... 1.12 File Handling File Operations. U I Chapter - 2 Searching and Sorting Algorithms (2 - 1) to (2 - 37) 2.1. Algorithms... 2.2. Asymptotic Notation .. (v) P..2.3 Time Complexity... 2.4 Space Complexity ... 2.5 Analysis of Iterative and Recursive Algorithms ......s.5s6. 2.6 Need for Searching and Sorting... 2.7. Searching Methods. | 2.8 Sorting Method: | Chapter-3 Stack and Queue (3- 1) to (3-23 3.1. Concept .. 3.2 Stack as ADT .. 3.3 ‘Basic Stack Operations... 3.4. Array Representation of Stacks 3.5 Stack Applications... 3.6 Expression Conversion .... 3.7 Evaluation of Expression .... 3.8 Queues : Concept..... 3.9 Queue as ADT. 3.10 Array Representation of Queues... ace aon 3.11 Priority Queue... 3.12 Applications of Queue... (vi)Lops} ———— Chapter - 4 Linked List (4 - 1) to (4 - 32) 4.1 Concept of Linked Organization ..... 4.2. Linked list as ADT... 4.3 Singly Linked List. 4.4 Operations on Linked List... 4.5. Stack using Linked List... 4.6 Queue using Linked List... 4.7. Types of Linked List 4.8 Doubly Linked List.. 4.9 Circular Linked List.... 4.10 Representation and Manipulations of Polynomials using Linked Lis 4.11 Comparison of Sequential and Linked Organization... ———— Chapter - 5 Trees (5 - 1) to (5 - 30) 5.1 Introduction to Trees 5.2, Basic Tree Concept: 5.3 Binary Tree..... 5.4 Representation of Binary Tree in Memory... 5.5 Traversing a Binary Tree. 5.6 Binary Search Tree (BST)... (vil)Data Structures 1-2 Introduction to C Pro, Q.2 Determine the output of the following "C" statements : Assume a = 13, b = 25 and c = 5. 4 i) z = ab, il)x = +ta-b, iii) y = b++ +, iv) x =c > b?1::0. CS [SPPU : Dec.-05, Mi Ans. : i) z = 20 as it is logical bit wise EX-OR operation The truth table for EX-OR operation is as shown below 0 Oo 0 Lo [1 1 1 1 0 1 1 0 ii) - 11 since x stHa-b=14-25=-11 ] ‘As ++a is a pre increment operator the value of a is incremented by before the expression gets evaluated. iii) 30 since y = b+t+e = 25 +5 As b++ is a post increment operator, after expression gets incremented ae value of b becomes 26. — iv) 0 : | The meaning of this expression is if c > b is true then print 1 otherwise) 0. As value of c is less than b the output will be 0. Q.3 Explain comma and sizeof operators used in 'C’. Give a suitable example to illustrate use of each operator. TG [SPPU : Dec.-06, Marks 6) : The comma operator is used to separate variables statements in a contvol statement, to separate multiple conditions in a conditional statement. Ans, : Comma operator For example, i) inta,b,¢; ii) for @= 0, j = 0; i < 10; i++) | iii) for (= 0, j = 0; 1 < 10 && j< 10; i++, j44) A Guide for Engineering Studentsita Structures 1-3 Introduction to C Programming "ylzeof operator : The sizeof operator retums the number of bytes the perand occupies. The operand may be a variable, a constant or. a data ‘pe. izeof operator is used for finding length of structures and arrays. It is ery useful in finding the storage requirement for dynamic allocation of aemory. pamples 5 nt x, y, z; int m; x = sizeof (m); y = sizeof (float); ng = sizeof (‘A’); | 1 ‘itwise Operations | 442-4 Write various bitwise operators used in C. Explain with SJuitable example the bitwise OR operator UF [SPPU : Hay 13, Merk ‘Ans. : The bitwise operators are as follows : | Example void main() { int a,b,ans; clrsor(); Printf(‘\n Enter a Number"); Scanf("%d" &a); b=1; | ° A Guide for Engineering StudentsData Structures 1-4 Introduction to C) ans=a&b; printf(“\n Result of AND operation with 1"); if (ans==0) printf("\n The Rightmost bit is OFF"); else ; printf("\n The Rightmost Bit is ON"); | 2.6 ans=a/b; } printf("\n Result Of OR operation with 1"); print{(“\n The Rightmost bit is Tuned ON and the result is%d", | ans); | getch(); } . | Q5 Using bitwise operators write a program to print wheth given number is odd or even. Ee [SPPU : May-11, Marks §) Ans. : C program to check whether the given number is even or ¢ using the bitwise operator. | : \ #include | #include | void main() ” { int ab,ans; clrscr(); printf("\n Enter the number’); | scanf("%hd' fa); | b=1; | Anding the number with 1 and on checking i ans=agkb; the result we get right most bit. If itis 0 then)| get rig! iffans==0) ‘number is even. print{(’\n The number is even"); else print{(\n The number is odd"); t A Guide for Engineering Students es a\ ta Structures 1-5 Introduction to C Programming Output Enter the number11 The number is odd 1.4 : Decision Control and Looping Statements Ae Write output of the following C code 0&[SPPU : May-12, Marks 6] ) # include main () int x=3; float if (x==y) printf ("\nx and y are equal’); else printf ("\nx and y are not equal’); } # include void main() { int i=0; for (;i;) printf ("\n Here is some mail for you"); } . iii) # include main() { int x=4; . while (x==1) ~ { x= x-1; printf ("\n%d", x); -% A Guide for Engineering StudentsData Structures 1-6 Ans. : i) x and y are equal ii) The printf statement will not be executed. Hence there will message on the console. iii) The printf statement will not be executed.As x=4 and the while loop gets false. The control will not enter in the | Hence there will not be any message on the console. sg 4 Q.7 Explain use of "break" and "continue" keywords in 'C \= suitable example. CSP [SPPU : May-10, Marg Ans. : The break statement is used to terminate the execution of the. It can be used to break the looping of for, while, do-while and Switch, For example : While(i<10) ; ‘ Pprintf("6d", i) if(i==5) — when i reaches to the value 5 the while loop will terminated. break; i++; } The continue statement is used to continue the execution of the cont loop. For example : E for(i=0; i<3; i++) ‘ j for(j=0; j<3; j++) i { . , if(alil==bij]) — continue statement skips this value continue; else print{('%d%q", ali],bIj]); A Guide for Engineering StudentsX I y Structures 1-7 Introduction to C Programming above code if ai] = b[j] simply go back and increment j. Hence if Sony bfj] then both afi] and b{j] will be displayed. I “Oy What Is the difference between for loop and while loop ? Also, | difference between while and do-while loop. vg {Difference between for loop and While loop for while Initialization, termination and Only initialization and iteration are the three conditions termination conditions are that are written with in a loop at written at the top of the loop. the top of the loop for(initialization; condition; while ( condition) iteration) { £ | [hoody of for loop statements; /fbody of lop a = ‘The for loop is used only when The while loop is used only we already know the number of _ when we do not know exact iterations. number of iterations. In 'for' loop the initialization ‘Ih while loop if initialization is ~ once done is never repeated. done during condition checking, then initialization is done each time the loop iterate. Ifference between while and do-while loop whi do-while In while loop the condition is In. do-while loop, loop gets checked at the start of the loop. If the condition is false initially then the loop will not get executed at all, = ws Beconss A Guide for Engineering StudentsData Structures Important Points to Remember Arrays can be defined as a set of pair-index and the value, a0} aft) a2] a3] al4] af] [6] af7] af8) a9) 30 | 40. Fig. 1.1 Array as index and value pair Syntax The syntax of declaring an array is Pp p) data_type name_of_array [size] ; ‘sr For example, int a [10]; double b[10] [10]; {fe Here ‘a’ is the name of the array inside the square bracket size of & array is given. This array is of integer type i.e. all the elements are¢ integer type in array ‘a : Q9 Write a program to print diagonal elements of a square mati ' E@[SPPU : May-10, Marks 4) Ans. : * | #include #include #define MAX 3 main() { int i,,m,n,mat[MAX](MAX],sum; clrscr(); printf(""\n Enter The Order Of matrix"); scanf("shd%d” fm, &n), printf(“\n Enter The Elements Of Matrix”); for(i=0;i void main() if : int al]={10,20,30,40,50}; int in,si sum=sum+ ali]; printf(""%d",sum); } A Guide for Engineering Studentsli Data Structures 1-10 Introduction to C Programmis 14 Q. penatlon in toe aes oe ree column major storage Ans.: Row Major Representation : If the elements are stored i rowwise manner then it is called row major representation. For example : If we want to store elements 10 20 30 40 50 60S then in a two dimensional array 0 The => elements + will be stored horizontally | 9 To access any element in two dimensional array we must specify both its row number and column number. That is why we need two variables which act as row index and column index. Column Major Representation If elements are stored in column wise manner then it is called column major representation. For example : If we want to store elements 10 20 30 40 50 60 then the elements will be filled up by columnwise manner as follows (consider array a[3] [2]). 0 1 , ee ae 1 [ape Foe | > Eee aa - A Gulde for Engineering SudentsData Structures 1-11 Introduction to C Programming Q.12 What will be the output of the following code ? Justify your answer. SGP [SPPU : May-17, Marks 6] for(i = 0;1< 4; i++) { for j= 0;)< 4; j++) { alillj] = 20 * (i + j); printf("%d", alil{i]); print{("|n"); } Printf(%d%d, i, j); Ans. : The output will be 0 20 40 60 20 40 60 80 40 60 80 100 60 80 100 120 The array a{i][j] values will be displayed (printf inside nested for loops) 4 4 < values of i and j respectively. (printf at the end). Justification : In the given code, inside the nested for loop (i + j) is multiplied by 20. and the result of multiplication is stored at afi]{j]. When i becomes = 4 and j = 4, then the values of i and j are displayed using printf statement. Q.13° What is string ? Also explain how it is used in C. Ans. : ¢ Definition : String is a sequence of characters. The strings are defined within a double quote. ¢ Example : "I love India". © The string is stored in the memory with the terminating character ‘\0' with ASCII code. * C representation : In C, the string is represented as array of characters. For example the string str can be represented as char str[10]; A Guide for Engineering Studentstli Data Structures 1-12 Introduction to C Pros ra Q.14 What is string ? How do you declare a string variable in Write and explain the function strlen, strepy. Ta [SPPU : May-13, Marks Ans. : String and its declaration : Refer Q13. strlen function : The strlen function is for computing the length of string. For example char str[]="Hello"; int len=strlen(str);-//It will retum 5 as length of string. "Hello" strepy function : The stropy function is for copy one string to another, char strl(]="Hello"; j char str2[10]; strepy(str2,str1);//copies string "Hello" to str2 Q.15 Write C function to display length of string. i * US [SPPU : May-17, Marks 3 Ans. : int str_length(char s[]) ‘ j { i=0;s[i]!="\0';i+ +); semicolon retum i; } Q46 Write a C function to copy one string to another ‘Ur [SPPU : May-17, Marks 3] Ans. : ris str_copy(cher s1[],char s2{)) int ij; i=0; J=0; is while(s1(i]!="\0') 4 Copying the contents of e2i)|=s1(i); si{]tos2[] S++; A Guide for Engineering StudettN Data Structures 1-13 Introduction to C Programming © itt; } s2{j]="\0'; oy printf("\n The copied string is %s",s2); } ; Q.17 Write a C program to find whether the given string is palindrome or not without using library functions. Ans. : #include #include #include void main() { char str1(10); intij; elrscr(); printf("\n Enter the string: "); gets(str1); for(i=0;str1 i stri*/ for(j=i-1,i=0,j>=0;j- '\0';i++);/*finding the length of string sit+) {/*comparing last character with first character of str1*/ if(str1[i}!=str1[j)) { ; printf(“\n The String is not Palindrome"); return; } } printf(""\n The string is palindrome"); getch(); } Output (Run 1) a ‘A Guide for Engineering Studentsea Data Structures 1-14 Introduction to C Program Enter the string: madam { The string is palindrome ‘Output (Run 2) Enter the string: abed The String is not Palindrome Important Points to Remember © Definition : Function is a group of statements that perform certaiq\ ‘task. «A function can be handled in C in following manner 1. Function Declaration 2, Call to the function 3. Function Definition Syntax for Function Declaration Return_type function name(parameter-list with datatypes); Syntax for Call to the function : fumction_name(parameter-list without datatypes); Syntax for Function Definition Return_type function-name(parameter-list with datatypes) { J ffxaction body Saas ha nS ae aS } function to find factorial of number. UE (SPU : Dec.-10, Marks 6] — ‘Ans.: For a large code segment is grouped to form a function.» Sometimes such a code segment is repeatedly required in the program, ) joence writing the same set of instructions repeatedly increases the 7 overhead on execution of program, If such a code segment is bound in 4 y function then the programs will not be lengthy and it will get executed in 1 faster manner. Factorial of a number ‘it fact{int n) 4 A Guide for Engineering Students | |Pata Structures 1-15 Introduction to C Programming int prod=1; x= while(x>0) prod*x; return prod; .19 Explain parameter passing by value and by reference with uitable example Ee [SPPU : Dec.-18,19, Marks 6] i 1, Call by Value : The call by value is a parameter passing ethod in which actual value is passed as a fumction parameter. For it a,b; id sum(int a,int b);/*declaration*/ rintf("\n Enter The two numbers"); scanf("%d",&a,&b); |Jsum(a,b);/*call*/ id sum(int x,int y)/*definition using passing parameter by value */ 4 int ¢; c=xty; printf("\n The Addition is %q',c); ) @. Call by Reference : In call by reference the parameters are taken by ‘Peference. Pointer variables are passed as, parameters. (For example main’) (eeens A Guide for Engineering Students~~. Data Structures 1-16 Introduction to C Program { int a,b; void sum(int *,int *); printf("\n Enter The Two Numbers"); scanf("%d%d" &a,&b); sum(&a,&b); } void sum(int *x,int *y) t z int ¢; c=*xt*: printf("“%d' De @.20 Explain parameter passing by value and by reference with example of swapping of two values. IP [SPPU : Dec.-16, Marks 6) Ans. : Parameter passing by value : This is a method in which the values are passed as parameters to the function. 7 In this method, the changes made in the function are not reflected after returning from the function to main. 10); Following example illustrates this method of parameter passing. #include void main() { int a, b; void swap(int a, int b); printf("\nEnter First number : "); scanf(“%d", &a); printf(“\aEnter Second number : "); scanf("%d", &b); print{("\nBefore Swaping x = %d-and y = %a", x, y); swap(a, b); // Function Call - Pass By Reference print{("\nAfter Swaping a = %d and b = %d", a, b); A Gulde for Engineering StudentsWy Data Structures 1-17 Introduction to C Programming } void swap(int x, int y) { int temp; temp x x= y; y = temp; } Parameter passing by reference : Parameter passing by reference is a parameter passing method in which the address of the parameter is passed. The address of a variable is passed as a parameter by using pointer variable. In this method, the changes made in ‘the function remain as it is even after returning from the function to main. Following example illustrates this method of parameter passing. #include void main() { int a, b; void swap(int *a, int *b); printf(""\nEnter First number scanf("%d", &a); Pprintf("\nEnter Second number scanf("%d", &b); Printf("\nBefore Swaping x = %d and y = %d", x, y); swap(&a, &b); // Function Call - Pass By Reference printf("\nAfter Swaping a = %d and b = %d", a, b); } void swap(int *x, int *y) A Guide for Engineering Students“<=, Data Structures 1-18 Introduction to C Progray { Q.21 What do you mean by recursive function ? Explain suitable example. OS [SPPU : Dec.-17, Marks Ans. : Recursive function : The function that calls itself repeatedly , retums to main eventually is called recursive function. | Example : Finding factorial of given number | int fact (int n) { if(a>=1) retum n * fact (n- 1); else retum 1; | | | | | i Important Points to Remember ¢ Definition : Pointer is a variable that represents the memory location| of some other variable, The purpose of pointer is to hold the memory location and not the actual value. © In C declaration if the variable is preceded by asterisk or * then it is called pointer variable, © For example int *ptr; * 10 pointers two important operators * and & are used. The * means Contents at the specified address’ and & means the ‘address at'. A Guide for Engineering Students |\ Data Structures 1-19 Introduction to C Programming Q.22 Write a C function to interchange two numbers using pointers. GP [SPPU : May-06, Marks 4] Ans. : void inter(int*x,int*y) { int temp; temp="x; “Yi emp; Q.23 Write output of the following program with explanation : ‘US [SPPU : Dec.-12, Marks 4] void main() { int a=1; int *p; ~ p=&a; printf("%d\n", a); printf"%u\n", &a); printf("%d\n", *p); printf("%u\n", p); Ans. : 1 address of a 1 address of p Output The & represents ‘address of' value and *represents actual value stored in variable. A Guide for Engineering Students— Data Structures 1-20 Introduction to C Progray Q.23 What is pointer ? What are the advantages using pointe Explain pointer declaration and its initialization with an examply, Tar [SPPU : Dec.-17, Mark, Ans. : Pointer : Refer important points to remember of section 1.8,' Advantages : Following are some advantages of using pointer « illustrates its significance, 1. Pointers allow the dynamic memory management. 2. It helps to return more than one values from the function. 3. It allows to pass arrays, strings and structures efficiently. 4. It provides direct access to the memory. 5, It improves the execution speed of the program. Declaration and initialization : Consider the variable declaration int “ptr; ptr is the name of our variable. The * informs the compiler that we 4 pointer variable, the int says that we are using a pointer variable whi will actually store the address of an integer. Such a pointer is said to & integer pointer. Thus ptr is now ready to store an address of a : the value which is of We can store the address A of some variable whose integer type. value can be referred. Consider, various ways ef poimier deslaatin Fig. Q.24.1 Pointer variable and initialization Line 1-> int *ptr; E | Line 2-> int a,b; Line3-> @=10; /*storing some value in a*/ M Line4-> _ptr=&ai/*storing address of a in ptr*/ Line5-> b=*ptr/*getting value from addrese in tr and storing it in b*/ A Guide for Engineering Studentswy > Data Structures 1-21 Introduction to C Programming Pk, @.25 Write a C program to illustrate how does the function return ‘kiya pointer ? Ans. : ‘int* sum(int*, int*); int main() { int a,b; int *¢; printf("\n Enter the value of a and b"); scanf("%d%d' &a,&b); c=sum(&a, &b); Printf('Sum of %d and %d is %d",a,b,*c); return 0; int* sum(int *x, int *y) int *z; *2=*xt*y; retum Z; ; @.26 Write a function in 'C’ using pointers, to add two matrices and return the resultant matrix to calling function. TS [SPU : Dec.-08, Marks 6) Ans. : void addition (int a[10}[10], int *m1, int*n1, int b[10] [10], int ¢[10][10}) { { alee ih D; Q.27 Write a user defined function in 'C’ using pointers for checking whether given string is’ palindrome or not. S&F [SPPU : May-09, Marks 6) Ans. : #include #include #include void main() A Guide for Engineering StudentsData Structures 1-22 Introduction to C Pregraning { char str{20); void palindrome(char str[20}); elrser(); printf("Enter a string: \n"); scanf("%s", str); palindrome(str); } void palindrome(char str[20]) { int flag = 0; char “ptr; int i, length; length = strlen(str); if(*(ptrti)I= *(ptr+tlength-i-1)) { flag = 1; break; } } if(flag==1) ie printf(“%s is not a palindrome\n’, str); } else { printf("%s is e palindrome\n', str); + } A Guide for Engineering StudentsData Structures 1-23 Introduction to C Programming Q.28 Write a C function with and without pointers to arrays for checking whether the given string is a palindrome or not. TGP [SPPU : Dec.-16,18,19, Marks 6] Ans. : Refer Q.17 and Q.27. Q.29 Explain the function pointer concept with necessary C code. Ans. : #include void my_function(int val) { printf("%d",val); } void main() { void (*test_function)(int); test_function=&my_function; /* Method! to call a Function my_function*/ test_function(10); /*"Method2 to call a function*/ (*test_function)(20); } Q.30 Explain how a pointer can point to another pointer Ans. : Following program illustrates the concept of pointer to pointer. void main() { int a; int *ptrl,**ptr2; a=10; ” ptrl=&a; ptr2=&ptr1; print{("\n a= %d",a); print{("\n *ptr1 = %d',*ptr1);/*value at address in ptr1*/ print{(’\n ptr1 = %u',ptr1);/*storing address of a*/ Printf("\n *ptr2= %u',*ptr2);/*storing address of ptr1*/ printf("\n ptr2 = %u'\ptr2);/*address of ptr2*/ } A Guide for Engineering Students w+ + seweneeeData Structures 1-24 Introduction to C Program, Q.31 Differentiate between static and dynamic memory allocatio, Ans. : ‘Sr. no. Static memory Dynamic memory 1. The memory alllocatioa is done Memory allocation is done a 2 compile time. dynamic time. Q32 Explain the use of malloc and free in dynamic memoy management Ams. : (1) The malloe function is used to allocate the memory of desired size. By default the malloc retums the void pointer. The symax for malloc is voad “melioc(size) For example eet i= (ee ekoezeottint) (2) The allccaed block function. ‘The syntax of Sze is vod S270 *pointer) of memory can be deleted using the free —= ee A Guide for Engineering StudentsData Structures 1-25 Introduction to C Programming For example int *i; i=(int* )malloc(sizeof{int)); free(i); 1,9 : Structures and Union Important Points to Remember Definition : Union is a user defined data structure which is just similar to structure. It is used to store members of differeat data types. struct student { char name[20]; int roll_no; union { int primary; char pre_pri [10]; }std; yi Q.33 What are structures ? Explain its use. Define structure having name, age and salary E@ [SPU : Dec-10, Marks 6] Ans. : Definition : A structure is a group of items in which each item is defined by some identifier. These items are called members of the structure. Thus structure is a collection of various data items which can be of different data types. ahs struct employee { NY Aces) char name[20]; Vnbmatt (9 d -e int age; : (yy double salary; je ie oe ; ik e2.age = 122"; struct employee 61,62; i a “yr a salary 1300 ee 3 A Guide for Engineering StudentsData Structures 1-26 Introduction to C Prosran, Q.34 Discuss in brief the difference between array and structurg, Ans. : Structure Array is a collection of similar type of elements. Array elements can be accessed by the index placed within [ J. To represent an array, array name is followed by {1 Example: int a [20]; Q.35 Write a C program to represent a complex number using: structure and add two complex numbers. 03°[SPPU : May-06, Marks 4]_ Ans. : #include #include typedef struct Complex { float real; float img; 3G; void main() { { A Guide for Engineering StudentsData Structures 1-27 Introduction to C Programming Cxy,2z; clrscr(); Printf("\n Enter the real part of first complex number’); scanf("%f",&x.real); printf("\n Enter the imaginary part of first complex number’); scanf("%f',&x.img); printf("\n Enter the real part of second complex number’); Scant("%f",&y.real); print{("\n Enter the imaginary part of second complex number’); scanf("%f',&y.img); printf("\n\t The First complex number is %3.2f+ %3.2fx.real,x.img); printf("\n\t The second complex number is %3.2f +-%.2f" y.real,y.img); z1eal=x.real+ y.real; z.img=x.img+ y.img; printi("\n The Addition is %3.2f + %3.2fi\n",z.real,z.img); getch(); : Q.36 Database of 100 students is required to be stored. Each student record contains fields such as roll no, name of student, total marks. Write a program in 'C’ to input the database of 100 students with fields mentioned above using : i) Array ii) Array of structures. Display record of student who scores maximum marks. TS (SPPU : May-08, Marks 8] Ans. : #include #include * #include struct student { int roll_no; char sname|[20); int Total_Marks; }s[100]; int r[100],m[100}; char n[100}{20); void main() A Guide for Engineering Students- Data Structures 1-28 Introduction to C Programs { int ij,choice; clrser(); printf("\n 1. Array \n 2.Array of structure "); printf("\n Enter your choice: "); scanf("%d",&choice); switch(choice) { case 1:for(i=0ji<100;i++) { printf("\n Enter Roll No. scanf("%d" &rli]); printf(’\n Enter name of student: "); scanf("%s",n[il); printf("\n Enter Marks: "); scanf("%d" &mli)); } j for(i=0;i<100;i++) { ‘f(m{i]>mfj))/*data with maximum mark is obtained*/ mark that record by index j*/ : j= t printf("\n Student with maximum marks is. printf("\n Roll.No.\t Name \t Total Marks "); printi("\n %d %s %a' fj] nbj].mbj)); break; case 2:for(i=0; i<100;i++) { print{("\nEnter Roll No: "); scanf("%d" &s{i]x0ll_no); printf("\nEnter name of student: scanf(%s",s[i].sname); printf("\nEnter marks: A Guide for Engineering StudentsData Structures 1-29 Introduction to C Programming scanf("%d'",&s[i].Total_Marks); } j=0; for(i=0;1<100;i+ +) + if(s[i].Total_Marks>s{j].Total_Marks) printf("\n Student with maximum marks is. printf("\n Roll.No.\t Name \t Total Marks "); printi("\n %d %s %d',sfjJ.roll_no,s{j].sname,s{j]. Total Marks); break; } } Q.37 Explain with suitable examples, how do you pass structure variable to a function. GS [SPPU : Dec.-17, Marks 6] Ans. : The entire function can be passed to the structure. Following program illustrates how to pass a structure to the function #include #include struct student { int roll; char name|[20]; ki void fun(struct student record); int main() { struct student record; tecord.roll=10; stropy(record.name, "XYZ"); fun(record);//Function call: passing structure A Guide for Engineering Students. Data Structures 1-30 Introduction to C Program return 0; ) void func(struct student record)//Function Definition : { Printf(" Id is: %d \n', record.roll); printf(’ Name is: %s \n’, record.name); } Q.38 Define union having array of characters of size 2, one intege and one float as its elements. OP [SPPU : Dec.-12, Marks:§) Ans. : union { char a[2]; int § float j; h Q.39 Write difference between union and structure with example. ES [SPU : Dec.-05, Marks 4, May.-10,19, Marks 6] stored at same memory location. Hence only one member can be zccessed at a time by union variable. Secor A Guide for Engineering StudentData Structures 1-31 Introduction to C Programming For example - For example - struct student union student { { int roll_no; int roll_no; char name[10]; char namef10}; }st; jet; 1.10 ; Enumeration Q.40 What is enumerated data type ? Give suitable example. Ans. : The enum is an abbreviation used for enumerated data type. When this keyword is used we can basically initialize the sequence of integer constants. The syntax is enum identifier_name{sequence of items}; For example : enum fruit {Mango, Orange, Banana, Grapes, Guava}; Here fruit is the name given to the set of constants. If there is no value given to the sequence then by default the first value in the list is 0. The main advantage of enum is that even if we do not initialize the constants, each one would have a unique value. The first would be zero and the rest would be one more than the previous one. 11 : MACROS Q.41 What is macro ? Explain with example. Distinguish between macro and function Ans. : Macro is an abbrevation for sequence of instructions. When this abbrevation is encountered in a program then defined sequence of instructions are submitted over there. This process is called macro substitution. . COD A Guide for Engineering StudentsData Structures 1-32 Introduction to C Programniy For example : # define TRUE 1 # define FALSE 0 The macro TRUE and FALSE is declared at the beginning of 4 program. Hence whenever we read TRUE it is replaced by value 1 ay FALSE is replaced by value 0. Difference between Macro and Function Function ‘The code gets executed eHiciently There is overhead on compiler to when macro is used. execute function. Hence execution is comparatively slower. The macro itself can not be passed as ’ The function itself can be passed asa ‘parameters to another Macro. parameter to another function. ; ‘When there is a small piece of code For large code segment the function required repeatedly then macro is can be used. | used. | ‘The macro can not have retum value, The function can have return value. Q.42 What are advantages and disadvantages of macros ? Ans. : Advantages : 1.The code gets executed efficiently. 2. When a small piece of code required repeatedly then macro is used. Disadvantages :1. The macro itself cannot be passed as parameters to another macro. 2. The macro cannot have retum value. Hence the output of one macro execution cannot be passed to another macro. 1,12 : File Handling File Operations Q43 What is file ? Give the difference between text file and binary tree ‘Ans. : Definition : A file is a collection of records. In generalized form, a file’ of size n has n items or n records in sequence where a record is collection of one or more fields. = — A Guide for Engineering StudentsData Structures 1-33 Introduction to C Programming Assume that we have a file "Student.dat" having contents as follows : Text file Binary file Text files contain plain text data. The binary file contain the data in binary form. 2. The text file does not contain the ‘The binary file can store the data graphical data. such as text, graphics, image and sound. “3, Text files can be directly read and “The binary files can not be read’ interpreted. directly. With the help of some ‘ “ ~ tool the binary file can be read. - For example HexDump is used ‘to read the binary files. 4. The text files are not executable The binary files can be files. Se ‘executable files. Q.44 Explain the file open and close operations in detail. Ans. : Opening a file : Syntax : filepointer = fopen("filename","mode"); where A Guide for Engineering StudentsData Structures 1-38 Introduction to C Progra mode can be - read Saath br append = al Depending on the type of file we want to open/create we use -"rb", 4 or just "YP, "Ww", "2" 4 Using "r” opens the file in read mode. If the file does not exist, it create a new file, but such a file’ created is of no use as you cannot wri to any file in read mode. ‘Using "r+" sllows to read from file as well as write to the file. Using "6" opens 2 file in write mode. If the file does not exist, it will orate a pew file Use "we" allows you to write contents to file, read them as well as mandy existing contents. 4 ‘Use "PS" qpess the file in append mode. If the file does not exist, then if ~ qxeams a mew Sie. Opening a file in append mode allows you to append sSoe comments at the end of the file. Usage "=" abows to append a file, read existing records, cannot modify emseng Decerds. Some: > = open(Srudent dat’,‘w?); Stsing 2 Fie ~ & Gite mast be closed after using it for the desired purpase. , = daiter closing @ He all the links that are associated with the file ae SSraten I ails reverts the misuse of the file, = Wwe close tthe file after Ws use We can reqpen in different made. ~ Somme. -Slaw/Tiepoie) AOR er Dreedmmering SaoData Structures 1-35 Introduction to C Programming Example : fclose(fp)/*closes the file pointed by fp*/ Q.45 Give the syntax and example for reading and writing the integer to a file. Ans. : Writing Integer to file : Syntax: fputv/(integer, filepointer); Example : ‘Suppose if we want to write a number to the file then we write as - int num=10; fputw(num,fp); The above operation writes the number 10 to the file pointed by fp. Reading integer from file: Syntax: fgetw(filepointer); Example : num=fgetw(fp); /* Will read the number in variable num from file ; pointed by fp*/ Q.46 Write a program to copy the contents of one file to another. Ans. : Step 1: The C code for copying the contents of one file to another is as follows - C Program #include #include #include #include int main() { char ch; int in; FILE *fp,*fp1; fp=fopen("in.dat’,"r’);/*already created file opened for teading*/ A Guide for Engineering StudentsData Structures fp1=fopen(‘out.dat"w');/‘new file in which contents can be written*/ ch=getc(fp); while(lfeof(fp)) { pute(ch,fp1);/*writing the contents to the new file*/ ch=gete(fp);/*reading the contents from input file*/ } felose(fp); fclose(fp1); printf("\n The file is copies fp1=fopen(‘out.dat’,‘r’); printf("\n\n The copied file is...\n"); while((ch=getc(fp1))I=EOF) printf("%c',ch); felose(fp1); getch(); retum 0; } Step 2: Create a text file in.dat and store the contents in it as follows - in.dat a b c ‘Step 3: Introduction to C Pro; Execute the C Code created in Step 1. The output will be as follows - The file is copied... The copied file is... A Guide for Engineering StudentsData Structures 1-37 Introduction to C Programming Q.47 Write a program to create Student database file and perform insert, delete and update operations on it. | Ans, : [EOE CARO REE UE EOE TURRET UE TU TUITE ITIL NEARER ERE Implementation of various file operations such as create, display, search and modification on student database with USN,Name and marks of three subjects sennnananeeunaaannnnnnannnnunananenanenunnantneennnannnnnsennes/ #include #include #include #include struct record. { int USN; char name[20}; int marks1,marks2,marks3; , k struct record r; FILE “fp; void main() { int n,choice; char ch; void Create_file(int); void Display_file(int); void Modify file(); struct record *Search_file(); clrscr(); printf("\n How many Records are there in the file?"); scanf("%ed' &n); do { clrscr(); printf("\n\t Main Menu'); \ A Guide for Engineering StudentsData Structures 1-38 Introduction to C Progray, printf("\n!. Create a file"); Dati printf("\n2. Display a file"); i printf("\n3. Search a file"); printf("\n4. Modify a file"); - printf("\n5. Exit"); printf("\n Enter Your Choice "); scanf("%d", &choice); switch(choice) { case 1 : Create_file(n); break; case 2 : Display_file(n); break; case 3: r=*Search_file(); printf("\n USN Name = marksi marks2 marks3\n"); Printf(\t-mee——aae eee \n"); flushall(); printf("%d_ es hd = %d \n'USN, r. name, r. marks1, r. marks2,r.marks3); vi printf("\n——-—--. os --\n"); { break; i case 4: Modify file(); break; © case 5 : exit(0); } j Pxintf(‘\n Do You want To Continue?"); ch=getch(); }while(ch=='y| |ch=='y); getch(); } . void Create_file(int n) | { | int i; I fp=fopen('stud.dat','a+*); i . ide. 4 ee 4 de EntesingSaen lll aData Structures 1-39 Introduction to C Programming for (i=0;i no. Similarly ¢ is some constant such that c > 0, We can write a {(n) < o*g(a) then f(n) is big oh of g(n). It is also denoted as f(n) € O (g(n)). The big oh describes upper bound of complexity. ie A Gulde for Engineering Students) Data Structures 2-4 Searching and Sorting Algorithms 'C * g(n) f(n) To : n f(r) € O(g(n)) Fig. Q.4.1 Big oh notation 2. Omega notation: : Omega notation is denoted by '2' A function f(a) is said to. be in Q (g(n)) if f{n) is bounded below by some positive constant multiple of g(n) such that f(n) > ¢ * g(n) For all n 2 ng It is denoted as f(n) € Q (g(n)). fin) c « g(n) t t { { To n Fig, Q.4.2 Omega notation f(n) <2 (a(n) [he big omega describes lower bound of the complexity. AGuide for Engineering Studentsn Fig. Q.4.3 Theta notation f(n) < © (g(n)) 3. Theta notation : The theta notation is denoted by ©. Let fin) and g(n) be two non negative functions. There are two constants namely ¢, and cy such that cy < g(a) Sc; gin) Then we can say that f(a) < 9 (g(a) ‘The big theta describes the exact bound of the complexity. Some Examples of Asymptotic Order loggn€ O(n) + loggn < O(n), the order of growth of logyni slower than n. But logon Qn) ~ logyn Max_value)then Max_value < Ali). Ifany value is larger than current ‘Max_value then set new Max_valne by } obtained larger value return Max value Mathematical Analysis Step 1 : The input size is n ice. total number of elements in array. Step 2 + The basic operation is comparison in loop for finding larg) value. ee A Guide for Engineering Studess'Data Structures 2-8 Searching and Sorting Algorithms Step 3 : The comparison is executed on each ition of the loop. As the comparison is made for each value of n there is no need to find best case, worst case and average case analysis, Step 4 : Let C(n) be the number of times the comparison is executed The algorithm makes comparison each time the loop executes. That means with each new value of i the comparison is made. Hence for i = 1 to ni —I times the comparison is made. Therefore we can formulate C(a) as - C(n) = One comparison made for each value of i Step 5 : Let us simplify the sum n=1 ca) = S11 1 Ca) = n-1€0(@) [vine the rule ) 1= ne O(n) i=1 J Thus the efficiency of above algorithm is © (n). Q.9 Write an algorithm for obtaining matrix multiplication. Also analyse it. Ans.: While performing matrix multiplication we scan row of first matrix and column of second matrix. For example : oo Por 490 01 292 1 2 1 2 3 C= x | on “10 11 12 4 4 5 2x3 | boy bay 5 6 Isx2 ‘The formula for multiplication of the above two matrices is 09 X boo + a1 X big + ag2x bag agg X boy + aX byy + ax bay 10% boo + a1 big + ay2X bay aygX boy + aX by +ayX boy ‘A Guide for Engineering SmdentsData Structures 2-9 Searching and Si 1x14+2x343x5 1x 242x443) 4x145x346x5 4x245xK44 22 28 c= [3 64 | Now the algorithm for matrix multiplication is - Algorithm Matrix_Mul (A[0..0-1, 0...n-1), B[O...n-1, 0...n—-1], //Problem Description : This algorithm performs multiplication //of two square matrices /fnput : Two matrices A and B //Output : C matrix containing multiplication of A and B for i-0 to n-1 do for j-0 to n-1 do Chi, J] 0 fork [SPPU : Dec.-06, Marts ¢| Ans, : Sorting is useful for arranging the data-in desired order. sorting the required element can be located easily. Searching technique is essential for locating the position of the requ clement from the heap of data. Important Points to Remember © Seaching is a technique used for locating the position of & sequixed elerment from heap of data. \e Sorting is useful for arranging the data in desired order. Q.14 What is searching technique ? Explain the basic charactaistics f searching algorithm. Ans. ; When we want w find out particular record efficiently from Given Sist of cements then there are various methods of searching element, These methods are called searching methods. at A Gulde for Engineering SextesData Structures 2-14 Searching and Sorting Algorih The basic characteristic of any searching algorithm is - i. It should be efficient. Less number of computations must be involved in it. iii. The space occupied by searching algorithms must be less. Q.15 Explain sequential searching with suitable example. Ans. : Sequential search is technique in which the given list of elements is scanned from the beginning. The key element is compared with every element of the list. If the match is found the searching is stopped otherwise it will be continued to the end of the list. Example Fig. Q.15.1 Represents students database for sequential search From the above Fig. Q.15.1 the array is maintained to store the students record. The record is not sorted at all. If we want to search the student's record whose roll number is 12 then with the key-roll number we will see the every record whether it is of roll number = 12. We obtain such a record at Array [4] location. Q.16 Write a C function for linear search. Discuss its time complexity. 5 [SPU : Dec-15, Marks 6] A Guide for Engineering Soadenss rVEULIVNGData Structures 2-15 Searching ‘and Sorting Ans, : search(int k) { for(i=0;ihigh) Tetum; mid =(low+high)/2; if: [mid}) Tetum (mid); . if(x arr [£]) fsf-a f=fta b=a b=b-a a=a-b A Guide for Engineering Students vie atin eesData Structures If Key = 20 ie. Key < ar[f] ive. 20< 70 of=f-a57-3=4 bea=3 a=b-a=2 Again we compare if (Key < ar [f]) ie. 20 < ar [4] i.e. if (20 < 40) — Yes At Present f= 4,b=3,a=2 of=f-2=4-2=2 b=a=2 a=b-a=3-2=1 Now we get f= 2,b=2,a= ath Lo] xToJoT soo] deee 8 6 os) 1 7 If Key = 60 ie, Key < arr [f] 60 < 70 wfef-a=7= 3 s14) beaa3 a=b-a=2 Again we compare if (Key > arr [f]) 60 > arr [f] ie. 40 wf=fta=4+2=6° b=b-a=3-2=1 a=a-b=2-3=-1 a b f [ [20 T 20 Tao [50 [0 [a 4 2 3 4 5 61 If (Key < arr [f]) ive, if (60 < 60) > No A Gulde for Engineering Suit?Data Structures 2-22 Searching and Sorting Algorithms If (Key < arr {f) If (key > arr (9) ie. if (20 < 20) > No If Key > arr [f]) i.e. if (60 > 60) + No ive. if (20 > 20) > No That means "Element is present — That means "Element is present at f= 2 location" at f = 6 location.” 2.8 : Sorting Methods Q.22 Write algorithm and C function for bubble sort method. Ans. : Algorithm : 1. Read the total number of elements say n 2. Store the elements in the array 3. Set thei=0. 4, Compare the adjacent elements. 5. Repeat step 4 for all n elements. 6. Increment the value of i by 1 and repeat step 4, 5 for i< n 7. Print the sorted list of elements. 8. Stop. *C! Function void bubblesort (int a[20], int n) int i, j, m,temp; for (i = O;1 A[j] then swap 4, elements. Pass | Vo 4 18 7 1 2 5 10 4 18 7 1 2 5 ha 18 7 1 is 5 4 ol 7 1 2. 5 4 10 ae 1 2 5 4 10 if ge 5 4 10 7 1 2 18 Pass Il 5 4 10 7 1 2 18 4 5 10 7 1 2 18 4 6 10 i 4 2 18 | 4 6 7 10 4 2 18 4 6 7 4 10 2 18 . 4 6 7 1 2 10 18 4 6 7 4 2 10 18 A Gulde for Engineering StudenssData Structures 2-24 Searching and Sorting Algorithms Pass Il 4 Kd 2 10 18 4 5 1 i 10 18 4 5 1 2 7 10 48 Pass IV 4 ia) 2 7 10 18 4 1 V3 7 10 48 SF 4 1 2 5 7 10 18 Pass V , TO 2 5 7 10 18 1 avi 5 7 10 18 1 2 ie 10 18 4 4 5 7 10 18 Pass Vi 1 2 4 5 This is the sorted list of elements. w 7 8 10 18 Q.24 Write a Pseudo code for selection sort algorithm, Ans, vold selection (int A/10] int 1,J,Min,temp; A Gulde for Engineering StudentsData Structures 2-25 Searching and Sorting. for (i=0;i<=n-2ji++) 41j<=n-1j++) if(A[j] [SPPU : May-10, Marks 10] Ans. : Let be the given elements. Pass 1: Consider the elements A[0] as the first element. Assume this ‘the minimum element. 0 4 2 3 4 5 t Scan the array for a finding the smallest element If smallest element is found, swap it with A[0] Ohm? i ai ae A Guide for Engineering Students:Data Structures 2-26 Searching and Sorting Algorithms Pass 2: 0 3.4 ~=65 41 2 [ere lelelel a) 4 —~_-—— Scan array for minimum element Min Pass 3: Scan array for minimum element ‘Swap Al2] and A[4] Min Pass 4: Scan'the array for finding minimum element Pass 5: o 1 2 3 4 5 Min Oo .1 02 3 4 8 a sorted list A Guide for Engineering StudentsData Structures Searching and Sorting A Q.26 What is the difference between internal sorting and sorting ? Sort he following numbers using selection sorts a ’ 25, 17, $1, 13, 2. USP (SPPU : May-18, Marks ¢) | Ans. : Difference which data resides in memory of ‘computer. . Secondary si When limited or small amount of data need to be sorted, then this technique is used, _ Examples ; Bubble sort, insertion sort, selection sort. Itis simple to implement and This is complicated and less efficient. efficient. : Step 1 : We will store the elements in an array. a Trt] 2 | — Scan array for Initially Min finding smallest element Now swap [=e Ta Te T=] these ; elements Min Smallest element [2 Tr [a TT] : ‘A Guide for Engineering StudentsData Structures 2-28 Step 2: element Swap the Be 8 NIE 728 71 «wo elements 31 | 17 | 25 ae [2 TeTe Tels] eigen Min Scan Step 4: Sorted list Se A Guide for Engineering Students Dubhlic avr -Data Structures 2-29 Searching and Sorting Algorithy, Algorithm 1, Set Oth element as Min element 2. Search the minimum element in the list. 3. If the minimum clement is found then swap it with Min. 4, Increment the position of Min to the next adjacent element 5. Repeat step 2 to 4 until the complete list gets sorted. Pseudo code Algorithm Selection(A(0...n-1]) //Problem Description : This algorithm is for sorting the //elements using selection sort method /Muput:An array of eléments A[0...1-1] that is to be sorted Output: The sorted array A[0...n-1] for(i=0;i< =n-2;i+ +) 1: { Min=i; forj=it 1j<=n-1j++) { if(A[]] #include int n; void’ main() A Guide for Engineering StudensData Structures 2-30 Searching and Sorting Algorithms int 1,A[10]; void selection(int A[10]); elrser(); printf(""\n\t\t Selection Sort\n"); printf("\n How many elements are there?”); scanf("%d" ,&n); printf(""\n Enter the elements\n"); for(i=0;i =0)&&(Alj]>temp)) { AU+1=Aqj); j=i-1;Data Structures 2-33 Searching and Sorting Algorithy, Alj+1]=temp; } Printf("\n The sorted list of elements is...\n"); for(i=0;i A [i] increment i and if A [j] > A [pivot] then decrement j. Otherwise swap A [i] and A [j] element, Step 2: A Gulde for Engineering Students