21xrx.com
2025-03-31 06:22:00 Monday
文章检索 我的文章 写文章
如何用C++写链表
2023-06-29 12:39:43 深夜i     14     0
C++ 链表 结点 指针 操作

链表（Linked List）是一种非常常见的数据结构，它把一组数据节点通过指针连接起来，构成一个链式结构，每个节点都包含一个数据元素和一个指向下一个节点的指针。链表可以实现大多数数组可以实现的操作，包括插入、删除、查找等操作，但是它比数组更灵活，可以实现动态扩展和缩小的功能。

在 C++ 中，我们可以通过定义一个结构体来表示链表的节点，如下所示：

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

其中，data 表示节点的数据元素，next 表示指向下一个节点的指针。我们可以通过定义一个指向 Node 结构体类型的指针来表示整个链表的头节点，如下所示：

Node* head = NULL;

这里的 head 只是一个指向链表起始节点的指针，我们还需要定义一些函数来对链表进行操作。下面是一个常见的链表操作函数列表：

- insert: 在链表中插入一个新的节点

- remove: 从链表中删除一个节点

- search: 在链表中查找给定元素

- print: 打印链表的全部元素

接下来我们将分别详细介绍这些操作函数的实现。

1. 插入节点

链表中插入节点的操作分为两种情况。如果要在链表的开头插入一个新节点，我们需要把新节点插入到链表的头部：

// 在链表开头插入一个新节点
void insert(int x) {
  Node* p = new Node;
  p->data = x;
  p->next = head;
  head = p;
}

这里我们首先使用关键字 new 动态申请一个新节点的内存空间，然后简单地将这个新节点的指针设置为原来的头节点，最后将新节点设置为头节点。

如果要在链表的中间或者末尾插入一个新节点，我们需要遍历链表找到需要插入的位置，然后执行插入操作：

// 在链表中间或末尾插入一个新节点
void insert(int x, int pos) {
  Node* p = new Node;
  p->data = x;
  Node* q = head;
  for (int i = 0; i < pos - 2; i++)
    q = q->next;
  
  p->next = q->next;
  q->next = p;
}

这里我们首先创建一个新节点 p，然后遍历链表找到插入位置 pos 的前一个节点 q，然后将新节点的 next 指针指向 q 的下一个节点，然后将 q 的 next 指针指向新节点 p。

2. 删除节点

从链表中删除一个节点也存在两种情况。如果要删除的节点是头节点，我们直接将头节点指向下一个节点即可：

// 删除链表头节点
void removeHead() {
  Node* p = head;
  head = head->next;
  delete p;
}

这里我们首先创建一个指向头节点的指针 p，然后将头节点指向下一个节点，最后释放掉 p 的内存空间。

如果要删除链表中的其他节点，我们需要遍历链表找到需要删除的位置，然后执行删除操作：

// 删除链表中间或末尾的节点
void remove(int pos) {
  Node* p = head;
  for (int i = 0; i < pos - 2; i++)
    p = p->next;
  
  Node* q = p->next;
  p->next = q->next;
  delete q;
}

这里我们首先遍历链表找到需要删除的位置 pos 的前一个节点 p，然后创建一个指向需要删除的节点的指针 q，将 p 的 next 指针指向 q 的下一个节点，最后释放 q 的内存空间即可。

3. 查找节点

在链表中查找给定元素需要遍历整个链表，依次比较每个节点的数据元素是否等于给定元素，如果找到相等的节点，返回这个节点的指针，否则返回空指针：

// 在链表中查找给定元素
Node* search(int x) {
  Node* p = head;
  while (p != NULL) {
    if (p->data == x)
      return p;
    
    p = p->next;
  }
  return NULL;
}

这里我们首先创建一个指向头节点的指针 p，然后不断遍历整个链表，依次比较每个节点的数据元素和 x 是否相等，如果相等则返回这个节点的指针，否则将指针指向下一个节点，继续搜索，直到整个链表被遍历完毕。

4. 打印节点

打印链表中的所有元素需要遍历整个链表，依次输出每个节点的数据元素：

// 打印链表中的所有元素
void print() {
  Node* p = head;
  while (p != NULL)
    cout << p->data << " ";
    p = p->next;
  
  cout << endl;
}

这里我们首先创建一个指向头节点的指针 p，然后不断遍历整个链表，依次输出每个节点的数据元素，最后输出一个换行符。这样就能非常方便地查看链表中的所有元素了。

最后，我们需要在主函数中调用这些操作函数，来构建和操作链表。整个代码如下所示：

#include <iostream>
using namespace std;
// 定义链表节点结构体
struct Node {
  int data;
  Node* next;
};
// 定义链表头指针
Node* head = NULL;
// 在链表开头插入一个新节点
void insert(int x) {
  Node* p = new Node;
  p->data = x;
  p->next = head;
  head = p;
}
// 在链表中间或末尾插入一个新节点
void insert(int x, int pos) {
  Node* p = new Node;
  p->data = x;
  Node* q = head;
  for (int i = 0; i < pos - 2; i++)
    q = q->next;
  
  p->next = q->next;
  q->next = p;
}
// 删除链表头节点
void removeHead() {
  Node* p = head;
  head = head->next;
  delete p;
}
// 删除链表中间或末尾的节点
void remove(int pos) {
  Node* p = head;
  for (int i = 0; i < pos - 2; i++)
    p = p->next;
  
  Node* q = p->next;
  p->next = q->next;
  delete q;
}
// 在链表中查找给定元素
Node* search(int x) {
  Node* p = head;
  while (p != NULL) {
    if (p->data == x)
      return p;
    
    p = p->next;
  }
  return NULL;
}
// 打印链表中的所有元素
void print() {
  Node* p = head;
  while (p != NULL)
    cout << p->data << " ";
    p = p->next;
  
  cout << endl;
}
// 主函数
int main() {
  insert(1);
  insert(2);
  insert(3);
  insert(4, 1);
  removeHead();
  remove(2);
  print();
  return 0;
}

以上就是使用 C++ 写链表的全部内容，希望可以对你有所帮助！

  
  

评论区