C语言实现一元多项式加法：线性链表与算法详解

本文将介绍如何使用C语言实现一元多项式的加法运算。我们将采用线性链表来存储多项式，并提供详细的算法讲解、代码示例以及测试用例。

1. 问题描述

编写一个程序，实现两个一元多项式的加法运算。例如，多项式A：3x^2 + 2x + 1，多项式B：x^3 + 4x + 2，则A+B = x^3 + 3x^2 + 6x + 3。

2. 解决方案

2.1 数据结构

采用线性链表存储多项式，每个节点包含系数、指数和指向下一个节点的指针。ctypedef struct PolyNode { int coef; // 系数 int exp; // 指数 struct PolyNode* next; // 下一个节点指针} polynomial;

2.2 算法描述

创建多项式链表: 分别读取多项式A和B的项数，然后按指数递增的顺序输入各项的系数和指数，创建对应的链表。2. 多项式相加: 遍历两个链表，比较当前节点的指数大小： - 若指数相同，则系数相加，并将结果存入新的节点； - 若指数不同，则将指数较小的节点插入结果链表，并将指针后移。3. 输出结果: 遍历结果链表，输出各项的系数和指数。

3. 代码示例c#include <stdio.h>#include <stdlib.h>

typedef struct PolyNode { int coef; // 系数 int exp; // 指数 struct PolyNode* next; // 下一个节点指针} polynomial;

// 创建多项式链表void CreatePolyn(polynomial** P, int m) { int i; polynomial *rear, *s; P = (polynomial)malloc(sizeof(polynomial)); rear = P; printf('请输入多项式的各项系数和指数（按指数递增顺序输入）： '); for (i = 0; i < m; i++) { s = (polynomial)malloc(sizeof(polynomial)); scanf('%d%d', &(s->coef), &(s->exp)); rear->next = s; rear = s; } rear->next = NULL;}

// 多项式相加void AddPolyn(polynomial* Pa, polynomial* Pb, polynomial** Pc) { polynomial p, q, pre, temp; p = Pa->next; q = Pb->next; Pc = (polynomial)malloc(sizeof(polynomial)); pre = Pc; while (p != NULL && q != NULL) { if (p->exp < q->exp) { temp = (polynomial)malloc(sizeof(polynomial)); temp->coef = p->coef; temp->exp = p->exp; pre->next = temp; pre = temp; p = p->next; } else if (p->exp > q->exp) { temp = (polynomial)malloc(sizeof(polynomial)); temp->coef = q->coef; temp->exp = q->exp; pre->next = temp; pre = temp; q = q->next; } else { if (p->coef + q->coef != 0) { temp = (polynomial)malloc(sizeof(polynomial)); temp->coef = p->coef + q->coef; temp->exp = p->exp; pre->next = temp; pre = temp; } p = p->next; q = q->next; } } while (p != NULL) { temp = (polynomial)malloc(sizeof(polynomial)); temp->coef = p->coef; temp->exp = p->exp; pre->next = temp; pre = temp; p = p->next; } while (q != NULL) { temp = (polynomial)malloc(sizeof(polynomial)); temp->coef = q->coef; temp->exp = q->exp; pre->next = temp; pre = temp; q = q->next; } pre->next = NULL;}

// 输出多项式void PrintPolyn(polynomial* P) { polynomial* p = P->next; if (p == NULL) { printf('<0,0> '); return; } while (p != NULL) { printf('< %d,%d >', p->coef, p->exp); if (p->next != NULL) { printf(','); } p = p->next; } printf(' ');}

int main() { int m, n; polynomial *Pa, Pb, Pc; Pa = (polynomial)malloc(sizeof(polynomial)); Pb = (polynomial)malloc(sizeof(polynomial));

printf('请输入多项式A的项数：

'); scanf('%d', &m); CreatePolyn(&Pa, m); printf('请输入多项式B的项数： '); scanf('%d', &n); CreatePolyn(&Pb, n);

printf('多项式Pa：');    PrintPolyn(Pa);    printf('多项式Pb：');    PrintPolyn(Pb);

AddPolyn(Pa, Pb, &Pc);    printf('多项式Pa+Pb：');    PrintPolyn(Pc);

return 0;}

4. 测试用例

输入:

请输入多项式A的项数：2请输入多项式的各项系数和指数（按指数递增顺序输入）：3 22 1请输入多项式B的项数：3请输入多项式的各项系数和指数（按指数递增顺序输入）：1 34 12 0

输出:

多项式Pa：< 3,2 >,< 2,1 >多项式Pb：< 1,3 >,< 4,1 >,< 2,0 >多项式Pa+Pb：< 1,3 >,< 3,2 >,< 6,1 >,< 2,0 >

5. 总结

本文介绍了如何使用线性链表实现一元多项式的加法运算，并提供了详细的算法讲解和代码示例。希望通过本文的介绍，读者能够更好地理解和掌握数据结构与算法的相关知识。