hi

this hw have four files:

1. for the main program

2. listp.cpp (the source file)

3. listp.h (the header file)

4. exception.h

if there is anybody who could help me with this hw i really appreciate

his help.

thanks for anybody in advance

#include <iostream>

#include <limits.h>

using std::cin;

using std::cout;

using std::endl;

using namespace std;

#define NumCities 5

#define MaxFib 100

#include "Exceptions.h"

#include "ListP.h"

#include "ListP.cpp"

void List::enterList()

// Prompt the user to enter integer values from the keyboard. Each

// value is inserted into the list. When the user enters -1, input

// from the keyboard stops. Adds the new values to the beginning of

// the current contents of list, if any.

{

ListItemType val;

int count = 1;

do

{

cout << "Enter value (-1 to end): " << count << endl;

cin >> val;

if (val != -1)

insert(count, val);

count++;

}

while (val != -1);

}

int fib(int n)

// Returns the nth Fibonacci number. The result is computed

// recursively. Does no error checking. What is the largest number

// you can compute this way?

int fib2(int n, int F[])

// Returns the nth Fibonacci number. The result is computed

// recursively. Does not compute any number more than once and uses

// the array F[] to store previously computed numbers. Does no error

// checking. What is the largest number you can compute this way?

void testFib()

// Helper function that prompts the user to enter an integer n, and

// prints the nth Fibonacci number.

{

int n;

cout << "enter n: " << endl;

cin >> n;

cout << fib(n) << endl;

}

void testFib2()

// Helper function that prompts the user to enter an integer n, and

// prints the nth Fibonnaci number.

{

int F[MaxFib];

int n;

for (int i = 0; i < MaxFib; i++)

F[i] = -1;

cout << "enter n: " << endl;

cin >> n;

cout << fib2(n,F) << endl;

}

int sum (int list[], int left, int right)

// Returns the sum of the numbers in array list, starting at index

// left and ending at index right. The sum is computed recursively.

void testSum()

// Function to test the sum function

{

int list[99999];

int i = 0;

int x;

cout << "Enter numbers, enter -1 to stop" << endl;

do

{

cin >> x;

if (x != -1)

list[i++] = x;

} while (x != -1);

cout << "The sum is " << sum(list,0,i-1) << endl;

cout << endl;

}

int multiply(int m, int n)

// Returns the product of m and n. The result is computed

// recursively. Assumes that m and n are positive integers, uses no

// loops or multiplication, and does no error checking.

void testMultiply()

// Function to test the multiply function.

{

int x,y;

cout << "Enter a number:" << endl;

cin >> x;

cout << "Enter a number:" << endl;

cin >> y;

cout << "The product of " << x << " and " << y << " is " <<

multiply(x,y) << endl;

}

bool findPathRecursive(int originCity, int destinationCity, bool

visited[],

int edge[][NumCities])

// Returns true if a path from originCity to destinationCity exists in

// the graph defined by edge. Paths are found using the following

// recursive algorithm: to find a path from city i to city j, check

// whether there is a path from any cities k, which are neighbors of

// i, to j. If a path exists, prints it in any order. This function

// does not use any stacks or queues.

void testFindPathRecursive()

// Helper function that prompts the user to enter source and

// destination cities, and then uses findPathRecursive to determine if

// a path exists in the graph from source to destination.

{

int edge[NumCities][NumCities] = {{0,1,0,0,0},

{0,0,1,1,0},

{0,0,0,0,1},

{0,1,0,0,0},

{0,0,0,0,0}};

int originCity, destinationCity, i;

bool visited[NumCities];

for (i = 0; i < NumCities; i++)

visited[i] = false;

cout << "Enter origin city: ";

cin >> originCity;

cout << "Enter destination city: ";

cin >> destinationCity;

if (!findPathRecursive(originCity, destinationCity, visited, edge))

cout << "No path found" << endl;

}

bool subsetSum(List aList, int sum)

// Return true if some subset of the integers stored in aList add up

// to sum. Uses recursion.

void testSubsetSum()

{

List aList;

int num;

cout << "Enter list values" << endl;

aList.enterList();

cout << "Enter a target sum" << endl;

cin >> num;

cout << "Result: " << subsetSum(aList, num) << endl;

}

int main()

{

int choice;

do

{

cout << "1. fib" << endl;

cout << "2. fib2" << endl;

cout << "3. multiply" << endl;

cout << "4. sum" << endl;

cout << "5. findPathRecursive" << endl;

cout << "6. subsetSum" << endl;

cout << "Enter a number, or -1 to exit: ";

cin >> choice;

switch (choice)

{

case 1:

testFib();

break;

case 2:

testFib2();

break;

case 3:

testMultiply();

break;

case 4:

testSum();

break;

case 5:

testFindPathRecursive();

break;

case 6:

testSubsetSum();

break;

}

} while (choice != -1);

}

// ************************************************** *******

// Header file ListP.h for the ADT list.

// Pointer-based implementation.

// ************************************************** *******

// Must define ListItemType before compilation

#ifndef ListP_h

#define ListP_h

#include "Exceptions.h"

typedef int ListItemType;

class List

{

public:

// constructors and destructor:

List(); // default constructor

List(const List& aList); // copy constructor

~List(); // destructor

// list operations:

bool isEmpty() const;

int getLength() const;

void insert(int index, ListItemType newItem)

throw(ListIndexOutOfRangeException, ListException);

void remove(int index)

throw(ListIndexOutOfRangeException);

void retrieve(int index, ListItemType& dataItem) const

throw(ListIndexOutOfRangeException);

void enterList();

private:

struct ListNode // a node on the list

{

ListItemType item; // a data item on the list

ListNode *next; // pointer to next node

}; // end struct

int size; // number of items in list

ListNode *head; // pointer to linked list of items

ListNode *find(int index) const;

// Returns a pointer to the index-th node

// in the linked list.

}; // end class

// End of header file.

#endif

// ************************************************** *******

// Implementation file ListP.cpp for the ADT list.

// Pointer-based implementation.

// ************************************************** *******

#include "ListP.h"

#include "Exceptions.h"

List::List(): size(0), head(NULL)

{

} // end default constructor

List::List(const List& aList): size(aList.size)

{

if (aList.head == NULL)

head = NULL; // original list is empty

else

{

// copy first node

head = new ListNode;

assert(head != NULL); // check allocation

head->item = aList.head->item;

// copy rest of list

ListNode *newPtr = head; // new list pointer

// newPtr points to last node in new list

// origPtr points to nodes in original list

for (ListNode *origPtr = aList.head->next;

origPtr != NULL;

origPtr = origPtr->next)

{

newPtr->next = new ListNode;

assert(newPtr->next != NULL);

newPtr = newPtr->next;

newPtr->item = origPtr->item;

} // end for

newPtr->next = NULL;

} // end if

} // end copy constructor

List::~List()

{

while (!isEmpty())

remove(1);

} // end destructor

bool List::isEmpty() const

{

return bool(size == 0);

} // end isEmpty

int List::getLength() const

{

return size;

} // end getLength

List::ListNode *List::find(int index) const

// --------------------------------------------------

// Locates a specified node in a linked list.

// Precondition: index is the number of the

// desired node.

// Postcondition: Returns a pointer to the desired

// node. If index < 1 or index > the number of

// nodes in the list, returns NULL.

// --------------------------------------------------

{

if ( (index < 1) || (index > getLength()) )

return NULL;

else // count from the beginning of the list

{

ListNode *cur = head;

for (int skip = 1; skip < index; ++skip)

cur = cur->next;

return cur;

} // end if

} // end find

void List::retrieve(int index,

ListItemType& dataItem) const

throw (ListIndexOutOfRangeException)

{

if ((index < 1) || (index > getLength()))

throw ListIndexOutOfRangeException(

"ListOutOfRangeException: retrieve index out of range");

else

{

// get pointer to node, then data in node

ListNode *cur = find(index);

dataItem = cur->item;

} // end if

} // end retrieve

void List::insert(int index, ListItemType newItem)

throw(ListIndexOutOfRangeException, ListException)

{

int newLength = getLength() + 1;

if ((index < 1) || (index > newLength))

throw ListIndexOutOfRangeException(

"ListOutOfRangeException: insert index out of range");

else

{

// create new node and place newItem in it

ListNode *newPtr = new ListNode;

if (newPtr == NULL)

throw ListException(

"ListException: insert cannot allocate memory");

else

{

size = newLength;

newPtr->item = newItem;

// attach new node to list

if (index == 1)

{

// insert new node at beginning of list

newPtr->next = head;

head = newPtr;

}

else

{

ListNode *prev = find(index-1);

// insert new node after node

// to which prev points

newPtr->next = prev->next;

prev->next = newPtr;

} // end if

} // end if

} // end if

} // end insert

void List::remove(int index)

throw(ListIndexOutOfRangeException)

{

ListNode *cur;

if ((index < 1) || (index > getLength()))

throw ListIndexOutOfRangeException(

"ListOutOfRangeException: remove index out of range");

else

{

--size;

if (index == 1)

{

// delete the first node from the list

cur = head; // save pointer to node

head = head->next;

}

else

{

ListNode *prev = find(index-1);

// delete the node after the

// node to which prev points

cur = prev->next; // save pointer to node

prev->next = cur->next;

} // end if

// return node to system

cur->next = NULL;

delete cur;

cur = NULL;

} // end if

} // end remove

// ************************************************** *******

// File Exceptions.h containing declarations of List and Stack

// Exceptions.

// ************************************************** *******

#ifndef Exceptions_h

#define Exceptions_h

#include <string>

#include <exception>

using namespace std;

class ListException

{

public:

ListException(const string &m = "")

{ message = m;}

string what() {return message;}

private:

string message;

}; // end ListException

class ListIndexOutOfRangeException

{

public:

ListIndexOutOfRangeException(const string &m = "")

{ message = m;}

string what() {return message;}

private:

string message;

}; // end ListIndexOutOfRangeException

class StackException

{

public:

StackException(const string & m="")

{ message = m;}

string what() {return message;}

private:

string message;

}; // end StackException

class QueueException

{

public:

QueueException(const string & m="")

{ message = m;}

string what() {return message;}

private:

string message;

}; // end QueueException

#endif