[자료구조] 윤성우의 열혈 자료구조 04-1 문제풀이

문제

예제 LinkedRead.c 에 익숙해지는 가장 빠르고도 흥미로운 길은 예제를 조금 수정해 보는 것이다. 

따라서 예제를 조금 수정해 볼 기회를 제공하고자 한다. 예제 수정을 위한 주제는 다음과 같다.

• 새 노드를 연결 리스트의 꼬리가 아닌 머리에 추가한다.

 

LinkedRead.c

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

typedef struct _node
{
    int data;
    struct _node *next;
} Node;

int main(void)
{
    Node *head = NULL;
    Node *tail = NULL;
    Node *cur = NULL;

    Node *newNode = NULL;
    int readData;

    while (1)
    {
        printf("자연수 입력 : ");
        scanf("%d", &readData);
        if (readData < 1)
            break;

        newNode = (Node *)malloc(sizeof(Node));
        newNode->data = readData;
        newNode->next = NULL;

        if (head == NULL)
            head = newNode;
        else
            tail->next = newNode;
        tail = newNode;
    }
    printf("\n");

    printf("입력받은 데이터의 전체출력!\n");
    if (head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다.\n");
    }
    else
    {
        cur = head;
        printf("%d ", cur->data);

        while (cur->next != NULL)
        {
            cur = cur->next;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");

    if (head == NULL)
    {
        return 0;
    }
    else
    {
        Node *delNode = head;
        Node *delNextNode = head->next;

        printf("%d을(를) 삭제합니다. \n", head->data);
        free(delNode);

        while (delNextNode != NULL)
        {
            delNode = delNextNode;
            delNextNode = delNextNode->next;

            printf("%d을(를) 삭제합니다. \n", delNode->data);
            free(delNode);
        }
    }
    return 0;
}

 

 

예제에서는 노드를 머리가 아닌 꼬리에 추가하였다. 따라서 3 -> 2 -> 7 -> 8의 순으로 연결되어 있는 리스트에 5를 추가로 삽입하면 3 -> 2 -> 7 -> 8 -> 5의 순으로 저장이 된다.

그런데 이번에는 다음 순으로 저장이 되도록 예제를 변경해보고자 한다.

 

5 -> 8 -> 7 -> 2 -> 3

 

즉 연결리스트의 머리에 노드가 추가되도록 예제를 변경하는 것이다. 이 문제가 쉬워 보이더라도 그림을 그려서 머리에 노드가 추가되는 과정을 완전히 정리한 다음에 코드로 옮기기 바란다. 그리고 이를 습관화하기 바란다.

 

 

정답

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

typedef struct Node
{
    int data;
    struct Node *link;
} Node;

int main(void)
{
    Node *head = NULL;
    Node *tail = NULL;

    Node *newnode = NULL;
    int inputdata = 0;

    Node *cur = NULL;
    while (1)
    {
        printf("데이터를 입력하세요 (0 이하의 수를 입력하여 종료) : ");
        scanf("%d", &inputdata);
        if (inputdata < 1)
        {
            break;
        }
        newnode = (Node *)malloc(sizeof(Node));
        newnode->data = inputdata;
        if (head == NULL)
        {
            head = newnode;
        }
        else
        {
            newnode->link = head;
            head = newnode;
        }
    }
    printf("\n");

    printf("입력받은 데이터의 전체출력!\n");
    if (head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다.\n");
    }
    else
    {
        cur = head;
        printf("%d ", cur->data);

        while (cur->link != NULL)
        {
            cur = cur->link;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");

    int select = 0;

    printf("추가로 입력하시겠습니까 ? \n1. 네 2. 아니오 : ");
    scanf("%d", &select);

    if (select == 1)
    {
        while (1)
        {
            printf("데이터를 입력하세요 (0 이하의 수를 입력하여 종료) : ");
            scanf("%d", &inputdata);
            if (inputdata < 1)
            {
                break;
            }
            newnode = (Node *)malloc(sizeof(Node));
            newnode->data = inputdata;
            if (head == NULL)
            {
                head = newnode;
            }
            else
            {
                newnode->link = head;
                head = newnode;
            }
        }
    }

    printf("입력받은 데이터의 전체출력!\n");
    if (head == NULL)
    {
        printf("저장된 자연수가 존재하지 않습니다.\n");
    }
    else
    {
        cur = head;
        printf("%d ", cur->data);

        while (cur->link != NULL)
        {
            cur = cur->link;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");
    return 0;
}

 

 

코드가 상당히 중복된다. 함수로 따로 만드는 것이 좋을 거 같다.

 

결과