1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <stdlib.h>
 
typedef struct ListNode { // 노드 타입
    int coef;
    int expon;
    struct ListNode *link;
} ListNode;
 
// 연결 리스트 헤더
typedef struct ListType { // 리스트 헤더 타입
    int size;
    ListNode *head;
    ListNode *tail;
} ListType;
 
// 오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
//  리스트 헤더 생성 함수
ListType* create()
{
    ListType *plist = (ListType *)malloc(sizeof(ListType));
    plist->size = 0;
    plist->head = plist->tail = NULL;
    return plist;
}
 
// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, 
// expon는 지수
void insert_last(ListType* plist, int coef, int expon)
{
    ListNode* temp =
        (ListNode *)malloc(sizeof(ListNode));
    if (temp == NULL) error("메모리 할당 에러");
    temp->coef = coef;
    temp->expon = expon;
    temp->link = NULL;
    if (plist->tail == NULL) {
        plist->head = plist->tail = temp;
    }
    else {
        plist->tail->link = temp;
        plist->tail = temp;
    }
    plist->size++;
}
 
// list3 = list1 + list2
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
    ListNode* a = plist1->head;
    ListNode* b = plist2->head;
    int sum;
 
    while (a && b) {
        if (a->expon == b->expon) {   // a의 차수 > b의 차수
            sum = a->coef + b->coef;
            if (sum != 0) insert_last(plist3, sum, a->expon);
            a = a->link; b = b->link;
        }
        else if (a->expon > b->expon) {  // a의 차수 == b의 차수 
            insert_last(plist3, a->coef, a->expon);
            a = a->link;
        }
        else {                    // a의 차수 < b의 차수
            insert_last(plist3, b->coef, b->expon);
            b = b->link;
        }
    }
 
    // a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 
    // 결과 다항식으로 복사
    for (; a != NULL; a = a->link)
        insert_last(plist3, a->coef, a->expon);
    for (; b != NULL; b = b->link)
        insert_last(plist3, b->coef, b->expon);
}
 
//
//
void poly_print(ListType* plist)
{
    ListNode* p = plist->head;
 
    printf("polynomial = ");
    for (; p; p = p->link) {
        printf("%d^%d + ", p->coef, p->expon);
    }
    printf("\n");
}
 
//
int main(void)
{
    ListType *list1, *list2, *list3;
 
    // 연결 리스트 헤더 생성
    list1 = create();
    list2 = create();
    list3 = create();
 
    // 다항식 1을 생성 
    insert_last(list1, 3, 12);
    insert_last(list1, 2, 8);
    insert_last(list1, 1, 0);
 
    // 다항식 2를 생성 
    insert_last(list2, 8, 12);
    insert_last(list2, -3, 10);
    insert_last(list2, 10, 6);
 
    poly_print(list1);
    poly_print(list2);
 
    // 다항식 3 = 다항식 1 + 다항식 2
    poly_add(list1, list2, list3);
    poly_print(list3);
 
    free(list1); free(list2); free(list3);
}
cs