带头节点的单链表C++

### 带头节点的单链表 C++ 实现 在 C++ 中实现带头节点的单链表时，通常会创建一个额外的节点作为头部节点（也称为哑节点），该节点并不存储实际的数据，仅用于简化某些操作逻辑。以下是完整的实现示例： #### 1. 节点结构定义 首先定义单链表中的节点结构 `ListNode`，它包含两个成员：一个是存储数据的整型变量 `data`，另一个是指向下一个节点的指针 `next`。 ```cpp // 定义单链表的节点结构 struct ListNode { int data; ListNode* next; // 构造函数初始化节点 ListNode(int val = 0, ListNode* ptr = nullptr) : data(val), next(ptr) {} }; ``` #### 2. 初始化带头节点的单链表 通过分配一个新的节点来充当头节点，并将其 `next` 指针置为 `nullptr` 表示初始状态下的空列表。 ```cpp // 初始化带虚拟头节点的单链表 void initList(ListNode*& head) { head = new ListNode(); // 创建新的头节点，默认构造函数使其 next 为 nullptr } ``` 此部分基于已有资料进行了扩展[^3]。 #### 3. 插入新节点到链表尾部 为了支持动态添加元素，在此处提供一种将新节点追加至链表末端的功能。 ```cpp // 尾插法插入节点 void appendNode(ListNode* head, int value) { ListNode* newNode = new ListNode(value); if (!head->next) { // 如果当前链表为空，则直接连接 head->next = newNode; } else { ListNode* temp = head; while (temp->next != nullptr) { // 遍历直到找到最后一个节点 temp = temp->next; } temp->next = newNode; // 连接新节点 } } ``` 上述代码片段展示了如何安全地向已存在的单链表中增加新项[^2]。 #### 4. 打印整个链表的内容 最后编写辅助功能用来展示所有保存于链表内的数值序列。 ```cpp // 输出链表内容 void printList(const ListNode* head) { const ListNode* current = head->next; // 忽略头节点本身 while (current != nullptr) { printf("%d -> ", current->data); current = current->next; } puts("NULL"); } ``` 这部分实现了遍历打印除头节点外的实际数据节点[^1]。 #### 主程序测试案例 综合以上各模块构建完整应用实例如下所示： ```cpp #include <iostream> using namespace std; int main() { ListNode* head = nullptr; initList(head); // 初始化带有头节点的单链表 // 添加一些节点 appendNode(head, 10); appendNode(head, 20); appendNode(head, 30); cout << "The list contains:" << endl; printList(head); // 显示最终结果 delete head; // 清理内存资源 return 0; } ``` 注意释放不再使用的对象以防止泄露问题发生[^4]。