PTA（顺序表）2-7 运用顺序表实现多项式相加

2-7 运用顺序表实现多项式相加

分数 7

作者 胡艳梅

单位 成都理工大学

本题要求输入两个一元多项式，然后输出它们的和（相加后得到的一元多项式）

输入格式:

输入一个整数n（表示输入组数），然后依次输入每一组数据：
输入一个整数A（表示多项式的项数，小于100），然后输入A对整数，每一对整数表示对应项的指数和系数。

输出格式:

对每一组输入，在一行中输出得到的一元多项式。

输入样例:

在这里给出一组输入。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
5
0 2
1 4
5 7
7 10
8 19
4
0 3
2 6
4 19
5 -9
3
0 3
4 7
8 2
3
0 -3
5 9
7 21

输出样例:

在这里给出相应的输出。例如：

1
2
5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^8
7x^4+9x^5+21x^7+2x^8

答案

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
#include <iostream>
using namespace std;

// 定义多项式项的结构体：指数+系数
typedef struct {
    int exp;  // 指数
    int coeff; // 系数
} PolyTerm;

// 定义顺序表结构
typedef struct {
    PolyTerm *data;
    int length;
} sqList;

void initList(sqList &L, int n) {
    L.data = new PolyTerm[n];
    L.length = 0;
}

// 将x插入到表尾部
void insertELem(sqList &L, int exp, int coeff) {
    L.data[L.length].exp = exp;
    L.data[L.length].coeff = coeff;
    L.length++;
}

// 将两个多项式相加
void addPoly(sqList L1, sqList L2, sqList &L) {
    int i = 0;
    int j = 0;

    while (i != L1.length && j != L2.length) { // 只要有一个指针走完就结束
        // 系数小的就进新的地方
        if (L1.data[i].exp < L2.data[j].exp) { // L1的当前指数小
            insertELem(L, L1.data[i].exp, L1.data[i].coeff);
            i++; // 指针向后
        } else if (L1.data[i].exp > L2.data[j].exp) { // L2的当前指数小
            insertELem(L, L2.data[j].exp, L2.data[j].coeff);
            j++; // 指针向后
        } else if (L1.data[i].exp == L2.data[j].exp) { // 指数相同
            if (L1.data[i].coeff + L2.data[j].coeff != 0) { // 看是否抵消
                insertELem(L, L1.data[i].exp, L1.data[i].coeff + L2.data[j].coeff);
                i++;
                j++;
            } else {
                i++;
                j++;
            }
        }
    }
    // 处理L1遍历完了
    while (L2.length != j) {
        insertELem(L, L2.data[j].exp, L2.data[j].coeff);
        j++;
    }
    // 处理L2遍历完了
    while (L1.length != i) {
        insertELem(L, L1.data[i].exp, L1.data[i].coeff);
        i++;
    }
}

int main() {
    int n, A;
    cin >> n;
    while (n--) { // 循环n次

        // 输入第一个多项式
        cin >> A; // 读取输入的整数对数
        sqList L1;
        initList(L1, A);

        int exp, coeff; // exp指数    coeff系数
        for (int i = 0; i < A; ++i) {
            cin >> exp >> coeff;
            L1.data[i].exp = exp;
            L1.data[i].coeff = coeff;
            L1.length++;
        }

        // 输入第二个多项式
        int B;
        cin >> B; // 读取输入的整数对数
        sqList L2;
        initList(L2, B);

        for (int i = 0; i < B; ++i) {
            cin >> exp >> coeff;
            L2.data[i].exp = exp;
            L2.data[i].coeff = coeff;
            L2.length++;
        }

        // 合并两个多项式到新表中
        sqList L;
        initList(L, A+B);
        addPoly(L1, L2, L);
        // 输出新的顺序表
        for (int i = 0; i < L.length; ++i) {
            if (i != 0 && L.data[i].coeff > 0) {
                cout << "+";
            }
            cout << L.data[i].coeff << "x^" << L.data[i].exp;
        }
        if (n != 0) {
            cout << endl;
        }
    }
    
}
  1. 数据结构设计：
    • 使用结构体PolyTerm表示多项式的每一项，包含指数 (exp) 和系数 (coeff)
    • 使用顺序表sqList存储整个多项式，包含数据数组和长度信息
  2. 初始化与插入操作：
    • initList函数初始化顺序表，分配内存空间
    • insertELem函数用于在顺序表尾部插入新项
  3. 多项式相加核心算法：
    • 使用双指针法遍历两个多项式（i 指向 L1，j 指向 L2）
    • 比较当前指针所指项的指数：
      • 指数小的项先加入结果多项式
      • 指数相等的项系数相加，若和不为 0 则加入结果
    • 处理剩余项：当一个多项式遍历完后，将另一个多项式的剩余项加入结果
  4. 输入输出处理：
    • 读取测试组数 n，循环处理每组数据
    • 分别读取两个多项式的项数和各项的指数、系数
    • 调用相加函数得到结果多项式
    • 按照格式要求输出结果，注意系数为正时的 “+” 号处理
  5. 特殊情况处理：
    • 系数相加后为 0 的项不加入结果多项式
    • 输出时根据项的位置和系数符号控制 “+” 号的显示

这种思路利用顺序表的特性，通过双指针遍历实现了高效的多项式相加，时间复杂度为 O (m+n)，其中 m 和 n 分别是两个多项式的项数。