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

在C++编程中，单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和指向下一个节点的指针。带头结点的单链表在链表的开始处添加了一个特殊的节点，称为头结点，它的数据部分通常不存储实际的数据，而是作为链表的起点。本文将详细探讨如何实现带头结点单链表的基本操作，包括逆序建立链表、插入和删除等操作。 我们定义单链表节点的结构体： ```cpp struct ListNode { int data; // 存储数据 ListNode* next; // 指向下一个节点的指针 }; ``` **逆序建立链表**： 逆序建立链表意味着从输入数据的末尾开始构建链表。例如，给定数组{1, 2, 3, 4}，逆序链表将是4->3->2->1。实现方法是通过一个临时节点，从最后一个元素开始，逐个将元素添加到链表头部： ```cpp ListNode* reverseBuild(int arr[], int size) { ListNode* head = new ListNode(); ListNode* temp = head; for (int i = size - 1; i >= 0; --i) { ListNode* newNode = new ListNode(arr[i]); temp->next = newNode; temp = newNode; } return head; } ``` **插入操作**： 在链表的特定位置插入一个新节点，我们需要找到插入点的前一个节点，然后将新节点插入到它们之间。以下是在索引`pos`处插入值`val`的函数： ```cpp void insert(ListNode*& head, int pos, int val) { if (pos == 0) { ListNode* newNode = new ListNode(val); newNode->next = head; head = newNode; } else { ListNode* curr = head; for (int i = 0; i < pos - 1 && curr != nullptr; ++i) curr = curr->next; if (curr == nullptr) return; // 如果位置超出链表范围，则返回 ListNode* newNode = new ListNode(val); newNode->next = curr->next; curr->next = newNode; } } ``` **删除操作**： 删除链表中的某个节点需要找到要删除节点的前一个节点，然后更新其`next`指针。以下是在索引`pos`处删除节点的函数： ```cpp ListNode* removeAt(ListNode*& head, int pos) { if (pos == 0) { ListNode* temp = head; head = head->next; delete temp; return head; } ListNode* curr = head; for (int i = 0; i < pos - 1 && curr != nullptr; ++i) curr = curr->next; if (curr == nullptr) return head; // 如果位置超出链表范围，则返回原链表 ListNode* temp = curr->next; curr->next = curr->next->next; delete temp; return head; } ``` 以上就是带头结点单链表的基本操作实现。在实际编程中，还需要考虑异常处理和内存管理，例如在分配和释放节点时防止内存泄漏。此外，还可以扩展这些基础功能，例如实现查找、排序、合并等高级操作。在C++中，理解并熟练使用单链表是学习数据结构和算法的基础，对于提升编程能力具有重要意义。