1002. A+B for Polynomials (25)

时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue

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 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (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.5 Sample Output 3 2 1.5 1 2.9 0 3.2

链表版：

#include <stdlib.h>#include <stdio.h>struct Node;typedef struct Node* PtrNode;struct Node { float coefficient; int exponent; PtrNode next; int Num;};PtrNode Init(int N);PtrNode Sum(PtrNode A, PtrNode B);int main(){ PtrNode A, B, C; int N1,N2,N; scanf("%d", &N1); A=Init(N1); scanf("%d", &N2); B = Init(N2); C=Sum(A, B); printf("%d", C->Num); N = C->Num; if (C->next != NULL) { C = C->next; for (int i = 0; i < N; i++) { printf(" %d", C->exponent); printf(" %.1f", C->coefficient); C = C->next; } }    return 0;}PtrNode Init(int N){ PtrNode Head = (PtrNode)malloc(sizeof(struct Node)); PtrNode Tmp = Head; Head->coefficient = Head->exponent = -1; Head->Num = N; Head->next = NULL; for (int i = 0; i < N; i++) { PtrNode p = (PtrNode)malloc(sizeof(struct Node)); scanf("%d", &p->exponent); scanf("%f", &p->coefficient); p->next = NULL; Tmp->next = p; Tmp = p; } return Head;}PtrNode Sum(PtrNode A, PtrNode B){ A = A->next; B = B->next; PtrNode Head = (PtrNode)malloc(sizeof(struct Node)); Head->coefficient = -1; Head->exponent = -1; Head->next = NULL; Head->Num = 0; PtrNode tmp = Head; while (A != NULL && B != NULL) { if (A->exponent > B->exponent) { PtrNode p = (PtrNode)malloc(sizeof(struct Node)); p->coefficient = A->coefficient; p->exponent = A->exponent; p->next = NULL; tmp->next = p; tmp = p; A = A->next; Head->Num++; } else if (A->exponent < B->exponent) { PtrNode p = (PtrNode)malloc(sizeof(struct Node)); p->coefficient = B->coefficient; p->exponent = B->exponent; p->next = NULL; tmp->next = p; tmp = p; B = B->next; Head->Num++; } else { if (A->coefficient + B->coefficient != 0) { PtrNode p = (PtrNode)malloc(sizeof(struct Node)); p->coefficient = A->coefficient + B->coefficient; p->exponent = A->exponent; p->next = NULL; tmp->next = p; tmp = p; Head->Num++; } A = A->next; B = B->next; } } if (A == NULL && B != NULL) { while (B != NULL) { PtrNode p = (PtrNode)malloc(sizeof(struct Node)); p->coefficient = B->coefficient; p->exponent = B->exponent; p->next = NULL; tmp->next = p; tmp = p; B = B->next; Head->Num++; } } if (A != NULL &&B == NULL) { while (A != NULL) { PtrNode p = (PtrNode)malloc(sizeof(struct Node)); p->coefficient = A->coefficient; p->exponent = A->exponent; p->next = NULL; tmp->next = p; tmp = p; A = A->next; Head->Num++; } } return Head;}