多项式相乘与相加

02-线性结构2 一元多项式的乘法与加法运算 (20分)
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分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

#include< stdio.h>
#include< stdlib.h>
typedef int  Elementtype;
typedef struct Node* Listnode;//链表节点
typedef struct Node* Headnode;//头节点
typedef struct Node{
    Elementtype Coefficient;//系数
    Elementtype Exponent;//指数
    struct Node* Next;
}Node;
Headnode Creat(Elementtype n)//创头节点
{
    Headnode head;
    Listnode p, q;
    q = p = head = (Headnode)malloc(sizeof(Node));
    head->Next = NULL;
    while (n--)
    {
        p = (Listnode)malloc(sizeof(Node));
        scanf("%d%d", &p->Coefficient, &p->Exponent);
        //尾插
        q->Next = p;
        q = p;
    }
    q->Next = NULL;
    return head;
}
Headnode Sum_List(Headnode list_f, Headnode list_s)
{
    Headnode Sum_head, hf, hs;
    Listnode rear, p;
    Elementtype temp;
    hf = list_f->Next;//带头节点的链表头部不放数据
    hs = list_s->Next;
    rear = Sum_head = Creat(0);
    //使用子函数
    while (hf && hs)
    {
        if (hs != NULL && hf != NULL)
        {
            if (hf->Exponent > hs->Exponent)
            {
                p = (Headnode)malloc(sizeof(Node));
                p->Exponent = hf->Exponent;
                p->Coefficient = hf->Coefficient;
                rear->Next = p;
                rear = p;
                hf = hf->Next;
            }
            else if (hf->Exponent < hs->Exponent)
            {
                p = (Headnode)malloc(sizeof(Node));
                p->Exponent = hs->Exponent;
                p->Coefficient = hs->Coefficient;
                rear->Next = p;
                rear = p;
                hs = hs->Next;
            }
            else
            {
                p = (Headnode)malloc(sizeof(Node));
                if (temp = hf->Coefficient + hs->Coefficient)
                {//temp用于存放系数，如果系数为0的话就跳过
                    p->Exponent = hf->Exponent;
                    p->Coefficient = temp;
                    rear->Next = p;
                    rear = p;
                }
                hf = hf->Next;
                hs = hs->Next;
            }
        }
    }
    rear->Next = NULL;
    if (hs)
        rear->Next = hs;//直接指向hs，千万别再创链表
    if (hf)
        rear->Next = hf;
    return Sum_head;
}
Headnode Mult_List(Headnode list_f, Headnode list_s)
{//乘法的话多次利用加法，因为列a中的数乘于列b，那么这个数列必定是有序的
    Headnode Mult_head, Z_head, hf, hs;
    Listnode rear, p;
    hf = list_f->Next;
    hs = list_s->Next;
    Mult_head = (Headnode)malloc(sizeof(Node));
    Mult_head->Next = NULL;//用于存放乘法结果
    if (hf && hs)
    {
        while (hf)
        {
            rear = Z_head = (Headnode)malloc(sizeof(Node));
            //用于存放列a的某个数乘以列b所得到的新数列
            Z_head->Next = NULL;
            while (hs)
            {
                p = (Headnode)malloc(sizeof(Node));
                p->Exponent = hf->Exponent + hs->Exponent;
                p->Coefficient = hf->Coefficient * hs->Coefficient;
                rear->Next = p;
                rear = p;
                hs = hs->Next;
            }
            hs = list_s->Next;
            hf = hf->Next;
            rear->Next = NULL;//NULL一定要补，要不导致Mult没有结尾
            Mult_head = Sum_List(Mult_head, Z_head);
            //需要给Mult_head这个链表结尾NULL
        }
    }
    return Mult_head;
}
void PrintList(Headnode L)
{
    Elementtype f = 0;
    Headnode p = L->Next;
    if (!p)//全0的数列
        printf("0 0");
    else
    while (p)
    {
        //可以借鉴下这个第一个数不输入空格的方法
        if (f)
            printf(" ");
        else
            f = 1;
        printf("%d %d", p->Coefficient, p->Exponent);
        p = p->Next;
    }
}
int main()
{
    Headnode Sum_head, Mult_head;
    Listnode List_f, List_s;
    Elementtype n;
    scanf("%d", &n);
    List_f = Creat(n);
    scanf("%d", &n);
    List_s = Creat(n);
    PrintList(Mult_List(List_f, List_s));
    printf("\n");
    PrintList(Sum_List(List_f, List_s));
    return 0;
}

总结

1.这道题虽然思路并不复杂，但是操作确实需要对链表足够熟练
2.解题的难点是乘法，我们如果暴力直接得到新乘法链表，那么是无序的非常麻烦，所以我们需要考虑构造出有序的小链表，因为题目所给的是有序指数链表，所以得到一个指数必定是有序的
3.同样可以用桶排序来做