C++ 实现单链表的构造 |21xrx.com

C++ 实现单链表的构造

2023-07-02 16:28:44 深夜i 11 0

C++ 单链表构造

单链表是一种常见的数据结构，其使用基于指针的链式存储结构将数据连接起来。在 C++ 中，可以通过自定义一个类来实现单链表的构造。

首先，定义一个节点类 Node，该类包含一个数据成员和一个指向下一个节点的指针成员。节点类的定义如下：

class Node {
public:
  int data;
  Node* next;
};

接下来，定义一个单链表类 LinkedList，该类包含一个指向头节点的指针成员和一些常见的操作方法，如头插、尾插、删除、查找等。单链表类的定义如下：

class LinkedList {
private:
  Node* head;
public:
  LinkedList();
  ~LinkedList();
  void push_front(int data);
  void push_back(int data);
  void pop_front();
  void pop_back();
  bool empty();
  int front();
  int back();
  int size();
  void clear();
  Node* find(int data);
};

在类的实现中，可以使用动态内存分配来实现节点的插入和删除操作，即通过 new 和 delete 关键字来分别创建和释放节点对象。以下是单链表类的主要操作方法的实现：

LinkedList::LinkedList()
  head = new Node;
  head->next = NULL;
LinkedList::~LinkedList() {
  clear();
  delete head;
}
void LinkedList::push_front(int data) {
  Node* new_node = new Node;
  new_node->data = data;
  new_node->next = head->next;
  head->next = new_node;
}
void LinkedList::push_back(int data) {
  Node* ptr = head;
  while (ptr->next != NULL)
    ptr = ptr->next;
  
  Node* new_node = new Node;
  new_node->data = data;
  new_node->next = NULL;
  ptr->next = new_node;
}
void LinkedList::pop_front() {
  if (head->next == NULL)
    return;
  
  Node* temp = head->next;
  head->next = head->next->next;
  delete temp;
}
void LinkedList::pop_back() {
  if (head->next == NULL)
    return;
  
  Node* ptr = head;
  while (ptr->next->next != NULL)
    ptr = ptr->next;
  
  Node* temp = ptr->next;
  ptr->next = NULL;
  delete temp;
}
bool LinkedList::empty()
  return head->next == NULL;
int LinkedList::front()
  return head->next->data;
int LinkedList::back() {
  Node* ptr = head;
  while (ptr->next != NULL)
    ptr = ptr->next;
  
  return ptr->data;
}
int LinkedList::size() {
  int count = 0;
  Node* ptr = head->next;
  while (ptr != NULL) {
    count++;
    ptr = ptr->next;
  }
  return count;
}
void LinkedList::clear() {
  Node* ptr = head;
  while (ptr->next != NULL) {
    Node* temp = ptr->next;
    ptr->next = ptr->next->next;
    delete temp;
  }
}
Node* LinkedList::find(int data) {
  Node* ptr = head->next;
  while (ptr != NULL) {
    if (ptr->data == data)
      return ptr;
    
    ptr = ptr->next;
  }
  return NULL;
}

以上就是使用 C++ 实现单链表的构造的方法。通过自定义一个节点类和一个单链表类，并实现各种常见的操作方法，可以高效地存储和管理数据。

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

下一篇: C++中常用的分隔符

评论区

相似文章