【C语言】实现单链表及相关操作

摘要

本文介绍了C语言如何用结构体来实现单链表，以及单链表的基础操作。简洁起见，比较简单的操作都放在最后的完整代码里（说明在注释里），不再赘述。

有序插入

图解：

target的值为2
先找到合适的节点，此时prev=1，current=3
再改变next的值，将节点2指向3，节点1指向2。

IMG_20250228_193938

Node *orderInsert(Node *head, Node *target)
{
    Node *current = head;
    Node *prev = NULL;
    target->next = NULL; // 清空target的值，防止闭环、混入杂链等情况
    // head为空值的情况
    if (head == NULL)
        return target;

    while (current != NULL)
    {
        // 比较要插入的单位，若比当前节点大则继续寻找，直到找到比目标大的节点
        if (target->data <= current->data)
        {
            target->next = current;
            // target应放在头部的情况
            if (prev == NULL)
                head = target;
            else
                prev->next = target;
            return head;
        }
        prev = current;
        current = current->next;
    }
    prev->next = target;
    target->next = NULL;
    return head;
}

逆转

请注意，完成这个操作必须用至少3个临时变量，因为改变节点方向需要"瞻前"，进入下一个状态要"顾后"。

这里的next在循环的最开始赋值是取巧的，如果你把这行放在 current = next 的后面，current为NULL时执行 next = current->next 的会出错，需要另外增加一条if判断current是否为NULL。

Node *reverse(Node *head)
{
    Node *prev = NULL;
    Node *current = head;
    Node *next = NULL;

    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

冒泡排序

这里不再赘述冒泡排序的原理，只专注于冒泡排序交换的过程。

提醒一点：在交换时不要通过交换data来交换，这么做虽然能运行、代码看上去也更简洁，但从算法上来讲开销较大，抹除了链表本身的优势，在data较大的情况下尤为显著。

这一部分比较复杂，希望下面的文字和三张图可以讲清楚我的思路。

链表的交换涉及到了4个节点和用来操作他们的两个指针P和C，我们看看一个循环要做什么，显然将2和3交换了。那P和C呢，你会发现P标记到了原来顺序的第三个节点（即2），而C标记的还是3！

初始状态：
   P    C
-> 1 -> 3 -> 2 -> 4 ->
末状态：
        P    C
-> 1 -> 2 -> 3 -> 4 ->

下面一张图是实现：

prev = prev->next = current->next; 这行代码既完成了next1的赋值，又完成了P对第三个节点的标记。
current->next = prev->next; 完成了next2的赋值。
prev->next = current; 完成了next3的赋值。

至此3个next的赋值，和P对第三个点的标记的操作就完成了。

mdEpcgJak75X9xQ

下图是对特殊情况（第一次循环）的补充，只有第一个操作有差别，就是把Header更新到第二个节点和P的标记。

ZsCKejXlOt4TYEv

Node *boubleSort(Node *head)
{
    Node *prev = NULL;
    Node *current = head;
    Node *next = current->next;
    int flag = 1; // 检测当前轮数是否发生交换，若未发生说明排序成功。

    while (flag)
    {
        flag = 0;
        while (current->next != NULL)
        {
            if (current->data > current->next->data)
            {
                flag = 1;
                if (prev == NULL)
                    prev = head = current->next;
                else
                    prev = prev->next = current->next;
                current->next = prev->next;
                prev->next = current;
            }
            else{
                prev = current;
                current = current->next;
            }
        }
        prev = NULL;
        current = head;
    }
    return head;
}

插入排序

插入排序很好理解，和打扑克牌时的理牌过程相同，取一个节点插入合适的位置即可。插入排序非常契合链表的特点，插入对于链表来说开销非常小。

这个算法需要前面的有序插入，如果有序插入已经实现了，那插入排序将非常简单。

Node *insertSort(Node *head)
{
    Node *current = head;
    Node *next = current->next;
    head = NULL;
    int value;
    while (current != NULL)
    {
        next = current->next;
        // print(head);
        head = orderInsert(head, current);
        current = next;
    }
    return head;
}

图解：

AgLeCTVl8okR4UO

完整代码

#include 
#include 

// 定义节点
typedef struct Node
{
    int data;
    struct Node *next;
} Node;

// 创建链表
Node *create()
{
    Node *head = NULL, *tail;
    int value;
    head = tail = NULL;
    // 表示scanf正确接受了一个变量，因此输入非数字时，scanf会停止读取。
    while (scanf("%d", &value) == 1)
    {
        if (tail == NULL)
            head = tail = (Node *)malloc(sizeof(Node));
        else
            tail = tail->next = (Node *)malloc(sizeof(Node));
        tail->data = value;
        tail->next = NULL;
    }
    return head;
}

// 输出链表
void print(Node *head)
{
    Node *current = head;
    while (current != NULL)
    {
        printf("%d", current->data);
        current = current->next;
        if (current == NULL)
            printf("\n");
        else
            printf(" -> ");
    }
}

// 释放
void release(Node *head)
{
    Node *current = head;
    Node *next = NULL;
    while (current != NULL)
    {
        next = current->next;
        free(current);
        current = next;
    }
}

// 尾插
void append(Node *head, int value)
{
    Node *tail = head;
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = (Node *)malloc(sizeof(Node));
    tail->next->data = value;
    tail->next->next = NULL;
}

// 定位插入
void insert(Node *head, int value, int pos)
{
    Node *current = head;
    Node *prev = NULL;
    while (pos-- && current != NULL)
    {
        prev = current;
        current = current->next;
    }
    prev->next = (Node *)malloc(sizeof(Node));
    prev->next->data = value;
    prev->next->next = current;
}

// 删除
void delete(Node *head, int pos)
{
    Node *prev = NULL;
    Node *current = head;
    while (current->next != NULL && pos--)
    {
        prev = current;
        current = current->next;
    }
    prev->next = current->next;
    free(current);
}

Node *reverse(Node *head)
{
    Node *prev = NULL;
    Node *current = head;
    Node *next = NULL;

    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Node *boubleSort(Node *head)
{
    Node *prev = NULL;
    Node *current = head;
    Node *next = current->next;
    int flag = 1;

    while (flag)
    {
        flag = 0;
        while (next != NULL)
        {
            if (current->data > next->data)
            {
                flag = 1;
                if (prev == NULL)
                    head = next;
                else
                    prev->next = next;
                current->next = next->next;
                next->next = current;
            }
            prev = current;
            current = next;
            next = current->next;
        }
        prev = NULL;
        current = head;
        next = current->next;
    }
    return head;
}

Node *orderInsert(Node *head, Node *target)
{
    Node *current = head;
    Node *prev = NULL;
    target->next = NULL;

    if (head == NULL)
        return target;

    while (current != NULL)
    {
        if (target->data <= current->data)
        {
            target->next = current;
            if (prev == NULL)
                head = target;
            else
                prev->next = target;
            return head;
        }
        prev = current;
        current = current->next;
    }
    prev->next = target;
    target->next = NULL;
    return head;
}

Node *insertSort(Node *head)
{
    Node *current = head;
    Node *next = current->next;
    head = NULL;
    int value;
    while (current != NULL)
    {
        next = current->next;
        // print(head);
        head = orderInsert(head, current);
        current = next;
    }
    return head;
}

int main()
{
    Node *head = create();

    printf("Original List: ");
    print(head);

    append(head, 2);
    printf("List after appending: ");
    print(head);

    insert(head, 7, 7);
    printf("List after inserting: ");
    print(head);

    delete (head, 2);
    printf("List after deleting: ");
    print(head);

    head = reverse(head);
    printf("Reversed List: ");
    print(head);

    head = insertSort(head);
    printf("Insert sorted List: ");
    print(head);

    head = boubleSort(head);
    printf("Bouble sorted List: ");
    print(head);

    release(head);

    return 0;
}

回显：

112 34 214 211 232 32 #
Original List: 112 -> 34 -> 214 -> 211 -> 232 -> 32
List after appending: 112 -> 34 -> 214 -> 211 -> 232 -> 32 -> 2
List after inserting: 112 -> 34 -> 214 -> 211 -> 232 -> 32 -> 7 -> 2
List after deleting: 112 -> 34 -> 211 -> 232 -> 32 -> 7 -> 2
Reversed List: 2 -> 7 -> 32 -> 232 -> 211 -> 34 -> 112
Insert sorted List: 2 -> 7 -> 32 -> 34 -> 112 -> 211 -> 232
Bouble sorted List: 2 -> 7 -> 32 -> 34 -> 112 -> 211 -> 232

【C语言】实现单链表及相关操作

摘要

有序插入

逆转

冒泡排序

插入排序

完整代码

SageMath 9.3&10.4 安装指南

0xGame2024 WriteUp

Comments NOTHING

取消回复