#include<stdio.h>
#include<stdlib.h>
typedef struct  Node{
    int xishu;
    int mic;
    struct Node * next;
}Lnode, *Link;

void create_list(Link &head, int n)
{
    int i;
    Link rear, s;
    rear = head;
    for (i=1; i<=n; i++)
    {
        s = (Link)malloc(sizeof(Lnode));
        scanf("%d%d", &(s->xishu), &(s->mic));
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
}
void printf_list(Link head)
{
    Link p;
    p = head->next;
    while(p)
    {
        printf("%dx%d ", p->xishu, p->mic);
        p = p->next;
        if (p)
            if (p->xishu > 0) putchar('+');
    }
}
void polynomial_add(Link ha, Link hb, Link &hc)
{
    Link pa, pb, pc;
    pa = ha->next;        pb = hb->next;  pc = hc;
    while(pa && pb)
    {
        if (pa->mic < pb->mic)
        {
            pc->next = pa;    pc = pc->next;    pa = pa->next;
        }
        else if(pa->mic > pb->mic)
            {
            pc->next = pb;    pc = pc->next;  pb = pb->next;
            }
            else
            {
                int xsh;
                xsh = pa->xishu + pb->xishu;
                if (xsh)
                {
                    pa->xishu = xsh;
                    pc->next = pa;  pc = pc->next;
                }
                pa = pa->next;        pb = pb->next;
            }
    }
    if (pa)    pc->next = pa;
    if (pb) pc->next = pb;
}
int main()
{
    Link heada, headb, headc;
    int n;
    heada = (Link)malloc(sizeof(Lnode));
    headb = (Link)malloc(sizeof(Lnode));
    headc = (Link)malloc(sizeof(Lnode));
    printf("请输入多项式 A 的项数: ");
    scanf("%d", &n);
    printf("输入各项的系数和幂次: ");
    create_list(heada, n);
    printf("请输入多项式 B 的项数: ");
    scanf("%d", &n);
    printf("输入各项的系数和幂次: ");
    create_list(headb, n);
    polynomial_add(heada, headb, headc);
    printf("A+B的结果多项式为: ");
    printf_list(headc);

 
}