C++实现循环链表 |21xrx.com

C++实现循环链表

2023-07-07 12:57:36 深夜i -- --

C++ 循环链表实现

循环链表是一种特殊的链表，在普通单向链表的基础上，最后一个节点指向头节点，形成一个环形结构。循环链表可以用来解决很多问题，比如约瑟夫问题等。C++是一种高级编程语言，其面向对象的特性可以方便快捷地实现循环链表。

首先，定义循环链表节点的结构体：


struct Node
{
  int data;    // 节点数据
  Node* next;   // 指向下一个节点的指针
};

然后，定义一个循环链表类，并在其中定义一些操作，如插入节点、删除节点、遍历节点等：


class LoopList
{
public:
  LoopList() : head(nullptr), size(0) {}
  ~LoopList() { clear(); }
  void insert(int value);
  void remove(int value);
  void clear();
  void print();
private:
  Node* head;   // 头节点指针
  int size;    // 链表长度
};

其中 insert() 方法将一个新节点插入到链表中，remove() 方法删除特定节点，clear() 方法清空整个链表，print() 方法遍历链表，输出所有节点数据。

接下来是具体的实现：


void LoopList::insert(int value)
{
  Node* newNode = new Node;
  newNode->data = value;
  newNode->next = head;
  if (head == nullptr)  // 如果链表为空
  形成环形结构
  
  else  // 如果链表不为空
  {
    Node* tail = head;
    while (tail->next != head)
    
      tail = tail->next;
    
    tail->next = newNode;  // 将尾节点指向新节点
  }
  size++;
}
void LoopList::remove(int value)
{
  if (head == nullptr)  // 如果链表为空
  
    return;
  
  Node* target = nullptr;
  if (head->data == value)  // 如果头节点是要删除的节点
  {
    target = head;
    Node* tail = head;
    while (tail->next != head)
    
      tail = tail->next;
    
    tail->next = head->next;  // 将尾节点指向新的头节点
    head = head->next;     // 将头节点指向下一个节点
  }
  else  // 如果要删除的节点不是头节点
  {
    Node* cur = head;
    while (cur->next != head && cur->next->data != value)
    
      cur = cur->next;
    
    if (cur->next == head) // 如果找不到要删除的节点
    
      return;
    
    target = cur->next;
    cur->next = cur->next->next;
  }
  delete target;
  size--;
}
void LoopList::clear()
{
  while (head != nullptr)
  {
    Node* cur = head;
    head = head->next;
    delete cur;
  }
  size = 0;
}
void LoopList::print()
{
  if (head == nullptr)  // 如果链表为空
  
    return;
  
  Node* cur = head;
  do
  
    cout << cur->data << " ";
    cur = cur->next;
   while (cur != head);
  cout << endl;
}

其中 remove() 方法需要注意，由于是循环链表，所以删除节点时要考虑头节点和其他节点不同的情况。

最后，可以在主函数中测试循环链表的实现：


int main()
{
  LoopList myList;
  for (int i = 0; i < 10; i++)
  {
    myList.insert(i);
  }
  myList.print();
  myList.remove(5);
  myList.print();
  myList.clear();
  myList.print();
  return 0;
}

上述代码创建了一个含有 10 个节点的循环链表，然后删除了一个节点，并清空了整个链表。其输出结果如下：

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 6 7 8 9

可以看出，循环链表的实现是正确的。

上一篇: idea打包java可执行jar包

下一篇: C++实现获取指定月份的天数

评论区

()

相似文章