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

typedef struct node 
{
    float coef; 
    int exp;
    struct node *next; 
}node; 

node* CreatPolynode(node *P,int m) 
{ 
    if(m <= 0) return NULL; 
    node *h = P = (node*)malloc(sizeof(node)), *q; 
    P->coef = 0.0; 
    int i; 
    printf("依次輸入%d個數（前一個為系數，后一個為指數）\n",m*2); 
    for (i = 1; i <= m; ++i) 
	{  
        scanf("%f%d",&P->coef,&P->exp); 
        if(P->coef) 
        q = P; 
        P = P->next = (node*)malloc(sizeof(node)); 
	} 
    q->next = NULL; 
    free(P); 
    return h; 
} 

node* selsort(node *h) 
{ 
    node *g, *p, *q; 
    if(!h) return NULL; 
    float f; 
    int i, fini = 1; 
    for(g = h;g->next&&fini;g = g->next) 
	{ 
        fini = 0; 
        for(p = h,q = h->next;q;p = p->next,q = q->next) 
        if (p->exp < q->exp) 
		{ 
            f = p->coef;i = p->exp; 
            p->coef = q->coef;p->exp = q->exp; 
            q->coef = f;q->exp = i; 
            fini = 1; 
		} 
	} 
    for(g = h,p = g->next;p;) 
    if(g->exp==p->exp) 
	{ 
        g->coef += p->coef; 
        g->next = p->next; 
        q = p; 
        p = p->next; 
        free(q); 
	} 
    else if(g->next) 
	{ 
        g = g->next; 
        p = p->next; 
	} 
    return h; 
} 

void PrintfPoly(node *P) 
{ 
    node *q = P; 
    if(!q) 
	{ 
        putchar('0'); 
        return; 
	} 
    if(q->coef!=1) 
	{ 
        printf("%g",q->coef); 
        if(q->exp==1) putchar('X'); 
        else if(q->exp) printf("X^%d",q->exp); 
	} 
    else if(!q->exp) putchar('1'); 
    else if(q->exp==1) putchar('X'); 
    else printf("X^%d",q->exp); 
    q = q->next; 
    while (q) 
	{ 
        if(q->coef > 0) putchar('+'); 
        if(q->coef!=1) 
		{ 
            printf("%g",q->coef); 
            if(q->exp==1) putchar('X'); 
            else if(q->exp) printf("X^%d",q->exp); 
		} 
        else if(!q->exp) putchar('1'); 
        else if(q->exp==1) putchar('X'); 
        else printf("X^%d",q->exp); 
        q = q->next; 
	} 
} 

Compare(node *a, node *b) 
{ 
    if (a->exp < b->exp) return -1; 
    if (a->exp > b->exp) return 1; 
    return 0; 
} 

node* APolynode(node *Pa, node *Pb) 
{ 
    node *h, *qa = Pa, *qb = Pb, *p, *q; 
    float sum; 
    h = p = (node*)malloc(sizeof(node)); 
    p->next = NULL; 
    while (qa && qb) 
	{ 
        switch (Compare(qa,qb)) 
		{ 
            case -1:  
            p->next = qb; 
            p = qb; 
            qb = qb->next; 
            break; 
            case 0:  
            sum = qa->coef + qb->coef; 
            if (sum != 0.0) 
			{  
                p->next = qa; 
                qa->coef = sum; 
                p = qa; 
                qa = qa->next; 
			} 
            else 
			{  
                q = qa; 
                qa = qa->next; 
                free(q); 
			} 
            q = qb; 
            qb = qb->next; 
            free(q); 
            break; 
            case 1: 
            p->next = qa; 
            p = qa; 
            qa = qa->next; 
            break; 
		} 
	} 
    if (Pa) p->next = qa;  
    if (Pb) p->next = qb;  
    q = h; 
    h = h->next; 
    free(q); 
    return h; 
} 

node* A(node *Pa, node *Pb) 
{ 
    int n; 
    puts("輸入第二個一元多項式的項數："); 
    scanf("%d",&n); 
    Pb = CreatPolynode(Pb,n); 
    Pb = selsort(Pb); 
    PrintfPoly(Pa); 
    if(Pb && Pb->coef>0) printf(" + "); 
    PrintfPoly(Pb); 
    Pa = APolynode(Pa,Pb); 
    printf(" = "); 
    Pa = selsort(Pa); 
    PrintfPoly(Pa); 
    return Pa; 
} 


void main() 
{ 
    node *M,*N; 
    char s[2]; 
    int i,n; 
    puts("一元多項式計算:\n輸入第一個一元多項式的項數："); 
    scanf("%d",&n); 
    M = CreatPolynode(M,n); 
    M = selsort(M); 
    PrintfPoly(M);
    p: puts("\n1:加\n2:下一步"); 
    getchar(); 
    q: gets(s); 
    if(s[1]!='\0' || !isdigit(*s)) 
	{ 
        puts("輸入有誤,請重新輸入!");goto q; 
	} 
    i = *s-48; 
    switch(i) 
	{ 
        case 1:M = A(M,N);goto p;; 
        case 2:break; 
        default:puts("輸入有誤,請重新輸入!");goto q; 
	} 
}