티스토리 뷰

카테고리 없음

(C언어) 환형 연결리스트 (정리용)

앤글 2019. 2. 26. 06:15

환형 연결리스트

해당 글은 블로그의 단일 연결리스트와 이어집니다.

그림은 단일 연결리스트에서 생성된 노드를 가져와서 환형 연결리스트로 바꾸었습니다. 환형 연결리스트는 마지막 노드의 pNext가 첫 노드의 주소값을 가르킬 때 생성됩니다.

계속해서 이어지는 연결리스트인데요, 단일 연결리스트 포스팅에서 만들어진 코드로 설명하도록 하겠습니다.



  • 단일 연결리스트가 완성된 코드에서 환형 연결리스트를 만들어보자

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    /*##################################
    단일연결리스트(수업용)
    파일명: LinkedList_empty.cpp
    작성자: 김홍규 강사님
    마지막수정날짜: 2018.04.10
    버전: 1.05
    ###################################*/
     
    #include <stdio.h>
    #include <stdlib.h> //메모리 동적할당 헤더
    #include <crtdbg.h> //메모리 누수 탐지 헤더
    //#include  "linkedlistClass.h"
     
    struct SNode {
        int nData;
        SNode* pNext;
    };
     
    SNode* CreateNode(SNode* pNode, int data); //노드를 생성하여 리턴한다.
    SNode* FindNodeData(SNode* pStart, int data); //해당 데이터를 가진 노드를 찾는다.
    SNode* InsertNodeData(SNode* pStart, int data, int insert); //해당 데이터를 가진 노드 뒤에 노드를 추가한다.
    void DeleteNodeData(SNode* pStart, int del); //해당데이터를 가진 노드를 삭제한다.
    void PrintLinkedList(SNode* pStart); //노드를 순회하며 끝날때까지 출력한다.
    void DeleteLinkedList(SNode* pStart); //노드를 순회하며 모든데이터를 삭제한다.
    void ReverseLinkedList(SNode* pStart); //
     
                                           //연결리스트 동적으로 입력받기.(동적할당 설명용)
    void InputAdd();
     
    //정상작동 테스트를 위해서, 다음과 같이 기본적인 절차로 오류를 확인한다.
    //이 소스에 몇가지 버그가 존재한다.
    //이 코드가 정상작동 된 후 발견해볼것!
    //main()함수 내 코드는 절대 코드 변경하지말것.
    void main()
    {
        //_CrtSetBreakAlloc(71); //메모리 누수시 번호를 넣으면 할당하는 위치에 브레이크 포인트를 건다.
        //_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); //메모리 누수 검사 
     
        SNode* pBegin = NULL;
        SNode* pEnd = NULL;
     
        //노드 추가 테스트
        pEnd = CreateNode(pEnd, 10);
        pBegin = pEnd; //마지막 노드를 알아야 검색이 가능하므로 저장해둔다.
     
        pEnd = CreateNode(pEnd, 20);
        pEnd = CreateNode(pEnd, 30);
        pEnd = CreateNode(pEnd, 40);
        pEnd = CreateNode(pEnd, 50);
     
        PrintLinkedList(pBegin);
     
        SNode* pFind = FindNodeData(pBegin, 40);
        printf("Find:%d\n", pFind->nData);
     
        pEnd = InsertNodeData(pBegin, 30, 60);//노드 삽입
     
        PrintLinkedList(pBegin);
     
        DeleteNodeData(pBegin, 60); //노드 삭제
     
        PrintLinkedList(pBegin);
     
        DeleteLinkedList(pBegin); //모든노드삭제 - 이 함수를 호출하지않을시 메모리가 누수됨.
    }
     
    //여기서 부터 기능을 구현한다.
    //기존코드는 손대지말고, 추가만 하여 현 프로그램 정상 작동하도록할것.
    SNode* CreateNode(SNode* pNode, int data)
    {
        SNode* pTemp = NULL;
     
        pTemp = new SNode();
        pTemp->nData = data;
     
        if (pNode != NULL)
        {
            pNode->pNext = pTemp;
        }
     
        return  pTemp;
    }
     
    SNode* FindNodeData(SNode* pStart, int data)
    {
        SNode* pNode = pStart;
     
        while (pNode != NULL)
        {
            if (pNode->nData != data)
            {
                pNode = pNode->pNext;
            }
            else
                return pNode;
        }
     
        return pNode;
    }
     
    // pBegin, 30, 60
    SNode* InsertNodeData(SNode* pStart, int data, int insert)
    {
        SNode* pNode = pStart;
        SNode* pTemp = NULL;
     
        pTemp = new SNode();
        pTemp->nData = insert;
     
        pNode = FindNodeData(pStart, data);
     
        pTemp->pNext = pNode->pNext;
        pNode->pNext = pTemp;
     
        return pNode;
    }
     
    void DeleteNodeData(SNode* pStart, int del)
    {
        SNode* pPre = NULL;
        SNode* pNode = pStart;
     
        while (pNode != NULL)
        {
            /*printf("pNode data: %d\n", pNode->nData);
            printf("pNode p: %d\n", pNode->pNext);*/
            if (pNode->nData == del)
            {
                pPre->pNext = pNode->pNext;
                break;
            }
            else
            {
                pPre = pNode;
                /*printf("pPre data: %d\n", pPre->nData);
                printf("pPre p: %d\n", pPre->pNext);*/
            }
     
            pNode = pNode->pNext;
        }
    }
     
    void PrintLinkedList(SNode* pStart)
    {
        SNode* pNode = pStart;
        printf("data:");
        while (pNode)
        {
            printf("%d", pNode->nData);
            pNode = pNode->pNext;
     
            if (pNode != NULL)
                printf(",");
        }
        printf("\n");
    }
     
    void DeleteLinkedList(SNode* pStart)
    {
        SNode* pNode = pStart;
        SNode* pDel = NULL;
    }
     
    void InputAdd()
    {
        SNode* pStart = NULL;
        SNode* pNode = NULL;
        int nData = 0;
     
        //동적할당을 하면 프로그램이 사용자에 의해서 사용되는 메모리가 결정된다.
        //쉽게말해서, 컴파일단계에서 100개를 만들고 쓴다면, 
        //사용하지않더라도 100개의 메모리를 사용할수밖에없다.
        //그리고, 100개 이상의 메모리도 사용할수없다.
        //그러나, 동적할당을 하면 사용자가 추가한 메모리만큼만 메모리가 사용되고 
        //메모리용량이 허용하는 한 추가가 된다.
        while (nData != -1)
        {
            scanf("%d", &nData);
            pNode = CreateNode(pNode, nData);
     
            if (pNode == NULL)
            {
                printf("더 이상 사용할수 있는 메모리가 없습니다!");
            }
     
            if (pStart == NULL)
                pStart = pNode;
     
            PrintLinkedList(pStart);
        }
     
        DeleteLinkedList(pStart); //모든노드삭제 - 이 함수를 호출하지않을시 메모리가 누수됨.
    }
    		cs



  • main() 함수에서 환형 연결리스트 만들기

void main()
{
    //_CrtSetBreakAlloc(71); //메모리 누수시 번호를 넣으면 할당하는 위치에 브레이크 포인트를 건다.
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); //메모리 누수 검사 
 
    SNode* pBegin = NULL;
    SNode* pEnd = NULL;
 
    //노드 추가 테스트
    pEnd = CreateNode(pEnd, 10);
    pBegin = pEnd; //마지막 노드를 알아야 검색이 가능하므로 저장해둔다.
 
    pEnd = CreateNode(pEnd, 20);        // 이때부터 pTemp 가 연결이 안되었다.
    pEnd = CreateNode(pEnd, 30);
    pEnd = CreateNode(pEnd, 40);
    pEnd = CreateNode(pEnd, 50);
 
    PrintLinkedList(pBegin);
 
    SNode* pFind = FindNodeData(pBegin, 40);
    printf("Find:%d\n", pFind->nData);
     
    InsertNodeData(pBegin, 30, 60);//노드 삽입
 
    PrintLinkedList(pBegin);
 
    DeleteNodeData(pBegin, 60);//노드 삭제
 
    PrintLinkedList(pBegin);
 
    DeleteLinkedList(pBegin); //모든노드삭제 - 이 함수를 호출하지않을시 메모리가 누수됨.
}
cs

위 코드는 단일 연결리스트가 완성되있는 main() 함수입니다. 제가 생각하는 첫 번째 방법은 main() 함수에서 CreatNode가 모두 읽히고 난 후 환형 연결리스트를 구성하는 겁니다.

왜 CreatNode가 읽히고 난 후냐면 CreatNode는 새로운 노드를 만들어서 기존 노드와 잇는 함수입니다. 그러므로 모든 노드가 만들어진 후 마지막 노드의 pNext와 시작 노드의 주소를 이어야 환형 연결리스트가 만들어지겠죠.


CreatNode를 읽고 난 후 노드

CreatNode 함수가 main() 함수에서 모두 읽히고 난 후의 노드는 위 그림처럼 생성됩니다. 정말 간단한 문제죠. 0x05의 pNext와 0x01을 이어주면 되는 문제입니다.

환형 연결리스트 모식도

위 그림처럼 말이죠.



    0x05->pNext = 0x01;
 
    PrintLinkedList(pBegin);
cs

그림을 코드로 표현한다면 위 코드처럼 되겠죠? 그럼 고민을 해봐야합니다. 0x05의 pNext와 0x01을 동시에 알아야 됩니다.

우선 0x05의 pNext를 사용하기 위해선 0x05로 이동하여야 합니다. 그러므로 반복문을 통해서 0x05 노드로 이동해야 겠죠? 여기서 문제점이 있습니다. 0x05 노드까지 이동해야 0x05의 pNext에다가 0x01을 연결할 수 있는데 "0x01을 어디서 구하냐?"가 문제입니다.

pBegin 에서 가져오면 되지않냐고 생각할 수 있지만 pBegin 노드를 반복문을 통해서 0x05 노드로 이동하는 것이기 때문에 pBegin을 통해서는 0x01을 볼 수가 없습니다. 



    SNode* pCircular = NULL;
    pCircular = new SNode();
 
    pCircular = pBegin;
 
    // 0x05->pNext = 0x01;
    while (pCircular != NULL)
    {
        if (pCircular->pNext == NULL)
        {
            pCircular->pNext = pBegin;
            pBegin = pCircular;
            break;
        }
        
        pCircular = pCircular->pNext;
    }
cs

그렇기 때문에 어쩔 수 없이 새로운 노드를 생성해야 합니다. 반복문으로 pNext가 NULL인 마지막 노드까지 이동하여 pBegin의 시작 주소를 넣은 것을 알 수 있습니다.

이렇게 되면 마지막 노드라는 개념이 없는 환형 연결리스트가 됩니다. 하지만 이대로 출력하면 무한 출력에 빠집니다. 원하는 노드에서 멈춰야하죠.



void PrintLinkedList(SNode* pStart)
{
    SNode* pNode = pStart;
    printf("data:");
 
    while (pNode != NULL)
    {
        printf("%d", pNode->nData);
 
        if (pNode->pNext == pStart)
            break;
        else printf(",");
 
        pNode = pNode->pNext;
    }
    printf("\n");
}
cs

저는 반복문을 읽으면서 노드의 pNext가 pStart와 같을 때. 즉, 시작과 연결 되어있는 노드가 되었을 때 반복문을 멈추는 코드를 짜봤습니다.


여기까지 main() 함수에서 환형 연결리스트를 바로 만들어봤습니다. 다음은 CreateNode에서 새로운 노드를 만들 때마다 환형 연결리스트를 구성하는 코드를 만들어봅시다.



  • CreateNode() 함수에서 환형 연결리스트 만들기
CreateNode 함수는 새로운 노드를 만들어 이전 노드와 이어주는 함수입니다. 환형 연결리스트를 만들기 위해서는 새로운 노드를 만들 때 마다 pNext에 처음 노드의 주소를 대입해주면 되겠죠.

하지만 고민 해봐야 할게 있습니다. 우리는 CreateNode 함수 안에서 시작 노드의 주소를 모르죠. 하지만 매우 간단한 문제입니다. 매개변수로 pEnd를 불러 왔듯이 pBegin을 불러오면 되죠.

SNode* CreateNode(SNode* pNode, SNode* pBegin, int data)
{
    SNode* pTemp = NULL;
    pTemp = new SNode();      // SNode 만큼 메모리가 생성
    pTemp->nData = data;
    pTemp->pNext = pBegin;    // pTemp의 pNext에 시작노드 주소 연결
 
    if (pNode != NULL)
    {
        pNode->pNext = pTemp;
    }
 
    return  pTemp;
}
cs

매개변수로 pBegin을 받아왔습니다. pBegin은 시작 노드의 주소를 알고있습니다.

pNode의 pNext에 새로 만들어진 노드인 pTemp를 대입하여 새로만들어진 노드를 이어주죠. 만약에 pTemp의 pNext에 pBegin이 들어가있다면? 자연스럽게 마지막 노드와 시작 노드가 연결되게 되는 겁니다.


그렇지만 매개변수로 불러오는데 계속해서 런타임 오류가 생길겁니다.


19
SNode* CreateNode(SNode* pNode, SNode* pStart, int data); //노드를 생성하여 리턴한다.
cs

해당 코드 19번째 줄에 CreateNode를 선언하는 부분이 있습니다. 그곳에 새로운 매개변수를 추가하면 됩니다. 마찬가지로 CreateNode가 쓰이는 부분에 모두 매개변수를 추가해주면 코드에 오류는 사라집니다.


이상으로 환형 연결리스트 만드는 방법 2가지를 알아봤습니다. 해당 방법은 제가 알아낸 코드이므로 정답은 아닙니다. 감사합니다.


저작자표시 비영리 동일조건 (새창열림)
댓글