问题描述

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

输入格式:
输入分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

解决思路

解决这个问题主要有数组实现和链表实现两种方法，为了训练使用链表，以及可能会出现超时或者内存不足的情况，本文中是用链表形式来实现多项式的加法，乘法运算

数组实现

在加法数组中:（index-1000）表示指数，里面的内容表示系数
在加法数组中:（index-2000）表示指数，里面的内容表示系数
使用两个大小为2002*sizeof(int)数组来接受数据（因为绝对值不大于1000，最后一项放非零项的个数

定义存放加法结果的数组（大小同样为2002），初始化为0
将两个多项式分别放入加法数组中，对应的指数的系数+=放入系数即可；

定义存放乘法结果的数组（大小为4002）初始化为0
poly1（多项式1，下同）每个项分别乘以poly2，放到乘法数组之中，对应系数+=放入系数即可；

输出：首先先看非零项为0，便输出0 0，如果不是，则便利整个结果数组，只有遇到内容不是0，才输出对应系数和指数

算法分析

简单概括思路，只需要通过下标找到指数即可，然后对应内容加上系数。输出遇到系数为0便不输出

操作较为简单，如果非零项较小，便会有很多空的节点，内存开销太大，并且每次输入系数，输出都需要遍历整个数组，使得效率非常低

链表实现

1.首先使用链表接受数据，每个节点的数据格式如下：
[coust, power next]
[系数，指数，下一个节点地址]
头节点中的系数域用于放置非零项个数，指数域预置一个比较大的数（用处后面将讲解）

2.首先需要知道一点，在本题中多项式乘法的实现本质是加法的实现，因为多项式中乘法可以分解成为加法。乘法结果可以分解为poly1每个项乘以poly2的和，所以下面着重讲解加法的实现

3.我们使用一个空链表来存储加法结果（系数项预置为0，指数项预置为大于4000的值），接下来我们要做的便是分别把两个多项式放入这个链表中

放入这个链表的动作可以分为两步：
step1：通过传入需要放入的项的指数，在目标链表找到放的位置（return的是放的位置的地址）
step2：通过地址找到的节点，将系数放进去

乘法运算便是每个项与另一个项相乘形成的多项式分别放入乘法链表之中

4.输出链表，若头节点系数域为0，输出0 0；否则则遍历整个链表 遇到系数非零才会输出项

Some Detail Of Function（建议配合代码食用

Pnode createList(void)：用于存放输入数据，没什么好说的
Pnode copyList(Pnode head)：将链表拷贝到一个新链表

Notice：这里需要说明一下copyList在代码中的作用。在加法运算中，我的存放加法结果的addPoly本身不是空的,是已经拷贝了Poly1内容的链表，目的是为在加法运算时的方便，直接将poly2加入其中即可。不需要把poly1加入addPoly，再把poly2也加入

void add(Pnode head1, Pnode head2)：head1是加式，head2是被加式。也就是说，把head1加到head2上，最后head2存放的是加法结果（isInsert待会会讲解用处
1.每次temp1指向head1的存放数据的节点，将temp1->power传入findEle函数，寻找head2中的合适地址用于插入或者直接放入（下面会详细讲解
2.使用insert函数将该项放入head2之中，然后temp1指向下一个节点

Pnode findEle(int power, Pnode head)：传入指数，在被加式head中寻找出一个合适的地址并返回该地址；为什么会说是合适的地址？因为我们对加入项的操作可能是插入，或者不需要插入。如下图所示：

image.png

image.png

 值得一提的是，在整个加法插入中，我们只需遍历一次多项式，便可以整个加法运算，因为输入的项的指数是按从高到低的顺序

因为这块是难点重点，所以稍微总结一下：
 我们首先传入power，通过它来寻找一个合适的位置，传入的head便是从head指向的节点开始向后寻找（第一次使用这个函数传入的head都是指向头节点的）
 在寻找的过程中if (temp->power == power || temp->next == 0)，便返回temp；if(temp->next->power >= power)，便更新temp，否则便表示结果是需要在temp后面插入节点，返回temp；

void insert(int * isInsert, Pnode head1, Pnode head2)：将项插入节点后面后者修改该节点
 这里可以解释isInsert的作用，如果表示插入，那么我们便会把isInsert改成1，表示头结点的非零项的数目需要++；如果表示修改，便查看修改后的系数是否等于零，如果为零，便会改成1。表示需要将非零项的个数--；若不等于零便会改成0，不需要修改非零项的个数

Pnode multi(Pnode head1, Pnode head2)：核心和加法运算大致相同，只是多了一层二重循环，来执行乘法，看懂了上面仔细阅读即可了解

void printResult(Pnode head)：输出结果

Code

#include<stdio.h>
#include<malloc.h>
typedef struct node {
    int coust;
    int power;
    struct node* next;
}Node, *Pnode;
Pnode createList(void);
Pnode copyList(Pnode head);
void add(Pnode head1, Pnode head2);
Pnode multi(Pnode head1, Pnode head2);
void printResult(Pnode head);
Pnode findEle(int power, Pnode head);
void insert(int * isInsert, Pnode head1, Pnode head2);
int main(void) {
    Pnode poly1 = createList();
    Pnode poly2 = createList();
    Pnode addPoly = copyList(poly1);

    Pnode multiPoly = multi(poly1, poly2);
    add(poly2, addPoly);
    printResult(multiPoly);
    printResult(addPoly);
    return 0;
}
Pnode createList(void) {
    Pnode temp = 0;
    Pnode head = temp = (Pnode)malloc(sizeof(Node));
    head->power = 9999;
    int length;
    scanf("%d",&length);
    head->coust = length;
    for (int i = 0; i < length; i++) {
        temp->next = (Pnode)malloc(sizeof(Node));
        temp =  temp->next;
        scanf("%d %d",&temp->coust, &temp->power);
        temp->next = 0;
    }
    return head;
}
Pnode copyList(Pnode head) {
    Pnode tempOfHead = head;
    Pnode tempOfHead1 = 0;
    Pnode head1 = tempOfHead1 = (Pnode)malloc(sizeof(Node));
    head1->power = head->power;
    int length = head1->coust = head->coust;
    for (int i = 0; i < length; i++) {
        tempOfHead1->next = (Pnode)malloc(sizeof(Node));
        tempOfHead1 = tempOfHead1->next;
        tempOfHead = tempOfHead->next;
        tempOfHead1->coust = tempOfHead->coust;
        tempOfHead1->power = tempOfHead->power;
        tempOfHead1->next = 0;
    }
    return head1;
}
void add(Pnode head1, Pnode head2) {
    Pnode temp1 = head1->next;
    Pnode temp2 = head2;
    Pnode temp = 0;
    int isInsert = 0;
    for (;temp1 != 0;) {
        temp2 = findEle(temp1->power, temp2);
        insert(&isInsert, temp1, temp2);
        if (isInsert == 1) {
            head2->coust++;
        }
        else if (isInsert == -1) {
            head2->coust--;
        }
        temp1 = temp1->next;
    }
}
Pnode multi(Pnode head1, Pnode head2) {
    Pnode temp1 = head1;
    Pnode temp2 = head2;
    Pnode multi = (Pnode)malloc(sizeof(Node));
    Pnode temp3 = 0;
    Pnode temp = 0;
    multi->coust = 0;
    multi->next = 0;
    multi->power = 9999;
    if (head1->coust == 0 || head2->coust == 0) {
        return multi;
    }
    else {
        temp1 = head1->next;
        //temp2 = head2->next;
        int isInsert = 0;
        for (; temp1 != 0; temp1 = temp1->next) {
            temp2 = head2->next;
            temp3 = multi;
            for (; temp2 != 0; temp2 = temp2->next) {
                temp = (Pnode)malloc(sizeof(Node));
                temp->power = temp1->power + temp2->power;
                temp->coust = temp1->coust * temp2->coust;
                temp->next = 0;
                temp3 = findEle(temp->power, temp3);
                insert(&isInsert, temp, temp3);
                if (isInsert == 1)
                    multi->coust++;
                else if (isInsert == -1)
                    multi->coust--;
                free(temp);
            }
        }
    }
    return multi;
}
void printResult(Pnode head) {
    if (head->coust == 0) {
        printf("%d %d", 0, 0);
    }else
    {
        Pnode  temp = head->next;
        printf("%d %d", temp->coust, temp->power);
        temp = temp->next;
        for (;temp != 0; temp = temp->next) {
            if (temp->coust == 0) {
                continue;
            }else {
                printf(" %d %d", temp->coust, temp->power);
            }
        }
    }
    printf("\n");
}
Pnode findEle(int power, Pnode head) {
    Pnode temp = head;
    for (; temp!= 0;) {
        if (temp->power == power || temp->next == 0) {
            return temp;
        }
        else {
            if(temp->next->power >= power)
                temp = temp->next;
            else
                return temp;
        }
    }
    return temp;
}
void insert(int * isInsert, Pnode head1, Pnode head2) {
    if (head2->power == head1->power) {
        head2->coust += head1->coust;
        if (head2->coust == 0) {
            *isInsert = -1;
            //if(head2->next != 0)
                //head2->next = head2->next->next;
            
            return;
        }
        *isInsert = 0;
    }else {
            Pnode temp = (Pnode)malloc(sizeof(Node));
            temp->coust = head1->coust;
            temp->power = head1->power;
            temp->next = head2->next;
            head2->next = temp;
            *isInsert = 1;      
    }
}

Summary

 总体感觉还是有些难度的，主要难点在于findEle中，因为有几种寻找方式，不同的寻找方式会导致insert操作会有所不同
 而且有些查找方式不能很好的照顾到边界情况，例如在第一个节点前面插入一个节点，最后一个节点后面插入一个节点，或者不同的终止条件会造成可能不能遍历最后一个节点等等,如果不仔细想好合适的查找方式，很容易不能照顾到边界情况
 还要说一点，还是要多考虑极限情况才能比较顺畅的答题，否则很容易陷入打补丁式的编写