multinomial_calculate.cpp

一元稀疏多项式计算器

#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#define error 0
#define ok 1




typedef struct LNode
{
	float coef;
	int expn;
	struct LNode * next;
}ElemType, * Link;

typedef struct
{
	int len;
	Link head;
}LinkList;

void ClearInput(void)			 //非法输入错误处理函数
{
	char str[1024];
	cin.clear();
	cin.getline (str,1024);
	cout<<"非法输入，请重新输入：";
}

//初始化，建立头结点
void Init(LinkList & p)         
{
	p.head=new ElemType;
	if(!p.head)
	{
		cout<<"初始化失败！"<<endl;
		exit(0);
	}
	p.len=0;
	p.head->next=NULL;
}

float getvalue(LinkList & p,float x)
{
	Link temp;
	temp = p.head->next;
	float result = 0.0;
	while(temp)
	{		
		float y = 1.0;
		for(int i=1;i<=temp->expn;i++)y *= x;
		y *= temp->coef;
		result += y;
		temp = temp->next;
	}
	return result;
}

//输入多项式的各项的系数和指数
void create(LinkList & p,char name[])
{
	Link q,last,temp;
	temp = last = p.head;
	int sig;
	cout<<"多项式"<<name<<"是否为零 ？（1——不是    其他数字——不）";
	while (!(cin>>sig))ClearInput();
	if(sig!=1)
	{
		p.len = 1;
		return;
	}
	do
	{
		if(!(q=new ElemType))exit(0);		
		cout<<"输入系数：";
		while(!(cin>>q->coef))ClearInput();
		cout<<"输入指数：";
		while(!(cin>>q->expn))ClearInput();
		q->next = NULL;		
		if(q->coef == 0)cout<<"系数为0，不加入多项式中！"<<endl;
		else
		{				
			last->next = q;
			last = q;			
			p.len++;           //多项式项数加1			
		}
		cout<<"是否输入下一个？(1：继续 or 2：结束输入)";
		while(!(cin>>sig))ClearInput();
		while(!(sig==1||sig==2))
		{
			cout<<"输入错误，请重新输入!"<<endl;
			cout<<"是否输入下一个？(1：继续 or 2：结束输入)";
			while(!(cin>>sig))ClearInput();
		}
	}while(sig==1);
}

void clearResult(LinkList & p)  //释放头结点后的所有结点
{
	Link temp,q;
	q = p.head->next;
	while(q)
	{		
		temp = q;
		q = q->next;
		delete temp;
	}
	p.head->next = NULL;
	p.len=0;
}

void sort(LinkList & p,LinkList & result)  //对p表示的多项式排序，排序后的结果用链表result表示
{
	Link temp,r,q1,q2;
	q1 = p.head->next;	  //指向多项式的第一个项
	if(q1 == NULL)        //多项式为0，无须排序！
	{
		//cout<<"多项式为0，无须排序！"<<endl;
		result = p;
		return;
	}
	q1 = q1->next;     //指向多项式的第二项
	if(q1 == NULL)     //多项式仅一项，无须排序！
	{
		//cout<<"多项式仅一项，无须排序！"<<endl;
		result = p;
		return;
	}	
	//q1->next = NULL;     //多项式至少两项，排序——插入排序法
	q2 = p.head->next;   //指向多项式p的当前项
	r = result.head->next;
	while(q2)  //把p表示的多项式的每一项加入到result中
	{
		while(q2 && (q2->coef < 1e-10))q2 = q2->next;//若当前项系数为0
		if(!q2)break;  
		else
		{
			if(!(temp = new ElemType))
			{
				cout<<"内存分配失败！"<<endl;
				return;
			}
			
			temp->coef = q2->coef;
			temp->expn = q2->expn;
			temp->next = NULL;
		
			r = result.head;
			while(r->next && (r->next->expn > q2->expn))//找到放置q2的合适位置                                                                               
			{
				r = r->next;
			}
			if(!r->next)r->next = temp;//合适位置在链尾
			else 
			{
				//if(r->next->expn > )
				if(r->next->expn == q2->expn)//已经存在相同指数的项,系数相加
				{
					r->next->coef += q2->coef;
				}//if
				else //当 r->expn > q2->expn && r->next->expn < q2->expn时，将temp插入到r和r->next中间
				{
					temp->next = r->next;
					r->next = temp;
				}//else
			}//else			
		}//else
		q2 = q2->next;
	}//while
	//去掉result中系数为零的项
	r = result.head;
	while(true)
	{
		if(!r->next)break;
		if(r->next->coef <1e-10)
		{
			temp = r->next;
			r->next = temp->next;
			delete temp;
		}
		r = r->next;
	}//while
}


void compose_add(LinkList & p1,LinkList & p2,LinkList & p3) //p3=p1+p2
{
	LinkList pp1,pp2;
	Link q1,q2,q3,temp;

	Init(pp1);
	Init(pp2);
	sort(p1,pp1);
	sort(p2,pp2);
	
	q1 = pp1.head->next;
	q2 = pp2.head->next;
	q3 = p3.head;
	while(q1 && q2)
	{
		temp = new ElemType;
		if(!temp)
		{
			cout<<"分配失败！"<<endl;
			exit(0);
		}
		if(q1->expn > q2->expn)
		{
			temp->coef = q1->coef;
			temp->expn = q1->expn;
			temp->next = NULL;
			q3->next = temp;
			q3 = q3->next;
			p3.len++;
			q1 = q1->next;
		}
		else if(q1->expn < q2->expn)
		{
			temp->coef = q2->coef;
			temp->expn = q2->expn;
			temp->next = NULL;
			q3->next = temp;			
			q3 = q3->next;
			p3.len++;
			q2 = q2->next;
		}
		else 
		{
			temp->coef = q1->coef + q2->coef;
			temp->expn = q1->expn;
			temp->next = NULL;
			if(fabs(temp->coef) > 1e-10)  //若系数不相加为零
			{
				q3->next = temp;
				p3.len++;
				q3 = q3->next;
			}
			else
				delete temp;
			q1 = q1->next;
			q2 = q2->next;
		}
	
	}
	while(q1)
	{
		temp = new ElemType;
		if(!temp)
		{
			cout<<"分配失败！"<<endl;
			exit(0);
		}
		temp->coef = q1->coef;
		temp->expn = q1->expn;
		temp->next = NULL;
		q3->next = temp;		
		q1 = q1->next;
		q3 = q3->next;
		p3.len++;
	}
	while(q2)
	{
		temp = new ElemType;
		if(!temp)
		{
			cout<<"分配失败！"<<endl;
			exit(0);
		}
		temp->coef = q2->coef;
		temp->expn = q2->expn;
		temp->next = NULL;
		q3->next = temp;
		q2 = q2->next;
		q3 = q3->next;
		p3.len++;
	}
}

void compose_sub(LinkList & p1,LinkList & p2,LinkList & p3)  //p3=p1-p2
{
	LinkList pp1,pp2;
	Init(pp1);
	Init(pp2);
	sort(p1,pp1);
	sort(p2,pp2);
	Link q1,q2,q3,temp;
	q1 = pp1.head->next;
	q2 = pp2.head->next;
	q3 = p3.head;

	while (q1 && q2)    
	{
		temp = new ElemType;
		if(!temp)
		{
			cout<<"分配失败！"<<endl;
			exit(0);
		}
		if(q1->expn > q2->expn )
		{
			temp->coef = q1->coef;  
			temp->expn = q1->expn;
			q1 = q1->next;
			temp->next = NULL;
			q3->next = temp;
			q3 = q3->next;
			p3.len++;
		}
		else if(q1->expn < q2->expn)
		{
			temp->coef = -q2->coef;
			temp->expn = q2->expn;
			q2 = q2->next;
			temp->next = NULL;
			q3->next = temp;
			q3 = q3->next;
			p3.len++;
		}
		else //指数相等时
		{
			if(fabs((q1->coef - q2->coef))<1e-10)delete temp;   //若系数相等
			else												//若系数不等
			{
				temp->coef = q1->coef - q2->coef;
				temp->expn = q1->expn;
				temp->next = NULL;				
				q3->next = temp;
				q3 = q3->next;
				p3.len++;
			}
			q1 = q1->next;
			q2 = q2->next;
		}		
	}//end of while
	while (q1) 
	{
		temp = new ElemType;
		if(!temp)
		{
			cout<<"分配失败！"<<endl;
			exit(0);
		}
		temp->coef = q1->coef;
		temp->expn = q1->expn; 
		temp->next = NULL;
		q1 = q1->next;
		q3->next = temp;
		q3 = q3->next;
		p3.len++;
	}
	while (q2)
	{
		temp = new ElemType;
		if(!temp)
		{
			cout<<"分配失败！"<<endl;
			exit(0);
		}
		temp->coef = - q2->coef;
		temp->expn = q2->expn; 
		temp->next = NULL;
		q2 = q2->next;
		q3->next = temp;
		q3 = q3->next;
		p3.len++;
	}
}

void getDerivative(LinkList & p1,LinkList & p3)
{
	LinkList pp1;
	Init(pp1);
	sort(p1,pp1);
	Link q1,q3,temp;
	q1 = pp1.head->next;
	q3 = p3.head;

	while(q1)
	{
		if(!(temp = new ElemType))exit(0);

		if(q1->expn == 0)q1 = q1->next;		
		else 
		{
			temp->coef = q1->coef * q1->expn;
			temp->expn = q1->expn - 1;
			temp->next = NULL;
			q1 = q1->next;
			q3->next = temp;
			q3 = q3->next;
		}		
	}//end of while
}

//显示某一个多项式
void display(LinkList & p)
{
	Link temp;
	temp = p.head->next;
	if(!temp){cout<<0;return;}
	while(temp)
	{
		if(fabs(temp->coef) < 1e-10)cout<<"";//系数为0，此项输出空
		else 
		{		
			if(temp->expn==0)          //若指数为0，仅输出系数
			{
				if(temp == p.head->next)cout<<temp->coef;	 //若为第一项
				else										 //若不是第一项
				{
					if(temp->coef > 0)cout<<" + "<<temp->coef;
					else cout<<" - "<<fabs(temp->coef);
				}
			}
			else                      //若指数不为0，输出
			{
				if(temp == p.head->next)//若为第一项
				{
					if(temp->coef == 1)cout<<"";
					else if(temp->coef == -1)cout<<"-";
					else cout<<temp->coef;
				}		
				else 
				{
					if(temp->coef == 1)cout<<" + ";
					else if(temp->coef == -1)cout<<" - ";
					else if(temp->coef > 0)cout<<" + "<<temp->coef;
					else cout<<" - "<<fabs(temp->coef);
				}			
				cout<<"x^"<<temp->expn;
			}			
		}
		temp = temp->next;		
	}
}


void main()
{
	LinkList multinomial1,multinomial2,multinomial3;
	Init(multinomial1);	  	   //初始化多项式1，建立头结点
	Init(multinomial2);   	   //初始化多项式2，建立头结点
	Init(multinomial3);  	   //初始化多项式3，建立头结点，放置结果	
	
	int i;
	do 
	{
		system("cls");
		cout<<"     **************************************************************    "<<endl;
		cout<<"     **  1、加法  2、减法   3、在某点的值   4、导函数   5、退出  **    "<<endl;   
		cout<<"     **************************************************************    "<<endl;
		do
		{
			cout<<"输入你的选择（1 or 2 or 3 or 4 or 5）：";
			while(!(cin>>i))ClearInput();
		}while(!(i==1 || i==2 || i==3 || i==4 || i==5));	
		switch(i) {
		case 1:											//求和
			cout<<endl<<"建立被加数多项式！"<<endl;
			create(multinomial1,"multinomial1");		
				
			cout<<endl<<"建立加数多项式！"<<endl;
			create(multinomial2,"multinomial2");			
	
			compose_add(multinomial1,multinomial2,multinomial3);//相加
			
			cout<<endl<<"输出求和结果："<<endl;
			cout<<" ( ";
			display(multinomial1);
			cout<<" ) ";
			cout<<" + ";
			cout<<" ( ";
			display(multinomial2);
			cout<<" ) ";
			cout<<" = ";
			display(multinomial3);
			cout<<endl;
			break;
		case 2:													//求差
			cout<<endl<<"建立被减数多项式！"<<endl;
			create(multinomial1,"multinomial1");		
		
			cout<<endl<<"建立减数多项式！"<<endl;
			create(multinomial2,"multinomial2");			
				
			compose_sub(multinomial1,multinomial2,multinomial3);//相减

			cout<<endl<<"输出求差结果："<<endl;
			cout<<" ( ";
			display(multinomial1);
			cout<<" ) ";
			cout<<" - ";
			cout<<" ( ";
			display(multinomial2);
			cout<<" ) ";
			cout<<" = ";
			display(multinomial3);
			cout<<endl;
			break;
		case 3:									       	//求在某点的值
			cout<<endl<<"建立多项式！"<<endl;
			create(multinomial1,"multinomial1");		
				
			if(multinomial1.head->next == NULL)         //多项式为零
				cout<<endl<<"多项式值为0"<<endl;
			else
			{
				cout<<endl<<"求在某一点的值！"<<endl;
				float x;
				cout<<"输入x的值：";
				while(!(cin>>x))ClearInput();
				cout<<"多项式在"<<x<<"处的值为："<<getvalue(multinomial1,x)<<endl;
			}			
			break;		
		case 4:                 //求导
			cout<<endl<<"建立多项式！"<<endl;
			create(multinomial1,"multinomial1");
				
			if(multinomial1.head->next == NULL)           //多项式为零
				cout<<endl<<"多项式值为0，导数也为0"<<endl;
			else
			{
				cout<<endl<<"求导函数！"<<endl;
				getDerivative(multinomial1,multinomial3);//对multinlmial1求导，multinomial3中放置求导结果
				cout<<endl<<"输出导函数！"<<endl;
			    cout<<" ( ";
				display(multinomial1);
				cout<<" )' = ";
				display(multinomial3);
				cout<<endl;
			}
			break;			
		case 5:
			break;
		}	
		clearResult(multinomial3);	//清空结果链表，仅留头结点
		clearResult(multinomial2);	//清空链表，仅留头结点
		clearResult(multinomial1);	//清空链表，仅留头结点			
		if(i!=5)
		{
			cout<<endl<<"按回车继续！"<<endl;	
			getchar();	
		}		
	} while(i!=5);	
}