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

C++循环链表的实现

2023-07-12 07:05:04 深夜i -- --

C++ 循环链表实现数据结构链表操作

C++循环链表是一种非常常见的数据结构，它可以在一个链表的最后一个节点和第一个节点之间建立一个循环，循环链表可以用来在数据序列中进行循环查找、添加、删除等操作，同时也可以用来实现队列和栈等数据结构。

循环链表的实现主要包括节点类和链表类两部分。

1. 节点类的实现

节点类用来定义链表节点的属性和操作，通常包括数据域和指针域。代码如下：


template <typename T>
class Node{
public:
  T data; // 数据域
  Node<T> *next; // 指针域
  Node(T d, Node<T> *n=NULL)
    data = d;
    next = n;
  
};

2. 链表类的实现

链表类用来实现链表的基本操作，包括插入、删除、遍历、查找等操作。在循环链表中，需要特别注意的是头节点和尾节点的处理。代码如下：


template <typename T>
class CircularLinkedList{
public:
  Node<T> *head; // 头节点指针
  CircularLinkedList(){
    head = new Node<T>(0); // 创建头节点
    head->next = head; // 空链表中头节点的指针指向它本身
  }
  ~CircularLinkedList(){
    Node<T> *p = head, *q;
    while(p != head)
      q = p->next;
      delete p;
      p = q;
    
    delete head; // 删除头节点
  }
  void insert(T d, int pos=0){ // 在第pos个节点后插入新节点
    Node<T> *p = head, *q;
    for(int i=0;i<pos && p->next!=head;i++) p = p->next;
    q = new Node<T>(d, p->next);
    p->next = q;
  }
  void remove(int pos){ // 删除第pos个节点
    Node<T> *p = head, *q;
    for(int i=0;i<pos && p->next!=head;i++) p = p->next;
    if(p->next != head)
      q = p->next;
      p->next = q->next;
      delete q;
    
  }
  Node<T>* find(T d){ // 查找特定数据的节点
    Node<T> *p = head->next;
    while(p != head && p->data != d) p = p->next;
    if(p == head) return NULL;
    return p;
  }
};

以上就是C++循环链表的实现。可以看到，循环链表和普通链表的实现差别不大，只需注意头节点和尾节点的处理即可。循环链表是一种非常实用的数据结构，可以用于解决很多实际问题。

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

下一篇: C++ Map的全面解析

评论区

()

相似文章