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

Spreng 发布于 2024-12-24 最后更新于 13 天前 146 次阅读

摘要

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

有序插入

图解：

  1. target的值为2
  2. 先找到合适的节点，此时prev=1，current=3
  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 ->

下面一张图是实现：

  1. prev = prev->next = current->next; 这行代码既完成了next1的赋值，又完成了P对第三个节点的标记。
  2. current->next = prev->next; 完成了next2的赋值。
  3. 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
  1. 摘要
  2. 有序插入
  3. 逆转
  4. 冒泡排序
  5. 插入排序
  6. 完整代码