Microsoftware Monthly 19…2 Programming Power Tools/MASO9512.ISO/cpptutor/cpptutor.arj/EXAMPLES/EX1405.CPP

C/C++ Source or Header | 1993-10-27 | 9.5 KB | 305 lines

// \EXAMPLES\EX1405.CPP
//---------------------------------------------------------
#include <iostream.h>

// forward declaration of ListItem class.

class ListItem;


//----------------------------------------------------
// CLASS List : A base class for the classes
//              that implement specific kind of lists.
//----------------------------------------------------

class List {
public:
  virtual void add(ListItem&) =0;
  virtual int remove(ListItem&) =0;
  virtual void display() =0;
};

//----------------------------------------------------
// CLASS ListItem : A class for nodes that are stored
//                  in Lists.
//----------------------------------------------------

class ListItem {
private:
  int value;
public:
  ListItem(int i = 0): value(i) { }
  int operator==(const ListItem& li)
  { return ( value == li.value); }
  ListItem& operator=(const ListItem& li)
  { value = li.value; return (*this); }
  int get() { return value; }
};


//----------------------------------------------------
// CLASS SLList : A class that implements a List as a
//                singly-linked list.
//----------------------------------------------------

class SLList : public List {
  struct Node               // structure for nodes in the list
  {
    ListItem datum;         // value of current node
    Node* next;             // pointer to next node
  };
  Node* pList;              // pointer to beginning of list
  Node* last();             // return pointer to last node
public:
  SLList();                 // constructor
  ~SLList();                // destructor
  void add(ListItem&);      // add node to list
  int remove(ListItem&);    // remove from list
  void display();           // display contents of list
};

//----------------------------------------------------
// constructor for SLList
//----------------------------------------------------

SLList::SLList() {
  pList = NULL;
}

//----------------------------------------------------
// destructor for SLList
//----------------------------------------------------

SLList::~SLList() {
  Node* pTempNode;
  while ( pList != NULL ) {      // delete all the nodes in list
    pTempNode = pList;
    pList = pList->next;
    delete pTempNode;
    }
}

//----------------------------------------------------
// last() private member function
// It returns pointer to last node in list
//----------------------------------------------------

SLList::Node* SLList::last() {
  Node* currNode = pList;
  Node* retNode = NULL;
  while ( currNode != NULL ) {
    retNode = currNode;
    currNode = currNode->next;
  }
  return retNode;
}

//----------------------------------------------------
// add() - add a node to a list
//----------------------------------------------------

void SLList::add(ListItem& s) {
  Node* pNewNode = new Node;
  if ( pNewNode == NULL )
    cout << " Can't allocate list " << endl;
  else {
    Node* lastNode = last();
    pNewNode->datum = s;           // assign data value
    pNewNode->next = NULL;         //
    if ( lastNode != NULL )
      lastNode->next = pNewNode;   // last node in existing list
                                   // points to new node
    else
      pList = pNewNode;            // this is first item in list
    }
}

//----------------------------------------------------
// remove() remove a node from the list.  Any nodes that match
//          the value of the argument are removed from the list.
//----------------------------------------------------

int SLList::remove(ListItem& li) {
  Node* currNode = pList;
  Node* prevNode = NULL;
  Node* nextNode;
  int retval = 0;
  while (currNode != NULL) {
    nextNode = currNode->next;  // keep pointer to next node
    if (currNode->datum == li)  // if datum matches, remove node
    {
      retval = 1;               // set return value
      if ( prevNode == NULL )   // is this beginning of list?
        pList = currNode->next; // List begins at next node
     else                     // skip current node in link chain
        prevNode->next = currNode->next;
      delete currNode;          // delete current node
    }
    else
      prevNode = currNode;      // advance previous node pointer
    currNode = nextNode;        // advance current node pointer
  }
  return retval;
}

//----------------------------------------------------
// display() - print all of the nodes in the list
//----------------------------------------------------

void SLList::display() {
  Node* currNode = pList;
  cout << "List contains:" << endl;
  while ( currNode != NULL ) {
    cout << currNode->datum.get() << endl;
    currNode = currNode->next;
  }
}

//----------------------------------------------------
// CLASS DLList : A class that implements a List as a
//                doubly-linked list.
//----------------------------------------------------

class DLList : public List {
  struct Node            // structure for nodes in the list
  {
    ListItem datum;      // value of current node
    Node* prev;          // pointer to previous node
    Node* next;          // pointer to next node
  };
  Node* pList;           // pointer to beginning of linked list
  Node* last();          // return pointer to last node in list
public:
  DLList();              // constructor
  ~DLList();             // destructor
  void add(ListItem&);   // add node to list
  int remove(ListItem&); // remove nodes from list
  void display();        // display contents of list
};

//----------------------------------------------------
// constructor for DLList
//----------------------------------------------------

DLList::DLList() {
  pList = NULL;
}

//----------------------------------------------------
// destructor for DLList
//----------------------------------------------------

DLList::~DLList() {
  Node* pTempNode;
  while ( pList != NULL ) {   // delete all the nodes in the list
    pTempNode = pList;
    pList = pList->next;
    delete pTempNode;
    }
}

//----------------------------------------------------
// last() - private member function
//          returns pointer to last node in list
//----------------------------------------------------

DLList::Node* DLList::last() {
  Node* currNode = pList;
  Node* retNode = NULL;
  while ( currNode != NULL ) {
    retNode = currNode;
    currNode = currNode->next;
  }
  return retNode;
}

//----------------------------------------------------
// add() - add a node to a list
//----------------------------------------------------

void DLList::add(ListItem& s) {
  Node* pNewNode = new Node;
  if ( pNewNode == NULL )
    cout << " Can't allocate list " << endl;
  else {
    Node* lastNode = last();
    pNewNode->datum = s;           // assign data value
    pNewNode->next = NULL;         //
    if ( lastNode != NULL )  {
      lastNode->next = pNewNode;   // last node in existing list
                                   // points to new node
      pNewNode->prev = lastNode;   // new node points back to
                                   // last node in existing list
    }
    else {
      pNewNode->prev = NULL;       // this is first item in list
      pList = pNewNode;
    }
  }
}

//----------------------------------------------------
// remove() - remove nodes from the list.  Any ListItems
//            that match the value of the argument are removed
//----------------------------------------------------

int DLList::remove(ListItem& li) {
  Node* currNode = pList;
  Node* nextNode;
  int retval = 0;
  while (currNode != NULL) {
    nextNode = currNode->next;      // keep pointer to next node
    if (currNode->datum == li)      // if matches, remove node
    {
      retval = 1;                   // set return value
      if ( currNode->prev == NULL ) // beginning of list?
        pList = currNode->next;     // List begins at next node
     else                      // skip current node in link chain
        currNode->prev->next = currNode->next;
      delete currNode;              // delete current node
    }
    currNode = nextNode;          // advance current node pointer
  }
  return retval;
}

//---------------------------------------------------------
// display() - print all of the nodes in the list
//---------------------------------------------------------

void DLList::display() {
  Node* currNode = pList;
  cout << "List contains:" << endl;
  while ( currNode != NULL ) {
    cout << currNode->datum.get() << endl;
    currNode = currNode->next;
  }
}

//----------------------------------------------------
// FUNCTION useClass : client code to exercise List classes.
// parameters:  List& lp  -  reference to List class object
//----------------------------------------------------

void useClass(List& lp) {
  for ( int i = 0; i < 10; i++ ) {  // put nodes in the list
    ListItem li(i);                 // define a ListItem object
    lp.add(li);                     // add this ListItem to list
  }
  lp.display();                     // display List
  ListItem li(0);                   // add another node with
  lp.add(li);                       // value = 0 to the list
  lp.display();
  lp.remove(li);             // remove both nodes with value = 0
  lp.display();
}

//----------------------------------------------------
void main() {
  SLList sl;
  DLList dl;
  useClass(sl);            // call client code with SLList object
  useClass(dl);            // call client code with DLList object
}
//----------------------------------------------------