C语言之单链表的插入、删除与查找

C语言中单链表的插入、删除与查找是单链表操作中的基本操作。下面将对这三种操作进行详细讲解。

单链表基本知识

在讲解单链表的操作前，我们先来复习一下单链表的基本概念。单链表是一种链式存储结构，由若干个节点构成。每个节点由数据域和指针域组成，指针域指向下一个节点。单链表有一个头节点，头节点不存储实际的数据，其指针域指向第一个有效节点。

插入操作

单链表插入操作是在链表中任选一个节点的前面或后面，插入一个新节点。插入新节点大致分为以下几个步骤：

1. 创建一个新节点；
2. 找到要插入的位置，记录该位置节点和其前驱节点；
3. 将新节点的指针指向位置节点，前驱节点的指针指向新节点。

下面是单链表插入操作的实现：

void insert_node(pNode head, int pos, int data) {
    pNode new_node, cur_node;
    int count = 0;

    new_node = (pNode)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;

    cur_node = head;
    while (cur_node && count < pos - 1) {
        cur_node = cur_node->next;
        ++count;
    }

    if (!cur_node || count > pos - 1) {
        printf("插入位置无效！\n");
        free(new_node);
        return;
    }

    new_node->next = cur_node->next;
    cur_node->next = new_node;
}

从代码中可以看出，我们首先创建一个新节点，并将其数据域设为要插入的数据，将指针域设为NULL。然后，从头节点开始遍历，找到要插入的位置位置节点和其前驱节点。当遍历到位置节点时，将新节点的指针指向位置节点，位置节点的前驱节点的指针指向新节点即可。

下面是一条插入操作的示例：

pNode head = create_list();
if (head == NULL) {
    printf("创建链表失败！\n");
    return -1;
}
printf("插入前：\n");
print_list(head);
insert_node(head, 2, 5);
printf("插入后：\n");
print_list(head);

这条示例代码首先创建一个链表头节点，然后在第二个节点前插入一个值为5的新节点，最后输出插入前后的链表。

删除操作

单链表删除操作是在链表中删除指定位置的节点。删除节点大致分为以下几个步骤：

1. 找到要删除的位置，记录该位置节点和其前驱节点；
2. 将前驱节点的指针指向位置节点的下一个节点；
3. 释放要删除的节点。

下面是单链表删除操作的实现：

void delete_node(pNode head, int pos) {
    pNode del_node, cur_node;
    int count = 0;

    cur_node = head;
    while (cur_node->next && count < pos - 1) {
        cur_node = cur_node->next;
        ++count;
    }

    if (!cur_node->next || count > pos - 1) {
        printf("删除位置无效！\n");
        return;
    }

    del_node = cur_node->next;
    cur_node->next = del_node->next;
    free(del_node);
}

从代码中可以看出，我们首先遍历链表，找到要删除的位置位置节点和其前驱节点。然后，将前驱节点的指针指向位置节点的下一个节点，即可删除位置节点。最后，释放要删除的节点。

下面是一条删除操作的示例：

pNode head = create_list();
if (head == NULL) {
    printf("创建链表失败！\n");
    return -1;
}
printf("删除前：\n");
print_list(head);
delete_node(head, 2);
printf("删除后：\n");
print_list(head);

这条示例代码首先创建一个链表头节点，然后删除第三个节点，最后输出删除前后的链表。

查找操作

单链表查找操作是在链表中查找指定位置的节点。查找节点大致分为以下几个步骤：

1. 遍历链表，找到指定位置的节点。

下面是单链表查找操作的实现：

pNode get_node(pNode head, int pos) {
    pNode cur_node = head;
    int count = 0;

    while (cur_node && count < pos) {
        cur_node = cur_node->next;
        ++count;
    }

    if (!cur_node || count > pos) {
        printf("查找位置无效！\n");
        return NULL;
    }

    return cur_node;
}

从代码中可以看出，我们首先从头节点开始遍历，找到指定位置的节点。查找结束后，如果找到了该节点，就返回该节点的指针；否则，输出错误信息并返回NULL。

下面是一条查找操作的示例：

pNode head = create_list();
if (head == NULL) {
    printf("创建链表失败！\n");
    return -1;
}
pNode p = get_node(head, 2);
if (p != NULL) {
    printf("查找成功，第二个节点的值为%d。\n", p->data);
} else {
    printf("查找失败！\n");
}

这条示例代码首先创建一个链表头节点，然后查找第三个节点，并输出该节点的值。

好了，以上就是关于单链表插入、删除和查找操作的详细讲解。