This short assignment is to implement some functions that operate on C++ linked lists. You will need to write a few specific functions. A little interactive test program is provided to test your code.
Complete the implementation of the five functions longestRun, removeMultiplesOf3, insertMiddle, and merge. The complete specification for these functions (i.e., prototypes + function comments) is given in ecListFuncs.h. You put your implementations of these functions in ecListFuncs.cpp.
We provided a Makefile; to compile the code use the command:
make ectest
Make sure you are not wasting resources. For example, don't implement what should be an O(n) function in O(n 2 ), and make sure there are no memory leaks, e.g., by doing unnecessary calls to new, or not reclaiming memory no longer needed. There are a few additional restrictions on how you must complete merge -- see function comments for details.
Note: The completed versions of your functions should not print anything.
ecListFunds.h
// ecListFuncs.h
// You do not need to modify or submit this file.
#ifndef LIST_FUNCS_H
#define LIST_FUNCS_H
//*************************************************************************
// Node type used for lists
struct Node {
int data;
Node *next;
Node(int item);
Node(int item, Node *n);
};
typedef Node * ListType;
//*************************************************************************
// Utility functions used by the test driver code
// (these are defined in ectest.cpp)
// makes list into an empty list
// reclaiming memory used by nodes
// PRE: list is a well-formed list
// POST: list' is NULL
void clearList(Node * &list);
// prints list elements, space separated, ending with 'n'
// prints empty list as ""
// PRE: list is a well-formed list
void printList(Node *list);
//*************************************************************************
// Functions you need to write for this assignment:
// (implementations go in ecListFuncs.cpp)
/*
* longestRun
* A run is several adjacent nodes that have the same value.
*
* PRE: list is a well-formed list with at least one node
*
* After the function runs:
* maxRunVal will contain the value that occurred in the longest run
* maxRunLen will contain the length of that run
* If there are multiple sequences of the max length, it will return the value for the first one
* (see Examples 1 and 3 below).
* maxRunVal maxRunLen
* Example1: list = (3 0 -10) 3 1
* Example2: list = (3 7 5 0 0 9) 0 2
* Example3: list = (5 5 5 2 2 2 9 9 9) 5 3
* Example3: list = (3) 3 1
* Example4: list = (7 7 2 2 2 2 4 4 4) 2 4
* Example5: list = (7 7 3 3 7 7 7) 7 3
*/
void longestRun(ListType list, int & maxRunVal, int & maxRunLen);
/*
* removeMultiplesOf3
*
* PRE: list is a well-formed list.
*
* removes all all of the multiples of 3 from the list
*
* Examples:
* list before call list after call
* () ()
* (6 2 3 3 7 12) (2 7)
* (3 6 9 12) ()
* (1 5 1 7) (1 5 1 7)
*/
void removeMultiplesOf3(ListType & list);
/*
* insertMiddle
*
* PRE: list is a well-formed list.
*
* inserts midVal at the middle of the list
* If the list has an odd number of values beforehand, it will go just left of the middle.
*
* Examples:
* list before call midVal list after call
* (1 1 1 1 1 1) 6 (1 1 1 6 1 1 1)
* (1 1 1 1 1) 6 (1 1 6 1 1 1)
* () 32 (32)
* (10) 5 (5 10)
* (1 17) 85 (1 85 17)
*/
void insertMiddle(ListType & list, int midVal);
/*
* merge
*
* PRE: list1 and list2 are well-formed lists such that each one is
* a list of unique values in increasing order
*
* returns a list of unique values in increasing order that has all the values
* of the original lists. list1 and list2 are undefined after this operation.
*
* Note1: this is required to be a destructive merge: the new list will be made up of nodes of
* the original list, so this function will not call new or delete, except for the case
* mentioned in Note2.
*
* Note2: If list1 and list2 have any values in common, only one of these will end up in the
* result list and you must reclaim memory for the other one. (see ***'d examples below)
*
* Note3: your code must use the O(n+m) merge algorithm (discussed in lecture on 10/1)
*
* Examples:
* list1 before call list2 before call merge(list1, list2)
*
* (2 4 6) (1 3 5) (1 2 3 4 5 6)
* (1 2 3 4 5) (6 7 8) (1 2 3 4 5 6 7 8)
* (2 4 6 8 10 12) (3 6 9 12) (2 3 4 6 8 9 10 12) ***
* (3 4 5) (3 4 5) (3 4 5) ***
* (1 2 3 4 5) () (1 2 3 4 5)
* () () ()
* () (1 2 3 4 5) (1 2 3 4 5)
*/
ListType merge(ListType list1, ListType list2);
//*************************************************************************
#endif
ectest.cpp
// ectest.cpp
/*
* A console-based interactive program you can use to test your list functions.
* To run the program: ectest
*
* Note: this uses separate compilation. You put your code in ecListFuncs.cpp
* Code in this file calls those funcs.
* You do not need to modify or submit this file.
*/
#include
// for istringstream
#include
#include "ecListFuncs.h"
using namespace std;
int promptForInt (string prompt);
void buildList(ListType & theList);
void doHelp();
void doLastIndexOf(ListType list);
bool readAndDispatchCommand(ListType & theList);
void doMerge(ListType & list);
void doLongestRun(ListType list);
//*************************************************************************
/* a little test program */
int main ()
{
bool keepgoing = true;
ListType theList = NULL;
doHelp();
do {
keepgoing = readAndDispatchCommand(theList);
cout << "The list: ";
printList (theList);
} while (keepgoing);
return 0;
}
/*
* reads a command and executes it.
* The command execution updates and/or uses theList, thus it's passed
* by reference here.
* Returns false iff the command entered was q (quit)
*/
bool readAndDispatchCommand(ListType & theList) {
char cmd;
cout << "nPlease enter a command [b, l, r, i, m, p, h, q]: ";
cin >> cmd;
if (cmd == 'b') {
clearList(theList);
cout << "Please enter a sequence of zero or more ints followed by(e.g:1 2 3): ";
buildList(theList);
}
else if (cmd == 'l') {
doLongestRun(theList);
}
else if (cmd == 'r') {
removeMultiplesOf3(theList);
}
else if (cmd == 'i') {
int val = promptForInt("Value to insert");
insertMiddle(theList, val);
}
else if (cmd == 'm') {
doMerge(theList);
}
else if (cmd == 'p') {
cout << "Print list: " << endl;
printList(theList); cout << endl;
}
else if (cmd == 'q') {
return false;
}
else {
if (cmd != 'h') { cout << "ERROR: invalid command" << endl; }
doHelp();
}
return true;
}
/*
* promptForInt: Prompts for and reads an integer.
*/
int promptForInt (string prompt)
{
int value;
cout << prompt << ": ";
cin >> value;
return value;
}
// read input from the user to build a list.
// input will be a space separated list of numbers all on one line.
// old value of theList is destroyed.
// (needs to be O(n))
// Note: this code uses istringstream: this is the analogous feature
// to using a Scanner on a String in Java.
void buildList(ListType & theList) {
string lineStr;
getline(cin, lineStr); // consume rest of previous line
getline(cin, lineStr);
if (lineStr.empty()) {
theList = NULL;
return;
}
istringstream istr(lineStr);
Node *last = NULL;
int i;
istr >> i; // first one is a special case
theList = new Node(i);
last = theList;
while (istr >> i) { // comes out false if we reach end of string (i.e., eoln)
last->next = new Node(i);
last = last->next;
}
}
// prints out a command summary
void doHelp() {
cout << "Valid commands are" << endl;
cout << " b(uild new list), l(ongest run), r(emove multiples of 3),"
<< endl;
cout << " i(nsert middle), m(erge), " << endl;
cout << " p(rint), h(elp), q(uit)." << endl;
}
// run longestRun on list, and print results
void doLongestRun(ListType list) {
if (list == NULL) {
cout << "ERROR: list must be non-empty." << endl;
return;
}
int maxRunVal;
int maxRunLen;
longestRun(list, maxRunVal, maxRunLen);
cout<< "The longest run is of the value " << maxRunVal;
cout << ", occuring " << maxRunLen << " times in sequence." << endl;
}
// prompt for a second list, and run merge on list and the other list
// list will be updated to be the merged list.
void doMerge(ListType & list) {
ListType list2 = NULL;
cout << "Note this will only work with two lists in increasing order with no duplicates." << endl;
cout << "Enter the values for the other list as" << endl;
cout << "a sequence of zero or more ints followed by(e.g:1 2 3): ";
buildList(list2);
list = merge(list, list2);
}
//*****************************************************************
// utility list funcs and Node methods
// (Note: prototypes and comments for these functions are in ecListFuncs.h)
void printList(ListType list) {
if (list == NULL) {
cout << "";
}
Node *p = list;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void clearList(ListType &list) {
Node *rest = list;
while (list != NULL) {
rest = list->next; // rest is all but the first element
delete list; // reclaims one node only
list = rest;
}
}
Node::Node(int item) {
data = item;
next = NULL;
}
Node::Node(int item, Node *n) {
data = item;
next = n;
}