大作业.cpp

写多项式类

#include<iostream.h>
class polynomial;//先声名，以便后面将它定义为ListNode的友元类。   
class ListNode
{
friend  class polynomial;
private:
	double data1;//存放系数。
	int data2;//存放指数。
	ListNode *link;	
};
class polynomial
{ 
private:
	ListNode *first;
	int size;
public:
	polynomial();//初始化多项表为一个空的单链表。
	void set();     //设置多项式的数据                                 
	ListNode *findout(int i);
	void Delete(int i);
	void print();
	void sort();
	polynomial operator+(polynomial &p1);
	polynomial operator-(polynomial &p1);
};
polynomial::polynomial()
{
	first=new ListNode;
	first=NULL;
	size=0;
}
void polynomial::set()
{
	cout<<"输入的元素个数为：";
	cin>>size;
	double b;int c;
	//p、q指针用于循环输入结点的内容。
	ListNode *p,*q;
	p=new ListNode;
	cout<<"输入第0个数的系数：";cin>>b;
	cout<<"输入第0个数的指数：";cin>>c;
	p->data1=b;
	p->data2=c;
	p->link=NULL;
	first=p;//头指针的节点在while循环外面先存放好数据。
	int k=size;//保留size，
	for(int i=1;i<size;i++)
	{
		cout<<"输入第"<<i<<"个数的系数：";
		cin>>b;
		cout<<"输入第"<<i<<"个数的指数：";
		cin>>c;
		q=new ListNode;
		q->data1=b;
		q->data2=c;
		q->link=NULL;
		p->link=q;
		p=q;	//p不断后指，从而实现了不断添加结点的目的
	}
}
ListNode *polynomial::findout(int i)
//找到第i个结点的指针，为下面的插入删除作铺垫
{
	ListNode *p=first;
	if(i<0)//i不可能为负数
	{
		cout<<"不存在第"<<i<<"个结点";
		return NULL;
	}
	int j(0);
	while(p!=NULL&&j<i)
	{
		p=p->link;
		j++;
	}
	return p;
}
void polynomial::Delete(int i)
{
	ListNode*p=findout(i-1);
	if(p->link)
	{
		ListNode*q=p->link;
		p->link=q->link;
		delete q;
		size--;//注意size--
	}
}
void polynomial::print()//打印此节点。
{
	ListNode *p=first;
	while(p)
	{
		if(p==first)//由于第一个结点系数为正时不需要"+"号，故要分开讨论——p是否为第一个结点。
		{
			if(p->data1!=0&&p->data2!=0)
				cout<<p->data1<<"x^"<<p->data2;
			//else if(p->data1==0)不需要。
			else if(p->data1!=0&&p->data2==0)//指数为0时，只输出系数。
				cout<<p->data1;
		}	
		else
		{
			if(p->data1>0&&p->data2!=0)
				cout<<"+"<<p->data1<<"x^"<<p->data2;
			else if(p->data1<0&&p->data2!=0)
				cout<<p->data1<<"x^"<<p->data2;
			else if(p->data1>0&&p->data2==0)//指数为0时，系数为正时，系数还要前面添加一个加号。
				cout<<"+"<<p->data1;
			else if(p->data1<0&&p->data2==0)
				cout<<p->data1;
		}
		p=p->link;
	}
	cout<<endl;
}
void polynomial::sort()
{
	ListNode *p=first;
	ListNode *q;
	//冒泡法进行排序。
	while(p!=NULL)  //不能写成p->link，原因未知
	{
		q=p->link;
		ListNode *s=p;//s始终指向q的前一个结点。
		while(q)//p结点后面所有结点的data2跟p-〉data2比较。
		{//如果有指数一样的两项，要将它们合并。
			if(p->data2==q->data2)
			{//合并就是将后面的相同data2的结点的系数加到前面结点中去，然后把后面的结点delete掉。
				p->data1+=q->data1;
				s->link=q->link;
				delete q;//内存被delete掉后，需要将q定义为以前位置的下一个结点。
				q=s->link;//注意：q删掉后还是就没有指向了，要将它继续指向s-〉link继续循环。
				size--;//size记住由于合并了所以减少一个。
			}
			//如果p后面的结点指数比p小，就将这两个结点的所有数据交换。
			else if(p->data2>q->data2)
			{
				double m;int n;
				m=p->data1;
				p->data1=q->data1;
				q->data1=m;
				n=p->data2;
				p->data2=q->data2;
				q->data2=n;
				s=q;
				q=q->link;
			}
			else
			{
				s=q;
				q=q->link;
			}
		}
		p=p->link;
	}
}//如果利用友元函数进行编写，要注意，不能调用p1->data;因为友元函数并不是类中的，所以，不管此类是否为ListNode的友元类，此函数不可以调用ListNode的私有成员。
polynomial polynomial::operator+(polynomial &p1)
{
	sort();//先将两个多项式进行排序。
	p1.sort();
	ListNode *p=first;	ListNode *s=p;//s作为q的前面的结点。
	ListNode *q=p1.first;ListNode *t=q;
	while(p)
	{
		while(q)
		{//如果q->data2小，就新建一个与q存放数据一样的结点 放到p的前面，q再后指。
			if(q->data2<p->data2)
			{
				ListNode *m=new ListNode;
				m->data1=q->data1;
				m->data2=q->data2;
				//p要分是不是头结点两种情况，因为头结点前面没有结点了，在头结点前面添加结点和在其他结点前面添加情况有差别。
				if(p==first)
				{
					m->link=p;
					first=m;
				}
				else
				{
					m->link=p;
					s->link=m;
					s=s->link;//增加新的结点，s不是p的前一个结点，所以应该下移一个继续成为p的头一个结点。
				}
				t=q;
				q=q->link;
			}
			//如果两者的data2 相等就将p->data1+=q->data1即可。
			else if(q->data2==p->data2)
			{
				p->data1+=q->data1;
				t=q;
				q=q->link;
				break;
			}
			else
			break;
		}
		s=p;
		p=p->link;
	}
	if(q)
	{
		t->link=NULL;
		s->link=q;
	}
		return *this;
}
//减法运算与加法运算类似。
polynomial polynomial::operator-(polynomial &p1)
{
	sort();
	p1.sort();
	ListNode *p=first;	ListNode *s=p;
	ListNode *q=p1.first;ListNode *t=q;
	while(p)
	{
		while(q)
		{
			if(q->data2<p->data2)
			{
				ListNode *m=new ListNode;
				m->data1=-(q->data1);
				m->data2=q->data2;
				if(p==first)
				{
					m->link=p;
					first=m;
				}
				else
				{
					m->link=p;
					s->link=m;s=s->link;
				}
				t=q;
				q=q->link;
			}
			else if(q->data2==p->data2)
			{
				p->data1-=q->data1;
				t=q;
				q=q->link;
				break;
			}
			else
			break;
		}
		s=p;
		p=p->link;
	}
	if(q)
	{
		t->link=NULL;
		s->link=q;
		while(q)
		{
			q->data1=-(q->data1);
			q=q->link;
		}
	}
		return *this;
}
void main()
{
	polynomial p1,p2,p3;
	cout<<"————这是多项式1————"<<endl;
	p1.set();p1.sort();p1.print();
	cout<<"\n————这是多项式2————"<<endl;
	p2.set();p2.sort();p2.print();
	p3=p1+p2;
	cout<<"\n多项式1和多项式2相加后为：";
	p3.print();
	polynomial p4,p5,p6;
	cout<<"\n————这是多项式3————"<<endl;
	p4.set();p4.sort();p4.print();	
	cout<<"\n————这是多项式4————"<<endl;
	p5.set();p5.sort();p5.print();
	p6=p4-p5;
	cout<<"\n多项式3和多项式4相减后为：";
	p6.print();
}