llimpl.cpp

经典c++程序的实现

const int LIST_SIZE = 10;
typedef int ELEM;

class link {                  // A singly-linked list node
public:
  ELEM element;               // ELEM value for this node
  link *next;                 // Pointer to next node in list
  link(const ELEM& elemval, link* nextval =NULL)
    { element = elemval;  next = nextval; }
  link(link* nextval =NULL) { next = nextval; }
  ~link() { }                 // Destructor
};

/////////////////////////////////////////////////////////

class list {                  // Linked list class
private:
  link* head;                 // Pointer to list header
  link* tail;                 // Pointer to last ELEM in list
  link* curr;                 // Position of "current" ELEM
public:
  list(const int =LIST_SIZE); // Constructor
  ~list();                    // Destructor
  void clear();               // Remove all ELEMs from list
  void insert(const ELEM&);   // Insert ELEM at current pos
  void append(const ELEM&);   // Insert ELEM at tail of list
  ELEM remove();      // Remove + return current ELEM
        void setFirst();            // Set curr to first position
        void next();                // Move curr to next position
        void prev();                // Move curr to previous pos
        int  length() const;        // Return current length of list
        void setPos(const int);     // Set curr to specified pos
        void setValue(const ELEM&); // Set current ELEM's value
        ELEM currValue() const;     // Return current ELEM's value
        bool isEmpty() const;       // Return TRUE if list is empty
        bool isInList() const;      // TRUE if curr is within list
        bool find(const ELEM&);     // Find value (from current pos)
      };
      
      list::list(const int sz)       // Constructor -- Ignore sz
        { tail = head = curr = new link; }  // Create header node
      
      list::~list() {                // Destructor
        while(head != NULL) {        // Return links to free store
          curr = head;
          head = head->next;
          delete curr;
        }
      }
      void list::clear() {           // Remove all ELEMs from list
        while (head->next !=NULL) { // Return links 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
  { tail = tail->next = new link(item, NULL); }

ELEM list::remove() {              // Remove/return ELEM
  assert(isInList());              // Must be valid position
  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: set tail
  delete ltemp;                    // Send link to free store
  return temp;                     // Return value removed
}

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

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

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