CSc 335
Project 0 -- C++ Warm up
Due Dates:
Part 1: Wednesday, April 1, 2009 (no foolin'!)
Part 2: Monday, April 6, 2009
Objectives
- To start getting used to C++, if you're not familiar with it
already
- To remember good coding practices like thorough testing
Introduction
C++ is our primary language in this course, and the ability to
independently
learn new computer languages is a skill every computer scientist and
computer
engineer needs. In this project, you'll start getting comfortable with
C++
by implementing an old friend -- a doubly-linked list.
Your Mission
In Part 1, you'll implement a doubly-linked list in Java. In Part 2,
you'll
translate it to C++.
Part 1: Java
The following starter code should be used to implement your
doubly-linked
list in Java. This is not meant to be a generalized list, but
just a limited one with a few specific behaviors.
Each node in the list will contain two elements: a
key
(an int) and a data item (an Object). You should keep this list
in sorted order by key.
public class DLList
{
private DLLElement first; //pointer to first node
private DLLElement last; //pointer to last node
/**
* Creates an empty sorted doubly-linked list.
*/
public DLList()
{
}
/**
* Add item to the head of the list, setting the key for the new
* head element to min_key - 1, where min_key is the smallest key
* in the list (which should be located in the first node.)
* If no nodes exist yet, the key will be zero.
*/
public void prepend(Object item)
{
}
/**
* Removes the head of the list and returns the data item stored in
* it. Returns null if no nodes exist.
*/
public Object removeHead()
{
}
/**
* Returns true if the list is empty. Otherwise, false.
*/
public boolean isEmpty()
{
}
/**
* Inserts item into the list in sorted order according to sortKey.
*/
public void insert(Object item, Integer sortKey)
{
}
/**
* Print the list for debugging only. The "which" parameter is
* just a label you should print before the list so you know
* which printing this is. Example:
* PRINTING #1:
*/
public void printList(int which)
{
}
// the node class (inner class)
private class DLLElement
{
private DLLElement next;
private DLLElement prev;
private int key;
private Object data;
public DLLElement(Object item, int sortKey)
{
}
}
}
Notes:
- Do NOT import any classes or packages. You are taking care of
all the pointer manipulation yourself.
- You'll notice something in the code that you may not have seen
before
in Java: a private inner class. This lets DLList objects
access the
private DLLElement (node) instance variables as if they were
public. So
in DLList, you can say first.next and that would be ok.
- You will need to create a separate class for your main()
method
which should test the methods above. I recommend using Strings as
your data items. Watch out for special cases!
- You may use any development environment you wish.
Part 2: C++
Redo Part 1 in C++. All C++ programs in this entire course should be
done in your account on the antipasto server. You should
create three files:
- DLList.h for your declarations
- DLList.cc for the list implementation
- main.cc for your main() function, which will
simply test your list functions
To help you out, here is starter code for DLList.h:
#ifndef DLLIST_H
#define DLLIST_H
class DLLElement
{
public:
DLLElement(void *item, int sortKey);
DLLElement *next;
DLLElement *prev;
int key;
void *data;
};
class DLList
{
public:
DLList(); // constructor
~DLList(); // destructor
// Add item to the head of the list, setting the key for the new
// head element to min_key - 1, where min_key is the smallest key
// in the list (which should be located in the first node.)
// If no nodes exist yet, the key will be zero.
void Prepend(void *item);
// Sets sortKey to the key of the head element and removes the head
// of the list.
//
// Returns the data stored at the head of the list. If no nodes
// exist, returns null and sortKey will be left undefined.
void *RemoveHead(int *sortKey);
// Returns true if the list is empty. Otherwise, false.
bool IsEmpty();
// Inserts item into the list in sorted order according to sortKey.
void Insert(void *item, int sortKey);
// Print the list for debugging only. The "which" parameter should be
// printed before the list so you know which printing this is.
void PrintList(int which);
private:
DLLElement *first;
DLLElement *last;
};
#endif
Notes:
- The RemoveHead() function has changed slightly in
the C++ version. It now takes a single int parameter called
sortKey. The
RemoveHead() function will set sortKey
to be the key of the head of the list, remove the first node, and then
return the associated data item. This demonstrates C++'s ability to
explicitly return multiple items from a subroutine: one via the return
type,
and one via the parameter.
- Don't use cin and cout for I/O. Nachos doesn't play well with
those.
(And you're going to use your linked list in Nachos in the next
project.) Use printf for output instead.
- For this part, please use chars as data objects instead of strings.
Strings may give
you some headaches since C and C++ each has a different way
of defining them.
- Read the C++ FAQ. The answer you need
may be there.
Compiling and Running programs on antipasto
You'll use g++ to compile your programs on antipasto.
In the end, you won't be using it directly (because I'm requiring
you to use a makefile -- see below), but if you want to
compile it directly, do this:
g++ <file1> <file2> ...
where the files are all of your *.cc files.
To make your compiled code traceable by the gdb debugger,
use the -g option:
g++ -g <file1> <file2> ...
Remember that a link to the
gdb debugger manual
can be found on our web page.
Once you have removed all compiler errors, a file named
a.out will be produced. This is the binary
executable. To run it, just type
a.out
You may have to type ./a.out if your path variable
does not include the current directory.
Makefiles
As I said previously, by the end of this project you won't have to compile
your code directly in the way described above. That's because
I'm requiring you to create a makefile to compile
your program. Basically, a makefile is just a small script that
tells which source files need to be (re)compiled and linked
together. It makes recompiling efficient since it only compiles
those files that need it. It also ends up saving you quite a bit
of typing. Read this makefile tutorial to see how to make one.
For your own makefile please:
- name it Makefile (note capital M)
- name your executable DLL. You can change the name
of the executable from the default a.out by using the -o
option. See the tutorial for examples.
- use macros where you can to get the hang of them.
- include a clean target that will clean up object (*.o) and
executable files.
When complete, you should be able to just type:
make DLL
to compile your program and create the executable DLL
ready to run.
And, of course, please ask me if you get confused or stuck.
For this small project, a makefile is really overkill, but (1) they're
lifesavers for really big projects and (2) Nachos is big enough that
it uses makefiles. So understanding them now will help you understand
what Nachos is doing in the future.
Finally...
After getting your DLList class and your makefile
to work, create one more file
named
DLList-driver.cc. This will contain two functions:
- AddN(). This function will take a DLList * (pointer to a
DLList)
and an int (call it n) as parameters. This function will add n elements
to the given DLList. You may create random keys and data items for the
nodes
or else hard code specific keys and data items to make debugging easier.
- RemoveN(). This function takes a DLList * and an int n as
parameters. It removes and prints n elements from the head of the given
DLList.
Add calls to AddN() and RemoveN() to your
main.cc file. Alter your makefile to include the new
DLList-driver.cc file in the compilation.
Debug until it works.
How to turn this in
Part 1 should be zipped up and submitted to the dropbox
on Blackboard. (This
is probably the only time we'll be using the dropbox in
this course.) Part 2 will be submitted using a script I
have set up on the antipasto server. Be sure all of the files
you want to turn in are in a single directory and then type
/home/csc335pub/submit csc335 <full path to directory>
where <full path to directory> is the complete path to the
directory you want to submit. (Use the "pwd" command to find out
the full path to your current directory). So, for example, if
I kept all of my relevant files in a directory named proj0,
I would submit it with
/home/csc335pub/submit csc335 /home/fernandc/proj0
You should also turn in your code on paper (for both parts). Include your
output tests with your paper copy.
Grading
This project is worth 25 points: 10 points for Part 1 and 15 points for
Part 2.
I'll be grading on correct output,
having all of the required elements in your makefile,
and the quality of your testing.
Be sure to check for boundary conditions (empty
list, inserting at the start of the list, etc.)
Having trouble? Don't wait until the last minute! Come see me and get
your
$80 worth.
Administrative statement
Programming assignments, like homework
assignments, are individual projects. I encourage you to
talk to
others about the general nature of the project and ideas about how to
pursue it.
However, the technical work, the writing, and the inspiration behind
these must
be substantially your own. If any person besides you contributes in any
way to
the project, you must credit their work on your homework. Similarly, if
you
include information that you have gleaned from other published sources,
you must
cite them as references. Looking at, and/or copying, other people's
programs or
written work is inappropriate, and will be considered cheating.
Return to
Project Index