问双链接列表实现[C++]

EN

class node {
  public:
    node *prev;
    node *next;
    int key;
    char type;
};

class dList {
  private:
    node *head; // dummy head
    node *tail; // dummy tail

  public:
    dList() { // default constructor, creates empty list
      cout << "in default constructor" << endl; // to debug
      head = nullptr;
      tail = nullptr;
    }
    // destructor
    ~dList() {
      cout << "in destructor" << endl; // to debug
      node *ptr = head;
      while (ptr != nullptr) {
        delete ptr;
        ptr = ptr->next;
      }
      tail = nullptr;
    }

    // searches list for occurence of int parameter and returns pointer to node containing key
    node *search(int k);

    // outputs all keys that have type equal to character parameter, front to back
    void find(char t);

    // parametrized constructor, initialize list w/ contents of arrays
    dList(int arrayNums[], char arrayChars[], int size);

    // creates new node at front of list
    void addFront(int k, char t);

    // creates new node at back of list
    void addBack(int k, char t);

    // moves node pointed to by parameter to front of list
    void moveFront(node* ptr);

    // moves node pointed to by parameter to back of list
    void moveBack(node* ptr);

    // outputs first int elements of list, starting at front or back depending on char parameter
    void out(int num, char = 'f');

    // splits list in two
    node *split(node* headRef);

    // merges two linked lists
    node *mergeLists(node* first, node* second);

    // performs mergeSort on linked list
    node *mergeSort(node* headRef);

    // peforms an O(NlogN) sort on list; list should be in increasing order based on integer key
    void sort();
};

// parametrized constructor, initialize list w/ contents of arrays
dList::dList(int arrayNums[], char arrayChars[], int size) {
  node *newNode = nullptr;
  //cout << "parametrized constructor called" << endl;
  for (int i = 0; i < size; i++) {
    //cout << "in for loop" << endl;
    if (head == nullptr) {
      //cout << "in first if statement" << endl;
      newNode = new node;
      newNode->key = arrayNums[i];
      newNode->type = arrayChars[i];
      newNode->prev = nullptr;
      newNode->next = nullptr;
      head = newNode;
      tail = head;
    }

    else {
      //cout << "in else statement" << endl;
      newNode = new node;
      newNode->key = arrayNums[i];
      newNode->type = arrayChars[i];
      newNode->prev = tail;
      tail->next = newNode;
      tail = newNode;
    }
  }
}

void dList::addFront(int k, char t) { // creates new node at front of list
  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

  if (head != nullptr) {
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
  }
  else {
    newNode->prev = nullptr;
    newNode->next = nullptr;
    head = newNode;
    tail = nullptr;
  }
}

void dList::addBack(int k, char t) { // creates new node at back of list
  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

  node *ptr = head;

  if (ptr != nullptr) {
    while (ptr->next != nullptr) {
      ptr = ptr->next;
    }
    ptr->next = newNode;
    newNode->next = nullptr;
    newNode->prev = ptr;
  }
  else {
    newNode->next = nullptr;
    newNode->prev = nullptr;
    ptr = newNode;
    tail = ptr;
  }
}

void dList::moveFront(node *ptr) { // moves node pointed to by parameter to front of list
  //node *tempHead = head;
  //node *tempTail = tail;

  if (ptr == head) {
    return;
  }
  else if (ptr == tail) {
    ptr->prev->next = nullptr;
    tail = ptr->prev;
  }
  else {
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
  }

  head->prev = ptr;
  ptr->next = head;
  ptr->prev = nullptr;
  head = ptr;
}

void dList::moveBack(node *ptr) { // moves node pointed to by parameter to back of list
  //node *tempHead = head;
  //node *tempTail = tail;

  if (ptr == tail) {
    return;
  }
  else if (ptr == head) {
    head = ptr->next;
    tail->next = ptr;
    ptr->prev = tail;
    ptr->next = nullptr;
    tail = ptr;
  }
  else {
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
    tail->next = ptr;
    ptr->prev = tail;
    tail = ptr;
  }
}
// searches list for occurence of int parameter and returns pointer to node containing key
node *dList::search(int k) {
  node *ptr = head;
  while (ptr->next != nullptr) {
    if (ptr->key == k) {
      return ptr;
    }
    else {
      ptr = ptr->next;
    }
  }

  return nullptr;
}
// outputs all keys that have type equal to character parameter, front to back
void dList::find(char t) {
  node *ptr = head;
  while (ptr->next != nullptr) {
    if (ptr->type == t) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->next;
    }
    else {
      ptr = ptr->next;
    }
  }
}
// outputs first num elements of list, starting at front or back depending on char parameter
void dList::out(int num, char side) {
  cout << "out() called" << endl;
  if (side == 'b') {
    node *ptr = tail;
    for (int i = 0; i < num; i++) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->prev;
    }
  }
  else {
    node *ptr = head;
    for (int i = 0; i < num; i++) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->next;
    }
  }
}

#include <iostream>
using namespace std;
#include "dList.cpp"
#define SMALL 200
#define MAX 100000
#define ROUNDS 100
int main(){
    int i, x[MAX];
    char ch[MAX];

    for(i=0;i<SMALL;i++) {
      x[i] = (2*SMALL)-i;
      ch[i] = 'a' + (i % 26);
    }
    dList A(x,ch,SMALL), B;
    A.out(10);
    node *tmp = A.search(2*SMALL-8);
    A.moveFront(tmp);
    A.out(10);
    A.moveBack(tmp);
    A.out(10);
    A.find('b');
    A.sort();
    A.out(10);
    A.out(10,'b');
    A.addBack(500,'d');
    A.addFront(501,'z');
    A.out(10);
    A.out(10,'b');
    B.addFront(1,'a');
    B.addBack(2,'b');
    B.out(2);

    for(int j=0; j<ROUNDS; j++){
      cout << endl << "round " << j << endl;
      for(i=0;i<MAX;i++) {x[i] = 2*MAX-i; ch[i] = 'a'+ (i%26);}
      dList A(x,ch,MAX);
      node *tmp = A.search(2*MAX-8);
      A.moveFront(tmp);
      A.moveBack(tmp);
      A.sort();
      A.out(10);
      A.out(10,'b');
    }
}