3-4： 一元多项式的乘法与加法运算

题目链接：https://pintia.cn/problem-sets/434/problems/5865

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

struct Node {
    int coef;
    int expon;
    struct Node* Next;
};

typedef struct Node* List;

//在链表尾部添加元素
void Attach(int c, int e, List *Rear)
{
    List p = (List)malloc(sizeof(struct Node));
    p->coef = c;
    p->expon = e;
    p->Next = NULL;
    (*Rear)->Next = p;
    *Rear = p;
}

List CreateList()
{
    int N, coef, expon;
    List front, rear, temp;
    front = rear = (List)malloc(sizeof(struct Node));
    front->Next = rear->Next = NULL;
    scanf("%d", &N);
    while (N--)
    {
        scanf("%d %d", &coef, &expon);
        Attach(coef, expon, &rear);
    }
    temp = front;
    front = front->Next;
    free(temp);
    return front;
}

//比较两个结点的指数，将返回结果作为switch函数的参数
int Compare(int expon1, int expon2)
{
    if (expon1 > expon2)
        return 1;
    else if (expon1 == expon2)
        return 0;
    else
        return -1;

}

//将两个多项式相加
List AddPoly(List p1, List p2)
{
    List t1, t2, front, rear, temp;
    int sum;
    front = rear = (List)malloc(sizeof(struct Node));
    front -> Next = rear -> Next = NULL;
    t1 = p1; t2 = p2;
    while (t1 && t2)
    {
        switch (Compare(t1->expon, t2->expon))
        {
        case 1:
            Attach(t1->coef, t1->expon, &rear);
            t1 = t1->Next;
            break;
        case 0:
            sum = t1->coef + t2->coef;
            if (sum)
                Attach(sum, t1->expon, &rear);
            t1 = t1->Next;
            t2 = t2->Next;
            break;
        case -1:
            Attach(t2->coef, t2->expon, &rear);
            t2 = t2->Next;
            break;
        }
    }
    for (; t1; t1= t1->Next)
        Attach(t1->coef, t1->expon, &rear);
    for (; t2; t2 = t2->Next)
        Attach(t2->coef, t2->expon, &rear);
    temp = front;
    front = front->Next;
    free(temp);
    return front;
}

//将两个多项式相乘
List MultiPolynomial(List p1, List p2)
{
    List t1, t2, temp, front, rear, cell;
    
    int sum;
    front = rear = (List)malloc(sizeof(struct Node));
    front->Next = front -> Next = NULL;
    t1 = p1; t2 = p2;
    if (!t1 || !t2)
    {
        return NULL;
    }
    while (t1 && t2)
    {
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &rear);
        t2 = t2->Next;
    }
    t1 = t1->Next; t2 = p2;
    while (t1)
    {
        while (t2)
        {
            temp = (List)malloc(sizeof(struct Node));
            temp->coef = t1->coef * t2->coef;
            temp->expon = t1->expon + t2->expon;
            for (cell = front; cell->Next && (cell ->Next)->expon > temp->expon ; cell = cell->Next);
            if (!cell->Next)
            {
                cell->Next = temp;
                temp -> Next = NULL;
            }
                
            else if (cell->Next->expon == temp->expon)　　//如果cell->Next结点的指数和temp的指数相同
            {
                sum = cell->Next->coef + temp->coef;
                if (sum)　　　　　　　　　　　　　　//如果两项系数相加不为0，则只需更新原项的系数即可
                    cell->Next->coef = sum;
                else
                {
                    temp = cell->Next;　　　　　　//如果两项系数相加为0，则需将原项结点删除
                    cell->Next = temp->Next;
                    free(temp);
                }
            }
            else
            {
                temp->Next = cell->Next;
                cell->Next = temp;
            }
            t2 = t2->Next;
        }
        t2 = p2;
        t1 = t1->Next;
    }
    temp = front;
    front = front->Next;
    free(temp);
    return front;
}


//打印一个链表多项式
void printPoly(List p)
{
    List cell;
    int flag = 0;
    if (!p)
    {
        printf("0 0
");
        return;
    }
    for (cell = p; cell; cell = cell->Next)
    {
        if (!flag)
            flag = 1;
        else
            printf(" ");
        printf("%d %d", cell->coef, cell->expon);
    }
    printf("
");
}

int main()
{
    List p1 = CreateList();
    List p2 = CreateList();
    List p4 = MultiPolynomial(p1, p2);
    printPoly(p4);

    List p3 = AddPoly(p1, p2);
    printPoly(p3);
    

    return 0;
}