多项式乘法（链表）

末蓝、 2022-05-27 12:09 237阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    typedef struct PolyNode
    {
        int coef;
        int exp;
        struct PolyNode *link;
    }* Polynomial;
    void Attach(int c,int e,Polynomial *pRear);//创建新的结点并插入
    Polynomial ReadPoly();//建立一条单链表
    Polynomial Mult(Polynomial p1,Polynomial p2);//多项式相乘
    void PrintPoly(Polynomial p);//遍历链表
    Polynomial Add(Polynomial p1,Polynomial p2);//多项式相加
    
    int main()
    {
        Polynomial p1,p2,pp,ps;
        p1 = ReadPoly();
        p2 = ReadPoly();
        pp =Mult(p1,p2);
        PrintPoly(pp);
        ps = Add(p1,p2);
        PrintPoly(ps);
    
        return 0;
    }
    void Attach(int c,int e,Polynomial *pRear)//指针的指针作为参数，可以改变实参
    {
        Polynomial p;
    
        p = (Polynomial)malloc(sizeof(struct PolyNode));
    
        p->coef = c;//对新节点赋值
        p->exp = e;
        p->link = NULL;
    
        (*pRear)->link = p;// 修改pRear的值
       * pRear = p;
    }
    Polynomial ReadPoly()//建立一条单链表
    {
        Polynomial Rear,p,t;
    
        int c,e,n;
        scanf("%d",&n);
        p = (Polynomial)malloc(sizeof(struct PolyNode));
        p->link = NULL;
        Rear = p;
    
        while(n--)
        {
            scanf("%d %d",&c,&e);
            Attach(c,e,&Rear);
    
        }
        t = p;
        p = p->link;
        free(t);
        return p;
    }
    
    Polynomial Mult(Polynomial p1,Polynomial p2)//多项式相乘
    {
        Polynomial p,t1,t2,Rear,t;
    
        int c,e;
    
        if(p1 == NULL || p2 == NULL)
            return NULL;
        t1 = p1;
        t2 = p2;
        p = (Polynomial)malloc(sizeof(struct PolyNode));
        p->link = NULL;
        Rear  = p;
        while(t2)
        {
            Attach(t1->coef*t2->coef,t1->exp + t2->exp,&Rear);
            t2 = t2->link;
        }
        t1 = t1->link;
    
        while(t1)
        {
            t2 = p2;
            Rear = p;
            while(t2)
            {
                e = t1->exp + t2->exp;
                c = t1->coef*t2->coef;
                while(Rear ->link && Rear->link->exp>e)
                    Rear = Rear->link;
                if(Rear->link && Rear ->link->exp == e)//指数相等，系数相加
                {
                    if(Rear->link->coef+c)
                        Rear->link->coef += c;
                    else
                    {
                        t = Rear->link;
                        Rear ->link = t->link;
                        free(t);
                    }
                }
                else
                {
                    t = (Polynomial)malloc(sizeof(struct PolyNode));
                    t->coef =c;
                    t->exp = e;
                    t->link = Rear->link;//插入结点之后，仍然保持顺序
                    Rear->link = t;
                    Rear = Rear->link;
                }
            }
            t1 = t1->link;
        }
        t2 = p;
        p = p->link;//释放头结点
        free(t2);
        return p;
    }
    
    void PrintPoly(Polynomial p)//遍历链表
    {
        int flag = 0;
        if(p == NULL)
        {
            printf("0 0\n");
            return ;
        }
        while(p)
        {
            if(flag == 0)
                flag =1;
            else
                printf(" ");
            printf("%d %d",p->coef,p->exp);
            p = p->link;
    
        }
        printf("\n");
    }
    
    Polynomial Add(Polynomial p1,Polynomial p2)//多项式相加
    {
        Polynomial t1,t2,p;
        t1 = p1->link;
        t2 = p2->link;
        p = (Polynomial)malloc(sizeof(struct PolyNode));
        p->link = NULL;
    
        while(t1 && t2)
        {
            Polynomial temp = (Polynomial)malloc(sizeof(struct PolyNode));
            temp->link =NULL;
            if(t1->exp == t2->exp)
            {
                if((t1->coef + t2->coef) == 0)
                {
                    t1=t1->link;
                    t2=t2->link;
                }
                else
                {
                    temp->coef = t1->coef +t2->coef;
                    temp->exp = t1->exp;
                    p->link = temp;
                    p = temp;
                    t1 = t1->link;
                    t2 = t2->link;
                }
            }
            else if(t1->exp > t2->exp)
            {
                temp->coef = t1->coef;
                temp->exp = t1->exp;
                p->link = temp;
                p = temp;
                t1 = t1->link;
            }
            else
            {
                temp->coef = t2->coef;
                temp->exp = t2->exp;
                p->link = temp;
                p = temp;
                t2 = t2->link;
            }
        }
        while(t1)
        {
            p->link = t1;
        }
    
        while(t2)
        {
            p->link = t2;
        }
        return p;
    }