C语言单向链表的表示与实现实例详解

介绍

单向链表是一种常见的数据结构，它由若干个节点构成，每个节点包含一个数据域和一个指向下一个节点的指针。单向链表通常用于需要频繁插入、删除节点的场景，如操作系统的进程调度、内存管理等。

本文将介绍C语言中单向链表的表示和实现，包括链表的定义、插入节点、删除节点等操作。

链表的定义

在C语言中，链表通常由一个结构体表示，该结构体包含一个数据域和一个指向下一个节点的指针。如下所示：

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

其中，data为节点的数据域，next为指向下一个节点的指针。当next为空指针NULL时，表示链表结束。

插入节点

插入节点是链表中最常见的操作之一。它需要在链表中找到一个指定的位置，将新节点插入到该位置。在C语言中，插入节点的代码示例如下：

void insert_node(struct node* head, int data, int pos) {
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;

    struct node* current = head;
    int i = 0;
    while (current != NULL && i < pos - 1) {
        current = current->next;
        i++;
    }

    if (current == NULL) {
        printf("Error: invalid position");
        return;
    }

    new_node->next = current->next;
    current->next = new_node;
}

该函数接受三个参数：链表头指针head、新节点的数据data和新节点需要插入到的位置pos。首先，该函数分配一个新节点，并将数据data存储到该节点的数据域中。然后，遍历链表，找到需要插入的位置，将新节点插入到该位置。

删除节点

删除节点是链表中另一个常见的操作。它需要找到链表中一个指定的节点，并将其从链表中删除。在C语言中，删除节点的代码示例如下：

void delete_node(struct node* head, int pos) {
    struct node* current = head;
    int i = 0;
    while (current != NULL && i < pos - 1) {
        current = current->next;
        i++;
    }

    if (current == NULL || current->next == NULL) {
        printf("Error: invalid position");
        return;
    }

    struct node* temp = current->next;
    current->next = temp->next;
    free(temp);
}

该函数接受两个参数：链表头指针head和需要删除的节点的位置pos。首先，该函数遍历链表，找到需要删除的节点的前一个节点。然后，将需要删除的节点从链表中断开，并释放该节点所占用的内存。

示例说明

假设我们有一个整数类型的单向链表，包含以下几个节点：

1 -> 2 -> 3 -> 4 -> 5

现在要在第三个节点的后面插入一个新节点6，代码示例如下：

insert_node(head, 6, 3);

执行代码后，链表变成：

1 -> 2 -> 3 -> 6 -> 4 -> 5

然后，我们要将第四个节点删除，代码示例如下：

delete_node(head, 4);

执行代码后，链表变成：

1 -> 2 -> 3 -> 4 -> 5

总结

本文介绍了C语言中单向链表的表示和实现，包括链表的定义、插入节点、删除节点等操作。单向链表是一种常见的数据结构，掌握它的基本操作对于理解其他数据结构也是非常有益的。