OJ刷题记录：一元多项式的运算 题目编号:463

#include <iostream>

using namespace std;

struct Node {
	int _coef;
	int _exp;
	Node* _next;
	Node(int coef, int exp):_coef(coef), _exp(exp), _next(NULL) {}
};

class Polynomial {
	public:
		Polynomial();
		~Polynomial();

	public:
		void Insert(int coef, int exp);
		void Print();
		Node* getHead();

	private:
		Node* head_;
		Node* rear_;
};

Polynomial::Polynomial() {
	head_ = new Node(0, 0);
	rear_ = head_;
}

Polynomial::~Polynomial() {
	Node* afterHead = NULL;

	for (Node* p = head_; p != NULL; p = afterHead) {
		afterHead = p->_next;
		delete p;
	}
}

void Polynomial::Insert(int coef, int exp) {
	Node* node = new Node(coef, exp);

	rear_->_next = node;
	rear_ = node;
}

void Polynomial::Print() {
	for (Node* p = head_->_next; p != NULL; p = p->_next) {
		cout << p->_coef << ' ' << p->_exp << endl;
	}
}

Node* Polynomial::getHead() {
	return head_;
}

void getResToA(Polynomial &A, Polynomial &B) {
	Node* previousA = A.getHead();
	Node* previousB = B.getHead();
	Node* pA = previousA->_next;
	Node* pB = previousB->_next;
	Node* temp = NULL;
	
	while (pA != NULL && pB != NULL) {
		if (pA->_exp < pB->_exp) {
			previousA = pA;
			pA = pA->_next;
		} else if (pA->_exp > pB->_exp) {
			temp = pB->_next;
			previousA->_next = pB;
			pB->_next = pA;
			previousA = pB;
			pB = temp;
			previousB->_next = pB;
		} else {
			pA->_coef = pA->_coef + pB->_coef;
			if (pA->_coef == 0) {
				previousA->_next = pA->_next;
				delete pA;
				pA = previousA->_next;
			} else {
				previousA = pA;
				pA = pA->_next; 
			}
			previousB->_next = pB->_next;
			delete pB;
			pB = previousB->_next;
		}
	}
	if (pB != NULL) previousA->_next = pB;
}

int main() {
	Polynomial A, B;
	char key;
	int coef, exp;

	while (cin >> key) {
		if (key == 'E') break;

		switch (key) {
			case 'A':
				while (true) {
					cin >> coef >> exp;
					if (coef == 0) break;
					A.Insert(coef, exp);
				}
				break;

			case 'B':
				while (true) {
					cin >> coef >> exp;
					if (coef == 0) break;
					B.Insert(coef, exp);
				}
				break;

			case 'C':
				getResToA(A, B);
				A.Print();
				break;
		}
	}

	return 0;
}