Source Code. Projects. Nerd Stuff. Art Stuff.

Lesson 5: Arrays

Arrays

Array – a series of variables that share a name and are referred to using their name and a number. e.g. int score[3] declares 3 integer variables: score[0], score[1], and score[2].

  • Individual variables can be called indexed variables, subscripted variables, or my favorite: elements
  • Number in brackets of declaration is size, and it must be a integer literal or constant.
  • Number in brackets when the array is used is the index (also called subscript). Integer literal, variable or constant can be used. When indexed in this way, we are referring to an individual variable (element) in the array.
  • Arrays can be of any base type, such as “char card[5]“
  • Arrays are stored in memory using consecutive memory addresses. If you refer to an index value out of range, say score[3], then that is a valid memory location, but will cause either a run-time or a logic error – potentially very elusive! Make sure to stay in bounds!
  • Array assignment must be done one element at a time. So you can’t write “score = 0;”
  • Example program: ArrayExp.cpp: Sample Array program.
  • Array elements can be passed as arguments to functions just like individual variables.
  • An entire array (array parameter) can also be passed as an argument to a function, if that function is declared with a corresponding array parameter. e.g.
    1
      void get_hours(int hours[], int num_employees);
  • When a whole array is passed, its contents may be changed. The array’s start address (location) is what�s passed by-value. The only way to prevent this possibility is with a const parameter, e.g.
    1
      void show_hours(const int hours[], int num_employees);
  • Notice also that any size array may be passed in for hours[].

    Summary of Parameter-Passing Mechanisms:

    • Call-by-Value – the default parameter-passing mechanism for all datatypes except for arrays. In this mechanism, the argument and the parameter occupy separate memory spaces, and the value of the argument is copied to give the parameter its initial value. This way, changes to the parameter’s value are local to the function, and don’t affect the argument. Example:
      1
         void displayValue(int x);
    • Call-by-Reference – specified by an & following the datatype. In this mechanism, the argument and the parameter use the same memory space. So changes to the parameter are changes to the argument as well. Example:
      1
         void getValues(int& x, int& y);
    • Array Parameters – the default parameter-passing mechanism for arrays. In this mechanism, the starting address of the array is passed by value, but the actual contents of the array aren’t duplicated (because that could take too much time and memory). The array referred to by the parameter is the same one in the same location as that referred to by the argument. So changes to the parameter array’s values are changes to the argument array’s values. Very similar behavior to call-by- reference. Example:
      1
         void getValues(int values[], int numVals);
    • Constant Array Parameters – the only way to get call-by-value – like behavior with array parameters. The const keyword is used to specify that the contents of the array parameter cannot be modified by the function. So any changes to the array in the function will generate compiler errors. Example:
      1
         void displayValues(const int values[], int numVals);

     

  • Sequential Search – go through array one by one until you find target, return index. Code for it is on page 598 (Sec. 10.3)
  • Example program: rem_char.cpp: Removes a specified character from an array of characters. Shows use of array parameters in functions. Also shows use of new_line() function to clear input stream.
  • There is a good example of how to build a complex program at beginning of Sec. 10.3 – read it.

Example array program – Design Process

Let’s write a program to delete all repeated characters from an array which the user enters. We’ll actually look at the code for the solution next time, but today let’s talk about its design. Let’s break it up into some subtasks:

  void delete_element(char a[], int del_idx, int& size);
  // deletes element with index del_idx from array a,
  // adjusting size accordingly.

  int second_occurrence(const char a[], int first_occ, int size);
  /* Precondition: a[first_occ] != a[x] for all x < first_occ.
     Returns the smallest int x > first_occ such that
     a[first_occ] == a[x], or -1 if a[first_occ] is unique.
     Algorithm is similar to sequential search.
  */

  void delete_second_occurrences(char a[], int first_occ, int& size);
  // Precondition: a[first_occ] != a[x] for all x < first_occ.
  // Deletes all repeats of the character a[first_occ] in array a,
  // adjusting size accordingly.

If we assume we can figure out how to write each of those somewhat simplified functions, then we can use them to write delete_repeats:

  void delete_repeats(char a[], int& size)
  {
    for(int idx=0; idx<size; idx++)
      delete_second_occurrences(a, idx, size);
  }

The complete program described above is available here.

Or there’s another way to approach this problem, if we can assume our array is made of only of letters: build an array of Booleans, one representing each letter (use ASCII character set in Appendix 3, p.958). A value of true in this array would mean we’ve already found the letter in our input array; false would mean we haven’t yet found it. Then we’d write the following functions:

  void delete_element(char a[], int del_idx, int& size);
  // (Same as above) deletes element with index del_idx
  // from array a, adjusting size accordingly.

  bool already_found(char ch, bool letters[]);
  // Returns true if ch�s numeric code is already true in the
  // letters array. Else sets ch�s flag to true and returns false.

  int char_to_num(char ch);
  // Returns the number corresponding to ch,
  // e.g. 0 for a, 1 for b, 2 for c, etc.
  // (int(ch) - int('a'))

Using those, here’s how delete_repeats would look:

  void delete_repeats(char a[], int& size)
  {
    int idx;
    bool letters[26];

    for(idx=0; idx<26; idx++) letters[idx] = false;
    for (idx=0; idx<size; idx++)
    {
      if (already_found(a[idx], letters))
        delete_element(a, idx, size);
    }
  }

 

Sorting

There are many different sorting algorithms, which you’ll study more if you continue on to CIS 110C or 110L, but today we’ll look at one program for sorting an array. The algorithm it uses is called Selection Sort. You can find this program here on my web siteor on pages 603-604 (Section 10.3). The diagram on p.601 may help you understand this program.