C语言单向链表入门：结构与插入操作详解

为什么选择链表

在处理大量数据时，数组是最常见的存储方式，但其局限性明显：一旦定义容量，扩展困难。以已排序数组 [2, 3, 5, 8, 9, 10] 为例，若需插入元素 6，系统必须将 8 及其后的所有元素向后移动一位，时间复杂度为 O(n)。

相比之下，链表由离散的节点组成，每个节点包含数据域和指向下一节点的指针。插入 6 仅需修改相邻节点的指针指向，无需移动数据，从而显著提升效率。

动态内存与节点结构

实现链表的核心在于动态内存申请与指针管理。C语言中使用 malloc 函数在运行时按需分配空间，其返回值类型为 void*，使用前需强制转换为目标指针类型。

#include <stdlib.h>
// 强制转换为特定结构体指针类型

链表的基本单元称为“节点”，通常使用 struct 定义，包含两部分：

• 数据域：存储实际数值（如 int date）。
• 后继指针：存储下一个节点的内存地址（如 struct node* next）。

struct node {
    int date;
    struct node* next;
};

由于当前节点的 next 指向的是同类型的下一个节点，因此指针类型必须定义为 struct node* 以保持类型一致性。

构建单向链表

构建过程涉及初始化头指针、逐个创建节点并链接。以下是标准操作流程：

第1步：初始化头指针

链表建立初期为空，头指针 head 应初始化为 NULL，表示尚未指向任何有效节点。

struct node* head = NULL;

第2步：创建首个节点并链接

当插入第一个节点时，需要动态申请内存，赋值后直接将 head 指向该节点。

struct node* p = (struct node*)malloc(sizeof(struct node));
p->date = value;
p->next = NULL;
if (head == NULL) {
    head = p; // 首个节点作为头

第3步：追加后续节点

对于第二个及以后的节点，需维护一个尾指针 q 始终指向当前最后一个节点。将新节点 p 挂接到 q->next，随后更新 q 指向 p。

} else {
    q->next = p; // 旧尾部指向新节点
}
q = p; // 尾指针更新为新节点

第4步：完整构建代码

结合循环输入，可一次性构建包含 N 个节点的链表，并遍历输出验证结果。

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

struct node {
    int date;
    struct node* next;
};

int main() {
    struct node* head, *p, *q = NULL, *t;
    int i, n, a;
    
    scanf("%d", &n);
    head = NULL;
    
    for (i = 1; i <= n; i++) {
        scanf("%d", &a);
        p = (struct node*)malloc(sizeof(struct node));
        p->date = a;
        p->next = NULL;
        
        if (head == NULL)
            head = p;
        else
            q->next = p;
        
        q = p;
    }

    // 遍历输出
    t = head;
    while (t != NULL) {
        printf("%d  ", t->date);
        t = t->next;
    }
}

实现有序插入操作

在已排序链表中插入新值 a，需找到合适的插入位置（即前一个节点的值小于等于 a，且下一个节点值大于 a），调整指针指向。

操作逻辑：

1. 定义临时指针 t 从头节点开始遍历。
2. 判断终止条件：t->next 为空（到达末尾）或 t->next->date > a（发现比待插入值大的节点）。
3. 执行插入：

// 申请新节点
p = (struct node*)malloc(sizeof(struct node));
p->date = a;

// 关键指针重定向
p->next = t->next;  // 新节点指向原后继
t->next = p;        // 当前节点指向新节点

完整实现代码

以下代码整合了链表构建与有序插入功能，可直接编译运行测试。

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

struct node {
    int date;
    struct node* next;
};

int main() {
    struct node* head, *p, *q = NULL, *t;
    int i, n, a;
    
    scanf("%d", &n);
    head = NULL;
    for (i = 1; i <= n; i++) {
        scanf("%d", &a);
        p = (struct node*)malloc(sizeof(struct node));
        p->date = a;
        p->next = NULL;
        if (head == NULL) head = p;
        else q->next = p;
        q = p;
    }

    // 读取待插入值
    scanf("%d", &a); 
    t = head;
    
    // 寻找插入点并插入
    while (t != NULL) {
        if (t->next == NULL || t->next->date > a) {
            p = (struct node*)malloc(sizeof(struct node));
            p->date = a;
            p->next = t->next;
            t->next = p;
            break;
        }
        t = t->next;
    }

    // 输出最终结果
    t = head;
    while (t != NULL) {
        printf("%d  ", t->date);
        t = t->next;
    }
}

以上就是C语言数据结构与算法之链表(一)的详细内容，更多关于C语言数据结构 链表的资料请关注本站其它相关文章！