数据结构实战：用C语言链表手搓多项式加法，附赠PTA 6-3题全测试点解析

数据结构实战：用C语言链表手搓多项式加法，附赠PTA 6-3题全测试点解析

链表操作是数据结构课程的核心技能之一，而多项式加法则是检验这项能力的经典考题。无论是PTA、PAT还是LeetCode，这类题目都频繁出现。本文将带你从零开始，用C语言实现多项式加法，并针对PTA 6-3题的所有测试点进行详细解析，让你不仅会写代码，更理解背后的设计思路和常见陷阱。

1. 理解题目与数据结构设计

多项式加法看似简单，但要在计算机中优雅地实现它，需要先明确几个关键点。题目通常要求我们处理形如P(x) = 3x^5 + 2x^3 - 4x^2 + 7的多项式，其中每一项包含系数和指数两个关键信息。

链表节点的标准定义：

typedef struct PolyNode *Polynomial; struct PolyNode { int coef; // 系数 int expon; // 指数 Polynomial link; // 指向下一个节点的指针 };

选择链表而非数组的原因在于：

• 多项式项数不确定，链表可以动态增长
• 插入和删除操作更高效
• 零系数项可以轻松跳过，节省空间

注意：PTA 6-3题特别要求使用带头节点（dummy node）的链表结构，这能简化边界条件的处理。

2. 算法核心思路拆解

多项式加法的本质是合并两个有序链表（按指数降序排列）。以下是分步思考过程：

1. 初始化：创建结果链表的头节点
2. 遍历比较：使用双指针分别扫描两个多项式
   • 当前节点指数相同：系数相加
     • 若和不为零：创建新节点
     • 若和为零：跳过（不创建节点）
   • 当前节点指数不同：将较大指数的节点加入结果
3. 处理剩余项：将未遍历完的链表剩余部分接上
4. 返回结果：注意跳过空的头节点

关键伪代码逻辑：

while (p && q) { if (p->expon == q->expon) { sum = p->coef + q->coef; if (sum != 0) Attach(sum, p->expon, &rear); p = p->link; q = q->link; } else if (p->expon > q->expon) { Attach(p->coef, p->expon, &rear); p = p->link; } else { Attach(q->coef, q->expon, &rear); q = q->link; } }

3. 完整代码实现与逐行解析

以下是带详细注释的完整实现，特别注意内存管理和边界条件处理：

#include <stdio.h> #include <stdlib.h> typedef struct PolyNode *Polynomial; struct PolyNode { int coef; int expon; Polynomial link; }; void Attach(int coef, int expon, Polynomial *rear) { Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode)); P->coef = coef; P->expon = expon; P->link = NULL; (*rear)->link = P; *rear = P; } Polynomial ReadPoly() { Polynomial P, rear, temp; int N, c, e; P = (Polynomial)malloc(sizeof(struct PolyNode)); // 创建头节点 P->link = NULL; rear = P; scanf("%d", &N); while (N--) { scanf("%d %d", &c, &e); Attach(c, e, &rear); } temp = P; P = P->link; free(temp); // 释放头节点 return P; } Polynomial Add(Polynomial P1, Polynomial P2) { Polynomial front, rear, temp; int sum; rear = (Polynomial)malloc(sizeof(struct PolyNode)); // 结果链表头节点 front = rear; while (P1 && P2) { if (P1->expon == P2->expon) { sum = P1->coef + P2->coef; if (sum) Attach(sum, P1->expon, &rear); P1 = P1->link; P2 = P2->link; } else if (P1->expon > P2->expon) { Attach(P1->coef, P1->expon, &rear); P1 = P1->link; } else { Attach(P2->coef, P2->expon, &rear); P2 = P2->link; } } for (; P1; P1 = P1->link) Attach(P1->coef, P1->expon, &rear); for (; P2; P2 = P2->link) Attach(P2->coef, P2->expon, &rear); rear->link = NULL; temp = front; front = front->link; free(temp); // 释放头节点 return front; } void PrintPoly(Polynomial P) { if (!P) { printf("0 0\n"); return; } // 处理零多项式 int flag = 0; while (P) { if (!flag) flag = 1; else printf(" "); printf("%d %d", P->coef, P->expon); P = P->link; } printf("\n"); } int main() { Polynomial P1, P2, PS; P1 = ReadPoly(); P2 = ReadPoly(); PS = Add(P1, P2); PrintPoly(PS); return 0; }

4. PTA 6-3全测试点分析与避坑指南

根据大量学生提交的反馈，我们总结出以下关键测试点和常见错误：

高频错误TOP 3：

1. 未处理系数相加为零的情况，导致错误节点出现
2. 内存泄漏，特别是在使用带头节点写法时忘记释放临时头节点
3. 输出格式错误，包括末尾多余空格或缺少零多项式处理

提示：在本地测试时，可以构造以下极端案例：

• (0项) + (0项)
• (2x^100) + (-2x^100)
• (1 + 2x + 3x^2) + (-3x^2 - 2x -1)

5. 链表操作优化技巧

对于追求更高效率的学习者，可以考虑以下优化方向：

1. 递归实现：更简洁但可能有栈溢出风险

   Polynomial Add(Polynomial P1, Polynomial P2) { if (!P1) return P2; if (!P2) return P1; Polynomial P; if (P1->expon > P2->expon) { P = P1; P->link = Add(P1->link, P2); } else if (P1->expon < P2->expon) { P = P2; P->link = Add(P1, P2->link); } else { int sum = P1->coef + P2->coef; if (sum) { P = P1; P->coef = sum; P->link = Add(P1->link, P2->link); } else { return Add(P1->link, P2->link); } } return P; }

2. 二级指针技巧：避免使用Attach函数

   void AddWithPP(Polynomial P1, Polynomial P2, Polynomial *PP) { while (P1 && P2) { if (P1->expon == P2->expon) { int sum = P1->coef + P2->coef; if (sum) { *PP = P1; P1->coef = sum; PP = &(P1->link); P1 = P1->link; } else { Polynomial tmp = P1; P1 = P1->link; free(tmp); } P2 = P2->link; } // ...其他情况类似处理 } }

3. 内存池预分配：对于频繁的malloc/free操作，可以考虑预分配节点池

在实际工程项目中，这些优化可能带来性能提升，但在教学环境中，清晰可读的代码往往比微优化更重要。建议初学者先掌握基础实现，再考虑优化方案。