qqq.cpp

数据结构C语言实现一元多项式运算

#include <STDIO.H>    
#include <STDLIB.H>    
#include <MALLOC.H>    
#include <CONIO.H>    
   
typedef struct node   
{   
    int coef;    
    int expn;    
    struct node * next;    
} PolyNode;   
   
PolyNode * Create_Poly(char ch) //输入    
{    
    PolyNode * p, *s,*r;   
    int x; int y;   
    p=(PolyNode *)malloc(sizeof(PolyNode));   
    p->next=NULL;   
    printf("输入多项式%c:(格式:系数 指数,指数递增,以0 0结束.)\n",ch);   
    scanf("%f %d",&x,&y);   
    while(x!=0)   
    {    
        s=(PolyNode *)malloc(sizeof(PolyNode));   
        s->coef=x;   
        s->expn=y;   
        s->next=NULL;   
        if(p->next==NULL)   
        {   
            p->next=s;   
            r=s;   
        }   
        else   
        {    
            r->next=s;   
            r=s;   
        }   
        scanf("%f %d",&x,&y);   
    }   
    return p;   
}   
   
PolyNode * Add_Poly(PolyNode * f,PolyNode * g)  //多项式相加    
{    
    PolyNode * fg;   
    PolyNode *t,*q,*s,*r;   
    float m;   
    t=f->next;   
    q=g->next;   
    fg=r=(PolyNode*)malloc(sizeof(PolyNode));   
    fg->next=NULL;   
    while(t&&q)   
    {    
        if(t->expn==q->expn)              //指数相等时系数相加    
        {    
            m=t->coef+q->coef;   
            if(m!=0)                        //系数为不0时加到结果中去    
            {   
                s=(PolyNode *)malloc(sizeof(PolyNode));   
                s->coef=m;   
                s->expn=t->expn;   
                s->next=NULL;                   
            }   
            t=t->next;   
            q=q->next;    
        }   
        else                                //指数小的加到结果中去再后移    
            if(t->expn<q->expn)                 
            {                  
                s=(PolyNode *)malloc(sizeof(PolyNode));   
                s->coef=t->coef;   
                s->expn=t->expn;   
                s->next=NULL;   
                t=t->next;    
            }   
            else    
            {   
                s=(PolyNode *)malloc(sizeof(PolyNode));   
                s->coef=q->coef;   
                s->expn=q->expn;   
                s->next=NULL;   
                q=q->next;   
            }   
   
        if(fg->next==NULL)   
        {    
            fg->next=s;   
            r=s;    
        }   
        else   
        {   
            r->next=s;   
            r=s;   
        }    
    }//while    
    r->next=t?t:q;                           //把没加完的接上    
    return fg;   
}   
   
   
void Out_Poly(PolyNode * f)                 //输入多项式    
{   
    PolyNode *t;   
    t=f->next;   
    if(!f->next){   
        printf("0\n");  return;   
    }   
    while(t)   
    {   if(t->coef>0&&f->next!=t) printf("+");   
        if(t->expn==0)   
            printf("%f",t->coef);   
        else   
            printf("%f*X^%d",t->coef,t->expn);   
        t=t->next;   
    }   
   printf("\n");   
}   
   
   
   
PolyNode * Mul_Poly(PolyNode *f,PolyNode *g)//多项式相乘    
{   
    PolyNode *h;   
    PolyNode *t,*q,*s,*r;   
    h=(PolyNode *)malloc(sizeof(PolyNode));   
    h->next=NULL;   
    r=(PolyNode *)malloc(sizeof(PolyNode));   
    r->next=NULL;   
    for(t=f->next;t;t=t->next)            //相乘时把第一项多项式的每一项    
    {                               //与第二个多项式中的每一项相乘    
        for(q=g->next;q;q=q->next)        //用双重循环实现    
        {   
            s=(PolyNode *)malloc(sizeof(PolyNode));   
            r->next=s;   
            s->coef=q->coef*t->coef;   
            s->expn=q->expn+t->expn;   
            s->next=NULL;   
            h=Add_Poly(r,h);            //把每项相乘结果加起来    
        }   
   
    }   
    return h;   
}   
   
void Open()                         //用户选择界面    
{   


  
    printf("1.相加\n");   
    printf("2.相乘\n");   
  
}   
   

   
void main()   
{   
    Open();   
    PolyNode * f,* g,* fg;   
    int i=-1;                               //设置标志    
    while(i!=0)    
    {   
        scanf("%d",&i);   
        getchar();   
        switch(i)   
        {      

        case 1:  // 相加  
 
            f=Create_Poly('A');             //输入多项式A    
            printf("A=");   
            Out_Poly(f);   
            g=Create_Poly('B');             //输入多项式B    
            printf("B=");   
            Out_Poly(g);   
            printf("A+B=");   
            fg=Add_Poly(f,g);   
            Out_Poly(fg);   
            i=-1;                           //复位标志    
            Open();                     //回复用户选择界面    
            break;   
        case 2:   //相乘
   
  
            f=Create_Poly('A');             //输入多项式A    
            printf("A=");   
            Out_Poly(f);   
            g=Create_Poly('B');             //输入多项式B    
            printf("B=");   
            Out_Poly(g);   
            printf("A*B=");   
            fg=Mul_Poly(f,g);   
            Out_Poly(fg);   
            i=-1;                           //复位标志    

            Open();                             //回复用户选择界面    
         
  
   
        }   
    }   
     
}