The program for this assignment, and everything else except the README file, is due at 9 PM on Wednesday, April 5, 2000. The README file is due at 12 midnight on the same day.
The primary purposes of this assignment are:
Your assignment is to implement a generic singly-linked list class that can store any data type. To test your class, you will write a program that uses the lists to perform two simple tasks: sorting a list of integers, and printing a list of strings in reverse order. (Note that both tasks could probably be done better in other ways; the point is to test your class, not to implement the best sorting and reversal algorithms possible.)
The list class should contain the usual constructors and destructors, plus functions for adding and removing items at both ends of the list, and a function for inserting an item in the correct place in an ordered list. These list functions will be described in greater detail below.
Your test program will read integers from a file and place them onto a sorted list. When that file is empty, will begin reading strings from a second file and will place them onto the tail of a second list. All input will be done using the string-reading function you developed for assignment #3. You must use your function from assignment #3 or you will lose points. However, you do not have to use your old function without changes. You are allowed to make improvements and bug fixes to your function so that it will be more suitable for this assignment.
When the second file is exhausted, your program will then print the sorted list of integers separated by blanks. On a separate line, it will print the list of strings in reverse order. The output format is specified precisely below.
Your submission should consist of at least seven files:
Makefile
make utility.
The executable generated by "make" (no arguments)
must be named assign_07.
Unlike in previous assignments, the Makefile is not
supplied; you must create it yourself.
Your Makefile will be graded.
assign_07.cc
README
If you wish, you can create other files to help you develop this assignment, but it is not necessary.
Your program will read from two files, whose names are
supplied on the
command line. It will write to standard output (cout).
Your program must verify that it received the correct number of input
arguments and print a usage message (like the example below) if it is
invoked incorrectly. See the section below
for more information on how command-line arguments are provided to the
program.
So, a sample run of your code might look like:
prompt> ./assign_07 h7-int-input.txt h7-char-input.txt -15 -2 0 1 2 2 3 4 4 5 7 8 9 The value of x times 3 is normally written as 3x. prompt> ./assign_07 Usage: ./assign_07 numberfile stringfile
One critical point about your program is that it must perform the reversal of strings by pushing and popping data at the tail of the string list, not the head. You will lose points if you work from the head of the list, even if your program generates correct output.
Both input files will be in the same format: a series of strings, separated by whitespace, as returned by your readstring function. Either file may be empty, or may consist solely of whitespace. The strings in the first file will consist exclusively of positive and negative integers; these might or might not appear in a sorted order. The second file will contain arbitrary strings. Note that the second file might contain some valid integers, but they should still be treated just like any other string.
You will need a way to convert C-style
strings into long integers.
The function atol
("ASCII to long") will do this for you. It is declared in
the include file <stdlib.h>, which you will need to
#include at the top of your program. You can use it
somewhat like this:
long value = atol(nextstring);
The same library contains a range of similar functions, such as atoi (convert to non-long integers) and atof (convert to doubles).
All of these functions have a severe flaw: if they encounter an
illegal number, they simply quit converting and return what they have
so far. For example, atol returns 0 if given the string
"XYZ"; if it is given "3X4Y" it will return 3. There is no easy way
to detect illegal input, other than writing your own loop to test
every character. The POSIX standardization committee has recently
designed similar functions with error checking (strtol,
strtoul, and strtod), but they are not yet
standard and are more difficult to use. Therefore, for this
assignment, we will not require that you detect such errors.
When a C++ program is invoked under Unix, you can give it one or more
arguments (parameters) on the command line. The system
preprocesses these arguments for you and makes them available to your
main program as function parameters. You should declare
your main program like this:
int main(int argc, char* argv[])
{
// ...
}
The parameter argc gives the number of arguments that
appeared on the command line, including the name of the
program itself. So an invocation like "./assign_07" will produce an
argc of 1, while "./assign_07 x y z" will set
argc to 4.
The parameter argv is an array of pointers to character,
i.e., an array of C-style strings. argv[0] is always the
name of the program as you invoked it, e.g.,
"./assign_07". Similarly, argv[1] is the first
argument, expressed as a string; argv[2] is the second
argument, and so forth. It is illegal to refer to
argv[i] when i is greater than or equal to
argc.
When you run a C++ program, three streams just exist by magic:
cin (standard input, which is usually the terminal but
can be redirected using "<"), cout
(standard output, which can be redirected away from the terminal using
">"), and cerr (error output, which
almost always goes to the terminal). To read input from a named file,
you must open
a new stream connected to that file.
File streams are of type ifstream (input) or ofstream (output).
A file stream is an object, like any other. It is possible to create the object and then later connect it to a file (called "opening" the file), but it is more common to do both jobs at once. For example:
ifstream fp_in("myfile.txt");
if (fp_in.bad()) {
// Failed to connect stream to file, deal with it
}
The above snippet will create an ifstream object and try
to connect it to a file named myfile.txt. If something
goes wrong (e.g., myfile.txt doesn't exist), the stream
will become "bad" and you must deal with it. Otherwise, the stream is
ready for use, and you can treat it like any other
istream (input stream), such as cin.
It turns out that when you are done with a stream, you need to tell the system that you are done. This is called "closing" a file. The easiest way to close a stream-based file is to simply destroy the object that it is connected to. So, for example:
if (need_to_produce_output) {
ofstream fp_out("myoutput.txt"); // Creates an output file
if (fp_out.good()) {
// ..produce output
}
}
// fp_out is destroyed, so myoutput.txt has been closed
You can also explicitly close a file by calling the close
member function. It does not hurt to close the file and later destroy
the stream: the file will not be closed twice.
The snippets above omit some important stuff, such as setting up the
proper #include files. Here is a more complete example,
showing how to read from a file whose name is stored in the
char* variable filename:
#include <iostream.h>
#include <fstream.h>
// ...
// Open input file
ifstream fp_in(filename);
if (fp_in.bad()){
cerr << "Cannot read file " << filename << endl;
exit(1);}
}
// Read something from file
char *nextString = readString(fp_in);
// ...
// Done reading file, close it
fp_in.close();
Although all open files are automatically closed when the program terminates, good practice dictates that a file should always be closed as soon as you are done with it. This is particularly important when you intend to open a lot of files and you will be done with them long before the program terminates, as there may be a limit on how many files you can have open at once and someone else might want to use the files when you are done with them. It also helps to ensure that your work will not be lost if the machine crashes.
As in homework #4/5, you must use your string-reading function from homework #3 to read whitespace-separated strings from the input file. To make your life easier, you should put the function into a separate file. If you did assignments 3, 4, and 5 correctly, this will be extremely simple, and the function will work properly the first time.
As usual, the output of your program will be graded automatically, so it is important that you conform to the specified format. For this assignment, the output format is simple and easy to generate. There will be only two lines of output:
The important part of the assignment is the list class. It is worth spending some time on this class, because you'll be using it again to help you implement more complex data structures later in the term. In fact, you might want to write some additional test code to make sure that all of your functions work properly, and then remove it before turning in your assignment.
The list you will implement should be singly linked, not doubly linked. You may or may not wish to maintain a separate pointer to the tail of the list; doing so will make certain functions more efficient at the expense of complicating your code.
Your list class must be templated, so that you can instantiate it for different data types (in particular, both strings and integers).
Your list class also must make use of both a special list-header class and an internal auxiliary class. The auxiliary class will be invisible to the outside user, and will hold list elements. Your implementation should be similar to the code given in the header and implementation of the templated list class discussed in class. You will lose points if you attempt to implement the list using only a single class that holds data and also serves as the List object visible to outside users. (Furthermore, such an implementation will turn out to be a problem when you try to use it later in the term.)
Finally, your class must implement the following functions at a minimum:
Any proper list class will implement the following essential functions:
true or
false to indicate whether the list has any
items in it.
In addition to the above basic functionality, many list classes also implement the following functions. Your list class must implement at least pushing and popping at the tail:
Some list classes go much farther than the above functionality. You
will only need one truly fancy function, which will allow you to
insert an item in its proper place in an ordered list. The function
can assume that the templated data type implements the "<" operator
and use that operator for sorting. In other words, if your list
template is instantiated on ints, it would sort integers
into ascending order, but if it is instantiated on int*,
it would sort the pointers into order by address.
Your list class must implement sorting by inserting items into their correct place in the list. It is not acceptable to insert an item at the head or tail, and then call a sorting function to reorder the list. Part of the point of the assignment is to teach you how to manipulate pointers in the middle of the list.
Other functions that are often found in list classes (but that you do not have to implement) include:
Your list class should check for errors such as popping from an empty
list. If an error is detected, you should generate a message to
cerr and abort the program by calling exit(1).
Here are trivial sample integer and string input files, as well as the output generated from them.
The sample files are also available for downloading as a ZIP archive or gzipped tar archive.
icc Files
By default, emacs doesn't know that icc files contain C++
code. There are three ways to tell emacs to use C++ mode:
ESC x c++-mode RET" each time you visit
the file. Obviously, this is a pain.
// ;-*-C++-*-" as the first line
of the file. Emacs will recognize the line and automatically
switch to C++ mode. This is less of a pain, but you still
have to do it to every file.
.emacs" file in
your home directory. (If you don't have a
".emacs" file, create one containing this line:
(setq auto-mode-alist (append '(("\\.icc$" . c++-mode)) auto-mode-alist))
The line must be inserted exactly as given above,
including the double backslash, the parentheses, and the funny
single quote.
There are several parts of this assignment that can surprise you. Here are a few:
readString
that always read from cin, rather than the stream
specified by the argument, or that do some operations on the
stream and others on cin. Those mistakes will
show up in this assignment. Your readString
function should not mention cin anywhere.
readString onto a
list of character pointers, don't delete them
right away, or you will get garbage output. Instead, you must
wait until you have generated your output before you get rid
of them. (I made this mistake myself, in the first version of
the sample solution.) But don't forget to delete
them eventually, or you will lose points for a memory leak!
longs).
When you get that working, you can convert it to a templated
class.
private section. That way, the compiler will
warn you if you accidentally invoke them.
This page maintained by Geoff Kuenning.