浙大PAT甲級-1002
2414 ワード
この問題は大学1年生の時にやったもので、演算子を再ロードしたばかりです.今私が使っているのはチェーン時計で、忘れそうなデータ構造を復習しているのではないでしょうか.
#include
#include
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> 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;
}