BIG C++
Cay Horstmann & Timothy Budd

Laboratory Notebook
Chapter 9 - Vectors and Arrays


Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.


Lab Objectives

To gain experience with


P1. Vector Subscripts

In the text, we have frequently used the rand_int function to generate random integers. For example, rand_int(1, 6) generates random numbers between 1 and 6, simulating the throw of a die. In this lab assignment you will use a vector to test whether the random generator is fair, that is, whether each possible value is generated approximately equally often.

Your program should ask the user

Make a vector with high - low + 1 elements, one for each possible outcome. Set each element to 0. Then keep calling the random number generator. If it returns a value v, then increment the counter belonging to v. There is just one catch. The random numbers are generated in the range low...high. The vector subscripts fall in the range 0...high - low. Therefore, you need to shift the ranges: the vector element corresponding to the random value v has subscript v - low.

After all numbers have been generated, print the counters. Here is a typical program run:

How many numbers do you want to generate? 1000
What is the low value? 1
What is the high value? 10
1    78
2   101
3   118
4    97
5   103
6   102
7   112
8    91
9    94
10  104


P2. Using Vectors to Collect Data Items

Vectors are frequently used to store and provide random access to a collection of objects of like type. In the following lab program, you will generate random circle objects and store them in a vector. If a circle does not intersect any of the previously stored circles, you will add it to the vector. Finally, display all circles that you collected in the vector. The result should look something like this: (Note that none of the circles intersect.)

Randomly generated non-overlapping circles

Use the code of the circle_intersect function that is given below to test whether two circles intersect. To randomly generate a circle, simply pick random x- and y- positions between -10 and 10 for the center and a random radius between 0 and 1. You need to compare each newly generated circle with all other circles before you can add it. (For that reason, we need a vector to hold all circles.) If the new circle passes the test, use push_back to add it to the end of the vector.

#include <vector>
using namespace std;
#include "ccc_win.cpp"

bool circle_intersect(Circle c1, Circle c2)
/* PURPOSE: Test if two circles intersect
            (distance between centers is less than sum of radii)
*/
{  if ( (c1.get_radius() + c2.get_radius()) < 
         sqrt( pow((c2.get_center().get_x() - 
                    c1.get_center().get_x()),2) + 
               pow((c2.get_center().get_y() - 
                    c1.get_center().get_y()),2)))
      return false;
   else
      return true; 
}

int main()
/* PURPOSE: Program to plot a finite number of non-overlapping, 
            randomly sized circles.
*/
{  vector<Circle> rand_circles;
   int max_circles;
   double rand_radius;
   double x,y;
   Point rand_center;
   Circle c1;
   bool intersect;

   max_circles = cwin.get_int("How many random circles would you like to see ? ");
   
   /*
      YOUR WORK GOES HERE
   */

   return 0;
}


P3. Resizing Vector Elements

We can dynamically resize vectors so that they may grow and shrink. While this is very convenient, it is inefficient. It is best to know the number of elements that you need for your vector when you create it. However, you might come across a situation someday where you do not know the number of elements in advance and need to implement a dynamic vector.

Rewrite the following program so that the user can enter any number of purchases instead of just 10.

#include <vector>
#include <iostream>
using namespace std;

int main()
{
	vector <double> purchases(10);
	int i;
	for (i=0;i< 10;i++)
	{
		cout <<"Enter a purchase amount";
		cin >>purchases[i];
	}
	return (0);
}

Now, add to the above code to print out the vector in reverse order and remove each element after it is printed.


P4. Return Parameters and Return Values

As with any other data type, when passing a vector as a parameter to a function, you need to choose between "pass by value" and "pass by reference". If vector elements are being changed in the function, pass the vector as a reference parameter, for example, vector<Employee>& empl. If the vector's contents are not going to be changed, then pass it as a value, vector<Employee> empl, or, for greater efficiency, as a const reference paramter, like vector<Employee> const& empl.

Copying an entire vector into a function can be expensive. Similarly, returning an entire vector as the result of a function can be expensive. Rewrite (and re-comment) the following function into a procedure that accepts a reference parameter and updates that parameter instead of returning a new vector as the result. Supply a main function that tests your function.

/* PURPOSE:  procedure to reverse elements in an integer vector
   RECEIVES: int_values - a vector of integer values
   RETURNS:  a copy of the vector, with the elements reversed
*/   
vector<int> reverse(vector<int> int_values)
{  int temp;
   vector<int> result(int_values.size());
   

   for(i = 0 ; i < int_values.size() / 2; i++)
       result[int_values.size() - i - 1] = int_values[i];
   
   return int_values;
}


P5. Simple Vector Algorithms -

Consider finding an average shipping cost from a sequence of 5 shipments where the lowest shipping cost is discarded. Write a program to locate the max and min values in 1.52, 3.44, 5.34, 6.43,4.44, 9.87, discard the lowest, and compute the average of the remaining scores.

How does your program handle duplicate shipping costs ? For example, how would it process 3.43,3.43,3.43,2.11,2,11? What do you think it should do?


P6. Avoiding Parallel Vectors

Write a program that reads in the names and scores of students and displays the names of the students with the highest and lowest score.

A simple method of carrying out this task would be to have two parallel vectors

vector<string> names;
vector<int> scores;

However, you should avoid parallel vectors in your solution.


P7. Arrays

Vectors are generally more convenient to use than the traditional C-style arrays. When defining an array, you must initialize its size to a constant value, and you cannot change that value again. If you fill the array gradually, you must keep track of the actual size of the array and ensure that it does not exceed the maximum size.

Rewrite the program in exercise P2, but store the circles in an array

Circle bubbles[BUBBLES_MAXSIZE];

Do not show more circles than BUBBLES_MAXSIZE, even if the user requests a larger value.


P8. Defining and Using Two-Dimensional Arrays

Vectors store a linear arrangement of values accessed by a single index. Two-dimensional arrays store a tabular arrangement of values accessed by two indexes, for example matrix[i][j], where i is the row index and j is the column index. A common two-dimensional array that you should have seen early on in your education is a multiplication table. For example, here is the multiplication table up to 5 x 5:

1 2 3 4 5
1 1 2 3 4 5
2 2 4 6 8 10
3 3 6 9 12 15
4 4 8 12 16 20
5 5 10 15 20 25

Write a program which asks the user for the number of rows and columns for a multiplication table and prints out the corresponding results.



P9. Additional Practice with Two-Dimensional Arrays

Crosswords are a type of puzzle which have letters in common. For example,

          d
       across
          w
          n

share the letter 'o'.

Write a program that will accept a list of words into a vector of strings, then make a 20 x 20 array of characters that contains a crossword puzzle with these words.

const int PUZZLE_ROWS = 20;
const int PUZZLE_COLS = 20;
char puzzle[PUZZLE_ROWS][PUZZLE_COLS];

For example, your program when given the list addle, apple, clowning, incline, plan, burr it displays it as:

   addle
   p   
   p   
  clowning
   e   n
       c
       l
       i
    plan
       e

That is, use the following method: Place the first word horizontally in the center of the top row. Place the next word vertically. Check if there is a common letter with the preceding word, and if all the squares into which you want to place that word are still empty. (If you cannot place it, skip the word.) Then switch back to horizontal, place the next word if possible, and so on.


Do not forget to send your answers when you are finished.