C语言单向链表数据结构：原理图解与完整实现代码

单向链表的核心结构与原理

在C语言中，单向链表（Singly Linked List）是一种线性存储结构。与数组不同，链表不需要预先分配连续的内存空间，而是由一系列被称为“节点”的结构体组成。每个节点包含两部分：

1. 数据域（data）：用于存储实际的信息或元素值。
2. 指针域（next）：用于存储指向下一个节点的地址。

链表的访问必须从头结点开始，沿着指针域逐个向后查找，直到遇到最后一个节点，其指针域通常指向空值（NULL），作为链表的结束标志。这种单向遍历的特性使得它在某些固定顺序访问的场景（如邻接表）中具有优势，但在需要频繁逆向查找时效率较低。

为了简化边界处理（如在头部插入或删除节点），工程实践中常采用带头结点的单链表。头结点不存储有效数据，其指针域指向第一个实际存有数据的节点（首元节点）。若链表为空，则头结点的指针域直接为 NULL。

C语言单向链表的完整代码实现

下面我们将分模块解析单链表的定义及关键算法实现。代码基于经典的《数据结构》教材标准，涵盖了内存分配、基本CRUD操作以及两个有序链表的归并算法。

第1步：定义链表节点结构

首先，我们需要定义节点的结构体。这里使用了泛型占位符 ElemType，在实际使用时可替换为 int、float 或其他自定义类型。

/* c2-2.h 线性表的单链表存储结构 */
struct LNode {
    ElemType data;
    struct LNode *next;
};
typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */

第2步：初始化与销毁操作

初始化（InitList）：为链表分配头结点内存，并将其指针域初始化为 NULL。需检查 malloc 是否成功，防止内存溢出导致程序崩溃。

销毁（DestroyList）：从头结点开始，遍历整个链表，逐个释放节点内存，最后将头指针置为 NULL，彻底释放链表占用的资源。

Status InitList(LinkList *L) {
    *L=(LinkList)malloc(sizeof(struct LNode));
    if(!*L) exit(OVERFLOW);
    (*L)->next=NULL;
    return OK;
}

Status DestroyList(LinkList *L) {
    LinkList q;
    while(*L) {
        q=(*L)->next;
        free(*L);
        *L=q;
    }
    return OK;
}

第3步：核心数据操作（插入、删除、查询）

获取元素（GetElem）：通过计数器 j 和指针移动 p=p->next，定位到第 i 个节点，并将数据赋给外部变量 e。

插入元素（ListInsert）：在第 i 个位置之前插入新节点 s。关键在于先找到第 i-1 个节点 p，然后修改指针：s->next = p->next; 然后 p->next = s;。注意顺序不可颠倒，否则会导致后续链表断裂。

删除元素（ListDelete）：同样需定位到第 i-1 个节点 p。记录待删除节点 q，修改指针 p->next = q->next;，保存 q 的数据域供返回值使用，最后 free(q)。

Status ListInsert(LinkList L,int i,ElemType e) {
    int j=0;
    LinkList p=L,s;
    while(p&&jnext;
        j++;
    }
    if(!p||j>i-1) return ERROR;
    s=(LinkList)malloc(sizeof(struct LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

第4步：创建列表与归并算法

正位序/逆位序输入（CreateList/CreateList2）：展示了如何在循环中通过 scanf 读取数据，并使用 malloc 生成新节点插入链表。逆位序插入通常在表头进行，因此生成的链表顺序与输入相反；正位序插入需在表尾追加，逻辑稍复杂。

归并两个有序链表（MergeList）：这是一个经典算法。已知 La 和 Lb 均按非递减排列，利用指针 pa、pb 分别遍历两者，比较当前节点数据大小，将较小的节点接入新链表 pc。由于共用 La 的头结点作为 Lc 的头结点，只需释放 Lb 的额外头结点即可，无需重新分配内存，时间复杂度为 O(m+n)，空间复杂度 O(1)。

void MergeList(LinkList La,LinkList *Lb,LinkList *Lc){
    LinkList pa=La->next,pb=(*Lb)->next,pc;
    *Lc=pc=La; /* 用La的头结点作为Lc的头结点 */
    while(pa&&pb)
        if(pa->data<=pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    pc->next=pa?pa:pb; /* 插入剩余段 */
    free(*Lb); /* 释放Lb的头结点 */
    Lb=NULL;
}

测试主函数执行流程

在 main 函数中，我们演示了上述函数的调用顺序：初始化两个链表 -> 按不同规则输入数据 -> 遍历输出验证 -> 归并合并 -> 输出最终结果。这提供了一个完整的闭环测试环境。