一元多项式的乘法与加法运算

发表于 2019-03-10 阅读次数：本文字数： 4.9k 阅读时长 ≈ 4 分钟

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

输入格式

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

输出格式

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

输入样例

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

输出样例

1 2	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>
typedef struct NUM * List;
struct NUM {
    int coef;//系数
    int expo;//指数
    List next;
};
void addNode(int coef, int expo, List *rear);
List add(List quem, List quen);
List mul(List quem, List quen);
List insertSortandMerge(List front);
void Print(List res);
int main()
{
    int m, n,coef,expo;
    List quem, quen, resadd, resmul;
    List rearm = (List)malloc(sizeof(struct NUM)), rearn = (List)malloc(sizeof(struct NUM));
    rearm->next = NULL;
    rearn->next = NULL;
    quem = rearm;
    quen = rearn;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &coef, &expo);
        addNode(coef, expo, &rearm);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &coef, &expo);
        addNode(coef, expo, &rearn);
    }
    resadd = add(quem->next, quen->next);
    resmul = mul(quem->next, quen->next);
    Print(resmul);
    printf("\n");
    Print(resadd);
    return 0;
}
void addNode(int coef, int expo, List *rear)
{
    //由于在本函数中需要改变当前结果表达式尾项指针的值
    //所以函数传递进来的是尾项结点指针的地址，*rear指向尾项
    List P = (List)malloc(sizeof(struct NUM));//申请新节点并赋值
    P->coef = coef;
    P->expo = expo;
    P->next = NULL;
    //将P指向的新节点插入到当前结果表达式尾项的后面
    (*rear)->next = P;
    *rear = (*rear)->next;//修改rear值
}
List add(List quem, List quen)
{
    List front, rear, temp;//为方便表头插入，先产生一个临时空结点作为结果多项式链表头
    rear = (List)malloc(sizeof(struct NUM));
    front = rear;//由front记录结果多项式链表头结点
    int sum;
    while (quem&&quen)//当两个多项式都有非零项待处理时
    {
        if (quem->expo == quen->expo)//两数据项指数相等
        {
            sum = quem->coef + quen->coef;
            if (sum)
                addNode(sum, quem->expo, &rear);
            quem = quem->next;
            quen = quen->next;
            continue;
        }
        if (quem->expo < quen->expo)//quen中的数据项指数较大
        {
            addNode(quen->coef, quen->expo, &rear);
            quen = quen->next;
            continue;
        }
        if (quem->expo > quen->expo)//quem中的数据项指数较大
        {
            addNode(quem->coef, quem->expo, &rear);
            quem = quem->next;
            continue;
        }
    }
    //将未处理完的另一个多项式的所有结点依次复制到结果多项式中去
    while (quem)
    {
        addNode(quem->coef, quem->expo, &rear);
        quem = quem->next;
    }
    while (quen)
    {
        addNode(quen->coef, quen->expo, &rear);
        quen = quen->next;
    }
    rear->next = NULL;
    temp = front;
    front = front->next;//令front指向结果多项式第一个非零项
    free(temp);//释放临时空表头结点
    return front;
}
List mul(List quem, List quen)
{
    List front, rear, temp, Fquem;//Fquem保存quem的位置
    int sum, mul;
    rear = (List)malloc(sizeof(struct NUM));
    front = rear;
    Fquem = quem;
    while (quen)
    {
        while (quem)
        {
            sum = (quem->coef) * (quen->coef);
            mul = (quem->expo) + (quen->expo);
            addNode(sum, mul, &rear);
            quem = quem->next;
        }
        quem = Fquem;//重置quem
        quen = quen->next;
    }
    rear->next = NULL;
    temp = front;
    front = front->next;
    free(temp);
    front = insertSortandMerge(front);

    return front;
}
List insertSortandMerge(List front)
{
    //处理多项式乘法的结果
    /*按指数从大到小进行插入排序，第二个循环中顺便将要插入的项与之前排好序的“队列”中指数相同的项进行合并*/
    List head, temp, front_to_free = front;
    int sum;
    head = (List)malloc(sizeof(struct NUM));
    head->next = NULL;
    if (front == NULL)
        return NULL;
    else
    {
        head->coef = front->coef;
        head->expo = front->expo;
        front = front->next;
    }
    while (front)
    {
        temp = head;
        while (temp->next)
        {

            if (front->expo == temp->next->expo)
            {
                sum = temp->next->coef + front->coef;
                if (sum)
                {
                    temp->next->coef = sum;
                }
                else
                {
                    temp->next = temp->next->next;
                }
                front = front->next;
                break;
            }
            if (front->expo > head->expo)
            {
                List t = (List)malloc(sizeof(struct NUM));
                t->coef = front->coef;
                t->expo = front->expo;
                t->next = head;
                head = t;
                front = front->next;
                free(t);
                break;
            }
            if (front->expo < temp->expo && front->expo>temp->next->expo)
            {
                List t = (List)malloc(sizeof(struct NUM));
                t->coef = front->coef;
                t->expo = front->expo;
                t->next = temp->next;
                temp->next = t;
                front = front->next;
                free(t);
                break;
            }
            temp = temp->next;
        }
        if (temp->next == NULL)
        {
            addNode(front->coef, front->expo, &temp);
            front = front->next;
        }
    }
    free(front_to_free);
    return head;
}
void Print(List res)
{
    //输出操作，首先特判一下
    if (res == NULL)
        printf("0 0");
    else while (res)
    {
        printf("%d %d", res->coef, res->expo);
        if (res->next)
            printf(" ");
        res = res->next;
    }
}

测试点信息

测试点    提示
0        sample换个数字
1        同类项合并时有抵消
2        系数和指数取上限，结果有零多项式
3        输入有零多项式和常数多项式

~~什么都不想说，因为写了六个小时，太累了。~~

好吧，时隔一个星期，我又回来补上了一部分注释。