多项式相加

coding>C++
2k 词

题目描述

一条单链表可以表示一个一元多项式，每个节点包含三个域：指数、系数和后继节点（指针或引用）。

表示多项式3X4-6X2+5X-10的单链表如图所示。给定两个多项式，实现两个多项式相加算法。

输入

第一行输入包含两个整数m,n

后续为m行和n行数据

m，n分别代表两个多项式的项数

后续每一行代表多项式的项，包含a,b两个数据，表示该项的系数和指数。

输出

从较高指数到较低指数，依次输出求得的和。

每行一项，格式与输入相同，但无需输出项数，系数为0的项也不输出。

样例输入

1
2
3
4
5
6
2 3
1 2
1 1
2 2
1 1
2 0

样例输出

1
2
3
3 2
2 1
2 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
#include<bits/stdc++.h>
using namespace std;
typedef struct {
    double xs;
    double zs;
} Term;
typedef struct ploy
{
    Term term;
    ploy* next;
} ploy, * LinkList;
void Li(LinkList& L)
{
    L = (ploy*)malloc(sizeof(ploy));
    L->term.xs = 0.0;
    L->term.zs = -1;
    L->next = NULL;
}
int cmp(Term a, Term b)
{
    if (a.zs < b.zs) return 1;
    else if (a.zs == b.zs) return 0;
    else return -1;
}
void in(LinkList& L, Term e)
{
    ploy* q = L;
    while (q->next != NULL)
    {
        if (cmp(q->next->term, e) < 0)
            q = q->next;
        else break;
    }
    if (q->next != NULL && cmp(q->next->term, e) == 0)
    {
        q->next->term.xs += e.xs;
    }
    else
    {
        ploy* node = (ploy*)malloc(sizeof(ploy));
        node->term.xs = e.xs;
        node->term.zs = e.zs;
        if (q->next == NULL)
            node->next = NULL;
        else
            node->next = q->next;
        q->next = node;
    }
}
void CP(LinkList& L, int m)
{

    Term e;
    Li(L);
    for (int i = 1; i <= m; i++)
    {
        cin >> e.xs >> e.zs;
        in(L, e);
    }
}
void add(LinkList& L1, LinkList& L2)
{
    ploy* q;
    for (q = L2->next; q != NULL; q = q->next)
    {
        in(L1, q->term);
    }
    free(L2);
}
void SubtracatPolyn(LinkList& L1, LinkList& L2)
{
    ploy* q;
    for (q = L2->next; q != NULL; q = q->next)
    {
        q->term.xs = -(q->term.xs);
        in(L1, q->term);
    }
    free(L2);
}
void visitList(LinkList L)
{
    ploy* q = L;
    while (q->next != NULL)
    {
        q = q->next;
        if (q->term.xs != 0)
        {
            cout << q->term.xs << " " << q->term.zs << endl;
        }
    }
}
int main()
{
    LinkList L1, L2;
    int n1, n2;
    cin >> n1 >> n2;
    CP(L1, n1);
    CP(L2, n2);
    add(L1, L2);
    visitList(L1);
    return 0;
}