#include<stdio.h>
#include<stdlib.h>
#include<string.h>


typedef struct term{
    float coef;
    int    expn;
}ElemType;

typedef struct node{
    ElemType    data;
    struct    node *next;
}Node;

void PrintPolyn(Node *);
//创建一个含有m项的多项式，需要输入m次参数，每次输入两个参数：系数和指数, 且每次输入的指数不能相同
void CreatPolyn( Node *P, int m )
{
    int i;
    Node *current,*pre;
   
    P->next = NULL;
    pre = P;
   
    for( i = 0; i < m; i++ )
     {
        current = ( Node * )malloc( sizeof( Node ) );
        current->next = NULL;
        printf("输入第%d项的系数和指数，以空格隔开\n",i+1);
        scanf( "%f%d",&( current->data.coef ),&( current->data.expn) );
        if( i == 0 )
            P->next = current;  
        else
            pre->next = current;
        if(pre->data.expn == current->data.expn)
        {
            printf("ERROR:指数重复\n");
            exit(EXIT_FAILURE);
         }
        pre = current;  
    }
}

//计算多项式的长度，即项数
int PolynLength( Node * P )
{
    int count = 0 ;
    Node *current;

    current = P->next;
    while( current != NULL ){
        current = current->next;
        count++;
    }
    return count;
}

//冒泡法将多项式按升序排列，即幂次小的在前，幂次大的在后
void Increase( Node *P1)
{
    Node    *current;
    Node    *nex;
    Node    *pre;
    int count = PolynLength( P1 );
    int i,j;

    for( i = 1; i < count; i++ ){
        current = P1->next;
        pre = P1->next;
        for( j = 0; j < count - i; j++ ){
            nex = current->next;
            if( current->data.expn > nex->data.expn ){
                current->next = nex->next;
                nex->next= current;
                if( current ==  P1->next ){
                    P1->next = nex;
                    pre = P1->next;
                }
                else{
                    pre->next = nex;
                    pre = pre->next;
                }
            }
            else{
                pre = current;
                current = nex;
            }
        }
    }
}

/*
* 函数功能：将指定链表逆序
* 主要用于辅助除法运算
*/
Node reverse(Node *head)
{
    Node *p,*q,*t;
    p=NULL;
    q=head->next;
    while( q!=NULL ) {
        t=q->next;
        q->next =p;
        p=q;
        q=t;
    }
   
    head->next =p;
    return *head;
}

//将两个多项式相加，且相加后P1指向相加结果的头结点，释放P2
void AddPolyn( Node *P1, Node *P2 )
{
    Node *current1,*current2,*pre;
    Increase( P1 );
    Increase( P2 );
    current1 = P1->next;
    current2 = P2->next;
    pre = P1;
   
    while( current1 && current2 ){                                 //当两个多项式都没有达到末尾时
        if( current1->data.expn < current2->data.expn ){          //如果current1对应的指数小于current2对应的指数时
            if( current1 == P1->next && current2 == P2->next ){ //如果是第一个多项式的第一项的指数小于第二个多项式的第一项的指数
                P1->next = current1;                            //则current1也是相加后的多项式的第一项
            }                                                
            else{                                                //否则将current1添加到相加后的多项式的最后一项            
                pre->next = current1;                                
            }
            pre = current1;                                     //pre指向相加后的多项式的最后一项
            current1 = current1->next;                          //第一个多项式的current1指向当前项的后一项
        }
        else if( current1->data.expn == current2->data.expn ){  //如果current1对应的指数等于current2对应的指数时
            current1->data.coef += current2->data.coef;          //将两个多项式的系数相加赋给第一个多项式的对应项的系数
            if( current1 == P1->next && current2 == P2->next ){ //如果是第一个多项式的第一项的指数等于第二个多项式的第一项的指数
                P1->next = current1;                            //则current1也是相加后的多项式的第一项
            }
            else{                                
                pre->next = current1;                            //否则将current1添加到相加后的多项式的最后一项
            }
            pre = current1;                                        //pre指向相加后的多项式的最后一项
            current1 = current1->next;                            //第一个多项式的current1指向当前项的后一项
            current2 = current2->next;                            //第二个多项式的current2指向当前项的后一项
        }
        else{                                                    //如果current1对应的指数大于current2对应的指数时
            if( current2 == P2->next && current1 == P1->next){     //如果是第一个多项式的第一项的指数大于第二个多项式的第一项的指数
                P1->next = current2;                            //则current2也是相加后的多项式的第一项
            }
            else{                                                //否则将current2添加到相加后的多项式的最后一项
                pre->next = current2;
            }
            pre = current2;                                        //pre指向相加后的多项式的最后一项
            current2 = current2->next;                            //第二个多项式的current2指向当前项的后一项
        }
    }

    if( current1 )                                //如果第一个多项式的元素有剩余，则将第一个多项式剩余的元素连接在相加后的多项式链表的末尾
        pre->next = current1;
    else                                        //否则将第二个多项式剩余的元素连接在相加后的多项式链表的末尾
        pre->next = current2;
    P2->next = NULL;                             //释放P2

}

//将两个多项式相减，且相减后P1指向相减结果的头结点，释放P2
void SubtractPolyn( Node *P1, Node *P2 )
{

    Node *current1;
    Node *current2;
    Node *pre;
   
    Increase( P1 );
    Increase( P2 );
   
    current1 = P1->next;
    current2 = P2->next;
    pre = P1;

    while( current1 && current2 ){                                 //当两个多项式的current都非空时
        if( current1->data.expn < current2->data.expn ){        //如果第一个多项式的指数小于第二个多项式的指数
            if( current1 == P1->next && current2 == P2->next){     //如果是第一个多项式的第一项的指数小于第二个多项式的第一项的指数
                P1->next = current1;                            //则current1即为相减后的多项式的第一项
            }
            else{
                pre->next = current1;                            //否则将current1添加到相减后的多项式的最后一项
            }
            pre = current1;                                        //pre指向相减后的多项式的最后一项
            current1 = current1->next;                            //第一个多项式的current1指向当前项的后一项
        }
        else if( current1->data.expn == current2->data.expn ){  //如果第一个多项式的指数等于第二个多项式的指数
            current1->data.coef -= current2->data.coef;            //用第一个多项式的系数减去第二个多项式的系数结果赋给第一个多项式的对应项的系数
            if( current1 == P1->next && current2 == P2->next ){    //如果两个多项式的第一项的指数相等
                P1->next = current1;                            //则current1即为相减后的多项式的第一项
            }
            else{                                                //否则将current1添加到相减后的多项式的最后一项
                pre->next = current1;
            }
            pre = current1;                                        //pre指向相减后的多项式的最后一项
            current1 = current1->next;                            //第一个多项式的current1指向当前项的后一项
            current2 = current2->next;                            //第二个多项式的current2指向当前项的后一项
        }
        else{
            current2->data.coef = -current2->data.coef;           //如果第一个多项式的指数大于第二个多项式的指数
            if( current2 == P2->next && current1 == P1->next ){    //若第二个多项式的第一项的指数小于第一个多项式的第一项的指数
                P1->next = current2;                            //则current2即为相减后的多项式的第一项
            }
            else{                                                //否则将current1添加到相减后的多项式的最后一项
                pre->next = current2;                           
            }
            pre = current2;                                        //pre指向相减后的多项式的最后一项
            current2 = current2->next;                            //第二个多项式的current2指向当前项的后一项
        }
    }

    if( current1 )
        pre->next = current1;
    else{
        while( current2 ){
            current2->data.coef = -current2->data.coef;
            pre->next = current2;
            current2 = current2->next;
        }
    }
    P2->next = NULL;
}

//将两个多项式相乘，且相乘后P1指向相乘结果的头结点，释放P2
void MultiplyPolyn( Node *P1, Node *P2 )
{

    Node *current1,*current2,*temp,*current,*pre;
    current1 = P1->next;
    current2 = P2->next;
   
    temp = ( Node *)malloc( sizeof( Node ) );
    temp->next = NULL;

//1、用多项式1的第一个结点current1与多项式二的各个节点依次相乘，结果存放在以P1指向的结点为头结点的链表中，current1指向下一个结点
//2、用多项式1的current1与多项式二的各个节点依次相乘，结果存放在以temp指向的结点为头结点的链表中，current1指向下一个结点
//3、将以上两个链表相加
//4、循环重复步骤2和3直至current1指向下一个结点为空
    for( ; current1 != NULL; current1 = current1->next ){      
        for( current2 = P2->next; current2 != NULL; current2 = current2->next ){
            current = ( Node *)malloc( sizeof( Node ) );                    //创建一个新的多项式结点
            current->data.coef = current1->data.coef * current2->data.coef; //给该结点赋值，
            current->data.expn = current1->data.expn + current2->data.expn;
            current->next = NULL;
            if( current2 == P2->next ){
                if( current1 == P1->next ){
                    pre = P1;
                    P1->next = current;
                }
                else{
                    pre = temp;
                    temp->next = current;
                }
            }
            else{
                pre->next = current;
            }
            pre = current;
        }
        if( temp->next != NULL );
            AddPolyn( P1, temp );
    }
//    free( temp );
    temp->next = NULL;
    P2->next = NULL;
}


//将两个多项式相除，且相除后P1指向相除结果的头结点，释放P2
void DividePolyn(Node *P1, Node *P2)
{
    Node *temp1,*temp2,*consult,*p;
     Increase( P1 );
      reverse( P1 );
    Increase( P2 );
    reverse( P2 );
    consult = ( Node *)malloc( sizeof( Node ) );
    consult->next = NULL;
    p = ( Node *)malloc( sizeof( Node ) );
    p->next = NULL;
    //用被除数的指数最大的项除以除数指数最大的项，然后用这个商遍乘除数
    //然后被除数再减遍乘过后的那个积，差又是下一轮的被除数，如此直到最后被除数幂小于除数
    while(P1->data.expn>=P2->data.expn)
    {
        temp2=( Node* )malloc( sizeof(temp2) );
        temp1=( Node* )malloc( sizeof(Node) );
        temp1->data.coef=temp1->data.expn=0;
        temp1->next=NULL;
        temp2->data.coef=(P1->data.coef)/(P2->data.coef);
        temp2->data.expn=(P1->data.expn)-(P2->data.expn);
        AddPolyn(temp1,P2);                 //temp1是P2的一个拷贝，P2在此期间一直不变
        p=temp1->next;
        
        temp2->next=consult->next;
        consult->next=temp2;
        
        while(p!=NULL)   //除数的遍乘
        {
            p->data.coef*=temp2->data.coef;
            p->data.expn+=temp2->data.expn;
            p=p->next;
         }
        SubtractPolyn(P1,temp1);    //被除数减去遍乘后的积
        while(temp1->next!=NULL)
        {
            temp1->next=temp1->next->next;
            free(temp1->next);
        }
    }
    temp1=P1;
    temp2=P2;
    P1=consult;
    Increase( P1 );
    P2=temp1;
    Increase( P2 );
    while(temp2->next!=NULL)
        {
            temp2->next=temp2->next->next;
            free(temp2->next);
        }      
}

//打印多项式
void PrintPolyn(Node *P)
{
    int i;
    Node *p;
   
    p = P->next;
    for(i=1; i<=PolynLength(P); i++)
    {
        if(i==1)
        {
            if(p->data.coef!=1)
            printf("%g", p->data.coef);
        }   
        else
        {
            if(p->data.coef>0)
            {
                if(p->data.coef!=1)
                {
                    printf(" + ");
                    printf("%g", p->data.coef);
                }
                else
                {
                    printf(" + ");
                }
            }
            else if(p->data.coef<0)
            {
                if(p->data.coef!=-1)
                {
                    printf("%g", p->data.coef);
                }
                else
                {
                    printf(" - ");
                }
            }
            else printf("");               
        }
        if(p->data.expn)
        {
            printf("x");
            
            if(p->data.expn!=1)
                printf("^%d", p->data.expn);
        }
        p = p->next;
    }
    printf("\n");
}

main()  
{  
    Node *polyn1,*polyn2;  
    Node head1,head2;  
    polyn1 = &head1;  
    polyn2 = &head2;   
    int m, n, i,option;                                       
    printf("请选择要执行的选项:\n1 加法;\n2 减法;\n3 乘法;\n4 除法;\n5 退出\n");
    for(i=0;i!=-1;i++)
    {
        scanf("%d",&option);
        if(option==1){
            //创建第一个多项式
            printf("你的第一个多项式有几项?\n");
            scanf("%d",&m);
              CreatPolyn( polyn1, m );
              //创建第二个多项式
              printf("你的第二个多项式有几项?\n");
            scanf("%d",&n);
              CreatPolyn( polyn2, n );
              printf("两多项式相加结果为：\n");
            AddPolyn( polyn1, polyn2 );
            PrintPolyn( polyn1 );         
        }
        
        else if(option==2){
            //创建第一个多项式
            printf("你的第一个多项式有几项?\n");
            scanf("%d",&m);
              CreatPolyn( polyn1, m );
              //创建第二个多项式
              printf("你的第二个多项式有几项?\n");
            scanf("%d",&n);
              CreatPolyn( polyn2, n );
              printf("两多项式相减结果为：\n");
            SubtractPolyn(polyn1, polyn2);
            PrintPolyn(polyn1);         
        }
        else if(option==3){
            //创建第一个多项式
            printf("你的第一个多项式有几项?\n");
            scanf("%d",&m);
              CreatPolyn( polyn1, m );
              //创建第二个多项式
              printf("你的第二个多项式有几项?\n");
            scanf("%d",&n);
              CreatPolyn( polyn2, n );
              printf("两多项式相乘结果为：\n");
            MultiplyPolyn(polyn1, polyn2);
            PrintPolyn(polyn1);         
        }
        else if(option==4){
            //创建第一个多项式
            printf("你的第一个多项式有几项?\n");
            scanf("%d",&m);
              CreatPolyn( polyn1, m );
              //创建第二个多项式
              printf("你的第二个多项式有几项?\n");
            scanf("%d",&n);
              CreatPolyn( polyn2, n );
              printf("两多项式相除结果为：\n");
            DividePolyn(polyn1, polyn2);
            PrintPolyn(polyn1);
            printf("余数为：");
            PrintPolyn(polyn2);         
        }
        else if(option==5) break;
        else printf("选择错误\n");   
    }
}