CSC 270
Homework 4

Assigned Oct. 4, due Oct. 16

What I want you to do

Write a C++ definition of a class named StringList that holds a list of strings and can have elements added and deleted easily.
Write a main program that reads in a sequence of strings into a StringList (note that you do not know in advance how many there will be, and cannot assume any fixed limit in advance). It then computes the average length of the strings, and prints it out; it then sorts the list into alphabetical order, prints it out, finds the median element in alphabetical order, deletes it from the list, and prints out the new list along with its average length.

The assignment should (if at all possible) be done in teams of two students, working together at one workstation much or all of the time. Each team should turn in one copy of the homework with both names on it.

What's a StringList?

The tasks of reading in the list values, sorting them, and printing them should each be done by a method of the StringList class. Other methods of the StringList class should include

This still leaves you with a lot of possible implementations. The one I'd like you to try for this assignment is a shrinking-and-growing array:

Shrinking and growing array, naive version
In this approach, the StringList class actually contains an array, but the array is dynamically allocated. When an element is added to the StringList, it allocates a new array one element longer, copies the elements of the old array into the new one (with the new element inserted at the appropriate position), and de-allocates the old one. Likewise, when an element is deleted, it allocates a new array one element shorter, copies the elements of the old array (except the element being deleted) into the new one, and de-allocates the old one.
This approach makes it very easy to jump around in the list and swap elements (adjacent or not), but adding and deleting elements is inefficient.
Shrinking and growing array, smarter version
As above, except that rather than allocating a new array one element longer or shorter, and copying the whole thing, every time an element is added or removed, it allocates a new array several elements longer or shorter so that it doesn't have to do it as often. The disadvantage is that you need to keep track of how many elements are really in the array, as well as how large the array is right now.
For example, if the increment were 10, it would need to allocate and copy when the first element was added, but not again until the 11th (21st, etc.) element was added, and any insertions and deletions in between would require no dynamic allocation of memory. Another neat way to do it is to always grow the array by a factor of 2, and only shrink it when less than half of it is in use.
This approach makes inserting and deleting elements more complex, but significantly more efficient. Since the underlying data structure is still an array, you can still jump around in the list and swap elements (adjacent or not) very easily.
Write your class definition in such a way as to hide the implementation: that is, the person using your class shouldn't need to know whether you're using singly-linked lists, doubly-linked lists, shrinking-and-growing arrays, or something else.

How to sort the list?

There are lots of sorting algorithms in the world. The bubble-sort we used in the previous problem is fairly simple, but not very efficient. Get your program to work correctly using the bubble-sort from the previous homework, and then, for extra credit, try Quicksort and/or Mergesort.

Quicksort

The idea here is to pick an element of the list -- called the "pivot" -- and divide the list into three categories: the elements less than the pivot, the elements equal to the pivot, and the elements greater than the pivot. To do this, you may want to write a categorize method that "returns" three lists (by taking in three List & parameters and assigning them). Once this is done, recursively sort the elements-less list and the elements-greater list (the elements-equal list, having only one value in it, is already sorted). Then you can simply concatenate the sorted elements-less list, the elements-equal list, and the sorted elements-greater list and get the final answer.

Mergesort

Mergesort, too, involves dividing the whole list into smaller pieces, sorting the pieces recursively, and putting them back together. But rather than dividing the list into those less than, equal to, and greater than a pivot, we'll just divide the list into the first half and the second half. Sort each of them recursively. Now you have two sorted lists, and need to put them together. Imagine each one is a sorted deck of cards: to combine two sorted decks into one, you look at the top card in each deck and take the smaller of the two, then do that again, and again, until one or the other deck becomes empty, at which point you take the entire remaining deck.

Last modified: 
Stephen Bloch / sbloch@adelphi.edu