CSCI 161 lab exercise 1: linked lists, file i/o, command line arguments, and seperate compilation

list.C tips

The lab exercise 1 is to be submitted electronically by 10am January 21st, and covers the work from the first two lab sessions (Jan. 7-9, 14-16), suitably cleaned up to adhere to standards. The submission mechanism is detailed below, and must be followed to obtain credit for the lab.

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:

In this lab you will create a mechanism to store a collection of names/phone numbers using a linked list, including the ability to read the collection in from a file supplied as a command line argument.

Ultimately, your program will be able to:

Implementation details

The C++ code will be split across three seperate files:

The labex1.C and list.h files will be provided for you, while you will be expected to write and submit the list.C file.

The code below specifies the main routine, datatypes, and function prototypes to be used by the program. It also provides implementations for a number of the supporting functions used by the main routine and the processCommands function.

Your task is to implement the remaining seven functions, placing the code in list.C:

bool insertEntry(string key, string value, keyValue* &list)
bool lookupEntry(string key, string &value, keyValue* list)
keyValue* lookupEntry(string key, keyValue* list)
bool changeEntry(string key, string &value, keyValue* list)
bool deleteEntry(string key, keyValue* &list)
void displayEntries(keyValue* list)
int insertFromFile(char filename[], keyValue* &list)
You are not to alter anything in labex1.C or list.h, and must put your implementations of those seven functions in a file named list.C.

The functions in your list.C must not require any user input (i.e. no cin, scanf, etc).

Files available here: labex1.C, list.h
// list.h
#ifndef LIST_H
#define LIST_H 

#include <string>
#include <iostream>
using namespace std;

// =========================================================
// ====== Data types and constants used in the program =====

// define the contents of a single key/value pair
struct keyValue {
   string key;      // search key
   string value;    // associated data value
   keyValue *next;  // next pair in the list
   keyValue *prev;  // previous pair in the list
};

// define a maximum length for text 
const int MaxTextLen = 256;

// =========================================================
// ====== Prototypes for student-implemented routines ======

// insertEntry
// -----------
// adds one key/value pair to the front of the list
//    as long as the key does not already appear in the list
// returns true if successful, false otherwise
bool insertEntry(string key, string value, keyValue* &list);


// lookupEntry  (internal use)
// -----------
// search the list for an entry matching the specified key,
//    return a pointer to the entry if found,
//    return null otherwise
keyValue* lookupEntry(string key, keyValue* list);


// lookupEntry  (public use)
// -----------
// search the list for an entry matching the specified key,
//    set the matching value and return true if found,
//    return false otherwise
bool lookupEntry(string key, string &value, keyValue* list);


// changeEntry
// -----------
// search the list for 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, keyValue* list);


// deleteEntry
// -----------
// 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, keyValue* &list);


// displayEntries
// --------------
// display each key/value pair in the list,
//   with one key/value pair per line of output
void displayEntries(keyValue* list);


// insertFromFile
// --------------
// 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
//     etc.
int insertFromFile(char filename[], keyValue* &list);

#endif
// labex1.C
#include "list.h"

// 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 = '-' 
             };

// =========================================================
// ====== Prototypes for provided support routines =========

// read a name from the user
//    and store it in the parameter provided
void getName(string &name);

// read a phone 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, keyValue* &phoneBook);

// =========================================================
// ====== Provided main routine ============================

int main(int argc, char* argv[])
{
   // current list of messages, initially empty
   keyValue *phoneBook = NULL;

   // 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 = insertFromFile(argv[1], phoneBook);
      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 =====

// 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 phone 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 remove a 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 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, keyValue* &phoneBook)
{
   string name, number;
   switch (cmd) {
      case HelpCmd: 
         printCommands();
         break;
      case InsertCmd: 
         getName(name);
         getNumber(number);
         cout << "Insert attempt (";
         cout << name << ":" << number << ")" << endl;
         if (insertEntry(name, number, phoneBook)) {
            cout << "...succeeded" << endl;
         } else {
            cout << "...failed" << endl;
         }
         break;
      case PrintCmd: 
         cout << "Phone book contents:" << endl;
         displayEntries(phoneBook);
         break;
      case LookupCmd:
         getName(name); 
         cout << "Lookup attempt for " << name << endl;
         if (lookupEntry(name, number, phoneBook)) {
            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 (changeEntry(name, number, phoneBook)) {
            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 (deleteEntry(name, phoneBook)) {
            cout << "...succeeded" << endl;
         } else {
            cout << "...failed - no entry found" << endl;
         }
         break;
      case QuitCmd:
         // no action required
         break;
      default: 
         cout << "Invalid command supplied, please try again\n";
         printCommands();
         break;
   }
}


Recommended development sequence

I strongly advise you follow a well-thought out sequence of development steps in completing the exercise. The set below would be a reasonable starting point:

    PHASE 0

  1. Copy labex1.C and list.h to your labex1 directory.

  2. Also in your labex1 directory, create a file named list.C and make sure it #include's "list.h"

    PHASE I

  3. For each of the functions you are required to complete, copy the prototype to your list.C file and put in an empty function body.
    For functions that return a value, simply return a default value of an appropriate type.
    Compile the program to ensure you have all the functions appropriately declared, and get it to compile cleanly.
    Don't proceed with the next phase until you are sure these are working properly.
    Note that any errors that you get are because of the code you have added (or failed to add):
    do not change anything that has been provided in the code above.

  4. Try compiling your code (note the new compilation command needed because of the seperate files):
    g++ -Wall labex1.C list.C -o labex1

  5. Implement the insertEntry, displayEntries, and keyValue* lookupEntry(...) functions, as it will be pretty difficult to proceed with any of the other functions before you get these working.
    Don't proceed with the next phase until you are sure these are working properly.

  6. Implement the bool lookupEntry(...) function, as it is the simplest out of lookup, change, and delete.
    Don't proceed with the next phase until you are sure this one is working properly.

  7. Implement the changeEntry and deleteEntry functions (in whatever order you prefer).
    Don't proceed with the next phase until you are sure this one is working properly.

    PHASE II

    Note that phase II deals entirely with the implementation of the insertFromFile function.

  8. First, get the function to simply open and close the file correctly, returning true if the file open succeeded and false otherwise.
    Don't proceed with the next phase until you are sure this one is working properly.

  9. Next, add the code to get the function to read a single key/value pair from the file and insert it in the list.
    Don't proceed with the next phase until you are sure this one is working properly.

  10. Next, get the loop working to keep reading/inserting until the end of file is detected.
    Don't proceed with the next phase until you are sure this one is working properly.

  11. Finally, test the functionality in a variety of ways and ensure the robustness of your routines:


Submission mechanism

All the code for the list functions must be in a single file named list.C (correct spelling and capitalization is essential for the submission to work correctly).

To submit the assignment, cd to the directory that contains your labex1 files and type the following command:

   /home/faculty/wesselsd/bin/submit  161  list.C
Note that each submission overwrites any previous submission you have made.


Marking guidelines:

Marks will be based on meeting all the criteria below:

Code standards:

  • The maximum width of a line, including whitespace and the final return character, is 96 characters.

  • One or two blank lines should be used to visually seperate logically distinct code segments.

  • The preferred style of bracket alignment for different control structures is illustrated below:
    for (...) {
        ...
    }
    
    while (...) {
        ...
    }
    
    do {
        ...
    } while (...);
    
    if (...) {
        ...
    } else {
        ...
    }
    
    switch (...) {
       case xxx:
          ...
          break;
       default:
          ...
          break;
    };
    

  • The preferred style of bracket alignment for function definitions is illustrated below:
    void myfunction(int someParam)
    {
        ...
    }
    

  • All indentation is to consist of levels of three or four spaces, and spaces must be used instead of tabs.

    There should be one layer of indentation for each and every level of nesting associated with an instruction, e.g.

            int main()
            {
            
                ...
                for (i = 1; i < 10; i++) {
                    ...
                    if (x < y) {
                        ...
                    } else {
                        ...
                    }
                    ...
                }
                ...
            }
            
    Layers of nesting include functions (including the main routine), loops, if/else statements, switch statements, and multiline comments.

  • Functions must be accompanied by comments explaining the purpose/use of the function. This should include necessary information about what values/ranges are acceptable as parameters, and what kind of data the function returns (if any).

    Function prototypes must also be accompanied be a brief comment describing the purpose of the function.

  • Comments should generally be used to explain either the intended behaviour of a code segment or the logic behind a code segment - comments should not simply echo code behaviour.

    As an example, the logic of the following might not be immediately obvious:

       char dig;
       cin.get(dig);
       int  val;
       val = dig - '0';
    
    The workings make more sense with some explanatory comments:
       // Get the user to type a single digit, then store it as an int
       char dig;
       cin.get(dig); // read the digit entered
    
       // subtract the ascii value of digit '0' to get the integer equiv
       int val = dig - '0'; 
    

  • All variables must be declared locally (i.e. inside the main routine or some other function) at the start of the routine, and must have meaningful/explanatory names.

    Variables should be initialized and accompanied by a short comment explaining their purpose.

  • Any hard-coded literal values that are used in multiple locations in your program should be replaced by either a constant or an enumerated type. Hard-coded values that have a high probability of being altered as a routine part of program maintenance should also be replaced by suitable constants. Both constants and enumerated types should be given meaningful/explanatory names.

  • For clarity, all arithmetic expressions should be fully parenthesized.

    Complex arithmetic expressions should either be broken into smaller, clearer steps or accompanied by suitable explanatory comments.

  • In work submitted for this course, the following language constructs are not permitted:
    • global variables (global constants are acceptable and encouraged, global variables are not)
    • goto statements
    • continue statements