#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct Node
{
float coef;//系数
int expo;//指数
};
typedef struct Polynomial//多项式结构体
{
struct Node element;
struct Polynomial *next;
}Polynomial,*PLink;

//typedef struct Polynomial Polynomial;
//typedef struct Polynomial *PLink;
typedef PLink Polynode;//为了自己写着方便的一系列坑爹货

void initial(Polynode p)//初始化链表
{
Polynode p1;
p1=p;
while(p1)
{
p1->next=NULL;
p1=p1->next;
}
p=p1;
}

int judgeSame(Polynode p1,Polynode p2)//判断两项中的指数是否相等
{
Polynode p;
p=p1->next;

while(p!=NULL && p->element.expo != p2->element.expo)
p=p->next;
if(p==NULL)
return 0;
return 1;//指数相同返回1，否则返回0

}

void createPolynomial(Polynode p)//建立链表储存多项式
{
int i=0,n=0;
Polynode p2,setPo;

if(p!=NULL)
{
initial(p); //初始化
}

printf("请输入要创建的项数：");
scanf("%d",&n);

for(i=1;i<=n;i++)
{
setPo = (Polynode)malloc(sizeof(Polynomial));
initial(setPo);
printf("请输入第%d项的指数：",i);
scanf("%d",&setPo->element.expo);

if(setPo->element.expo<0)//指数为负数时提示错误
{
printf("你的输入有误，指数不能为负数，请重新输入！\n");
scanf("%d",&setPo->element.expo);
}

printf("请输入第%d项的系数：",i);
scanf("%f",&setPo->element.coef);

while(p->next!=NULL && p->next->element.expo > setPo->element.expo)
p=p->next;
p2=p->next;

if(!judgeSame(p,setPo))//判断新输入的项是否已经存在
{
/*    while(p)
        p=p->next;
        */
p->next=setPo;
setPo->next=p2;
}
else
{
printf("您输入的多项已经存在，请重新输入！\n");
createPolynomial(p);
break;
}
}

}
void Output(Polynode p)//输出加法运算后的链表
{
p=p->next;

while(p!=NULL)
{
printf("%.1fX^%d",p->element.coef,p->element.expo);
p=p->next;
if(p!=NULL)
if(p->element.coef > 0)
{
printf(" + ");//这样结尾处就没有加号了
}
}
}

void Attach(float c,int e,Polynode p)//将一个链表链入另一个链表
{
Polynode x;
x = (Polynode)malloc(sizeof(Polynomial));

x->element.expo = e;
x->element.coef = c;
p->next = x;
}

void addPoly(Polynode p1,Polynode p2,Polynode p)
{
Polynode temp;
temp = (Polynode)malloc(sizeof(Polynomial));
temp=p;
p1=p1->next;
p2=p2->next;

while(p1!=NULL && p2!=NULL)
{
if(p1->element.expo > p2->element.expo)
{
Attach(p1->element.coef,p1->element.expo,temp);
p1=p1->next;
temp=temp->next;
}
else if(p1->element.expo < p2->element.expo)
{
Attach(p2->element.coef,p2->element.expo,temp);
p2=p2->next;
temp=temp->next;
}
else
{
p1->element.coef = p1->element.coef + p2->element.coef;

if(p1->element.coef!=0)
{
temp->next=p1;
p1=p1->next;
p2=p2->next;
temp=temp->next;
}
}
}
while(p1!=NULL)//将剩余的p1全部链入p
{
Attach(p1->element.coef,p1->element.expo,temp);
p1=p1->next;
temp=temp->next;
}
while(p2!=NULL)//将剩余的p2全部链入p
{
Attach(p2->element.coef,p2->element.expo,temp);
p2=p2->next;
temp=temp->next;
}
p=temp;
p->next=NULL;//不然结尾处还有个加号，而且会崩
}

void subPoly(Polynode p1,Polynode p2,Polynode p)//多项式的减法，p=p1-p2
{
Polynode temp,pd;
temp = (Polynode)malloc(sizeof(Polynomial));
pd = (Polynode)malloc(sizeof(Polynomial));
temp=p;
p2=p2->next;
p1=p1->next;

while(p1!=NULL && p2!=NULL)
{
if(p1->element.expo > p2->element.expo)
{
Attach(p1->element.coef,p1->element.expo,temp);
p1=p1->next;
temp=temp->next;
}
else if(p1->element.expo < p2->element.expo)
{
Attach(-(p2->element.coef),p2->element.expo,temp);//被减数的系数要取反
p2=p2->next;
temp=temp->next;
}
else
{
p1->element.coef = p1->element.coef - p2->element.coef;

if(p1->element.coef!=0)
{
Attach(p1->element.coef,p1->element.expo,temp);
p1=p1->next;
p2=p2->next;
temp=temp->next;
}
else
{
pd->next=p1;//如果这一项系数为零，则删除此节点
pd=p1->next;
p1=p1->next;
p2=p2->next;

}
}
}
while(p1!=NULL)//将剩余的p1全部链入p
{
Attach(p1->element.coef,p1->element.expo,temp);
p1=p1->next;
temp=temp->next;
}
while(p2!=NULL)//将剩余的p2全部链入p,且要反转系数
{
p2->element.coef =0 -(p2->element.coef);
Attach(p2->element.coef,p2->element.expo,temp);
p2=p2->next;
temp=temp->next;
}
p=temp;
p->next=NULL;//不然结尾处还有个加号，而且会崩
}

void menu()
{
int i;

printf("                                                                               \n");
printf("++++++++++++++++++++++++++++++++++O(∩_∩)O~+++++++++++++++++++++++++++++++++++\n");
printf("+                                                                             +\n");
printf("+                          一元多项式的加减法运算                             +\n");
printf("+                                                                             +\n");
printf("+                                                                             +\n");
printf("+                                1.加法运算                                   +\n");
printf("+                                                                             +\n");
printf("+                                2.减法运算                                   +\n");
printf("+                                                                             +\n");
printf("+                                3.退出系统                                   +\n");
printf("+                                                                             +\n");
printf("+                                                                             +\n");
printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
}

int main()
{
Polynode p;
Polynode L,sum,subp;
int c;

p=(Polynode)malloc(sizeof(Polynomial));
L=(Polynode)malloc(sizeof(Polynomial));
sum =(Polynode)malloc(sizeof(Polynomial));
subp=(Polynode)malloc(sizeof(Polynomial));

menu();
printf("选择功能：");
scanf("%d",&c);
switch(c)
{
case 1:
createPolynomial(p);
printf("您输入的多项式为：");
Output(p);
printf("\n");

createPolynomial(L);
printf("您输入的多项式为：");
Output(L);
printf("\n");

printf("多项式相加之和为：");
addPoly(p,L,sum);
Output(sum);
printf("\n");
break;
case 2:
createPolynomial(p);
printf("您输入的多项式为：");
Output(p);
printf("\n");

createPolynomial(L);
printf("您输入的多项式为：");
Output(L);
printf("\n");

printf("多项式相减之和为：");
subPoly(p,L,subp);
Output(subp);
printf("\n");
break;
case 3:
exit(0);
break;
}

return 0;
}