普通情况下，一元n次多项式可写成：

当中，pi是指数为ei的项的非零系数，且满足

因此。我们能够採用线性表（定义：线性表是由n个数据元素构成的有限序列，比方数组、向量、链表等等）来表示：

当中。每一项的指数i能够用其系数pi的序号表示。

       在通常的应用中，多项式的次数比較大，使得线性表的长度非常难确定，因此我们能够考虑链表，向量也能够（c++中）。举例说明：假如我们用数组来表示以下的多项式：

       可见。我们须要一个大小为1549的数组来表示。而实际实用的信息仅仅有数组中的4个元素，其它地方都是0，所以造成了空间浪费。而且假设我们事先不知道多项式的最高次项的指数，则我们须要定义一个足够大的数组来存储，这样做显然浪费了非常多内存空间。我们能够使用链表来解决上述问题：

       在计算机内，我们用一个结点来存放多项式的一项，为了节约空间。并和书写习惯一致。仅仅需保留非零系数的项。每一个结点分系数、指数和指针三个域，例如以下图所看到的。当中的指针next指明下一项的位置。

比如。以下多项式分别为A，B:

        

用循环链表能够表演示样例如以下：

       两个多项式相加的运算规则非常easy，对全部指数同样的项，将其相应系数相加，若和不为零，则构成和多项式中的一项。将全部指数不同样的项拷贝到和多项式中。详细实现时，我们以上面的多项式A，B为測试例子。可採用另建链表来存储和的多项式的方法。或採用把一个多项式归并入还有一个多项式的方法。我们以后种方法为例,即将A+B的和多项式存储到A中。详细程序实现例如以下（我採用了循环链表）：

#include
     
      #include
      
       #include
       
        typedef struct pnode//用链表来存储多项式信息{	float coef;//多项式系数	int   exp;//多项式指数	struct pnode *next;}polynode;polynode *Create(){	float coef;	int exp;	polynode *head,*s,*r;	head=(polynode*)malloc(sizeof(polynode));	head->coef=0;	head->exp=-1;	r=head;	printf("请输入各项的系数和指数：\n");	while(1)	{		scanf("%f %d",&coef,&exp);		if(coef!=0)//输入0 0来结束输入		{			s=(polynode*)malloc(sizeof(polynode));			s->coef=coef;//s用来保存当前节点			s->exp=exp;			r->next=s;			r=s;		}		else			break;	}	r->next=head;//构造循环链表	return head;}polynode*PolyAdd(polynode* pa,polynode* pb)//进行多项式相加{	polynode *p,*q,*r,*s;	float x;	p=pa->next;//分别指向多项式的第一项	q=pb->next;	s=pa;//s用于保存当前节点	while((p!=pa)&&(q!=pb))//没有结束，回到链表头	{		if(p->exp
        
         exp)//p的指数小于q的指数，将p放入链表中		{			s=p;			p=p->next;		}		else if(p->exp>q->exp)//p的指数大于q的指数。将q放入链表中		{			r=q->next;			q->next=p;			s->next=q;			s=q;			q=r;		}		else//当两者指数同样时。进行合并		{			x=p->coef+q->coef;			if(x!=0)			{				p->coef=x;				s=p;			}			else//若合并结果为0，将该节点移除			{				s->next=p->next;				free(p);			}					p=s->next;		r=q;		q=q->next;		free(r);		}	}	if(q!=pb)//假设多项式b的项数少于多项式a的情况	{		r=q;		while(r->next!=pb)			r=r->next;		s->next=q;		r->next=pa;	}	return pa;}void Output(polynode *head)// 输出多项式信息{	polynode *p;	printf("系数和指数分别为：");	p=head->next;	while(p!=head)	{		printf("%.1f , %d    ",p->coef,p->exp);		p=p->next;	}	printf("\n");}void main(){	polynode* ha,*hb;	printf("\n建立多项式A:");	ha=Create();	Output(ha);	printf("\n建立多项式B:");	hb=Create();	Output(hb);	ha=PolyAdd(ha,hb);	printf("\n多项式A+B：");    Output(ha);}
        
       
      
     

执行结果例如以下：

原文：

作者：nineheadedbird

版权声明：本文博客原创文章，博客，未经同意，不得转载。