C语言如何建立动态链表：原理与代码实现

核心原理与准备工作

所谓建立动态链表，是指在程序执行过程中，根据需要逐个申请内存空间（开辟结点），输入各结点数据，并通过指针建立起前后相连的关系。相比数组，动态链表不需要预先定义固定大小，能够根据实际运行时的输入量灵活调整存储空间，有效避免了空间浪费或溢出问题。

准备条件：自引用结构体

链表的核心在于节点。一个标准的链表节点通常由两部分组成：数据域（存放实际数据）和指针域（存放下一个节点的地址）。

在C语言中，这需要通过“自引用结构体”来实现，即结构体中的成员指针指向的是与结构体本身相同的类型：

struct Student {
    long num;             // 数据域：学号
    float score;          // 数据域：分数
    struct Student *next; // 指针域：指向下一个节点
};

第一步：建立动态链表（输入与连接）

这是文章的核心操作步骤。我们需要创建一个函数来持续接收用户输入，直到满足结束条件（如输入特定值）为止。

第1步：初始化与首次内存分配

首先定义头指针 `head` 和两个辅助工作指针 `p1`、`p2`。

• `head`：始终指向链表的第一个节点（入口）。
• `p1`：用于接收新申请的节点，负责读入数据。
• `p2`：用于指向上一次循环结束时的最后一个节点，负责连接新节点。

第2步：循环读取与链接

进入 while 循环，只要输入的学号不为0，就持续执行以下动作：

1. 申请内存：使用 malloc(sizeof(struct Student)) 为当前输入申请一块堆内存。
2. 录入数据：将用户输入的值填入 p1->num 等字段。
3. 判断是否为第一个节点：
   • 如果是（n == 1），则让 head = p1，确立链表头。
   • 如果不是，则执行 p2->next = p1，将上一个节点的指针指向当前新节点，完成串联。
4. 后移指针：将 p2 移动到 p1 的位置（p2 = p1），为下一次连接做准备。

第3步：收尾工作

当循环结束时（输入0退出），必须对最后的节点进行处理：p2->next = NULL。这一步至关重要，它标志着链表的结束，防止遍历时出现野指针。

#include <stdio.h>
#include <stdlib.h> // 修正了原稿 stdib.h 的错误

#define LEN sizeof(struct Student)

struct Student {
    long num;
    float score;
    struct Student * next;
};

int n; // 记录节点数量

struct Student * creat(void) {
    struct Student * head;
    struct Student * p1, *p2;
    
    n = 0;
    
    // 初始申请一个节点空间
    p1 = (struct Student *)malloc(LEN);
    scanf("%ld,%f", &p1->num, &p1->score);
    
    head = NULL;
    
    while(p1->num != 0) {
        n = n + 1;
        if(n == 1)
            head = p1;      // 设置头指针
        else
            p2->next = p1;  // 连接前一个节点
        
        p2 = p1;                    // p2跟进
        p1 = (struct Student *)malloc(LEN); // 再开一个新节点
        scanf("%ld,%f", &p1->num, &p1->score); // 注意补全了原稿缺失的scanf格式符
    }
    
    p2->next = NULL; // 结尾标记
    return(head);
}

静态链表与动态链表的区别

为了更深入理解动态链表，有必要将其与静态链表进行对比。两者都是线性表链式存储的不同表现形式，但在物理结构和灵活性上有显著差异。

1. 静态链表（Static Linked List）

静态链表虽然名为“链表”，但其底层通常是基于数组实现的顺序存储结构。

• 特点：物理地址连续，长度在定义时已固定。
• 优势：插入和删除操作时，只需修改指针（索引），无需移动大量元素，效率高于顺序表。
• 局限：无法改变总长度，存在预先分配不足或浪费的问题。

以下是静态链表的标准实现参考：

#include <stdio.h>

/* 静态链表 */
struct node {
    int num;
    struct node *next; // 这里的指针指向的是数组内的另一个元素的地址
};

int main() {
    struct node stu[3]; // 预定义的连续内存块
    struct node *head, *p;

    stu[0].num = 10;
    stu[1].num = 20;
    stu[2].num = 30;

    head = &stu[0];
    stu[0].next = &stu[1];
    stu[1].next = &stu[2];
    stu[2].next = NULL;

    // 遍历
    p = head;
    do {
        printf("%d\n", p->num);
        p = p->next;
    } while (p != NULL);

    return 0;
}

2. 动态链表（Dynamic Linked List）

动态链表是使用内存申请函数（如 malloc）在运行时动态申请内存。

• 特点：物理地址不一定连续，长度无限制，可随需增减。
• 风险：每个节点没有固定的名字（变量名），只能靠指针维系关系。如果某个节点的指针意外“断开”，后续节点将无法访问且可能造成内存泄漏。

总结

掌握动态链表的建立关键在于理解 `malloc` 的使用时机以及 `p1`、`p2`、`head` 三个指针的角色分工：`p1` 负责新数据的接收，`p2` 负责旧关系的保持，`head` 负责全局入口。在实际工程中，务必记得在程序退出前释放所有动态分配的内存（Free），以保持良好的编程习惯。 以上就是C语言如何建立动态链表的详细内容，更多关于C语言数据结构学习的资料请关注本站其它相关文章！