I'm very confused. I'm suposed to expand this pointer-based list class in this program by setting ListItemType to int then adding methods to find the smallest number, the largest number, and the average of the list. Before I added the findLargest function the program would compile but, when ran, gave the message "ABNORMAL PROGRAM TERMINATION." I know my findAverage and findLargest functions have problems but I'm not sure how to properly implement them. Any tips/advice/suggestions would be appreciated.

* ADT list - Pointer-based implementation. */
class List
{
public:
// Constructors and destructor:

   /** Default constructor. */
   List();

   /** Copy constructor.
    * @param aList The list to copy. */
   List(const List& aList);

   /** Destructor. */
   ~List();

// List operations:
   bool isEmpty() const;
   int getLength() const;
   void insert(int index, const ListItemType& newItem)
      throw(ListIndexOutOfRangeException, ListException);
   void remove(int index)
      throw(ListIndexOutOfRangeException);
   void retrieve(int index, ListItemType& dataItem) const
      throw(ListIndexOutOfRangeException);
   float getAverage(int index, ListItemType& dataItem);
   int findLargest(int index, ListItemType& dataItem);
   int findSmallest(int index, ListItemType& dataItem);

private:
   /** A node on the list. */
   struct ListNode
   {
      /** A data item on the list. */
      ListItemType item;
      /** Pointer to next node. */
      ListNode    *next;
   }; // end ListNode

   /** Number of items in list. */
   int       size;
   /** Pointer to linked list of items. */
   ListNode *head;

   /** Locates a specified node in a linked list.
    * @pre index is the number of the desired node.
    * @post None.
    * @param index The index of the node to locate.
    * @return A pointer to the index-th node. If index < 1
    *         or index > the number of nodes in the list,
    *         returns NULL. */
   ListNode *find(int index) const;
}; // end List
// End of header file.
/** @file ListP.cpp
 *  ADT list - Pointer-based implementation. */

#include <cstddef>     // for NULL
#include <new>         // for bad_alloc
#include "ListP.h"     // header file

using namespace std;

// definitions of methods follow:
//   . . .

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;
      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;
         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 size == 0;
}  // end isEmpty


int List::getLength() const
{
   return size;
}  // end getLength


List::ListNode *List::find(int index) const
{
   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(
         "ListIndexOutOfRangeException: 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, const ListItemType& newItem)
   throw(ListIndexOutOfRangeException, ListException)
{
   int newLength = getLength() + 1;

   if ( (index < 1) || (index > newLength) )
      throw ListIndexOutOfRangeException(
         "ListIndexOutOfRangeException: insert index out of range");
   else
   {  // try to create new node and place newItem in it
      try
      {
         ListNode *newPtr = new ListNode;
         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 try
      catch (bad_alloc e)
      {
         throw ListException(
            "ListException: memory allocation failed on insert");
      }  // end catch
   }  // end if
}  // end insert


void List::remove(int index) throw(ListIndexOutOfRangeException)
{
   ListNode *cur;

   if ( (index < 1) || (index > getLength()) )
      throw ListIndexOutOfRangeException(
         "ListIndexOutOfRangeException: 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


float List::getAverage(int index, ListItemType& dataItem)
{
  cout << "getAverage called." << endl;
  int total = 0;

  for(int i = 0; i , index; i++){
    total += dataItem;
  }
  return total/index;
} // end getAverage


int List::findLargest(int index, ListItemType& dataItem)
{
  ListNode *prev = head;
  ListNode *cur = prev -> next;
  int largest;

  for(int i = 0; i < index; i++){
    if(prev -> next > cur -> dataItem){
      largest = prev -> next;
    }
  }
  return largest;
} // end findLargest


void main()
{
  List alst;
  int mydata, i;

  for( i = 0; i < 3; i++){
    alst.insert( i, mydata + i);
  }
  cout << alst.getAverage( i, mydata);
};

start quote:

int List::findLargest(int index, ListItemType& dataItem)
{
  ListNode *prev = head;
  ListNode *cur = prev -> next;
  int largest;

  for(int i = 0; i < index; i++){
    if(prev -> next > cur -> dataItem){
      largest = prev -> next;
    }
  }
  return largest;
} // end findLargest

end quote.

if(prev -> next > cur -> dataItem){

shouldn't even compile. Your algorithm does NOT do what you think. Initialize largest with a "meaningful low" value:

int largest = (std::numeric_limits<int>::min)();

then traverse your nodes and if a node's value is larger than the value of largest, replace the value of largest with this value. For finding the smallest value, initialize

int smallest = (std::numeric_limits<int>::max)();

and replace it if the value of the current visited node is bigger tha the value of smallest.

Edited 3 Years Ago by mike_2000_17: Fixed formatting

what is this???

for(int i = 0; i , index; i++)
{
    total += dataItem;
  }

Why that ','

Sorry. When I did the original post I forgot to comment this out. I know it doesn't work as is. My intention was to attempt to translate this into a pointer-based function to match the rest of the program.

if(prev -> next > cur -> dataItem){

shouldn't even compile. Your algorithm does NOT do what you think. Initialize largest with a "meaningful low" value:

int largest = (std::numeric_limits<int>::min)();

then traverse your nodes and if a node's value is larger than the value of largest, replace the value of largest with this value. For finding the smallest value, initialize

int smallest = (std::numeric_limits<int>::max)();

and replace it if the value of the current visited node is bigger tha the value of smallest.

Again, sorry that I wasn't clearer in my original post. No, this function doesn't compile which is why I need your guidance. I can do the method fine without pointers. When I start working WITH pointers I get myself VERY confused.

This article has been dead for over six months. Start a new discussion instead.