C++实现单链表的定义 |21xrx.com

C++实现单链表的定义

2023-07-04 19:27:35 深夜i -- --

C++ 单链表定义

单链表是一种由节点构成的数据结构，每个节点包含元素以及指向下一个节点的指针。该结构可以用于队列、堆栈、哈希表等数据结构的实现。C++作为一门高效、强大的编程语言，可以用于实现单链表。

在C++中，可以使用结构体定义一个节点：


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

其中data表示该节点存储的数据，next则为指向下一个节点的指针。这里使用指针的原因是节点的大小不确定，而指针的大小是固定的。这样可以避免浪费过多的内存。

定义好节点后，就可以定义链表了。链表由头节点和若干个子节点组成，因此需要定义头节点以及指向它的指针。以下是链表的定义：


class LinkedList{
private:
  Node* head;
public:
  LinkedList();
  void insert(int data);
  void remove(int data);
  Node* search(int data);
};

其中LinkedList是链表的类名，head是头节点的指针。insert方法用于向链表中插入一个数据，remove方法用于从链表中删除一个数据，search方法用于在链表中查找一个数据。

链表的构造函数初始化头节点：


LinkedList::LinkedList()
  head = NULL;

insert方法的实现如下：


void LinkedList::insert(int data){
  Node* new_node = new Node;
  new_node->data = data;
  new_node->next = head;
  head = new_node;
}

该方法首先创建一个新节点，将数据存储到其中，然后将该节点指向头节点，最后将头节点指针指向新节点。这样就实现了向链表头部插入一个节点的功能。

remove方法的实现如下：


void LinkedList::remove(int data){
  Node* prev = NULL;
  Node* curr = head;
  while (curr != NULL && curr->data != data)
    prev = curr;
    curr = curr->next;
  
  if (curr == NULL) return;
  if (prev == NULL) head = curr->next;
  else prev->next = curr->next;
  delete curr;
}

该方法首先遍历链表，找到要删除的节点。如果该节点不存在，直接返回。如果该节点是头节点，则将头节点指针指向下一个节点。如果不是头节点，则将前一个节点的next指针指向下一个节点。最后删除该节点。这样就实现了从链表中删除一个节点的功能。

search方法的实现如下：


Node* LinkedList::search(int data){
  Node* curr = head;
  while (curr != NULL && curr->data != data)
    curr = curr->next;
  
  return curr;
}

该方法遍历链表查找指定数据的节点。如果该节点不存在，返回NULL。如果存在，返回该节点的指针。

以上就是使用C++实现单链表的定义。单链表是一种简单、灵活的数据结构，可以用于许多场合。使用C++语言可以灵活高效地实现其定义和操作。

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

下一篇: 10次for循环的C++重复执行

评论区

()

相似文章