C-programming-class 3

Session 03

Arrays, Strings and Functions

1

Session Objectives • • • • •

To learn about array declaration and manipulation To learn about matrix operation using two dimensional arrays To learn about string handling using arrays. To learn about functions and function declaration in C To about passing values to the functions

2

Session Topics • Accessing the array elements and array initialization • Single and multidimensional array • Strings and string variables: Reading and Printing a string • Functions in C and function definitions • Passing arguments to a function • Functions and arrays

3

Arrays • An array lets you declare and work with a collection of values of the same type. For example, you might want to create a collection of five integers. Example :int a, b, c, d, e; • Using arrays it could be declared as below. int a[5]; This reserves memory for an array that to hold five integer values • The five separate integers inside this array are accessed by an index. All arrays start at index 0 and go to (n-1) in C. For example: int a[5]; a[0] = 12; a[1] = 9; a[2] = 14; • You need to make a declaration before a[3] = 5; using an array and to specify its data type, a[4] = 1; its name and, in most cases

• Make sure the array has a valid name 4

Arrays • Arrays are storage structures in memory that can help store multiple data items having a common characteristic. • An array is referred to only by a single name, although they have multiple data items • The individual data items can be of any type, like integers, float or characters. • But inside one array, all the data items must be of a single type – If we have an array of 50 elements,all of them must be of integer type or of any one type – We cannot have the first 20 being integers while the rest are float type • Character arrays have a special property... • Each element of the array can hold one character. But if you end the array with the NULL CHARACTER, denoted by ‘\0’ (that is, backslash and zero), you'll have what is known as a STRING CONSTANT. The null character marks the end of a string 5

Initializing Arrays • •

You can assign values to the array in several ways this example demonstrates int main() { int arrayOfInts1[8] = {1, 2, 3, 4, 5, 6, 7, 8}; int arrayOfInts2[8]; int arrayOfInts3[] = {1,2,3,4,5, 6,7,8}; /* an unsized array */ int arrayOfInts4[10]; int i; arrayOfInts2[0] = 1; arrayOfInts2[1] = 2; arrayOfInts2[2] = 3; arrayOfInts2[3] = 4; arrayOfInts2[4] = 5; arrayOfInts2[5] = 6; arrayOfInts2[6] = 7; arrayOfInts2[7] = 8; for(i=0 ; i<8 ; i++) arrayOfInts4[i] = i + 1; return 0; }

6

Arrays • One of the feature about array indexing is that, you can use a loop to manipulate the index. For example, the following code initializes all of the values in the array to 0: int a[5]; int i; for (i=0; i<5; i++) a[i] = 0; • The following code initializes the values in the array sequentially and then prints them out: #include <stdio.h> int main() { int a[5], i; for (i=0; i<5; i++) a[i] = i; for (i=0; i<5; i++) printf("a[%d] = %d\n", i, a[i]); } 7

Multi-Dimensional Arrays • An array's DIMENSION is the number of indices required to reference an element. • For example, arrayOfInts[0] is the first element. The index is 0 there is only 1 index so arrayOfInts is one dimensional. • what about 2D? int array2D[3][5]; This tells the computer to reserve enough memory space for an array with 15, that is, 3 x 5 elements. • If you ever wanted to find out how much memory your arrays occupy (1D or multidimensional), you can use the sizeof() operator. 8

Example of a 2D Array main() { int t,i,num[3][4]; for(t=0;t<3;t++) for(i=0;i<4;++i) num[t][i]=(t * 4) + i + 1; for(t=0;t<3;t++) { for(i=0;i<4;++i) printf(“%3d ”,num[t][i]); printf(“\n”); } } 9

Memory Allocation of a 2D Array num[t][i]

0

1

2

3

1

2

3

4

1 5

6

7

8

2 9

10

11

12

0

10

3D Array •

A three dimensional array can be thought of as an array of arrays of arrays. • Example: static int [2][2][2]={ { {1,2}, {3,4} } { {5,6}, {7,8} } }

11

Memory Allocation of a 3D Array

0th 2-D Array

1

2

3

1st 2-D Array

4

5

6

7

8

12

An Introduction to Strings • Strings in C are an array of charecters terminated with a null character, '\0',. • This means that the length of a string is the number of characters it contains plus one to store the null character. •

Examples: char string_1 = "Hello"; char string_2[ ] = "Hello"; char string_3[6] = "Hello";

One can use the string format specifier, %s, to handle strings.

13

Reading Strings • One possible way to read in a string is by using scanf. However, the problem with this, is that if you were to enter a string which contains one or more spaces, scanf would finish reading when it reaches a space, or if return is pressed. • We could use the gets function... gets takes just one argument - a char pointer, or the name of a char array, but don't forget to declare the array / pointer variable first!  What's more, is that it automatically prints out a newline character, making the output a little neater

14

Writing Strings • Like with printf and scanf, if you want to use gets( ) and puts( ) you'd have to include the stdio.h header file. • puts( ) is similar to gets in the way that it takes one argument - a char pointer. This also automatically adds a newline character after printing out the string.

15

Strings: An Example #include <stdio.h> void main() { char array1[50],array2[]; printf("Now enter another string less than 50"); printf(" characters with spaces: \n"); gets(array1); printf("\nYou entered: "); puts(array1); printf("\nTry entering a string less than 50"); printf(" characters, with spaces: \n"); scanf("%s", array2); printf("\nYou entered: %s\n", array2); } 16

Output Now enter another string less than 50 characters with spaces: hello world You entered: hello world Try entering a string less than 50 characters, with spaces: hello world You entered: hello 17

String Functions defined in string.h • strlen(str)---Returns length of the string str. • strcpy(str1,str2)---Copies the string str2 to string str1. • strncpy(str1,str2,n)---Copies at most n charecters of string str2 to string str1. • strcat(str1,str2)---Append string str2 to string str1. • strncat(str1,str2,n)---Append first n charecters of string str2 in string str1. • strcmp(str1,str2)---Compare two strings str1 and str2.

18

String Functions defined in string.h • strstr(str1,str2)---Finds the occurrence of string str2 in string str1. • Strset(str1,c)---Sets all occurrence in str1 to the character identified by c. • strchr(str,c)---Scans the string str for the first occurrence of character c. • strrchr(str,c)---Find the last occurrence of the character c in string str. • strlwr(str)---Converts the string str to lowercase. • strupr(str)---Converts the string str to uppercase. • strrev(str)---Reverses the string str. 19

What are Functions? •

A function can be thought of as a mini-program, where you can pass in information, execute a group of statements and return an optional value.

•

A function is CALLED (or INVOKED) when you need to branch off from the program flow and execute the group of statements within that function. Once the statements in the function are executed, program flow resumes from the place where you called your function.

•

You've already encountered a few functions: main, printf and scanf.

•

The main function is special, in the way that it's called automatically when the program starts.

•

In C, and other programming languages, you can create your own functions.

20

Function Features Functions have 5 main features: 1. The DATA TYPE is the data type of the RETURN VALUE of the function. 2. The NAME is required as an identifier to the function, so that the computer knows which function is called. Naming of functions follows the same set of rules as the naming of variables. 3. Functions can take ARGUMENTS - a function might need extra information for it to work. Arguments are optional. 4. The function BODY is surrounded by curly brackets and contains the statements of the function. 5. The RETURN VALUE is the value that is passed back to the main program. Functions exit whenever you return a value. If the function does not return a value, we put the void keyword before the function name. 21

Why “Functions”? •

Allows a large program to be broken down into smaller, manageable, self contained parts

•

Allows for modularization of a complex task

•

Functions are the only way in which modularization can be achieved in C

•

Avoids the need for repeated programming of the same instructions needed by various programs or parts of a program

•

Decomposition of a large program through functions enhances logical clarity

•

Programmers may build their own set of functions in a customized library

•

Writing programs using functions allows the separation of machine dependent portions from others, enhancing portability of programs

22

Defining Functions • Every function in C has the form type name (argument list, // if any) { declarations, statements, and/or expressions }

• The set of arguments in a function header is optional. • Each argument is preceded by its type declaration data-type name (type arg1, type arg2, ...); • If a function does not take any inputs the header will have a function name followed by ( ). 23

The Function Body • The function body is a set of statements enclosed between { }. • These set of statements define the task carried out by the function. • This function body, like any other compound statement, can contain any type of statements – – – –

assignment statement compound statements function calls anything that is a valid statement

• The body must contain at least one return statement. • The return statement helps in passing the single value result back to the calling program. 24

The return Statement • The general form of the return statement is return (expression); • This contains the keyword return followed by an optional expression. • The value of the expression is returned to the calling part of the program. • Since an expression can result in only one value, a function can also return only one value. • If the expression is omitted, the return statement does not transfer any value to the calling program, but just transfers control to the calling program. • Such functions are defined as void. void functionName() { statements; return; }

25

The return Statement (Contd…) void functionName(int x, int y, int z) { if (x > y) { statements; return; else if (x > z) statements; return; }

• The above code fragment illustrates the use of return in void functions. • The return statement causes the calling program to start execution from the statement immediately following the function call. • A function body can contain one or more return statements.

26

Function Definition:An Example int max(int x, int y) { if (x >= y) return (x); else return (y); } • A function called max is defined that returns an int. • The function body is fairly simple as it just checks which of the variables in greater and returns that value 27

Invoking & Using Functions •

A function can be invoked by specifying the name of the function followed by the list of arguments separated by commas.

•

This is also called a call to the function or a function call.

•

If a function does not require any arguments, just write the name of the function with ( ) as in filler( );

•

The function call can happen in a simple expression or part of a complex expression.

•

The arguments in the function call are called as actual arguments.

•

The arguments used in the function definition are called as formal arguments.

•

There is a one-to-one match of the list and type of the formal arguments with the actual arguments.

•

The value of each actual parameter will be passed as input to the called function through the corresponding formal parameter.

•

We already made use of a function as

•

A function not returning anything can appear as a standalone statement such as printf(...);

return ((x * Y)/gcd(x,y));

28

Call by Value void some(int m,int n) { m=100;

Called function

n=200; } void main() { int a,b; a=10; b=20;

Calling function

some(a,b); printf(“a = %d and b = %d”,a,b);

}

29

Call by Value:Sequence of steps Start a=10

1000

a

10

b

1004 20

m n

2000 10 100

void some(m,n)

2004 20 200

m=100

b=20

some(a,b)

n=100

write a,b Stop

Calling Function

Called Function 30

Call by Value: Sequence of steps • • • • • • • • •

Execution starts from the calling function. After executing the statements a=10,b=20 the values of 10 and 20 will be copied into memory locations()(Assume 1000 and 1004). The function some() is invoked with two parameters a and b. The control is now transferred to the called function some(). Memory is allocated for the formal parameters m and n(Assume 2000 and 2004). When the statements m=100,n=200 are executed, the earlier values of 10 and 20 are replaced with 100 and 200. Control is transferred from the called function to the calling function to the point from where it has been invoked earlier. The copy of actual parameters(formal parameters) is changed and actual parameters are un-affected. Execution is stopped.

31

Call by Reference void some(int *m,int *n) {

Called function

*m=100; *n=200; } void main() { int a,b; a=10;

Calling function

b=20; some(&a,&b); printf(“ a = %d and b = %d”,a,b); }

32

Call by Reference:Sequence of steps Start

a

1000 10 100

m m

1004

a=10

b

20 200

nn

2000 1000

void some(m,n)

2004 2000 200

b=20

m=100

some(&a,&b)

n=100

write a,b Stop

Calling Function

Called Function 33

Call by Reference:Sequence of steps • • • • • • • • •

Execution starts from the calling function. After executing the statements a=10,b=20 the values of 10 and 20 will be copied into memory locations()(Assume 1000 and 1004). The function some() is invoked with two parameters a and b. The control is now transferred to the called function some(). Memory is allocated for the formal parameters m and n(Assume 2000 and 2004).Since the addresses are passed as parameters,these addresses are copied into the locations 2000 and 2004 respectively. When the statements *m=100,*n=200 the memory location pointed to be m i.e,the contents pointing to 1000 which in this case is 10 is replaced by 100. Control is transferred from the called function to the calling function to the point from where it has been invoked earlier. The actual parameters can be changed by formal parameters through pointers indirectly. Execution is stopped. 34

What is Recursion? •

Recursion is the name given for expressing anything in terms of itself. A function which contains a call to itself or a call to another function, which eventually causes the first function to be called is known as RECURSIVE FUNCTION. • Each time a function is called, a new set of local variables and formal parameters are allocated on the stack and execution starts from the beginning of the function using these new value. • The call to itself is repeated till a base condition is reached. Once a base condition or a terminal condition is reached, the function returns a result to the previous copy of the function. • A sequence of returns ensure that the solution to the original problem is obtained.

35

Case Study: Factorial of n Design Process The series can be multiplied pictorially as shown below: prod 1*

Recursive Technique

1 * 2 * 3 * …… n

1 Fact(n) =

prod

if n = 0

n * fact(n-1) otherwise

prod prod 36

Program to find the factorial of n int fact(int n) { if (n==0) return 1; /* 0! = 1 */ return n*fact(n-1); /* n!=n*(n-1)! */ } void main() { int n; printf(“Enter value for n\n”); scanf(“%d”,&n); printf(“The factorial of %d = %d\n”,n,fact(n)); }

37

Tower of Hanoi

RULES There are three towers. N gold disks, with decreasing sizes, placed on the source tower. You need to move all of the disks from the source tower to the destination tower. Larger disks can not be placed on top of smaller disks. The third tower can be used to temporarily hold disks. 38

Tower of Hanoi

AIM • To create an algorithm to solve this problem. • It is convenient to generalize the problem to “N-disk”.

SOLUTION • First we move the N-1 disks from first tower to third tower. • Then we move the Nth disk to the second tower. • Thirdly we move the N-1 disks from temporary tower to destination tower.

39

Tower of Hanoi

Source

Temporary

Destination

40

Tower of Hanoi (0,0,0)

41

Tower of Hanoi (0,0,1)

42

Tower of Hanoi (0,1,1)

43

Tower of Hanoi (0,1,0)

44

Tower of Hanoi (1,1,0)

45

Tower of Hanoi (1,1,1)

46

Tower of Hanoi (1,0,1)

47

Tower of Hanoi (1,0,0)

48

Advantages and Disadvantages of Recursion Advantages Clearer and simple versions of algorithms can be created. Recursive definition can be easily transferred into a recursive function.

Disadvantages Separate copy of the function variables are created for each call and definitely consumes lot of memory. Most of the time is spent in pushing and popping the necessary items from the stack and so consumes more time to compute the result. They often execute slowly when compared to their iterative counterpart because of the overhead of the repeated function calls. 49

Iteration v/s Recursion Iteration Uses repetition structures such as for,while loops. It is counter controlled and the body of the loop terminates when the termination condition is failed. They execute much faster and occupy less memory and can be designed easily.

Recursion Uses selection structures such as if-else,switch statements. It is terminated when a base condition.The terminal condition is gradually reached by invocation of the same function repeatedly. It is expensive in terms of processor time and memory usage. 50

Summary • An array lets you declare and work with a collection of values of the same type. • One of the feature about array indexing is that, you can use a loop to manipulate the index. • A three dimensional array can be thought of as an array of arrays of arrays. • Strings in C are an array of charecters terminated with a null character, '\0',. • A function can be thought of as a mini-program, where you can pass in information, execute a group of statements and return an optional value. • Recursion is the name given for expressing anything in terms of itself. A function which contains a call to itself or a call to another function. 51

Thank You!

52