C语言中带头结点的单链表的建立与操作

# 1. **引言**

- 简介
- 单链表概述
- 头结点的作用

# 2. 带头结点的单链表的定义

在C语言中，为了更方便地对单链表进行操作，引入了头结点的概念。头结点是一个不存放有效数据的节点，仅用于指向链表的第一个节点，从而简化链表的插入、删除等操作。下面将详细介绍带头结点的单链表的定义。

### 结构体定义

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 头结点结构体
typedef struct {
    Node* head;         // 指向链表第一个节点的指针
} LinkedList;

在上面的结构体定义中，`Node`代表链表节点，包含数据域 `data` 和指针域 `next`；`LinkedList`代表带头结点的单链表，包含指向链表第一个节点的指针 `head`。

### 头结点的初始化

为了方便后续操作，需要初始化头结点：

// 初始化带头结点的单链表
void initLinkedList(LinkedList* list) {
    list->head = (Node*)malloc(sizeof(Node));
    if (list->head == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    list->head->next = NULL;
}

通过以上代码，我们定义了带头结点的单链表的结构体，并实现了初始化带头结点的单链表的方法。在下一节中，我们将介绍如何使用头结点来实现带头结点单链表的建立。

# 3. 带头结点单链表的建立

在C语言中，带头结点单链表的建立常见的有两种方法：头插法和尾插法。

**头插法建立方法**：

头插法是在链表的头部插入新节点，即新节点始终保持在链表的第一个位置。代码实现如下：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 初始化带头结点的单链表
Node* initList() {
    Node *head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

// 头插法建立链表
void headInsert(Node *head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

// 主函数中的调用示例
int main() {
    Node *head = initList();
    // 头插法插入节点
    headInsert(head, 3);
    headInsert(head, 2);
    headInsert(head, 1);
    return 0;
}

**尾插法建立方法**：

尾插法是在链表的尾部插入新节点，即新节点始终保持在链表的最后一个位置。代码实现如下：

// 尾插法建立链表
void tailInsert(Node *head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    Node *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

// 主函数中的调用示例
int main() {
    Node *head = initList();
    // 尾插法插入节点
    tailInsert(head, 1);
    tailInsert(head, 2);
    tailInsert(head, 3);
    return 0;
}

以上是带头结点单链表建立过程中的头插法和尾插法方法，可以根据实际需求选择合适的建立方式。

# 4. **带头结点单链表的基本操作**

在带头结点的单链表中，我们可以进行一些基本的操作，包括插入节点、删除节点和查找节点等。接下来我们将详细介绍这些基本操作的实现方法。

#### **插入节点操作**

插入节点操作可以分为两种情况：在指定位置插入节点和在指定数值后插入节点。具体实现代码如下：

// 在指定位置插入节点
void insertNodeAtPosition(struct Node* head, int position, int data) {
    int i = 0;
    struct Node* p = head;
    while (p != NULL && i < position) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        printf("Error: Invalid position!\n");
        return;
    }

    struct Node* newNode = createNode(data);
    newNode->next = p->next;
    p->next