The exercise will be marked out of 10, and is worth 5% of your total grade.
Late submissions will be penalized 2.5 marks per day late or part thereof.
Exercise details:
For lab exercise 2 you will be implementing the phone book as class, again using a linked list for the internal storage.
In lab exercise 1 your phonebook was a collection of standalone items:
- a struct held individual
entries in the phone book as part of a linked list,
- a variable in the main routine kept track of
the front list element, and
- you implemented a number of functions to build, search,
and manipulate the list.
In lab exercise 2, you will implement a collection of class methods that provide all the list functionality, this time as a doubly-linked list which tracks both the front and back of the list.
The main routine and support functions are provided for you in file labex2.C, and the definition of the class and some supporting constants are provided in header file LList.h.
Your implementations of the class methods will go in file LList.C, which will be the file you submit for the exercise.
Here are the files labex2.C and LList.h
// LList.h
#ifndef LLIST_H
#define LLIST_H
#include <string>
using namespace std;
// =========================================================
// ====== Data types and constants used in the program =====
// define a maximum length for text
const int MaxTextLen = 256;
// define the list class that stores keys/values
// in a linked list
class LList {
private:
// define the contents of a single key/value pair
struct keyValue {
string key; // search key
string value; // associated data value
keyValue *next; // next key/value in the list
keyValue *prev; // previous key/value in the list
};
// maintain pointers to the front and back items in the list
keyValue *front, *back;
// lookupEntry (internal use)
// -----------
// search the list or an entry matching the specified key,
// return a pointer to the entry if found,
// return null otherwise
keyValue* lookupEntry(string key);
public:
// constructor to initialize the empty list
LList();
// destructor to deallocate all list entries
// when the list is deleted
~LList();
// adds one key/value pair to the list
// as long as the key does not already appear in the list
// if the addFront flag is true then the entry
// is inserted at the front of the list,
// otherwise it is inserted at the back
// returns true if successful, false otherwise
bool insertEntry(string key, string value, bool addFront=true);
// search the list or an entry matching the specified key,
// set the matching value and return true if found,
// return false otherwise
bool lookupEntry(string key, string &value);
// search the list or an entry matching the specified key,
// set the new matching value and return true if found,
// return false otherwise
bool changeEntry(string key, string &value);
// search the list or an entry matching the specified key,
// remove the entry from the list, delete it,
// and return true if found,
// return false otherwise
bool deleteEntry(string key);
// display each key/value pair in the list,
// with one key/value pair per line of output
void displayEntries();
// if the specified file cannot be opened return -1,
// otherwise
// add each key/value pair in the file to the list
// returning a count of the total number of successful inserts
// assumes the file contains an even number of lines,
// alternating between keys and values, e.g.
// Fred Jones
// 555-123-4567
// Scoobert Doo
// 555-987-6543
int insertFromFile(char filename[]);
// if the list is empty simply return false,
// otherwise remove and delete one element from the list
// after copying its key/value to the parameters
// removes the front element if atFront is true,
// the back element otherwise
// returns true if successful
bool removeFrom(string &key, string &value, bool atFront=true);
};
#endif
|
// labex2.C
#include "LList.h"
#include <iostream>
using namespace std;
// =========================================================
// ====== Data types and constants used in the program =====
// define the valid single-character commands
enum Command {
QuitCmd = 'Q', InsertCmd = 'I',
EditCmd = 'E', LookupCmd = 'L',
HelpCmd = 'H', RemoveCmd = 'R',
PrintCmd = 'P', FileInsertCmd = 'F',
InvalidCmd = '-', ExtractCmd = 'X',
};
// define the character used to select front vs back of list
const char ListFront = 'F';
// =========================================================
// ====== Prototypes for provided support routines =========
// get the user to pick which end of the list to work on,
// returns true for front, false for back
bool pickEnd();
// read a name from the user
// and store it in the parameter provided
void getName(string &name);
// read a number from the user
// and store it in the parameter provided
void getNumber(string &number);
// display the list of valid commands
void printCommands();
// read and return a valid single-character command,
// limits to one command per line
// (anything beyond the first command is discarded)
Command getCommand();
// process a command and update the name/number list
void processCommand(Command cmd, LList &phoneBook);
// =========================================================
// ====== Provided main routine ============================
int main(int argc, char* argv[])
{
// current list of messages, initially empty
LList phoneBook;
// current user command
Command cmd;
// display the welcome message
cout << "Welcome to the phonebook system\n" << endl;
// load names/numbers from the file specified in
// the command line argument (if any)
if (argc > 1) {
int numLoaded = phoneBook.insertFromFile(argv[1]);
if (numLoaded < 0) {
cout << "Attempt to load from file \"" << argv[1];
cout << "\" was unsuccessful" << endl;
} else {
cout << "Load from file \"" << argv[1];
cout << "\" inserted " << numLoaded << " entries\n" << endl;
}
}
// display the command list on startup
printCommands();
// keep obtaining and processing commands
// until the user decides to quit
do {
cmd = getCommand();
processCommand(cmd, phoneBook);
} while (cmd != QuitCmd);
// shut down
cout << "Exiting the phonebook system\n" << endl;
return 0;
}
// =========================================================
// ====== Implementations of provided support routines =====
// get the user to pick which end of the list to work on,
// returns true for front, false for back
bool pickEnd()
{
char choice;
char junk[MaxTextLen];
cout << "Please enter " << ListFront;
cout << " to work from the front of the list,\n";
cout << "or anything else to work from the back: " << endl;
cin >> choice;
cin.getline(junk, MaxTextLen);
if (toupper(choice) == ListFront) {
return true;
}
return false;
}
// read a name from the user
// and store it in the parameter provided
void getName(string &name)
{
char text[MaxTextLen];
cout << "Please enter the name of the person or organization" << endl;
cin.getline(text, MaxTextLen);
name = text;
}
// read a number from the user
// and store it in the parameter provided
void getNumber(string &number)
{
char text[MaxTextLen];
cout << "Please enter the phone number of the person or organization" << endl;
cin.getline(text, MaxTextLen);
number = text;
}
// display the list of valid commands
void printCommands()
{
cout << "Enter " << (char)(HelpCmd) << " to print this menu,\n";
cout << " or " << (char)(InsertCmd) << " to insert a new phone book entry,\n";
cout << " or " << (char)(PrintCmd) << " to print the phone book contents,\n";
cout << " or " << (char)(LookupCmd) << " to lookup a phone number,\n";
cout << " or " << (char)(EditCmd) << " to edit someone\'s phone number,\n";
cout << " or " << (char)(RemoveCmd) << " to search for and remove a phone book entry,\n";
cout << " or " << (char)(ExtractCmd) << " to remove the first or last phone book entry,\n";
cout << " or " << (char)(QuitCmd) << " to quit,\n" << endl;
}
// read and return a valid single-character command
// limits to one command per line
// (anything beyond the first command is discarded)
Command getCommand()
{
char cmd = QuitCmd;
char junk[MaxTextLen]; // used to discard rest of line
do {
cout << "Please enter a command: ";
cin >> cmd;
cin.getline(junk, MaxTextLen);
cmd = toupper(cmd);
switch (cmd) {
case HelpCmd: return HelpCmd;
case InsertCmd: return InsertCmd;
case PrintCmd: return PrintCmd;
case LookupCmd: return LookupCmd;
case EditCmd: return EditCmd;
case RemoveCmd: return RemoveCmd;
case ExtractCmd: return ExtractCmd;
case QuitCmd: return QuitCmd;
default:
cout << "Invalid command entered: " << cmd << endl;
cout << "Please try again" << endl;
cmd = InvalidCmd;
break;
}
} while (cmd == InvalidCmd);
return InvalidCmd;
}
// process a command and update the name/number list
void processCommand(Command cmd, LList &phoneBook)
{
string name, number;
bool atFront;
switch (cmd) {
case HelpCmd:
printCommands();
break;
case InsertCmd:
getName(name);
getNumber(number);
atFront = pickEnd();
cout << "Insert attempt (";
cout << name << ":" << number << ")" << endl;
if (phoneBook.insertEntry(name, number, atFront)) {
cout << "...succeeded" << endl;
} else {
cout << "...failed" << endl;
}
break;
case PrintCmd:
cout << "Phone book contents:" << endl;
phoneBook.displayEntries();
break;
case LookupCmd:
getName(name);
cout << "Lookup attempt for " << name << endl;
if (phoneBook.lookupEntry(name, number)) {
cout << "...number is " << number << endl;
} else {
cout << "...no entry found" << endl;
}
break;
case EditCmd:
getName(name);
getNumber(number);
cout << "Edit attempt for " << name << endl;
if (phoneBook.changeEntry(name, number)) {
cout << "...new number is " << number << endl;
} else {
cout << "...no entry found" << endl;
}
break;
case RemoveCmd:
getName(name);
cout << "Attempting to remove entry for " << name << endl;
if (phoneBook.deleteEntry(name)) {
cout << "...succeeded" << endl;
} else {
cout << "...failed - no entry found" << endl;
}
break;
case ExtractCmd:
atFront = pickEnd();
cout << "Extracting element from phonebook end\n";
if (phoneBook.removeFrom(name, number, atFront)) {
cout << "...removed " << name << ":" << number << endl;
} else {
cout << "...failed, list is empty" << endl;
}
break;
case QuitCmd:
// no action required
break;
default:
cout << "Invalid command supplied, please try again\n";
printCommands();
break;
}
}
|
Recommended development sequence
Again, I strongly advise you follow a well-thought out sequence of development steps in completing the exercise.
PHASE 0: set up the files
PHASE I: study the definition of the LList class
Study LList.h, noting the definition of the structs (with pointers to next and prev), the fields of the class (including pointers to front and back), and the various methods.
PHASE II: implement skeletons for the LList methods
This involves just getting empty bodies created in LList.C for all the class methods.
LList::LList()
{
}
Note that, unlike labex1, we now are maintaining pointers to both the front and back of the list.
Note that for the private lookupEntry method you will also need
to tell the compiler where the keyValue struct is defined,
so that method definition becomes:
LList::keyValue* LList::lookupEntry(string key)
(The LList:: is not needed before any of the other methods' return types, since they are all types that the compiler already recognizes: bool, int, void, etc.)
PHASE III: implement the basic LList methods
These will work much like they did in labex1, except some tweaks since it is now part of a class and we have back and prev to deal with.
For insert, at first just worry about inserting at the front of the list:
The public version can simply call the private one.
If the private one returns null, the public one returns false.
Otherwise, the public one copies the data value out of
the struct returned by the private one, and returns true.
The private version starts at the front of the list and scans until it finds what it's looking for (and returns the pointer) or it hits the end of the list (and returns null).
changeEntry would call the private lookup, and if that returns null just return false, otherwise update the value field and return true.
Now let's finish off the implementation of insertEntry:
The list isn't allowed to hold duplicates, so before inserting
we should really check that the key isn't anywhere in the list.
To do this we can simply call the private lookupEntry on the key value, and if it returns true then simply return false instead of performing the insert.
PHASE IV: implement the deleteEntry method
This is a little trickier now that it is a doubly-linked list, with tracking of both back and front.
In addition to the general case where the item is somewhere in the middle of the list, we also have to deal with special cases where the element deleted is (i) the only thing in the list, (ii) the front thing in the list, or (iii) the back thing in the list.
PHASE V: implement the removeFrom method
This deals with removing the first or last item specifically, rather than searching for an item by its key.
PHASE VI: use removeFrom to finish the destructor
PHASE VII: complete the insertFromFile routine
Since this routine just relies on calls to
insertEntry, this should actually be identical
to the working solution from labex1.
Get this working, clean things up, and labex2 is done!
Submission mechanism
All the code for the assignment must be in a single file named LList.C (correct spelling and capitalization is essential for the submission to work correctly).
To submit the assignment, cd to the directory that contains your LList.C file and type the following command:
/home/faculty/wesselsd/bin/submit 161 LList.C
Marking guidelines:
Marks will be based on:
Code standards:
The submission must follow the code standards for labex1, plus the following standards for classes:
|