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

在使用链表结构储存多项式时，每个节点通常包含三个部分：系数、指数和指向下一个节点的指针。为了保持多项式的系数随着指数递减排序，我们可以设计一个自定义的链表节点类，比如`PolynomialNode`，它有如下的结构：

class PolynomialNode:
    def __init__(self, coefficient, exponent):
        self.coefficient = coefficient
        self.exponent = exponent
        self.next = None

然后，对于两个多项式A和B，我们需要创建它们各自的头结点`head_A`和`head_B`，并分别维护这两个链表。当我们需要求和两个多项式时，可以创建一个新的空链表`result_head`作为和的存储位置，并遍历两个链表：

1. 创建一个临时节点`temp`用于暂存计算结果，初始化为None。
2. 比较A和B当前节点的指数，选择较大的一个进行累加。如果它们的指数相同，则取两者的系数相加；否则，将较小的那个节点的值追加到结果链表中，并更新`temp`为较大的节点。
3. 然后移动较大的节点，直到其中一个链表结束。
4. 将剩余未添加的链表（如果有）的最后一个节点追加到`result_head`后面。

遍历结束后，`result_head`就是求和后的多项式的头节点。

相关问题

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

C++代码如下：

#include <iostream>
using namespace std;

struct Node {
    int coef; // 系数
    int exp;  // 指数
    Node* next;
    Node(int c, int e): coef(c), exp(e), next(nullptr) {}
};

class Polynomial {
public:
    Polynomial() {
        head = new Node(0, -1); // 头结点
    }

    void addTerm(int c, int e) {
        Node* cur = head;
        while (cur->next && cur->next->exp > e) {
            cur = cur->next;
        }
        if (cur->next && cur->next->exp == e) { // 合并同类项
            cur->next->coef += c;
            if (cur->next->coef == 0) { // 如果系数为0，删除该节点
                Node* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
        } else { // 插入新节点
            Node* newNode = new Node(c, e);
            newNode->next = cur->next;
            cur->next = newNode;
        }
    }

    void print() const {
        Node* cur = head->next;
        while (cur) {
            if (cur->coef > 0 && cur != head->next) {
                cout << "+"; // 正数打印“+”
            }
            cout << cur->coef;
            if (cur->exp > 0) {
                cout << "x";
                if (cur->exp > 1) {
                    cout << "^" << cur->exp;
                }
            }
            cur = cur->next;
        }
        cout << endl;
    }

    Polynomial operator+(const Polynomial& other) const {
        Polynomial res;
        Node* cur1 = head->next;
        Node* cur2 = other.head->next;
        while (cur1 || cur2) {
            if (!cur2 || (cur1 && cur1->exp > cur2->exp)) {
                res.addTerm(cur1->coef, cur1->exp);
                cur1 = cur1->next;
            } else if (!cur1 || (cur2 && cur1->exp < cur2->exp)) {
                res.addTerm(cur2->coef, cur2->exp);
                cur2 = cur2->next;
            } else {
                res.addTerm(cur1->coef + cur2->coef, cur1->exp);
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
        }
        return res;
    }

private:
    Node* head;
};

int main() {
    Polynomial A, B;
    A.addTerm(5, 3);
    A.addTerm(-2, 2);
    A.addTerm(4, 0);
    B.addTerm(3, 4);
    B.addTerm(1, 2);
    B.addTerm(-7, 0);
    cout << "A = ";
    A.print();
    cout << "B = ";
    B.print();
    Polynomial C = A + B;
    cout << "C = ";
    C.print();
    return 0;
}

输出结果：

A = 5x^3-2x^2+4
B = 3x^4+x^2-7
C = 3x^4+5x^3-x^2-3

C语言 用链表结构存储多项式，求两个多项式A加B的和 要求在建立多项式链表时，总是按照指数从大到小排列的

#include<stdio.h>
#include<stdlib.h>

// 定义多项式结点结构体
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef; // 系数
int expon; // 指数
Polynomial link; // 指向下一个结点的指针
};

// 函数声明
Polynomial ReadPoly(); // 读入多项式
Polynomial Add(Polynomial A, Polynomial B); // 多项式加法
void PrintPoly(Polynomial P); // 输出多项式

int main()
{
Polynomial A, B, S;
// 读入两个多项式
A = ReadPoly();
B = ReadPoly();
// 求和
S = Add(A, B);
// 输出结果
PrintPoly(S);
return 0;
}

// 读入多项式
Polynomial ReadPoly()
{
Polynomial P, rear, t;
int c, e;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
rear = P;
// 读入系数和指数，建立多项式链表
scanf("%d %d", &c, &e);
while (c != 0) {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c;
t->expon = e;
// 寻找合适的插入位置
while (rear->link && rear->link->expon > e) {
rear = rear->link;
}
// 插入结点
t->link = rear->link;
rear->link = t;
// 继续读入
scanf("%d %d", &c, &e);
}
return P;
}

// 多项式加法
Polynomial Add(Polynomial A, Polynomial B)
{
Polynomial P, rear, ta, tb, t;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
rear = P;
ta = A->link;
tb = B->link;
// 合并两个多项式
while (ta && tb) {
if (ta->expon > tb->expon) {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = ta->coef;
t->expon = ta->expon;
rear->link = t;
rear = t;
ta = ta->link;
} else if (ta->expon < tb->expon) {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = tb->coef;
t->expon = tb->expon;
rear->link = t;
rear = t;
tb = tb->link;
} else {
int sum = ta->coef + tb->coef;
if (sum != 0) {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = sum;
t->expon = ta->expon;
rear->link = t;
rear = t;
}
ta = ta->link;
tb = tb->link;
}
}
// 将剩余部分加入结果链表中
while (ta) {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = ta->coef;
t->expon = ta->expon;
rear->link = t;
rear = t;
ta = ta->link;
}
while (tb) {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = tb->coef;
t->expon = tb->expon;
rear->link = t;
rear = t;
tb = tb->link;
}
// 返回结果链表
rear->link = NULL;
return P;
}

// 输出多项式
void PrintPoly(Polynomial P)
{
if (!P->link) {
printf("0 0\n");
return;
}
while (P->link) {
printf("%d %d", P->link->coef, P->link->expon);
P = P->link;
if (P->link) {
printf(" ");
}
}
printf("\n");
}