程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 雙向線性鏈表 C++實現

雙向線性鏈表 C++實現

編輯：C++入門知識

雙向線性鏈表 C++實現

雙向線性鏈表的思想

雙向線性鏈表的每一個節點都有兩個指針，分別指向當前節點的前一個節點和後一個節點。
頭指針的前驅指向空，尾指針的後驅指向空
這裡寫圖片描述

需要實現的成員方法

私有方法

Node *at(int pos) const

獲取指定位置的節點

公有方法

void push_front(const DataType &data);
void push_back(const DataType &data);
void pop_front();
void pop_back();
void insert(int pos, const DataType &data);
void erase(int pos);
void erase(int start, int end);

push_front 在鏈表頭部增加一個節點
push_back 在鏈表尾部增加一個節點
pop_front 在鏈表頭部刪除一個節點
pop_back 在鏈表尾部刪除一個節點
insert 在鏈表指定位置增加一個節點
erase 在鏈表指定位置刪除一個節點或刪除指定范圍內所有節點
注意到insert和兩個push都是增加節點的操作，而insert的工作更加廣泛。因此在實現兩個push的時候可以利用insert。
同理，兩個pop可以利用erase實現

List &operator=(const List &li);
void assign(const List &li);
void assign(DataType *start, DataType *end);

這三個函數有相同的作用，給鏈表分配數據。
assign有兩個版本，一個是分配另一個鏈表，另一個是分配整個數組。
對賦值運算符的重載，是可以通過調用assign來實現。
assign的兩個版本均可利用push_back來完成。

void swap(List *li)

交換兩個鏈表的內容

void resize(int n)

重新設定鏈表的長度。
如果n大於鏈表長度，則在多出的部分補充類型的默認數值（比如int是0，string是“”）
如果n小於鏈表長度，則將大於n的部分刪除

void clear()

清空鏈表

void splice(int pos, List *li1, List *li2)

從指定位置截斷，將指定位置以前的內容分配給li1，以後的內容分配給li2

void merge(const List &li1, const List &li2)

融合兩個鏈表li1和li2，並分配給當前調用該函數的鏈表

void remove(const DataType &data)

刪除有指定數據的節點

void remove_if(bool (*condition)(Node *p))

刪除滿足條件的節點

void unique()

刪除有重復數據的節點

void sort()

升序排序

void reverse()

反轉鏈表

bool empty() const

判斷鏈表是否為空

int size() const

返回鏈表長度

DataType front() const;
DataType back() const;
DataType &operator[](int index) const;

分別返回頭節點，尾節點，指定節點的值

void display() const

打印鏈表的值

代碼實現

雙向線性鏈表的類聲明以及類定義

// List.h

#pragma once

#include 
using namespace std;

// Class Declaration

template  class Node {
public:
  DataType data;
  Node *prev;
  Node *next;

  Node(const DataType &d = DataType(), Node *p = NULL, Node *n = NULL)
      : data(d), prev(p), next(n) {}
};

template  class List {
private:
  Node *head;
  Node *tail;
  int listSize;

  // Get the Node at pos
  Node *at(int pos) const;

public:
  // Constructor
  List();

  // Copy Constructor
  List(const List &li);

  // Constructor for array
  List(DataType *start, DataType *end);

  // Destructor
  ~List();

  // Modifiers
  List &operator=(const List &li);
  void assign(const List &li);
  void assign(DataType *start, DataType *end);
  void push_front(const DataType &data);
  void push_back(const DataType &data);
  void pop_front();
  void pop_back();
  void insert(int pos, const DataType &data);
  void erase(int pos);
  void erase(int start, int end);
  void swap(List *li);
  void resize(int n);
  void clear();

  // Operations
  void splice(int pos, List *li1, List *li2);
  void merge(const List &li1, const List &li2);
  void remove(const DataType &data);
  void remove_if(bool (*condition)(Node *p));
  void unique();
  void sort();
  void reverse();

  // Capacity
  bool empty() const;
  int size() const;

  // Element Access
  DataType front() const;
  DataType back() const;
  DataType &operator[](int index) const;

  // Printer
  void display() const;
};

// Class Implementation

// Get the Node at pos
template  Node *List::at(int pos) const {
  if (pos < 0 || pos > listSize - 1)
    return NULL;
  Node *p = head;
  while (pos--)
    p = p->next;
  return p;
}

// Constructor
template  List::List() {
  head = tail = NULL;
  listSize = 0;
}

// Copy Constructor
template  List::List(const List &li) {
  assign(li);
}

// Constructor for array
template 
List::List(DataType *start, DataType *end) {
  assign(start, end);
}

// Destructor
template  List::~List() { clear(); }

// Modifiers
template 
List &List::operator=(const List &li) {
  assign(li);
  return *this;
}

template 
void List::assign(const List &li) {
  if (!empty())
    clear();
  if (li.empty()) {
    head = tail = NULL;
    listSize = 0;
  } else {
    for (Node *p = li.head; p != NULL; p = p->next)
      push_back(p->data);
  }
}

template 
void List::assign(DataType *start, DataType *end) {
  if (!empty())
    clear();
  for (DataType *p = start; p != end; ++p)
    push_back(*p);
}
template 
void List::push_front(const DataType &data) {
  insert(0, data);
}

template 
void List::push_back(const DataType &data) {
  insert(listSize, data);
}

template  void List::pop_front() { erase(0); }

template  void List::pop_back() {
  erase(listSize - 1);
}

template 
void List::insert(int pos, const DataType &data) {
  if (pos < 0 || pos > listSize)
    return;
  if (pos == 0) {
    Node *newNode = new Node(data);
    if (empty()) {
      head = tail = newNode;
      ++listSize;
    } else {
      newNode->next = head;
      head->prev = newNode;
      head = newNode;
      ++listSize;
    }
  } else if (pos == listSize) {
    Node *newNode = new Node(data);
    if (empty()) {
      head = tail = newNode;
      ++listSize;
    } else {
      newNode->prev = tail;
      tail->next = newNode;
      tail = newNode;
      ++listSize;
    }
  } else {
    Node *p = at(pos);
    Node *newNode = new Node(data, p, p->next);
    p->next = newNode;
    p->next->prev = newNode;
    ++listSize;
  }
}

template  void List::erase(int pos) {
  if (pos < 0 || pos > listSize || empty())
    return;
  if (pos == 0) {
    if (listSize == 1) {
      delete head;
      head = tail = NULL;
      --listSize;
    } else {
      Node *p = head->next;
      p->prev = NULL;
      delete head;
      head = p;
      --listSize;
    }
  } else if (pos == listSize - 1) {
    if (listSize == 1) {
      delete tail;
      head = tail = NULL;
      --listSize;
    } else {
      Node *p = tail->prev;
      p->next = NULL;
      delete tail;
      tail = p;
      --listSize;
    }
  } else {
    Node *p = at(pos);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    --listSize;
  }
}

template  void List::erase(int start, int end) {
  if (start >= end || start < 0 || end > listSize || empty())
    return;
  if (start == 0) {
    for (int i = start; i < end; i++)
      pop_front();
  } else if (end == listSize) {
    for (int i = start; i < end; i++)
      pop_back();
  } else {
    Node *p1 = at(start);
    Node *p2 = at(end);
    p1->prev->next = p2;
    p2->prev = p1->prev;
    while (p1 != p2) {
      Node *temp = p1->next;
      delete p1;
      p1 = temp;
      --listSize;
    }
  }
}

template  void List::swap(List *li) {
  List temp = *this;
  *this = *li;
  *li = temp;
}

template  void List::resize(int n) {
  if (n == listSize)
    return;
  int temp = listSize;
  if (n < listSize)
    for (int i = n; i < temp; i++)
      pop_back();
  if (n > listSize)
    for (int i = temp; i < n; i++)
      push_back(DataType());
}

template  void List::clear() {
  while (!empty())
    pop_front();
}

// Operations
template 
void List::splice(int pos, List *li1, List *li2) {
  li1->clear();
  li2->clear();
  Node *breakPos = at(pos);
  for (Node *p = head; p != breakPos; p = p->next)
    li1->push_back(p->data);
  for (Node *p = tail; p != breakPos->prev; p = p->prev)
    li2->push_front(p->data);
}

template 
void List::merge(const List &li1,
                           const List &li2) {
  if (listSize != 0)
    clear();
  for (Node *p = li1.tail; p != NULL; p = p->prev)
    push_front(p->data);
  for (Node *p = li2.head; p != NULL; p = p->next)
    push_back(p->data);
}

template  void List::remove(const DataType &data) {
  while (true) {
    bool judge = false;
    int pos = 0;
    for (Node *p = head; p != NULL; p = p->next) {
      if (p->data == data) {
        judge = true;
        erase(pos);
        break;
      }
      pos++;
    }
    if (!judge)
      break;
  }
}

template 
void List::remove_if(bool (*condition)(Node *p)) {
  while (true) {
    bool judge = false;
    int pos = 0;
    for (Node *p = head; p != NULL; p = p->next) {
      if (condition(p)) {
        judge = true;
        erase(pos);
        break;
      }
      pos++;
    }
    if (!judge)
      break;
  }
}

template  void List::unique() {
  if (listSize <= 1)
    return;
  Node *p1 = head;
  while (p1 != NULL) {
    Node *p2 = p1->next;
    while (p2 != NULL) {
      if (p1->data == p2->data) {
        if (p2 == tail) {
          pop_back();
          p2 = NULL;
        } else {
          Node *p = p2->next;
          p2->prev->next = p2->next;
          p2->next->prev = p2->prev;
          p2 = p;
          --listSize;
        }
      } else {
        p2 = p2->next;
      }
    }
    p1 = p1->next;
  }
}

template  void List::sort() {
  if (listSize <= 1)
    return;
  Node *p1 = head;
  while (p1 != NULL) {
    Node *p2 = p1->next;
    while (p2 != NULL) {
      if (p1->data > p2->data) {
        DataType temp = p1->data;
        p1->data = p2->data;
        p2->data = temp;
      }
      p2 = p2->next;
    }
    p1 = p1->next;
  }
}

template  void List::reverse() {
  Node *phead = head;
  Node *ptail = tail;
  while (ptail - phead > 1) {
    DataType temp = phead->data;
    phead->data = ptail->data;
    ptail->data = temp;
    phead = phead->next;
    ptail = ptail->prev;
  }
}

// Capacity
template  bool List::empty() const {
  return listSize == 0;
}

template  int List::size() const {
  return listSize;
}

// Element Access
template  DataType List::front() const {
  if (empty())
    return *reinterpret_cast(NULL);
  return head->data;
}
template  DataType List::back() const {
  if (empty())
    return *reinterpret_cast(NULL);
  return tail->data;
}

template 
DataType &List::operator[](int index) const {
  return at(index)->data;
}

// Printer
template  void List::display() const {
  if (empty()) {
    cout << "Empty list" << endl;
  } else {
    for (Node *p = head; p != NULL; p = p->next) {
      if (p == tail)
        cout << p->data << endl;
      else
        cout << p->data << ' ';
    }
  }
}

測試List類的程序

#include "List.h"
#include 
#include 
#include 
using namespace std;

bool condition1(Node *p) {
  if (p->data % 2)
    return false;
  return true;
}

bool condition2(Node *p) {
  if (p->data.size() % 2)
    return true;
  return false;
}

void testList() {
  if (true) {
    srand(time(0));
    cout << "Test for int" << endl;
    int arr[10];
    for (int i = 0; i < 10; i++)
      arr[i] = rand() % 10;

    List li1(arr, arr + 10);
    List li2(li1);
    List li3;
    for (int i = 0; i < 10; i++)
      li2.insert(i, rand() % 10);
    li3.merge(li1, li2);
    li1.display();
    li2.display();
    li3.display();

    li3.splice(li3.size() / 4, &li1, &li2);
    li1.display();
    li2.display();
    li3.display();

    for (int i = 0; i < 10; i++)
      li1.remove(i);
    li2.unique();
    li3.sort();
    li1.display();
    li2.display();
    li3.display();

    for (int i = 0; i < 10; i++) {
      li1.push_front(rand() % 10);
      li1.push_back(rand() % 10);
    }
    li2.remove_if(condition1);
    for (int i = 0; i < 10; i++)
      li3.erase(i);
    li1.display();
    li2.display();
    li3.display();

    li1.swap(&li2);
    li2.erase(li2.size() / 4, li2.size() / 2);
    li3.reverse();
    li1.display();
    li2.display();
    li3.display();

    li1.resize(li1.size() * 2);
    li2.resize(li2.size());
    li3.resize(li3.size() / 2);
    li1.display();
    li2.display();
    li3.display();

    for (int i = 0; i < li1.size(); i++) {
      li1[i] = i + 1;
      if (i == li1.size() - 1)
        cout << li1[i] << endl;
      else
        cout << li1[i] << ' ';
    }
    cout << li2.front() << endl;
    cout << li3.back() << endl;
  }

  cout << endl;

  if (true) {
    cout << "Test for string" << endl;
    string arr[5] = {"Ahem", "Boom", "Oh", "Bang", "Ha"};

    List li1(arr, arr + 5);
    List li2(li1);
    List li3;
    for (int i = 0; i < 5; i++)
      li2.insert(i, arr[i]);
    li3.merge(li1, li2);
    li1.display();
    li2.display();
    li3.display();

    li3.splice(li3.size() / 4, &li1, &li2);
    li1.display();
    li2.display();
    li3.display();

    for (int i = 0; i < 5; i++)
      li1.remove(arr[i]);
    li2.unique();
    li3.sort();
    li1.display();
    li2.display();
    li3.display();

    for (int i = 0; i < 5; i++) {
      li1.push_front(arr[i]);
      li1.push_back(arr[i]);
    }
    li2.remove_if(condition2);
    for (int i = 0; i < 10; i++)
      li3.erase(i);
    li1.display();
    li2.display();
    li3.display();

    li1.swap(&li2);
    li2.erase(li2.size() / 4, li2.size() / 2);
    li3.reverse();
    li1.display();
    li2.display();
    li3.display();

    li1.resize(li1.size() * 2);
    li2.resize(li2.size());
    li3.resize(li3.size() / 2);
    li1.display();
    li2.display();
    li3.display();

    for (int i = 0; i < li1.size(); i++) {
      li1[i] = i + 'A';
      if (i == li1.size() - 1)
        cout << li1[i] << endl;
      else
        cout << li1[i] << ' ';
    }
    cout << li2.front() << endl;
    cout << li3.back() << endl;
  }
}

int main() {
  testList();
  return 0;
}

運行結果范例：
這裡寫圖片描述