C语言数据结构之单链表操作详解

本文将详细讲解C语言数据结构中单链表的操作方法，包括单链表的建立、遍历、插入、删除等操作，并提供两个示例进行说明。

单链表的定义

单链表是一种常见的动态数据结构，由若干节点组成，每个节点通常包含一个数据元素和一个指向下一个节点的指针。单链表最后一个节点的指针指向NULL，表示链表的结尾。

单链表的节点定义

单链表的节点通常由结构体定义，包含数据和指向下一个节点的指针。定义如下：

typedef struct Node
{
    int data;
    struct Node *next;
} Node, *PNode;

其中，data表示节点的数据，next指向下一个节点。

单链表的建立

单链表的建立过程即为不断插入节点的过程，通过设置一个指向头节点的指针，不断向其中添加节点即可。

PNode CreateLinkedList(int n)
{
    PNode head, p, q;
    int i;

    head = (PNode)malloc(sizeof(Node));
    head->next = NULL;

    q = head;

    for (i = 0; i < n; i++)
    {
        p = (PNode)malloc(sizeof(Node));
        printf("请输入第%d个节点的值：", i+1);
        scanf_s("%d", &p->data);
        q->next = p;
        q = p;
    }
    p->next = NULL;

    return head;
}

上述代码中，先创建一个指向头节点的指针head（初始指向NULL），再依次循环添加节点，每次添加时需要按照如下方式进行：

1. 创建新节点p；
2. 设置p的数据值；
3. 将节点p加入到链表中，即将p链接到q的后面；
4. 将q指向p，更新q的位置。

单链表的遍历

遍历单链表的过程即为顺序访问每个节点的过程，通常使用while循环来实现。

void TraverseLinkedList(PNode head)
{
    PNode p = head->next;

    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

上述代码中，先将指针p指向第一个节点，然后依次输出每个节点的数据值，直到p指向NULL结束。

单链表的插入

单链表的插入操作即为在链表中加入新节点的过程。新节点插入到链表中间时，必须先找到其前驱节点，再进行链接操作。

int InsertLinkedList(PNode head, int i, int x)
{
    PNode p = head, q;
    int j = 0;

    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL || j > i - 1)
    {
        return 0;
    }

    q = (PNode)malloc(sizeof(Node));
    q->data = x;
    q->next = p->next;
    p->next = q;

    return 1;
}

上述代码中，先找到第i个节点的前驱节点p，然后创建新节点q，并将其链接到p的后面，最终返回1表示插入成功，返回0表示插入失败。

单链表的删除

单链表的删除操作即为删除链表中某个节点的过程。删除节点时，必须找到其前驱节点，并将前驱节点与后继节点链接起来。

int DeleteLinkedList(PNode head, int i)
{
    PNode p = head, q;
    int j = 0;

    while (p->next != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p->next == NULL || j > i - 1)
    {
        return 0;
    }

    q = p->next;
    p->next = q->next;
    free(q);

    return 1;
}

上述代码中，先找到第i个节点的前驱节点p，然后将p与q的后继节点链接起来，最终删除节点q。

示例1

例如，现有如下节点已经按顺序插入到链表中：1 2 3 4 5，若要在第3个节点后插入节点6，可按照如下方式实现：

PNode head = CreateLinkedList(5);
printf("插入前：");
TraverseLinkedList(head);

InsertLinkedList(head, 3, 6);
printf("插入后：");
TraverseLinkedList(head);

输出结果如下：

请输入第1个节点的值：1
请输入第2个节点的值：2
请输入第3个节点的值：3
请输入第4个节点的值：4
请输入第5个节点的值：5
插入前：1 2 3 4 5 
插入后：1 2 3 6 4 5 

示例2

再如，现有如下节点已经按顺序插入到链表中：1 2 3 4 5，若要删除第2个节点，可按照如下方式实现：

PNode head = CreateLinkedList(5);
printf("删除前：");
TraverseLinkedList(head);

DeleteLinkedList(head, 2);
printf("删除后：");
TraverseLinkedList(head);

输出结果如下：

请输入第1个节点的值：1
请输入第2个节点的值：2
请输入第3个节点的值：3
请输入第4个节点的值：4
请输入第5个节点的值：5
删除前：1 2 3 4 5 
删除后：1 3 4 5 

以上为单链表的建立、遍历、插入、删除等基本操作详解，并提供两个示例进行说明。