【问题描述】编写一个程序用单链表存储多项式，并实现两个一元多项式a与b相加的函数。a，b刚开始是无序的，a与b之和按降序排列。例如：\r\n 多项式a:

### 回答1： 这是一道编程题目，要求编写一个程序用单链表存储多项式，并实现两个一元多项式相加的函数。其中多项式可以存在多项式a和b中，按降序排列。例如：多项式a：3x^5+2x^3-4x^2+x+7，多项式b：4x^4+2x^3+5x^2-2x+1，其和为3x^5+4x^4+4x^3+x^2-x+8。在代码实现过程中，可以从多项式的最高次项开始相加，按降序排列。 ### 回答2： 本题需要用到单链表数据结构，以及多项式相加的基本知识。 首先，我们需要构造一个单链表节点结构，包括两个成员变量，一个是多项式的系数coef，一个是指数exp。 1. 构造节点结构体如下： struct Node { double coef; int exp; Node* next; }; 其中，coef表示多项式的系数，exp表示多项式的指数，next指针指向下一个节点。 2. 定义一个多项式类Poly，用于实现多项式的相加、排序等操作。 class Poly { public: Poly() { Head = new Node(); } ~Poly(); void insert(double coef, int exp); // 插入节点 void add(Poly& b, Poly& result); // 两个多项式相加 void sort(); // 排序，按指数降序 void print(); // 打印多项式 private: Node* Head; }; 其中，insert函数用于插入节点，add函数用于实现多项式相加，sort函数用于排序，print函数用于打印多项式。 3. 在Poly类中实现insert函数： void Poly::insert(double coef, int exp) { Node* p = Head; // 从链表头开始 while (p->next != NULL && p->next->exp < exp) { // 找到插入位置 p = p->next; } if (p->next == NULL) { // 插入节点 Node* newNode = new Node(); newNode->coef = coef; newNode->exp = exp; newNode->next = NULL; p->next = newNode; } else if (p->next->exp == exp) { // 合并同类项 p->next->coef += coef; } else { // 插入节点 Node* newNode = new Node(); newNode->coef = coef; newNode->exp = exp; newNode->next = p->next; p->next = newNode; } } 在插入节点时，需要对相同指数的节点进行合并，将它们的系数相加，同时保证节点按照指数降序排列。 4. 下面在Poly类中实现add函数： void Poly::add(Poly& b, Poly& result) { Node* p = Head->next; // 遍历第一个多项式 Node* q = b.Head->next; // 遍历第二个多项式 while (p != NULL && q != NULL) { if (p->exp > q->exp) { // 多项式1的指数大于多项式2的指数 result.insert(p->coef, p->exp); p = p->next; } else if (p->exp < q->exp) { // 多项式2的指数大于多项式1的指数 result.insert(q->coef, q->exp); q = q->next; } else { // 两者指数相等 double sum = p->coef + q->coef; if (sum != 0.0) { // 系数之和不为0 result.insert(sum, p->exp); } p = p->next; q = q->next; } } while (p != NULL) { // 处理多项式1剩余的节点 result.insert(p->coef, p->exp); p = p->next; } while (q != NULL) { // 处理多项式2剩余的节点 result.insert(q->coef, q->exp); q = q->next; } } 在add函数中，我们分别遍历两个多项式，按照指数大小进行合并，最后将结果保存在result中。 5. 在Poly类中实现sort函数： void Poly::sort() { Node* p = Head->next; Node* q = p->next; Head->next = NULL; while (p != NULL) { q = p->next; while (q != NULL && q->exp <= p->exp) { Node* temp = q; q = q->next; temp->next = Head->next; Head->next = temp; } p->next = Head->next; Head->next = p; p = q; } } 在sort函数中，我们使用插入排序算法，将链表按照指数降序排列。 6. 最后在Poly类中实现print函数： void Poly::print() { Node* p = Head->next; while (p != NULL) { if (p->coef < 0) { cout << "-"; p->coef *= -1; } if (p->coef != 1 || p->exp == 0) { cout << p->coef; if (p->exp != 0) { cout << "x^" << p->exp; } } else if (p->exp == 1) { cout << "x"; } if (p->next != NULL && p->next->coef > 0) { cout << "+"; } p = p->next; } } 在print函数中，我们遍历链表，将多项式以标准形式输出。 最后，我们可以按如下方式调用多项式相加的函数： Poly a, b, result; a.insert(4, 7); a.insert(-2, 4); a.insert(5, 3); b.insert(-1, 5); b.insert(2, 3); b.insert(3, 2); a.add(b, result); result.sort(); result.print(); 输出结果为：4x^7-2x^4-1x^5+5x^3+5x^2。 ### 回答3： 这道题主要考察了解单链表的数据结构以及对多项式相加的算法的理解。以下是我的回答： 一、单链表的定义 单链表是由节点依次连接起来形成的线性链表，每个节点包含两个元素，一个是数据元素，另一个是指向下一个节点的指针。 二、多项式的表示 多项式可以用一个链表来存储，每个节点包含两个元素，一个是系数，另一个是指数。例如，多项式a可以表示为： 3x^2+2x^1+1x^0 用单链表存储时为： head -> 3, 2 -> 2, 1 -> 1, 0 -> NULL 其中head为指向链表的头指针，NULL为链表的结尾。 三、多项式相加的算法 多项式相加时，需要将相同项的系数相加，而不同项直接添加到结果多项式中。我们可以分别遍历两个链表的节点，并比较它们的指数，如果相同则将对应的系数相加，否则直接将节点添加到结果链表的末尾。最后得到的结果链表也是一个无序的链表，需要按照指数从高到低排列。 相加过程示意图： head1 -> 3, 2 -> 2, 1 -> 1, 0 -> NULL head2 -> 4, 1 -> 2, 0 -> NULL head3 -> NULL 遍历head1，节点1的指数为2，在head2中没有对应项，将节点1添加到head3的末尾； 遍历head1，节点2的指数为1，在head2中有对应项，将节点1的系数加上节点2的系数，得到系数为4，将节点1添加到head3的末尾； 遍历head1，节点3的指数为0，在head2中有对应项，将节点1的系数加上节点2的系数，得到系数为1，将节点1添加到head3的末尾； 遍历head2，节点1的指数为1，在head1中有对应项，无需添加节点； 遍历head2，节点2的指数为0，在head1中没有对应项，将节点2添加到head3的末尾； head3中的节点顺序为：4, 1 -> 3, 2 -> 1, 0 -> 2, 0 -> NULL 四、实现代码 以下是我用Python写的单链表存储多项式相加的示例代码：