[数据结构与算法]两个多项式的相加操作 C语言（链式存储结构）

内容:

? ? ? ?完成两个多项式的相加操作：已知有两个多项式P(x)，Q(x)，设计算法实现P(x)+Q(x)运算。而且对加法运算不重新开辟存储空间。要求用链式存储结构。

? ? ? ?例如：P(x)=5x^3+2x+1,Q(x)=3x^3+x^2-2x-3,其计算输出结果为：8x^3+1x^2-2.

相减操作，以上述为例，则其输出结果为：2x^3-x^2-4x-2

步骤：

1.问题分析和算法设计：

? ? ? 多项式加法：本题的需要求出两个多项式的和，因此需要先使用Init()来初始化一个空链表，再使用CreateFromTail()用来创建一个链表，在此程序中使用尾插法来创建链表。对于两个多项式的加法，使用Polyadd()用来实现两个多项式的相加算法；用Print()输出多项式。

? ? ? ?两个多项式相加算法的实现，首先是将两个多项式分别用链表进行存放。可以设置两个指针LA1和LB1分别从多项式P(x)和Q(x)的首结点移动，比较LA1和LB1所指结点的指数项，分下面三种情况进行处理：

(1)若LA1->exp<LB1->exp,则LA1所指结点为多项式中的一项，LA1指针在原来的基础上向后移动一个位置。

(2)若LA1->exp=LB1->exp,将对应项的系数相加，然后分两种情况处理：如果系数的和为0，则释放LA1和LB1所指向的结点：如果系数项的和不为0，则修改LA1所指向结点的系数域，释放LB1结点。

(3)若LA1->exp>LB1->exp,则LB1所指结点为多项式中的一项，LB1指针在原来的基础上向后移动一个位置。

2.概要设计：

3.程序运行流程图：

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图1? 程序流程图

4.源代码（vc++6.0调试通过）

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct poly
{
	int exp;           /*指数幂*/
	int coef;          /*系数*/
	struct poly *next;  /*指针域*/
 }PNode,*PLinklist;
 int Init(PLinklist *head)   /*链表初始化*/
 {
 	*head=(PLinklist)malloc(sizeof(PNode));
 	if(*head)
 	{
 		(*head)->next=NULL;
 		return 1;
	 }
	 else
	 	return 0;
 }
int CreateFromTail(PLinklist *head)  /*尾插法创建链表*/
{
 	PNode *pTemp,*pHead;
 	int c;               /*存放系数*/
 	int exp;             /*存放指针*/
	int i=1;             /*计数器提示用户输入第几项*/ 
	pHead=*head;
	scanf("%d,%d",&c,&exp);
	while(c!=0)          /*系数为0表示结束输入*/
	{
		pTemp=(PLinklist)malloc(sizeof(PNode));
		if(pTemp)
		{
			pTemp->exp=exp;  /*接收指数*/
			pTemp->coef=c;    /*接收系数*/
			pTemp->next=NULL;
			pHead->next=pTemp;
			pHead=pTemp;
			scanf("%d,%d",&c,&exp);
		}
		else
			return 0;
	 } 
	 return 1;
  } 
  void Polyadd(PLinklist LA,PLinklist LB)/*两个多项式相加，该方法两个表都是按指数顺序增长*/
  {   /*对指数进行对比分三类情况；A<B时将A链到LA后，A==B时比较系数，A>B时将B链到表中*/
  		PNode *LA1=LA->next;    /*用于在LA中移动*/
  		PNode *LB1=LB->next;     /*用于在LB中移动*/
  		/*LA与1B在充当LA1和LB1的前驱*/
  		PNode *temp;          /*保存要删除的结点*/
		  int sum=0;      /*存放系数的和*/
		  while(LA1&&LB1)
		  {
		  	if(LA1->exp<LB1->exp)
		  	{
		  		LA->next=LA1;     /*LA的当前结点可能时LB1或LA1*/
		  		LA=LA->next;
		  		LA1=LA1->next;
			  }
			  else if(LA1->exp==LB1->exp)  /*指数相等系数相加*/ 
			  {
			  	sum=LA1->coef+LB1->coef;
				  if(sum)   /*系数不为0，结果存入LA1中，同时删除结点LB1*/
				  {
				  	LA1->coef=sum;
					LA->next=LA1;
		            LA=LA->next;
		            LA1=LA1=LA1->next;
		            temp=LB1;
		            LB1=LB1->next;
		            free(temp);
				   } 
				   else     /*系数为0时的情况下删除两个结点*/
				   {
				   	temp=LA1;
					LA1=LA1->next;
					free(temp);
					temp=LB1;
					LB1=LB1->next;
					free(temp); 
			  }
		   } 
		   else
		   {
		   	LA->next=LB1;
			LA=LA->next;
			LB1=LB1->next; 
		   }
		   
  }
  if(LA1)  /*将剩余结点链入链表*/
  		LA->next=LA1;
	else
		LA->next=LB1;
}
  void Print(PLinklist head) /*输出多项式*/
{
	head=head->next;
	while(head)
	{
		if(head->exp)
				printf("%dx^%d",head->coef,head->exp);
			else
				printf("%d",head->coef);
			if(head->next)
				printf("+");
			else
				break;
			head=head->next;
	}
}
void main()
{
	PLinklist LA;  /*多项式列表LA*/
	PLinklist LB;  /*多项式列表LB*/
	Init(&LA);
	Init(&LB);
	printf("输入第一个多项式的系数，指数（例如10，2）输入0，0结束输入\n");
	CreateFromTail(&LA);
	printf("输入第二个多项式的系数，指数（例如10，2）输入0，0结束输入\n");
	CreateFromTail(&LB);
	Print(LA);
	printf("\n");
	Print(LB);
	printf("\n");
	Polyadd(LA,LB);
	printf("两个多项式相加的结果：\n");
	Print(LA);    /*相加的结果保存在LA中，打印LA*/
	printf("\n"); 
}

?5.测试结果：

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 图2? 测试结果图

?以上为使用链式存储进行多项式加法的全部分析过程和操作。