llist.cpp

经典c++程序的实现

// llist.cpp

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

#include "..\include\book.h"

typedef int ELEM;

#include "..\include\link.h"

#include "..\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
}