数据结构——多项式相乘

超、凢脫俗 2022-12-24 11:51 385阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h> 
    #define LEN sizeof(Poly)
    typedef struct term{
        
        float coef;        
        int expn;        
        struct term *next;
    }Poly,*Link;
    int LocateElem(Link p, Link s, Link &q); 
    void CreatePolyn(Link &p,int m);    
    void PrintPolyn(Link p);                        
    int cmp(Link a, Link b);
    Link Reverse(Link p);                
    Link MultiplyPolyn(Link A,Link B);    
    void Calculate(Link p,float x); 
           
    int LocateElem(Link p, Link s, Link &q){
        
        Link p1 = p->next;
        Link p2 = p;
        while(p1){
        
            if(s->expn > p1->expn){
        
                p1 = p1->next;
                p2 = p2->next;
            }else if(s->expn == p1->expn){
        
                q = p1; 
                return 1;
            }
    		else{
        
                q = p2;
                return 0;
            }
        }
        if(!p1){
        
            q = p2;
            return 0;
        }
    }
    
    void CreatePolyn(Link &p,int m) 
    {
        
        Link s,q;
        int i;
        p=(Link)malloc(LEN);
        p->next=NULL;
        for(i=0;i<m;i++)
        {
        
            s=(Link)malloc(LEN);
            printf("输入系数和指数（以空格隔开）:");
            scanf("%f %d", &s->coef, &s->expn);
            if(!LocateElem(p, s, q)){
            
                s->next = q->next;
                q->next = s;
            }else{
                                                       
                q->coef+=s->coef;
            }
        }
    }
    
    void PrintPolyn(Link p)
    {
        
        Link s;
        s = p->next;
        while(s)
        {
        
                printf(" %.2f X^%d", s->coef, s->expn);
                s = s->next;
                if(s!=NULL)  
                    if(s->coef>=0) printf(" +");               
        }
        printf("\n");
    }
    Link Reverse(Link p)
    {
        
        Link head=p; 
        Link q1,q2;
        q2=head->next;
        head->next=NULL;
        while(q2)
        {
        
            q1=q2;      
            q2=q2->next; 
            q1->next=head->next; 
            head->next=q1;  
        }      
        return head;
    }
    Link MultiplyPolyn(Link A,Link B)
    {
        
      Link pa,pb,pc,s,head;
      int k,maxExpn,minExpn;
      float coef;
      head=(Link)malloc(LEN);
      head->next=NULL;
      if(A->next!=NULL&&B->next!=NULL){
        
          minExpn=A->next->expn+B->next->expn;  
         A=Reverse(A); 
        B=Reverse(B);
          maxExpn=A->next->expn+B->next->expn; 
      }
      else{
        
              return head;
      }       
       pc=head;
       B=Reverse(B);
    for(k = maxExpn;k>=minExpn;k--){
                      
               pa = A->next;
               while(pa !=NULL&&pa->expn>k){
         
                   pa = pa->next;
               }
               pb = B->next;
               while(pb!=NULL&&pa!=NULL&&pa->expn+pb->expn<k){
        
                   pb = pb->next;
               }
            coef=0.0;
            while(pa!=NULL&&pb!=NULL){
        
                if(pa->expn+pb->expn==k){
          
                    coef+=pa->coef*pb->coef;
                    pa=pa->next;
                    pb=pb->next;
                }
                else if(pa->expn+pb->expn>k){
        
                    pa = pa->next;
                }
                else{
        
                        pb = pb->next;
                }    
            }
            if(coef!=0.0){
        
                s=(Link)malloc(LEN);
                s->coef=coef;
                s->expn=k;
                s->next=pc->next;
                pc->next=s;
                pc=s;
            }
       }
       B = Reverse(B);
       head=Reverse(head);
       return head;    
    }
    
    int main()
    {
        
        Link P1,P2,P3;    
        int L1,L2;       
        printf("请输入第一个多项式的项数：");
        scanf("%d",&L1);
        CreatePolyn(P1,L1);
        printf("第一个多项式为：");
        printf("P1(X)=");
        PrintPolyn(P1);
        printf("请输入第二个多项式的项数：");
        scanf("%d",&L2);
        CreatePolyn(P2,L2);
        printf("第二个多项式为：");
        printf("P2(X)=");
        PrintPolyn(P2); 
        printf("\n");
      printf("两个一元多项式相乘：   ");
                 printf("P1(X)*P2(X)=");
                 P3=MultiplyPolyn(P1, P2);
                PrintPolyn(P3);
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]: /images/20221120/21d102942db44ea29ed9771e8f4a6359.png