两个多项式的相加操作 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->expexp,则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
#include
#include
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)          
	{
		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)
  {   
  		PNode *LA1=LA->next;    
  		PNode *LB1=LB->next;     
  		
  		PNode *temp;          
		  int sum=0;      
		  while(LA1&&LB1)
		  {
		  	if(LA1->expexp)
		  	{
		  		LA->next=LA1;     
		  		LA=LA->next;
		  		LA1=LA1->next;
			  }
			  else if(LA1->exp==LB1->exp)   
			  {
			  	sum=LA1->coef+LB1->coef;
				  if(sum)   
				  {
				  	LA1->coef=sum;
					LA->next=LA1;
		            LA=LA->next;
		            LA1=LA1=LA1->next;
		            temp=LB1;
		            LB1=LB1->next;
		            free(temp);
				   } 
				   else     
				   {
				   	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;  
	Plinklist 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);    
	printf("n"); 
}

 5.测试结果：

                                                                              图2  测试结果图

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