자료구조 :: 리스트(5) 연결리스트를 이용한 다항식

# 단순 연결리스트를 이용한 다항식

Polynomial.cpp

다항식의 노드는 계수(coef)와 지수(expon), 링크(link) 필드로 구성되어 있다.
다항식의 경우 두개의 리스트 a,b 에 각각 다항식 노드를 연결하고 a와b의 항들을 따라 순회하면서
각 항들을 더하면된다. a와b가 가리키는 항의 지수에 따라 3가지의 경우로 나누어 처리할 수 있다.

① a.expon == b.expon :
두 지수가 같은경우 계수를 계산하고 새로운 항을 만들어 다항식 리스트 c에 추가한다.

② a.expon < b.expon :
b의 항을 다항식 리스트 c에 추가하고 b만 다음 노드로 이동한다.

③ a.expon > b.expon :
a의 항을 다항식 리스트 c에 추가하고 a만 다음 노드로 이동한다.

위 과정은 a,b 둘중 하나가 NULL이 될때까지 반복되어야 하며 둘중 하나가 NULL이 되면 남은 다항식 노드를
다항식 리스트 c에 전부다 추가 하면된다.

단순 연결리스트의 불편한점을 개선시키기 위해 이중으로된 헤드 노드를 만들어서 리스트의 처음과 끝을 항상
유지 할 수 있도록 구성한다. 헤드 노드는 끝을 항상 유지하므로써 새로운 노드를 추가할 때 마지막 노드까지
가야 하는 번거로움을 줄일 수 있다.

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

typedefstruct NODE 
{ 
int coef;  // 계수
int expon; // 지수
    NODE *link; 
}NODE; 

typedefstruct LISTHEAD 
{ 
int lenght; // 노드의 총 길이(갯수)
    NODE *head; // NODE의 시작 부분
    NODE *tail; // NODE의 끝 부분
}LISTHEAD; 


void Init(LISTHEAD *pList) // 이중 연결 구조를 가지는 head 노드 초기화
{ 
    pList->lenght=0; 
    pList->head=pList->tail=NULL; 
} 

NODE* Insert_Node(LISTHEAD *pList,int coef,int expon) 
{ 
    NODE *New_Node=(NODE*)malloc(sizeof(NODE)); 
if(New_Node == NULL) 
    { 
        printf("메모리 할당 에러"); 
        exit(1); 
    } 

    New_Node->coef=coef; 
    New_Node->expon=expon; 
    New_Node->link=NULL; 

if(pList->tail==NULL) 
    { 
        pList->head=pList->tail=New_Node; 
    } 
else
    { 
        pList->tail->link = New_Node; // NODE 데이터 연결
        pList->tail = New_Node; // HEAD노드의 tail은 새로 추가된 노드를 가리킴
    } 
    pList->lenght++; 
} 

// 계산 할 리스트 2개와 저장 리스트 1개
void Poly_Add(LISTHEAD *pList1,LISTHEAD *pList2,LISTHEAD *pList3)  
{ 
    NODE *a,*b; 
int sum; 

    a=pList1->head; 
    b=pList2->head; 

while(a && b) 
    { 
if(a->expon == b->expon) 
        { 
            sum=a->coef+b->coef; 

if(sum != 0) 
            { 
                Insert_Node(pList3,sum,a->expon); 
                a=a->link; 
                b=b->link; 
            } 
        } 
elseif(a->expon < b->expon) 
        { 
            Insert_Node(pList3,b->coef,b->expon); 
            b=b->link; 
        } 
else
        { 
            Insert_Node(pList3,a->coef,a->expon); 
            a=a->link; 
        } 
    } 

while(a!=NULL) 
    { 
        Insert_Node(pList3,a->coef,a->expon); 
        a=a->link; 
    } 

while(b!=NULL) 
    { 
        Insert_Node(pList3,b->coef,b->expon); 
        b=b->link; 
    } 
} 

void Poly_Print(LISTHEAD *pList) 
{ 
    NODE *p=pList->head; 

while(p!=NULL) 
    { 
        printf("%dx%d ",p->coef,p->expon); 
        p=p->link; 
    } 
    printf("\n"); 
} 
int main() 
{ 
    LISTHEAD list1,list2,list3; 

    Init(&list1); 
    Init(&list2); 
    Init(&list3); 

// LIST1 = 10x5 + 7x3 + 3x2 + 2

    Insert_Node(&list1,10,5); 
    Insert_Node(&list1,7,3); 
    Insert_Node(&list1,3,2); 
    Insert_Node(&list1,2,0); 

// LIST2 = 4x5 + 2x4 - 5x3 + 8x2 + 7

    Insert_Node(&list2,4,5); 
    Insert_Node(&list2,2,4); 
    Insert_Node(&list2,-5,3); 
    Insert_Node(&list2,8,2); 
    Insert_Node(&list2,7,0); 

    Poly_Add(&list1,&list2,&list3); 

    Poly_Print(&list3); // LIST3 = 14x5 + 2x4 + 2x3 + 11x2 + 9x0 

return0; 

}