Our Recommendation for You Search your Query, You can find easily. for example search by book name or course name or any other which is related to your education

Followers

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 5thelement, 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 'forloop' 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;
  do
  {
  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 ifblock.
  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] ;
  ……
  ……
  ……
  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
  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>
  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