2606 - 多项式相加
一条单链表可以表示一个一元多项式，每个节点包含三个域：指数、系数和后继节点（指针或引用）。
表示多项式3X4-6X2+5X-10的单链表如图所示。给定两个多项式，实现两个多项式相加算法。
题目输入
第一行输入包含两个整数m,n
后续为m行和n行数据
m，n分别代表两个多项式的项数
后续每一行代表多项式的项，包含a,b两个数据，表示该项的系数和指数。
题目输出
从较高指数到较低指数，依次输出求得的和。
每行一项，格式与输入相同，但无需输出项数，系数为0的项也不输出。
输入/输出样例
题目输入
2 3 1 2 1 1 2 2 1 1 2 0
题目输出
3 2 2 1 2 0
C++解答
#include <stdio.h> #include <malloc.h> typedef struct LNode { int data; //系数 int index; //指数 struct LNode *next; } LNode; void init(LNode *&L, int data, int index) { LNode *s, *p, *q; s = L; p = L -> next; q = (LNode *) malloc(sizeof(LNode)); q -> next = NULL; q -> data = data; q -> index = index; if (p) { int subIndex; while (p) { subIndex = q -> index - p -> index; if (subIndex > 0) { q -> next = p; s -> next = q; break; } if (subIndex == 0) { p -> data += q -> data; //系数相加,指数不变 free(q); break; } s = p; p = p -> next; } if (p == NULL) { q -> next = p; s -> next = q; } } else { q -> next = p; s -> next = q; } } void output(LNode *L) { LNode *p; p = L -> next; while (p) { if (p -> data != 0) { printf("%d %d\n", p -> data, p -> index); } p = p -> next; } } int main() { int i; int m, n; int data, index; LNode *L; L = (LNode *) malloc(sizeof(LNode)); L -> next = NULL; scanf("%d %d", &m, &n); for (i = 1; i <= m+n; ++i) { fflush(stdin); scanf("%d %d", &data, &index); if (data != 0) { //系数不为0时，才插入链表 init(L, data, index); } } output(L); return 0; }