一元多项式相加.cpp

包含几十个有关数据结构算法的源代码 包括栈 队列 树图等 是初学者的最佳选择

#include <conio.h>
#include <stdio.h>
#include <iostream.h>

class NODE
{
	//友元类设置是为了使链表类能访问此结点类的私有成员
	friend class LIST;
	private :
		NODE *NEXT;
		double coe;//系数
		int exp;//指数
};

class LIST
{
	private :
		NODE *HEAD;//多项式的链表的头指针
	public :
		LIST()
		{
			HEAD=0;
		}
		NODE* GET_HEAD();
		void LIST::DISPLAY(NODE *TEMP);
		void LIST::INSERT(double coe,int exp);
		void LIST::CREAT();
		LIST LIST::ADD(LIST mulA,LIST mulB);
		LIST operator+(const LIST& other);  //加法运算
	//	LIST operator=(const LIST& other);
		void CLEAR();//
		~LIST()
		{
			CLEAR();
		}
};

NODE* LIST::GET_HEAD()
{
	return (HEAD);
}

void LIST::DISPLAY(NODE *TEMP)
{
	if (HEAD==0)
	{
		printf("----Sorry!!!  It's EMPTY !!! ");
	}
	else
	{
		while(TEMP!=0)
		{
			printf("%.2f^%d  ",TEMP->coe,TEMP->exp);
			TEMP=TEMP->NEXT;
		}
	}
	printf("\n");
}

void LIST::INSERT(double coe,int exp)
{
	NODE *TEMP=HEAD;
	NODE *PREVIOUS;
	NODE *NEWNODE;

	NEWNODE=new NODE;
	NEWNODE->coe=coe;
	NEWNODE->exp=exp;
	NEWNODE->NEXT=0;

	if(HEAD==0)
	{
		HEAD=NEWNODE;
	}
	else
	{
		while(((NEWNODE->exp)<exp)&&(TEMP!=0))
		{

		   PREVIOUS=TEMP;
		   TEMP=TEMP->NEXT;
		}
		if(TEMP==HEAD)
		{
			NEWNODE->NEXT=HEAD;
			HEAD=NEWNODE;
		}
		else
		{
			NEWNODE->NEXT=TEMP;
			PREVIOUS->NEXT=NEWNODE;
		}
	}
}

void LIST::CREAT()
{
	int n,i;
	double coe;
	int exp;
	cout<<"请输入多项式的项数（包括常数项）：";
	cin>>n;
	cout<<"请依次输入多项式的每项的系数和指数：";
	for(i=1;i<=n;i++)
	{
		cin>>coe>>exp;
		INSERT(coe,exp);
	}
}

LIST LIST::ADD(LIST mulA,LIST mulB)
//LIST LIST::operator+(const LIST& other)
{
	LIST TEMP;
	TEMP.HEAD->NEXT=NULL;
	NODE *la=mulA.HEAD,*lb=mulB.HEAD,*lc=TEMP.HEAD;
	double sum;
	int a,b;
	while(la&&lb)
	{    
		//a，b分别动态记录两个参与运算的多项式的每一项的指数；
 		a=la->exp;b=lb->exp;
		if(a<b){
			NODE *p;
		//	if(p){
			p->coe=la->coe;p->exp=la->exp;
			p->NEXT=lc->NEXT;lc->NEXT=p;
			la=la->NEXT;
		//	}
		//	else exit(0);
		 }
		if(a==b){
			sum=la->coe+lb->coe;
			if(sum-1E-15>0.0||sum+1E-15<0.0){
			NODE *p;
		//	if(p){
			p->coe=sum;
			p->exp=la->exp;
			p->NEXT=lc->NEXT;
			lc->NEXT=p;
			la=la->NEXT;
			lb=lb->NEXT;
		//	}
		//	else exit(0);
			}
			else{
				la=la->NEXT;lb=lb->NEXT;
			}
		}
	   if(a>b){
		    NODE *p;
		//	 if(p){
				 p->coe=lb->coe;//对flag的判断
			     p->exp=lb->exp;
			     p->NEXT=lc->NEXT;
			     lc->NEXT=p;
			     lb=lb->NEXT;
		//	   }
	//	else exit(0);	
	   }
	} 
	    //这里是对两个链表的没有比较的元素的处理；
		if(la)
			while(la){
				  NODE *p;
			//	  if(p){
			      p->coe=la->coe;p->exp=la->exp;
			      p->NEXT=lc->NEXT;
			      lc->NEXT=p;
			      la=la->NEXT;
			 //     }
			//	  else exit(0);
				}
		else
			while(lb){
					NODE *p;
			//	    if(p){
			        p->coe=lb->coe;p->exp=lb->exp;
			        p->NEXT=lc->NEXT;
			        lc->NEXT=p;
			        lb=lb->NEXT;
			//		}
			//	   else exit(0);
				}
	return TEMP;
}
/*
LIST LIST::operator=(const LIST& other)
{
	HEAD=other.HEAD;
	return *this;
}
*/
void LIST::CLEAR()
{
	NODE *TEMP_HEAD=HEAD;

	if (TEMP_HEAD==0) return;
	do
	{
		NODE *TEMP_NODE=TEMP_HEAD;
		TEMP_HEAD=TEMP_HEAD->NEXT;
		delete TEMP_NODE;
	}
	while (TEMP_HEAD!=0);
}

int main(void)
{
	LIST A,B,C;
	NODE *Head;
//	double coe;
//	int exp;
//	TEST.INSERT(2.3,2);
//	TEST.INSERT(2.4,5);
//	TEST.INSERT(3,4);
    A.CREAT();
	Head=A.GET_HEAD();
	printf("The data in the list is(from HEAD to END):");
	A.DISPLAY(Head);
	B.CREAT();
	Head=B.GET_HEAD();
	printf("The data in the list is(from HEAD to END):");
	B.DISPLAY(Head);
	C=C.ADD(A,B);
	Head=C.GET_HEAD();
	printf("The data in the list is(from HEAD to END):");
	C.DISPLAY(Head);
//	printf("\nInput a number to insert in the list:");
//	scanf("%",&coe);
//	scanf("%d",&exp);
//  cin>>coe;
//  cin>>exp;
//	printf("%f\n",coe);
//	printf("%d\n",exp);
//	TEST.INSERT(coe,exp);
//	Head=TEST.GET_HEAD();/*SOMETIMES HEAD MAY BE CHANGED*/
//	TEST.DISPLAY(Head);
	getch();
	return 0;
}