472,794 Members | 2,173 Online

# help needed c++

hi
this hw have four files:
1. for the main program
2. listp.cpp (the source file)
4. exception.h
if there is anybody who could help me with this hw i really appreciate
his help.

#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);
}

// ************************************************** *******
// 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 *find(int index) const;
// Returns a pointer to the index-th node

}; // end class

#endif

// ************************************************** *******
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// ************************************************** *******

#include "ListP.h"
#include "Exceptions.h"

{
} // end default constructor

List::List(const List& aList): size(aList.size)
{
head = NULL; // original list is empty
else
{
// copy first node
assert(head != NULL); // check allocation

// 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

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
{

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
}
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
}

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

Jul 23 '05 #1
5 2019
jh*******@gmail.com wrote:
hi
this hw have four files:
1. for the main program
2. listp.cpp (the source file)
4. exception.h
if there is anybody who could help me with this hw i really appreciate
his help.

What kind of help are you looking for? You need to define the problem
you're trying to solve. Please don't make us guess it from the code
you posted (it's good that you posted it, BTW).

V
Jul 23 '05 #2
hi
iam sorry for not mentioning but iam trying to find someone to give me
some solution because all the files are correct but the program.cpp
that should be fixed
thank you

Jul 23 '05 #3
jhon02148 wrote:

hi
iam sorry for not mentioning but iam trying to find someone to give me
some solution because all the files are correct but the program.cpp
that should be fixed

Fixed because of *what*?

What happens:
Do you get a compiler error?
If yes, which one and at which line number

Does the program compile, but does it crash during runtime?
In that case, fire up your debugger and figure out *where*
it crashed. Once you know *where* it crashes, the time has
come to think of reasons *why* it crashes at that position.
--
Karl Heinz Buchegger
Jul 23 '05 #4
the only problem that i have. i couldnt figure out how to start this
thank you
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;

}

Jul 23 '05 #5
jhon02148 wrote:

the only problem that i have. i couldnt figure out how to start this
thank you
bool subsetSum(List aList, int sum)
// Return true if some subset of the integers stored in aList add up
// to sum. Uses recursion.

very same with paper and pencil.

Say I give you that list

6 8 2 10 7

And then I ask: Is there a subset in this list that sums
up to 18?
Why? How did you come to that conclusion? What steps
did you take? (Note: The answer: "Because I looked at it
and saw it" is not an allowed. You need to give a cookbook
that even the dumbest person on earth can follow and get
to the same conclusion then you).

Note: If a recursion is required with lists, it is often
a good idea, to divide the list into 2 parts:
* the first element
* the rest of the list
The recursion then operates on the 'rest of list part'.

Hint2: For a moment forget about the 'sum of to something
part'. Can you write a (recursive function) that generates
all possible subsets of a given list? If you can do that,
the extension to 'does one of the subsets sum up to x'
should be fairly easy.

--
Karl Heinz Buchegger