Linked Lists I, Continued; Polynomial Class

Tom Kelliher, CS18

May 3, 1996

• Evaluations on Monday.
• Quiz on Monday. Material: Today's list class for the polynomial class.
• Source code for the files available straight from the homepage.

Picking up from last time...

The ADT List

Operations:

• CreateList()
• DestroyList()
• ListIsEmpty()
• ListLength()
• ListInsert(NewPosition, NewItem, Success)
• ListDelete(Position, Success)
• ListRetrieve(Position, DataItem, Success)

ListIsEmpty()

int List::ListIsEmpty(void)
{
   return list == NULL;
}

ListLength()

int List::ListLength(void)
{
   int len = 0;
   listPointer temp = list;

   while (temp != NULL)
   {
      ++len;
      temp = temp->next;
   }

   return len;
}

Tradeoffs?

ListInsert()

void ListInsert(int newPosition, int newItem)
{
   listPointer newI;

   assert (1 <= newPosition && newPosition <= ListLength() + 1);

   if (newPosition == 1)
   {
      newI = new listItem;
      assert (newI != NULL);

      newI->next = list;
      newI->value = newItem;
      list = newI;
   }
   else
   {
      listPointer temp = list;

      newI = new listItem;
      assert (newI != NULL);

      while (newPosition > 2)
      {
         --newPosition;
         temp = temp->next;
      }

      newI->next = temp->next;
      newI->value = newItem;
      temp->next = newI;
   }
}

Exercise

Try the remaining List methods on your own.

A Polynomial Class

• How can we use a linked list to represent a ``sparse'' polynomial?
• Is there anything special about this list?
• What about ``inheritance?''

Necessary files:

• list.cpp, list.h
• poly.cpp, poly.h
• main.cpp

list.h

#ifndef __LIST_H
#define __LIST_H

#include <stdlib.h>

struct ListItem
{
   ListItem* next;
   int exponent;
   double coeff;
};

typedef ListItem* ListP;

class List
{
 private:
   ListP l;

   void Copy(const List& b);
   void Free(void);

 public:
   List(void) : l(NULL) {}
   ~List();
   List(const List& b);
   const List& operator=(const List& b);
   int Insert(int exp, double co);
   int Retrieve(int exp, double& co);
   int Delete(int exp);
   void Print(void);   // For testing.
};

#endif

list.cpp

#include <iostream.h>
#include <stdlib.h>
#include <assert.h>
#include "list.h"

void List::Free(void)
{
   ListP tmp;

   while (l != NULL)
   {
      tmp = l;
      l = l->next;
      delete tmp;
   }
}

List::~List()
{
   Free();
}

void List::Copy(const List& b)
{
   ListP newCur;
   ListP bCur;

   if (b.l == NULL)
   {
      l = NULL;
      return;
   }

   l = new ListItem;
   assert (l != NULL);
   l->exponent = b.l->exponent;
   l->coeff = b.l->coeff;

   newCur = l;   // Pointer to first item on target list.
   bCur = b.l->next;   // Pointer to second item on source list.

   while (bCur != NULL)
   {
      newCur->next = new ListItem;
      assert (newCur != NULL);
      newCur= newCur->next;
      newCur->exponent = bCur->exponent;
      newCur->coeff = bCur->coeff;
      bCur = bCur->next;
   }

   newCur->next = NULL;
}

List::List(const List& b)
{
   Copy(b);
}

      
const List& List::operator=(const List& b)
{
   if (this != &b)
   {
      Free();
      Copy(b);
   }

   return *this;
}

// It's up to the user to ensure there are no duplicate exponents on
// the list.

int List::Insert(int exp, double co)
{
   ListP tmp;

   tmp = new ListItem;
   if (tmp == NULL)
      return 0;

   tmp->exponent = exp;
   tmp->coeff = co;
   tmp->next = l;
   l = tmp;

   return 1;
}

int List::Retrieve(int exp, double& co)
{
   ListP i;

   for (i = l; i != NULL; i = i->next)
      if (i->exponent == exp)
      {
         co = i->coeff;
         return 1;
      }

   return 0;
}

int List::Delete(int exp)
{
   ListP cur;
   ListP tmp;

   if (l == NULL)
      return 0;

   if (l->exponent == exp)
   {
      tmp = l;
      l = l->next;
      delete tmp;
      return 1;
   }

   cur = l;

   while (cur->next != NULL)
   {
      if (cur->next->exponent == exp)
      {
         tmp = cur->next;
         cur->next = cur->next->next;
         delete tmp;
         return 1;
      }

      cur = cur->next;
   }

   return 0;
}

void List::Print(void)
{
   ListP tmp;

   cout << "----------\n";

   for (tmp = l; tmp != NULL; tmp = tmp->next)
      cout << "exp: " << tmp->exponent << "   coeff: "
           << tmp->coeff << endl;

   cout << "----------\n";
}

listtest.cpp

#include <iostream.h>
#include "list.h"

void f(List a);

int main()
{
   List a;

   a.Insert(1, 2.3);
   a.Insert(4, 5.6);

   a.Print();

//   List b;
   List b = a;

//   b = a;

   b.Print();

   cout << a.Delete(1) << endl;

   a.Print();
   b.Print();

   cout << "Calling f().\n";
   f(b);

   b.Print();

   cout << "Testing self-assignment.\n";

   List c;

   c.Insert(10, 11.12);
   c.Insert(13, 14.15);

   c.Print();
   c = c;
   c.Print();

   cout << "Testing multiple-assignment.\n";

   a = b = c;

   a.Print();
   b.Print();

   return 0;
}

void f(List a)
{
   cout << a.Delete(1) << endl;

   a.Print();
}