PREFACE This study material deals with the concepts of c programming and algorithms. C is a general- Purpose high level language that was originally developed by Dennis Ritchie for the Unix operating system. Tt was first implemented on the Digital Equipment Corporation PDP-11 computer in 1972. C was initially "used for system development work, in particular the programs that make-up the operating system. C was adopted as a system development language because it produces code that runs nearly as fast as code written in assembly language. All the C programs are written into text files with extension ".c’. When you write any program in C language to be executed then, that program need to be compiled by aC Compiler. The compiler converts the program into object code which can be read by a computer. This is called machine language (i.e. binary format). So before proceeding, make sure you have C Compiler available in your computer. Analgorithm refers to the concept of data structures in detail. efore introducing data structures we should understand that, computer is to store, retrieve, and process « large amount of data. Ifthe data is stored in well organized way on a storage medium and in computer's memory then it can be accessed quickly for processing. This can further reduce the latency and the user is provided fast response. Data Structure isa way of collecting and organizing data in such a way that we can perform operations on these data in an effective way. Data Structures is about rendering data elemeats in terms of some relationship, for better organization and storage. A data structure should be seen as a logical concept that must address two fundamental concerns. First, how the data will be stored, and second, what operations will be performed on it? As data structure isa scheme for data organization so the functional definition of a data structure should be independent of its implementation. The functional definition ofa data structure is known as ADT (Abstract Data Type) which is independent of implementation. The implementation partis left on developers who decide which technology better suits to their project needs. Ms. Uma Shankari HoD Department of Computer Application Dr. M.G.R. Janaki Arts & Science College for WomenDEGREE OF BACHELOR OF COMPUTER APPLICATIONS & LAW (B.C.A.LLB,) Title of the Programming in Cand Algorithms(HDAH) Course/ Paper Core - 1 1 Year & Second Semester Credit: 4 Objective of | This course introduces the basic programming concepts and fundamentals of the course Programming Language C and Algorithm Unit 1: C fundamentals Character set — Identifier and keywords — data types — constants ~ Variables — Declarations ~ Expressions ~ Statements - Operators ~ Library functions- Data input output functions - Simple C programs — Flow of control - if, if-else, while, do-while, for loop, Nested control structures ~ Switch, break and continue, go to statements - Comma operato- Unit-2: Functions -Definition ~ proto-types — Passing a:guments- Recursions- Storage Classes ~ Arrays ~ Defining and Processing ~ Passing arrays to functions = Multi-dimension arrays — Arrays and String. Structures ~ User defined data types ~ Passing structures to functions — Self-referential structures - Unions — Bit Course outline | wise operations. Unit 3: Fundamentals of algorithms - Notion of an algorithm- Pseudo-code conventions like assign ment statements and basic controi structures ~ Analysis of algorithms - Running t me of an algorithm - worst and average case analysis. Unit-4: Sorting Algorithms - Bubble, Selection- Insertion and Merge sort- Efficiency of algorithms -Implement using C- Searching Algorithms-Linear Search and Binary Search - Graph Algorithms- BFS, DFS, shortest paths - single source and all pairs. Unit-5 : Pointers ~ Decla-ations — Passing pointers to Functions — Operation in Pointers - Pointer and Arrays ~ Arrays of Pointers ~ Structures and Pointers — Files- Creating, Processing, Opening and Closing a data file. Recommended Texts () — E.Balagursamy, 2010, Programming in ANSI G, Fifth Edition, TMH. New Delhi. (ii) Horowitz, S. Sahni, and S. Rajasekaran, Computer Algorithms, Galgotia Pub, Pvt. LTs., 1998. Reference Books (i) B. W. Kernighan and D. M. Ritchie, 1990, The C Programming Language, Second Edition, PHI, New Delhi. (ii) J.R. Hanly and E. B. Koffman, 2005, Problem solving and program design in C, Fourth Edition, Pearson Education India. (iii) H.Schildt, C: The Complete Reference, 4” Edition, TMH Edition, 2000.PROGRAMMING IN C AND ALGORITHMS S.No. CHAPTER DETAIL PAGE No. 1. INTRODUCTION TO C 1 2. C FUNDAMENTALS 5 3. OPERATORS AND EXPRESSIONS 11 4, DATA INPUT AND OUTPUT FUNCTIONS 16 5. CONTROL STRUCTURES 20 6. FUNCTIONS 28 7. STORAGE CLASSES 34 8. ARRAYS AND STRINGS 36 9. STRUCTURES AND UNIONS 42 10. ALGORITHMS 49 11. SORTING ALGORITHMS 72 12. SEARCHING ALGORITHMS 86 13. POINTERS, 100 14. DATA FILES. 104 SIMPLE C PROGRAMS 110CHAPTER 1 INTRODUCTION Computer Basically it is a fast calculating machine which is nowadays used for variety of uses ranging from house hold works to space technology. The credit of invention of this machine goes to the English Mathematician Charles Babbage. Types of Computers: Based on nature, computers are classified into Analog computers and Digital computers. The former one deals with measuring physical quantities (concerned with continuous variables) which are of late rarely used. The digital computer operates by counting and it deals with the discrete variables. There isa combined form called Hybrid computer, which has both features. Based on application comput2rs are classified as special purpose computers and general computers. As the name tells special computers are designed to perform certain specific tasks where as the other category is designed to cater the needs of variety of users. Basic structure of a digital computer The main components of a computer are 1) Inputunit (IU), 2) — Central Processing unit (CPU) and 3) Output unit (OU). The information like data, programs etc are passed to the computer through input devices. The Keyboard, mouse, floppy disk, CD, DVD, joystick etc are certain input dev ices. The output device is to get information from a computer after processing. VDU (Visual Display Unu'), Printer, Floppy disk, CD etc are output devices. The brain ofa computer is CPU. It has three components- Memory unit, Control unit and Arithmetic and Logical unit (ALU)- Memory unit also called storage device is to store information. Two types memory are there in a computer. They are RAM (random access memory) and ROM (read only memory). When é program is alld, itis loaded and processed in RAM. When the computer is switched off, what ever stored in RAM will be deleted. So it is atemporary memory. Where KOM isa permanent memory, where data, program etc are stored for future use. Inside a computer there is storage device called Hard disk, where data are stored and can be accessed at any time. The contro} unit is for controlling the execution and interpreting of instructions stored in the memory. ALU is the unit where the arithmetic and Logical operations are performed. The information toa computer is transformed to groups of binary digits, called bit. The length of bit varies from computer to computer, from 8 to 64. A group of 8 bits is called a Byte and a byte generally represents one alphanumeric (Alphabets and Numerals) character. The Physical components of a computer are called hardwares. But for the machine to work it requires certain programs (A set of instructions is called a program). They are called softwares. There are two types of softwares ~ System software and Application software ~ System software includes Operating systems, Utility programs and Language processors.ASCII Codes: American Standard Code for Information Interchange. These are binary codes for alpha numeric data and are used for printers and terminals that are connected to a computer systems for alphabetizing and sorting. Operating Systems The set of instructions which resides in the computer and governs the system are called operating systems, without which the machine will never function. They are the medium of communication between a computer and the user. DOS, Windows, Linux, Unix etc are Operating Systems. Utility Programs ‘These programs are developed by the manufacturer for the users to do various tasks. Word, Excel, Photoshop, Paint etc are some of them. Languages These programs facilitate the users to make their own programs. User's programs are converted to machine oriented and the computer does the rest of works. Application Programs These programs are written by users for specific purposes. Computer Languages They are of three types — 1 Machine Language (Low level language) 2 Assembly language (Middle level language) 3 User Oriented languages (High level language) Machine language depends on the hardware and comprises of 0 and 1 . his is tough to write as one must. know the internal structure of the computer. At the same time assembly language makes use of English like wordsand symbols. With the help of special programs called Assembler, assembly language is converted to machine oriented language. Here also a programmer faces practical difficulties. To overcome this hurdles user depends on high level languages, which are far easier to learn and use. To write programs in high level language, programmer need not know the characteristics of a computer. Here he uses English alphabets, numerals and some special characters. Some of the High level languages are FORTRAN, BASIC, COBOL, PASCAL, C, C++, ADA etc. We use C to write programs. Note that High level languages cannot directly be followed by a computer. It requires the help of certain software's to convert it into machine coded instructions. This software's are called Compiler, Interpreter, and Assembler. The major difference between a compiler and an interpreter is that compiler compiles the user's program into machine coded by reading the whole program at a stretch where as Interpreter translates the program by reading it line by line. C and BASIC are an Interpreter where as FORTRAN is aPROGRAMMING METHODOLOGY A computer is used to solve a problem. The steps involved are : 1. Analyze the problem Identify the variables involved Design the solution Write the program Enterit into a computer Compile the program and correct errors Correct the logical errors if any Test the program with data pena een Document the program Algorithms Step by step procedure for solving a problem is called algorithm. Example To make a coffee Stepl: Take proper quantity of water in a cooking pan Step2: Place the pan on a gas stove and light it Step3: Add Coffee powder when it boils Step4: Put out the light and add sufficient quantity of sugar and milk Step5: Pour into cup and have it. Toadd two numbers Step1: Input the numbers asx, y Step2: sum=x+y Step3: print sum Fora better understanding of an algorithm, it is represented pictorially. The pictorial representation of an algorithm is called a Flow Chart. For this certain pictures are used. Consider a problem of multiplying two numbers Algorithm Step1: Input the numbers asa and b Step2: find the product axbStep3: Print the result Consider the following problem to find the highest of three numbers Algorithm Step 1: read the numbers as x,y and z Step 2: compare xand y Step 3: ifx > y then compare x with z and find the greater Step 4: Otherwise compare y with z and find the greater Review Questions 1. Define computers? 2. Enlist the features of C. 3. How will you classify computer systems? 4. Whatare the basic operations of Computer? 5. Whatare the characteristics of computers? 6. Whatare the steps to solve the problem in a computer system? Exercise: Write Algorithm and flow chart for the solution to the problems: 1. Tofind the sum ofr, say 10, numbers. To find the factorial of n, say 10. To find the sum of the series 1+x+x2+x3+... To find the sum of two matrices. To find the scalar product of two vectors To find the Fibonacci series up ton. yoy es op To find ged of two numbersCHAPTER 2 C FUNDAMENTALS A BRIEF HISTORY OF C evolved from a language called B, written by Ken Thompson at Bell Labs in1970. Ken used B to write one of the first implementations of UNIX. Bin turn was descendant of the language BCPL (developed at Cambridge (UK) in 1967), with most of its instructions removed. So many instructions were removed in going from BCP]. to B, that Dennis Ritchie of Bell Labs put some back in (1972), and called the language C. The famous book The C Programming Language was written by Kernighan and Ritchie in 1978, and was the definitive reference book on C for almost a decade. The original C was still too limiting, and not standardized, and so in 1983 an ANSI committee was established. to formalise the language definition. It has taken until now (ten years later) for the ANSI (American National Standard Institute) standa-d to become well accepted and almost universally supported by compilers STRUCTURE OF A PROGRAM AC program basically consists of the following parts: © Preprocessor Commands . Functions * Variables © Statements & Expressions © Comments Let us look ata simple code that would print the words “Heilo World”: #includecstdio.h> Intmain() { /*my first program in C*/ Printf(“Hello, World! \n"); Return 0; } Let us look various parts of the above program: 1. Thefirstline ofthe program #include is a preprocessor command, which tells a C compiler to include stdio.h file before going to actual compilation 2. Thenext ine int main()is the main function where program execution begins. 3. Thenextline/*.../ will be ignored by the compiler and it has been put to add additional comments in the program. So such lines are called comments in the program. 4, Thenext line printf{...)is another function available in C which causes the message “Hello, World!” to be displayed on the screen. 5. The next line return 0; terminates main()function and returns the value 0. 5THE CHARACTER SET The character set is the fundamental raw material of any language and they are used to represent information. Like natural languages, computer language will also have well defined character set, which is useful to build the programs. Types Character Set Lowercase Letters az Uppercase Letters AtoZ Digits 0-9 Special Characters 1@#S%"K* White Spaces ‘Tab Or New line Or Space IDENTIFIER AND KEYWORDS Identifier are names given to various program elements like variables, arrays and functions. () The name should begin with a letter and other characters can be letters and digits and also can contain underscore character ( _)Example: area, average, x12, name_of_place etc.. (ii) Keywords are reserved words in C language. They have predicted meanings and are used for the intended purpose. Standard keywords are auto,break, case, char, const, continue, default, do, double, else enum, extern, float, for, goto, if, int, long, register, return, short, signed, sizeof, static, struct, switch, typedef, union, unsigned, void, volatile, while. (Note that these words should not be used as. identities.) DATA TYPE © The variables and arrays are classified based on two aspects first is the data type it stores and the second is the type of storage. © The basic datatypes in C language are int, char, float and double. © They are respectively concerned with integer quantity, single character, numbers, with decimal point or exponent number and double precision floating point numbers (ie; of larger magnitude ). © These basic data types can be augmented by using quantities like short, long, signed and unsigned. ( ie; long int, short int, long double etc.....) CONSTANTS There are 4 basic types of constants. They are integer constants, floating-point constants, character constants and string constants (a) Integer constants: It is an integer valued numbers, written in three different number system, decimal (base 10) , octal(base8), and hexadecimal(base 16). A decimal integer constant consists of 0,1,.. Example : 75 6,0,32, etc..... 5,784, 39,98, 2-5, 09 etc are not integer constants. 6‘An octal integer constant consists of digits 0,1,....7. with Ist digit 0 to indicate that it is an octal integer. Example : 0, 01, 0756, 032, etc..... 32, 083, 07.6 etc..... are not valid octal integers. A hexadecimal integer constant consists of 0,1, ....9,A, B.C, D, E, F. It begins with Ox. Example: 0x7AA2, OxAB, etc...... 0x8.3, OAF2, OxG etc are not valid hexadecimal constants. Usually negative integer constant begin with (-) sign. An unsigned integer constant is identified by appending U to the end of the constant like 673U, 098U, 0xACLFUetc. Note that 1234560789LU is an unsigned integer constant. (b) floating point constants : It is a decimal number (ie: base 10) with a decimal point or an expor ent or both. Ex; 32.65, 0.654, 0.2E-3, 2.65E10 etc. These numbers have greater range than integer constants. (©) Character constants : It is a single character enclosed in single quotes like ‘a’. ‘3', ”, ‘A’ etc. each character has an ASCII to identify. For example ‘A’ has the ASCII code 65, '3' has the code 51 and soon. (@) escape sequences: An escape sequence is used to express non printing character like a new line, tab etc. it begin with the backslash (\) followed by letter like a. n, b, t, v,r, etc. the commonly used escape sequence are \a: for alert \n: newline \0: null \b: backspace \F: form feed \?: question mark \f:horizontal tab \r: carriage return _\’: single quote \v: vertical tab —_\": quotation mark (©) string constants: it consists of any number of consecutive characters enclosed in double quotes .Ex C program” , “mathematics” etc...... VARIABLES AND ARRAYS A variable is an identifier thar is used to represent some specified type of information. Only a single data can be stored in a variable. The data stored in the variable is accessed by its name. before using a variable ina program, the data type it has to store is to be declared. Example : int a, b, c, a=3; c=atb; Note: A statement to declare the data types of the identifier is called declaration statement. An array isan identifier which is used to store a collection of data of the same type with the same name. the data stored isan array are distinguished by the subscript. The maximum size of the array represented by the identifier must be mentioned. Example : int mark(100] . With this declaration n, mark is an array of size 100, they are identified by mark{0},mark{1}...........mark[99].Note : along with the declaration of variable, it can be initialized too, For example int x=10; with this the integer variable x is assigned the value 10, before it is used. Also note that Cis a case sensitive language. i.e. the variables d and D are different. DECLARATIONS This is for specifying data type. All the variables, functions etc must be declared before they are used. A declaration tells the compiler the name and type of a variable you'll be using in your program. nits simplest form, a declaration consists of the type, the name of the variable, and a terminating semicolon: Example : inta,bc; Float mark, x{100], average: char name(30); char e; inti; float f; You may wonder why variables must be declared before use. There are two reasons: 1. It makes things somewhat easier on the compiler; it knows right away what kind of storage to allocate and what code to emit to store and manipulate each variable; it doesn’t have to try to intuit the programmer's intentions. 2, It forces a bit of useful discipline on the programmer: you cannot introduce variables willy-nilly; you must think about them enough to pick appropriate types for them. (The compiler’s error messages to you, telling you that you apparently forgot to declare a variable, are as often helpful as they are a nuisance: they're helpful when they tell you that you misspelled a variable, or forgot to think about exactly how you were going to use it.) EXPRESSION This consists of a single entity like a constant, a variable, an array or a function name. it also consists of some combinations of such entities interconnected by operators. Example : a, a+b, xey, caatb, xcay ete. STATEMENTS Statements are the “steps” ofa program. Most statements compute and assign values or call functions, but we will eventually meet several other kinds of statements as well. By default, statements are executed in sequence, one after another ‘A statement causes the compiler to carry out some action. There are 3 different types of statements ~ expression statements compound statements and control statements. Every statement ends with a semicolon.Example: (1) e=a +b; QE a=3; (3) if (a (greater than ), >= ( greater than or equal to), equal to) and = (not equal to ) are relational operators. A logical expression is expression connected with a relational operator. For example ‘b'b — 4°a'c4 has the value true k-2) 2. (ac=3) || (b>2) In the first example if a= -3 or a=6 the logical expression returns true. ASSIGNMENT OPERATORS ‘These operators are used for assigning a value of expression tw another identifier. a+ /z and %= are assignment operators. a= bic results in storing the value of bec in ‘a’. a+=5 results in increasing the value of a by 5 a /=3 results in storing the value a/3 in a and it is equivalent a: a/3 Note : 1. ifa floating point number is assigned to a integer type data variable, the value will be ‘truncated. Example : float =5.36; int; bea It results in storing 5 to b. Similarly if an integer value is a assigned to a float type like float x=3 the value of x stored is 3.0. CONDITIONAL OPERATOR The operator ?: is the conditional operator. It is used as variable 1 = expression 1 ? expression 2 : expression 3. Here expression 1 isa logical expression and expression 2 and expression 3 are expressions having numerical values. If expression 1 is true, value of expression 2 is assigned to variable | and otherwise expression3 is assigned. Example : inta,b,c,d,e de(acb)?a: e=(b>c) 2b; ‘Then d=3 and e=8 13LIBRARY FUNCTIONS They are built in programs readily available with the C compiler. These functions perform certain operations or calculations. Some of these functions return values when they are accessed and some carry out certain operations like input, output. A library function accessed in a used written program by referring its name with values assigned to necessary arguments. Some of these library functions are : abs(i),ceil(d), cos(d), cosh(d), exp(d),_fabs(d),floor(d), —getchar(_—_), 1og(4),pow(d,d’),printf( ), putchar(c), rand( ), sin(d), sqrt(d), scanf( ), tan(d), toascii(c),toupper(c), tolower(c). Note: the arguments i, c, d are respectively integer, char and double type. Example: #includecmath.h> #includecstdio.h> #include main() { float x, s; printf(“\n input the values of x:"); scanf(“F", 8%); sesqrt(x)s printf(“\n the square root is 96f”,s); J Review Questions 1. Distinguish between binary minus and unary minus. List out the different operators involve for comparision and logical decision making in C. List out the five arithmetic operators in C. What are the rules to use period(.) operator. What is an expression? How is an expression different from the variables? What is mean by conditional expression? Noyes wn What is mean by the comparision and logical operator? How are they different from the arithmetic and assignment operator? 8. What is mean by the equality operator? How do these differ from an assignment operator. 14‘What is modulus operator and how does it operate in C. “What is the associtivity rules involve in this operator. What is unary operator? List out the different operator involve in the unary operator. Can multiple assignments be written in C. In what order will the assignment be carried out. Describe arithmetic operator? Differentiate between relational and logical operators used in C? Discuss Precedence order and associativity of operators Discuss the conditional operator with the help ofa program. Explain * operator and & operator with example. Explain conditional operator with example. Explain logical operators and expressions used in C? Explain sizeof operator with example. Explain the difference between ‘=’ and ‘==’ operator explain with example? Explain with example ++i and i++. ‘What are Operators? Mention their types in C. What do you understand by operators? Explain the use of the following operators : “What is an expression? How is an expression differing from variables? ‘What is the modulus operator and how does it works explain it with example ‘What is the purpose of comma operator within which statement does the comma operator usually appear. ‘What is unary operator? ‘Write a short note precedence & order of ‘evaluation?CHAPTER 4 DATA INPUT & OUTPUT For inputting and outputting data we use library function. The important of these functions are getch( ), Putchar( ), scanf{ ), printf(), gets( ), puts( ). For using these functions in a C-program there should be a Preprocessor statement #include. {A preprocessor statement is a statement before the main program, which begins with # symbol.) stdio.h isaheader file that contains the builtin program of these standard input output function. getchar function - It is used to read a single character (char type) from keyboard. The syntax is char variable name = getchar( ); Example: chary, c= getchar( ); For reading an array of characters or a string we can use getchar() function. Example: #include main() { char place(80); int i; for(i = 0;( place [i] = getchar( ))! = “\n’, ++i); } This program reads line of text. putchar function - Itis used to display single character. The syntax is putchar(char ¢); Example: char; cma; putchar(c); Using these two functions, we can write very basic program to copy the input, a character ata time, tothe output: #include /" copy input to output */ main() i inte; c=getchar();while(c != EOF) { putchar(c); c= getchar(); } return 0; } scan function - This function is generally used to read any data type: int, char, double, float, string, The syntax is scanf (control string, list of arguments); The control string consists of group of characters, each 8roup beginning % sign and a conversion character indicating the data type of the data item, The conversion eharacen are c,d,e,f.0,s,u,x indicating the type resp, char decimal integer, floating point value in exponent form, Aloating point value with decimal point, octal integer, string, unsigned integer, hexadecimal integer. ie "Se" "Oia etcare such group of characters, An example of reading a data: #includecstdio.h> main() ( char name{30), line; int x; float y; scanf(“%bs%d%F", name, &x, &y); scanf(“%c",}ine); } NOTE: 1)In the list of arguments, every argument is followed by & (ampersand symbol) except string variable. 2) s-type conversion applied to a string is terminated by a blank space character. So string having blank space like “Govt, Victoria College” cannot be read in this manner Fae reading such a string constant we use the conversion string as “%[*\n]" in place of “96g”, Example: char place{80}; scanf("%[\n)", place); with these statements. line: of text (until carriage return) can be input the variable ‘place’, 17printf function Thisis the most commonly used function for outputting data of any tyPe- The syntax is printf(control string, list of arguments) Here also control string consists of group of characters, each group having % symbol and conversion characters like ¢, d, 0, f, xete. Example: #includecstdio.h> ‘main() t intx; scanf("%6d” Sx); xox printf(“The square of the number is %d".*) } Note that in this list of arguments the variable names are without &symbol unlike in the case of scanf{ ) fametion. Inthe conversion string one can include the message to ‘be displayed. In the above example “The square of the number is” is displayed and is Followed by the value of x. For writing a line of text (which isctude blank spaces)the conversion string is “és” unlike in scanf function. (There itis “{*\n)")- More about printf statement There are quite a number of format specifiers for printf, Here are the basic ones: print an int argument in decimal print along int argument in decimal printa character printa string print a float or double argument same as %f, but use exponential notation use %e or %f, whichever is better print an int argument in octal (base 8) princan int argument in hexadecimal (base 16) geegeeerge print a single % To illustrate with a few more examples: the call printf(‘%c ed 96£%e 96s %649694\n”, ‘1’ 2.3.14, 56000000.,"eight”, 9); would print 123.140000 5.600000e+07 eight 9% The call printf(“96d %o %x\n”, 100, 100, 100); 18would print 100 144 64 Successive calls to printf just build up the output a piece at a time, so the calls printf(“Hello, *); printf(‘world!\n”); ‘would also print Hello, world! (on one line of output). While inputting or outputting data field width can also be specified. This is included in the conversion. string.(if we want to display a floating point number convert to3 decimal places the conversion string is “9.3f") For assigning field width, width is placed before the conversion character like"9%10f’,"%8d"."%12e” and so on... Also we can display data making correct toa fixed no of decimal places. For example if we want to display x-30.2356 as 30.24 specification may be “9%5.2f" or simply “%.2f". Review Questions 1. _ Distinguish between i)fprintf()ii)fscanf() 2. Distinguish between getch and getc 3. Distinguish between putch and pute 4. Explain i)fprintf()ii)fscanf() 5. Explain putc and getc in brief 6. Whatare the format codes used along with the scanf(). Display the various data types in C. 7. Whatare the salient features of standard input and output file 8 Whatis the printf() and compare with putchar(). 9. What is the scanf{) and how does it differ from the getchar‘).. 10. Difference between formatted & unformatted statement? 11. Explain - a) getc() b) pute’) 12. Explain Getw() & Putw() function 13, Explain printf() function with an example 14. Explain the following functions i)getch() and ii) clrscr()CHAPTER 5 CONTROL STATEMENTS When we run a program, the statements are executed in the order in which they appear in the program. Also each statement is executed only once. But in many cases we may need a statement or a set of statements to be executed a fixed no of times or until a condition is satisfied. Also we may want to skip some statements based on testinga condition. For all these we use control statements. Control statements are of two types ~ branching and looping. BRANCHING Itis to execute one of several possible options depending on the outcome of a logical test, which is carried at some particular point within a program. LOOPING It is to execute a group of instructions repeatedly, a fixed number of times or until a specified condition is. satisfied. BRANCHING 1. if else statement Itis used to carry out one of the two possible actions depending on the outcome ofa logical test. The else portion is optional. The syntax is If (expression) statement! [if there is no else part] Or If (expression) Statement 1 else Statement 2 Here expression isa logical expression enclosed in parenthesis. If expression is true, statement 1 or statement 2 is a group of statements, they are written as a block using the braces {} Example: 1. if(x=90) printf(‘\n excellent”); else if(mark>=80) printf(“\n very good”); else if{mark>=70) printf(“\n good”); else if(mark>=60) printf(“\n average”); else printf(“\n to be improved”); SWITCH STATEMENT It is used to execute a particular group of statements to be chosen from several available options. The selection is based on the current value of an expression with the switch statement. The syntax is: switch(expression) { 21case value]: sl breal case value 2: s2 break; default: sn All the option are embedded in the two braces { }. Within the block each group is written after the label case followed by the value of the expression and a colon. Each group ends with ‘break’ statement. The last. may be labelled ‘default’, This is to avoid error and to execute the group of statements in default if the value of the expression does not match valuel, value2,....... LOOPING 1, The while statement This is to carry out a set of statements to be executed repeatedly until some condition is satisfied. The syntax is: While (expression) statement The statement is executed so long as the expression is true. Statement can be simple or compound. Example 1: #includecstdio.h> while(n > 0) i printf(“\n"); nen-1; } Example 2: #include main() C int while(x main() { intiel; do { Prinef(“%6d",i); +i; Jwhile(ic=10); J THE DIFFERENCE BETWEEN while loop AND do ~ while Joop 1) Inthe while loop the condition is tested in the beginning whereas in the other case itis ‘done at the end. 2)In while loop the statements in the loop are executed only if the condition is true. whereas in do- while loop even if the condition is not true the ‘statements are executed atleast once. 3. for loop Itis the most commonly used looping statement in C. The general form is For(expression expression2;expression3)statement Here expression! is to initialize some parameter that controls the looping action. expression2 is a condition and it must be true to carry out the action. expression3 isa unary expression er an assignment expression. Example: #includecstdio.h> main() { int & for(i=1sic=10;+4i) 23printf(“%d”,i); } Here the program prints istarting from 1 to 10-First iis assigned the value ? and then it checks whether iex10 If iis printed and then jis increased by one. Itcontinues until ic=10. An example for finding the average of 10 numbers. #include main() { int i: float x.avg-0; for(i=1si main() { int x, sum=0; intn=1; while(n #include main() { inti, j printf(“9d\n”, 2); 1 sqrt(i)) { printf(“%d\n”, i); break; } j } return 0; J Here while loop breaks if the mput for x is ~ve. The continue statement {tis used to bypass the remainder of the current pass through a loop. The loop does not terminate when Continue statement is encountered, but statements after continue are skipped and proceeds to the next pass through the loop. j+1) Inthe above example of summing up the non negative numbers when a negative valu input, it breaks and the execution of the loop ends. Incase if we want to sum 10 nonnegative numbers, we ean use contin instead of break 25Example : #include main() { int x, sum=0, n=0; while(n main() { intn=1,x,sum=0; while(n int maximum (int x,int y) { intz; ze(x>ey) 2x5 return (2); } main() f inta,b,c; scanf("%d%d" &a,&b); c-maximum(a,b); printf(“\n maximum number=%d",¢); } FUNCTION PROTOTYPE Teisa common practice that all the function programs are written after the main() function. When they are accessed in the main program, an error of prototype function is shown by the compiler. It means the computer has no reference about the programmer defined functions, as they are accessed before the definition To overcome this, i.e to make the compiler aware that the declarations of the function referred at the calling point follow, a declaration is done in the beginning of the program immediately after the preprocessor statements, Such a declaration of function is called prototype declaration and the corresponding functions are called function prototypes. Example 1: #includecstdio.h> int maximum(int x,int y); main() { intabic; scanf(“%d%d” 8&a,&b); c=maximum(a,b); printf(“\n maximum number is : %d",c); } int maximum(int x, int y) { int 2; 302(x>=y) 2x :y; return(z); J Example 2: #includecstdio.h> void int factorial(int m); main() C intn; scanf{"%d”,&n); factorial(n); J Void int factorial(int m) { Printf(“\n factorial of Md is %d “.m,p); return( ); J Note: In the prototype decleration of function, ifit return no value, in the place: Of data-type we use void, Eg: void maximum(int x,int ys Passing arguments to a function ‘he values are passed tothe function pireram through the arguments. When a Value is passed toa function 8an argumentin the calling Statement, the value is copied into the formal argument ofthe function (may have the same name of the a-eus] mnbtment ofthe calling function) This Procedure of passing the value ie called passing by value. Even 'fformal argument changes in the fanction program, the value ofthe actual argument does not change, Example: #includecstdio,hs Void square (int x); main() { intx; scanf(“%d”, 8x); square(x): 313 void square(int x) { xox printf(*\n the square is 90d".»)s return; 3 In his program the value of xin the program is unaltered. RECURSION It is the process of calling a function by itself, until some specified condition is satisfied. It is used for repetitive computation (like nding factorial of anumbe) in ‘which each action isstated in term of previous result Example: #include Jong int factorial(int n): main() { int; Jongint ms scanf("4od” 8); mefactorial(n); printf(“\n factorial is 9d", m); 3 Jong int factorial(int m) { if(n long int Fibonacci (int count) main() 34{ int i, m=20; for (i=1 ;i main() C intx,i; float x{100],avg=0; 37printf(“\n the no: of values “); scanf(‘%d”,8n); prinef(‘\n Input the numbers’); for(i=1; { scanf(‘%of” Sofi); avg=avgtx{i}s } avgzavg/ni printf(“\n Average=%6f" avg); } PASSING ARRAYS TO FUNCTION Remember to passa value to a function we include the name ofthe variable asan argument of the function. Similarly an aray can be passed toa function by including army ‘name (without brackets) and size of the array as arguments. In the function defined the array name together with empty square brackets is an argument. =n;++i) Example: (calling function)-avg= average (n, x)s where nis the size of the data stored in the array x(]. (function defined)- float average (int n, float x{)s Now let us see to use a function program to calculate the average of aset of values. #includecstdio.h> float average(int n,float y{))s main() C intn; float x{100].avg: printf(“\n Input the no: of values"); scanf(“%d",&n); printf(‘\n Input the values”): for(i: scanf(“%6F" 8x{i)); avgeaverage(n.x)s jcens++i) print{("\n The average is %6f" ave): 38J float average(int n, float y(); { float sum=0; inti; for(i=l;ic=n;++i) sum=sum+yfi}; sum=sum/n; return(sum); J Note: #include void arrange(int n float x{}); arrange(n,x); J arrange(int n,float x{}); { return; } Problem: Write a program to arrange a set of numbers in ascending order by using a function Program with global declaration, 39MULTI-DIMENSIONAL ARRAYS Multi-dimensional arrays are defined in the same manner one dimensional arrays except that aseparate pair of square brackets is required to each subscript. Example: float matrix{20][20] (two dimensional) Int x{10}[10]{5] (@-dimensional) Initiating a wo dimensional array we doas int x int x(3)[4)= ((1.2,3.4}5 5.6.7.8); {89,10,11,1233 NOTE: The size of the subscripts is not essential for initialization. For reading a two dimensional array we use two for-loop. Example: for(j=1j main() { Struct biodata { Char name(30}; Char Place[40}] Intpin; Long Int phone; Char grade; k Struct biodata student{50}; Intn; Prinf(“\n no of students”); Scanf("%d".n); For(i= { Scanf{‘%s” student{i].name); Scanf(“%s" student{i).place); Scanf(‘%d" student{i.pin); Scanf{"9ld’ student{i].phone); Scanf{"%c"’student{i).grade); } } USER DEFINED DATA TYPE Thisis to define new data type equivalent to existing datatypes. Once defined a user-defined data type then new variables can be declared in terms ofthis new data type. For defining new data type we use the syntax typedef as follows Typedef type new-type Here type refers to existing data type ni++i) 44For example Example 1: ‘Typedef int integer; Now integer is a new type and using this type variable, array etc can be defined as Integer x; Integer mark(100]; Example 2: Typedef struct i Intaccno; Char name(30}; Float balance; record; Now record is structure type using this type declare customer, staffs record type Record customer; Record staff{100]; Passing structures to functions Mainly there are two methods by which structures can be transferced to and from a function. 1 . Transfer structure members individually 2.. Passing structures as pointers (ie by reference) Example 1 #includecstdio.h> Typedef struct { Int accno; Char name(30}; Float balance; Jrecord; main() { Record customer; 453 Float adjust(char name|], int accnumber, float bal) i Float x; Return(x); J Example 2 #includecstdio.h> Typedef struct { Intaccno; Char name{30}; Float balance; record; main() f Record customer; Void adjust(record “cust) Adjust(& customer); Printf("\n %s\t%f",coustomer.name,customer.balance) } Void adjust(record *cust) [ Float x; Cust->balance=... 46Im the first example structure members are passed individually where as in the second case customer is Passed entirely as a pointer named cust. The values of structure membersare accessed by using -> symbol like cust->name, cust->balance etc. UNIONS Union is a concept similar to a structure with the major difference in terms of storage. In the case of Structures each member has its own storage location, but a union may contain many members of different types but can handle only one ata time. Union is also defined as a structure is done bar using the syntax union, Union var f Intm; Charc; Float a; J Union var x; Now xisa union containing three members m.c.a But only one value can be stored eitherinx.m,xcorxa BITWISE OPEATIONS Bitwise operators operate on individual bits of integer (int and long) values. Thisis useful for writing low- level hardware or OS code where the ordinary abstractions of numbers, characters, pointers, and so on, are Biwise operators are: ~ Bitwise Negation one’s complement (unary) & Bitwise And | Bitwise Or \ Bitwise Exclusive Or > Right Shift by right hand side (RHS) (divide by power of 2) = ; 5. There are two Boolean values TRUE and FALSE. a Logical Operators. AND, OR, NOT aRelational Operators , 6. The following looping statements are employed. For, while and repeat-until While Loop: While ; ; For Loop: For variable= value-1 to value-2 ; ; J 55repeat-until: repeat ; ; until 7. Aconditional statement has the following forms. a If { :} a If { Else (3} Switch statement: Switch { Case : ; Case : ; Default : ; 8. Inputand output are done using the instructions read & write. 9. There is only one type of procedure: Algorithm, the heading takes the form, Algorithm Name (Parameter lists) a Asan example, the following algorithm fields & returns the maximum of n’ given numbers: 1. algorithm Max(A,n) 2. / Kisanarray of sizen 3 { 564. Result = A[1); 5. fork=2tondo 6. if A[I] > Result then 7. Result :=A[I}; 8 return Result; 9 3 In this algorithm (named Max), A & n are procedure parameters. Result & I are Lucal variables. Pseudocode for selection sort Algorithm Selection sort (B) { forp=1ton-1 { min x= Bip] forj=m+lton f If B[q] 0 a belongs to the class n* 4. x(a) =5nlogn +n x belongs to the class nlogn 5. x(n)=2+1/n x belongs to the class 1 Practical Complexities We have previously analyzed that we can obtain a different order of growth by means of constant multiple (CinC'f{n)). We used different types of notations for these orders of growth. But we do not restrict the classification of order of growth to &!, Tand O. There are various efficiency classes and each class possesses certain characteristic which is shown in table Growth | Name ofthe Explanation Example Order | Efficiency Class 1 Constant Specifies that algorithm?s running | Scanning the elements of array time is not changed with increase in size of the input logn | Logarithmic For each iteration of algorithm a _ | Performing the operations of constant factor shortens the binary search problem's size a Linear ‘Algorithms that examine thelist _| Performing the operations of of size n. sequential search nlogn | n-log-n Divide and conqueralgorithms. | Using merge sort or quick sort elements are sorted | nd Quadratic ‘Algorithms with twoembedded | Scanning the elements of matrix loops 3 Cubic Algorithms with three Executing matrix embedded loops. _| Multiplication an Exponential Algorithms that generate allthe _| Generatingall the subsets which are present inn subsets of n different — element sets elements nt Factorial Algorithmsthat generate all the | All the permutationsare generated permutations ofan n-element set 62