[자료구조] [2] 배열과 구조체

배열

- 배열의 직접 접근 방식

 k번째 항목을 참조할 때 이 항목의 위치(주소)가 바로 계산되어 항목을 참조할 수 있다. 

 이것을 직접 접근 방식이라고 한다. 항목 접근의 시간 복잡도는 O(1).

 

* 연결리스트의 접근 방식과 비교

 연결 리스트에서는 k번째 항목을 참조할 때 맨 처음 항목부터 k번을 반복적으로 찾아가야 한다.

 이것을 순차 접근 방식이라고 한다. 항목 접근의 시간 복잡도는 O(n). 하지만 다른 장점이 있다.

 

 

- 1차원 배열

- 배열에서는 모든 요소들이 메모리의 연속된 공간에 저장된다.

아래와 같은 정수 배열을 선언한다면,

 int A[6];

 

A는 배열이 저장된 공간의 시작 주소(또는 기본주소)가 된다. 

배열의 요소들은 메모리의 연속된 공간에 저장되어 있기 때문에 각 항목들의 주소가 기본 주소로부터 일정하게 계산된다.

A[0] <- 배열 A의 기본 주소(시작 주소) : base
A[1] <- base + sizeof(int)
A[2] <- base + 2 * sizeof(int)
A[3] <- base + 3 * sizeof(int)
.
.
.

 

- 배열은 선언하면서 초기화할 수 있다. 데이터가 일부만 주어져 있다면 앞에서 부터 초기화 되고, 나머지 항목들은 0이 된다.

int A[6] = {1,2,3,4};      // A[4],A[5]는 0

- 배열은 대입연산자로 한꺼번에 복사할 수 없으며, 각 항목을 일일이 복사해야 한다.

int A[4] = {};
int B[4] = {1,2,3,4};

A = B;    // 오류! 배열은 한꺼번에 복사 불가

 

- 2차원 배열

- 2차원 배열의 선언 : 자료형 배열이름[행의_크기][열의_크기]

int A[4][3] = { {1,2,3}, {4,5,6}, {7,8,9}, {10,11,12} };

- 2차원 배열 요소의 실제 메모리 안에서의 위치는 다음과 같은 순서로 저장된다.

A[0][0]

A[0][1]

A[0][2]

A[1][0]

A[1][1]

...

 

- 함수의 매개변수로서의 배열

• 배열을 매개변수로 전달하는 것은 주소를 전달하는 것이다. 이 주소를 통해 배열의 모든 항목을 참조할 수 있다. 따라서 그 함수에서 배열의 내용을 수정하면 원래의 배열이 수정된다. 
• 배열을 매개변수로 전달할 때에는 배열의 길이도 전달해야 한다. 그렇지 않으면 함수에서 배열의 길이를 모른다.

 

---

 

구조체

배열이 같은 자료형의 데이터 모임이라면, 구조체는 다양한 자료형의 데이터 모임.

구조체는 기존의 자료형들을 조합해 새로운 자료형을 만드는 방법.

 

 

- 구조체도 배열과 같이 선언과 동시에 초기화 가능. 중괄호 내의 값들은 구조체의 필드 순서대로 할당.

Student a = { 201803156, "홍길동", 96.3" }

- 구조체끼리 대입 연산 가능. 구조체 변수에 구조체를 복사할 수 있다.

 

- 함수의 매개변수로서의 구조체

• 함수의 매개변수로서 전달할 때는 구조체의 주소를 넘겨줘야 한다. (call by reference)
• call by value 방식은 새로운 매개변수가 만들어지고 값이 복사되는 것이다. 

typedef struct {
	double a;
    double b;
} Test;

void reset_Test(Test t) { // call by value -> 새로운 매개변수 t가 만들어지고 a의 내용이 t에 "복사" 된다.
	t.a = t.b = 0.0;
}

void main() {
	Test a = {1.0,2.0};
	reset_Test(a); // call by value이기 때문에 a는 초기화 되지 않는다!
}