#include<iostream>
using namespace std;
struct LNode{   //节点类
	double p;//系数项
	int  e;//指数项
	LNode * next;
};

class LsList{//一元多项式链式线性表
private:
	LNode head;//头结点
	size_t size;//节点个数
	double mx;//一元多项式的变量值
public:
	LNode & GetHead(){return head;}
	size_t & GetSize(){return size;}
	size_t GetSize() const {return size;}
	LsList()
	{//初始化一个空的线性表
		size = 0;
		head.next = 0;
		mx = 0;
	}

//初始化一元多项式线性表中的系数项、指数项
 LsList(double ps[],int es[],int n)//ps代表系数项数组，es代表指数项数组,n代表该一元多项式的个数
{
	size = 0;
	head.next = 0;
	mx = 0;
	int i =0;
	LNode * p = &head;
	for(;i<n;i++)
	{
		LNode * p1 = (LNode*)malloc(sizeof(LNode));
		p1->e = es[i];
		p1->p = ps[i];
		p->next = p1;
		p = p->next;
		size++;
	}
	p->next = 0;
}
//复制构造函数
	LsList(LsList &list2)
{
	size = 0;
	head.next = 0;
	mx = 0;
	LNode * p = &head;
	LNode *p1  = list2.GetHead().next;
	while(p1!=0)
	{
		LNode * p2 = (LNode*)malloc(sizeof(LNode));
		p2->e = p1->e;
		p2->p = p1->p;
		p->next = p2;
		p1 = p1->next;
		p = p->next;
		size++;
	}
	p->next = 0;
}
//赋值操作符重载
LsList & operator=(LsList &list2)
{
	
	clear();
	LNode * p = &head;
	LNode *p1  = list2.GetHead().next;
	while(p1!=0)
	{
		LNode * p2 = (LNode*)malloc(sizeof(LNode));
		p2->e = p1->e;
		p2->p = p1->p;
		p->next = p2;
		p1 = p1->next;
		p = p->next;
		size++;
	}
	p->next = 0;
	return *this;
}


//设置该一元多项式的变量值X
void SetX(double d)
{
  mx = d;
}

//清空一个线性表
void clear()
{

	LNode * p = head.next;
	while(p!=0)
	{
		LNode * p2 = p->next;
		free(p);
		p = p2;
	}
	size = 0;
	head.next = 0;
	mx = 0;
}

//打印该一元线性表
void PrintLsList()
{
	if(mx==0)
	{
	 cout<<"请先设置变量x值"<<endl;
	 return ;
	}
	LNode * p = head.next;
	while(p!=0)
	{
		cout<<p->p<<"*"<<mx<<"^"<<p->e;
		p = p->next;
		if(p!=0&&p->p>0) 
		cout<<"+";
	}
}

//计算该一元多项式结果
double GetResult()
{
 double sum =0;
 if(mx==0)
	{
	 cout<<"请先设置变量x值"<<endl;
	 return -1;
	}
 LNode * p = head.next;
 while(p!=0)
	{
		sum+=(p->p)*pow(mx,p->e);
		p = p->next;
	}
 return sum;
}

//删除多项式中的某一项数据
bool DeleElem(int e)
{  
	LNode * p1 = &head;
	LNode * p = p1->next;
     while(p!=0)
	{
		if(p->e==e)
		{  
			p1->next = p->next;
			free(p);
			size--;
			return true;
		}
		p1 = p1->next;
		p =  p1->next;
	}
	 return false;
}


//给多项式添加一项数据
void AddElem(double pi,int ei)
{
	
	LNode * p = head.next;

	if(p==0)
	{
	    LNode * p2 = (LNode*)malloc(sizeof(LNode));
		p2->e =ei;
		p2->p = pi;
		head.next = p2;
		size++;
		p2->next = 0;
		return;
	}
	if(p->e>ei)
	{
		LNode * p2 = (LNode*)malloc(sizeof(LNode));
		p2->e =ei;
		p2->p = pi;
		head.next = p2;
		p2->next = p;
		size++;
		return;
	}

     while(p!=0)
	{
		if(p->e == ei)
		{
			if(( p->p + pi)==0)
			{
			 DeleElem(ei);//删除
			 return;
			}
			else
			{
				p->p += pi;
			    return;
			}
		}
		if((p->e<ei && p->next!=0 && p->next->e>ei)||(p->e<ei&&p->next==0))
		{
		  LNode * p2 = (LNode*)malloc(sizeof(LNode));
		  p2->e =ei;
		  p2->p = pi;
		  p2->next = p->next;
		  p->next = p2;
		  size++;
		  return ;
		}
		p = p->next;
	}

}

//完成多项式的相加运算，并销毁多项式list2
void AddList(LsList &list2)
{
	int s1 = size;
	int n=0;
	size =0;
	LNode * p1 = head.next;
	LNode * p = &head;
	LNode * p2 = list2.GetHead().next;

	while(p1!=0&&p2!=0)
	{
		if(p1->e < p2->e)
		{
			p->next = p1;
			p1 = p1->next;
			p = p->next;
			size++;
		}
		else
		{
		if(p1->e > p2->e)
			{
				p->next = p2;
				p2 = p2->next;
				p = p->next;
				size++;
			}
			else{
				double db = (p1->p)+(p2->p);
				if(db!=0)
				{
					p1->p  = db;
					p->next = p1;
					p = p->next;
					size++;
					p1 = p1->next;
					LNode * p3 = p2->next;
					free(p2);
					p2=p3;
					size++;

				}
				if(db==0)
				{
					LNode * pa = p1->next;
					LNode * pb = p2->next;
					free(p1);
					free(p2);
					p1 = pa;
					p2 = pb;
					n++;
				}
			}
		}
	
	}


	if(p1==0)
	{
	p->next = p2;
	size += list2.GetSize() - size - n;
	}
	else
	{
	p->next = p1;
	size += s1 - size - n;
	}

	list2.GetHead().next = 0;
}

//完成多项式的相减运算，并销毁多项式list2
void Sub(LsList &list2)
{
	LNode *p  = list2.GetHead().next;
	while(p!=0)
	{
		p->p = -(p->p);
		p = p->next;
	}
	AddList(list2);
}

//完成多项式的相乘运算，并销毁多项式list2
void Mul(LsList &list2)
{
	LNode *p  = list2.GetHead().next;
	LsList ili = *this;
	while(p!=0)
	{
		LsList li = ili;
		for(LNode * p1 = li.GetHead().next;p1!=0;p1 = p1->next)
		{
			p1->p = (p1->p)*(p->p);
			p1->e = p1->e + p->e;
		}
		AddList(li);
		p = p->next;
	}
}

////完成多项式的相除运算，并销毁多项式list2
//void Devi()
//{
//
//
//}
};

int main()
{
	/*
	*测试一
	*/
//创建一个空的线性表
	LsList list1;
//给该空的线性表添加项信息
	list1.AddElem(1,2);
	list1.AddElem(1.5,3);
	list1.AddElem(2,4);
//设置该一元多项式的变量x的值
	list1.SetX(3);
	cout<<endl;
	cout<<"创建一个空的线性表后添加每项的数据"<<endl;
	cout<<"输出该一元多项式的表达式和求值:"<<endl;
	list1.PrintLsList();
//输出该一元多项式的表达式和求值
	cout<<" = "<<list1.GetResult()<<endl;

	/*
	*测试二
	*/
//用每项的信息数组初始化线性表
	double ps[5] = {1,2.5,3,5.4,6};//每项的系数信息数组
	int es[5] = {1,2,4,6,7};//每项的指数信息数组
	LsList list2(ps,es,5);
//设置该一元多项式的变量x的值
	list2.SetX(2);
	cout<<endl;
	cout<<"用每项的信息数组初始化线性表"<<endl;
	cout<<"输出该一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	list2.PrintLsList();
	cout<<" = "<<list2.GetResult()<<endl;

	/*
	*测试三
	*/
//直接赋值构造一个一元多项式线性表对象
	LsList list3 = list2;
//设置该一元多项式的变量x的值
	list3.SetX(2);
	cout<<endl;
	cout<<"直接赋值构造一个一元多项式线性表对象"<<endl;
	cout<<"输出该一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	list3.PrintLsList();
	cout<<" = "<<list3.GetResult()<<endl;
//给该线性表再添加一项数据
	cout<<endl;
	cout<<"给该线性表再添加一项数据:其中系数为4，指数为5"<<endl;
	list3.AddElem(4,5);
	cout<<"输出该一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	list3.PrintLsList();
	cout<<" = "<<list3.GetResult()<<endl;
//给该线性表再添加一项数据
	cout<<endl;
	cout<<"给该线性表再添加一项数据:其中系数为-1，指数为2"<<endl;
	list3.AddElem(-1,2);
	cout<<"输出该一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	list3.PrintLsList();
	cout<<" = "<<list3.GetResult()<<endl;
//删除线性表中的一项数据信息
	cout<<endl;
	cout<<"删除该一元多项式中指数项为2的项"<<endl;
	list3.DeleElem(2);
	cout<<"输出该一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	list3.PrintLsList();
	cout<<" = "<<list3.GetResult()<<endl;


	/*
	*测试四
	*/
	LsList myList = list2;
	LsList myList1 = list3;
	myList.SetX(2);
	myList1.SetX(2);
	cout<<endl;
	cout<<"输出该一元多项式list2的表达式:"<<endl;
//输出该一元多项式的表达式
	list2.PrintLsList();
	cout<<" = "<<list2.GetResult()<<endl;
	cout<<endl;

	cout<<endl;
cout<<"输出该一元多项式list3的表达式:"<<endl;
//输出该一元多项式的表达式
	myList1.PrintLsList();
	cout<<" = "<<myList1.GetResult()<<endl;
	cout<<endl;
//将list2一元多项式加上list3一元多项式
	myList.AddList(myList1);
	cout<<endl;
	cout<<"输出将list2一元多项式加上list3一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	myList.PrintLsList();
	cout<<" = "<<myList.GetResult()<<endl;


//将list2一元多项式减去list3一元多项式
	LsList myList3 = list2;
	LsList myList4 = list3;
	myList3.SetX(2);
	myList4.SetX(2);
	myList3.Sub(myList4);
	cout<<endl;
	cout<<"输出将list2一元多项式减去list3一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	myList3.PrintLsList();
	cout<<" = "<<myList3.GetResult()<<endl;

//将list2一元多项式乘以list3一元多项式
	
	myList3 = list2;
	myList4 = list3;
	myList3.SetX(2);
	myList4.SetX(2);
	myList3.Mul(myList4);
	cout<<endl;
	cout<<"输出将list2一元多项式乘以list3一元多项式的表达式和求值:"<<endl;
//输出该一元多项式的表达式和求值
	myList3.PrintLsList();
	cout<<" = "<<myList3.GetResult()<<endl;

	list2.clear();
	list3.clear();
return 0;
}

JAVA设计模式之享元模式,布布扣,bubuko.com

JAVA设计模式之享元模式