【C语言】单链表

单链表

单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的.

每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)

• 元素就是存储数据的存储单元
• 指针就是连接每个结点的地址数据。

以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。

单链表插入数据

在链表头部插入

以下代码有BUG，不能用于实际场景，只是例子这样写，没有释放空间

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

// 定义一个结构体
struct Info {
    char name[255];
    struct Info *next; // 指向下一个 Info 结构体
};

// 申请链表节点
struct Info *applyNode() {
    struct Info *node;
    node = (struct Info *) malloc(sizeof(struct Info));
    if (node == NULL)exit(0); // 空间申请失败
    return node;
}

// 输出单链表的值
void printInfo(struct Info *head){
    // 传入的链表头部，通过头部链表找后面的链表
    struct Info *info;
    info = head->next;
    while(info != NULL){
        printf("%s ",info->name);
        info = info->next;
    };
    printf("\n");
}

int main(void) {
    // 申请一个空间 创建链表的头部
    struct Info *head;
    head = applyNode();
    head->next = NULL; // 初始化头部链表

    char name[255];
    while(1){
        // 申请新的节点
        struct Info *node = applyNode();

        // 用户输入
        printf("输入姓名（n 退出）：");
        scanf("%s",node->name);
        if (*(node->name) == 'n')exit(0); // n 退出

        // 改变指针 指向地址
        node->next = head->next;
        head->next = node;

        // 输出单链表的值
        printInfo(head);
    }

    return 0;
}

在链表尾部插入

以下代码有BUG，不能用于实际场景，只是例子这样写，没有释放空间

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

// 定义一个结构体
struct Info {
    char name[255];
    struct Info *next; // 指向下一个 Info 结构体
};

// 申请链表节点
struct Info *applyNode() {
    struct Info *node;
    node = (struct Info *) malloc(sizeof(struct Info));
    if (node == NULL)exit(0); // 空间申请失败
    return node;
}

// 输出单链表的值
void printInfo(struct Info *head){
    // 传入的链表头部，通过头部链表找后面的链表
    struct Info *info;
    info = head->next;
    while(info != NULL){
        printf("%s ",info->name);
        info = info->next;
    };
    printf("\n");
}

int main(void) {
    // 申请一个空间 创建链表的头部 保存链表头部地址
    struct Info *head;
    head = applyNode();
    head->next = NULL; // 初始化头部链表

    struct Info *tail = head; // 一直表示链表尾部，第一次就是 链表头部

    char name[255];
    while(1){
        struct Info *node = applyNode();
        // 用户输入
        printf("输入姓名（n 退出）：");
        scanf("%s",node->name);
        if (*(node->name) == 'n')exit(0); // n 退出

        // 改变指针 指向地址
        tail->next = node;
        tail = node;
        tail->next = NULL;

        // 输出单链表的值
        printInfo(head);

    }

    return 0;
}

综合应用-在单链表中间插入链（完整代码）

新输入的值，自动插入到适合大小位置

相应函数

// 数组结构体
struct IntList {
    int num;
    struct IntList *next;
};

struct IntList *applyNode(); // 新节点申请空间
void addNum(struct IntList *head, struct IntList *node);  // 插入值
void printIntList(struct IntList *head); // 输出单链表的内容
void clearNode(struct IntList *head); // 释放空间

完整代码

代码的难点: 在于需要兼顾第一次、在头部、中间、尾部 这些不同位置的插入。

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

// 数组结构体
struct IntList {
    int num;
    struct IntList *next;
};

struct IntList *applyNode(); // 新节点申请空间
void addNum(struct IntList *head, struct IntList *node);  // 插入值
void printIntList(struct IntList *head); // 输出单链表的内容
void clearNode(struct IntList *head); // 释放空间

// 申请空间
struct IntList *applyNode() {
    struct IntList *node;
    node = (struct IntList *) malloc(sizeof(struct IntList));
    node->next = NULL;
    return node;
}

// 插入值
void addNum(struct IntList *head, struct IntList *node) {
    struct IntList *lastNode; // 插入节点的前一个
    struct IntList *now; // 当前节点
    struct IntList *nextNode; // 插入节点的前一个

    now = head->next;

    // 第一次插入，直接加在头部后面
    if (now == NULL) {
        head->next = node;
        return;
    }

    // 处理最小值，直接再头部插入
    if (node->num <= now->num) {
        node->next = now;
        head->next = node;
        return;
    }

    // 插入在中间的链
    while (now != NULL) {
        lastNode = now;
        nextNode = now->next;

        // 遍历到最后，认为是最大值，插入在尾部
        if (nextNode == NULL) {
            now->next = node;
            return;
        }

        // 比前一个大，比后一个小，然后中间插入
        if (lastNode->num <= node->num && node->num <= nextNode->num) {
            lastNode->next = node;
            node->next = nextNode;
            return; // 插入完成 退出函数
        }
        now = nextNode;
    }
};

// 输出单链表值
void printIntList(struct IntList *head) {
    struct IntList *node;
    node = head->next;
    while (node != NULL) {
        printf("%d ", node->num);
        node = node->next;
    }
    printf("\n");
};

// 清理空间
void clearNode(struct IntList *head) {
    struct IntList *node;
    // 循环清理所有空间
    while (head != NULL) {
        node = head->next;  // 记录下一个 node 地址
        free(head);         // 清理 head
        head = node;        // node 变成新的 head
    }
    printf("空间清理完成 ！！！");
};

int main() {
    struct IntList *head = applyNode(); // 申请链表头部

    int num = 0;
    while (1) {
        printf("输入一个数字(-1 退出并清理空间)：");
        scanf("%d", &num);
        if (num == -1) {
            // 清理空间 并退出
            clearNode(head);
            exit(0);
        }

        // 申请节点空间
        struct IntList *node = applyNode();
        node->num = num;
        // 把值插入链表
        addNum(head, node);
        // 输出链表的内容
        printIntList(head);
    }