#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define OVERFLOW -2
#define FALSE -1
#define OK 0

#define ElemType  int 

 struct LNode{
	ElemType coefficient;//系数 
	ElemType power; //幂次 
	struct LNode *next;
}LNode,*LinkList;
//有序化建立链表
struct LNode *Create_Link(struct LNode *head,int LNode_number){
	struct LNode *ptemp,*pfront,*pnew;
	int i,tempC,tempP,flag=0;
	pnew=(struct LNode *)malloc(sizeof(LNode));
	head=pnew;
	pnew->next=NULL;//头结点的初始化 
	//第一个结点
	pnew=(struct LNode *)malloc(sizeof(LNode));
	pnew->next=NULL;
	scanf("%d %d",&tempC,&tempP);
	pnew->coefficient=tempC;
	pnew->power=tempP;
	head->next=pnew;
    for(i=1;i<LNode_number;i++){
		pnew=(struct LNode *)malloc(sizeof(LNode));
		pnew->next=NULL;
		scanf("%d %d",&tempC,&tempP);
		pnew->coefficient=tempC;
	    pnew->power=tempP;
	    //所插入的元素的幂小于第一个结点的元素的幂 
	    if(pnew->power<head->next->power){
	    	pnew->next=head->next;
			head->next=pnew; 
	    }
	    else{
	    	//所插入的元素的幂大于最后一个结点的元素的幂 
	    	ptemp=head;
	    	ptemp=ptemp->next;
	    	while(ptemp->power<=pnew->power){
	    	  pfront=ptemp;
			  ptemp=ptemp->next;
	    	  if(ptemp==NULL){
	    	  	pfront->next=pnew;
	    	  	flag=1;
				break; //此处得加break，不然没有结束while循环，导致错误 
	          }
	        }
		    //所插入的元素的幂介于最大值与最小值之间 
		    if(flag==0){
			pnew->next=ptemp;
		    pfront->next=pnew;
		    }
	} 
}
   return  head;
} 

struct LNode *polynomials_sum(struct LNode *Link1_head,struct LNode *Link2_head){
	struct LNode *pnew,*ptemp,*pLink1,*pLink2,*pLink3_head;
	pLink1=Link1_head;
	pLink2=Link2_head;
	pLink1=pLink1->next;
	pLink2=pLink2->next;
	//Link3：开辟头结点 
	pnew=(struct LNode*)malloc(sizeof(LNode));
	pLink3_head=pnew;//pLink3为指向头结点的指针 
	pnew->next=NULL;
	ptemp=pnew;
	// 第一个结点的特殊之处 
    while((pLink1!=NULL)&&(pLink2!=NULL)){
    	if(pLink1->power==pLink2->power){
    		pnew=(struct LNode*)malloc(sizeof(LNode));
    		pnew->next=NULL;
			pnew->power=pLink1->power;
			pnew->coefficient=pLink1->coefficient+pLink2->coefficient;
			ptemp->next=pnew;
			ptemp=ptemp->next;
			pLink1=pLink1->next;
			pLink2=pLink2->next; 
    	}
    	else{
    		if(pLink1->power<pLink2->power){
    			pnew=(struct LNode*)malloc(sizeof(LNode));
    			pnew->next=NULL;
				pnew->power=pLink1->power;
    			pnew->coefficient=pLink1->coefficient;
    			ptemp->next=pnew;
			    ptemp=ptemp->next;
    			pLink1=pLink1->next;
    		}
    		else{
    			pnew=(struct LNode*)malloc(sizeof(LNode));
    			pnew->next=NULL;
    			pnew->power=pLink2->power;
    			pnew->coefficient=pLink2->coefficient;
    			ptemp->next=pnew;
			    ptemp=ptemp->next;
    			pLink2=pLink2->next;
    		}
    	}
    }
    if(pLink1==NULL){
    	while(pLink2!=NULL){
    		pnew=(struct LNode*)malloc(sizeof(LNode));
    		pnew->next=NULL;
    		pnew->power=pLink2->power;
    		pnew->coefficient=pLink2->coefficient;
    		ptemp->next=pnew;
    		ptemp=ptemp->next;
    		pLink2=pLink2->next;
    	}
    }
    else{
    	while(pLink1!=NULL){
    		pnew=(struct LNode*)malloc(sizeof(LNode));
    		pnew->next=NULL;
    		pnew->power=pLink1->power;
    		pnew->coefficient=pLink1->coefficient;
    		ptemp->next=pnew;
    		ptemp=ptemp->next;
    		pLink1=pLink1->next;
    	}
    }
    return pLink3_head;
}

int main(){
	struct LNode *Link1_head,*Link2_head,*Link3_head, *ptemp;
	int number;
	printf("input the number of A(X):");
	scanf("%d",&number);
	printf("please input A(X):\n"); 
	Link1_head=Create_Link(Link1_head,number);
	ptemp=Link1_head->next;
	printf("output the member of A(X):\n");
    while(ptemp!=NULL){
    	printf("%d ",ptemp->coefficient);
    	printf("%d      ",ptemp->power);
    	ptemp=ptemp->next;
    }
    printf("\n");
    printf("input the number of B(X):");
	scanf("%d",&number);
	printf("please input B(X):\n"); 
	Link2_head=Create_Link(Link2_head,number);
	ptemp=Link2_head->next;
	printf("output the member of B(X):\n");
    while(ptemp!=NULL){
    	printf("%d ",ptemp->coefficient);
    	printf("%d      ",ptemp->power);
    	ptemp=ptemp->next; 
    }
    printf("\n");
    Link3_head=polynomials_sum(Link1_head,Link2_head);
    ptemp=Link3_head->next;
	printf("output the member of A(X)+B(X):");
    while(ptemp!=NULL){
    	printf("%d ",ptemp->coefficient);
    	printf("%d      ",ptemp->power);
    	ptemp=ptemp->next;
    }
    printf("\n");
    
    system("pause");
    return OK;
}