C语言中单链表的基本操作(创建、销毁、增删查改等)

下面我将为你详细讲解C语言中单链表的基本操作，包括创建、销毁、增删查改等。

单链表的基本结构

单链表是一种常见的数据结构，它由多个节点组成，每个节点都包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。

在C语言中，我们可以通过定义一个结构体来表示一个节点，结构体中包含数据域和指针域两个成员变量，如下所示：

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

创建单链表

创建单链表的基本思路是从头节点开始，依次添加新节点。在C语言中，我们可以通过动态分配内存的方式来创建新节点。

具体步骤如下：

1. 创建头节点，并将其next指针初始化为NULL；
2. 依次读入数据，创建新节点，并将其插入到链表中。

下面是示例代码：

Node* createList() {
    Node *head = (Node*) malloc(sizeof(Node));   // 创建头节点
    head->next = NULL;   // 初始化头节点指针为空

    int data;
    Node *tail = head;   // 只有一个节点时，头节点和尾节点都指向它

    while (scanf("%d", &data) != EOF) { // 依次读入数据，插入到链表中
        Node *node = (Node*) malloc(sizeof(Node));
        node->data = data;
        node->next = NULL;

        tail->next = node;
        tail = node;   // 将尾指针指向新节点
    }

    return head;
}

销毁单链表

销毁单链表的基本思路是从头节点开始，依次释放每个节点的内存。具体步骤如下：

1. 依次遍历节点，释放每个节点的内存；
2. 将头节点的指针设为NULL，避免野指针。

下面是示例代码：

void destoryList(Node *head) {
    Node *p = head;

    while (p != NULL) {
        Node *q = p->next;
        free(p);
        p = q;
    }

    head = NULL;
}

增加节点

增加节点的基本思路是先找到所要插入的位置，然后将新节点插入到该位置。具体步骤如下：

1. 找到插入位置的前一个节点；
2. 创建新节点，并将其next指针指向插入位置的后一个节点；
3. 将插入位置的前一个节点的next指针指向新节点。

下面是示例代码（在第k个节点后插入新节点）：

void insertNode(Node *head, int k, int data) {
    Node *p = head;
    int i = 0;

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

    if (p == NULL) { // 如果k大于链表长度，直接返回
        return;
    }

    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = p->next;
    p->next = node;
}

删除节点

删除节点的基本思路是先找到要删除的节点，然后将其前一个节点的next指针指向要删除节点的后一个节点，最后释放要删除节点的内存。具体步骤如下：

1. 找到要删除节点的前一个节点；
2. 将其next指针指向要删除节点的后一个节点；
3. 释放要删除节点的内存。

下面是示例代码（删除第k个节点）：

void deleteNode(Node *head, int k) {
    Node *p = head;
    int i = 0;

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

    if (p == NULL || p->next == NULL) { // 如果k大于链表长度，直接返回
        return;
    }

    Node *q = p->next;
    p->next = q->next;
    free(q);
}

查找节点

查找节点的基本思路是从头节点开始遍历链表，依次比较每个节点的数据域，直到找到所要查找的节点或遍历完整个链表。具体步骤如下：

1. 从头节点开始遍历链表，依次比较每个节点的数据域；
2. 如果找到所要查找的节点，返回该节点的指针；
3. 如果遍历完整个链表，仍未找到所要查找的节点，返回NULL。

下面是示例代码（查找链表中第一个数据为x的节点）：

Node* findNode(Node *head, int x) {
    Node *p = head->next;

    while (p != NULL) {
        if (p->data == x) {
            return p;
        }
        p = p->next;
    }

    return NULL;
}

更改节点

更改节点的基本思路是先找到所要更改的节点，然后修改其数据域。具体步骤如下：

1. 找到要更改的节点；
2. 修改其数据域。

下面是示例代码（将链表中第k个节点的数据域改为x）：

void changeNode(Node *head, int k, int x) {
    Node *p = head->next;
    int i = 1;

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

    if (p == NULL) { // 如果k大于链表长度，直接返回
        return;
    }

    p->data = x;
}