博客

题目描述：

思路：

一开始
我的想法是用一个顺
序表来
存储
多项式
，然后进行运算。
但
后来发现
顺序表
适用于
稠
密多
项式
，对于
稀
疏多项式
(即相邻
项的幂相差很大
)
来说时间就不可接受了
。
那怎么解决
这个问题呢？
那就是用一个链表
。
利用链表的特性可以直接
跳过
中间那些系数为0的项，从而大大节省时间。
相加操作的执行有一点归并排序的思想。即利用两个指针的移动，来判断当前哪个指针指向的项的幂大，幂大的就添加到sum求和多项式里，若幂相同则将系数相加再添加到sum求和多项式里(需要注意若系数相加后为0，则应该将此项的幂也变为0，即零多项式应输出 0 0)。

完整代码如下：

#include typedef struct Node  {    int coef;    //项的系数    int exp;     //项的幂    struct Node *next;} PolyTerm;PolyTerm *Createpoly(PolyTerm *L, int m) //创建一个m项多项式{    PolyTerm *p;    L = (PolyTerm *)malloc(sizeof(PolyTerm));    L->next = NULL;    p = L;    for (int i = 1; i <= m; i++)    {        PolyTerm *tmp = (PolyTerm *)malloc(sizeof(PolyTerm));        scanf("%d%d", &tmp->coef, &tmp->exp);        p->next = tmp;        p = p->next;    }    p->next = NULL; //最后表尾指向空    return L;}void InsertPoly(PolyTerm *L, PolyTerm *x) //将x插入L表尾{    while (L->next != NULL)        L = L->next;    PolyTerm *tmp;    tmp = (PolyTerm *)malloc(sizeof(PolyTerm));        tmp->coef = x->coef;    if(x->coef==0)    tmp->exp=0;    else    tmp->exp = x->exp;    L->next = tmp;    tmp->next = NULL;}void AddPoly(PolyTerm *L1, PolyTerm *L2, PolyTerm *sum){    while (L1 != NULL && L2 != NULL)    {        if (L1->exp > L2->exp)        {            InsertPoly(sum, L1);            L1 = L1->next;        }        else        {            if (L1->exp < L2->exp)            {                InsertPoly(sum, L2);                L2 = L2->next;            }            else //若进入此else 代表L2幂与L1幂相同            {                L1->coef = L1->coef + L2->coef;                InsertPoly(sum, L1);                L1 = L1->next;                L2 = L2->next;            }        }    }    //若L1或L2有剩余，则将剩余项全部加到sum表末尾    if(L1!=NULL)        {        while(L1!=NULL)        {            InsertPoly(sum,L1);            L1=L1->next;        }    }    if(L2!=NULL)    {        while(L2!=NULL)        {            InsertPoly(sum,L2);            L2=L2->next;        }    }}int main(){    int m, n;    PolyTerm *L1, *L2, *sum, *head;    scanf("%d", &m);    L1 = Createpoly(L1, m);    scanf("%d", &n);    L2 = Createpoly(L2, n);    sum = (PolyTerm *)malloc(sizeof(PolyTerm));    head = sum;    sum->next = NULL;    AddPoly(L1->next, L2->next, sum);    int first = 1;    while (head->next != NULL)    {        if (first)        {            printf("%d %d", head->next->coef, head->next->exp);            first = 0;        }        else        {            printf(" %d %d", head->next->coef, head->next->exp);        }        head = head->next;    }}

此算法的时间复杂度为O(M*N)。