llistf.cpp

经典c++程序的实现

#include <stdio.h>
#include <iostream.h>
#include <assert.h>

#include "book.h"

typedef int ELEM;

#include "linkf.h"

// This creates space for the freelist variable
link* link::freelist = NULL;

void* link::operator new(size_t) { // Overload new operator
  if (freelist == NULL) return ::new link;  // Create new space
  link* temp = freelist;           // Otherwise, get from freelist
  freelist = freelist->next;
  return temp;                     // Return the link node
}

void link::operator delete(void* ptr) { // Overload delete operator
  ((link*)ptr)->next = freelist;        // Put on freelist
  freelist = (link*)ptr;
}

#include "llist.h"

// Load the member functions for list
list::list(const int sz)       // Constructor -- Ignore sz
  { tail = head = curr = new link; }  // Create header node

list::~list() {                // Destructor
  while(head != NULL) {        // Return link nodes to free store
    curr = head;
    head = head->next;
    delete curr;
  }
}

void list::clear() {           // Remove all ELEMs from list
   while (head->next != NULL) { // Return link nodes to free store
     curr = head->next;         //   (keep header node)
     head->next = curr->next;
     delete curr;
   }
   curr = tail = head;          // Reinitialize
 }
 
 // Insert ELEM at current position
 void list::insert(const ELEM& item) {
   assert(curr != NULL);       // Must be pointing to list ELEM
   curr->next = new link(item, curr->next);
   if (tail == curr)           // Appended new ELEM
     tail = curr->next;
 }
 
 void list::append(const ELEM& item) // Insert ELEM at tail of list
   { tail = tail->next = new link(item, NULL); }

 ELEM list::remove() {              // Remove and return current ELEM
   assert(isInList());              // Must be valid position in list
   ELEM temp = curr->next->element; // Remember value
   link* ltemp = curr->next;        // Remember link node
   curr->next = ltemp->next;        // Remove from list
   if (tail == ltemp) tail = curr;  // Removed last ELEM: set tail
   delete ltemp;      // Send link to free store
        return temp;                     // Return value removed
      }
      
      void list::setFirst()              // Set curr to first position
        { curr = head; }
      
      void list::next()                  // Move curr to next position
        { if (curr != NULL)  curr = curr->next; }
      
      void list::prev() {                // Move curr to previous position
        link* temp = head;
        if ((curr == NULL) || (curr == head)) // No previous ELEM
          { curr = NULL;  return; }           //   so just return
        while ((temp!=NULL) && (temp->next!=curr)) temp=temp->next;
        curr = temp;
      }
      
      int list::length() const {          // Return current length of list
        int cnt = 0;
        for (link* temp = head->next; temp != NULL; temp = temp->next)
           cnt++;                         // Count the number of ELEMs
        return cnt;
      }
      
      void list::setPos(const int pos) { // Set curr to specified position
        curr = head;
        for(int i=0; (curr!=NULL) && (i<pos); i++)
          curr = curr->next;
      }
      
      void list::setValue(const ELEM& val) // Set current ELEM's value
  { assert(isInList());  curr->next->element = val; }

ELEM list::currValue() const         // Return value of current ELEM
  { assert(isInList());  return curr->next->element; }

bool list::isEmpty() const          // Return TRUE if list is empty
  { return head->next == NULL; }

bool list::isInList() const         // TRUE if curr is within list
  { return (curr != NULL) && (curr->next != NULL); }

bool list::find(const ELEM& val) {  // Find value (starting at curr)
  while (isInList())
    if (curr->next->element == val) return TRUE;
    else curr = curr->next;
  return FALSE;                     // Not found
}