C语言实现带头结点的链表的创建、查找、插入、删除操作

C语言实现带头结点的链表的创建、查找、插入、删除操作攻略

一、链表基本概念

链表是一种动态的数据结构，它可以在运行时动态地分配内存，支持数据的插入、删除等操作。链表（Linked List）由多个节点（Node）组成，每个节点包含两部分，一个是数据部分（Data），另一个是指向下一个节点的指针（Next）。

二、带头结点的链表

带头结点的链表是一种特殊的链表，它的头结点不存储任何数据，只是一个哨兵节点，可以简化链表的操作。在插入和删除节点时，只需要调整相邻节点的指针，不需要特判第一个节点和最后一个节点。

三、创建链表

创建链表需要分配内存空间，为每个节点赋值并建立节点之间的关系。对于带头结点的链表，在创建时需要先创建一个头结点，并将其指针域设为空。

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

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

LinkedList createList() {
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

四、查找节点

在链表中查找一个节点，需要从链表的头结点开始，依次访问各个节点，直到找到目标节点或者链表末尾。如果找到节点，则返回节点指针，否则返回NULL。

Node *findNode(LinkedList list, int x) {
    Node *p = list->next;
    while (p != NULL && p->data != x) {
        p = p->next;
    }
    return p;
}

五、插入节点

在链表中插入一个节点，需要先查找节点的插入位置，然后在该位置的前一个节点后面插入新节点，最后建立新节点与后面节点的关系。

void insertNode(LinkedList list, int x) {
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = NULL;

    Node *prev = list;
    Node *cur = list->next;
    while (cur != NULL && cur->data < x) {
        prev = cur;
        cur = cur->next;
    }
    p->next = prev->next;
    prev->next = p;
}

例如，现在有一个升序的链表1->3->5->7，需要在其中插入数值为4的节点，插入后的链表为1->3->4->5->7。

LinkedList list = createList();
insertNode(list, 1);
insertNode(list, 3);
insertNode(list, 5);
insertNode(list, 7);
insertNode(list, 4);
// 遍历链表
Node *p = list->next;
while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
}

六、删除节点

在链表中删除一个节点，需要先查找节点的位置，然后从链表中摘除该节点，并将其内存空间释放。

void deleteNode(LinkedList list, int x) {
    Node *prev = list;
    Node *cur = list->next;
    while (cur != NULL && cur->data != x) {
        prev = cur;
        cur = cur->next;
    }
    if (cur != NULL) {
        prev->next = cur->next;
        free(cur);
    }
}

例如，现在有一个升序的链表1->3->5->7，需要删除数值为5的节点，删除后的链表为1->3->7。

LinkedList list = createList();
insertNode(list, 1);
insertNode(list, 3);
insertNode(list, 5);
insertNode(list, 7);
deleteNode(list, 5);
// 遍历链表
Node *p = list->next;
while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
}

七、总结

带头结点的链表是一种常用的数据结构，能够动态地分配内存空间，支持插入和删除等操作。在进行操作时，需要考虑到头结点等特殊情况，并利用指针建立节点之间的联系，从而完成链表的创建、查找、插入、删除等操作。