7-2 一元多项式的乘法与加法运算 (20 分) （链表实现）

7-2 一元多项式的乘法与加法运算 (20 分) （链表实现）
设计函数分别求两个一元多项式的乘积与和。

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

代码如下：

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

typedef struct PolyNode{//结构，用来存放多项式结点
    int coef;//系数
    int expon;//指数
    struct PolyNode * next;
}Node, *pNode;
typedef struct poly{//结构，用来表示多项式
    pNode front;//指向多项式的第一项
    pNode rear;//指向多项式的最后一项
}Poly, *pPoly;

Poly create(int coef, int expon);//创建仅含一个系数为coef指数为expon的结点的多项式并将其返回
void attach(int coef, int expon, pPoly p);//将一个系数为coef指数为expon的结点附在多项式p后
Poly addpoly(Poly p1, Poly p2);//两多项式相加，并将结果多项式返回
Poly nodemulpoly(Node node, Poly p);//用多项式中的一项乘以另一个多项式p，返回结果多项式
Poly mulpoly(Poly p1, Poly p2);//将多项式p1与多项式p2相乘，返回结果多项式
void printpoly(Poly p);//输出多项式p

int main() {
    int n1, n2;
    scanf("%d", &n1);
    int c = 0, e = 0;
    Poly p1 = create (c, e);
    if (n1) {//这里需要注意，n1或n2可能为零
        scanf("%d %d", &c, &e);
        p1 = create(c, e);
    }
    for (int i = 1; i < n1 ; ++i) {
        scanf("%d %d", &c, &e);
        attach(c, e, &p1);
    }
    scanf("%d", &n2);
    Poly p2 = create(0, 0);
    if (n2) {
        scanf("%d %d", &c, &e);
        p2 = create(c, e);
    }
    for (int i = 1; i < n2 ; ++i) {
        scanf("%d %d", &c, &e);
        attach(c, e, &p2);
    }
    
   //以上为读入数据部分
    
    Poly Padd = addpoly(p1, p2);
    Poly Pmul = mulpoly(p1, p2);
    printpoly(Pmul), printpoly(Padd);
    return 0;
}
Poly create(int coef, int expon)//创建仅含一个系数为coef指数为expon的结点的多项式并将其返回
{
    pNode s = (pNode)malloc(sizeof(Node));
    s->coef = coef;
    s->expon = expon;
    s->next = NULL;
    Poly p = {.front = s, .rear = s};
    return p;
}
void attach(int coef, int expon, pPoly p)//将一个系数为coef指数为expon的结点附在多项式p后
{
    pNode s = (pNode)malloc(sizeof(Node));
    s->next = NULL;
    s->coef = coef;
    s->expon = expon;
    p->rear->next = s;
    p->rear = s;
}
Poly addpoly(Poly p1, Poly p2)//两多项式相加，并将结果多项式返回
{
    Poly ans = create(0, 0);
    pNode s1 = p1.front, s2 = p2.front;
    while (s1 || s2) {
        switch ((s1->expon > s2->expon) ? 1 : ( (s1->expon == s2->expon) ? 0 : -1)) {
            case 1:
                attach(s1->coef, s1->expon, &ans);
                if (s1) s1 = s1->next;
                break;
            case 0:
                if (s1->coef + s2->coef != 0)
                    attach(s1->coef + s2->coef, s1->expon, &ans);
                if (s1) s1 = s1->next;
                if (s2) s2 = s2->next;
                break;
            case -1:
                attach(s2->coef, s2->expon, &ans);
                if (s2) s2 = s2->next;
        }
        if (!s1) {
            while (s2) {
                if (s2->coef)
                    attach(s2->coef, s2->expon, &ans);
                s2 = s2->next;
            }
            break;
        } else if (!s2) {
            while (s1) {
                if (s1->coef)
                    attach(s1->coef, s1->expon, &ans);
                s1 = s1->next;
            }
            break;
        }
    }
    if (ans.front == ans.rear && ans.front->coef == 0)
        return ans;    
    pNode tmp = ans.front;
    ans.front = ans.front->next;
    free(tmp);
    return ans;
}
Poly nodemulpoly(Node node, Poly p) {//用多项式中的一项乘以另一个多项式p，返回结果多项式
    Poly ans = create(0, 0);
    pNode s = p.front;
    while(s) {
        attach(node.coef * s->coef, node.expon + s->expon, &ans);        
        s = s->next;
    }
    ans.front = ans.front->next;
    return ans;
}
Poly mulpoly(Poly p1, Poly p2)//将多项式p1与多项式p2相乘，返回结果多项式
{
    Poly ans = create(0, 0);
    if (p1.front->coef == 0 || p2.front->coef == 0)
        return ans;
    pNode s = p1.front;
    while (s) {
        Poly tmp = nodemulpoly(*s, p2);
        ans = addpoly(tmp, ans);
        s = s->next;
    }
    return ans;
}
void printpoly(Poly p)//输出多项式p
{
    pNode s = p.front;
    while (s->next) {
        printf("%d %d ", s->coef, s->expon);
        s = s->next;
    }
    printf("%d %d\n", s->coef, s->expon);
}

算法思路大致如下

用链表来存储多项式的每一项，每一个结点的数据域存放系数ceof和次数expon。多项式为从高次数项至低次数项排列。

先实现加法。取两个多项式，从头开始遍历：

①若第一个多项式的当前项比第二个多项式的当前项次数高，则把第一个多项式的当前项放入结果多项式中；
②若第一个多项式的当前项与第二个多项式的当前项相同，则令两项相加。一个细节是，若加完后系数为零，则不把该项放入结果多项式中。
③若第一个多项式的当前项比第二个多项式的当前项次数低，则把第二个多项式的当前项放入结果多项式中；
④若在遍历过程中有一个多项式已经被处理完毕，则将另一个多项式的剩余项放入结果多项式中。

再实现乘法。
取两个多项式，遍历其中一个多项式的所有项。在此过程中，用遍历的当前项乘以另一个多项式的所有项，与结果多项式相加。最终得到的结果多项式即为乘法的结果。

由以上算法可以看出，加法的时间复杂度是O(N)，乘法的时间复杂度为O(N^2)，乘法的时间复杂度有优化的空间。（不知道怎么优化(T＿T)）
这个题的细节很多，再具体的细节就直接看代码吧。