(C언어) 단일 연결리스트 (배운거 정리용)

• 단일 연결 리스트

정의

자료가 배열과 다르게 연속적이지 않으므로, 추가 삽입이 간편하다.

처음부터 시작해 검색하므로, 중간과 끝에 있는 자료는 찾는데, 시간이 걸린다.

노드 다음 노드를 가르킨다.

시작을 항상 가지고 있다.

• 전체 소스 (런타임 오류 투성이)

/*##################################
단일연결리스트(수업용)
파일명: 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;
 
    return  pTemp;
}
 
SNode* FindNodeData(SNode* pStart, int data)
{
    SNode* pNode = pStart;
 
    return pNode;
}
 
SNode* InsertNodeData(SNode* pStart, int data, int insert)
{
    SNode* pNode = pStart;
 
    pNode = FindNodeData(pStart, data);
 
    return pNode;
}
 
void DeleteNodeData(SNode* pStart, int del)
{
    SNode* pPre = NULL;
    SNode* pNode = pStart;
 
 
}
 
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);
}

우선 각각의 의미를 가지고 있는 함수들이 있습니다. CreateNode는 생성, FindNodeData는 찾기, InsertNodeData는 삽입 그리고 DeleteNodeData는 삭제의 의미를 가지고있습니다. 물론 다른 함수들도 각자의 의미를 가지고 있습니다.

하지만 런타임 오류 투성이죠. CreateNode로 새로운 노드를 생성하지만 연결이 되지않아 시작 노드의 data만 읽어지거나, FindNodeData로 특정 노드를 찾지만 안찾아진다거나, InsertNodeData로 특정 노드를 삽입 할려지만 삽입이 안되고 DeleteNodeData로 특정 노드 삭제를 할려지만 삭제가 안되죠.

이 코드가 정상작동 하도록 고치는 것이 목표입니다. 단일 연결리스트에는 몇 가지 조건이 있습니다. main()함수를 수정해서 고치면 안됩니다. 그 밖에는 주석으로 표시해두었습니다.

전체 코드를 보았으니 이제 코드를 해석해봅시다. C언어는 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를 NULL 값으로 생성하고 있습니다. 어떤식으로 생성되는 걸까요? SNode* 함수로 가봅시다.

struct SNode {
    int nData;
    SNode* pNext;
};