ZeePedia Add to Favourites   |   Contact us


Introduction to Programming

<<< Previous Arrays: Initialization of Arrays, Copying Arrays, Linear Search Next >>>
 
img
CS201 ­ Introduction to Programming
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
Introduction
Arrays
Initialization of Arrays
Sample Program 1
Copying Arrays
Linear Search
The Keyword `const'
Tips
Page 103
img
CS201 ­ Introduction to Programming
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
Page 104
img
CS201 ­ Introduction to Programming
Memory
24
C[0]
59
C[1]
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
Page 105
img
CS201 ­ Introduction to Programming
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.
Page 106
img
CS201 ­ Introduction to Programming
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:
Page 107
img
CS201 ­ Introduction to Programming
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;
do
{
int z , i = 0 ;
cout << "Please enter the number (-1 to end input) " << endl;
cin >> z ;
if ( z != -1 )
{
c[ i ] = z ;
Page 108
img
CS201 ­ Introduction to Programming
}
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
2
3
4
5
6
-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] ;
Page 109
img
CS201 ­ Introduction to Programming
......
......
......
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 ++ )
{
Page 110
img
CS201 ­ Introduction to Programming
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
1
2
3
4
5
6
7
8
9
10
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>
Page 111
img
CS201 ­ Introduction to Programming
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:
Page 112
img
CS201 ­ Introduction to Programming
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 " ;
}
Page 113
img
CS201 ­ Introduction to Programming
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];
Page 114
img
CS201 ­ Introduction to Programming
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
Page 115
Table of Contents:
  1. What is programming
  2. System Software, Application Software, C language
  3. C language: Variables, Data Types, Arithmetic Operators, Precedence of Operators
  4. C++: Examples of Expressions, Use of Operators
  5. Flow Charting, if/else structure, Logical Operators
  6. Repetition Structure (Loop), Overflow Condition, Infinite Loop, Properties of While loop, Flow Chart
  7. Do-While Statement, for Statement, Increment/decrement Operators
  8. Switch Statement, Break Statement, Continue Statement, Rules for structured Programming/Flow Charting
  9. Functions in C: Structure of a Function, Declaration and Definition of a Function
  10. Header Files, Scope of Identifiers, Functions, Call by Value, Call by Reference
  11. Arrays: Initialization of Arrays, Copying Arrays, Linear Search
  12. Character Arrays: Arrays Comparisonm, Sorting Arrays Searching arrays, Functions arrays, Multidimensional Arrays
  13. Array Manipulation, Real World Problem and Design Recipe
  14. Pointers: Declaration of Pointers, Bubble Sort Example, Pointers and Call By Reference
  15. Introduction, Relationship between Pointers and Arrays, Pointer Expressions and Arithmetic, Pointers Comparison, Pointer, String and Arrays
  16. Multi-dimensional Arrays, Pointers to Pointers, Command-line Arguments
  17. String Handling, String Manipulation Functions, Character Handling Functions, String Conversion Functions
  18. Files: Text File Handling, Output File Handling
  19. Sequential Access Files, Random Access Files, Setting the Position in a File, seekg() and tellg() Functions
  20. Structures, Declaration of a Structure, Initializing Structures, Functions and structures, Arrays of structures, sizeof operator
  21. Bit Manipulation Operators, AND Operator, OR Operator, Exclusive OR Operator, NOT Operator Bit Flags Masking Unsigned Integers
  22. Bitwise Manipulation and Assignment Operator, Programming Constructs
  23. Pre-processor, include directive, define directive, Other Preprocessor Directives, Macros
  24. Dynamic Memory Allocation, calloc, malloc, realloc Function, Dangling Pointers
  25. History of C/C++, Structured Programming, Default Function Arguments
  26. Classes and Objects, Structure of a class, Constructor
  27. Classes And Objects, Types of Constructors, Utility Functions, Destructors
  28. Memory Allocation in C++, Operator and Classes, Structures, Function in C++,
  29. Declaration of Friend Functions, Friend Classes
  30. Difference Between References and Pointers, Dangling References
  31. Operator Overloading, Non-member Operator Functions
  32. Overloading Minus Operator, Operators with Date Class, Unary Operators
  33. Assignment Operator, Self Assignmentm, Pointer, Conversions
  34. Dynamic Arrays of Objects, Overloading new and delete Operators
  35. Source and Destination of streams, Formatted Input and Output, Buffered Input/Output
  36. Stream Manipulations, Manipulators, Non Parameterized Manipulators, Formatting Manipulation
  37. Overloading Insertion and Extraction Operators
  38. User Defined Manipulator, Static keyword, Static Objects
  39. Pointers, References, Call by Value, Call by Reference, Dynamic Memory Allocation
  40. Advantages of Objects as Class Members, Structures as Class Members
  41. Overloading Template Functions, Template Functions and Objects
  42. Class Templates and Nontype Parameters, Templates and Static Members
  43. Matrices, Design Recipe, Problem Analysis, Design Issues and Class Interface
  44. Matrix Constructor, Matrix Class, Utility Functions of Matrix, Input, Transpose Function
  45. Operator Functions: Assignment, Addition, Plus-equal, Overloaded Plus, Minus, Multiplication, Insertion and Extraction