Lifeignite

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

앞으로 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) 등과 같이 나타낸다.

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

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

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