11.cpp

这里面有很多经典的算法

#include "stdio.h"
#include "stdlib.h"
typedef struct polynode{
	int coef;
	int exp;
	struct polynode *next;
}PNode;

PNode *creat_list(int n);
PNode *add(PNode *pa,PNode *pb);
PNode *sub(PNode *pa,PNode *pb);
PNode *mul(PNode *pa,PNode *pb);
PNode *qiudao(PNode *pa);
void print_list(PNode *h);
int value(PNode * pa,int elem);
void writer(PNode *g);
void trans(PNode *pa);
 
void main()
{ 
	PNode *Ha,*Hb,*La,*A;
	int la,lb,a,b;
	printf("enter la,lb:");
	scanf("%d,%d",&la,&lb);
	printf("\ncreat Ha\n");
	Ha=creat_list(la);//建链表一
	printf("A(x)=");
	writer(Ha);
	//print_list(Ha); 
	
    printf("\n对一元多项式求值，请输入x的值:");
	scanf("%d",&b);
    a=value(Ha,b);//求x为elem的值
	printf("\n");

	printf("\n对一元多项式求导:\n");
	A=qiudao(Ha);//对Ha求导
	printf("A(x')=");
	print_list(A);

	printf("\ncreat Hb\n");
	Hb=creat_list(lb);//建链表二
	printf("B(x)=");
	print_list(Hb);

	printf("\n一元多项式相加:\n");
	La=add(Ha,Hb);//加法操作
	printf("\nA(x)+B(x)=");
	print_list(La);
	
	printf("\n一元多项式相减:\n");
    La=sub(Ha,Hb);//减法操作
	printf("\nA(x)-B(x)=");
	writer(La);
	//print_list(La);


    printf("\n一元多项式相乘:\n");
	La=mul(Ha,Hb);//乘法操作
	printf("\nA(x)*B(x)=");
	//trans(La);
	print_list(La);
}

PNode *creat_list(int n)
{//创造链表
	PNode *head,*p,*s; int i;
	head=(PNode *)malloc(sizeof(PNode));
	head->next=NULL;
	p=head;
	printf("enter coef,exp:\n");
	for(i=1;i<=n;i++)
	{
		s=(PNode *)malloc(sizeof(PNode));
		scanf("%d,%d",&s->coef,&s->exp);
		s->next=NULL;
		p->next=s;
		p=s;
	}
	return(head);
}


void print_list(PNode *h)
{//打印输出
	PNode *p;
	p=h->next;
	while(p->next)
	{
		printf("%dx^%d+",p->coef,p->exp);
		p=p->next;
	}
	if(p->exp)
		printf("%dx^%d\n",p->coef,p->exp);
	else 
		printf("%d\n",p->coef);
}

PNode *add(PNode *pa,PNode *pb)
{//多项式的加法运算
	PNode *qa,*qb,*head,*p;
	int sum;
	qa=pa->next;qb=pb->next;
	head=(PNode *)malloc(sizeof(PNode));
	head->next=NULL;
	p=head;	
	while(qa&&qb)
	{
		
		if(qa->exp == qb->exp)
		{
			
			sum=qa->coef+qb->coef;
            PNode *q=new PNode;
			if(sum==0)
				delete(q);		
			else
			{
			    q->coef=sum;
			    q->exp=qa->exp;
			    q->next=NULL;
				p->next=q;
				p=q;
			}
			    qa=qa->next;
			    qb=qb->next;		
			
		}


		else
		{
		
			if(qa->exp > qb->exp)
			{
				PNode * s=new PNode;
				s->coef=qa->coef;			
				s->exp=qa->exp;			
				s->next=NULL;
				p->next =s;
				p=s;
				qa=qa->next;
				
			}

			else
			{
				PNode * t=new PNode;
				t->coef=qb->coef;			
				t->exp=qb->exp;			
				t->next=NULL;
				p->next =t;
				p=t;
				qb=qb->next;											

			}
		}
	}

	while(qa)
		{
			PNode * w=new PNode;
				w->coef=qa->coef;			
				w->exp=qa->exp;			
				w->next=NULL;
				p->next =w;
				p=w;
				qa=qa->next;

		}
	 while(qb)
	 {
		 PNode * v=new PNode;
				v->coef=qb->coef;			
				v->exp=qb->exp;			
				v->next=NULL;
				p->next =v;
				p=v;
				qb=qb->next;
	 }
	
	
	return (head);

}

PNode *sub(PNode *pa,PNode *pb)
{//多项式的减法运算
	PNode *qa,*qb,*head,*p;
	int sum;
	qa=pa->next;qb=pb->next;
	head=(PNode *)malloc(sizeof(PNode));
	head->next=NULL;
	p=head;	
	while(qa&&qb)
	{
		
		if(qa->exp == qb->exp)
		{
			
			sum=qa->coef-qb->coef;
            PNode *q=new PNode;
			if(sum==0)
				delete(q);		
			else
			{
			    q->coef=sum;
			    q->exp=qa->exp;
			    q->next=NULL;
				p->next=q;
				p=q;
			}
			    qa=qa->next;
			    qb=qb->next;		
			
		}


		else
		{
		
			if(qa->exp > qb->exp)
			{
				PNode * s=new PNode;
				s->coef=qa->coef;			
				s->exp=qa->exp;			
				s->next=NULL;
				p->next =s;
				p=s;
				qa=qa->next;
				
			}

			else
			{
				PNode * t=new PNode;
				t->coef=-qb->coef;			
				t->exp=qb->exp;			
				t->next=NULL;
				p->next =t;
				p=t;
				qb=qb->next;											

			}
		}
	}

	while(qa)
		{
			PNode * w=new PNode;
				w->coef=qa->coef;			
				w->exp=qa->exp;			
				w->next=NULL;
				p->next =w;
				p=w;
				qa=qa->next;

		}
	 while(qb)
	 {
		 PNode * v=new PNode;
				v->coef=-qb->coef;			
				v->exp=qb->exp;			
				v->next=NULL;
				p->next =v;
				p=v;
				qb=qb->next;
	 }
	
	
	return (head);

}

int value(PNode * pa,int elem)
{//求x为elem的值
	PNode *pre,*p;
	pre=pa;
	p=pa->next;
	int temp=1;
	int he=0;
	while(p)
	{		
			temp=p->coef;
		for(int i=0;i<p->exp;i++)
		{			
				temp*=elem;
		}
		he=he+temp;
		p=p->next;
		
	}
	printf("A(%d)=",elem);
	printf("%d",he);
	return 1;
}

PNode *qiudao(PNode *pa)
{//求导
	PNode *qa,*head,*p,*q;
	
	qa=pa;
	p=qa->next ;
	head=(PNode *)malloc(sizeof(PNode));
	head->next=NULL;
	q=head;
	while(p)
	{
		if(p->exp)
		{
		    PNode * t=new PNode;
		    t->coef=p->coef*p->exp ;			
		    t->exp=p->exp-1;			
		    t->next=NULL;			
		    p=p->next;
		    q->next=t;
		    q=t;
		}
		else
		{
			PNode * s=new PNode;
		    s->coef=0 ;			
		    s->exp=0;			
		    s->next=NULL;			
		    p=p->next;
		    q->next=s;
		    q=s;
		}

	}
	return (head);
}

PNode *mul(PNode *pa,PNode *pb)
//实现多项式的乘法
{
	PNode *qa,*qb,*head,*p;
	qa=pa->next;qb=pb->next;
	head=(PNode *)malloc(sizeof(PNode));
	head->next=NULL;
	p=head;	
	while (qa)
	{
		while (qb)
		{
			PNode *r = new PNode ;
			r->coef = qa->coef*qb->coef;
			r->exp = qa->exp+qb->exp;
			r->next = NULL;
			qb=qb->next;
			p->next= r;
			p = r;
		}
		qb = pb->next;
		qa = qa->next;
	}
	
    //trans(head);
	PNode *q;      //对多项式进行合并同类项
	p=head->next ;
	while(p)
	{
		PNode *t=p ;
		while(t->next )
		{
			if(t->next->exp == p->exp )
			{	
				int summ=p->coef+t->next->coef ;
				p->coef =summ;
			    q=t->next ;
			    t->next =q->next ;
				delete q;
				
				t=t->next;
			}
			else
				t=t->next;
		}
		p=p->next ;
	}



	return head;
}


void writer(PNode *g)
{//打印输出
	PNode *p=g->next;
	while(p)
	{
		printf("%d",p->coef);
		if(p->exp)
			printf("x^%d",p->exp);
		if(p->next&&p->next ->coef >0)
			printf("+");
		p=p->next ;

	}
	printf("\n\n");
}

void trans(PNode *pa)
{
	PNode *p,*q;
	p=pa->next ;
	while(p)
	{
		PNode *t=p ;
		while(t->next  )
		{
			if(t->next ->exp==p->exp )
			{	
				int summ=p->coef+t->next->coef ;
				p->coef =summ;
			    q=t->next ;
			    t->next =q->next ;
				delete q;
				
				t=t->next;
			}
			else
				t=t->next;
		}
		p=p->next ;
	}

}