• We've seen how to store values as integers, characters, etc we refer to these as simple data types, i.e. containing just a single unit of data
• Often we have more complex data to store, containing information in multiple parts (such as a list of values)
• for these we create a data structure: i.e. a collection of simple data elements organized (by some set of rules) into a single more complex item. There are several common data structures we will consider, including:
  • arrays: form groups of data where all the data is of the same type, for example a list of 10 real numbers.
  • structs: form groups of data where the data might be of a variety of types but is all somehow logically related. For example, a "student record" might be composed of
    • a student name as an array of characters,
    • a student number as a long integer,
    • and the student's marks as an array of floats
  • classes: form groups of data of a variety of types plus functions that manipulate the data. For example, in addition to having a student record include student information shown above, we might also want to include an update function which somehow updates the students marks.
• Arrays and structs we will consider in csci160, we will introduce classes, but will not cover them in detail until csci161.

• An array stores a fixed number of data items, which are all of the same type, e.g. 20 reals, or 4 integers, etc.
• Think of the array as a row of boxes, each of which can hold one data item
• Suppose we want to record the rainfall each year for a century - we might use an array of 100 floats - one floating point value for each year
• Each `box' has a number associated with it, the first box being number 0, so for N data items the array positions are numbered 0 through N-1
• When we talk about an array we refer to the index as specifying which array position (box) we're looking at, and the contents as being the value stored there

• Generally, all the data items for an array are stored together in memory
• The compiler records what kind of data is stored in the array, how many data items the array can hold, and therefore how much space the array takes up
• Because of this, we have to specify in advance (i.e. in the source code, wherever we declare the array) exactly how many data items the array holds
• When we want to look at, say the contents of the 7th data item in array foo, we specify foo[6] (remember the numbering starts at 0)
  • The compiler determines where the array starts (say memory address 4000, though as programmers we rarely need to know the specific address),
    it also knows how many bytes of memory each data item takes up (e.g. 4 for an integer),
    Thus when computing how to look up foo[6] to get to data item 7 we go to memory at address 4000 + 6*4 = 4024
  • The good news is that all the memory details are taken care of for you, all you need to work with are the index positions (e.g. 6)

• Declaring an array variable:
  <datatype> <arrayname> [ <size> ];
  the size must be an integer or a constant - it cannot be a variable or an expression involving variables. The reason for this is that the compiler has to figure out how much space to allocate for the array at compile time - i.e. well before the program is ever executed, and hence well before there is ever a value in a variable.

  To confuse the issue a bit, some compilers (g++ being one of them) actually let you get away with declaring variable-sized arrays, as an extension of C (where this was allowed). If you are trying to create quality portable code you should stick with constants.

• Example: an array, called foo, of 30 characters:

   char foo[30]; 

• Example: using a constant for an array of 12 floats:

  const int SIZE = 12;
  int main()
  {
     float myarray[SIZE];
  }
  

• If there is a particular kind of array you would like to use over and over, we can make a type definition:

  #include <cstdio>
  
  // mystring will describe a type of array,
  //    consisting of 80 characters
  const int SIZE = 80;
  typedef char mystring[SIZE];
  
  int main()
  {
      // declare two variables of type mystring,
      // i.e. two character arrays of size 80
      mystring  firststring, anotherstring;
  }
  

• To specify the contents of array position i, we use the syntax myarray[i]
• This can be used anywhere a variable of the same type could be used, e.g.:

    int myarray[25];
    int x, y, z;
  
    myarray[12] = 99;
    myarray[8] = 0;
    x = myarray[12];
    myarray[23] = x + myarray[8] * 3;
  

• The index values can be specific integers, integer variables, or expressions which evaluate to integers, e.g.:

     int x = 0;       
     int myarray[20];    // an array of 20 integers
  
     myarray[0] = 17;    // store 17 in position 0
     x = myarray[0];     // x is assigned 17
     myarray[x] = 3;    // store 3 in position 17
     myarray[x-3] = 0;  // store 0 in position 14
  
     myarray[1] = myarray[0];  
          // copy 17 from position 0 to position 1
  

• We will often wish to apply some form of processing to a series of elements of an array (e.g. print out the array contents, or update each array element)
• Loops are a natural way to do this, the for loop in particular
• Example: go through the first 10 elements of an array and set the contents of each element to be the square of the index

  for (int index = 0; index < 9; index++) {
      myarray[index] = index * index;
  }
  

• Example: myarray holds a list of numbers, use a for loop to check if any of the numbers are negative:

  int myarray[SIZE];
  bool neg_flag = false;
  
  for (int index = 0; index < SIZE; index++) {
      if (myarray[index] < 0) neg_flag = true;
  }
  
  printf("The array did ");
  if (!neg_flag) printf("not ");
  printf("hold negative numbers\n");
  

• Like all data, we must be sure to initialise the contents of arrays before using them
• The best habit to get into is to quickly initialise all the contents of all arrays, e.g.

  #include <cstdio> 
  
  const int INTSIZE = 20;
  const int FLOATSIZE = 32;
  const int CHARSIZE = 80;
  
  typedef int   intarray[INTSIZE];
  typedef float floatarray[FLOATSIZE];
  typedef char  chararray[CHARSIZE];
  
  int main()
  {
     intarray   myints;
     floatarray myfloats;
     chararray  mychars;
  
     for (int index = 0; index < INTSIZE; index++) 
         myints[index] = 0;
     for (int index = 0; index < FLOATSIZE; index++) 
         myfloats[index] = 0.0;
     for (int index = 0; index < CHARSIZE; index++) 
         mychars[index] = ' ';
   
     // and on with the rest of the program      
  }
  

• One of the most common needs is to print out the contents of an array

  for (int i = 0; i < SIZE; i++) {
     printf("%d ", myarray[i]);
  }
  

• Note you have to print things out one element at a time, things like printf("%f", myarray); (usually) won't work and can have really weird results
• For data structures like arrays, structs, and classes we generally have to write code to print out their contents
• It's useful to have an array-printing function, e.g.:

  int main() {
     float myarray[30];
     // do whatever to create array values
     // and now print it out:
     print_float_array(myarray, 30);
  }
  
  void print_float_array(float arr[], int size) {
     for (int i = 0; i < size; i++) {
         printf("%f ", arr[i]);
     }
     printf("\n");
  }
  

• There are two types of array access: sequential, and random
• Sequential access is when we consider a series of array elements in order (as we've done with initialising, printing, searching, etc)
• Random access is when we use the array elements in non-sequential order, e.g.:

    myarray[3] = 17;
    x = myarray[12] + myarray[z]
  

• Arrays are very flexible in terms of the types of data items they can hold, as long as the compiler knows the size of a type of data item we can create an array of that type.
• Common simple data items include bool, int, float, and char

  const int SIZE = 80;
  
  int main() {
     bool boolarray[SIZE];
     int     intarray[SIZE];
     float   floatarray[SIZE];
     char    chararray[SIZE];
  
     for (int index = 0; index < SIZE; index++) {
         boolarray[index] = false;
         intarray[index] = 0;
         floatarray[index] = 0.0;
         chararray[index] = ' ';
     }
  }
  

• Text in C++ is generally recorded as arrays of characters, and is a special case for input and output

• Forgetting to initialize array contents
  (as discussed earlier)
• Forgetting to print one element at a time
  (also as discussed earlier)
• Forgetting the N indices go 0..N-1, not 1..N
• Off-by-one errors For example initializing elements 0..49 then trying to print 0..50, most commonly occurs with loops (e.g. using < instead of <= or vice versa)
• Going outside the array boundaries:

  int myarray[50];
  ...
  myarray[93] = 7; 
  

  If the program doesn't immediately crash it will still probably screw up other program data, another cause of really weird behaviour

• Using pass-by-value, or pass-by-reference you can pass an array element anytime it has the correct data type for the function.

  In the example below, the functions expect a floating point value,
  and each array element contains a floating point value
  so we can pass an individual array element:

  void printfloat(float data);
  void incrementfloat(float &data);
  
  int main()
  {
     float  myfloats[5] = { 10, 20, 30, 40, 50 };
     printfloat(myfloats[3]);
     incrementfloat(myfloats[3]);
     printfloat(myfloats[3]);
  }
  
  void printfloat(float data)
  {
     printf("%f\n", data);
  }
  
  void incrementfloat(float &data)
  {
     data = data + 1;
  }
  

• To pass the entire array, or to change the contents of the array, by default they act like reference parameters, but we don't use the & in the parameter list. For example:

  void change(float arr[], int place, float newval);
  
  int main()
  {
     float thearray[SIZE];
     change(thearray, 3, 17.4);
  }
  
  void change(float arr[], int place, float newval)
  {
     arr[place] = newval;
  }
  

  Function change replaces the array value at position place with the newval. Here effectively thearray[3] = 17.5
• Note there is nothing inside the square brackets in the parameter list

void cannotChange(const float arr[], int val)
{
    // this function cannon alter the contents of the array parameter
}

• As pointed out in the earlier example, the parameter list in the function does not have a size recorded for the array
• This is good, in that at different times we can pass arrays of different sizes to the function
• Unfortunately, the function usually needs to know how big the array is (for error checking if nothing else)
• Solution: pass the array size as another parameter:

  void printarray(float arr[], int arrsize);
  
  int main()
  {
     float myarray[10];
     for (int index = 0; index < 10; index++) {
         myarray[index] = 0 - index;
     }
     printarray(arr, 10);
  }
  
  void printarray(float arr[], int arrsize)
  {
     for (int index = 0; index < arrsize; index++)
         printf("%f\n", arr[index]);
     }
  }
  

void fillarray(int array[], int size);

int main()
{
   int myarray1[20], myarray2[12];

   printf("Filling first array\n");
   fillarray(myarray1, 20);

   printf("Filling second array\n");
   fillarray(myarray2, 12);
}

void fillarray(int array[], int size)
{
   int numRead; // variable to track how many things scanf read
   int value;           // variable for converted value
   bool valid;       // recording validity of input

   for (int index = 0; index < size; index++) {
       // get and test input value
       valid = false;
       do {
          printf("Enter a positive integer\n");
          int numRead = scanf("%d", &value);
          if (numRead <= 0) {
             printf("sorry, invalid input\n");
          }
       } while (numRead <= 0);

       // assign to array once valid entry obtained
       array[index] = value;
   }
}

• Strings - i.e. sequences of characters - are widely needed in most applications (representing words, sentences, etc.)
• Most languages provide some mechanism for representing strings, the two most common are:
  • Fixed length: we give an integer, N, stating the length of the string, then provide the N characters
  • Null-terminated: we have a special character, the null, that signals the end of a string
• C and C++ use both when we choose to store text as arrays of characters

  const int STRINGSIZE = 80;
  typedef char mystring[STRINGSIZE];
  

  The value STRINGSIZE here tells us the longest string we can store However most string manipulation functions look for the null character, '\0', to tell them where the string actually ends.

• As mentioned, the null character, '\0', is used to indicate the end of a string
• This is the character with ascii value 0, i.e. char(0)
  (as an aside, the character with ascii value 17 can be denoted '\17', etc)
• We have to store the null character in addition to the part of the string we actually want to work with, so if you want to be able to use N characters in a string then you should declare your array size as N+1

  // Here we use a typedef to create our own group of arrays,
  //    used to represent names, and with a predefined fixed length
  //    of up to 20 characters for the name itself, so a 21-character array
  
  const int NAMESIZE = 21;
  typedef char name[NAMESIZE];
  
  int main()
  {
     // declare some name variables
     name firstname, lastname;
  

• usually we can only use scanf and printf to handle one array element at a time, - character arrays are the exception, e.g.:

  // here we use a typedef to create our own string type,
  //   again just an array of characters, with a fixed length
  const int STRINGSIZE = 81;
  typedef char MyStringType[STRINGSIZE];
  
  int main()
  {
     MyStringType text;
     printf("Enter a line of up to 80 characters\n");
     // we use fgets to read the text, telling it to read from stdin (standard input)
     fgets(text, STRINGSIZE-1, stdin);
     printf("The line you entered was\n");
     printf("%s", text);
  }
  

• As with most input, fgets doesn't take effect until the user hits enter.
• Cute trick: you can assign a value to a string variable at the point where you declare it (but no other time), e.g.
  MyStringType name = "Dave";

• We can use printf to print out an entire character array, as long as it is null terminated.
  printf("%s", arrayname);
• To print a single character at position i:
  printf("%c", arrayname[i]);
• To print the array contents from position i onwards:
  printf("%s", &(arrayname[i]));
• Remember that, unless we're printing a single character,
  printf will keep printing until it hits a null-terminator,
  even if this means it runs way past the end of the array and into other memory
• If you use fgets scanf("%80s", arrayname); // (the 80 is the char limit) the null terminator is automatically inserted. If you insert the characters into the array one at a time you must remember to put the null terminator in as well

The programmer may either specify the data is read from the keyboard (using the keyword stdin) or specify an open file pointer to use instead. (File pointers are discussed in the file io notes.)

A sample call would look like:
fgets(arrayName, maxSize, stdin);

(Note: this is NOT the same as the C++ string library and class.)

• strlen(char arr[])
  returns the length of the string
• strcat(char arr1[], char arr2[])
  appends the second string to the end of the first string
• strcpy(char arr1[], char arr2[])
  copies the second string into the first
• strncpy(char arr1[], char arr2[], int N)
  copies the first N characters of the second string into the first
• strcmp(char arr1[], char arr2[])
  compares the two strings, returns 0 if they are equal, non-zero otherwise
• strncmp(char arr1[], char arr2[], int N)
  as per strcmp but only compares the first N characters

• int atoi(char arr[])
  takes a string and converts it to an int
• long atof(char arr[])
  takes a string and converts it to a long
• double atof(char arr[])
  takes a string and converts it to a double

#include <cstdio>
#include <cstring>

const int SIZE = 81;
typedef char mystring[SIZE];

int main()
{
   mystring surname1, given1, whole1;  // names for person 1
   mystring surname2, given2, whole2;  // names for person 2

   printf( "Person 1: enter your given name\n");
   fgets(given1, SIZE-1, stdin);
   printf( "and now your surname (family name)\n");
   fgets(surname1, SIZE-1, stdin);

   printf( "Person 2: enter your given name\n");
   fgets(given2, SIZE-1, stdin);
   printf( "and now your surname (family name)\n");
   fgets(surname2, SIZE-1, stdin);

   // create whole names for each by copying given name
   // then appending the surname
   strcpy(whole1, given1);
   strcat(whole1, " ");
   strcat(whole1, surname1);

   strcpy(whole2, given2);
   strcat(whole2, " ");
   strcat(whole2, surname2);

   // print them in order of last name
   if (strcmp(surname1, surname2) < 0) {
      printf("%s\n%s\n", whole1, whole2);
   } else if (strcmp(surname1, surname2) > 0) {
      printf("%s\n%s\n", whole2, whole1);
   } else {
       printf("You have the same names!\n");
   }
}

• Suppose we ask the user to enter a number and instead they enter one or more characters
• To check this, see if the scanf succeeded, and throw away their input if not.

  #include <cstdio>
  #include <cstdlib>
  int main()
  {
     int myint;
    
     printf("Enter an integer\n"); 
     int numRead = scanf("%d", &myint);
   
     // see if (atoi returned 0), and 
     //        (user didn't actually enter value 0)  
     if (numRead == 0) {
        scanf("%*s");
        printf( "Invalid value entered\n");
     } else {
        printf("Valid value %d\n");
     }
  }
  

  Common errors with null-terminated character arrays

  • Filling a string one character at a time and forgetting the null terminator:
    • cstring routines won't work properly,
    • printf prints the string plus other rubbish
  • writing over top of null terminator (similar effects)
  • declaring an array that is too small to hold the strings you enter (will write overtop of other sections of memory)
  • confusing character operations with string operations e.g. single vs double quotes, or using
    printf("%s", array[x]); // instead of printf("%c", array[x]);
  • trying to assign a char array outside the declaration, e.g.

    char name[80];
    name = "Dave";
    

// assume gettext prompts a user to enter a paragraph
// with up to 1000 characters, and returns its size
//
// printcounts takes an array of 26 integers and
// prints out its contents

int main()
{
   char paragraph[1000];
   int alphacount[26];
   int textlength;

   textlength = gettext(paragraph, 1000);
   freqcount(paragraph, textlength, alphacount);
   printcounts(alphacount);
}

// freqcount records how often each letter of the alphabet
// appears in a character array. It stores the count for
// a,A in freq[0], the count for b,B in freq[1], etc

void freqcount(char text[], int size, int freq[])
{
   char nextchar;
   int asciival;

   // for each character in the block of text
   for (int index = 0; index < size; index++) {
       // get the next char and find its ascii value
       nextchar = text[index];
       asciival = int(nextchar);

       // 'A' to 'Z' have ascii values 65 to 90  
       if ((asciival >= 65) && (asciival <= 90)) {
          freq[asciival - 65] += 1;
       }
       // 'a' to 'z' have ascii values 97 to 122
       if ((asciival >= 97) && (asciival <= 122)) {
          freq[asciival - 97] += 1;
       }
   }
}

// brack_check takes an array of text which includes
// left and right curly brackets and checks to see
// if the brackets match up correctly
//
// we do this by scanning through the text and counting
// how many brackets are currently "open", incrementing
// the count by 1 each time we see { and decrementing
// the count by 1 each time we see }
//
// the text is invalid if either:
//   we encounter a } when the current count is 0
// or at the end of the text the current count is not 0
//
// brack_check returns true for valid layouts,
// false for invalid

bool brack_check(char text[], int size)
{
    int opencount = 0;

    for (int index = 0; index < size; index++) {

        if (text[index] == '{') opencount++;

        if (text[index] == '}') {
             if (opencount == 0) return(false);
             else opencount--;
        }
    }

    if (opencount != 0) return(false);
    else return(true);
}

• The arrays we have considered are called one-dimensional, they can be thought of as a single row of storage locations
• Sometimes it is useful to think of multiple dimensions of storage, such as a two-dimensional table of marks:

         Tutorial | Week 2 | Week 3 | Week 4 |
  Student         |        |        |        |
  ----------------+--------+--------+--------+
  Barney          |  0.001 | 0.05   | 1.5    |
  Homer           |  0.0   | 0.0    | 0.0    |
  Marge           |  1.5   | 1.5    | 1.0    |
  Moe             |  0.5   | 0.4    | 1.0    |
  ----------------+--------+--------+--------+
  

• We can create arrays organised in such a fashion (though the arrays only hold the data, not the headings)
• Most arrays are either 1-dimensional, 2-dimensional, or 3-dimensional since we can relate those to rows, tables, and physical space respectively
• You can, however, create as many dimensions as you like

• A 2D array stores data in rows and columns (e.g. a row for each student, and a column for each tutorial mark)
• The syntax is similar to one-dimensional arrays, but we use one set of square brackets for each dimension:
  e.g. myarray[row][col] = value;

  const int ROWS = 10;
  const int COLUMNS = 20;
  typedef float TwoDArray[ROWS][COLUMNS];
  
  int main()
  {
     TwoDArray  marktable;
  
     // initialise all values to 0.0
     for (int r = 0; r < ROWS; r++) {
         for (int c = 0; c < COLUMNS; c++) {
             marktable[r][c] = 0.0;
         }
     }
  
     // set the value for the third student's
     // second tutorial to 1.5
     marktable[2][1] = 1.5;
  
     // print out all the fifth student's marks:
     for (int c = 0; c < COLUMNS; c++) {
         printf("%f ", marktable[4][c]);
     }
     printf("\n");
  }
  

• Declare your array dimensions as const and use typedef to name the array types (else the compiler gets confused)
• Then parameter passing is easy
  (and like 1-D arrays is always pass-by-reference)

  const int Rows = 8;
  const int Cols = 8;
  typedef char Chessboard[Rows][Cols];
  
  void initialise(Chessboard game);
  
  int main()
  {
     Chessboard game1, game2;
  
     initialise(game1);
  }
  
  void initialise(Chessboard game)
  // sets the board positions to black or white
  {
     for (int r = 0; r < Rows; r++) {
         for (int c = 0; c < Cols; c++) {
             if ((r % 2) == (c % 2)) game[r][c] = '*';
             else game[r][c] = ' ';
         }
     }
  }
  

const int MAXSTUDENTS = 32;
const int MAXTUTES = 13;
typedef float Table[MAXSTUDENTS][MAXTUTES];

void readmarks(table grades, int students, int tutes);

int main()
{
   int numstudents, numtutes;
   Table grades98;

   // find out how many students and tutes
   printf("Enter the number of students and tutes\n");
   
   scanf("%d", &numstudents);
   scanf("%d", &numtries);

   // get the marks read in
   readmarks(grades98, numstudents, numtutes);
}

void readmarks(table grades, int students, int tutes)
{
   // go through each student
   for (int s = 0; s < students; s++) {

       // get all of that students marks
       for (int t = 0; t < tutes; t++) {

           // prompt the tutor and read the mark
           printf("Enter mark for student %d", s+1);
           printf(" tutorial %d\n", t+1);
           scanf("%f", &(grades[s][t]));

       }
   }
}

// representing a space as blocks of 1 cubic mile each,
// looking at a section 30 miles long, 10 high, and 50 wide
//
// Each array entry holds true if there is an asteroid
// in that cubic mile, false otherwise

const int Length = 30;
const int Height = 10;
const int Width = 50;

typedef bool Space[Length][Height][Width];

int main()
{
   Space region1;

   // initialise to no asteroids present
   for (int len = 0; len < Length; len++) {
       for (int hi = 0; hi < Height; hi++) {
           for (int wid = 0; wid < Width; wid++) {
               region1[len][hi][wid] = false;
           }
       }
   }

   // set asteroids in co-ordinates 
   // (0, 0, 0) and (12, 7, 43)
   region1[0][0][0] = true;
   region1[12][7][43] = true;
}