02-线性结构2 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式：

输入分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

code

#include<stdio.h>
typedef struct Node *List;
struct Node{
    int coefficient;
    int Index;
    List Next;
};
List read();
void Attach(int coefficient, int Index, List *rear); 
List pyAddition(List L1, List L2);
int compare(int e1, int e2);
List pymultiplication(List L1, List L2);
void Attach(int coefficient, int Index, List *rear)
{
    List p;
    p = malloc(sizeof(struct Node));
    p->coefficient = coefficient;
    p->Index = Index;
    p->Next = NULL;
    (*rear)->Next = p;
    *rear = p;
}
int compare(int e1,int e2)
{
    if(e1>e2) return 1;
    else if(e1<e2) return -1;
    else return 0;
}
List read()
{
    int n,c,i,j;
    List L,r;
    L = malloc(sizeof(struct Node));
    r = L;
    scanf("%d",&n);
    for(j=0; j<n; j++)
    {
        scanf("%d",&c);
        scanf("%d",&i);
        Attach(c,i,&r);
    }
    r->Next = NULL;
    return L->Next;
}
List pyAddition(List L1, List L2)
{
    List P1 = L1,P2 = L2,P3,rear;
    P3 = malloc(sizeof(struct Node));
    rear = P3;
    while(P1&&P2){
        switch(compare(P1->Index,P2->Index)) {
            case 1:
                Attach(P1->coefficient,P1->Index, &rear);
                P1=P1->Next;
                break;
            case -1:
                Attach(P2->coefficient,P2->Index, &rear);
                P2=P2->Next;
            case 0:
                if(P1->coefficient+P2->coefficient) Attach(P1->coefficient+P2->coefficient,P1->Index, &rear);
                P1 = P1->Next;
                P2 = P2->Next;
                break;
        }
    }
    for(; P1; P1=P1->Next) Attach(P1->coefficient,P1->Index, &rear);
    for(; P2; P2=P2->Next) Attach(P2->coefficient,P2->Index, &rear);
    rear->Next = NULL;
    P3 = P3->Next;
    return P3; 
}
List pymultiplication(List L1, List L2)
{
    List P,rear,t1,t2,t;
    int c,i;
    if(!L1||!L2) return NULL;
    t1 = L1;t2 = L2;
    P = malloc(sizeof(struct Node));P->Next = NULL;
    rear = P;
    while(t2){
        Attach(t1->coefficient*t2->coefficient,t1->Index+t2->Index, &rear);
        t2 = t2->Next;  
    }
    t1 = t1->Next;
    while(t1){
        t2 = L2;rear = P;
        while(t2){
            c = t1->coefficient*t2->coefficient;
            i = t1->Index+t2->Index;
            while(rear->Next && rear->Next->Index>i)
                rear = rear->Next;
            if(rear->Next && rear->Next->Index==i){
                if(rear->Next->coefficient+c)
                    rear->Next->coefficient += c;
                else{
                    t = rear->Next;
                    rear->Next = t->Next;
                    free(t);
                }
            }
            else{
                t = malloc(sizeof(struct Node));
                t->coefficient=c;t->Index=i;
                t->Next = rear->Next;
                rear->Next=t;rear=rear->Next;
            }
            t2 = t2->Next;
        }
        t1 = t1->Next;
    }
    t2=P;P=P->Next;free(t2);
    return P;   
} 
int main()
{
    List L1,L2,L3,L4;
    L1 = read();
    L2 = read();
    L3 = pymultiplication(L1,L2);
    if(!L3) printf("0 0");
    while(L3){
        printf("%d %d",L3->coefficient,L3->Index);
        if(L3->Next) printf(" ");
        L3 = L3->Next;
    }
    printf("\n");
    L4 = pyAddition(L1,L2);
    if(!L4) printf("0 0");
    while(L4){
        printf("%d %d",L4->coefficient,L4->Index);
        if(L4->Next) printf(" ");
        L4 = L4->Next;
    }
    return 0;
}

运行结果：

运行结果

---