PTA 算法2-9 一元多项式加法运算

算法2-9 一元多项式加法运算

分数 20

作者 陈越

单位 浙江大学

请编写程序，求两个多项式的和。

输入格式：

输入给出两个多项式的信息。对每个多项式，首先在一行中给出其非零项的个数 n，随后按指数递减的顺序给出 n 对 系数 指数，其中 系数 为实数，绝对值均不超过 1000，指数 为不超过 1000 的非负整数。注意：零多项式对应的 n 为 0。

输出格式：

按指数递减的顺序输出两个多项式的和的每个非零项，每项占一行，格式为 系数 指数，其中 系数 输出小数点后 2 位。注意：零多项式不输出任何内容。

输入样例：

1
2
3
4
3
9 12 15 8 3 2
4
26 19 -4 8 -13 6 82 0

输出样例：

1
2
3
4
5
6
26.00 19
9.00 12
11.00 8
-13.00 6
3.00 2
82.00 0

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <iomanip>

using namespace std;

// 定义链表结构：数据域中存放指数和系数，指针域放指向下一个结点的指针
typedef struct LNode {
    double coeff; // 系数
    int exp; // 指数
    struct LNode *next;
} LNode, *LinkList;

// 初始化链表，带头结点的链表
void initList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
}

// 尾插法插入到最后
void insertAtTail(LinkList &tail, double num1, int num2) {
    LNode *newNode = new LNode;
    newNode->coeff = num1;
    newNode->exp = num2;
    newNode->next = NULL; // 新节点是最后一个，next为NULL
    tail->next = newNode; // 插入到tail后面
    tail = newNode; // 更新tail指向新节点
}
void printResult(LinkList L) {
    LNode *p = L->next; // 用于遍历
    while (p != NULL) {
        cout << fixed << setprecision(2);
        cout << p->coeff << " " << p->exp << endl;
        p = p->next;
    }
}

// 计算两个多项式
LinkList add(LinkList L1, LinkList L2) {
    // 定义一个存放结果的链表
    LNode *result;
    initList(result);

    // 开始计算多项式
    LNode *p1 = L1->next; // 定义一个指针p1用于遍历链表1
    LNode *p2 = L2->next; // 定义一个指针p2用于遍历链表2
    LNode *rTail = result; // 定义一个存放结果链表的尾指针

    while (p1 != NULL && p2 != NULL) {
        if (p1->exp > p2->exp) { // 多项式1当前项指数大于多项式2的当前项
            insertAtTail(rTail, p1->coeff, p1->exp);
            p1 = p1->next;
        } else if (p2->exp > p1->exp) { // 多项式2当前项指数大于多项式1的当前项
            insertAtTail(rTail, p2->coeff, p2->exp);
            p2 = p2->next;
        } else if (p1->exp == p2->exp) { // 多项式1当前项指数等于多项式2的当前项
            if (p1->coeff + p2->coeff != 0) { // 合并系数不为0
                insertAtTail(rTail, p1->coeff + p2->coeff, p1->exp);
                // 遍历指针同时往后
                p1 = p1->next;
                p2 = p2->next;
            } else { // 系数合并之后为0，该项不不要了
                // 指针直接往后挪
                p1 = p1->next;
                p2 = p2->next;
            }
        }
    }
    if (p1 == NULL) { // p1遍历结束
        // 将第二个多项式剩余的添加到结果多项式
        while (p2 != NULL) {
            insertAtTail(rTail, p2->coeff, p2->exp);
            p2 = p2->next;
        }
    }
    if (p2 == NULL) { // p2遍历结束
        // 将第一个多项式剩余的添加到结果多项式
        while (p1 != NULL) {
            insertAtTail(rTail, p1->coeff, p1->exp);
            p1 = p1->next;
        }
    }
    return result; // 返回结果多项式
}

int main() {
    // 第一个多项式的链表
    LNode *L1; // 定义一个头指针
    initList(L1);
    int n;
    cin >> n; // 读取第一个多项式的项数
    double num1; // 用于存放读取的系数
    int num2; // 用于存放读取的指数
    LNode *tail1 = L1; // 定义一个尾指针，方便每次插入到尾部
    for (int i = 0; i < n; i++) {
        cin >> num1 >> num2;
        insertAtTail(tail1, num1,num2);
    }

    // 第二个多项式的链表
    LNode *L2; // 定义一个头指针
    initList(L2);
    cin >> n; // 读取第二个多项式的项数
    LNode *tail2 = L2; // 定义一个尾指针，方便每次插入到尾部
    for (int i = 0; i < n; i++) {
        cin >> num1 >> num2;
        insertAtTail(tail2, num1, num2);
    }

    // 调用函数计算两个多项式相加
    LinkList result = add(L1, L2);

    printResult(result);
}

Summary

本题是实现两个多项式的加法运算，采用带头结点的链表来存储多项式（每个节点存储一项的系数和指数），核心思路如下：

  1. 存储多项式：通过尾插法将输入的多项式项依次插入链表，保证链表中项按指数递减顺序存储（因为输入是按指数递减给出的，尾插法能保持顺序）。
  2. 多项式相加：同时遍历两个多项式链表，比较当前节点的指数：
    • 若指数不同，将指数大的项插入结果链表。
    • 若指数相同，合并系数（系数和不为 0 时插入结果链表）。
    • 处理完共同部分后，将剩余未遍历完的多项式的剩余项插入结果链表。
  3. 输出结果：遍历结果链表，按要求格式（系数保留 2 位小数）输出每一项的系数和指数。

之前出现的错误

  1. insertAtTail 函数实现错误：最初的 insertAtTail 实际是头插法（新节点插入在当前节点前面），导致链表元素顺序与输入顺序相反，指数无法保持递减，后续比较逻辑混乱。
  2. 尾指针初始化错误：
    • 如 tail1 初始化为 L1->next（初始为 NULL），rTail 初始化为 result->next（初始为 NULL），导致链表无法正确插入节点。
  3. 尾指针未随插入移动：插入新节点后，尾指针没有后移到新节点，使得后续插入仍在原地，链表结构混乱。
  4. 输出格式问题：仅使用 setprecision(2) 是设置有效数字位数，而非固定保留 2 位小数，需要结合 fixed 来实现固定小数位输出。