[자료구조] 윤성우의 열혈 자료구조 ch 04. 연결리스트 2 04-2 문제풀이

문제

 

더미 노드의 유무에 따른 코드의 변화를 직접 경험하는 것은 코드의 이해력을 높이는 데 도움이 된다.

그래서 LinkedRead.c에서 생성하는 연결 리스트에 더미 노드를 추가하고, 그에 따른 코드의 변화를 직접 확인하기로 하겠다.

 

이 예제는 리스트의 끝에다가 노드를 추가하는 방식이므로 head 와 tail 이 모두 필요하다. 

조건에 맞게 코드를 수정하라.

 

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;
}

 

 

 

 

더미 노드를 추가한 결과

#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;
    }
    newNode = (Node *)malloc(sizeof(Node)); // 더미 노드 생성!
    newNode->data = '\0'; // 더미 노드 데어터는 NULL 값으로 지정
    newNode->next = head; 
    head = 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;
}

 

 

입력받은 값으로 연결리스트를 구성한 후에, 더미 노드를 추가하여 head를 재설정하는 방법으로 코드를 작성하였다.

 

 

결과