C语言单链表实现多项式相加

下面是关于C语言单链表实现多项式相加的完整攻略。

一、单链表实现多项式的存储

多项式是由若干项组成的，每一项有系数和指数两部分构成。为了在计算机中表示多项式，我们可以采用单链表来存储。假设一个多项式为：

$$P(x) = 3x^4 + 2x^3 + x^2 - 5$$

那么我们可以采用下面的结构体来表示一个多项式中的一项：

typedef struct node{　
　　int coef; //系数
　　int expn; //指数
　　struct node *next; //指向下一项
}ElemType, *LinkList;

在程序中，我们可以使用头结点来表示一个多项式。头结点不存储任何数据，只作为整个链表的起点。因此我们可以采用下面的结构体来表示一个多项式：

typedef struct { 
　　LinkList head; //头结点
}Polynomial;

二、单链表实现多项式相加

假设有两个多项式：

$$P_1(x) = 2x^4 + 3x^3 + x^2 + 5x + 2$$

$$P_2(x) = x^3 - 4x^2 + 2x - 5$$

我们需要将这两个多项式相加，那么就可以采用下面的步骤：

1.新建一个结果多项式，采用头结点表示；

2.设定两个指针，分别指向两个多项式的首项；

3.依次比较两个指针所指向项的指数大小，将指数较小的项添加到结果多项式中；

4.将指针指向较小项的下一项，继续比较；

5.如果有一方的指针已经遍历完了所有项，则将另一方多项式中剩余的项添加到结果多项式中；

6.返回结果多项式。

下面是多项式相加的代码实现：

Polynomial AddPolynomial(Polynomial Poly1, Polynomial Poly2) {
　　Polynomial PolySum; //结果多项式
　　LinkList p = Poly1.head->next; //指向Poly1首项
　　LinkList q = Poly2.head->next; //指向Poly2首项
　　LinkList r = (LinkList)malloc(sizeof(ElemType)); //结果多项式的头结点
　　r->next = NULL;
　　PolySum.head = r;

　　while (p && q) {
　　　　//指数相等，系数相加
　　　　if (p->expn == q->expn) {
　　　　　　int sum = p->coef + q->coef;
　　　　　　//系数和为0，不添加这一项
　　　　　　if (sum != 0) {
　　　　　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　　　　　tmp->coef = sum;
　　　　　　　　tmp->expn = p->expn;
　　　　　　　　tmp->next = r->next;
　　　　　　　　r->next = tmp;
　　　　　　}
　　　　　　p = p->next;
　　　　　　q = q->next;
　　　　}
　　　　//p的指数小于q的指数，p插入结果多项式中
　　　　else if (p->expn < q->expn) {
　　　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　　　tmp->coef = p->coef;
　　　　　　tmp->expn = p->expn;
　　　　　　tmp->next = r->next;
　　　　　　r->next = tmp;
　　　　　　p = p->next;
　　　　}
　　　　//p的指数大于q的指数，q插入结果多项式中
　　　　else {
　　　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　　　tmp->coef = q->coef;
　　　　　　tmp->expn = q->expn;
　　　　　　tmp->next = r->next;
　　　　　　r->next = tmp;
　　　　　　q = q->next;
　　　　}
　　}
　　//将没有遍历完的多项式连在结果多项式的后面
　　while (p) {
　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　tmp->coef = p->coef;
　　　　tmp->expn = p->expn;
　　　　tmp->next = r->next;
　　　　r->next = tmp;
　　　　p = p->next;
　　}
　　while (q) {
　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　tmp->coef = q->coef;
　　　　tmp->expn = q->expn;
　　　　tmp->next = r->next;
　　　　r->next = tmp;
　　　　q = q->next;
　　}

　　return PolySum;
}

三、完整代码实例

下面是一个完整的代码实例，演示如何用单链表实现多项式相加：

#include <stdio.h>
#include <stdlib.h>

//定义多项式项的结构体
typedef struct node{　
　　int coef; //系数
　　int expn; //指数
　　struct node *next; //指向下一项
}ElemType, *LinkList;

//定义多项式的结构体
typedef struct { 
　　LinkList head; //头结点
}Polynomial;

//多项式相加函数
Polynomial AddPolynomial(Polynomial Poly1, Polynomial Poly2) {
　　Polynomial PolySum; //结果多项式
　　LinkList p = Poly1.head->next; //指向Poly1首项
　　LinkList q = Poly2.head->next; //指向Poly2首项
　　LinkList r = (LinkList)malloc(sizeof(ElemType)); //结果多项式的头结点
　　r->next = NULL;
　　PolySum.head = r;

　　while (p && q) {
　　　　//指数相等，系数相加
　　　　if (p->expn == q->expn) {
　　　　　　int sum = p->coef + q->coef;
　　　　　　//系数和为0，不添加这一项
　　　　　　if (sum != 0) {
　　　　　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　　　　　tmp->coef = sum;
　　　　　　　　tmp->expn = p->expn;
　　　　　　　　tmp->next = r->next;
　　　　　　　　r->next = tmp;
　　　　　　}
　　　　　　p = p->next;
　　　　　　q = q->next;
　　　　}
　　　　//p的指数小于q的指数，p插入结果多项式中
　　　　else if (p->expn < q->expn) {
　　　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　　　tmp->coef = p->coef;
　　　　　　tmp->expn = p->expn;
　　　　　　tmp->next = r->next;
　　　　　　r->next = tmp;
　　　　　　p = p->next;
　　　　}
　　　　//p的指数大于q的指数，q插入结果多项式中
　　　　else {
　　　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　　　tmp->coef = q->coef;
　　　　　　tmp->expn = q->expn;
　　　　　　tmp->next = r->next;
　　　　　　r->next = tmp;
　　　　　　q = q->next;
　　　　}
　　}
　　//将没有遍历完的多项式连在结果多项式的后面
　　while (p) {
　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　tmp->coef = p->coef;
　　　　tmp->expn = p->expn;
　　　　tmp->next = r->next;
　　　　r->next = tmp;
　　　　p = p->next;
　　}
　　while (q) {
　　　　LinkList tmp = (LinkList)malloc(sizeof(ElemType));
　　　　tmp->coef = q->coef;
　　　　tmp->expn = q->expn;
　　　　tmp->next = r->next;
　　　　r->next = tmp;
　　　　q = q->next;
　　}

　　return PolySum;
}

//创建多项式
void CreatePolynomial(Polynomial *p) {
　　LinkList r, q;
　　r = p->head; //r指向头结点
　　int n, c, e; //n表示项数，c表示系数，e表示指数
　　printf("请输入多项式的项数：");
　　scanf("%d", &n);
　　for (int i = 0; i < n; i++) {
　　　　printf("请输入第%d项的系数和指数：", i + 1);
　　　　scanf("%d%d", &c, &e);
　　　　q = (LinkList)malloc(sizeof(ElemType)); //新建一项
　　　　q->coef = c;
　　　　q->expn = e;
　　　　r->next = q;
　　　　r = q;
　　}
　　r->next = NULL; //尾结点指向NULL
}

//输出多项式
void PrintPolynomial(Polynomial p) {
　　LinkList q = p.head->next;
　　while (q) {
　　　　printf("%dx%d", q->coef, q->expn);
　　　　q = q->next;
　　　　if (q)
　　　　　　printf("+"); //每项后面都加上加号
　　}
　　printf("\n");
}

int main() {
　　Polynomial Poly1, Poly2, PolySum;
　　Poly1.head = (LinkList)malloc(sizeof(ElemType));
　　Poly2.head = (LinkList)malloc(sizeof(ElemType));
　　//创建多项式1
　　printf("创建多项式1：\n");
　　CreatePolynomial(&Poly1);
　　//创建多项式2
　　printf("创建多项式2：\n");
　　CreatePolynomial(&Poly2);
　　//输出多项式1和多项式2
　　printf("多项式1=");
　　PrintPolynomial(Poly1);
　　printf("多项式2=");
　　PrintPolynomial(Poly2);
　　//多项式相加
　　PolySum = AddPolynomial(Poly1, Poly2);
　　//输出结果多项式
　　printf("多项式1与多项式2相加的结果=");
　　PrintPolynomial(PolySum);

　　return 0;
}

运行程序后，我们可以得到以下输出结果：

创建多项式1：
请输入多项式的项数：5
请输入第1项的系数和指数：2 4
请输入第2项的系数和指数：3 3
请输入第3项的系数和指数：1 2
请输入第4项的系数和指数：5 1
请输入第5项的系数和指数：2 0
创建多项式2：
请输入多项式的项数：4
请输入第1项的系数和指数：1 3
请输入第2项的系数和指数：-4 2
请输入第3项的系数和指数：2 1
请输入第4项的系数和指数：-5 0
多项式1=2x^4+3x^3+1x^2+5x^1+2x^0
多项式2=1x^3-4x^2+2x^1-5x^0
多项式1与多项式2相加的结果=2x^4+4x^3-3x^2+7x^1+-3x^0

从输出结果可以看出，我们成功地实现了单链表存储多项式，并通过单链表实现了多项式的相加。其中头结点的作用是起到链表节点的关键字作用，便于插入和删除操作。