In the rest of this lab you will help build such a list clas

In the rest of this lab, you will help build such a list class. The class definition is stored in intlist.h - please study it to know its parts:

The public declarations show what a client program can do with an IntList object. Notice, however, that the list node structure definition is in the private area. Clients can\'t directly use or even refer to such nodes, but all that clients should care about are the values stored in these nodes anyway! Also notice that every list object will have one node pointer, to point at the first node in the list or at 0 if the list is empty.

Now look at intlist.cpp. All but sum, contains, max, average and insertFirst are already done. You will implement those five methods in Step 4. The other parts are implemented at the bottom of the file - do not change what is done.

An application file would create IntList objects and use them to solve problems. For this lab, our application is just a testing program - testlist.cpp - and you should look at that file next. Two IntList objects are created; then numbers read from the command line are appended to one of the lists; and finally the methods are tested for each list.

You can use this Makefile to help you complile the program. If you store all four of these files in the same directory, then you just type \"make\" (without the quotes) to compile them and create the executable program.

Step 4: Implement five linked list functions

First: switch roles between pilot and navigator if you did not already do that. Always stay logged into the original pilot\'s account.

You should be able to run the program now (assuming you compiled it in Step 3) - it requires you to enter a starter list of integers on the command line:

Next time we\'ll run it properly. The contains method is checked for three values that ought to be in the list, plus one value that should not (the sum). Here is a sample run with initial values of 5, 7, 9 and 11:

See that append, print and count all work. But the others need to be fixed.

Use an editor (e.g., emacs) to make the following changes to intlist.cpp - do not change any of the other files.

Fix the comment at the top to show your name(s) and the date.

Implement the sum method. See the count method for guidance.

Save, and then test your sum implementation - compile and execute testlist again. Verify sum is working before going on.

Then implement the contains method, save again and test again.

Continue with the other three functions in the same way: implement and test one at time.

Here are correct results for the same sample data as above:

FILES:

Solution

#include \"IntList.h\"
#include <iostream>
using std::cout;

// return sum of values in list
int IntList::sum() const {
int result = 0;
Node *n = first;
while (n) {
result+= n->info;
n = n->next;
}
return result;

}

// returns true if value is in the list; false if not
bool IntList::contains(int value) const {
Node *n = first;
while (n) {
if(n->info == value) return true;
n = n->next;
}
return false; // REPLACE THIS NON-SOLUTION
}

// returns maximum value in list, or 0 if empty list
int IntList::max() const {
int result = 0;
if(IntList::count() == 0) return result;
Node *n = first;
while (n) {
if(n->info > result)
result = n->info;
n = n->next;
}
return result;
  
}

// returns average (arithmetic mean) of all values, or
// 0 if list is empty
double IntList::average() const {
float result = 0.0;
if(IntList::count() == 0) return result;
Node *n = first;
while (n) {
result+= n->info;
n = n->next;
}
return result/IntList::count();
}

// inserts value as new node at beginning of list
void IntList::insertFirst(int value) {
// IMPLEMENT

Node *n = new Node;
n->info = value;
n->next = first;
  
first = n;

}

// DO NOT CHANGE ANYTHING BELOW (READ IT THOUGH)

// constructor sets up empty list
IntList::IntList() : first(0) { }

// destructor deletes all nodes
IntList::~IntList() {
Node *n = first;
while (n) {
Node *garbage = n;
n = n->next;
delete garbage;
}
}

// append value at end of list
void IntList::append(int value) {
if (first == 0) { // empty list
first = new Node;
first->info = value;
first->next = 0;
}
else {
Node *n = first;
while (n->next) // not last node yet
n = n->next;
n->next = new Node;
n->next->info = value;
n->next->next = 0;
}
}

// print values enclose in [], separated by spaces
void IntList::print() const {
Node *n = first;
cout << \'[\';
while (n) {
cout << n->info;
if (n->next)
cout << \" \";
n = n->next;
}
cout << \']\';
}

// return count of values
int IntList::count() const {
int result = 0;
Node *n = first;
while (n) {
++result;
n = n->next;
}
return result;
}