# Linked List練習

[toc]

## Additional of Polynomials
cyclic linked list

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

using namespace std;

struct Node   //user defined data type   |4bytes|4bytes|*8bytes|-->|  |  |  |
{
    int coef;
    int expo;
    struct Node * next;
};            //可以被引用, 尚未有實體空間

struct Node *a_first, *b_first, *c_first, *a_last, *b_last, *c_last;

struct Node * newHeader(int coef, int expo)    //一個空白節點用來避開空串列
{
    struct Node * r = (struct Node*)malloc(sizeof(Node));
    r->coef = coef; r->expo = expo;
    r -> next = r;
    return r;
}

struct Node * copyTerm(struct Node*s)
{
    struct Node *r = (struct Node*)malloc(sizeof(Node));
    *r = *s;
    return r;
}

struct Node * AttachLast(struct Node *last, struct Node *z)
{
    z->next = last->next;
    last->next = z;
    last = z;
    return last;
}

struct Node *clearList(struct Node *a)
{
    struct Node *p, *q;
    for(p=a->next; p!=a; q=p, p=q->next, free(q));
    p->next = a;
    return p;
}

struct Node *clearListHeader(struct Node *a)
{
    struct Node *p, *q;
    for(p=a->next; p!=a; q=p, p=q->next, free(q));
    free(a);
    return NULL;
}

struct Node *PolyAdd(struct Node* a_first, struct Node* b_first)
{
    struct Node *x, *y, *z;
    int coef;
    c_last = c_first = newHeader(0, -1);
    for(x = a_first->next, y=b_first->next; (x!=a_first||y!=b_first);)
    {
        if(x->expo == y->expo){
            if((coef = x->coef + y->coef)!=0){
                z = copyTerm(x);
                z->coef = coef;
            }
            x = x->next; y->next;
        }else if(x->expo > y->expo){
            z = copyTerm(x);
            x = x->next;
        }else{
            z = copyTerm(y);
            y = y->next;
        }
        if (coef) c_last = AttachLast(c_last, z);
    }
    return c_first;
}

void show(struct Node *a)
{
    while(a->next != a){
        printf("%dx^%d", a->coef, node->expo);
        a = a->next;
        if(a->coef >= 0){
            if(a->next!=NULL)
                printf("+");
        }
    }
}

int main()
{

}