1467 数据结构：一元多项式加法

1467 数据结构：一元多项式加法

数据结构：一元多项式加法 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByteDescription

给定2个一元多项式，计算它们的和。例如：f(x)=5x3-3x2+1和g(x)=3x4+3x2+x，则h(x)=f(x)+g(x)=3x4+5x3+x+1。 Input 只有一个测试案例，输入包括2行。 第1行为多项式f(x)的项数n和n项的系数和次方（按照次方从大到小）。第2行为多项式g(x)的项数m和m项的系数和次方（按照次方从大到小）。 其中：0

AC代码：

#includetypedef struct term{ int coef; int expn; }term; typedef struct LNode { term data; struct LNode *next;}LNode,*Polynomial;int equal(int e1,int e2){ if(e1==e2) return 1; return 0; }int LocateElem(Polynomial p1,Polynomial r1,int (*cmp)(int,int)){ Polynomial q; q=p1->next; while(q) { if((*cmp)((q->data).expn,(r1->data).expn)) break; q=q->next; } if(q) { (q->data).coef=(r1->data).coef+(q->data).coef; return 1; } else return 0; }void Inpolyn(Polynomial &p,Polynomial &r){ Polynomial q; q=p; while(q->next&&(q->next->data).expn>(r->data).expn) q=q->next; r->next=q->next; q->next=r;}void CreatPolyn(Polynomial &p,int m){ p=(Polynomial)malloc(sizeof(LNode)); (p->data).coef=0; (p->data).expn=-1; p->next=NULL; Polynomial r,q; q=p; int i; for(i=1;i<=m;i++) { r=(Polynomial)malloc(sizeof(LNode)); scanf("%d%d",&(r->data).coef,&(r->data).expn); if(!LocateElem(p,r,equal)) Inpolyn(p,r); }}void AddPolyn(Polynomial &pa,Polynomial &pb,Polynomial &pc){ pc=(Polynomial)malloc(sizeof(LNode)); (pc->data).coef=0;(pc->data).expn=-1;pc->next=NULL; Polynomial p1,p2,p3,de; p1=pa->next; p2=pb->next; p3=pc; free(pa);free(pb); while(p1&&p2) { if((p1->data).expn==(p2->data).expn) { (p1->data).coef+=(p2->data).coef; if((p1->data).coef) { p3->next=p1; p3=p1; p1=p1->next; de=p2; p2=p2->next; free(de); } else { de=p1; p1=p1->next; free(de); de=p2; p2=p2->next; free(de); } } else if((p1->data).expn>(p2->data).expn) { p3->next=p1; p3=p1; p1=p1->next; } else { p3->next=p2; p3=p2; p2=p2->next; } } if(p1) p3->next=p1; if(p2) p3->next=p2;}int main(){ Polynomial ha,hb,hc,th; int t1,t2; scanf("%d",&t1); CreatPolyn(ha,t1); scanf("%d",&t2); CreatPolyn(hb,t2); AddPolyn(ha,hb,hc); th=hc->next; while(th->next) { printf("%d %d ",(th->data).coef,(th->data).expn); th=th->next; } printf("%d %d\n",(th->data).coef,(th->data).expn); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。