Lifeignite

링크드리스트에 관한 포스팅에 들어가기전에 대부분의 자료구조에서 사용되는 자기참조구조체에 관해서 알아보도록 하자.

 자기참조구초제(Self-referential structure)는 링크드리스트 뿐만 아니라 여러 자료구조에서(이를테면 그래프의 표현이나, 트리등의 자료구조를 작성할 때) 사용한다. 

아주 중요한 개념이라고 할 수 있는데 실질적으로 작성해보면 어렵지 않다. 

자기참조구조체를 사용하는 자료구조에서는 대부분 하나의 데이터 단위를 자기참조구조체로 관리하게 되는데 기본적으로 자기가 관리하는 데이터 정보와 자신의 타입의 레퍼런스를 가지고 있다. 모양을 보면 다음과 같다.

여기서 이런 공부를 처음 시작하는 사람들이 자주 혼동하는 개념이 있다.

이게 다 이름을 저 모양으로 지어놔서 그렇다. ㅡㅡ.. 

자기참조구조체면 마치 나 스스로를 참조할 것 같아 보이지만 참조의 대상이 나라는 구조체가 아니라 나와 같은 타입이다. 즉, 나와 같은 타입의 다른 구조체를 가르킨다고 보면 된다.( 물론 구현에 따라 자기 스스로를 가르킬... 수도 있다.)

여기서 자기참조구조체는 참조하는 대상이 한개일 수도 있지만 여러개일 수 있다. 이것도 어떤 자료구조를 구현할지에 따라서 달라진다. 예를들면 double linked list 를 구현하게 될경우 레퍼런스를 두개 사용해야하고, 자식의 갯수가 n개인 n-진트리를 작성하게 될 경우 레퍼런스가 n개가 될 것이다. 

double linked list의 자기참조 구조체를 잠깐 살펴보면 아래와 같다.

서론이 너무 길었던 것 같다. 다음번 포스트는 정말로 링크드리스트에 관하여 다루겠다.

스터디 때도 진행된적이 있는 포스팅에 앞선 기본 지식들을 점검하는 시간이다. 

앞으로 C로 자료구조를 구현하는데 있어서 기본이 되는 

C를 처음 배우는 친구들이 모를 것 같은 문법과 기초 지식들을 소개해본다. 

1. 구조체(Structure Types)

구조체는 서로 다른 기본 자료형들을 한데 묶어 관리할 수 있게 도와주는 놈이다. 

구조체 없이도 자료구조를 구현하는데 문제 없을 수 있다. 

순수하게 배열과 동적할당, 그리고 로직들을 사용하여 자료구조를 구현할 수 있는데 그런 방식으로 코드를 작성하게 될 경우 코드도 읽기 힘들고, 짜는데도 시간이 오래걸릴 수 있다. 

즉 구조체는 여러가지 구현에 있어서 우리를 편리하게 해준다. 

구조체는 우리가 직접 정의한다는 관점에서 사용자 정의 자료형이라고 볼 수도 있는데 형태는 다음과 같다.

구조체에 대해 더 자세한 내용을 알고 싶은 분들은 다른 블로그나 구글을 참고하길 바란다.

2. 동적할당

동적 할당이란 런타임중에 원하는 메모리 공간을 할당받는 것을 말한다. 

막 프로그래밍을 시작한 사람들에게 말이 조금 어려울 수 있는데, 간단히 원하는 크기 만큼 그때 그때 메모리를 받을 수 있는 것이다...(전혀 간단하지 않은 것 같다..)

하지만 역시 이 포스트는 C언어의 사용법을 다루는 것이 아니므로 자세한 설명은 생략하도록 하겠다.

C언어 에서는 이 동적할당을 편하게 이용하기 위해서 대표적으로 2가지 함수를 제공하고 있는데 

malloc과 calloc이 그 두개다.

C언어에서 이 두 함수가 작동하는 방식은 다음과 같다.

시스템에게 원하는 만큼 메모리 요청하면 그 메모리만큼을 미리 힙에 할당하고 메모리의 시작 주소를 반환

단, malloc과 calloc의 차이점은 malloc은 해당하는 메모리 영역을 초기화 하지 않고 사용자에게 반환하고, calloc은 초기화(0으로) 시키고 사용자에게 반환한다는 사실이다. 

해당하는 메모리 영역을 어떤 방식으로 활용할지는 전적으로 사용자에게 위임하기 때문에 return형은 void * 형이다. 그래서 대부분 원하는 타입으로 케스팅해서 다시 사용한다.

이 두함수는 모두 stdlib.h 라는 헤더에 존재한다.

자세한 함수의 원형을 알고 싶은 사람은 

malloc <-클릭

calloc <-클릭

사용방식은 다음과 같다. 

 이 함수를 사용할 때 주의 할 사항은 일반 기본자료형과 다르게 구조체의 크기는 시스템마다 할당하는 크기가 다를 수 있다는 것이다. 그렇기 때문에 일반적으로 해당 자료형의 사이즈를 반환해주는 sizeof 연산자와 함께 사용한다.

  또 사용이 끝난 공간은 메모리를 해제 해 주기 전까지 영원히 남아있다. 반드시 사용이 종료되면 메모리를 해제해 주어야 한다. 이는 free함수로 메모리 해제를 시스템에 알릴 수 있다.

3. 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

시간 복잡도와 공간복잡도에 대해서는 굉장히 많은 내용을 설명해야 한다. 주로 다룰 내용은 빅-오 표현이 굉장히 중요하다.(사실 평균도 나름 중요하다.)

그래서 안할꺼다.  간단히 설명하자면 상수 때고 가장 크게 영향을 주는 식만을 시간 복잡도로 나타낸다. 보통 O(n),O(lgn) 등과 같이 나타낸다.

역시 구글과 다른 블로그들을 참조하길 바란다. 앞으로 대부분의 자료구조에서 연산을 정의할 때 그 정의된 연산이 얼만큼의 시간복잡도와 공간복잡도를 가지는 지를 소개할 텐데 꼭필요한 부분이다. 학습하고 오시길 ^ㅇ^ 

이부분은 나중에 따로 포스팅 할 수도 있다. 

잘못된 내용은 덧글로 알려주세요. 수정하도록 하겠습니다.

현재 학교 소모임에서 자료구조를 스터디 하고 있는데

학년도 4학년이기도 하고 다시 자료구조를 스터디하거나 

심도있게 다룰 것 같지는 않습니다. 

마지막이라는 심정으로 자료구조를 포스팅하도록 할게요.

아마 겨울 방학 때는 알고리즘 쪽 스터디를 맡을 수도 있는데

그렇게 되면 아마 알고리즘 관련 포스팅도 진행할 것 같아요.

자료구조 관련 포스팅은 기본적으로 C로 진행됩니다.

후반부로 가면  C++을 사용하긴 할 것 같습니다만... 가봐야 알겠네요.

포스팅 순서는 아마도

링크드 리스트

스택

큐

트리

힙

------------------------------------ 요기까지 C

그래프

최단거리알고리즘

MST알고리즘

------------------------------------ 요기까지 C++ 

이런 것들을 다룰 것 같습니다. 더 다룰수도 있고 아닐수도 있고...