C++单链表基本操作实现 |21xrx.com

C++单链表基本操作实现

2023-06-22 19:02:59 深夜i 19 0

C++ 单链表基本操作实现

在C++中，单链表是一种常见的数据结构。它是一种线性表，由节点组成，每个节点包含一个存储元素的数据部分和一个指向下一个节点的指针部分。单链表的基本操作包括创建、插入、删除、查找和遍历等。

首先，我们需要定义一个节点类型。节点类型包含两部分内容，一个存储具体数据的成员和一个指向下一个节点的指针成员。代码如下：

struct Node{
  int data;  // 存储数据的成员
  Node* next; // 指向下一个节点的指针成员
};

接下来，我们需要定义一个链表类。链表类包含多个成员函数，用于实现链表的基本操作。代码如下：

class LinkedList{
private:
  Node* head; // 头节点指针
public:
  LinkedList();     // 构造函数，初始化头节点
  ~LinkedList();     // 析构函数，释放链表空间
  void insert(int data); // 插入新的节点
  void remove(int data); // 删除节点
  Node* search(int data);// 查找节点
  void display();    // 遍历链表，输出每个节点的值
};

在链表类的构造函数中，我们需要初始化头节点。头节点是一个特殊节点，它不包含存储任何数据的成员，只是为了方便操作而设置的。头节点的next成员指向链表中的第一个实际节点。代码如下：

LinkedList::LinkedList()
  head = new Node;
  head->next = NULL;

在链表类的析构函数中，我们需要释放链表的空间。从头节点开始，依次释放每个节点的空间。代码如下：

LinkedList::~LinkedList(){
  Node* p = head;
  while(p != NULL){
    Node* temp = p;
    p = p->next;
    delete temp;
  }
}

插入新的节点时，我们需要找到插入位置的前一个节点，然后将新节点插入到该位置之后。代码如下：

void LinkedList::insert(int data){
  Node* p = head;
  while(p->next != NULL && p->next->data < data)
    p = p->next;
  
  Node* newNode = new Node;
  newNode->data = data;
  newNode->next = p->next;
  p->next = newNode;
}

删除节点时，我们需要找到要删除的节点，并将它的前一个节点的next指针指向它的下一个节点。代码如下：

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

查找节点时，我们需要依次遍历每个节点，直到找到与要查找的值相等的节点。代码如下：

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

遍历链表时，我们需要依次输出每个节点的值。代码如下：

void LinkedList::display(){
  Node* p = head->next;
  while(p != NULL)
    cout << p->data << " ";
    p = p->next;
  
  cout << endl;
}

综上所述，实现单链表的基本操作需要定义节点类型和链表类，并实现插入、删除、查找和遍历等操作。这些操作是C++程序中常用的数据结构操作，在实际开发中具有广泛的应用。

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

下一篇: C++实现判断两个数之间的素数

评论区

相似文章