浙大PAT甲级-1002

这道题是大一的时候就做过的，当时刚学运算符重载。现在我用的是链表来做的，也算是复习一下快忘光的数据结构吧。

#include <iostream>
#include<iomanip>
using namespace std;

//节点（多项式的项）
struct listNode{
int exp;
double coe;
listNode *link;
listNode(){}
listNode(int e, double c){
exp = e;
coe = c;
link = NULL;
}
};

class list{
public:
listNode *first;
listNode *last;   //方便后面直接用就没设为private啦
list(){

first = NULL;
last = NULL;
}
//输入，初始化链表
void init(int n){
int e;
double c;
for (int i = 0; i<n; i++){
cin >> e >> c;
insert(e, c);
}
}
    //插入节点
void insert(int e, double c){
listNode *newNode = new listNode(e,c);
if (first == NULL){
newNode->link = first;
first =  newNode;
last = newNode;
}
else{
last->link = newNode;
last = newNode;
}
last->link = NULL;
}
//将系数为0的节点都剪掉
void merge(){
while (first!=NULL && first->coe == 0){
first = first->link;
}
if (first != NULL){
listNode *m = first->link;
listNode *n = first;
while (m != NULL){
if (m->coe == 0){
n->link = m->link;
}
else{
n = n->link;
}
m = m->link;
}
}
}
//链表长度
int Length(){
listNode *p = first;
int cnt = 0;
while (p != NULL){
p = p->link;
cnt++;
}
return cnt;
}
};
int main()
{
int p, q;
while (cin >> p){
list a, b, c;
a.init(p);
cin >> q;
b.init(q);

//多项式加法
listNode *ca = a.first;
listNode *cb = b.first;
while (ca != NULL&&cb != NULL){
if (ca->exp > cb->exp){
c.insert(ca->exp, ca->coe);
ca = ca->link;
}
else if (ca->exp == cb->exp){
c.insert(ca->exp, ca->coe + cb->coe);
ca = ca->link;
cb = cb->link;
}
else{
c.insert(cb->exp, cb->coe);
cb = cb->link;
}
}

if (ca != NULL){
while (ca != NULL){
c.insert(ca->exp, ca->coe);
ca = ca->link;
}
}
else if (cb != NULL){
while (cb != NULL){
c.insert(cb->exp, cb->coe);
cb = cb->link;
}
}

c.merge();
cout << c.Length();
listNode *m = c.first;
while (m != NULL){
cout << " " << m->exp << " " << setiosflags(ios::fixed)
<< setprecision(1) << m->coe;//输出是有精度要求的哦
m = m->link;
}
cout << endl;
}
return 0;
}