C语言链表详解及代码分析

简介

链表是一种常见的数据结构，它主要用于存储线性数据结构，可以动态地进行添加和删除操作。在C语言中，链表可以通过链式存储结构来实现。本篇攻略将详细讲解C语言链表的实现，包括定义链表、节点、添加节点、删除节点等操作。

链表的定义

链表由一个个节点组成，每个节点包含两个信息：数据和指向下一个节点的指针。在C语言中，可以通过结构体实现每个节点的定义。

struct Node {
    int data;           // 存储节点数据
    struct Node *next;  // 存储指向下一个节点的指针
};

这里定义了一个名为Node的结构体，包含了一个用于存储节点数据的整型变量data和一个用于存储指向下一个节点的指针的结构体类型Node*。其中，Node*是指向该类型结构体的指针类型，因此可以指向该类型的某个节点。

添加节点

链表的添加操作主要有两个：在链表头部添加新节点和在链表尾部添加新节点。以下代码分别实现这两个操作：

在链表头部添加新节点：

struct Node* addNodeAtHead(struct Node* head, int data) {
    // 创建新节点
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    // 把原先的头节点作为新节点的next指针
    newNode->next = head;
    // 把新节点设置为新的头节点
    head = newNode;
    return head;
}

在链表尾部添加新节点：

struct Node* addNodeAtTail(struct Node* head, int data) {
    // 创建新节点
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    // 如果链表为空，把新节点作为头节点
    if (head == NULL) {
        head = newNode;
        return head;
    }
    // 找到链表尾部
    struct Node* curNode = head;
    while (curNode->next != NULL) {
        curNode = curNode->next;
    }
    // 把新节点作为链表的最后一个节点
    curNode->next = newNode;
    return head;
}

两个函数都接收一个Node*类型的参数表示链表头节点，返回一个指向头节点的指针。其中，使用了动态内存分配函数malloc来分配一个新节点，并将节点的两个信息进行初始化。

删除节点

链表的删除操作通常通过找到要删除的节点，然后将其上一个节点的next指针指向其下一个节点，进而将其从链表中移除。以下是找到对应节点并删除的代码：

struct Node* deleteNode(struct Node* head, int data) {
    struct Node* curNode = head;
    struct Node* prevNode = NULL;
    // 找到节点
    while (curNode != NULL && curNode->data != data) {
        prevNode = curNode;
        curNode = curNode->next;
    }
    // 如果链表中不存在要删除的节点
    if (curNode == NULL) {
        return head;
    }
    // 如果要删除的节点是头节点
    if (curNode == head) {
        head = head->next;
    } else {
        prevNode->next = curNode->next;
    }
    free(curNode);
    return head;
}

函数接收一个指向头节点的指针和一个要删除的节点的数据，返回一个指向头节点的指针。在找到要删除的节点后，需要保存其上一个节点的指针，否则无法将其从链表中删除。如果要删除的节点是头节点，则需要特殊处理。

示例说明

以下是一个使用链表实现求平均数的示例。

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

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

double getAverage(struct Node* head) {
    int sum = 0;
    int count = 0;
    struct Node* curNode = head;
    while (curNode != NULL) {
        sum += curNode->data;
        count++;
        curNode = curNode->next;
    }
    return (double)sum / (double)count;
}

int main() {
    int arr[] = { 1,2,3,4,5 };
    int len = sizeof(arr) / sizeof(int);

    struct Node* head = NULL;

    for (int i = 0; i < len; i++) {
        head = addNodeAtTail(head, arr[i]);
    }

    double avg = getAverage(head);
    printf("平均数为：%.2f", avg);

    // 释放链表内存
    struct Node* curNode = head;
    while (curNode != NULL) {
        struct Node* temp = curNode;
        curNode = curNode->next;
        free(temp);
    }

    return 0;
}

该程序首先定义了一个名为Node的结构体，用于表示链表节点。接着定义了一个计算平均数的函数getAverage，该函数接收一个指向头节点的指针并返回一个浮点型平均数。函数中使用了链表遍历的方法来计算总和，并统计链表中元素的个数。

在主函数中，将一组数据存储于数组arr中，并使用addNodeAtTail函数将元素添加到链表中，最后调用getAverage函数计算平均数并输出。程序结束后需要手动释放链表内存。

另一个示例是使用链表来实现红包扫雷游戏的。游戏规则：共有$n$个红包，每个红包的金额是随机生成的，并且保证总金额为$m$元。每轮游戏中，用户需要猜测剩余红包的总金额，如果猜对则获得该金额，并继续下一轮游戏，否则游戏结束。以下是一个使用链表实现游戏的示例。

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

struct Node {
    int money;
    struct Node* next;
};

int getRemainMoney(struct Node* head) {
    int sum = 0;
    struct Node* curNode = head;
    while (curNode != NULL) {
        sum += curNode->money;
        curNode = curNode->next;
    }
    return sum;
}

int main() {
    srand((unsigned int)time(NULL));

    int n = 10;
    int m = 100;

    // 初始化红包
    struct Node* head = NULL;
    struct Node* curNode = NULL;
    for (int i = 0; i < n; i++) {
        int money = rand() % (m - n + 1) + 1;
        curNode = (struct Node*)malloc(sizeof(struct Node));
        curNode->money = money;
        curNode->next = NULL;
        if (head == NULL) {
            head = curNode;
        } else {
            struct Node* tail = head;
            while (tail->next != NULL) {
                tail = tail->next;
            }
            tail->next = curNode;
        }
    }

    // 游戏开始
    int remainMoney = getRemainMoney(head);
    int count = 0;
    int guess;
    printf("红包总金额为：%d元\n", m);
    while (remainMoney > 0) {
        printf("剩余红包总金额为：%d元，请猜测总金额：", remainMoney);
        scanf("%d", &guess);
        if (guess == remainMoney) {
            int money = curNode->money;
            printf("恭喜你，猜对了，红包金额为：%d元\n", money);
            head = head->next;
            free(curNode);
            curNode = head;
            count++;
            remainMoney = getRemainMoney(head);
        } else {
            printf("猜错了，游戏结束。");
            break;
        }
    }
    printf("游戏结束，你猜了%d次。", count);

    // 释放链表内存
    curNode = head;
    while (curNode != NULL) {
        struct Node* temp = curNode;
        curNode = curNode->next;
        free(temp);
    }

    return 0;
}

该程序首先定义了一个名为Node的结构体，用于表示红包。接着使用函数srand随机设置种子，生成每个红包的金额，并将其添加到链表中。在游戏开始后，程序每轮接受用户的猜测并将其与剩余金额进行比较，如果猜对则移除当前红包节点并将游戏次数加1，否则游戏结束。程序结束后需要手动释放链表内存。