Welcome to Our Last Class!

Announcements

  • Final Exam: Tuesday from 4:00pm to 6:00pm in this classroom!
    • No makeups - the exam must be taken on the day and at the time given
    • How to study: Old Quizzes, Midterms, Programs (In and Out of Class)
    • Final will be cumulative from first day of class through today's lesson
    • Will select one function from your fun with functions worksheet
    • Will select one function from your fun with arrays worksheet (tonight's homework)
    • Expect a program from a homework assignment I assigned after Midterm 2
    • Start studying now!
  • Return Quiz 7
  • Last lab due Friday at midnight
    • File I/O and arrays
  • Last homework due Friday at midnight
  • No office hours next week
    • Will be available by email
    • No more late work accepted



Review Activity

1. With a partner, declare an array of doubles named weights and assign it the values 135.6, 150.9, 187.8, 205.9 in TWO WAYS (static and non-static initializaton)!

2. Write a for loop to print out the values in the weights array.

3. Now write a function that prints out an array of doubles

  • The function is named printArray
  • It takes in two parameters - one is an array of doubles, one is an int for the size of the array
  • It returns nothing
4. Call printArray, passing it the weights array from question 1 above


Array Algorithms

Searching An Array for a Value

  • Suppose you want to find a particular value in an array
  • This is known as searching a list
  • An easy and straightforward algorithm is linear search (a.k.a. sequential search)
  • In linear search you:
    • Start at the beginning of the list
    • Compare each value in the list looking for matches:
      • If the value is found, then return the position (index)
      • If you reach the end of the list, return "not found"
  • Since an index must be >= 0, then we can use -1 as the "not found" value


Group Activity: Finding an Element in a List

  1. Select one volunteer to be the finder.
  2. All other students line up and each choose a number between 1-20, keeping the number to themselves.
  3. The finder writes the number he or she is looking for on the board.
  4. The finder starts at one end of the line and asks each student if he or she has the number sought.
  5. When a student with the sought after number is found, write the index number of the found student on the board.
  6. If the number is not found, the student writes -1 on the board.



Linear Search Pseudocode:

for each item in the array:
     if that item has the desired value,
         stop the search and return the item's location.
//End for loop
return -1


Activity 21.1: Linear Search (10pts)

  • Let's write the code for linear search
  • Open up a new C++ file and name it linearSearch.cpp
  • Copy and paste the starter code into your file.
  • Now, given the pseudocode for linear search above, write the linearSearch function.
  • Then, call your function inside of main using the two test values : value and newValue and storing the result in the variable indexOfValue.
  • Once your program is completed, upload linearSearch.cpp to Catalyst.


#include <iostream>
using namespace std;

int linearSearch(int array[], int sizeArray, int value);

//Searches an array for a particular value given
//array[] is the array to search
//sizeArray is the size of the array to search
//value is the value to search for
//returns the index of the item in the array if it exists in the array or -1 if it doesn't


int main() {
const int SIZE = 5;
int nums[] = {2,9,6,5,3};

int value = 5; //the value to search for
int indexOfValue; //the index of the value
    //function call to linear search goes here

if (indexOfValue != -1) {
cout << "The index of " << value << " is: " << indexOfValue << endl;
} else {
cout << value << " is not in the array." << endl;
}

    int newValue = 14;
    //function call to linear search goes here
    //use indexOfValue again to store return value of function

    if (indexOfValue != -1) {
        cout << "The index of " << newValue << " is: " << indexOfValue << endl;
    } else {
        cout << newValue << " is not in the array." << endl;
    }

return 0;
}

int linearSearch(int array[], int sizeArray, int value) {
    //write the function here
}

Removing Array Elements Option 1: Swapping the Element to Be Removed with the Last Element

  • Once we find an element in an array, we may want to remove it from the array
  • Unfortunately, the capacity of an array cannot change after it is declared
  • If the order is not important then:
    1. Overwrite the element to be removed with the last element of the array
    2. Shrink the size of the array (Note that the provided function does not change the array size variable. You will need to modify the array size accordingly each time you call the remove function.)
  • For instance:
void remove(int array[], int sizeArray, int indexToErase) {
    array[indexToErase] = array[sizeArray-1];
}

  • The following diagram shows this operation:


Removing Array Elements Option 2: Maintaining Order in the Array

  • However, if order matters then we must:
    1. Write over the element you wish to remove with the following element (at index i+1).
    2. Move all subsequent elements up by one index (each element's index becomes one less).
    3. Shrink the size of the array by one. ( Again, note that the provided function does not change the array size variable. You will need to modify the array size accordingly each time you call the remove function).
  • For instance:
void remove(int array[], int sizeArray, int indexToRemove) {
    for (int i = indexToRemove; i < sizeArray-1; i++) {
        array[i] = array[i+1];
    }
    return;
}

  • The following diagram shows this operation


Group Activity: Removing an Item from an Array

  1. Select one volunteer to be the remover.
  2. All other students line up and write their number in the list (index number) on a piece of paper starting at zero, and hold their paper up for view.
  3. The instructor chooses an index number and writes it on the board.
    cout << rand() % numberOfElements;
    
  4. The remover goes to the starting position and asks the removed student to return to their seat.
  5. The remover then assigns each of the students after the removed student an index number that is one less than their previous number.
  6. The students with reassigned index numbers update the indexes on their paper.

Example Program to Remove an Element from an Array


#include <iostream>
using namespace std;

void remove(int array[], int sizeArray, int indexToRemove);

//removes an item from a list, given the index of the item to remove
//array[] is the original list stored as an array
//sizeArray is the size of the original list before the value was removed
//indexToRemove is the index of the item to remove

int main() {
    const int CAPACITY = 10;
    int size = 5;
    int myArray[CAPACITY] = {1,2,3,4,5};
    int indexToRemove = 2;

    remove(myArray, size, indexToRemove);
    size--;

    //Print the array to make sure that the item was removed
    for (int i = 0; i < size; i++) {
        cout << myArray[i] << endl;
    }

    return 0;
}

void remove(int array[], int sizeArray, int indexToRemove) {
    for (int i = indexToRemove; i < sizeArray-1; i++) {
        array[i] = array[i+1];
    }
    return;
}





Inserting Elements Option 1: Adding the Element to the End of the Array

  • If we want to add an item to an array, the easiest way is to place it at the end of the array.
const int CAPACITY = 10;
int size = 3;
int my_array[CAPACITY] = {2,3,4};
int newValue = 8;
my_array[3] = newValue; //array now contains 2, 3, 4, 8
size++;
  • However, the size of your array must be smaller than its capacity.

const int CAPACITY = 5;

int size = 5;

int nums[CAPACITY] = {2,9,6,5,3};
  
nums[5] = 8;


Produces the following warning:


  • However, beware that there is not always an error message when you make this mistake.


Inserting Elements Option 2: Adding the Element to the Middle of the Array

  • What if we want to insert an item in the middle of a array?
  • We might choose this option if we wish to maintain a specific ordering of our elements.
  • In this case, we must:
  • Move all elements after the insertion location down by one slot (the index of these elements increases by one)
  • Assign the new value to the element at the insertion slot
  • The following diagram shows this operation



Group Activity: Adding an Item to the Middle of the Array

  1. Select one volunteer to be the adder.
  2. Select one volunteer to be added.
  3. All other students line up and write their number in the list (index number) on a piece of paper starting at zero, and hold their paper up for view.
  4. The instructor chooses an index number and writes it on the board.
    cout << rand() % numberOfElements;
    
  5. The adder goes to the end of the list and asks each student to step one position more towards the end, adding one to their index number.
  6. When the add position is reached, ask the student to be added to move to the position.


Activity 21.2: Inserting an Element into an Array (10pts)

  • Open up a new C++ file and save it as insert.cpp.
  • Copy and paste the starter code from below into your file:

#include <iostream>
using namespace std;

void insert(int array[], int size, int capacity, int value, int index);

//inserts a new item into a list, creating a new array in the process
//The parameter array is the original list stored as an array
//The parameter size is the size of the original list before the new value is added
//The parameter capacity is the total capacity of the array
//The parameter value is the value to be added to the list
//The parameter index is the index at which to add the new value to the list
 

int main() {
    const int CAPACITY = 10;
    int size = 5;
    int nums[CAPACITY] = {2,9,6,5,3};
    int valueToAdd = 100;
    int index = 2;
    insert(nums, size, CAPACITY, valueToAdd, index);
    size++;
   
    //Prints out the array to make sure the new value was added to the array
    for (int i = 0; i < size; i++) {
        cout << nums[i] << endl;
    }

    return 0;
}

//You fill in the rest of the code for the function
void insert(int array[], int size, int capacity, int value, int index) {
    if (size == capacity) {
        cout << "Array is full. No items can be inserted." << endl;
        return; //function will end here
    }
    
for(int i = size; i > index; i--) {
        //What goes in here;
    }
    array[index] = value;
    return;
}
  • It is your job to write the insert function.
  • Your function should insert into an array whose capacity is larger than its size.
  • In other words, your function needs to shift down all of the items in the array starting from the index of the new value that you wish to insert to the last element in the array
  • Then, insert the new item in the array at the desired index.
  • Use the pseudocode in the section above to help yourself.
  • When you are finished writing your function, run your program and make sure the new element was inserted into the correct location.
  • Once everything is running properly, upload your insert.cpp file to Catalyst.


Wrap Up
  • With your partner, answer the questions from today's learning objectives

Upcoming Assignments
  • Assignment 20 due Friday at midnight on Catalyst
  • Lab 9 due Friday at midnight
~ Good Luck Studying! ~