21xrx.com
2025-03-22 06:05:26 Saturday
文章检索 我的文章 写文章
C++实现单向链表
2023-06-23 18:26:03 深夜i     16     0
C++ 单向链表 实现

C++是广泛使用的编程语言，它可以用于实现各种数据结构和算法。其中一个非常常见和基础的数据结构是链表。链表是一种动态数据结构，它可以动态增加和删除元素。它由节点组成，每个节点包含一个数据和一个指针，指向下一个节点。C++中可以使用指针和类来实现单向链表。

首先我们来定义一个链表节点类，包含一个数据成员和一个指向下一个节点的指针成员：

class Node {
public:
  int data;
  Node* next;
  Node(int d) : data(d), next(nullptr) {}
};

然后我们定义一个链表类，它包含一个指向头节点的指针和链表中节点的数量：

class LinkedList {
public:
  Node* head;
  int size;
  LinkedList() : head(nullptr), size(0) {}
};

链表的基本操作有插入、删除和打印。下面我们来实现这些操作：

void insert(LinkedList &list, int data) {
  Node* new_node = new Node(data);
  if (list.head == nullptr)
    list.head = new_node;
   else {
    Node* curr = list.head;
    while (curr->next != nullptr)
      curr = curr->next;
    
    curr->next = new_node;
  }
  list.size++;
}
void remove(LinkedList &list, int data) {
  if (list.head == nullptr)
    return;
  
  if (list.head->data == data) {
    Node* temp = list.head;
    list.head = list.head->next;
    delete temp;
    list.size--;
    return;
  }
  Node* curr = list.head;
  while (curr->next != nullptr && curr->next->data != data)
    curr = curr->next;
  
  if (curr->next != nullptr) {
    Node* temp = curr->next;
    curr->next = curr->next->next;
    delete temp;
    list.size--;
  }
}
void print(const LinkedList &list) {
  Node* curr = list.head;
  while (curr != nullptr)
    cout << curr->data << " ";
    curr = curr->next;
  
  cout << endl;
}

现在我们可以在主函数中创建一个链表对象，然后进行插入、删除和打印操作：

int main() {
  LinkedList list;
  insert(list, 1);
  insert(list, 2);
  insert(list, 3);
  print(list); // 输出：1 2 3
  remove(list, 2);
  print(list); // 输出：1 3
  return 0;
}

通过上述代码，我们成功地使用C++实现了单向链表。链表作为一种基础数据结构，是许多高级算法的基础，如图论、高级搜索、排序等。熟练掌握链表的实现原理和操作，有助于提高算法和程序设计能力。

  
  

评论区