Question

数据结构题目，求各位高手相助，感激不尽

利用顺序表或单链表实现两个一元多项式L1(x)和L2(x)相加，要求：
1.一元多项式的数据由键盘输入
2.要显示相加的两个一元多项式
3.要显示相加后的两个一元多项式

Answer 1

#include<stdio.h>
#include<stdlib.h>
typedef struct
{ float coef; //系数
int expn; //指数
}term;
typedef struct LNode
{ term data; //term多项式值
struct LNode *next;
}LNode,*LinkList;
typedef LinkList polynomail;
/*比较指数*/
int cmp(term a,term b)
{ if(a.expn>b.expn) return 1;
if(a.expn==b.expn) return 0;
if(a.expn<b.expn) return -1;
else exit(-2);
}
/*又小到大排列*/
void arrange1(polynomail pa)
{ polynomail h=pa,p,q,r;
if(pa==NULL) exit(-2);
for(p=pa;p->next!=NULL;p=p->next); r=p;
for(h=pa;h->next!=r;)//大的沉底
{ for(p=h;p->next!=r&&p!=r;p=p->next)
if(cmp(p->next->data,p->next->next->data)==1)
{ q=p->next->next;
p->next->next=q->next;
q->next=p->next;
p->next=q;
}
r=p;//r指向参与比较的最后一个，不断向前移动
} }
/*由大到小排序*/
void arrange2(polynomail pa)
{ polynomail h=pa,p,q,r;
if(pa==NULL) exit(-2);
for(p=pa;p->next!=NULL;p=p->next); r=p;
for(h=pa;h->next!=r;)//小的沉底
{ for(p=h;p->next!=r&&p!=r;p=p->next)
if(cmp(p->next->next->data,p->next->data)==1)
{ q=p->next->next;
p->next->next=q->next;
q->next=p->next;
p->next=q;
}
r=p;//r指向参与比较的最后一个，不断向前移动
} }
/*打印多项式,求项数*/
int printpolyn(polynomail P)
{ int i;
polynomail q;
if(P==NULL) printf("无项！\n");
else if(P->next==NULL) printf("Y=0\n");
else
{ printf("该多项式为Y=");q=P->next;i=1;
if(q->data.coef!=0&&q->data.expn!=0)
{ printf("%.2fX^%d",q->data.coef,q->data.expn); i++; }
if(q->data.expn==0&&q->data.coef!=0)
printf("%.2f",q->data.coef);//打印第一项
q=q->next;
if(q==NULL)
{printf("\n");return 1;}
while(1)//while中，打印剩下项中系数非零的项，
{ if(q->data.coef!=0&&q->data.expn!=0)
{ if(q->data.coef>0) printf("+");
printf("%.2fX^%d",q->data.coef,q->data.expn); i++;
}
if(q->data.expn==0&&q->data.coef!=0)
{ if(q->data.coef>0) printf("+");
printf("%f",q->data.coef);
}
q=q->next;
if(q==NULL)
{ printf("\n"); break; }
}
}
return 1;
}
/*1、创建并初始化多项式链表*/
polynomail creatpolyn(polynomail P,int m)
{ polynomail r,q,p,s,Q;
int i;
P=(LNode*)malloc(sizeof(LNode));
r=P;
for(i=0;i<m;i++)
{ s=(LNode*)malloc(sizeof(LNode));
printf("请输入第%d项的系数和指数：",i+1);
scanf("%f%d",&s->data.coef,&s->data.expn);
r->next=s; r=s;
}
r->next=NULL;
if(P->next->next!=NULL)
{ for(q=P->next;q!=NULL/*&&q->next!=NULL*/;q=q->next)//合并同类项
for(p=q->next,r=q;p!=NULL;)
if(q->data.expn==p->data.expn)
{ q->data.coef=q->data.coef+p->data.coef;
r->next=p->next;
Q=p;p=p->next;
free(Q);
}
else
{ r=r->next;
p=p->next;
}
}
return P;
}
/*2、两多项式相加*/
polynomail addpolyn(polynomail pa,polynomail pb)
{ polynomail s,newp,q,p,r;int j;
p=pa->next;q=pb->next;
newp=(LNode*)malloc(sizeof(LNode));
r=newp;
while(p&&q)
{ s=(LNode*)malloc(sizeof(LNode));
switch(cmp(p->data,q->data))
{case -1: s->data.coef=p->data.coef;
s->data.expn=p->data.expn;
r->next=s; r=s;
p=p->next;
break;
case 0: s->data.coef=p->data.coef+q->data.coef;
if(s->data.coef!=0.0)
{ s->data.expn=p->data.expn;
r->next=s;
r=s;
}
p=p->next;
q=q->next;
break;
case 1: s->data.coef=q->data.coef;
s->data.expn=q->data.expn;
r->next=s; r=s;
q=q->next;
break;
}//switch
}//while
while(p)
{ s=(LNode*)malloc(sizeof(LNode));
s->data.coef=p->data.coef;
s->data.expn=p->data.expn;
r->next=s; r=s;
p=p->next;
}
while(q)
{ s=(LNode*)malloc(sizeof(LNode));
s->data.coef=q->data.coef;
s->data.expn=q->data.expn;
r->next=s; r=s;
q=q->next;
}
r->next=NULL;
for(q=newp->next;q->next!=NULL;q=q->next)//合并同类项
for(p=q;p!=NULL&&p->next!=NULL;p=p->next)
if(q->data.expn==p->next->data.expn)
{ q->data.coef=q->data.coef+p->next->data.coef;
r=p->next;
p->next=p->next->next;
free(r);
}
printf("升序 1 , 降序 2\n");
printf("选择:");
scanf("%d",&j);
if(j==1) arrange1(newp);
else arrange2(newp);
return newp;
}
void main()
{ polynomail pa=NULL,pb=NULL;
polynomail p,q;
polynomail addp=NULL;
int n,m;
int sign='y';
printf("1、创建两个一元多项式\n");
printf("2、两多项式相加得一新多项式\n");
printf("3、退出\n");
printf("\n");
while(sign!='n')
{ printf("请选择：");
scanf("%d",&n);
switch(n)
{case 1:
if(pa!=NULL)
{ printf("已建立两个一元多项式，请选择其他操作！");
break;
}
printf("请输入第一个多项式：\n");
printf("要输入几项：");
scanf("%d",&m);
while(m==0)
{ printf("m不能为0，请重新输入m:");
scanf("%d",&m);
}
pa=creatpolyn(pa,m);
printpolyn(pa);
printf("请输入第二个多项式：\n");
printf("要输入几项：");
scanf("%d",&m);
pb=creatpolyn(pb,m);
printpolyn(pb);
break;
case 2:
if(pa==NULL)
{ printf("请先创建两个一元多项式！\n");
break;
}
addp=addpolyn(pa,pb);
printpolyn(addp);
break;
case 3:
if(addp!=NULL)
{ p=addp;
while(p!=NULL)
{ q=p;
p=p->next;
free(q);
}
}
if(subp!=NULL)
{ p=subp;
while(p!=NULL)
{ q=p;
p=p->next;
free(q);
}
}
exit(-2);
}//switch
}//while
}