Data-Structure - Linked-List( Application - 2 )

Available Space List (1)

---

• Available spcae list 또는 avail lsit는 우리가 새로운 node가 필요할 때 평가해서 그 때 그 떄 사용할 수 있습니다.
• 또한 처음에는 avail는 NULL로 초기화 됩니다.
• 우리는 node를 malloc()하거나, free()하는 것이 아니라, 아래서 볼 getNode()이나 retNode()를 사용하면 됩니다.

getNode()

이는 getNode()메소드의 기본적인 작동 방식을 묘사한 것입니다. avail이 있다면 이 avail은 avail->link를 가리키게 하고 avail을 필요로 하는 node에게 avail을 주어주는 방식으로 작동됩니다.

retNode()

이는 retNode()메소드의 기본적인 작동 방식을 묘사한 것입니다. node->link를 avail을 가리키게 하고 node가 이제 avail의 head로 만들어 주면 끝입니다. 이렇게 하면 node가 나중에 필요할 때 쓸 수 있는 avail로 들어가게 됩니다.

 

이럴 활용해서 저번에 구현한 polynomials를 합치는 logic을 작성해보겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_QUEUES 10 /* maximum number of stacks */
#define ERROR_KEY -100
 
#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }
 
typedef struct polyNode
{
    float coef;
    int expon;
    struct polyNode *link;
} * polyPointer;
 
polyPointer a, b;
 
polyPointer avail = NULL;
 
polyPointer getNode(void)
{
    polyPointer node;
    if (avail)
    {
        node = avail;
        avail = avail->link;
    }
    else
        MALLOC(node, sizeof(struct polyNode));
    return node;
}
 
void retNode(polyPointer node)
{
    node->link = avail;
    avail = node;
}
 
int COMPARE(int expon1, int expon2)
{
    if (expon1 < expon2)
        return -1;
    else if (expon1 > expon2)
        return 1;
    else
        return 0;
}
 
void attach(float coefficient, int exponent, polyPointer *ptr)
{
    polyPointer temp;
    temp = getNode();
    temp->coef = coefficient;
    temp->expon = exponent;
    temp->link = (*ptr)->link;
    (*ptr)->link = temp;
    *ptr = temp;
}
 
polyPointer padd(polyPointer a, polyPointer b)
{
    float sum;
    polyPointer c, rear, temp;
    MALLOC(rear, sizeof(*rear));
    rear->link = NULL;
    c = rear;
 
    while (a && b)
    {
        switch (COMPARE(a->expon, b->expon))
        {
        case -1:
            attach(b->coef, b->expon, &rear);
            b = b->link;
            break;
        case 0:
            sum = a->coef + b->coef;
            if (sum)
            {
                attach(sum, a->expon, &rear);
            }
            a = a->link;
            b = b->link;
            break;
        case 1:
            attach(a->coef, a->expon, &rear);
            a = a->link;
            break;
        }
    }
    /*
        copy rest of list a and then list b
    */
 
    for (; a; a = a->link)
        attach(a->coef, a->expon, &rear);
    for (; b; b = b->link)
        attach(b->coef, b->expon, &rear);
 
    /*
        delete extra initial node
    */
 
    temp = c;
    c = c->link;
    retNode(temp);
    // free(temp);
    return c;
}
 
void insert(polyPointer *first, polyPointer x, float coef, int expon)
{
    polyPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->coef = coef;
    temp->expon = expon;
 
    if (*first)
    {
        temp->link = x->link;
        x->link = temp;
    }
    else
    {
        temp->link = NULL;
        *first = temp;
    }
}
 
void printList(polyPointer first)
{
    printf("The list contains: ");
    for (; first; first = first->link)
    {
        if (first->expon != 0)
        {
            if (first->link == NULL)
            {
                printf("%.2fx^%d", first->coef, first->expon);
                putchar('\n');
                return;
            }
            printf("%.2fx^%d + ", first->coef, first->expon);
        }
        else
        {
            printf("%.2f", first->coef);
            putchar('\n');
            return;
        }
    }
 
    printf("\n");
}
 
void readPolynomial(polyPointer *pPoint, FILE *fp_read)
{
    int i, number, expon;
    float coef;
    polyPointer temp = NULL;
    fscanf(fp_read, "%d", &number);
 
    for (i = 0; i < number; i++)
    {
        fscanf(fp_read, "%f %d", &coef, &expon);
        insert(pPoint, temp, coef, expon);
        if (i == 0)
        {
            temp = *pPoint;
        }
        else
        {
            temp = temp->link;
        }
    }
}
 
void erase(polyPointer *ptr)
{
    polyPointer temp;
    while (*ptr)
    {
        temp = *ptr;
        *ptr = (*ptr)->link;
        retNode(temp);
        // free(temp);
    }
}
 
int main(void)
{
    FILE *fp_read;
    fp_read = fopen("a.txt", "r");
 
    polyPointer a = NULL;
    readPolynomial(&a, fp_read);
 
    polyPointer b = NULL;
    fp_read = fopen("b.txt", "r");
    readPolynomial(&b, fp_read);
 
    fclose(fp_read);
 
    polyPointer resultPolynomial = padd(a, b);
    printList(resultPolynomial);
    erase(&resultPolynomial);
 
    return 0;
}

Available Space List (2)

---

cerase()는 circular list에서 avail로 이주시키는 함수입니다.

cerase()

이는 cerase()메소드의 기본적인 작동 방식을 묘사합니다. (*ptr)->link를 일단 temp라고 합니다. 그리고 (*ptr)->link를 avail을 가리키게 하고 마지막으로 avail을 temp로 하게 되면 신기하게도 circular-list가 avail에 추가되게 됩니다.

 

Available Space List 총 정리

---

Zero Polynomial

---

또한 zero polynomials이라는 circular-list에서의 special case를 피하기 위해 몇가지 규칙을 정했습니다.

• 각각의 polynomial는 최소한 하나의 노드를 가지고 있어야 합니다.
• 또한 expon과 coef필드는 관계가 없습니다.

 

Additional List Operations (1)

---

Invertion Operations for Chains

이는 노드의 순서를 거꾸로 바꾸는 linked-list의 함수입니다. linked-list에서 순서를 바꾸려면 lead, middle, trail이라는 3개의 포인터가 필요하게 됩니다.

invert()

invert()함수의 기본 동작 방식은 위와 같습니다. 일단 middle, trail을 lead외에 추가적으로 생성해 줍니다. 그리고 lead가 NULL이 아닌 동안 trail = middle, middle = lead, lead = lead->link, middle->link = trail을 해주게 되면 최종적으로 lead가 NULL에 도달하는 순간 노드가 역순으로 되어 있을 겁니다.

 

Concatenating singly linked lists

이는 기본적인 singly linked-list를 이어 붙이는 함수입니다.

이는 인자로 받은 head포인터 2개 ptr1과 ptr2가 인자로 받아 들여지면 for(temp = ptr1; temp->link; temp = temp->link);로 temp를 ptr1 linked-list의 끝을 가리키게 하고 마지막으로 temp->link = ptr2를 하게 된다면 끝나게 됩니다.

 

중간 정리

---

Inserting at the front of a circular list

이는 circular-list에서 맨 앞에 node를 추가하는 함수입니다.

insertFront()

이는 circular-list의 맨 마지막 node와 추가할 node를 인자로 받습니다. 그리고 circular-list가 비었을 때와 비지 않았을 때를 나누어서 로직을 처리해주어야 합니다. 우선 list가 비었을 때에는 (*last) = node를 하고 node->link = node;를 해주면 끝입니다. 그다음으로는 list에 node가 있다면 node->link = (*last)->link를 하고 (*last)->link = node를 하면 됩니다.

 

Finding the length of a circular list

circular list의 길이를 알아내는 코드는 어떻게 짜는지 알아보겠습니다. 그냥 circular-list의 last 노드를 인자로 받습니다. 그냥 counter를 만들어주고 last부터 시작해서 temp = temp->link를 매번 해주고 temp != last)인동안 do - while문을 조져주면 counter에 circular-list의 크기가 들어가게 됩니다.

 

중간정리

---