Comp 11

More Complex Structures

Today:

Review: Structures vs. Arrays

How are structures and arrays similar? How are they different? Why do they matter?

Why we care

Computers allow us to deal with vast quantities of information, and with many types of information. Under the covers, the computer represents all of this as bits, coded patterns of zeros and ones. The simple types that C++ gives us like int and string are very useful for representing individual pieces of information, but they don't have the power we need to conveniently manipulate millions or billions of data items, or data with complex structure. Arrays and structures work together to give us this capability.

Arrays

Arrays let us exploit the computer's ability to represent lots of information. Important characteristics of arrays include:

Structures

Structures let us create our own first class types that match or model the objects we have in the real world. If a student has a name, a student ID, course listings, and a GPA in the real world, then we can create a structure type called Student that has just those fields. By first class type we mean that the new Student type is accepted by C++ in same ways that the built-in types are. In a sense, when you define a struct, you are extending the C++ language to manipulate just the type of data you need. This is a wonderful capability; indeed, the ability to do things like this is one of the characteristics that distinguishes computing systems from many other engineering innovations. Not only can we model new types of data as needed, we can write code that extends the computer with useful capabilities for manipulating that data. For example, we could write code that would automatically update the student's GPA when a new course is added to her list of courses taken. Computers can, in this sense, extend themselves and adapt to new uses in ways that other "machines" can't.

Using points to make rectangles

We've seen structures used to make new types for our C++ programs. Here we explore how these types can themselves be used in other structs.

Exercise

Specifically, consider a structure representing a point on the x,y plane:

struct Point {
        int x;
        int y;
};

How can we use two of these structs to define the bounds of a retangle? Explore rectangles.cpp.

That program created and displayed an array of retangles, each of which was built from two points. Now we can make the program do more:

Exercise

How can we expand that program to test whether a point we enter from the console is within any of our rectangles? Explore is_in_rectangle.cpp

Finding an Apartment

Go to an apartment website

How does such a web site work? What do they have to represent?

Exercise
Fill in apartment.cpp

Exercise
Design a Flight structure. Fill in travel-inc.cpp

Modifying versus Translating an Array

Often you want to transform the contents of an array.

Problem: Given array of temperatures in degrees Celsius, produce an array of equivalent temperatures in degrees Fahrenheit. See: ftoc-list.cpp

Sorting an array

Sorting is a common programming task. You want to sort a list of apartments by rent, by distance from campus, by the number of bedrooms. You want to sort a list of flights by price, by time enroute, by number of stops, by airline.

Given that sorting has been such a common problem since the inception of modern computing devices, there are many algorithms for accomplishing the task. You'll study quite a few and their relative efficiencies in Algorithms. First imagine how you might sort a stack of papers by the name. Would you create a new stack of papers and move the papers into it one at a time by inserting each one into its appropriate place (insertion sort)? Would you move the first name to the front, then move the next name to the second position (selection sort)? Divid the papers into piles, sort each one, then merge the results (merge sort)? Sorting can be done either in place (the sorted array occupies the same space as the original array) or into another array. Often, we prefer in-place solutions.

Today, just consider the problem of sorting an array of integers. To pick one example, we'll use selection sort. The basic idea is that we think of our array as having two parts, the sorted part, and the unsorted part. Initially, the sorted part contains no values and the entire array is unsorted. What element belongs in the first slot of the array? The least element. If we can find out the least element (minimum) in the unsorted part of the array and exchange it with whatever is currently in the first slot, then the first slot is sorted. So now the unsorted array consists of the second slot in the array through the end of the array. What element belongs in the first slot of the unsorted array (which is actually the second slot in the original array)? It's the minimum element. If we find that element and swap it with the element in that slot, then we have another sorted element. If we continue like this to the end of the array, the array is sorted.

Assume index_of_min(values, start_index, end) takes an array values returns the index of the least element found starting with index start_index and ending with index end - 1, i.e., the index of the least element in slots whose index is in [start_index, end).

Assume swap(values, i, j) swaps the elements at indices i and j.

/*
 * Sort the array in values into ascending order.
 */
void selection_sort_loop(int values[], int size)
{
	for (int i = 0; i < size; ++i) {
                int index_of_smallest = index_of_min(values, i, size);
		swap_fun(values, i, index_of_smallest);
        }
}
	
selection_sort.cpp shows this code in action. The example also illustrates some other fun things, including some handling of command line arguments, a fun way to swap elements, and a recursive encoding of the sorting algorithm. We'll discuss recursion more later, but note how it very directly reflects our description above: If you have some elements to sort, you put the least element in the first slot, and then you sort the rest of the list.
Mark A. Sheldon (msheldon@cs.tufts.edu) with modifications by Noah Mendelsohn (noah@cs.tufts.edu)
Last Modified 2017-Sep-07