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

C++ 单向循环链表实现

2023-07-10 04:14:30 深夜i 19 0

C++ 单向循环链表实现

单向循环链表是一种比较常见的线性数据结构，它与单向链表的区别在于，单向循环链表的尾结点指向头结点，形成一个环。这意味着可以从任何一个结点开始遍历整个链表，且可以轻松地实现一些循环遍历的操作。本文将介绍如何使用 C++ 实现单向循环链表。

首先，我们需要定义一个节点结构体，用来表示链表中的每个结点。它通常包含两个成员变量，一个是储存数据的变量，另一个是指向下一个节点的指针。定义如下：

struct Node{
  int data;
  Node* next;
};

接下来，我们需要定义链表类，包括头结点指针、链表长度以及实现一些基本的操作函数，比如插入、删除、查找等等。具体实现如下：

class CircularLinkedList{
private:
  Node* head;
  int length;
public:
  CircularLinkedList()
    head = NULL;
    length = 0;
  
  void addNode(int data){
    Node* newNode = new Node;
    newNode->data = data;
    if(head == NULL)
      head = newNode;
      newNode->next = head;
    else{
      Node* temp = head;
      while(temp->next != head)
        temp = temp->next;
      
      temp->next = newNode;
      newNode->next = head;
    }
    length++;
  }
  void removeNode(int data){
    if(head == NULL)
      return;
    
    Node* temp = head;
    Node* prev = NULL;
    while(temp->data != data){
      if(temp->next == head)
        return;
      
      prev = temp;
      temp = temp->next;
    }
    if(temp == head)
      head = head->next;
    
    prev->next = temp->next;
    length--;
    delete temp;
  }
  Node* findNode(int data){
    if(head == NULL)
      return NULL;
    
    Node* temp = head;
    while(temp->data != data){
      if(temp->next == head)
        return NULL;
      
      temp = temp->next;
    }
    return temp;
  }
  void display(){
    if(head == NULL)
      return;
    
    Node* temp = head;
    while(temp->next != head)
      cout << temp->data << "->";
      temp = temp->next;
    
    cout << temp->data << endl;
  }
};

在以上的代码实现中，我们实现了 addNode() 函数来在链表末尾添加结点；removeNode() 函数来删除指定数据的结点；findNode() 函数来查找链表中指定数据的结点；以及 display() 函数来打印链表中所有结点的值。需要注意的是，在删除结点时，需要找到要删除结点的前一个结点 prev，以便将它的 next 指针指向要删除结点的下一个结点。

最后，我们可以在 main() 函数中创建一个 CircularLinkedList 对象，然后使用它的函数来操作链表。如下所示：

int main(){
  CircularLinkedList list;
  list.addNode(1);
  list.addNode(2);
  list.addNode(3);
  list.addNode(4);
  list.display();
  list.removeNode(3);
  list.display();
  Node* foundNode = list.findNode(2);
  if(foundNode != NULL)
    cout << "Found node with data: " << foundNode->data << endl;
  
  return 0;
}

在以上代码中，我们首先创建了一个 CircularLinkedList 对象 list，并使用它的 addNode() 函数在链表末尾添加了四个结点，然后使用 display() 函数打印链表中的所有结点。接下来，我们使用 removeNode() 函数删除链表中数据为 3 的结点，然后再次使用 display() 函数打印链表中的所有结点。最后，我们使用 findNode() 函数查找链表中数据为 2 的结点，并打印出它的数据值。

总结一下，在本文中我们使用 C++ 实现了单向循环链表，并实现了 addNode()、removeNode()、findNode() 和 display() 等基本操作。通过这些操作，我们可以轻松地在链表中添加、删除和查找结点，希望对您理解和使用单向循环链表有所帮助。

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

下一篇: C++程序模块的构建与使用

评论区

相似文章