多项式乘法.cpp

自己编的用来算多项式相乘的程序

//                           多项式的相乘

//			作者：江海       班级：03009802       学号：03304067

//                程序中所有用来表示多项式的链表都不带头结点 


#include <iostream.h>     //头文件

struct PNode         //多项式链表的接点结点数据类型
{
	float coef;     //系数
	int expn;       //指数
	PNode *next;    //指向下一个结点的指针
};//struct


int cmp(int a, int b)
/*
函数：  两个整型数据的大小比较
参数：  整型变量 a 和 b
返回：  若 a>b  返回 1  ;   
        若 a=b  返回 0  ;  
        若 a<b  返回 -1  ;
 */
{
	if(a-b>0){return 1;}
	else{
		if(a-b<0){return -1;}
		else{return 0;}
	}
}//function


void InsertNode(PNode *&p,PNode *&ha)
/*
函数：  将一个结点插入到已有的多项式中
参数：  待插结点的指针值 p 和被插多项式的头指针 ha 
返回：  插入完成后多项式的头指针
备注：  函数执行后,  ha被修改为插入结点后的多项式
 */
{ 
	int flag=1;         //标记变量，用来结束含有switch语句的循环
    PNode *q,*r;
	q=ha;                          
	if(!q){    ha=p;  p->next=NULL;  return;}
	else{
		switch(cmp(p->expn,q->expn)){  //先对第一个结点进行判断，再处理后面的结点时，指针操作可以更简洁
		case 1:
            p->next=q;  ha=p;  break;
		case 0:
			q->coef+=p->coef;
			if(q->coef==0){
				ha=q->next;
				delete q;
			}
			break;
		case -1:
			while(q->next!=NULL&&flag){
				switch(cmp(p->expn,q->next->expn)){
				case -1:
					q=q->next;   break;
				case 0:
					q->next->coef+=p->coef;
					if(q->next->coef==0){
						r=q->next; 
						q->next=r->next;
						delete r;
					}//if
					flag=0;     //令flag=0结束循环
					break;
				case 1:
					p->next=q->next;
					q->next=p;
					flag=0;     //令flag=0结束循环
					break;
				}//switch
			}//while
			if(q->next==NULL){
				q->next=p;  p->next=NULL;
			}//if
			break;
		}//switch
	}//else
}//function


void PrintPolyn(PNode *pa)
/*
函数：  多项式的打印
参数：  将要被打印的多项式的头指针
*/
{
	PNode *p;
	p=pa;
	if(p==NULL){cout<<"0      "<<endl;}
	while(p!=NULL){
		switch(p->expn){
		case 0:
			cout<<p->coef;  break;  
		case 1:                       
			if(p->coef==1){  cout<<"x";  }
			else{
			    if(p->coef==-1){  cout<<"-x";  }
			    else{  cout<<p->coef<<"x";  }
			}
			break;	
		default:                           
			if(p->coef==1){  cout<<"x^"<<p->expn;  }   
			else{
			    if(p->coef==-1){  cout<<"-x^"<<p->expn;  }  
			    else{  cout<<p->coef<<"x^"<<p->expn;  }
			}
			break;
		}//switch
		if(p->next!=NULL&&p->next->coef>0){  
			cout<<"+";
		}
		p=p->next;
	}//while
}//function


PNode *CreatPolyn()
/*
函数：  创建一个多项式
返回：  已创建的多项式的头指针
*/
{
	PNode *p,*r;
	p=NULL;
	r = new PNode;
	cout<<endl<<"创建多项式:"<<endl;
	r->coef=0;  r->expn=-1;r->next=NULL;
	cin>>r->coef;  cin>>r->expn;  r->next=NULL;
	while(r->coef!=0){
		InsertNode(r,p);
		r= new PNode;
    	r->coef=0;  r->expn=-1;r->next=NULL;
		cin>>r->coef;  cin>>r->expn;  r->next=NULL;
	}//while
    delete r;
	return p;
}//function

void DestroyPolyn(PNode *&h)
/*
函数：  删除一个多项式
参数：  被删除的多项式的头指针
备注：  执行后，以h为头指针的多项式被删除
*/
{
	PNode *p;
	while(h!=NULL){
		p=h;
		h=p->next;
		delete p;
	}
}


PNode *MultiplyPolyn(PNode *ha, PNode *hb)
/*
函数：  乘法的运算
参数：  两个多项式的头指针。
返回：  一个新的多项式的头指针
备注：  对形参ha和hb没有影响
*/
{
	if(ha==NULL||hb==NULL){  return NULL;  }
	else{
    	PNode *p,*q,*r,*pa;
	    pa=NULL;
    	p=ha;
    	while(p!=NULL){ 
			q=hb;
	    	while(q!=NULL){
		    	r = new PNode;
 			    r->coef=p->coef*q->coef;
    			r->expn=p->expn+q->expn;
	    		r->next=NULL;
                InsertNode(r,pa);
			    q=q->next;
			}//while
	    	p=p->next;
		}//while
        return pa;
	}//else
}//function


void start()                       //开始函数：  作为程序运作的开始提示
{
	cout<<"                                多项式的相乘"<<endl;
    cout<<"注意输入格式："<<endl;
	cout<<"1 2          (第1项的系数和幂) "<<endl;
	cout<<"4 5          (第2项的系数和幂) "<<endl;
	cout<<"...          ................  "<<endl;
	cout<<"m n          (第N项的系数和幂) "<<endl;
	cout<<"0 0          (结束) "<<endl;
}//fuction


void main(void)                 //主函数
{
	start();                   //提示输入的格式
	PNode *pa,*pb,*pc;        
	pa=CreatPolyn();            //创建第一个多项式
	cout<<"第一个多项式:"<<endl;
	PrintPolyn(pa);
    pb=CreatPolyn();            //创建第二个多项式
	cout<<"第二个多项式:"<<endl;
    PrintPolyn(pb);
	cout<<endl;
	pc=MultiplyPolyn(pa,pb);    //调用乘法函数
	cout<<endl<<endl<<"相乘的结果是:"<<endl;
    PrintPolyn(pc);             //显示运算结果
	cout<<endl;
    DestroyPolyn(pa);
    DestroyPolyn(pb);
    DestroyPolyn(pc);           //释放多项式占用的内存
}   //main