CS 201 Lecture No 11 Video

Lecture Handout

Introduction to Programming

Lecture No. 11

Reading Material

Deitel & Deitel - C++ How to Program chapter 4

4.2, 4.3, 4.4

Summary

•

• Arrays

• Initialization of Arrays

• Sample Program 1

• Copying Arrays

• Linear Search

• The Keyword ‘const’

• Tips

Introduction

We have started writing functions, which will become a part of our every program. As C

language is a function-oriented language, so we will be dealing with too many functions.

Our programming toolkit is almost complete but still a very important component is

missing. We are going to discuss this component i.e. Arrays in this lecture.

Let us consider an example about calculation of average age of 10 students. At first, we

will declare 10 variables to store the age of each student and then sum up all the ages and

divide this with 10 to get the average age. Suppose, we have 100 students instead of 10,

we have to declare 100 variables i.e. one for each student’s age. Is there any other way to

deal with this problem? Arrays are possible solution to the problem.

Array is a special data-type. If we have a collection of data of same type as in the case of

storage of ages of 100 students, arrays can be used. Arrays are data structure in which

identical data types are stored. The concept of arrays is being explained further in the

following parts of the lecture.

Arrays

In C language, every array has a data type i.e. name and size. Data type can be any valid

data type. The rules of variable naming convention apply to array names. The size of the

array tells how many elements are there in the array. The size of the array should be a

precise number. The arrays occupy the memory depending upon their size and have

contiguous area of memory. We can access the arrays using the array index.

Declaration:

The declaration of arrays is as follows:

data_type array_name [size] ;

for example:

int ages[10];

Let's consider an array int C[10]; This is an array of integer and has a name ’C'. It has a

size ten which depicts that the array ‘C’ can contain ten elements of int data type. In the

memory, the array occupies the contiguous area, in this case it will occupy forty bytes

(one int = 4 bytes). The elements of the array are manipulated using the index. In C

language, the index of array starts from zero and is one less than array's size. Index of

array is also called subscript.

Memory image of an array:

Name

C[0] 24

C[1] 59

C[2] 35

C[3] …

C[7]

C[8]

C[9]

Index

In the above figure, the memory chunk containing the array C is shown. On the first line,

C[0] is written while on the 2nd line, C[1] is written and so on. The number in the [ ] is

the index of the array. C[0] is used for the first element, followed by C[1] for the second

element and so on. It is important to note that in an array the index 6 ([6]) means the

seventh element of the array and thus the eighth element will have an index 7. Thus, the

index of the last element of the array will be 1 less than the size of the array. On the right

hand side, the values of the elements are shown in the memory i.e. the value of the

element at zero position ( C[0] ) is 24 while that of the element at first position ( C[1] ) is

59 and so on. The important thing to be noted here is that the indexing of the array starts

from zero, not from one. So in the above example, the index of the array C will be from

C[0] to C[9]. If we have an array of size 25, its index will be from 0 to 24.

Usage of Arrays

To declare arrays, we have to give their data type, name and size. These are fixed-size

arrays. In the coming lectures, we will discuss arrays without using size at declaration

time. Arrays may be declared with simple variables in a single line.

int i, age [10];

int height [10], length [10] ;

To access array, we can’t use the whole array at a time. We access arrays element by

element. An index (subscript) may be used to access the first element of the array. In this

case, to access first element we write like age[0]. To access the 5th element, we will write

age[4] and so on. Using the index mechanism, we can use the array elements as simple

variables. Their use can be anywhere where there we can use a simple variable i.e. in

assignment statements, expressions etc. Please do not confuse the usage of array and

declaration of array. When we write int age [10], it means we are declaring an array of

type int, its name is age and its size is 10. When we write age[5], it means we are

referring to the single element of the array not the whole array.

Consider the example of student’s ages again. Is there a way to calculate the average age

of all the students in an array?

As we know that arrays can be accessed with indexing. So we can use a 'for loop' as

under;

for (i = 0 ; i < 10 ; i++ )

{

cout << “Please enter the age of the student “;

cin >> age [i];

}

In the above 'for loop' the value of i is changing from 0 to 9. Here the loop condition is

i<10. This means that the cin and cout statements will be executed 10 times. We have

used i as the index of the array. The index we are referring to the array needs to be an

integer. It can be 4, 5 or an integer variable like i. In the first repetition, the value of i is 0,

i.e. age[0] so the value of first element of the age will be read. In the second repetition,

the value of i becomes 1 i.e. age[1] so the value of 2nd element of the age will be read and

so on. We get all the 10 values from the user which will be stored in the array age.

Now we will calculate the total of ages. We can use another 'for loop' to add up all the

elements of the array age.

int totalAge = 0;

for (i = 0 ; i < 10 ; i++ )

{

totalAge += age [i];

}

In the above loop, all the elements of the array age will be added to the variable totalAge.

When the value of i is 0 i.e. age[0] the value of first element will be added to the

totalAge. As the value of i is changing from 0 to 9 so all the 10 elements of the array will

be added to the totalAge. By dividing this totalAge by 10 we will get the average age.

Initialization of Arrays

There are many ways to initialize an array. Don't use the default initialization of arrays.

Compiler may assign some value to each declared array. Always initialize the array in

such a manner that the process is clear.

We can initialize an array using a 'loop' while assigning some value.

int i, age [10];

for ( i = 0; i < 10 ; i++ )

{

age[i] = 0;

}

With the help of this simple loop, we have initialized all the elements of array age to

zero. In the loop condition, we have used the condition i < 10, where the size of the array

is ten. As we know, the array index is one less than the size of the array. Here we are

using i as the index of array and its values are from 0 to 9.

We can also initialize the array at the time of declaration as:

int age [10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

The above statement creates an array age of integers and initializes all the elements with

zero. We can use any value to initialize the array by using any other number instead of

zero. However, generally, zero is used to initialize the integer variables.

We can do it by using the following shortcut.

int age [10] = { 0 };

The above statement has also initialized all the elements of the array to zero.

We have different ways of initializing the arrays. Initialization through the use of loop is

a better choice. If the size of the array gets larger, it is tedious to initialize at the

declaration time.

Consider the following statement:

int age [ ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

Here we have not mentioned the size of the array. The compiler is quite intelligent as it

detects the initialization list which consists of ten 0’s. Therefore, it creates an array of 10

integers and initializes all the elements with zero.

The index of the arrays starts from the index 0 and is up to one less than the size of the

array. So if the size of the array is ten, the index will be from 0 to 9. Similarly, if the size

of the array is 253, the index will be from 0 to 252.

Sample Program 1

Problem Statement:

Write a program which reads positive integers from the user and stores these ones in an

array. User can enter a maximum of 100 numbers. Stop taking input when user enters -1.

Solution:

We have to declare an integer array of size 100 to be used to store the integers. We used a

loop to get the input from the users. There are two conditions to terminate the loop i.e.

either user has entered 100 numbers or user entered -1. 'For' and 'while' loops can execute

zero or more times whereas ‘do-while’ may execute one or more times. By analyzing the

problem, the loop will be executed at least once so do-while loop logically fits in this

problem. We take an integer z to get the input from the user and i as the counter so the

condition will be as ( z != -1 && i < 100 ). && is used to enforce that both the

conditions are true. If any of the two conditions becomes false, the loop will be

terminated. The loop counter is less than 100 because the index of the array will be from

0 to 99.

We will read a number from the user and store it at some particular location of the array

unless user enters -1 or 100 numbers are entered. In the loop, we will use the if statement

whether the number entered by user is -1 or not. If the number entered is not -1, then we

will store it in the array. The index of the array will also be incremented in each

repetition. We can assign some value to array element as:

c[ 3 ] = 33;

In an assignment statement, we cannot use expression on the left hand side. Here c[3] is

used as a variable which represents the 4th element of the array.

The complete code of the program as under:

// This program reads the input from user and store it into an array and stop at -1.

#include <iostream.h>

main( )

{

int c [ 100 ] ;

int i, z;

{

int z , i = 0 ;

cout << “Please enter the number (-1 to end input) “ << endl;

cin >> z ;

if ( z != -1 )

{

c[ i ] = z ;

}

i ++ ;

} while ( z != -1 && i < 100 ) ;

cout << “ The total number of positive integers entered by user is “ << i -1;

}

The above code shows that the assignment statement of the array is inside the if block.

Here the numbers will be assigned to the array elements when the 'if statement' evaluates

to true. When the user enters -1, the if statement will evaluate it false. So the assignment

statement will not be executed and next i will be incremented. The condition in the 'while

loop' will be tested. As the value of z is -1, the loop will be terminated.

Now we have to calculate how many positive numbers, the user has entered. In the end,

we have incremented i so the actual positive integers entered by the users is i -1.

The above example is very useful in terms of its practical usage. Suppose we have to

calculate the ages of students of the class. If we don’t know the exact number of students

in the class, we can declare an array of integers of larger size and get the ages from the

user and use -1 to end the input from the user.

A sample out put of the program is as follow.

Please enter the number (-1 to end input) 1

-1

The total number of positive integers entered by user is 6

Copying Arrays

Sometimes, we need to copy an array. That means after copying, both the arrays will

contain elements with same values. For being copy able, both arrays need to be of same

data type and same size. Suppose, we have two arrays a and b and want to copy array a

into array b. Both arrays are of type int and of size 10.

int array a[10];

int array b[10];

We know that a value can be assigned to an element of array using the index. So we can

write assignment statements to copy these arrays as:

b[0] = a[0] ;

b[1] = a[1] ;

b[2] = a[2] ;

……

b[9] = a[9] ;

As the size of array is 10, its index will be from 0 to 9. Using the above technique, we

can copy one array to another. Now if the array size is 100 or 1000, this method can be

used. Is there some other way to do things in a better way? We can use the loop construct

to deal with this easily in the following way.

for (i = 0; i < 10 ; i ++)

{

b[i] = a[i];

}

With the help of loop, it becomes very simple. We are no more worried about the size of

the array. The same loop will work by just changing the condition. We are assigning the

corresponding values of array a into array b. The value of first element of array a is

assigned to the first element of array b and so on.

Example:

Take the sum of squares of 10 different numbers stored in an array.

Here is the code of the program:

// This program calculates the sum of squares of numbers stored in an array.

#include <iostream.h>

main()

{

int a[10];

int sumOfSquares = 0 ;

int i =0;

cout << "Please enter the ten numbers one by one " << endl;

// Getting the input from the user.

for (i = 0 ; i < 10 ; i++ )

{

cin >> a [i];

}

// Calculating the sum of squares.

for ( i = 0 ; i < 10 ; i ++ )

{

sumOfSquares = sumOfSquares + a[ i ] * a[ i ] ;

}

cout << “The sum of squares is “ << sumOfSquares << endl;

}

A sample out put of the program is given below.

Please enter the ten numbers one by one

The sum of squares is 385

Linear Search

Arrays are used to solve many problems. As we have seen that loops are used along with

the arrays, so these two constructs are very important. Suppose, we are given a list of

numbers to find out a specific number out of them. Is the number in the list or not? Let's

suppose that there are 100 numbers in the list. We take an array of size 100 as int a [100].

For populating it, , we can request the user to enter the numbers. Either these numbers

can be stored into the array or we can just populate it with numbers from 0 to 99. We can

write a simple loop and assign the values as a[i] = i. This means that at ith position, the

value is i i.e. ( a[5] = 5 ), at 5th position the value is 5 and so on. Then we can request the

user to enter any number and store this number into an int variable. To search this

number in the array, we write a loop and compare all the elements with the number. The

loop will be terminated, if we found the number or we have compared all the elements of

the array, which means that number is not found. We used a flag to show that we have

found the number or not. If the value of found is zero, the number is not found while the

value 1 will mean that number has been found. When we find the number, is there a need

to compare it with other elements of the array? May be not, so when we found the

number, we just jumped out of the loop. In the end, we check the variable found. If the

value is 1, it means number has been found. Otherwise number stands unfound.

Here is the complete code of the program.

// This program is used to find a number from the array.

#include <iostream.h>

main()

{

int z, i ;

int a [ 100 ] ;

// Initializing the array.

for ( i =0 ; i < 100 ; i ++ )

{

a [ i ] = i ;

}

cout << “ Please enter a positive integer “ ;

cin >> z ;

int found = 0 ;

// loop to search the number.

for ( i = 0 ; i < 100 ; i ++ )

{

if ( z == a [ i ] )

{

found = 1 ;

break ;

}

if ( found == 1 )

cout << “ We found the integer at index ” << i ;

else

cout << “ The number was not found ” ;

}

The following is an output of the program.

Please enter a positive integer 34

We found the integer at index 34

The loop in the above program may run 100 times or less. The loop will terminate if the

number is found before the 100th repetition. Therefore, in the linear search the maximum

limit of the loop execution is the size of the list. If the size of list is 100, then the loop can

execute a maximum of 100 times.

Using random function (Guessing Game):

We can turn this problem into an interesting game. If we as programmers do not know,

which number is stored in the array? We can make this a guessing game. How can we do

that? We need some mechanism by which the computer generates some number. In all

the C compilers, a random number generation function is provided. The function is

rand() and is in the standard library. To access this function, we need to include

<stdlib.h> library in our program. This function will return a random number. The

number can be between 0 and 32767. We can use this function as:

x = rand ( );

The random function generates an integer which is assigned to variable x. Let's consider

the function-calling mechanism. The program starts its execution in the main function.

When the control goes to the statement containing a function call, the main program stops

here and the control goes inside the function called. When the function completes or

returns some value, the control comes back to the main program.

Here is the complete code of the program using rand().

// This program is used to find a number from the array.

#include <iostream.h>

#include <stdlib.h>

main()

{

int z, i ;

int a [ 100 ] ;

// Initializing the array.

for ( i =0 ; i < 100 ; i ++ )

{

a [i] = rand() ;

}

cout << “ Please enter a positive integer “ ;

cin >> z ;

int found = 0 ;

// loop to search the number.

for ( i = 0 ; i < 100 ; i ++ )

{

if ( z == a [ i ] )

{

found = 1 ;

break ;

}

if ( found == 1 )

cout << “ We found the integer at position ” << i ;

else

cout << “ The number was not found ” ;

}

The following is an output of the program.

Please enter a positive integer 34

The number was not found

The function rand ( ) returns a value between 0 and 32767. Can we limit the generated

random number in a smaller range? Suppose we have a die with six faces marked with 1,

2, 3, 4, 5 and 6. We want to generate random die number i.e. the number should be

between 1 and 6 inclusive. Here we can use the modulus operator to achieve this.

Modulus operator returns the remainder. What will be the result of the statement?

rand ( ) % 6

When 6 divides any number, the remainder will always be less than 6. Therefore, the

result will be between 0 and 5 inclusive. We want the number between 1 and 6, therefore

we will add 1.

1 + rand ( ) % 6;

The above statement will give us the desired result. We need to know whether this is a

fair die or not. A fair die is a die when it is rolled 10 or 100 million of times. Then on

average, equal number of 1’s, equal number of 2’s, equal number of 3’s etc. will be

generated. Can we test our die i.e. it is fair or not? That is there are equal numbers of

chances of 1 or 2 etc. Think about generating a test for our random number generator.

Does it produce a fair die?

The random function is very useful. It can be used to guess the tossing of the coin. There

can be only two possibilities of tossing a coin. Therefore we can use rand ( ) % 2 which

will give 0 or 1.

The Keyword ‘const’:

To declare an array, we need its data type, name and size. We use simple integer for the

size like 10 or 100. While using arrays in loops, we use the size a lot. Suppose if we have

to change the size of the array from 10 to 100, it will have to be changed at all the places.

Missing a place will lead to unexpected results. There is another way to deal this situation

i.e. keyword construct. The keyword const can be used with any data type and is written

before the data type as:

const int arraySize = 100;

This statement creates an identifier arraySize and assigns it the value 100. Now the

arraySize is called integer constant. It is not a variable. We cannot change its value in the

program. In the array declaration, we can use this as:

int age [arraySize];

Now in the loop condition, we can write like this:

for ( i = 0; i < arraySize ; i ++)

If we have to change the size of the array, we only have to change the value of arraySize

where it is declared. The program will work fine in this case. This is a good programming

practice to use const for array size.

Tips

• Initialize the array explicitly

• Array index (subscript) starts from 0 and ends one less than the array size

• To copy an array, the size and data type of both arrays should be same

• Array subscript may be an integer or an integer expression

• Assigning another value to a const is a syntax error

Post a Comment

Post a Comment

About Us

Contact Form

CS 201 Lecture No 11 Video

You might like

Post a Comment

Post a Comment

Contact Form