05.-Programming-Data-Structure_.pdf

Programming & Data Structures Published By: Physics Wallah ISBN: 978-93-94342-39-2 Mobile App: Physics Wallah (Available on Play Store) Website: www.pw.live Email: [email protected] Rights All rights will be reserved by Publisher...

Programming & Data Structures Published By: Physics Wallah ISBN: 978-93-94342-39-2 Mobile App: Physics Wallah (Available on Play Store) Website: www.pw.live Email: [email protected] Rights All rights will be reserved by Publisher. No part of this book may be used or reproduced in any manner whatsoever without the written permission from author or publisher. In the interest of student's community: Circulation of soft copy of Book(s) in PDF or other equivalent format(s) through any social media channels, emails, etc. or any other channels through mobiles, laptops or desktop is a criminal offence. Anybody circulating, downloading, storing, soft copy of the book on his device(s) is in breach of Copyright Act. Further Photocopying of this book or any of its material is also illegal. Do not download or forward in case you come across any such soft copy material. Disclaimer A team of PW experts and faculties with an understanding of the subject has worked hard for the books. While the author and publisher have used their best efforts in preparing these books. The content has been checked for accuracy. As the book is intended for educational purposes, the author shall not be responsible for any errors contained in the book. The publication is designed to provide accurate and authoritative information with regard to the subject matter covered. This book and the individual contribution contained in it are protected under copyright by the publisher. (This Module shall only be Used for Educational Purpose.)  Design Against Static Load INDEX 1. Data Types and Operators................................................................................................... 5.1 – 5.5 2. Control Flow Statements...................................................................................................... 5.6 – 5.8 3. Storage Class & Function..................................................................................................... 5.9 – 5.12 4. Arrays and Pointers.............................................................................................................. 5.13 – 5.22 5. Strings.................................................................................................................................. 5.23 – 5.26 6. Types of Data Structure, Array & Linked List........................................................................ 5.27 – 5.31 7. Stack and Queue.................................................................................................................. 5.32 – 5.33 8. Tree Data Structure.............................................................................................................. 5.34 – 5.38 9. Graph Traversal................................................................................................................... 5.39 10. Hashing................................................................................................................................. 5.40 – 5.41 GATE-O-PEDIA COMPUTER SCIENCE & INFORMATION TECHNOLOGY  Design Against Static Load 1 DATA TYPES AND OPERATORS 1.1 Data Types 1.1.1 Primitive Data Type (a) Integer Types: ✓ short int, unsigned short int ✓ int, unsigned int ✓ long int, unsigned long int ✓ long long int, unsigned long long int (b) Character Types: ✓ char,unsigned char (c) Floating Types: ✓ float, double, long double (d) Other: ✓ void, bool 1.1.2 Non – Primitive Data Type (a) Derived data type: ✓ Array ✓ Pointer ✓ String (b) User defined data type: ✓ Structure ✓ union ✓ Enum ✓ typedef C standard does not specify how many bits or bytes to be allocated for every type and different compiler may choose different ranges. Only restriction is that short and int types are at least 16 bits, long types are at least 32 bits and short is no longer than int which is no longer that long type. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.1  C Programming 1.2 Operators Depending upon the number of operands, an operator in C language can be unary, binary or ternary. 1.2.1 Arithmetic Operators (i) Addition (+) (ii) Subtraction (-) (iii) Multiplication () (iv) Division (/) (v) Modulus (%) Both operands for % operator must be integer types, otherwise error will be raised. The sign of the result for modulo operator is machine dependent. 1.2.2 Relational Operators (i) Less than () (iii) Less than equal to (< =) (iv) Greater than equal to (> =) (v) Equal checking (= =) (vi) Not Equal to (! =) The result of these operators is always 0 to 1 Ex.1: printf (“%d”,20 > 10) O/P: 1 Ex.2: printf (“%d”,20 = = 10) O/P: 0 1.2.3 Assignment Operator (=) Used to assign a value or value of an expression to a variable. Typically, the system is Lvalue = Rvalue Lvalue must be a variable. Lvalue cannot be a literal or expression. Rvalue can be an expression, variable, literal. Ex1. The following are invalid 10 = a; a + b = c; The result of assignment statement is the value we are assigning i.e…… int x; x = 3 + (x = 10); is perfectly valid. Firstly x = 10 evaluated and (1) 10 is assigned to x (2) then the result of (x = 10) will be 10 so, x = 3 + 10 GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.2  C Programming x = 13 Finally, 13 is assigned to x. 1.2.4 Logical Operators (i) Logical AND (&&) (ii) Logical OR (||) (iii) Logical NOT (!) Just like rational operators, the result of every logical operator is either 0 or 1. Logical NOT is a unary operator Logical NOT converts a non-zero operand into 0 and a zero operand in 1. 1.2.5 Short Circuiting in Logical Operators In case of logical AND, the second operand is evaluated only if the first operand is evaluated to be true. If the first operand is evaluated as false then the second operand is not evaluated. In case of logical OR operation, the second operand is not evaluated if the first operand is evaluated as true. Example1: void main () { printf (“Hello”) || printf (“Pankaj”); } O/P: Hello printf function display everything written within double quotes on the monitor and the result / value returned by printf () is the number of characters successfully displayed on the screen. So, printf (“Hello”) prints Hello and return 5. So, the expression printf (“Hello”) || printf (“Pankaj”); becomes 5 || printf (“Pankaj”) As the first operand for logical OR is evaluated as true, second printf () will never execute. 1.2.6 Increment and Decrement Operators (i) pre increment ++x (ii) post increment x++ (iii) pre decrement - -x (iv) post decrement x - - unary operator. can’t be applied on constant / literals. Pre increment: can be viewed as 2 step operators. 1st step: Increment the value of variable. 2nd step: After increment, use the value of variable. Post increment: can be viewed as 2 step operators 1st step: Use the value. 2nd step: Increase the value of variable by 1. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.3  C Programming 1.2.7 Bitwise operators (i) Bitwise AND (&) (ii) Bitwise OR (|) (iii) Bitwise XOR (^) (iv) Bitwise Left Shift () (vi) Bitwise Not ( ) All these operators work on binary representation of numbers. Typically, faster than arithmetic operators and other operators. #include int main () { int x = 3, y = 6; printf (“%d\n”,x & y); // output 2 printf (“%d\n”,x|y); // output 7 printf (“%d\n”, x^y) // output 5 return 0; } binary representation of 3: 00000000...0011 binary representation of 6: 00000000...0110 3 & 6: 00000000...0010 3 | 6: 00000000...0111 3 ^ 6: 00000000...0101 XOR of two bits is 1 if both bits are different. XOR of two bits is 0 if both bits are same.  x has output as – (x + 1) printf (“%d\n”, ~2) has output -3 i.e., -(2 + 1) Comma has lowest precedence among all operators in C language. sizeof() is used (i) To find the number of elements present in an array. (ii) To dynamically allocate block of memory. 1.2.8 Ternary operator (? :) It requires 3 operands i.e., Left, Middle, Right Left ? Middle : Right If left expression evaluates as true, then the value returned is middle argument otherwise the returned value is Right expression int a; a = 7 > 2 ? 3  2 + 5 : 6! = 7  Left expression: 7 > 2 is true  So, the value returned would be the middle argument. i.e., 3  2 + 5 = 11 so, a will get 11. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.4  C Programming Note: (a) No of ‘?’ and ‘:’ should be equal. (b) Every colon (:) should match with just before ‘?’. (c) Every ? followed by : not immediately but following. Example: int a; a = 2 > 5 ? 10 : !5! = 2 > 5 ? 20 : 30 L1 M1 R1 2 > 5 is false. so, for Leftmost ? the value returned is its right expression. a = ! 5 ! = 2 > 5 ? 20 : 30 : Left Mid Right Left expression: !5! = 2 > 5 0! = 2 > 5 0! =0 0 i.e., false. As left operand is false, the final value is right expression a = 30 Operators Associativity () [] ->. Left to right !  ++ -- + - * (type) size of Right to left */% Left to right +- Left to right > Left to right < >= Left to right == != Left to right & Left to right ^ Left to right | Left to right && Left to right || Left to right ?: Right to left = += -= *= /= %= &= ^= |= = Right to left , Left to right  GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.5  C Programming 2 2.1 Switch Statement CONTROL FLOW STATEMENTS “Case Value” can be of character type and int type. There can be one or many number of cases. Statements associated with a matching case executes until a break statement is reached. The position of default case does not matter. It can be placed anywhere. Default case is optional. Duplicate case labels are not allowed. Statements written before all the cases are ignored by the compiler. The break statement is optional. Case label cannot be a variable. 2.2 Iterative statements (Loop) An iterative statement, or loop, repeatedly executes a group of statements, known as body of loop, until the controlling expression is false. 2.2.1 For Loop The for statement evaluates 3 expressions and executes the loop body until second controlling expression executes to false. It is recommended to use for loop when the number of iterations is known in advance. Syntax of for loop is: for (expression – 1(optional); expression – 2(optional); expression – 3(optional)) { statement – 1 statement – 2 statement – n } for loop executes the loop body 0 or more times. for statements works as follows: (a) expression – 1 is evaluated once before the first iteration of the loop. (b) expression – 2 is a expression that determines whether to terminate the loop. expression – 2 is evaluated before every iteration. If the expression is true (non - zero), the loop body executed. If the expression is false (zero), execution of the for statement is terminated. (c) expression – 3 is evaluated after each iteration. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.6  C Programming (d) The for statement executes until expression-2 is false (0), or until a jump statement terminates execution of the loop. All 3 expression can be omitted (a) If we omit expression-2, the condition is considered as true for an example: for (i = 0; ; i++) represent an infinite loop statement. 2.3 While Statement The while statement evaluates a controlling expression before every execution of the loop body. If the controlling expression is true (non-zero), the loop body is executed. If the controlling expression is false (zero), then the while statement terminates. Syntax: while (expression) while (expression) OR { statement statement-1 statement-2 statement-n } 2.4 Do-while Loops Both for and while loop checks the loop termination condition before every iteration but do while loop check the condition after executing the loop body. do while loop body executes at least 1 time, no matter whether the loop termination condition is false or true. Syntax is: do do { statement statement-1 OR statement-2 while (expression); statement-n } while (expression); 2.5 Break Statement The break statement provides an early exit from for, while and do while. A break statement causes the innermost loop or switch to be exited immediately. In implementation, when we know the maximum number of repetition but some condition is there, where we require to terminate the repetition process, then use break statement. Example: void main () { int i = 1; while (i < = 15) { GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.7  C Programming printf(“%d\t”,i); if (i > 4) break; i = i + 1; } printf(“End”); } Output: 1 2 3 4 End In above code, when i becomes 5, the condition i > 4 becomes true, so break statement executes & control passed outside of the loop body i.e., printf(“End”) executed. 2.6 Continue Statement Continue statement is related to break but it is not used that much frequently. Whenever continue is encountered in a loop, it skips the remaining statement of the current iteration and continues with the next iteration of the loop. Only applicable with loops, not with switch statement. Example: void main () { int i = 1; for (i = 1; i < = 10; i++) { if(i%2 = = 0) continue; printf(“%d”,i); } } Output: 13579 (All odd numbers between 1 to 10) whenever i becomes even, condition i%2 = = 0 becomes true & continue causes the control to go to i++ & printf is skipped.  GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.8  C Programming 3 STORAGE CLASS & FUNCTION 3.1 Memory Organization of C Program 3.1.1 Code Segment It is also known as text segment. It contains executable instructions and this segment is a read only segment. Usually, this section is sharable. 3.1.2 Uninitialized data segment This section contains all static and global variables that are not initialized by the programmer and hence initialized to zero (default value). 3.1.3 Initialized data segment This section contains all static and global variables that are initialized by the programmer. 3.1.4 Stack In this local variables are stored and some other information is also saved. A set of values stored for a function is called as stack frame which atleast contain return address. 3.1.5 Heap This area is responsible for dynamic memory allocation. The heap area is managed by malloc(), calloc(), ralloc() and free() which may be use brk() and sbrk() system calls. 3.1.6 Static Memory Compile time allocation Static variable Global Variable 3.2 Storage Classes Storage Scope Life Time Default Storage area Class Within Garbage auto Local RAM function Value Till end of static Local main 0 RAM program GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.9  C Programming Till end of extern Global main 0 RAM program Within Register Local Garbage Register function Stack Overflow: Abnormal Termination If conflict between global and local variable occurs, then local variable gets preference. Declaration of a register variable is only a recommendation/request not a command. Cannot apply ‘&’ operator with register variable. No physical memory is allocated using ‘extern’ keyword. Extern declaration is mandatory when an external variable is referred before it is defined or if it is defined in some other source file from the file where it is being used. Declaration of an external variable tells about the properties like its type, while definition leads to storage allocation. 3.3 Recursion Definition: When the body of a function call the function itself directly or indirectly. Certain arguments for which the function does not call itself are called as base argument, base values. In general, for recursion to be non-cyclic whenever a function calls itself the formal arguments must get closer to the base argument. Example 1: Consider the factorial code: int factorial (int n) { if (n = = 0) return 1; else return n * factorial (n - 1); } If we call factorial (3), it will call factorial of 2 and so on …the argument will get closer to 0 i.e., the base argument. Recursion code is shorter than iterative code. Overhead is present. Some standard problems are best suited to be solved by using recursion for example- Tower of Hanoi, Factorial, merge Sort. 3.4 Static and dynamic scoping 3.4.1 Static Scoping Static scoping is also called as lexical scoping. In this scoping, the binding of a variable can be determined by the program text. In this type of scoping compiler first looks in the current block (local), then in global variables i.e., local and then ancestors’ strategy is followed. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.10  C Programming Example 1: int a = 10; void main () { int a = 1; { int a = 2 printf(“%d”,a); } } Output: 2 As printf is referring to a, compiler first check in the current block & gets a variable whose value is 2. Example 2: int a = 10; void main () { int a = 1; { Scope S1 int b; Scope S2 printf(“%d”,a); } } Output: 1 Compiler looks for ‘a’ in scope S1, because S1 does not have variable a, it will look into higher scope S2 that contains a variable name a whose value is 1. 3.4.2 Dynamic Scoping In this type of scoping, the compiler first searches the current block and then successively searches all calling functions. Example: int i; program main () { i = 10; call f (); } procedure f () { int c = 20; call g(); } Procedure g() { print i; } Assuming that the above program is written in a hypothetical programming language which allows global variables GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.11  C Programming and dynamic scoping, let’s try to find the output. The order of function calls is: calling calling main () ⎯⎯⎯⎯→ f() ⎯⎯⎯⎯→ g() g() is printing i, which is not present inside current block. So, because of dynamic scoping compiler will go to the function that calls g() i.e., compiler will search f() for variable i. Hence 20 is printed.  GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.12  C Programming 4 ARRAYS AND POINTERS 4.1 Array An array is defined as the collection of similar type of data items stored at contiguous memory locations. Arrays are the derived data type in C programming language which can store the primitive type of data such as int, char, double etc. It has the capability to store the collection of derived data types such as pointer, structure etc. Each element of an array is of same data type and carries the same size example int = 4 byte. Elements of the array are stored at contiguous memory locations, meaning, the first element is stored at the smallest memory location. Elements of the array can be randomly accessed since we can calculate the address of each element of array with the given base address and size of the data element. 4.1.1 Advantages of C Array 1) Code Optimization: Less code to access the data. 2) Ease of traversing: By using the for loop, we can retrieve the elements of an array easily. 3) Ease of sorting: To sort the elements of the array, we need a few lines of code only. 4) Random Access: We can access any element randomly using the array. 4.1.2 Disadvantages of Array Fixed Size: 1) Whatever size, we define at the time of declaration of the array, we can’t exceed the limit. 2) It does not grow the size dynamically like linked list. Declaration of C Array Syntax: Example: Initialization of C array: We can initialize each element of the array by using the index. Suppose array int marks. Then GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 5.13  C Programming marks = 80 marks = 60; marks = 70; marks = 85; marks = 75; 80 60 70 85 75 Marks Marks Marks Marks Marks C Array Example: # include int main () { int i = 0; int marks ; marks = 80; marks = 60; marks = 70; marks = 85; marks = 75; for(i = 0; i