프로그래밍/C언어

동적배열 자료구조의 시작

콘파냐 2014. 2. 28. 01:55
반응형

c언어에서 배열은 가장 단순하면서도 직관적인 자료구조다. 배열의 요소가 연속적인 메모리 공간에 붙어 있고 요소의 타입이 동일하기 때문에, 포인터 연산을 통한 데이터로의 접근이 빠르다. 그런데 배열을 사용하면서도 정형적인 형식과, 특징때문에, 유연한 요소의 삽입과 삭제에 제한이 있고,  일단 선언되면 배열의 크기를 가변적으로 바꿀 수 없기 때문에 유연한 사용에 한계가 있다.

memmove 함수를 이용해서 메모리의 위치를 이동하여 삽입 삭제가 가능하지만, 이 또한 처음에 정해진 배열의 크기안에서만 가능하다.

이를 해결 하기 위한 것이 동적배열이다.


2014/03/17 - [프로그래밍/C언어] - 동적배열에서 memmove함수 사용하기 연습 C언어


2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어


2014/03/21 - [프로그래밍/C언어] - 자료구조 스택(stack) C언어


2014/03/22 - [프로그래밍/C언어] - 자료구조 큐(Queue) C언어


memmove

동적배열을 다루기에 앞서 배열 안에서의 삽입과 삭제를 사용해보자.


memmove의 사용법은 간단하다.

void *memmove(void *dest, const void *src, size_t n);

첫번째인자 = 복사 목표 메모리 주소

두번째인자 = 복사 원 메모리 주소

세번째인자 = 복사되는 메모리의 크기


8째 줄을 보면 포인터 연산으로 7번째요소 이후의 값들을 5번째 요소의 위치로 이동시킨다. 즉 8,9,0을 6이 위치한 곳으로 옮긴다. 그런데 뒤에 9,0이 더 붙어 있다. 사실 memmove는 함수이름은 move지만 기능은 복사해서 붙여넣기를 했다.


만약 배열을 크기를 20으로 늘려서 수를 더 삽입하고 싶다면 어떻게 할까.

위 방법으로는 안될 것이다.




동적 배열

동적 배열은 heap을 이용하여 배열을 크기를 실행시간에 필요한 만큼 가변적으로 바꿀 수 있는 배열을 말한다. 엄밀히 말하면 힙영역에서 배열의 크기를 바꿀때, 즉 재할당이 일어날때, 메모리의 주소값이 바뀌기 때문에, 배열명은 포인터 상수라는 뜻에도 맞지않다. 또한 배열이지만, 배열의 선언문은 볼 수가 없다. 그래서 우리는 배열과 동적배열은 구분해서 생각해야 한다.


힙을 사용하기위해선 포인터를 선언했다. malloc으로 동적할당을 하는 것은 초기화 작업과 같다. 우리가 주목해야할 부분은 for문 내부에서 realloc을 이용할 힙 영역안에서의 재할당인다. 입력 받은 문자열의 크기에 따라서 재할당의 크기도 바뀐다. 이것은 실행시간에 결정되는 사항이다. 여기서는 간단한 예를 들었지만, 실제로 함수를 만들어 문자열의 길이, 문자열 내부의 원하는 부분에 삽입, 삭제, 조작하는 함수를 만들 수 있다. 이때도 memmove 함수를 사용한다.


input 함수는 원하는 곳에 문자를 대입하는 함수다. 원리는 간단하자. 삭제를 하는 함수도 위 코드를 참고하면 만들 수 있을 것이다.

입력한 만큼만 재할당을 하기 때문에, 추가적인 메모리의 손실이 일어나지 않는다.

다음 시간에는 동적배열을 활용하여 전화번호부를 만들어보고자 한다. 간단히 메모장에 결과를 저장하고 불러오는 기능을 만들려고 하는데 파일 입출력에 대해서 어느정도 알 필요가 있다.

반응형