자료구조 과제

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

typedef struct ListNode *ListPointer;

typedef struct ListNode {
int coef; //계수 저장할 변수
int expo; //지수를 저장할 변수
ListPointer link; //노드를 가리키는 link.
} ListNode;

ListPointer avail; // 포인터 avail

ListPointer getHead()
{
ListPointer head;

head = (ListPointer)malloc(sizeof(ListNode));
head->coef = 0;
head->expo = -1;
head->link = NULL;
return head;

}

void retNode(ListPointer node) // 지정된 노드를 avail로 반환
{
node->link = avail;
avail = node;
}

ListPointer getNode()
{
ListPointer node;

if (avail)
{
    node = avail;
    avail = avail->link;
}
else //새로 동적으로 노드를 생성
   node = (ListPointer)malloc(sizeof(ListNode));
return node;

}

void attach(int cof, int exp, ListPointer *ptr) // 다항식의 덧셈결과를 가지고 새로운 노드
{
ListPointer temp;

temp = getNode();
temp->coef = cof;
temp->expo = exp;
(*ptr)->link = temp;
*ptr = temp;

}

int length(ListPointer last) //리스트의 길이를 구하는 함수
{
ListPointer temp;

int count = 0;

if (last)
{
    temp = last->link;
    do
    {
        count++;
        temp = temp->link;
        if (temp->link == NULL) //avail리스트는 원형 
            break ;
    } while (temp->link != last->link);
}
return count;

}

int compare(int a_exp, int b_exp) //해당 지수의 값을 비교하여 반환값에 따라 스위치문에
{
if(a_exp < b_exp)
return -1;
else if(a_exp == b_exp)
return 0;
return 1;
}

ListPointer cpadd(ListPointer a, ListPointer b)
{
ListPointer startA, c, lastC;
int sub, done = 0; //

startA = a;
a = a->link;
b = b->link;
c = getNode();
c->expo = -1;
lastC = c;

do
{
    switch(compare(a->expo, b->expo))
    {
        case -1:
            attach(-b->coef, b->expo, &lastC);
            b = b->link;
            break;
        case 0:
            if (startA == a) done = 1;
            else
            {
                sub = a->coef - b->coef;
                attach(sub, a->expo, &lastC);
                a = a->link;
                b = b->link;
            }
            break;
        case 1:
            attach(a->coef, a->expo, &lastC);
            a = a->link;
    }
} while (!done);

lastC->link = c;
return c;

}

void createList(ListPointer h, int num1, int num2) //계수와 지수를 가지고 새로운 리스트를
{
ListPointer newnode;
ListPointer p;

newnode = getNode();
newnode->coef = num1;
newnode->expo = num2;

if(h->link == NULL)
{
    h->link = newnode;
    newnode->link = h;
}
else
{
    p = h->link;

    while (p->link != h)
        p = p->link;
    
    newnode->link = h;
    p->link = newnode;
}

}

void polyPrint(ListPointer p) // 다항식을 출력함.
{
ListPointer temp;

temp = p->link;

while (temp->link != p->link)
{
    printf("%d^%d", temp->coef, temp->expo);
    temp = temp->link;
    if (temp->link != p->link)
    printf(" + ");
}

}

void cerase(ListPointer *ptr) //원형리스트를 제거
{
ListPointer temp;

if (*ptr)
{
    temp = (*ptr)->link;
    (*ptr)->link = avail;
    avail = temp;
    *ptr = NULL;
}

}

int ft_form_len(char *form)
{
int ret;

ret = 0;
while (*form)
{
    if (*(form++) == '^')
        ret++;
}

return (ret);

}

int ft_get_num(char *str)
{
int num = 0;

while (*str && *str != '^' && *str != '+')
    num = num * 10 + *(str++) - 48;
return num;

}

int ft_get_dec(int num)
{
int ret;

ret = 0;
if (num < 0)
    num *= -1;

while (num)
{
    ret++;
    num /= 10;
}
return (ret);

}

void ft_get_stk(char *form, ListPointer ptr)
{
int i = 0;
int num1, num2, flag;
int form_len = ft_form_len(form);

while (i < form_len)
{
    flag = 1;
    if (*form == '-')
    {
        flag = -1;
        form++;
    }
    num1 = ft_get_num(form) * flag;
    form += ft_get_dec(num1) + 1;
    flag = 1;
    if (*form == '-')
    {
        flag = -1;
        form++;
    }    
    num2 = ft_get_num(form) * flag;
    createList(ptr, num1, num2);
    form += ft_get_dec(num2) + 1;
    i++;
}

}

int main (void)
{
char form1 = malloc(255);
char form2 = malloc(255);

ListPointer a, b, c;
avail = getHead();
a = getHead();
b = getHead();

printf("다항식 1 입력: ");
scanf("%s", form1);
ft_get_stk(form1, a);

printf("\n");

printf("다항식 2 입력: ");
scanf("%s", form2);
ft_get_stk(form2, b);

free(form1);
free(form2);

c = cpadd(a, b); 

printf("\n");

printf("두 다항식의 차 = ");
polyPrint(c);

cerase(&a);
cerase(&b); //a,b리스트를 avail 리스트로 반환

return 0;

}