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 12 Video



Lecture Handout
  Introduction to Programming
  Lecture No. 12
  Reading Material
  Deitel & Deitel - C++ How to Program    chapter 4 
  4.4, 4.5, 4.6, 4.8, 4.9
   Summary
    Character Arrays
    Initialization Of Character Arrays
    Arrays Comparison
    Sorting Arrays
 
    Functions And arrays
 
    Multidimensional Arrays
    Example 2
    Tips

  Character Arrays
  While dealing with words and sentences, we actually make use of character arrays. Up to
  now, we were dealing with integer arrays and storing integer values. Here we have to see
  what needs to be done for storing a name. A simple variable can't be used to store a name
  (which is a string of characters) as a variable stores only a single character. We need a
  character array to grab a name. A character array is not different from an integer array.
  To declare a character array, we will write as under:
  char name [100] ;
  In this way, we declare a string or character array. There are some special properties of
  character arrays. Suppose that we declare an array of 100 characters. We enter a name
  with 15-20 characters. These characters in the array occupy 15-20 character spaces. Now
  we have to see what has happened to the remaining character spaces in the array.
  Similarly, a question arises, will an array displayed on the screen, show 100 characters
  with a name in 15-20 spaces and blanks for the remaining. Here C has a character
  handling capability i.e. the notion of strings. When we place a string in a character array,
  the computer keeps a mark to identify that the array was of this size while the string
  stored in it is of the other size. That marker is a special character, called nullcharacter.
  The ASCII code of   nullcharacter is all zeros. In C language, we represent the   null
  character as “\0”. C uses this character to terminate a string. All strings are terminated
  with the null character. 
  Now, we will see how the character arrays are stored in memory. While declaring a
  character array, we normally declare its size larger than the required one. By using a
  character array, it becomes easy to store a string.  We declare a character array as under.
  char name [100] ;
  Now we can store a string in this array simply by using the cinstatement in the following
  way.
  cin >> name ;
  In the above statement, there is an array on right hand side of   cin instead of a simple
  variable. The cin stream has a built-in intelligence that allows the compiler (program) to
  read whole string at a time rather than a single character as in case of simple variable of
  type char. The compiler determines that the name is not a simple variable. Rather it is a
  string or character array. Thus cin reads a character array until the user presses the enter
  key. When enter key is pressed, cin takes the whole input (i.e. string) and stores it into the
  array name. The C language, by itself, attaches a nullcharacter at the end of the string. In
  this way, the total number of spaces occupied in the array by the string is the number of
  characters entered by the user plus 1 (this one character is the nullcharacter inserted at
  the end of the string by C automatically). The nullcharacter is used to determine where
  the populated area of the array has ended. If we put a string larger than the size of the
  array in absence of a   nullcharacter in it, then it is not possible to determine where a
  string is terminated in the memory. This can cause severe logical error. So, one should be
  careful while declaring a character array. The size of array should be one more than the
  number of characters you want to store. 
  Initialization Of Character Arrays 
  Now we will look into integer array initialization process that can provide a list of integer
  values separated by commas and enclosed in curly braces. Following is the statement
  through which we initialize an integer array.
  int age [5] = {12, 13, 16, 13, 14};
  If we don’t mention the size of the array and assign a list of values to the array, the
  compiler itself generates an array of the size according the number of values in the list.
  Thus, the statement    int age [] = {14, 15, 13}; will allocate a memory to the array of size
  3 integers. These things also apply to character arrays as well. We can initialize an array
  by giving a list of characters of the string, the way we assign integer values in integer
  array. We write the characters of this string one by one in single quotes (as we write a
  single character in single quotes), separated by commas and enclosed in curly braces. So
  the initialization line will be as under 
  char name [100] = {‘i’, ‘m’, ‘r’, ‘a’, ‘n’};
  we can also write the string on right hand side in double quotes as 
  char name [100] = “imran” ;
  The easy way to initialize a character array is to assign it a string in double quotes. We
  can skip the size of the array in the square brackets. We know that the compiler allocates
  the memory at the declaration time, which is used during the execution of the program. In
  this case, the compiler will allocate the memory to the array of size equal to the number
  of characters in the provided string plus 1 (1 is for the nullcharacter that is inserted at the
  end of string). Thus it is a better to initialize an array in the following way.
  char name [] = “Hello World” ;
  In the above statement, a memory of 12 characters will be allocated to the array name as
  there are 11 characters in double quotes (space character after Hello is also considered
  and counted)  while the twelfth is the null character inserted automatically at the end of
  the string. 
  We can do many interesting things with arrays. Let’s start with reading a string (for
  example your name) from keyboard and displaying it on the screen. For this purpose, we
  can write the following code segment
  char name [100] ;
  cout << “Please enter your name :   “ ;
  cin >> name ;
  In the cin statement,  when the user presses the enter key the previous characters entered,
  that is a string will be stored in the array name. Now we have a string in the array name.
  We can display it with cout statement. To display the string, we have stored in name. We
  can write as under 
  cout << name ;
  This will display the string. Alternatively, we can use a loop to display the string. As the
  string is an array of characters, we can display these characters one by one in a 'forloop'.
  We can write a loop as under
  for ( i = 0 ; i < 100 ; i ++ ) 
  cout << name [ i ] ;
  Thus this loop will display the characters in the array one by one in each iteration. First, it
  will display the character at name [0], followed by that at name [1] and so on. Here we
  know that the string in the array is terminated by a   null character and after this   null
  character, there are random values that may not be characters (some garbage data) in the
  array. We don’t want to display the garbage data that is in the array after this   null
  character. While using the statement cout << name; the coutstream takes the characters
  of the array name up to the nullcharacter and the remaining part of the array is ignored.
  When we are displaying the characters one by one, it is necessary to stop the displaying
  process at the end of a string (which means when null character is reached). For this
  purpose, we may put a condition in the loop to terminate the loop when the null character
  is reached. So we can use   ifstatement in the loop to check the   null character. We can
  modify the above for loop so that it could terminate when null character reaches in the
  array. 
  for ( i = 0 ; i < 100 ; i ++ ) 
  {     if (name [ i ] == ‘\0’)
  break ;
  cout << name [ i ] ;
  }
  Here a while loop can also be used instead of a  'for loop'.
  Arrays Comparison
  We can use this character-by-character manipulation of the array to compare the
  characters of two arrays of the same size. Two arrays can be equal only when first of all
  their sizes are equal. Afterwards, we compare the values of the two arrays with one to one
  correspondence. If all the values in the first array are equal to the corresponding values of
  the second array, then both the arrays will be equal. Suppose, we have two integer arrays
  num1 and num2 of size 100 each and want to find whether both arrays are equal. For this
  purpose, we will declare a flag and set it to zero, that means that arrays are not equal this
  time. For this flag, we write   int equals = 0 ;
  To compare the values of the arrays one by one, we write a for loop i.e.  for ( i = 0 ; i <
  100 ; i ++ ). In the body of the for loop, we use an ifstatement to check the values. In the
  if statement, we use the not equal operator ( != ). The advantage of using not-equal
  operator is that in case if the values at some position are not equal to each other, then we
  need not to compare the remaining values. We terminate the loop here and say that the
  arrays are not equal. If the values at a position are equal, we continue to compare the next
  values. If all the values are found same, we set the flag equal to 1 and display the results
  that both the arrays are identical. The same criterion applies to character arrays. The
  comparison of character arrays is very common. While finding a name in a database, we
  will compare two character arrays (strings). The comparison of two strings is so common
  in programming that C has a function in its library to manipulate it. We will discuss it
  later in the lecture on string handling. For the time being, we will write our own function
  to find the equality of two strings.  
  Following is the code of a program, which takes two arrays of 5 numbers from the user
  and compares them for equality.
  // This program takes two arrays of 5 integers from user 
  //displays them and after comparing them displays the result
  # include <iostream.h>
  main ( )
  {
  int num1 [5], num2 [5], i, equals = 0 ;
  // input of 5 integers of first array
  cout << “Please enter five integers for the first array” << endl ;
  for ( i = 0 ; i < 5 ; i ++)
  cin >> num1 [ i ] ;
  // input of 5 integers of 2nd array
  cout << “Please enter five integers for the second array” << endl ;
  for ( i = 0 ; i < 5 ; i ++)
  cin >> num2 [ i ] ;
  //display the elements of two arrays
  cout << “\n The values in the first array are  :   “ ;
  for ( i = 0 ; i < 5 ; i ++)
  cout << “\t” << num1 [ i ] ;
  cout << “\n The values in the second array are :   “ ;
  for ( i = 0 ; i < 5 ; i ++)
  cout << “\t” << num2 [ i ];
  // compare the two arrays 
  for ( i = 0 ; i < 5 ; i ++ )
  {   if ( num1 [ i ]  != num2 [ i ] )
  {
  cout << “\n The arrays are not equal “ ;
  equals = 0 ;   //set the flag to false
  break ;
  }
  equals = 1;   //set flag to true
  }
  if (equals)
  cout << “\n Both arrays are equal” ;
  }
  Similarly, we can write a program that compares two strings (character arrays) of the
  same size. While comparing strings, a point to remember is that C language is case-
  sensitive. In C-language ‘A’ is not equal to ‘a’. Similarly, the string “AZMAT” is not
  equal to the string “azmat” or “Azmat”. 
  A sample out-put of the program is given below.
  Please enter five integers for the first array  
  1
  3
  5
  7
  9
  Please enter five integers for the second array
  1
  3
  4
  5
  6
  The values in the first array are :   1    3   5   7   9
  The values in the first array are :   1    3   4   5   6
  The arrays are not equal
  Sorting
  We want to sort an array in ascending order. There may be many ways to sort an array.
  Suppose we have an array of 100 numbers. To sort it in ascending order, we start from
  the first number (number at zero index ) and find the smallest number in the array.
  Suppose, we find it at sixteenth position (index 15). If we assign this number directly to
  the first position, the number already placed at first position will be over written. But we
  want that number should exist in the array. For this purpose, we use a technique called
  swapping. In this technique, we swap two values with each other. For this purpose, we
  declare a variable and assign the value of first variable to this variable before assigning
  the second number (i.e. to be swapped) to the first variable. Then we assign the value of
  second variable to the first variable. Afterwards, the number, which we have stored in a
  separate third variable (that is actually the value of first variable) is assigned to the
  second variable. In arrays, the single element of an array is treated as a single variable so
  we can swap two numbers of an array with each other with this technique. 
  In our sorting process, we declare a variable   x and assign it the number at the first
  position. Then assign the number at sixteenth position to the first position. After this,  we
  assign the number in x (that is actually the number that was at first position in the array)
  to the sixteenth position. In programming, this can be done in the following fashion.
  x = num [0] ;        // assign number at first position to x
  num [0] = num [15] ; // assign number at sixteenth position to first
  position
  num [15] = x ;    // assign number in x to sixteenth position 
  We have the smallest number at the first position. Now we start reading the array from
  second position (index 1) and find the smallest number. We swap this number with the
  second position before starting from index 2. The same process can be repeated later. We
  continue this process of finding smallest number and swapping it till we reach the last
  number of the array. The sorting of array in this way is a brute force and a very tedious
  work. The computer will do fine with small arrays. The large arrays may slow it down.
  Searching
  The same applies to the search algorithms. For finding out a particular number in an
  array, we can use technique of linear search. In this technique, there may be as many
  comparisons as numbers in the array. We make comparison of the number to be found
  with each number in the array and find it out if it matches any number in the array.
  However, we can perform even better by using a binary search algorithm.
  Binary Search Algorithm
  In binary search algorithm, the ‘divide and conquer’ strategy is applied. This algorithm
  applies only to sorted arrays in ascending or descending order. Suppose that we want to
  search a number in an ascending array. For this purpose, we divide the array into two
  parts (say left and right). We compare the target value with the value at middle location
  of the array. If it does not match, we see whether it is greater or less than the middle
  value. If it is greater than the middle value, we discard the left part of the array. Being an
  ascending array, the left part contains the smaller numbers than the middle. Our target
  number is greater than the middle number. Therefore, it will be in the right part of the
  array. Now we have a sub-array, which is the half of the actual array (right side portion of
  main array). Now we divide this array into two parts and check the target value. If target
  value is not found, we discard a portion of the array according to the result whether target
  value is greater or less than the middle value. In each iteration of testing the target value,
  we get an array that is half of the previous array. Thus, we find the target value.
  The binary search is more efficient than the linear search. In binary search, each iteration
  reduces the search by a factor of two (as we reduce to half array in each iteration). For
  example, if we have an array of 1000 elements, the linear search could require 1000
  iterations. The binary search would not require more than 10. If an array has elements 2n,
  then the maximum number of iterations required by binary search will be n. If there are
  1000 elements (i.e. 210, actually it will 1024), the number of iterations would not be more
  than 10.
  Functions and Arrays 
  In C language, the default mechanism of calling a function is ‘call by value’. When we
  call a function, say   fn, and pass it a parameter   x(argument value) by writing statement
  fn(x), the calling mechanism puts the value of   x at some other place. Then calls the
  function and gives this value to it. This means a copy of the value is sent to the program.
  The original   xremains untouched and unchanged at its place. The function uses the
  passed value (that has placed at some other place) and manipulates it in its own way.
  When the control goes back to the calling program, the value of original x is found intact.
  This is the call by value mechanism. 
  Now let’s see what happens when we pass an array to a function. To pass an array to a
  function, we will tell the function two things about the array i.e. the name of the array and
  the size. The size of the array is necessary to pass to the function. As the array is declared
  in the calling function, it is visible there. The calling function knows its size but the
  function being called does not know the size of the array. So it is necessary to pass the
  size of the array along with its name. Suppose we have declared a character array in the
  program by the following statement:
  char name[50] ;
  We have a function (say   reverse, you should write it as an exercise) that reverses the
  array elements and displays them. 
  Firstly, we need to write the prototype of the function reverse. We say that this function
  returns nothing so we use the keyword void in its return type. Secondly, we have to write
  the parameters this function will get. We write these parameters with their type.
  Now the prototype of this function will be written as 
  void reverse ( char [], int ) ;  
  In the above statement, the brackets [] are necessary. These brackets indicate that an array
  of type char will be passed to the function. If we skip these brackets and simply write
  char, it will mean that a single character will be passed to the function. In addition, the
  second parameter i.e. of type   int, is of array's size. Note that in the prototype of the
  function we have not written the names of the parameters. It is not necessary to write the
  names of the parameters in function prototype. However, if we write the names, it is not
  an error. The compiler will simply ignore these names.
  Now we will define the function reverse. In the function's definition, we will use the
  array and variable names. These names are local to this function so we can give these
  variables a name other than the one used in declaration in the calling program. We write
  this as below.
  void reverse ( char characters [], int arraySize )
  {
  // The body of the function. 
    Here, the body of the function is left over for an exercise.
  Let’s say we have a character array name and a name ‘adnan’ is stored in it. We call the
  reverse function by passing the array name to it. For this we write    reverse ( name, 100 );
  In this  function call, we are sending the name of the array to the function i.e. name and
  the size of the array that is 100. When this call of the function is executed the control
  goes to the function reverse. The statements in this function are executed which reverses
  the array and displays it. After this, the control comes back to the main function to the
  statement next to the function call statement. The return type of the function is void so it
  does not return any thing. Now in the main, we write the statement cout << name; What
  will be displayed by this statement? Whether it will be the original name ‘adnan’ or
  something else. It will display the reversed array. In this instance, we see that whatever
  the function   reverse did to the array ( that was passed to it) is appearing in the calling
  function. It means that the original array in the calling program has been changed. Here
  we change (reverse) the order of the characters of array in the function and find that the
  characters of the array in the calling function are reversed. This means that the called
  function has not a copy of the array but has the original array itself. Whereas in case of
  simple variables, a called function uses a copy of variables passed to it in a 'call by value'
  mechanism, which is by default in case of simple variables. In arrays, the by default
  mechanism is ‘call by reference’.  While passing arrays to a function, we don’t need to
  use & and * operators, as we use for variables in call by reference mechanism. 
  Thus if we pass an array to a function, the array itself is passed to the function. This is
  due to the fact that when we declare an array, the name of the array has the address of the
  memory location from where the array starts. In other words, it is the address of the first
  element of the array. Thus the name of the array actually represents the address of the
  first location of the array. Passing the name of array to a function means the passing of
  the address of the array which is exactly the same as we do in   call by reference. So
  whatever the function does to the array, it is happening in the same memory locations
  where the array originally resides. In this way, any modifications that the function does to
  the contents of the array are taking place in the contents of the original array too. This
  means that any change to the array made by the function will be reflected in the calling
  program. Thus an important point to remember is that whenever we pass simple variables
  to a function, the default mechanism is call by value and whenever we pass an array to a
  function, the default mechanism is call by reference. We know that when we talk about a
  single element of an array like x [3] (which means the fourth element of the array x), it is
  treated as simple variable. So if we pass a single element of an array to a function (let’s
  say like fn ( x [3] ); ), it is just like a simple variable whose copy is passed to the function
  (as it is a call by value). The original value of the element in the array remains the same.
  So be careful while passing arrays and a single element of array to functions. This can be
  well understood from the following examples.
  Example 1
  Suppose we declare an array in the main program and pass this array to a function, which
  populates it with values. After the function call, we display the elements of the array and
   see that it contains the values that were given in the function call. This demonstrates that
  the called function changes the original array passed to it.
  Following is the code of the program.
  //This program demonstrates that when an array is passed to a function then it is a call by
  //reference and the changes made by the function effects the original array   
  # include <iostream.h>
  void getvalues( int [], int) ;
  main ( )
  {
  int num [10], i ;
  getvalues ( num, 10) ; //function call, passing array num
  //display the values of the array
  cout << “\n The array is populated with values \n” ;
  for ( i = 0 ; i < 10 ; i ++)
  cout << " num[" << i << "] = " << num[i]<< endl ;
  }
  void getvalues ( int num[], int arraysize)
  {
  int i ;
  for ( i = 0 ; i < arraysize ; i ++) 
    num[i] = i ;
   }
  Here in the function getvalues, we can get the values of the array from user by using the
  cin statement.
  Following is the output of the execution of the program.
  The array is populated with values
  num[0] = 0
  num[1] = 1
  num[2] = 2
  num[3] = 3
  num[4] = 4
  num[5] = 5
  num[6] = 6
  num[7] = 7
  num[8] = 8
  num[9] = 9 
  Multidimensional Arrays
  There may be many applications of arrays in daily life. In mathematics, there are many
  applications of arrays. Let’s talk about vectors. A vector is a set of values which have
  independent coordinates. There may be two-dimensional vector or three-dimensional
  vector. There are dot and cross products of vectors besides many other manipulations.
  We do all the manipulations using arrays. We manipulate the arrays with loops. Then
  there is a mathematical structure matrix, which is in rows and columns. These rows and
  columns are manipulated in two-dimensional arrays. To work with rows and columns, C
  provides a structure i.e. a two-dimensional array. A two dimensional array can be
  declared by putting two sets of brackets [] with the name of array. The first bracket
  represents the number of rows while the second one depicts the number of columns. So
  we can declare an array numbers of two rows and three columns as follows.
  int numbers [2] [3] ;
  Using two-dimensional arrays, we can do the addition, multiplication and other
  manipulations of matrices. A value in a two-dimensional array is accessed by using the
  row number and column number. To put values in a two-dimensional array is different
  from the one-dimensional array. In one-dimensional array, we use a single 'forloop' to
  populate the array while nested loops are used to populate the two-dimensional array. 
  We can do addition, multiplication and other manipulations of two-dimensional arrays. In
  C language, we can declare arrays of any number of dimensions (i.e. 1, 2, 3 … n ). We
  declare a n-dimensional array by putting n pair of brackets [] after the name of the array.
  So a three-dimensional array with values of dimensions 3, 5 and 7 respectively, will be
  declared as int num [3] [5] [7] ;
  Example 2
  Let’s have a matrix (two-dimensional array) of two rows and three columns. We want to
  fill it with values from the user and to display them in two rows and three columns.
  Solution
  To solve this problem, we use a two-dimensional array of two rows and three columns.
  First, we will declare the array by writing
  int matrix [2] [3] ;
  We declare different variables in our program. To put the values in the array, we use two
  nested forloops, which can be written as under.
  for ( row =  0 ; row < maxrows ; row ++ )
  {
  for ( col = 0 ; col < maxcols ; col ++)
  {
  cout << “Please enter a value for position [“ << row << “, ” << col << ”]” ;
  cin >> matrix [row] [col] ;
 
  }
  The inner   for loop totals the elements of the array one row at a time. It fills all the
  columns of a row. The outer for loop increments the row after each iteration. In the above
  code segment, the inner loop executes for each iteration of the outer loop. Thus, when the
  outer loop starts with the value of   row 0, the inner loop is executed for a number of
  iterations equal to the number of columns i.e. 3 in our program. Thus the first row is
  completed for the three columns with positions [0,0], [0,1] and [0,2]. Then the outer loop
  increments the   rowvariable to 1 and the inner loop is again executed which completes
  the second row (i.e. the positions [1,0], [1,1] and [1,2] ). All the values of matrix having
  two rows and three columns are found.
  Similarly, to display these values one by one, we again use nested loops.  
  Following is the code of the program.
  //This program takes values from user to fill a two-dimensional array (matrix) having two
  //rows and three columns. And then displays these values in row column format. 
  # include <iostream.h>
  main ( )
  {
  int matrix [2] [3], row, col, maxrows = 2, maxcols = 3 ;
  // get values for the matrix
  for ( row = 0 ; row < maxrows ; row ++)
  {
  for (col = 0 ; col < maxcols ; col ++)
  {
  cout << “Please enter a value for position [“ << row << “, ” << col << ”]  ” ;
  cin >> matrix [row] [col] ; 
  }
  }
  // Display the values of matrix
  cout << “The values entered for the matrix are “ << endl ;
  for ( row = 0 ; row < maxrows ; row ++)
  {
  for (col = 0 ; col < maxcols ; col ++)
  {
  cout << “\t” << matrix [row] [col] ; 
  }
  cout << endl ;  //to start a new line for the next row
  }
  }
  Please enter a value for position [0,0]   1
  Please enter a value for position [0,1]   2
  Please enter a value for position [0,2]   3
  Please enter a value for position [1,0]   4
  Please enter a value for position [1,1]   5
  Please enter a value for position [1,2]   6
  The values entered for the matrix are
  1   2   3
  4   5   6
  Tips
    A character array can be initialized using a string literal
    Individual characters in a string stored in an array can be accessed directly           
  using array subscript
    Arrays are passed to functions by reference
    To pass an array to a function, the name of the array(without any brackets)
  is passed along with its size
    To receive an array, the function’s parameter list must specify that an
  array will be received
    Including variable names in function prototype is unnecessary. The
  compiler ignores these names.