<7> Q2. 자료구조와 함께 배우는 알고리즘 입문 (C언어)

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

typedef struct
{
    int max;
    int num;
    int *set;
} IntSet;

int InputSet(IntSet *s)
{
    int i, j, k, a, b, max, temp;
    printf("원소의 개수 입력: ");
    scanf("%d", &s->max);
    if ((s->set = calloc(s->max, sizeof(int))) == NULL)
    {
        s->max = 0;
        return -1;
    }
    s->num = 0;
    for (int i = 0; i < s->max; i++)
    {
        printf("%d(input 0 = exit) : ", i + 1);
        scanf("%d", &s->set[i]);
        if (s->set[i] == 0)
            break;

        s->num++;
        a = 0;
        b = i, max = i;
        while (a <= b)
        {
            if (s->set[i] == s->set[(a + b) / 2])
            {
                a = (a + b) / 2;
                b = a;
                break;
            }
            else if (s->set[i] > s->set[(a + b) / 2])
            {
                a = (a + b) / 2 + 1;
            }
            else
            {
                b = (a + b) / 2 - 1;
            }
        }
        if (b < 0)
            b = 0;
        if (i != b)
        {
            if (b < a)
            {
                temp = s->set[max];
                for (k = max; k > b; k--)
                {
                    s->set[k] = s->set[k - 1];
                }
                s->set[(a + b) / 2 + 1] = temp;
            }
            else if (s->set[max] > s->set[a])
            {
                temp = s->set[max];
                for (k = max; k > a; k--)
                {
                    s->set[k] = s->set[k - 1];
                }
                s->set[(a + b) / 2 + 1] = temp;
            }
            else
            {
                temp = s->set[max];
                for (k = max; k >= a; k--)
                {
                    s->set[k] = s->set[k - 1];
                }
                s->set[(a + b) / 2] = temp;
            }
        }
    }
    return 1;
}

int SetAdd(IntSet *s)
{
    int temp, max, k, i, a, b;

    printf("Add : ");
    scanf("%d", &s->set[s->num]);

    a = 0;
    b = s->num - 1;

    while (a <= b)
    {
        if (s->set[s->num] == s->set[(a + b) / 2])
        {
            a = (a + b) / 2;
            b = a;
            break;
        }
        else if (s->set[s->num] > s->set[(a + b) / 2])
        {
            a = (a + b) / 2 + 1;
        }
        else
        {
            b = (a + b) / 2 - 1;
        }
    }
    if (b < 0)
        b = 0;
    if (s->num != b)
    {
        if (b < a)
        {
            temp = s->set[s->num];
            for (k = s->num; k > b; k--)
            {
                s->set[k] = s->set[k - 1];
            }
            s->set[(a + b) / 2 + 1] = temp;
        }
        else if (s->set[s->num] > s->set[a])
        {
            temp = s->set[s->num];
            for (k = s->num; k > a; k--)
            {
                s->set[k] = s->set[k - 1];
            }
            s->set[(a + b) / 2 + 1] = temp;
        }
        else
        {
            temp = s->set[s->num];
            for (k = s->num; k >= a; k--)
            {
                s->set[k] = s->set[k - 1];
            }
            s->set[(a + b) / 2] = temp;
        }
    }
    s->num++;
    return 1;
}

int SetRemove(IntSet *s)
{
    int temp, k, a, b, rm;

    printf("Remove : ");
    scanf("%d", &rm);
    a = 0, b = s->num;
    while (a <= b)
    {
        if (rm == s->set[(a + b) / 2])
        {
            a = (a + b) / 2;
            b = a;
            break;
        }
        else if (rm > s->set[(a + b) / 2])
        {
            a = (a + b) / 2 + 1;
        }
        else
        {
            b = (a + b) / 2 - 1;
        }
    }

    if (rm == s->set[a])
    {
        for (k = a; k < s->num; k++)
        {
            s->set[k] = s->set[k + 1];
        }
        s->num--;
        return 1;
    }
    else
        return -1;
}

int main(void)
{
    IntSet x;
    InputSet(&x);

    for (int i = 0; i < x.num; i++)
    {
        printf("%d ", x.set[i]);
    }
    printf("\n");

    SetAdd(&x);
    for (int i = 0; i < x.num; i++)
    {
        printf("%d ", x.set[i]);
    }
    printf("\n");

    SetRemove(&x);
    for (int i = 0; i < x.num; i++)
    {
        printf("%d ", x.set[i]);
    }
    printf("\n");
}

난장판;;