This time, you are supposed to find A+B where A and B are two polynomials.
Input
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:K N1 aN1 N2 aN2 ... NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10，0 <= NK < ... < N2 < N1 <=1000.
Output
For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.
Sample Input
2 1 2.4 0 3.2 2 2 1.5 1 0.5Sample Output
3 2 1.5 1 2.9 0 3.2
这是甲级第二题，刚来没摸清水深。。。。吐。。。重写链表真的想吐，其实大可不必想我这样做，因为最近在复习DS，所以很自然的把多项式那里全部都写了一遍，在写的时候有几个点，收获很大，之前的许多问题也解决了。我记得我以前只有代码一变长，函数一多，又手贱想加指针，我的指针就会出很多问题，，无奈脸.jpg，如果你也经常遇到指针乱指，或者局部指针释放后内存中混乱的问题，这里会有一些解决办法。
简单的算法可以参加其他大牛的算法，推荐柳婼学姐的。。坏笑.gif。
想说的是，最后在多项式相加时，addPoly中，当*p指向A，*q指向B。只要任意一个多项式没有了，就可以将有剩余的那个多项式直接贴在后面。。。哦哦，但是这里需要算长度，我当时没想到更好的方法。只有采用我的insert函数，一方面可以加长度，一方面可以加入元素。
但还需注意的是，在打印时，如果系数为0 则不打印，而且实际长度也会发生变化。刚开始的方法太菜，直接遍历两边，很蠢。。。勿喷。。。其实比较正规的方法是在insert的时候，判断coeff是否为0，不为0则不插。
#include<stdio.h> //#include<> struct node{ node* next; int expo; double coeff; }; struct polynomials{ node *first; int length; polynomials(){ node* f=new node; f->next=NULL; first=f; length=0; } void printPoly(); void insertNode(node* ai); void addPoly(polynomials B); }; void polynomials::printPoly(){ node* p=first->next; printf("%d",length); p=first->next; //int firstw=1; while(p){ if(p->coeff) printf(" %d %.1lf",p->expo,p->coeff); p=p->next; } } void polynomials::insertNode(node* ai){ node* p=first; node* q=new node; q->expo=ai->expo;q->coeff=ai->coeff;q->next=NULL; while(p->next) p=p->next; q->next=p->next; p->next=q; length++; } void polynomials::addPoly(polynomials B){ node* p=first->next;node* q=B.first->next; polynomials C; node* k=C.first; while(p && q){ if(p->expo > q->expo){ if(p->coeff){ C.insertNode(p); k=k->next; } p=p->next; } else if(p->expo < q->expo) { if(q->coeff){ C.insertNode(q); k=k->next; } q=q->next; } else{ node* plusNode=new node;plusNode->expo=p->expo; plusNode->coeff=p->coeff+q->coeff; if(plusNode->coeff){ k=k->next; C.insertNode(plusNode); } q=q->next;p=p->next; } } if(p) { while(p){ if(p->coeff) C.insertNode(p);p=p->next; } } else{ while(q){ if(q->coeff) C.insertNode(q);q=q->next; } } C.printPoly(); } int main() { int Num; polynomials A,B; scanf("%d",&Num); node* tempnode=new node; for(int j=0;j<Num;j++){ scanf("%d %lf",&tempnode->expo,&tempnode->coeff); A.insertNode(tempnode); } // A.printPoly(); scanf("%d",&Num); for(int j=0;j<Num;j++){ scanf("%d %lf",&tempnode->expo,&tempnode->coeff); B.insertNode(tempnode); } A.addPoly(B); return 0; }
