#include
#include
#include
//一元多项式相加
typedef int Status;
typedef struct Node{
float coef;
int expn;
struct Node *next;
}Node,*LinkList;
void CreatList(LinkList &P,int m)//按指数升序将元素依次插到第一个结点前，得到降序的表
{
void Insfirst(LinkList &P,LinkList &r);
LinkList h,r;
int i;
P=(LinkList)malloc(sizeof(Node));//建立头结点
if(!P)
P->next=NULL;P->expn=m;
h=P;
printf("按指数升序输入每一项的系数和指数：\n");
for(i=0;i<m;i++)
{
r=(LinkList)malloc(sizeof(Node)); //建立新的结点
printf("第%d项的系数和指数：",i+1);
scanf("%f%d",&r->coef,&r->expn); //将多项式的系数和指数存入
Insfirst(P,r); //将该结点插入到第一个结点之前
}
}
void Delfirst(LinkList &P,LinkList &q)//删除P指向的结点后的第一个结点
{
P->next=q->next;
}
void Insfirst(LinkList &P,LinkList &r)//在结点P之后紧接着插入一个结点
{
r->next=P->next;
P->next=r;
}
int cmp(int a,int b) //比较a和b大小
{
if(a<b)
return -1;
else if(a==b)
return 0;
else
return 1;
}
void Addpolyn(LinkList &Pa,LinkList &Pb)//多项式相加，结果保存在A(x)中，使按指数降序排列
{
LinkList ha,hb,qa,qb;
int m,n;
float sum=0;
ha=Pa;
hb=Pb; //ha，hb指向头结点
qa=ha->next;
qb=hb->next; //qa，qb指向Pa，Pb中的当前结点
while(qa&&qb) //当前结点非空
{
m=qa->expn;
n=qb->expn; //分别取Pa，Pb中当前结点的指数值保存在m，n中
switch(cmp(m,n))//比较指数大小
{
case 1: //m>n,Pa中当前结点指数大，不需要改变，ha、qa后移一位
ha=qa;
qa=qa->next;
break;
case 0: //m=n，指数相同需计算系数
sum=qa->coef+qb->coef; //计算系数和
if(sum!=0) //系数和不为零，改变qa的系数，Pa中的改变结束，ha更新（后移一位）
{
qa->coef=sum;
ha=qa;
}
else //系数和为零
{
Delfirst(ha,qa); //删除Pa中ha指向的结点后的第一个结点，即qa指向的结点，并释放
free(qa);
}
Delfirst(hb,qb);
free(qb); //删除并释放qb
qb=hb->next;
qa=ha->next; //重新获取qa、qb的地址
break;
case -1: //m<n，Pb中的指数大
Delfirst(hb,qb); //将该结点从Pb中删除
Insfirst(ha,qb); //将该结点连接在ha指向的结点之后
qb=hb->next; //更新qb的地址
break;
}//switch
}//while
if(Pb->next!=NULL) //Pb非空，链接Pb中剩余结点
ha->next=hb->next;
free(hb); //释放Pb的头结点
}
void Traversal(LinkList &L)//从第一个元素开始输出表中元素
{
LinkList p;
float a;
int b;
p=L->next; //p指向当前结点
while(p) //当p不是空的
{
a=p->coef;
b=p->expn;
printf("%f %d\t",a,b);//输出p中的系数和指数
p=p->next; //更新p值，p指向下一个结点
}
if(L->next!=NULL)
printf("\n");
}
int main()
{
LinkList Pa,Pb;
int m,n;
printf("输入多项式A(x)的项数：");
scanf("%d",&m);
CreatList(Pa,m); //建立第一个多项式
printf("输入多项式B(x)的项数：");
scanf("%d",&n);
CreatList(Pb,n); //建立第二个多项式
Addpolyn(Pa,Pb); //多项式相加
Traversal(Pa); //遍历操作，从表头开始输出多项式
return 0;
}
