dllist.cpp

经典c++程序的实现

// dllist.cpp

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

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

typedef int ELEM;

#include "..\include\dlinkf.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 "..\include\llist.h"

//  Definitions for list class -- doubly-linked list implementation.

list::list(const int sz)       // Constructor -- ignore sz
{ tail = head = curr = new link; }

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;
    head->next = curr->next;
    delete curr;
  }
  curr = tail = head;
}

// Insert ELEM at current position
void list::insert(const ELEM& item) {
  assert(curr != NULL);
  curr->next = new link(item, curr->next, curr);
  if (curr->next->next != NULL)
    curr->next->next->prev = curr->next;
  if (tail == curr)  tail = curr->next;
}

void list::append(const ELEM& item) { // Append ELEM at tail of list
  tail->next = new link(item, NULL, tail);
  tail = tail->next;
}

ELEM list::remove() {             // Remove ELEM at current position
  assert(isInList());             // Must be valid position in list
  ELEM temp = curr->next->element;
  link* ltemp = curr->next;
  if (ltemp->next != NULL) ltemp->next->prev = curr;
  else tail = curr;               // Removed tail ELEM - change tail
  curr->next = ltemp->next;
  delete ltemp;
  return temp;
}

void list::prev()                 // Move curr to previous position
  { if (curr != NULL)  curr = curr->prev; }

void list::setFirst()               // Set curr to first position
  { curr = head; }

void list::next()                   // Move curr to next position
  { if (curr != NULL)  curr = curr->next; }

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 elements
  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 (from current position)
  while (isInList())
    if (currValue() == val) return TRUE;
    else next();
  return FALSE;                     // Not found
}