이번 글은 서강대학교 소정민 교수님의 강의와 Ellis Horowitz의「Fundamentals of Data Structures in C」를 바탕으로 작성했음을 밝힙니다.
배열(Array)
배열(array)은 같은 타입의 변수들로 이루어진 유한 집합으로 정의됩니다.
추상적으로 정의하면, Array는 데이터를 저장하는 방법 중 <index, value>의 형식으로 저장하는 방법입니다. 즉, Array는 value만을 저장하는 것이 아니라(단순히 '일련의 연속적인 메모리 위치'가 아님), index를 붙여서 같이 저장하는 자료구조라고 할 수 있습니다.
1.1 ADT
- Object: <index, value>의 쌍으로 구헝된 집합(index와 value간에 mapping이 존재)
- Functions: retrieving a value, storing a value(value를 불러오거나 저장)
1.2 C에서의 Array
Array는 C에서 정말 많이 쓰는 자료구조이며, 많은 고급 자료 구조를 표현하는 데 이용됩니다.
Array는 메모리상 연속된 공간에 잡힙니다. 코딩을 통해 특정 메모리에 할당하라고 명령할 수는 없지만, 메모리를 잡을 때 특정 메모리(Base Memory)부터는 연속적으로 저장됩니다.
💡 C언어에서는 배열을 선언만 하고 초기화하지 않으면, 각 배열 요소에 아무런 의미를 가지지 않는 값이 저장되어 있게 됩니다. 따라서 초기화되지 않은 배열은 사용하지 않도록 주의를 기울여야 합니다.
1.3 배열의 특징
- 같은 타입의 데이터를 나열한 선형 자료구조 (sequence container) 입니다.
- 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것입니다.
- 연속된 메모리 공간에 순차적으로 저장됩니다.
- 논리적 저장 순서와 물리적 저장 순서가 일치합니다.
- 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용합니다.
- 배열의 크기는 고정. 선언할 때에 배열의 크기를 정하고, 변경할 수 없습니다.
1.4 배열의 장단점
장점
- 인덱스를 통해 모든 데이터에 직접 액세스하기 때문에 액세스 속도가 빠릅니다.
- 원소의 인덱스 값을 알고 있으면
O(1)에 해당 원소로 접근할 수 있습니다. - 즉, Random Access가 가능합니다.
- 원소의 인덱스 값을 알고 있으면
- 포인터 등 부가적인 정보가 없어 기록 밀도가 1입니다.
- 리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 되지 않지만, 배열은 부가정보 없이 데이터만 저장하기 때문에 기록밀도가 1입니다.
- 리스트나 그래프는 메모리에 분산시켜 데이터를 저장하고 포인터로 연결시킨 형태라 데이터외 부가 정보를 가지게 됩니다. 반대로 배열은 메모리의 연속된 공간에 데이터를 저장하고 인덱스를 이용한 연산을 통해 액세스 하기 때문에 부가정보가 필요 없습니다.
- 가장 간단하며 사용하기 쉽습니다.
단점
- 삽입과 삭제가 어렵고 오래 걸립니다.
- 원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 합니다. (연속된 메모리 공간에 저장되기 때문)
- 배열의 크기를 바꿀 수 없습니다.
- 배열은 처음 생성할 때 크기를 설정합니다.
- 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤 값을 복사해야 합니다.
- 연속된 메모리라서 공간 낭비가 발생합니다.
- 중간에 데이터가 삭제되면 공간 낭비가 발생할 수 있습니다. 또, 처음에 배열 크기를 100으로 생성했는데 10정도 밖에 쓰지 않으면 나머지 공간은 빈 공간으로 낭비가 발생합니다.
1.5 시간복잡도
- 삽입/삭제
- 배열의 맨 앞에 삽입/삭제하는 경우 :
O(n) - 배열의 맨 뒤에 삽입/삭제하는 경우 :
O(1) - 배열의 중간에 삽입/삭제하는 경우 :
O(n)
- 배열의 맨 앞에 삽입/삭제하는 경우 :
- 탐색
-O(1)
2. 구현
2.1 C
ex002.c
Implementing Basic Array
<#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
float sum(float[], int);
float input[MAX_SIZE], answer;
int i;
void main() {
for (i = 0; i < MAX_SIZE; i++)
input[i] = i;
answer = sum(input, MAX_SIZE);
printf("the sum is: %f\n", answer);
}
float sum(float *list, int n) {
int i;
float tempsum = 0;
for (i = 0; i < n; i++)
tempsum += list[i];
printf("address of list: %p\n", list);
return tempsum;
}
ex003.c
Printing Array with pointer
#include <stdio.h>
#include <stdlib.h>
void print1(int*, int);
void main() {
int one[] = { 0, 1, 2, 3, 4 };
print1(one, 5);
}
void print1(int* ptr, int rows) {
int i;
printf("address contents\n");
for (i = 0; i < rows; i++)
printf("%8p%5d\n", ptr + i, *(ptr + i));
}ex004.c
Dynamic Allocation using malloc and realloc
# include <stdio.h>
# include <stdlib.h>
void main() {
int i, n, m, * data;
printf("How many integers do you want to generate? ");
scanf_s("%d", &n);
data = malloc(n * sizeof(int));
printf("memory allocated at %p\n", data);
for (i = 0; i < n; i++)
data[i] = rand() % 100;
printf("How many integers do you want to generate additionally? ");
scanf_s("%d", &m);
data = realloc(data, (n + m) * sizeof(int));
printf("memory reallocated at %p\n", data);
for (i; i < n + m; i++)
data[i] = rand() % 100;
for (i=0; i < n + m; i++)
printf("%3d: %8d\n", i + 1, data[i]);
free(data);
}SourceCode
Work Hard, Play Hard 🔥🔥🔥