#include<stdio.h>
#include<stdlib.h>
typedef  struct NODE
{
    int a;
    int n;
    struct NODE *next;
}Node;
Node *create();
void output(Node*);
Node* Add(Node*, Node*);
void Paixu(Node *);
int main()
{
    Node *p, *q,*h;
    p = create();
    q = create();
    Paixu(q); Paixu(p);
    printf("第一个多项式为：\n");
    output(p); printf("\n");
    printf("第二个多项式为：\n");
    output(q); printf("\n");
    h=Add(p, q);
    printf("二个多项式之和为：\n");
    output(h);printf("\n");
    return 0;
}
Node *create()
{
    int  n,i;
    Node *p, *h = NULL, *q = NULL;
    printf("请输入多项式项数：");
    scanf("%d", &n);
    printf("请分别输入系数与次数：\n");
    for ( i = 0; i < n; i++)
    {
        p = (Node*)malloc(sizeof(Node));
        scanf("%d%d", &p->a, &p->n);
        if (h == NULL) h = p;
        else q->next = p;
        q = p;
    }
    q->next = NULL;
    return h;
}
void output(Node *h)
{
    if (h != NULL)
    {
        if (h->next != NULL) printf("%dx^%d + ", h->a, h->n);
        else printf("%dx^%d", h->a, h->n);
        output(h->next);

    }
}
Node* Add(Node *a, Node*b)
{
    Node *p, *q, *pre, *t,*h1,*h2;
    int s;
    h1 = (Node*)malloc(sizeof(Node)); h1->next = a;
    h2 = (Node*)malloc(sizeof(Node)); h2->next = b;
    p = a; q = b;
    pre = h1;
    while (p != NULL&&q != NULL)
    {
        if (p->n < q->n)
        {
            pre->next = p;
            pre = pre->next;
            p = p->next;
        }
        else if (p->n == q->n)
        {
            s = p->a+q->a;
            if (s != 0)
            {
                p->a = s;
                pre->next = p;
                pre = pre->next;
                p = p->next;
                t = q;
                q = q->next;
                free(t);
            }
            else
            {
                t = p->next;
                free(p);
                p = t;
                t = q->next;
                free(q);
                q = t;
            }
        }
        else
        {
            pre->next = q;
            pre = pre->next;
            q = q->next;
        }
    }
    if (p != NULL)
        pre->next = p;
    else
        pre->next = q;
    return h1->next;
}
void Paixu(Node *h)
{
    int p, t,m;
    Node *q, *r;
    do
    {
        p = h->n; q = h; r = h;
        do
        {

            if (r->n < p) { p = r->n; q = r; }
            r = r->next;
        } while (r != NULL);
        if (r != h) { t = h->n; m = h->a; h->n = q->n; h->a = q->a; q->n = t; q->a = m; }
        h = h->next;
    } while (h != NULL);
}