CS 107 - 7/24/15

Null versus empty versus un-initialized

  Null/null/NULL is an empty memory address value (usually 0)

  empty differs based on the type of data

  empty can be "un-initialize" which is really just whatever
    bits value are in the memory location from the last time
    it was used.

  Data that is a collection of information (arrays, strings)
    can truly be empty.   The collection has zero elements


  The "empty string" is often typed in as ""


A C-style string is a character array that ends with the
  null character (ASCII value 0)

  "Hello" as a c-style string is: Hello\0


Open a file and check/verify to see if the file opened correctly

   ifstream is;

   cout << "Enter the name of a file to read data: ";

   // string fname;
   // cin >> fname;
   // is.open (fname.c_str(), ios::in);

   char fname2[80];
   cin >> fname2;
   is.open (fname2, ios::in);

   if ( is.fail() )
     {
      //cout << "Error: file \"" << fname << "\" did not open properly." << endl;
      cout << "Error: file \"" << fname2 << "\" did not open properly." << endl;
      return 1;
     }

In Boggle, assume we have an array with the list of valid words
  stored into it.

  How do we determine if the user entered a valid word?

    We need to search the array for the word entered by the user.


 One approach is the Linear search Algorithm

bool doesWordExist ( string wordList[], int wlsize, string target )
{
 int i;

 for ( i = 0 ; i < wlsize ; i++ )
    {
      if ( wordList[i] == target )
         return true;
    }

 return false;
}


  A better approach is Binary Search Algorithm 

    We divide the list into two parts, then check if the value we are
       searching for is in the first part or the second part.

  The binary search does require the values to be in sorted order.

  bool binarySearch ( string wordList[], int wlsize, string target )
   {
     int beginningPos = 0;           // start of the sub-list
     int endingPos = wlsize - 1;     // end of the sub-list
     int midPos;

     // while the sub-list is not empty
     while ( beginningPos <= endingPos )
       {
         midPos = (beginningPos + endingPos) / 2;

         // check to see if target is in the middle position
         if ( wordList[midPos] == target )
           {
              return true;
           }

         // determine if target is in front half
         if ( wordList[midPos] > target )
           { 
              endingPos = midPos - 1;
           }
         else
           {
              beginningPos = midPos + 1;
           }
       }

    // when the sub-list become empty - the value does not exist
    return false;
  }


Dynamic lists of values

    Dynamic Arrays

    So far, we have been using static sized (fixed sized) arrays.
  
    C++ has the operator called "new" to dynamically allocate memory

    In C, we used a library function called "malloc"

    We will also need to de-allocate memory when we are finished using
       in.

       in C++, "delete" does de-allocation.
       in C, "free" does de-allocation.


To use a static array and to use a dynamic array, the code is the same.


     int st_arr[100];  // creates the variable AND allocates memory

      st_arr[6] = 95;  // uses the array



     int *dyn_arr;     // create the variable ONLY

     dyn_arr = new int [100];   // allocates memory for the array

     dyn_arr[6] = 96;  // uses the array

  Or more likely

     int *dyn_arr;     // create the variable ONLY

     cout << "Enter an array size";
     int size;
     cin >> size;

     dyn_arr = new int [size];   // allocates memory for the array

     dyn_arr[6] = 96;  // uses the array



The size of static arrays must be known at compile time.

The size of a dynamic array does not need to known until run time.


IMPORTANT!!! PLEASE REMEMBER!!

For a static array, the memory is allocated in the "stack space"

For a dynamic array, the memory is allocated in the "heap space"


Local variables are stored in stack space