main.cpp

多项式乘法

#include <iostream>
using namespace std;

template <class Type> class List; // 单链表类
template <class Type> class ListItr;// 单链表迭代器类

/* 节点类 
 * 包含数据域和指针场
 */
template <class Type>
class ListNode
{
	friend class List <Type>;
	friend class ListItr<Type>;

	private :
		ListNode <Type> *Next;// 指针场
		Type Element;// 数据域
	public:
		ListNode (const Type &E, ListNode <Type> *N = NULL)
			:Element (E), Next(N){}// 构造函数
		ListNode (): Next(NULL){}// 默认构造函数
		~ListNode (){}// 析构函数
};

/* 单链表类 */
template <class Type>
class List
{
	friend class ListItr <Type>;

	private:
		ListNode <Type> *head;// 头指针
	public:
		List() {head = new ListNode <Type> ();}//构造函数
		~List() {MakeEmpty(); delete head;}// 析构函数

		const List& operator = (const List& R);// 重载等号运算符
		int IsEmpty () const {return head->Next == NULL;} //判断是否为空
		void MakeEmpty();// 清空链表
};

template <class Type>
void List<Type>::MakeEmpty()
{
	ListNode <Type> *Ptr;
	ListNode <Type> *NextNode;
	for (Ptr = head->Next; Ptr != NULL; Ptr = NextNode)//从头遍历一次
	{
		NextNode = Ptr->Next;
		delete Ptr;//删除节点
	}
	head->Next = NULL;
}

/* 单链表迭代器类 */
template <class Type>
class ListItr 
{
	private:
		ListNode <Type> *head;// 头节点
		ListNode <Type> *Current;// 当前节点
	public:
		ListItr (const List <Type> &L): head(L.head) 
		{Current = L.IsEmpty ()? head: head -> Next;}// 构造函数
		~ ListItr (){}// 析构函数

		void MakeEmpty();// 清空迭代器
		void Insert (const Type & x);// 插入函数

		int operator + () const// 判断是否到头或是到尾节点
		{return Current && Current != head;}

		const Type & operator ()() const;// 返回当前节点的数据域
		void operator ++ ();// 当前节点后移一位
		void operator ++ (int) {operator ++();}// 当前节点后移一位
		void Zeroth() {Current = head;}// 使当前节点指向头节点
		void First();// 使当前节点指向头节点后一节点
		const ListItr & operator = (const ListItr &);// 重载等号
};

template <class Type>
void ListItr <Type> ::MakeEmpty()
{
	ListNode <Type> *Ptr;
	ListNode <Type> *NextNode;
	for (Ptr = head->Next; Ptr != NULL; Ptr = NextNode)
	{
		NextNode = Ptr->Next;
		delete Ptr;//删除节点
	}
	head->Next = NULL;

}

template <class Type>
void ListItr <Type> :: Insert (const Type & x)
{
	ListNode <Type> *p;
	p = new ListNode <Type> (x, Current -> Next);//插入节点
	Current = Current -> Next = p;// 当前节点后移一位
}

template <class Type>
const Type &  ListItr <Type> ::operator()()const
{
	return Current -> Element;// 返回当前节点的数据域
}

template <class Type>
void ListItr <Type> ::operator ++()
{
	Current = Current -> Next;// 当前节点后移一位
}

template <class Type>
const ListItr <Type> & ListItr <Type> ::operator = (const ListItr <Type> & R)
{
	if (this = &R) return  *this;// 如果是本身就不用复制直接返回

	head = R.head;// 指向R的头节点
	Current = R.Current;// 指向R的Current的节点
	return *this
}

template <class Type>
void ListItr <Type> ::First ()
{
	Current = head -> Next;// 使当前节点指向头节点后一节点
}

/* 多项式节点类 */
struct Term
{
	float coef;  // 系数
	int exp;   // 幂指数

	Term (float c, int e) {coef = c; exp = e;}// 初始化函数
	Term() {}

	friend int operator == (const Term & L, const Term & T) {return L.exp == T.exp;}// 判断是否相等
	friend int operator > (const Term & L, const Term & T) {return L.exp > T.exp;}// 判断大小关系
    friend int operator < (const Term & L, const Term & T) {return L.exp < T.exp;}// 判断大小关系

	friend Term & operator *= (Term & L, const Term & T)
	{L.coef *= T.coef; L.exp += T.exp; return L;}// 重载运算符
	friend Term & operator += (Term & L, const Term & T)
	{L.coef += T.coef; return L;}// 重载运算符

	friend int equal_stop (const Term & L, const Term & T)
	{return L.exp == T.exp && L.coef == T.coef;}// 设置停止标志
	friend char compare (const Term & P, const Term & T);// 比较两节点
	friend Is_Empty (const Term & T){return !T.coef;}// 判断是否为空
};

/* 比较项的指数 */
char compare (const Term & P, const Term & T)
{
	if (P == T) return '=';
	else if (P < T) return '<';
	else return '>';
}

/* 多项式类 */
template <class Type>
class Polynomial
{
public:
	friend class Polynomial <Type>;
	Polynomial (const Type & P) {Stop_flag = P;}// 构造函数
	Polynomial (){}
	~ Polynomial (){}

	Polynomial & operator = (const Polynomial & T);// 重载等号
	Polynomial & operator * (const Polynomial & T);// 重载乘号
	Polynomial & operator + (const Polynomial & T);// 重载加号
	void insert ();// 插入节点
	void print ();// 输出多项式
private:
	List <Type> poly;// 单链表对象
	Type Stop_flag;// 停止标志
};

template <class Type>
void Polynomial <Type> ::insert()
{
	Type elem;
	ListItr <Type> Itr (poly);// 生成迭代器
	cout << "Please input cofficient and power exponent one by one!\n";
	
	cout << "Please input a power cofficient!\n";
	cin >> elem.coef;// 输入系数
	cout << "Please input a power exponent!\n";
	cin >> elem.exp;// 输入指数
	if (equal_stop(elem, Stop_flag))// 判断多项式是否是空的，若是的就报错跳出程序
	{
		cerr << "you input an empty Polynomial" << endl;
	}
	Itr.Insert(elem);// 插入项

	while (1)
	{
		cout << "Please input a power cofficient!\n";
		cin >> elem.coef;
		cout << "Please input a power exponent!\n";
		cin >> elem.exp;
        if (equal_stop(elem, Stop_flag)) break;//当到了结束标志时跳出
		Itr.Insert(elem);// 插入节点
	}
}

template <class Type>
void Polynomial <Type> ::print()
{
	if (poly.IsEmpty())// 判断是否为空
		cout << "Polynomial is Empty!\n";
	else
	{
		ListItr <Type> Itr(poly);

		if (Itr().coef != 0)// 系数不为零
		{
			if (Itr().exp != 0)
			{
				cout << Itr().coef << "x^" << Itr().exp;//输出多项式
			}
			if (Itr().exp == 0)
			{
				cout << Itr().coef;
			}
		}
		++Itr;

		for (; +Itr; ++Itr)
		{
			if (Itr().coef != 0)// 系数不为零
			{
				if (Itr().coef > 0) cout << '+';
				if (Itr().exp != 0)
				{
					cout << Itr().coef << "x^" << Itr().exp;//输出多项式
				}
				if (Itr().exp == 0)
				{
					cout << Itr().coef;
				}
			}
		}
	}
}

template <class Type>
Polynomial <Type> & Polynomial <Type> :: operator = (const Polynomial & T)
{
	if (this == & T) return * this;// 判断是否是本身多项式

	poly.MakeEmpty();// 清空单链表
	ListItr <Type> ItrT (T.poly);
	ListItr <Type> ItrThis (poly);
	for (;+ItrT;++ItrT) ItrThis.Insert (ItrT());// 复制多项式
	return *this;
}

/*
 * 乘法 
 * 取出本身的每个节点 与输入的多项式的每一个节点相乘
 * 然后相加得到结果
 */
template <class Type>
Polynomial <Type> & Polynomial <Type> :: operator * (const Polynomial & T)
{
	Type elemA, elemB;
	Polynomial <Type> C;
	Polynomial <Type> D;
	ListItr <Type> ItrA (poly);// 生成单链表迭代器
	ListItr <Type> ItrB (T.poly);// 生成单链表迭代器
	ListItr <Type> ItrC (C.poly);// 生成单链表迭代器

	while (+ItrA)
	{
		while (+ItrB)
		{
			elemA = ItrA();// 取出A当前节点的数据域
			elemB = ItrB();// 取出B当前节点的数据域
			elemA *= elemB;// 相乘
			ItrC.Insert(elemA);//插入到C中
			++ItrB;// B的迭代器后移一位
		}
		D + C;// 加入到D中
		ItrC.Zeroth();// 将C中Current指针指向头节点
		ItrC.MakeEmpty();// 清空C
		++ItrA;// A的迭代器后移一位
		ItrB.First();// B的Current指针指向头
	}
	*this = D;
	return *this;

}

/* 加法 */
template <class Type>
Polynomial <Type> & Polynomial <Type> :: operator + (const Polynomial & T)
{
	Type elemA, elemB;
	Polynomial <Type> C;
	ListItr <Type> ItrA (poly);// 生成A迭代器
	ListItr <Type> ItrB (T.poly);// 生成B迭代器
	ListItr <Type> ItrC (C.poly);// 生成C迭代器

	while (+ItrA && + ItrB)
	{
		elemA = ItrA();
		elemB = ItrB();
		switch (compare (elemA, elemB))// 比较两节点大小
		{
		case '=':
				elemA += elemB;// 指数相等就相加
				if (!Is_Empty(elemA)) ItrC.Insert(elemA);
				++ItrA;// A的Current指针后移一位
				++ItrB;// B的Current指针后移一位
				break;
		case '>': // 如果A的指数大B的迭代器后移一位
			ItrC.Insert(elemB);
			++ItrB;
			break;
		case'<':// 如果B的指数大A的迭代器后移一位
			ItrC.Insert(elemA);
			++ItrA;
			break;
		}
	}

	if (+ItrA) //判断A是否为空
	{
		for (;+ItrA;++ItrA)
		{
			elemA = ItrA();
			ItrC.Insert(elemA);
		}
	}
    else 
	{
		for (;+ItrB;++ItrB)
		{
			elemB = ItrB();
			ItrC.Insert(elemB);
		}
	}
	*this = C;
	return *this;
}

void main(void)
{
	Term R(-1, -1);// 结束标志
	Polynomial <Term> a(R), b(R),c;
	a.insert();// 输入a多项式
	a.print();
	b.insert();// 输入b多项式
	c = a * b;// 多项式相乘
	c.print();// 输出多项式
}