02-线性结构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

代码实现

C语言

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


typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int expon;
    Polynomial link;
};


Polynomial ReadPoly() {
    int n;
    scanf("%d", &n);
    Polynomial Poly = (Polynomial)malloc(sizeof(struct PolyNode));
    Polynomial p = Poly;
    for (int i=0; i<n; i++ ) {
        Polynomial t = (Polynomial)malloc(sizeof(struct PolyNode));
        scanf("%d %d", &(t->coef), &(t->expon));
        t->link = NULL;
        p->link = t;
        p = t;      
    }
    return Poly;
}


Polynomial InsertPoly( Polynomial Poly, Polynomial t ) {
    Polynomial p, tmp;  // p标记当前项，tmp标记当前项的前一项 
    p = Poly;
    if ( p->link ) {
        while ( p->link ) { 
            tmp = p;
            p = p->link;
            if ( p->expon > t->expon ) {    //如果t的幂次小于此项，则继续向后查找
                continue;
            } else if ( p->expon < t->expon ) { //如果t的幂次大于此项 ，则t插入此项之前
                t->link = p;
                tmp->link = t;
                break;
            } else if ( p->expon == t->expon ) {    //如果t的幂次等于此项，则系数相加 
                p->coef = p->coef + t->coef;
                if ( p->coef == 0 ) {   //如果相加后系数为0，则删除该项 
                    tmp->link = p->link;
                    break;              
                } 
                break;  // 缺此句会重复添加。 
            }
        }
        if (p->expon > t->expon ) {
            p->link = t;    //  如果t的幂次最小，则添加到最后。 
        }
    } else {
        p->link = t;    // 如果是第一个节点则直接添加。 
    }
    return Poly;
}


Polynomial MultPoly( Polynomial P1, Polynomial P2 ) {
    Polynomial p1, p2, p;
    Polynomial Poly = (Polynomial)malloc(sizeof(struct PolyNode));
    Poly->link = NULL;
    p = Poly;
    p1 = P1;    
    while ( p1->link ) {
        p1 = p1->link;
        p2 = P2;
        while( p2->link ) {
            p2 = p2->link;
            Polynomial t = (Polynomial)malloc(sizeof(struct PolyNode));
            t->coef = p1->coef * p2->coef;
            t->expon = p1->expon + p2->expon;
            t->link = NULL;
            Poly = InsertPoly(Poly, t);
        }
    }
    return Poly;
}


Polynomial AddPoly( Polynomial P1, Polynomial P2 ) {
    Polynomial p1, p2, p;
    Polynomial Poly = (Polynomial)malloc(sizeof(struct PolyNode));
    p = Poly;
    p1 = P1->link;
    p2 = P2->link;
    while ( p1 && p2 ) {
        if ( p1->expon > p2->expon ) {
            Polynomial t = (Polynomial)malloc(sizeof(struct PolyNode));
            t->link = NULL;
            t->coef = p1->coef;
            t->expon = p1->expon;
            p->link = t;
            p = t;
            p1 = p1->link;
        } else if ( p1->expon < p2->expon ) {
            Polynomial t = (Polynomial)malloc(sizeof(struct PolyNode));
            t->link = NULL;
            t->coef = p2->coef;
            t->expon = p2->expon;
            p->link = t;
            p = t;
            p2 = p2->link;
        } else {
            Polynomial t = (Polynomial)malloc(sizeof(struct PolyNode));
            t->link = NULL;
            int tmp = p1->coef + p2->coef;
            if ( tmp ) {
                t->coef = tmp;
                t->expon = p1->expon;
                p->link = t;
                p = t;
                p1 = p1->link;
                p2 = p2->link;
            } else {
                p1 = p1->link;
                p2 = p2->link;
            }
        }
    } 
    p->link = p1?p1:p2;
    return Poly;
}


void PrintPoly( Polynomial Poly ) {
    int flag = 0;
    Polynomial p = Poly;
    if ( p->link ) {        
        while ( p->link ) {
            p = p->link;
            if ( flag ) {
                printf(" %d %d", p->coef, p->expon);
            } else {
                printf("%d %d", p->coef, p->expon);
                flag = 1;
            }           
        }
    } else {
        printf("0 0");
    }
}

int main() {
    Polynomial Poly_1, Poly_2, PolyAdd, PolyMult;
    Poly_1 = ReadPoly();
    Poly_2 = ReadPoly();
    PolyMult = MultPoly( Poly_1, Poly_2 );
    PolyAdd = AddPoly( Poly_1, Poly_2 );
    PrintPoly( PolyMult );
    printf("\n");
    PrintPoly( PolyAdd );
    return 0;
}