Computer Science - C++

 

STUDENT OUTLINE

Lesson 16 - Single Dimension Arrays

(apvector class)

 

NOTES:                                  The APCS Development Committee has developed five standard classes to be used in your AP course:  apvector, apmatrix, apstring, apstack, and apqueue.  There are several reasons for this standardization.

 

                                                1)   The ANSI standard classes are broad, full-featured classes which would require too much time to cover in depth.  Several software companies provide standard classes such as Hewlett-Packard's Standard Template Library (STL) and Microsoft's Foundation Classes.  The AP classes are subsets of the STL classes and any code students write should be compatible with STL classes.  Programs which compile with the apclasses should compile using the STL classes after making minor modifications.  The tools provided in the apclasses are sufficient to solve most of the problems students will encounter in a high school APCS course or a freshman university course. 

 

                                                2)   The built-in arrays of C and C++ are not range-checked.  If you access an array location beyond the boundaries of the memory allocated for the array, the results are unpredictable (usually bad).  The apvector class includes range-checking.

 

                                                                        http://www.collegeboard.org 

                                               

                                                Each class implementation has a header file and a source code file.  For example, the two files which support the apvector class are called apvector.h and apvector.cpp.

 

                                                apvector.h -    contains the implementation of the apvector class. 

 

                                                apvector.cpp - contains the specifications and the class definition.

 

                                                Both A and AB course students need to learn the apclasses as abstractions.  They need to know how to use an apclass without knowing its implementation.

 

                                                The lesson includes three handouts.  Here is the purpose of each:

 

                                                Handout H.A.16.1, apvector class

      Provides the specifications of the apvector class.

 

Handout H.A.16.2, Example Program • Arrays as Parameters

      A lengthy but important example program which illustrates various issues about passing arrays as parameters.  It is a very important handout to work through.

 

Handout H.A.16.3, Programming Pointers , Lesson 16

      Summarizes important syntax and software engineering issues about using the apvector class.

 

                                                Preparation of data files:           

 

                                                Lab exercise L.A.16.1, Statistics, can use the same data file used in L.A.14.2, numbers.txt.

 

                                                Lab exercise L.A.16.2, Compact, requires the use of a text file of integers.  Here is a suggested file of 20 integers which tests the boundary cases of the compact algorithm.

 

                                                0  6  13  0  0  75  33  0  0  0  4  29  21  0  86  0  32  66  0  0

 

INTRODUCTION:               Programs often need a way to work with large amounts of data without declaring thousands of scalar variables.  In this lesson we explain the terms data structure and algorithm, and then introduce you to a very important data structure, the array.  With each new data structure comes the complementary algorithms to manipulate the data it stores.  This combination of data structures and algorithms provide the powerful tools needed to solve computer science problems.

 

The key topics for this lesson are:

 

A.  Data Structures and Algorithms

B.   Example of an Array

C.  apvector Declarations and Memory Allocation

D.  Applications of Arrays

E.   Passing Arrays as Parameters

F.   Arrays and Algorithms

 

VOCABULARY:                   DATA STRUCTURE              ALGORITHM

                                                TRAVERSAL                          ARRAY

                                                SEQUENTIAL                        RANDOM ACCESS

INDEX                                    VECTOR

 

 

DISCUSSION:                       A.  Data Structures and Algorithms

 

1.   A scalar type is a simple data type which holds one value at a time.  The data types int, double, char, and bool are important and useful, but limited.

 

2.   A data structure is a collection of scalar data types which are all referenced or accessed through one identifier.

 

3.   Data structures can be created to store information about any real-world situation:

a.   Your high school transcript is a collection of grades.

b.   The English paper you wrote on a word processor is stored as a collection of characters, punctuation, and formatting codes.

c.   Your name, address, and phone number can be stored as a collection of strings.

 

4.   After defining a data structure, algorithms will be needed to solve the specific problems associated with such a data structure.

 

5.   One example of a data structure is an array.  An array will store a list of values.

 

6.   An algorithm is a sequence of programmed steps which solves a specific problem.

 

7.   The fundamental algorithms which apply to an array data structure are:  insertion, deletion, traversal, searching, and sorting.

 

8.   The terms array and apvector refer to the same category of data structure and will be used interchangeably.

 

 

B.   Example of an Array

 

1.   The following program will introduce you to some of the syntax and usage of the apvector class in C++:

 

Program 16-1

 

#include <iostream.h>

#include <iomanip.h>

#include <apvector.h>

 

main ()

{

apvector<int>  A(6);    //  an array of 6 integers

int  loop;

 

for  (loop=0; loop<6; loop++)

        A[loop] = loop * loop;

cout << "The contents of array A are:" << endl << endl;

for (loop=0; loop<6; loop++)

        cout << setw(5) << A[loop];

cout << endl;

return 0;

}

 

 

Run output:

 

The contents of array A are:

 

    0    1    4    9   16   25

 

 

2.   An array is a linear data structure composed of adjacent memory locations each holding values of the same type.

 

     

 

3.   The variable A is an array, a group of 6 related scalar values.  There are six locations in this array referenced by index positions 0 to 5.  It might seem odd to begin a list at position 0 instead of position 1.  The reason for this notation in C++ is the behind-the-scenes use of pointers and offsets.  This material will not be covered in the curriculum guide.

 

4.   The variable "loop" is used in a for loop to reference index positions 0 through 5.  The square of each index position is stored in the memory location occupied by each cell of the array. The syntax for accessing a memory location of an array requires the use of square brackets [].

 

5.   The square brackets [] are collectively an operator in C++.  They are similar to the parentheses as they have the highest level of precedence compared to all other operators.

 

6.   You may recall from your mathematics courses that one-dimensional arrays are also known as "vectors."

 

 

C.  apvector Declarations and Memory Allocation

 

1.   The apvectors are declared by stating the data type stored in the array, the name of the array, and the size of the array.  The size of the array must be of integer type.

 

      apvector<int>   list(6);

      apvector<double>   data(1000);

      apvector<char>  line(80);

 

2.   The size of an array can be defined by using a const value. 

 

      const  int

            MAX = 200;

 

      apvector<int>  num(MAX);

 

3.   When an array is declared, enough memory is allocated to set up the full size of the array.  For example, the array of int as described above, apvector<int>  list(6), will require 12 bytes of memory (2 bytes per cell).

 

4.   The apvector class supports resizing of an array.  After the array has been declared and allocated, the array can be resized larger or smaller depending on the current needs of the program.  The built-in arrays of C++ cannot be resized, an important difference between standard arrays and the apvector class.  However, be aware that resizing of an apvector does involve lots of copying of data.

 

See Handout H.A.16.1, apvector Class.

5.   The standard apvector class provides different types of constructors and member functions.  See Handout H.A.16.1, apvector Class, for examples. 

 

 

D.  Application of Arrays

 

1.   Suppose we have a text file of integer data (votes.txt) which contains all the votes cast in an election.  This election happened to have three candidates and the values in the integer file range from 1-3.

 

      Program 16-2

 

#include <iostream.h>

#include <fstream.h>

#include <apvector.h>

 

main ()

{

        ifstream  infile("votes.txt",ios::in);

        int  vote, total=0, loop;

        apvector<int> data(4,0);    // sized to 4 boxes, initialized to 0's

 

        while (infile >> vote)

        {

                data[vote]++;

                total++;

        }

        cout << "Total # of votes = " << total << endl;

        for (loop=1; loop<=3; loop++)

                cout << "Votes for #" << loop << " = " << data[loop] << endl;

        return 0;

}

 

a.   The array data consists of four cells, each holding an integer amount.  The first cell, data[0], is allocated but not used in this problem.  We could have stored the information for candidate 1 in position 0, candidate 2 in position 1, and so forth, but the code is easier to follow if we can use a direct correspondence.

 

       

 

b.   The value of vote is used to increment the appropriate cell of the array by +1.

 

2.   A second example counts the occurrence of each alphabet letter in a text file.

 

      Program 16-3

 

#include <iostream.h>

#include <fstream.h>

#include <apvector.h>

 

/* The array used will be allocated from 0..26.  Position 0 will

        not be used.  Position 1 counts a's, 2 counts b's, etc. */

 

main ()

{

        ifstream  infile ("sample.txt",ios::in);

        apvector<int>  letters(27,0);      // use positions 1..26 to count letters

        char  c1;

        int   loop, total = 0;

 

        while (infile >> c1)

        {

                if ('A'<=c1 && c1<='Z')  // if c1 is an upper case letter

                        c1 = c1 + 32;         // change c1 to lower case version

                if ('a'<=c1 && c1<='z')  // if we have a letter...

                {

                        letters[c1-96]++;  // if c1 == 'a', 97-96 = 1, etc.

                        total++;

                }

        }

        cout << "Count letters" << endl << endl;

        c1 = 'a'

        for (loop=1; loop<=26; loop++)

        {

                cout << c1 << " : " << letters[loop] << endl;

                c1++;

        }

        cout << endl << "Total letters = " << total << endl;

        return 0;

}

 

a.   Each character in the text file is read into c1.  If c1 is an uppercase letter it is converted to its lowercase counterpart.

b.   If the character is a letter, the ASCII value of the letter is adjusted to fit the range from 1-26.  For example, if c1 == 'a', the program solves 97 - 96 = 1.  Then the appropriate cell of the array is incremented by one.

c.   Again, position 0 in the array is not used to make the data processing easier.

 

 

E.   Passing Arrays as Parameters

 

See Handout H.A.16.2, Example Program • Arrays as Parameters.

1.   The program in Handout, H.A.16.2, will provide examples of passing arrays as parameters.  Notice that a global integer constant of 6 is used to size the array in this program. 

 

2.   The main  function declares an apvector named data.  The apvector is initialized with the values 0..5 inside function main.

 

3.   Function printList is declared with a const reference parameter.  This means that the local identifier list is an alias for the array data in function main.  No extra memory is allocated and no data needs to be copied.  The keyword const protects the parameter from any changes.  If any program statement attempts to modify the array the compiler will reject such code.  We gain the space and time efficiency of reference parameters with the data protection of a const parameter.

 

4.   Function squareList uses a reference parameter to an array.  This works just like passing a reference to an int or a double value.  Any local reference to array list inside function squareList is an alias for the array data inside function main.  Notice that after the call of squareList, the values stored in array data in function main have been permanently changed.

 

5.   When function rotateList is called, the copy constructor of the apvector class is invoked and the local array list is created as a copy of the array data in function main.  For C and C++ programmers who have used built-in arrays, passing arrays using the apvector class behaves differently.  Here is the distinction:

 

a.   When an apvector is passed as a value parameter, the copy constructor is invoked and a local apvector is created as a copy of the apvector parameter passed to the function.

b.   For built-in arrays in C and C++, arrays are pass­ed as reference parameters.  The function would receive the starting address of the array passed to the function.  This is dangerous as the function is working with the one and only copy of the array in memory.

 

6.   The function rotateList rotates the values one cell to the right, with the last value moved to the front of the list.  A call to printList is made inside the function rotateList just before leaving the function.  After returning to function main, notice that the array data is unchanged.  This illustrates that the value parameter used in function rotateList protects the actual parameter (array data in function main) from any changes.

 

 

F.   Arrays and Algorithms

 

1.   Insertion is a standard problem that must be solved for all data structures.  Suppose an array had 10 values and an 11th value was to be added.  We are assuming the array can store at least 11 values.

 

a.   If we could place the new value at the end, there would be no problem.

b.   But if the new value must be inserted at the beginning of the list in position 0, the other 10 values must be moved one cell down the list.

 

2.   Deletion of a value creates an empty cell that probably must be dealt with.  The most likely solution after deleting a value, is to move all values which are to the right of the empty spot one cell to the left.

 

3.   A traversal of an array consists of visiting every cell location, probably in order.  The visit could involve printing out the array, initializing the array, finding the largest or smallest value in the array, etc.

 

4.   Sorting an array means to organize values in either ascending or descending order.  These algorithms will be covered in depth in future lessons.

 

5.   Searching an array means to find a specific value in the array.  There are several standard algorithms for searching an array.  These will be covered in future lessons.

 

Handout H.A.16.3, Programming Pointers , Lesson 16

 

 

SUMMARY/REVIEW:         Arrays are tremendously useful data structures and you will have many opportunities (lots of labs!) to program with them.  After spending a few days working with single dimension arrays, we will move on to multi-dimensional arrays (apmatrix class).

 

 

ASSIGNMENT:        Lab Exercise L.A.16.1, Statistics

Lab Exercise L.A.16.2, Compact