polynomial.cpp

一个我的数据结构解题集合

#include <iostream>
#include "Polynomial.h"

using namespace std;


/* 本多项式加上项e
 */
void Polynomial::add(Term e) {

	// 找出多项式中首个系数大于等于项e的项的前一项
	SList<Term>::Itor itor = list_.head();			// 注意: 此处的itor始终指向想要访问的
													//		 项的前一项
	for ( ; ( itor != list_.tail() ) &&
			( (itor->next->data).compareTo(e) < 0 );
		  itor=itor->next)
		;	// 空循环体

	if ( itor == list_.tail() ||
		 (itor->next->data).compareTo(e) > 0 ) {	// 指数相等的项本来不存在
		list_.insertAfter(itor, e);
	} else {										// 找到指数相等的项
		(itor->next->data).coef += e.coef;
		if ( (itor->next->data).coef == 0 )
			list_.removeNext(itor);
	}

} // add(Term e)


/* 本多项式乘以项e
 */
void Polynomial::mul(Term e) {
	SList<Term>::Itor itor = list_.head();			// 注意: 此处的itor始终指向想要访问的
													//		 项的前一项
	for ( ; itor != list_.tail(); itor=itor->next) {

		(itor->next->data).coef *= e.coef;			// 系数相乘
		if ( (itor->next->data).coef == 0 )
			list_.removeNext(itor);

		(itor->next->data).expn += e.expn;			// 指数相加
	}

} // mul(Term e)


/* 本多项式加上多项式rhs
 */
void Polynomial::add(const Polynomial& rhs) {
	SList<Term>::Itor ilhs = list_.head(),
					  irhs = rhs.list_.head();		// 注意: 此处的litor和ritor
													//		 始终指向想要访问的项的前一项

	while ( ilhs != list_.tail() &&
			irhs != rhs.list_.tail() ) {
		int cmp = (ilhs->next->data).compareTo(irhs->next->data);	// 比较两个项指数大小

		if ( cmp > 0 ) {								// ilhs所指项的后一项指数大
			list_.insertAfter(ilhs, irhs->next->data);
			ilhs=ilhs->next;
			irhs=irhs->next;
		} else
		if ( cmp == 0 ) {								// ilhs和irhs所指项的后一项指数相等
			(ilhs->next->data).coef += (irhs->next->data).coef;
			if (ilhs->next->data.coef == 0) {
				list_.removeNext(ilhs);
			} else {
				ilhs=ilhs->next;
			}

			irhs=irhs->next;
		} else {										// ilhs所指项的后一项指数小
			ilhs=ilhs->next;							// 不是不加, 时候未到
		}
	}

	while ( irhs != rhs.list_.tail() ) {				// 加入剩余结点
		list_.insertAfter(list_.tail(), irhs->next->data);
		irhs=irhs->next;
	}


} // add(const Polynomial&)


/* 本多项式减去多项式rhs
 */
void Polynomial::sub(const Polynomial& rhs) {
	SList<Term>::Itor ilhs = list_.head(),
					  irhs = rhs.list_.head();		// 注意: 此处的litor和ritor
													//		 始终指向想要访问的项的前一项

	while ( ilhs != list_.tail() &&
			irhs != rhs.list_.tail() ) {
		int cmp = (ilhs->next->data).compareTo(irhs->next->data);	// 比较两个项指数大小

		if ( cmp > 0 ) {								// ilhs所指项的后一项指数大
			Term e = irhs->next->data;
			e.coef = -e.coef;

			list_.insertAfter(ilhs, e);

			ilhs=ilhs->next;
			irhs=irhs->next;
		} else
		if ( cmp == 0 ) {								// ilhs和irhs所指项的后一项指数相等
			(ilhs->next->data).coef -= (irhs->next->data).coef;
			if (ilhs->next->data.coef == 0) {
				list_.removeNext(ilhs);
			} else {
				ilhs=ilhs->next;
			}

			irhs=irhs->next;
		} else {										// ilhs所指项的后一项指数小
			ilhs=ilhs->next;							// 不是不减, 时候未到
		}
	}

	while ( irhs != rhs.list_.tail() ) {				// 加入剩余结点
		Term e = irhs->next->data;
		e.coef = -e.coef;

		list_.insertAfter(list_.tail(), e);
		irhs=irhs->next;
	}

} // sub(const Polynomial&)


/* 本多项式乘以多项式rhs
 */
void Polynomial::mul(const Polynomial& rhs) {
	Polynomial result, temp;
	SList<Term>::Itor itor = rhs.list_.begin();			// 注意: 此处的itor始终指向想要访问的
														//		 项本身
	for ( ; itor != rhs.list_.end(); itor=itor->next) {
		temp = *this;
		temp.mul(itor->data);
		result.add(temp);
	}

	*this = result;

} // mul(const Polynomial&)


/* 在cout打印一元多项式
 */
void Polynomial::print() const {

	SList<Term>::Itor itor = list_.begin();

	cout << itor->data.coef;
	if ( itor->data.expn != 0 )
		cout << " * x^(" << itor->data.expn << ")";
	itor = itor->next;

	for ( ; itor != list_.end(); itor=itor->next) {
		if ( itor->data.coef >= 0 )
			cout << " + " << itor->data.coef;
		else
			cout << " - " << -(itor->data).coef;

		if ( itor->data.expn != 0 )
			cout << " * x^(" << itor->data.expn << ")";
	}
	cout << endl;
} // print() const