linkedlist.cpp

一个很棒的网络控制系统仿真软件

#include <cstddef>

class Node {
public:
  Node *pNext;
  Node *pPrev;

  Node *getNext();
  Node *getPrev();

  virtual void print() = 0;
  Node(); // constructor
};

/* Constructor */
Node::Node() {
  pNext = NULL;
  pPrev = NULL;
}

/* Returns a pointer to the node after pNode, NULL if pNode last node */
Node *Node::getNext() {
  
  return pNext;
}

/* Returns a pointer to the node before pNode, NULL if pNode first node */
Node *Node::getPrev() {
  
  return pPrev;
}


class List {
  char *name;
  Node *pHead, *pTail;
  int (*compFcn)(Node *, Node *);
public:
  Node *getFirst();
  Node *getLast();
  void appendNode(Node *pNode);
  void insertAfter(Node *pNode, Node *pAfter);
  void insertBefore(Node *pNode, Node *pBefore);
  bool insertSorted(Node *pNode);
  void removeNode(Node *pNode);
  void deleteNode(Node *pNode);
  void print();
  int length();

  List(char *name, int (*compFcn)(Node *, Node *));
};

/* Constructor */
List::List(char *n, int (*cf)(Node *, Node *)) {
  pHead = NULL;
  pTail = NULL;
  name = n;
  compFcn = cf;
}

void List::print() {
  printf("%s:", name);
  Node *n = pHead;
  if (n == NULL) printf(" Empty");
  while (n != NULL) {
    printf(" *");
    n->print();
    n = n->pNext;
  }
  printf("\n");
}

int List::length() {
  int len = 0;
  Node *n = pHead;
  while (n != NULL) {
    len++;
    n = n->pNext;
  }
  return len;
}

/* Returns a pointer to the first node in the list */
Node *List::getFirst() {
  return pHead;
}

/* Returns a pointer to the last node in the list */
Node *List::getLast() {
  return pTail;
}

/* Appends a node to the end of the list */
void List::appendNode(Node *pNode)
{
  if (pHead == NULL) {
    pHead = pNode;
    pNode->pPrev = NULL;
  }
  else {
    pTail->pNext = pNode;
    pNode->pPrev = pTail;
  }
  pTail = pNode;
  pNode->pNext = NULL;
}

/* Inserts a node into the list after pAfter */
void List::insertAfter(Node *pNode, Node *pAfter)
{
  pNode->pNext = pAfter->pNext;
  pNode->pPrev = pAfter;
  if (pAfter->pNext != NULL)
    pAfter->pNext->pPrev = pNode;
  else
    pTail = pNode;
  pAfter->pNext = pNode;
}

/* Inserts a node into the list before pBefore */
void List::insertBefore(Node *pNode, Node *pBefore)
{
  pNode->pPrev = pBefore->pPrev;
  pNode->pNext = pBefore;
  if (pBefore->pPrev != NULL)
    pBefore->pPrev->pNext = pNode;
  else
    pHead = pNode;
  pBefore->pPrev = pNode;
}

/* Inserts a node in the list, sorted using compFcn */
bool List::insertSorted(Node *pNode)
{
  Node *p;

  p = pHead;
  if (p==NULL) {
    appendNode(pNode);
    return true;
  }
  else {
    while (p!=NULL) {
      if (compFcn(pNode,p) >= 0) {
	insertBefore(pNode,p);
	return false;
      } else {
	p = p->pNext;
      }
    }
    if (p==NULL) {
      appendNode(pNode);
      return true;
    } else {
      return false;
    }
  }
}


/* Removes the specified node from the list */
void List::removeNode(Node *pNode)
{
  if (pNode->pPrev == NULL)
    pHead = pNode->pNext;
  else
    pNode->pPrev->pNext = pNode->pNext;

  if (pNode->pNext == NULL)
    pTail = pNode->pPrev;
  else
    pNode->pNext->pPrev = pNode->pPrev;
}

void List::deleteNode(Node *pNode)
{
  removeNode(pNode);
  delete pNode;
}