用链表结构存儲多项式,求两个多项式A加B的和。要求在建立多项式链表时,总是按照指数从大到小顺序排列的。

算法步骤如下：

1.定义一个结构体PolyNode表示多项式，包含两个成员变量：系数coeff和指数exp，以及一个指向下一个多项式节点的指针next。

struct PolyNode {
int coeff;
int exp;
PolyNode *next;
};

2.定义一个函数createPoly()，用于创建多项式链表。该函数从键盘输入多项式的每一项，按照指数从大到小的顺序插入到链表中。如果指数重复，则将系数相加。

PolyNode *createPoly() {
PolyNode *head = new PolyNode(); // 创建头节点
head->next = NULL;
PolyNode *p = head; // 指向链表最后一个节点的指针
int n;
cin >> n; // 输入项数
while (n--) {
int coeff, exp;
cin >> coeff >> exp; // 输入系数和指数
// 在链表中查找指数为exp的项
PolyNode *q = head;
while (q->next && q->next->exp > exp) {
q = q->next;
}
if (q->next && q->next->exp == exp) {
// 指数相同，系数相加
q->next->coeff += coeff;
if (q->next->coeff == 0) {
// 系数为0，删除该节点
PolyNode *tmp = q->next;
q->next = q->next->next;
delete tmp;
}
} else {
// 插入新节点
PolyNode *tmp = new PolyNode();
tmp->coeff = coeff;
tmp->exp = exp;
tmp->next = q->next;
q->next = tmp;
}
}
return head;
}

3.定义一个函数addPoly()，用于将两个多项式相加。该函数创建一个新的多项式链表，并将两个多项式的每一项按照指数从大到小的顺序插入到链表中，如果指数重复，则将系数相加。

PolyNode *addPoly(PolyNode *A, PolyNode *B) {
PolyNode *C = new PolyNode(); // 创建头节点
C->next = NULL;
PolyNode *p = C; // 指向链表最后一个节点的指针
PolyNode *p1 = A->next, *p2 = B->next;
while (p1 && p2) {
if (p1->exp > p2->exp) {
// 将A的当前项插入到C中
PolyNode *tmp = new PolyNode();
tmp->coeff = p1->coeff;
tmp->exp = p1->exp;
tmp->next = p->next;
p->next = tmp;
p = p->next;
p1 = p1->next;
} else if (p1->exp < p2->exp) {
// 将B的当前项插入到C中
PolyNode *tmp = new PolyNode();
tmp->coeff = p2->coeff;
tmp->exp = p2->exp;
tmp->next = p->next;
p->next = tmp;
p = p->next;
p2 = p2->next;
} else {
// 指数相同，系数相加
int sum = p1->coeff + p2->coeff;
if (sum != 0) {
// 插入新节点
PolyNode *tmp = new PolyNode();
tmp->coeff = sum;
tmp->exp = p1->exp;
tmp->next = p->next;
p->next = tmp;
p = p->next;
}
p1 = p1->next;
p2 = p2->next;
}
}
// 将剩余项插入到C中
while (p1) {
PolyNode *tmp = new PolyNode();
tmp->coeff = p1->coeff;
tmp->exp = p1->exp;
tmp->next = p->next;
p->next = tmp;
p = p->next;
p1 = p1->next;
}
while (p2) {
PolyNode *tmp = new PolyNode();
tmp->coeff = p2->coeff;
tmp->exp = p2->exp;
tmp->next = p->next;
p->next = tmp;
p = p->next;
p2 = p2->next;
}
return C;
}

4.主函数中调用createPoly()函数分别创建A和B两个多项式链表，然后调用addPoly()函数求出它们的和C，并遍历C链表输出结果。

int main() {
PolyNode *A = createPoly();
PolyNode *B = createPoly();
PolyNode *C = addPoly(A, B);
PolyNode *p = C->next;
if (!p) {
cout << "0 0" << endl;
} else {
while (p) {
cout << p->coeff << " " << p->exp << " ";
p = p->next;
}
cout << endl;
}
return 0;
}