【链表】还不会用C++实现链表?一文教会你各种链表的实现

简介: 【链表】还不会用C++实现链表?一文教会你各种链表的实现

本文将用C++语言来实现数据结构中的无头单链表,带头循环链表,以及带头循环双向链表等链表结构(带头单链表与后两种链表的结构相似,实现起来比后两种更简单,读者阅读完本文即可自行实现)

一、无头单链表的实现

无头单链表在头插时需要改变头指针的位置,具体代码实现如下:

//无头单链表
#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
//先定义链表中的节点
struct SListNode
{
  T data;
  SListNode* next;
  SListNode(T x)
  {
    this->data = x;
    this->next = nullptr;
  }
};
template <class T>
class SList
{
private:
  //链表初始化后链表中就有一个节点
  SListNode<T>* head;
  
public:
  SList(T x)
  {
    this->head = new SListNode<T>(x);
  }
  ~SList()
  {
    SListNode<T>* cur = head;
    while (cur)
    {
      SListNode<T>* next = cur->next;
      delete cur;
      cur = next;
    }
  }
  // 动态申请一个节点
  SListNode<T>* BuySListNode(T x);
  // 单链表打印
  void SListPrint();
  // 单链表尾插
  void SListPushBack(T x);
  // 单链表的头插
  void SListPushFront(T x);
  // 单链表的尾删
  void SListPopBack();
  // 单链表头删
  void SListPopFront();
  // 单链表查找
  SListNode<T>* SListFind(T x);
  // 单链表在pos位置之后插入x
  void SListInsertAfter(SListNode<T>* pos, T x);
  // 单链表删除pos位置之后的值
  void SListEraseAfter(SListNode<T>* pos);
};
template <class T>
SListNode<T>* SList<T>:: BuySListNode(T x)
{
  SListNode<T>* tmp = new SListNode<T>(x);
  tmp->next = nullptr;
  return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
  SListNode<T>* cur =head;
  while (cur)
  {
    cout << cur->data << "->";
    cur = cur->next;
  }
  cout << "NULL" << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
  SListNode<T>* cur = head;
  while (cur->next)
  {
    cur = cur->next;
  }
  SListNode<T>* newnode = BuySListNode(x);
  cur->next = newnode;//连接
}
template <class T>
void SList<T>::SListPushFront(T x)
{
  SListNode<T>* newnode = BuySListNode(x);
  newnode->next = head;
  head = newnode;
}
template <class T>
void SList<T>::SListPopBack()
{
  assert(head);//头结点为空就不能继续删除了
  SListNode<T>* tail = head;
  //链表中只有一个节点就只能删除头结点
  if (tail->next == nullptr)
  {
    delete head;
  }
  else
  {
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    delete tail->next;
    tail->next = nullptr;
  }
}
template <class T>
void SList<T>::SListPopFront()
{
  assert(head);
  SListNode<T>* cur = head->next;
  delete head;
  head = cur;
}
template <class T>
SListNode<T>* SList<T>::SListFind(T x)
{
  assert(head);
  SListNode<T>* cur = head;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(SListNode<T>* pos, T x)
{
  assert(pos);
  SListNode<T>* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
template <class T>
void SList<T>::SListEraseAfter(SListNode<T>* pos)
{
  assert(pos->next && pos);
  SListNode<T>* cur = pos->next;
  pos->next = pos->next->next;
  delete cur;
}
int main()
{
  SList<int> cur(1);
  cur.SListPushBack(2);
  cur.SListPushBack(3);
  cur.SListPushBack(4);
  cur.SListPushBack(5);
  cur.SListPushBack(6);
  cur.SListPrint();
  cur.SListPopFront();
  cur.SListPrint();
  cur.SListPopBack();
  cur.SListPrint();
  SListNode<int>* p1 = cur.SListFind(2);
  cur.SListInsertAfter(p1, 20);
  cur.SListPrint();
  cur.SListEraseAfter(p1);
  cur.SListPrint();
  
  return 0;
}

二、带头循环链表的实现

带头意味着链表中会一直存在着一个头结点,无论链表的插入还是删除都是对头结点后面的节点进行的操作。头插的节点也是直接连接在头结点的下一个结点,不会改变头结点。循环意味着尾节点的next指针指向头节点,就像是形成了一个环一样。

具体实现代码如下:

#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct Node
{
  T data;
  struct Node* next;
  Node()
  {
    this->data = 0;
    this->next = nullptr;
  }
  Node(T data)
  {
    this->data = data;
    this->next = nullptr;
  }
};
template <class T>
class SList
{
private:
  Node<T>* head;
  Node<T>* tail;
public:
  SList()
  {
    this->head = new Node<T>();
    this->tail = head;
  }
  ~SList()
  {
    Node<T>* p = head;
    Node<T>* q = head;
    while (p != tail)
    {
      q = p->next;
      delete p;
      p = q;
    }
    delete tail;
  }
  
  // 动态申请一个节点
  Node<T>* BuySListNode(T x);
  // 单链表打印
  void SListPrint();
  // 单链表尾插
  void SListPushBack(T x);
  // 单链表的头插
  void SListPushFront(T x);
  // 单链表的尾删
  void SListPopBack();
  // 单链表头删
  void SListPopFront();
  // 单链表查找
  Node<T>* SListFind( T x);
  // 单链表在pos位置之后插入x
  void SListInsertAfter(Node<T>* pos, T x);
  // 单链表删除pos位置之后的值
  void SListEraseAfter(Node<T>* pos);
};
template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
  Node<T>* tmp = new Node<T>;
  tmp->data = x;
  tmp->next = nullptr;
  return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
  assert(head->next);//保证头节点后还有结点才打印,不然报错
  Node<T>* cur = head->next;
  while (cur != head)
  {
    cout << cur->data << "->";
    cur = cur->next;
  }
  cout << "NULL" << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
  Node<T>* newnode = BuySListNode(x);
  tail->next = newnode;
  tail = newnode;
  tail->next = head;//尾节点的next指向头节点
}
template <class T>
void SList<T>::SListPushFront(T x)
{
  Node<T>* newnode = BuySListNode(x);
  if (head == tail)
  {
    head->next = newnode;
    tail = newnode;
    tail->next = head;
  }
  else
  {
    newnode->next = head->next;
    head->next = newnode;
  }
}
template <class T>
void SList<T>::SListPopBack()
{
  assert(head->next);
  Node<T>* cur = head;
  while (cur->next != tail)
  {
    cur = cur->next;
  }
  delete tail;
  tail = cur;
  tail->next = head;
}
template <class T>
void SList<T>::SListPopFront()
{
  assert(head->next);
  Node<T>* cur = head->next;
  if (head->next == tail)
  {
    delete tail;
    tail = head;
  }
  else
  {
    head->next = cur->next;
    delete cur;
  }
}
template <class T>
Node<T>* SList<T>::SListFind(T x)
{
  assert(head->next);
  Node<T>* cur = head->next;
  while (cur != head)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
  assert(pos);
  if (pos->next == head)
  {
    SListPushBack(x);
  }
  else if(pos == head)
  {
    SListPushFront(x);
  }
  else
  {
    Node<T>* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
  }
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
  assert(pos);
  //尾节点后的头节点不能删
  if (pos->next == head)
  {
    exit(-1);
  }
  else if (pos == head)
  {
    SListPopFront();
  }
  else
  {
    Node<T>* cur = pos->next;
    pos->next = pos->next->next;
    delete cur;
  }
}
int main()
{
  SList<int> SL1;
  SL1.SListPushBack(1);
  SL1.SListPushBack(2);
  SL1.SListPushBack(3);
  SL1.SListPushBack(4);
  SL1.SListPushBack(5);
  SL1.SListPrint();
  SL1.SListPushFront(10);
  SL1.SListPrint();
  SL1.SListPopFront();
  SL1.SListPrint();
  SL1.SListPopBack();
  SL1.SListPrint();
  Node<int>* cur = SL1.SListFind(2);
  SL1.SListInsertAfter(cur, 20);
  SL1.SListPrint();
  SL1.SListEraseAfter(cur);
  SL1.SListPrint();
  return 0;
}

三、带头双向循环链表的实现

具体实现思路与带头循环链表大同小异,只是在节点中需要增加一个指向前一个节点的指针。

具体实现代码如下:

#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct Node
{
  T data;
  struct Node* prev;//指向前一个节点的指针
  struct Node* next;
  Node()
  {
    this->data = 0;
    this->prev = nullptr;
    this->next = nullptr;
  }
  Node(T data)
  {
    this->data = data;
    this->prev = nullptr;
    this->next = nullptr;
  }
};
template <class T>
class SList
{
private:
  Node<T>* head;//头节点
  Node<T>* tail;//尾节点
public:
  SList()
  {
    this->head = new Node<T>();
    head->next = nullptr;
    head->prev = nullptr;
    this->tail = head;
  }
  ~SList()
  {
    Node<T>* p = head;
    Node<T>* q = head;
    while (p != tail)
    {
      q = p->next;
      delete p;
      p = q;
    }
    delete tail;
  }
  Node<T>* getHead()
  {
    return this->head;
  }
  // 动态申请一个节点
  Node<T>* BuySListNode(T x);
  // 单链表打印
  void SListPrint();
  // 单链表尾插
  void SListPushBack(T x);
  // 单链表的头插
  void SListPushFront(T x);
  // 单链表的尾删
  void SListPopBack();
  // 单链表头删
  void SListPopFront();
  // 单链表查找
  Node<T>* SListFind(T x);
  // 单链表在pos位置之后插入x
  void SListInsertAfter(Node<T>* pos, T x);
  // 单链表删除pos位置之后的值
  void SListEraseAfter(Node<T>* pos);
};
template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
  Node<T>* tmp = new Node<T>;
  tmp->data = x;
  tmp->prev = nullptr;
  tmp->next = nullptr;
  return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
  assert(head->next);
  Node<T>* cur = head->next;
  while (cur != head)
  {
    cout << cur->data << "<->";
    cur = cur->next;
  }
  cout << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
  Node<T>* newnode = BuySListNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  tail = newnode;
  tail->next = head;
  head->prev = tail;
}
template <class T>
void SList<T>::SListPushFront(T x)
{
  Node<T>* newnode = BuySListNode(x);
  if (head == tail)//头节点后没有节点
  {
    head->next = newnode;
    newnode->prev = head;
    tail = newnode;
    tail->next = head;
    head->prev = tail;
  }
  else
  {
    newnode->next = head->next;
    newnode->prev = head;
    head->next = newnode;
  }
}
template <class T>
void SList<T>::SListPopBack()
{
  assert(head->next);
  Node<T>* cur = tail->prev;
  head->prev = tail->prev;
  delete tail;
  tail = cur;
  tail->next = head;
  
}
template <class T>
void SList<T>::SListPopFront()
{
  assert(head->next);//只剩头节点不删
  Node<T>* cur = head->next;
  if (head->next == tail)//头节点后只有一个节点
  {
    delete tail;
    tail = head;
    head->next = head;
    head->prev = head;
  }
  else
  {
    head->next = cur->next;
    cur->next->prev = head;
    delete cur;
  }
}
template <class T>
Node<T>* SList<T>::SListFind(T x)
{
  assert(head->next);
  Node<T>* cur = head->next;
  while (cur != head)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
  assert(pos);
  if (pos->next == head)
  {
    SListPushBack(x);
  }
  else if (pos == head)
  {
    SListPushFront(x);
  }
  else
  {
    Node<T>* newnode = BuySListNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next = newnode;
  }
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
  assert(pos);
  if (pos->next == head)//尾节点后的头节点不删
  {
    exit(-1);
  }
  else if (pos == head)
  {
    SListPopFront();
  }
  else
  {
    Node<T>* cur = pos->next;
    pos->next = pos->next->next;
    pos->next->prev = pos;
    delete cur;
  }
}
int main()
{
  //SListNode<int>* head = new SListNode<int>;
  SList<int> SL1;
  SL1.SListPushBack(1);
  SL1.SListPushBack(2);
  SL1.SListPushBack(3);
  SL1.SListPushBack(4);
  SL1.SListPushBack(5);
  SL1.SListPrint();
  SL1.SListPushFront(10);
  SL1.SListPrint();
  SL1.SListPopFront();
  SL1.SListPrint();
  SL1.SListPopBack();
  SL1.SListPrint();
  Node<int>* cur = SL1.SListFind(2);
  SL1.SListInsertAfter(cur, 20);
  SL1.SListPrint();
  SL1.SListEraseAfter(cur);
  SL1.SListPrint();
  return 0;
}
相关文章
|
6天前
|
存储 缓存 C++
C++链表常用的函数编写(增查删改)内附完整程序
C++链表常用的函数编写(增查删改)内附完整程序
|
6天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
43 0
|
6天前
|
存储 算法 程序员
深入理解 C++ 自定义链表中实现迭代器
深入理解 C++ 自定义链表中实现迭代器
61 0
|
6天前
|
存储 算法 Linux
【C/C++ 线性表】C++ 从零开始实现 双向循环链表(Exploring Doubly Circular Linked List in C++)
【C/C++ 线性表】C++ 从零开始实现 双向循环链表(Exploring Doubly Circular Linked List in C++)
67 0
|
6天前
|
存储 算法 编译器
【C/C++ 数据结构 线性表】 数据结构 解析 链表中哨兵节点(伪节点)的作用
【C/C++ 数据结构 线性表】 数据结构 解析 链表中哨兵节点(伪节点)的作用
20 0
|
6天前
|
存储 缓存 算法
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
59 0
|
6天前
|
C语言 C++
【c++】用c++实现带头双向循环链表
【c++】用c++实现带头双向循环链表
|
6天前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
31 0
|
6天前
|
存储 算法 C++
【数据结构】链表—C/C++实现
【数据结构】链表—C/C++实现
61 1
|
6天前
|
Python Linux Ubuntu
Linux系统部署Python语言开发运行环境
Linux系统部署Python语言开发运行环境
100 0
Linux系统部署Python语言开发运行环境