3. 线性表进阶：循环链表、双向链表、静态链表、线性表的应用（一元多项式）

好，咱们继续往前走。上一章我们把单链表的基本操作捋了一遍，那是最基础的线性表链式存储。但实际干活的时候，你会发现单链表有时候挺「拧巴」的——比如你想从中间某个节点往回找，对不起，得从头再来一遍。这就像你开车上了单行道，想掉头？没门。

这一章，咱们就把这些「单行道」升级成「环岛」、「双向四车道」，再聊聊一种不用指针的「静态链表」。最后，我会拿一元多项式这个经典案例，把线性表的应用串起来讲。

3.1 循环链表：让尾巴连上头

循环链表是什么？说白了，就是把单链表的最后一个节点的 next 指针，从 NULL 改成指向头节点。这样一来，整个链表就变成了一个环。

核心区别： 单链表判断结尾看 p->next == NULL；循环链表判断结尾看 p->next == head。

我早年做嵌入式 GUI 菜单系统的时候，就吃过这个设计的红利。菜单项是循环的——按「下一个」到了最后一项，再按一下回到第一项。如果用单链表，你得额外维护一个尾指针；用循环链表，天然就支持这种周而复始的操作。

3.1.1 循环链表的初始化与遍历

// 循环链表节点定义
typedef struct CNode {
    int data;
    struct CNode *next;
} CNode, *CLinkList;

// 初始化一个空循环链表（带头节点）
CLinkList InitCLinkList() {
    CLinkList head = (CLinkList)malloc(sizeof(CNode));
    if (!head) return NULL;
    head->next = head;  // 指向自己，形成空环
    return head;
}

// 遍历循环链表
void TraverseCLinkList(CLinkList head) {
    if (head == NULL) return;
    CNode *p = head->next;
    while (p != head) {  // 回到头节点说明遍历完了
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

注意看那个 while 条件——p != head。这是循环链表遍历的「死穴」，写错了就是死循环。我有个同事曾经把条件写成 p != NULL，结果程序跑起来直接卡死，CPU 飙到 100%。嗯，调试了半小时才发现。

3.1.2 循环链表的合并

循环链表有一个特别爽的应用：合并两个循环链表。你想想，如果两个单链表要合并，你得先找到各自的尾节点，然后改指针。循环链表呢？直接操作头节点就行，时间复杂度 O(1)。

// 合并两个带头节点的循环链表
CLinkList MergeCLinkList(CLinkList headA, CLinkList headB) {
    if (headA == NULL || headB == NULL) return NULL;
    
    CNode *tailA = headA->next;
    CNode *tailB = headB->next;
    
    // 找到 A 的尾节点
    while (tailA->next != headA) tailA = tailA->next;
    // 找到 B 的尾节点
    while (tailB->next != headB) tailB = tailB->next;
    
    // 开始拼接
    tailA->next = headB->next;  // A 的尾巴连 B 的第一个数据节点
    tailB->next = headA;        // B 的尾巴连 A 的头节点
    
    free(headB);  // B 的头节点没用了
    return headA;
}
我的习惯： 做循环链表的时候，我一般会额外维护一个尾指针。这样找尾节点就是 O(1)，不用每次都遍历。空间换时间，值。

3.2 双向链表：前后都能走

双向链表，顾名思义，每个节点有两个指针——一个指向前驱，一个指向后继。结构体长这样：

typedef struct DNode {
    int data;
    struct DNode *prior;  // 前驱指针
    struct DNode *next;   // 后继指针
} DNode, *DLinkList;

你可能会问：「多一个指针，内存开销大了，图啥？」

图的是操作效率。单链表里，你要删除某个节点的前驱节点，得从头遍历找到它前一个节点。双向链表呢？直接 p->prior 就拿到了。我在做数据库缓存池的 LRU 淘汰算法时，用的就是双向链表——因为要频繁地把一个节点移动到链表头部，双向链表做这个操作简直不要太顺手。

3.2.1 双向链表的插入操作

插入操作比单链表稍微麻烦一点，因为要改四个指针。我总结了一个口诀：「先连后断，先右后左」。什么意思？先把新节点和它的右边邻居连好，再处理左边。

// 在节点 p 之后插入新节点 s
int InsertAfterDNode(DNode *p, int value) {
    if (p == NULL) return -1;
    
    DNode *s = (DNode *)malloc(sizeof(DNode));
    if (!s) return -1;
    s->data = value;
    
    // 第一步：连右边
    s->next = p->next;
    s->prior = p;
    
    // 第二步：连左边（注意 p 可能是尾节点）
    if (p->next != NULL) {
        p->next->prior = s;
    }
    p->next = s;
    
    return 0;
}
我曾经踩过的坑： 在双向链表里删除节点时，一定要先判断 p->next != NULL 再改 p->next->prior。如果 p 是尾节点，p->next 是 NULL，你直接访问 p->next->prior 就是段错误。这个 bug 我当年调了一整个下午。

3.3 静态链表：没有指针的链表

有些场景下，你不能用动态内存分配——比如在单片机上，或者在一些实时性要求极高的系统里，malloc 和 free 是不允许的。这时候，静态链表就派上用场了。

静态链表本质上是一个结构体数组。数组的每个元素是一个节点，包含数据域和「游标」域——游标存的是下一个节点的数组下标。这就像用数组模拟了链表的逻辑结构。

#define MAXSIZE 100

typedef struct {
    int data;
    int cur;  // 游标，相当于 next 指针
} SLinkList[MAXSIZE];

静态链表里，下标为 0 的节点是头节点，它的 cur 指向第一个空闲节点。最后一个节点的 cur 为 0，表示链表结束。

说实话，静态链表现在用得不多。但我建议你理解它的思想——「用数组模拟链式结构」。我在做内存池管理的时候，就用过类似的手法：预分配一大块内存，然后用游标把空闲块串起来，分配和释放都是 O(1)。

3.4 线性表的应用：一元多项式

好了，前面铺垫了这么多，咱们来看一个实实在在的应用——一元多项式的表示和运算。

一个一元多项式长这样：P(x) = 3x^5 + 2x^3 + 7x + 9。怎么存？最直接的想法是用数组，下标当指数，值当系数。但问题是，如果多项式是 x^100 + 1，数组就得开 101 个元素，中间全是 0，太浪费了。

所以，我们用链表来存——每个节点存一个非零项，包含系数和指数。

typedef struct PolyNode {
    float coef;          // 系数
    int expn;            // 指数
    struct PolyNode *next;
} PolyNode, *Polynomial;

这样，3x^5 + 2x^3 + 7x + 9 就变成了四个节点，按指数降序排列。

3.4.1 多项式加法

两个多项式相加，核心逻辑就是：遍历两个链表，比较当前节点的指数。指数相等，系数相加；指数不等，把指数大的节点插入结果链表。

Polynomial AddPolynomial(Polynomial A, Polynomial B) {
    Polynomial C = (Polynomial)malloc(sizeof(PolyNode));
    C->next = NULL;
    PolyNode *pa = A->next, *pb = B->next, *pc = C;
    
    while (pa && pb) {
        if (pa->expn == pb->expn) {
            float sum = pa->coef + pb->coef;
            if (sum != 0.0) {  // 系数和为0，跳过
                PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode));
                s->coef = sum;
                s->expn = pa->expn;
                s->next = NULL;
                pc->next = s;
                pc = s;
            }
            pa = pa->next;
            pb = pb->next;
        } else if (pa->expn > pb->expn) {
            // 复制 A 的节点
            PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode));
            *s = *pa;  // 结构体赋值
            s->next = NULL;
            pc->next = s;
            pc = s;
            pa = pa->next;
        } else {
            // 复制 B 的节点
            PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode));
            *s = *pb;
            s->next = NULL;
            pc->next = s;
            pc = s;
            pb = pb->next;
        }
    }
    
    // 处理剩余节点
    while (pa) {
        PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode));
        *s = *pa;
        s->next = NULL;
        pc->next = s;
        pc = s;
        pa = pa->next;
    }
    while (pb) {
        PolyNode *s = (PolyNode *)malloc(sizeof(PolyNode));
        *s = *pb;
        s->next = NULL;
        pc->next = s;
        pc = s;
        pb = pb->next;
    }
    
    return C;
}
注意： 系数相加后如果为 0，这个节点就不要了。我见过有人忘了这个判断，结果多项式里多了个 0x^5，虽然数学上没错，但浪费空间，也不优雅。

3.4.2 多项式乘法

乘法比加法复杂一点。基本思路是：用 A 的每一项去乘 B 的所有项，然后把结果插入到结果多项式中。插入的时候要按指数排序，如果指数相同就合并系数。

这个算法的时间复杂度是 O(m×n)，m 和 n 分别是两个多项式的项数。如果多项式很稀疏，这个效率是可以接受的。

3.5 本章知识结构图

下面这张图把本章的核心知识点串起来了，你可以对照着回顾一下：

线性表进阶知识结构 线性表进阶 循环链表 尾指针指向头节点 遍历条件 p != head 合并操作 O(1) 双向链表 prior + next 双指针 插入需改4个指针 删除前驱 O(1) 静态链表 数组 + 游标实现 适合无动态内存环境 内存池管理思想 一元多项式应用 链表存储非零项 加法：指数匹配合并 乘法：逐项相乘再合并

这一章的内容，说白了就是让你从「只会用单链表」进化到「根据场景选链表」。循环链表适合周而复始的场景，双向链表适合频繁前后操作的场景，静态链表适合受限环境。而一元多项式，则是把这些知识揉在一起的一次实战演练。

我个人觉得，学数据结构最忌讳的就是「背代码」。你理解了每种结构的「为什么存在」，写代码就是水到渠成的事。下次遇到一个需要频繁在中间插入删除的问题，你脑子里第一个蹦出来的应该是链表，而不是数组——这就对了。

公众号:蓝海资料掘金营，微信deep3321
← 上一章 📖 返回目录 下一章 →