#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
 
#define LEN sizeof(node);
 
typedef struct polynode
{
    int coef;//系数
    int exp;//指数
    struct polynode *next;
}node,*ListPolynode;
 
/*倒序创建一元多项式*/
void createPoly(ListPolynode L,int n)
{
    ListPolynode p;
    for (int i=n;i>0;i--)
    {
        p=(ListPolynode)malloc(sizeof(node));
        printf("请输入第%d项系数\n",i);
        scanf_s("%d",&p->coef);
        printf("请输入第%d项指数\n",i);
        scanf_s("%d",&p->exp);
        p->next=L->next;
        L->next=p;
    }
}
/*正序创建一元多项式*/
ListPolynode createPoly1(ListPolynode L,int n)
{
    ListPolynode p;
    ListPolynode head=L;
    for (int i=0;i<n;i++)
    {
        p=(ListPolynode)malloc(sizeof(node));
        printf("请输入第%d项系数\n",i+1);
        scanf_s("%d",&p->coef);
        printf("请输入第%d项指数\n",i+1);
        scanf_s("%d",&p->exp);
        L->next=p;
        p->next=NULL;
        L=L->next;
    }
    return head;
}
/*打印一元多项式*/
void printfPoly(ListPolynode L)
{
    ListPolynode p=L->next;
    while(p)
    {
        printf("%d*x^%d ",p->coef,p->exp);
        p=p->next;
    }
    printf("\n");
}
 
/*多项式相加*/
void addPoly(ListPolynode La,ListPolynode Lb)
{
    ListPolynode currenLa=La->next;//指向La的当前结点
    ListPolynode currenLb=Lb->next;//指向Lb的当前结点
    ListPolynode temp;//待释放空间的临时结点
    ListPolynode pre=La;/*位置指针，指向和多项式La,利用pre修改La*/
    int sum;//相同指数结点系数之和
    while (currenLa!=NULL&&currenLb!=NULL)
    {
        if (currenLa->exp<currenLb->exp)//La的当前结点指小于于Lb的当前结点指数
        {
            //Lb的当前位置不变,La当前位置后移
            pre->next=currenLa;
            pre=pre->next;
            currenLa=currenLa->next;
        } 
        else if (currenLa->exp==currenLb->exp)//La的当前结点指数等于Lb的当前结点指数
        {
            sum=currenLa->coef+currenLb->coef;
            if (sum!=0)
            {
                //将La当前结点的系数改为sum,并链接到pre；将La的当前结点后移，之后过河拆桥将La的当前结点释放
                currenLa->coef=sum;
                pre->next=currenLa;
                pre=pre->next;
                currenLa=currenLa->next;
                temp=currenLb;
                currenLb=currenLb->next;
                free(temp);
            } 
            else
            {
                temp=currenLa->next;
                free(currenLa);//过河拆桥干掉La当前结点
                currenLa=temp;
 
                temp=currenLb->next;
                free(currenLb);//策略雷同，过河拆桥
                currenLb=temp;
            }
        }
        else//La的当前结点指数大于Lb的当前结点指数
        {
            //Lb当前位置添加到La当前位置之前，同时Lb向后移动一位，La向后移动一位
            pre->next=currenLb;
            pre=pre->next;
            currenLb=currenLb->next;
        }
    }
 
    if (currenLa!=NULL)//La未结束，将其全部链接到pre
    {
        pre->next=currenLa;
    }
    else//若Lb未结束，将其全部链接到pre
    {
        pre->next=currenLb;
    }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    ListPolynode La=(ListPolynode)malloc(sizeof(node));
    La->next=NULL;
    printf("请输入创建一元多项式的项数\n");
    int n;
    scanf_s("%d",&n);
    createPoly1(La,n);
    printfPoly(La);
 
    ListPolynode Lb=(ListPolynode)malloc(sizeof(node));
    Lb->next=NULL;
    printf("请输入创建一元多项式的项数\n");
    scanf_s("%d",&n);
    createPoly(Lb,n);
    printfPoly(Lb);
 
    addPoly(La,Lb);
    printfPoly(La);
 
 
 
    system("pause");
    return 0;
}