数据结构中之单链表实现多项式的加减

拼搏现实的明天。 2022-08-14 01:00 174阅读 0赞

一般情况多项式主要由系数，幂来进行表示。在多项式进行相加时，至少有两个或两个以上的多项式同时并存，而且运算过程中产生的中间多项式以及结果多项式的项数和指数都不可预测，因此在进行多项式相加时，采用顺序表时必然会产生大量的空间浪费，计算机中常采用链表来进行表示多项式。

1、多项式主要由系数和幂组成，因此表达多项式的链表结构如下所示：

typedef struct node
 {
 	float conf;	//多项式的系数;
 	int exp;	//多项式的幂数;
 	struct node* next;	
 }node;

2、 分析：假设链表ah表示多项式1，链表bh表示多项式2，链表ch表示多项式1与多项式2相加的结果链表。假设pa指向链表ah的表头，pb指向链表bh的表头，多项式相加时依次移动pa与pb，当pa!=NULL&&pb!=NULL时会存在以下三种情况：

（1）当pa->exp>pb->exp时，把pa的系数与幂数构建一个新的结点，加到新的结果链表ch中，同时pa指向下一结点，pb不变。

（2）当pa->exp==pb->exp时，把pa的系数相加，如果之和不为0的话，创建新的结点加到结果链表ch中，同时pa指向下一结点，pb也指向下一结点。

（3）当pa->exp<pb->exp时，同理，只不过pa保持不变，pb指向下一个结点。

执行完成后，如果还存在pa!=NULL或者pb!=NULL的情况，则把剩下的部分全部加到ch的链表中。

为了更方便的添加新的节点，这里先实现一个添加节点到ch链表的函数，并且把指针指向链表的尾部。

//在链表后面添加一个新的节点,并把pc指向该链表的表尾,注意需要传递指针的引用;
 void attach(float conf,int exp,node* &pc)
 {
     node* p=(node*)malloc(sizeof(node));
     p->conf=conf;
     p->exp=exp;
     pc->next=p;    
     pc=p;        
 }

3、编写多项式相加的算法，根据上文的分析，不难实现多项式相加的算法，如下所示：

/**
 	多项式A表达成单链表形式ah；
 	多项式B表达成单链表形式bh;
 	多项式C为运算后的结果表示成单链表的形式；
 */
 void Add(node* ah,node* bh, node* &ch)
 {
 	node* pa=ah;		//指向链表ah的表头;
 	node* pb=bh;		//指向链表bh的表头;
 
 	ch=(node*)malloc(sizeof(node));
 	node* pc=ch;
 	
 	while(pa!=NULL&&pb!=NULL)
 	{
 		if(pa->exp>pb->exp)	//如果多项式A的幂的系数大于多项式B的幂系数;
 		{
 			attach(pa->conf,pa->exp,pc);
 			pa=pa->next;			
 		}
 		else if(pa->exp==pb->exp) //如果多项式A的幂的系数等于多项式B的幂系数;
 		{
 			float sum=pa->conf+pb->conf;
 			if(sum!=0)
 			{
 				attach(sum,pa->exp,pc);
 				pa=pa->next;
 				pb=pb->next;
 			}
 		}
 		else if(pa->exp<pb->exp) //如果多项式A的幂的系数小于多项式B的幂系数;
 		{
 			attach(pb->conf,pb->exp,pc);
 			pb=pb->next;		
 		}	
 	}
 	while(pb!=NULL)
 	{
 		attach(pb->conf,pb->exp,pc);
 		pb=pb->next;
 	}
 	while(pa!=NULL)
 	{
 		attach(pa->conf,pa->exp,pc);
 		pa=pa->next;
 	}	
 
 	pc->next=NULL;
 	node* q=ch;
 	ch=ch->next;
 	free(q);
 }

4、总结：多项式相加的算法，时间主要是花费在比较和系数相加上，如果A(x)有m项，B(x)有n项，则该算法运动的时间为O（n+m）。