(자료구조론 필사) 2장 배열과 구조

**출처) C로 쓴 자료구조론 2판, 이석호, 실리콘프레스 교보문고

 

2.1 배열

 

-추상데이터타입(ADT)

: 배열은 인덱스와 값 <index, value>의 쌍으로 구성돈 집합으로서 정의된 각 인덱스는 그 인덱스와 관련된 값을 가진다.

: 수학 용어로 이를 대응(correspondance) 혹은 사상(mapping)이라고 부른다.

: 그러나 ADT를 고려할 때는 배열에서 수행 가능한 "연산"들에 더 관심을 두게 된다, 새로운 배열의 생성을 제외하고 대부분의 프로그래밍 언어에서는 배열에 대해 값을 추출하는 연산과 저장하는 연산만을 제공한다.

• object
  • <index, value> 쌍의 집합. index 부분은 0 ~ n-1로 나타냄
  • 1차원 배열의 index 부분은 { 0, 1, ... n-1 }
  • 2차원 배열의 index 부분은 { (0,0), (0,1), ,.. (0, n-1), (1, 0), ... (n-1, n-1)}
• function
  • A ∈ Array, i∈ index, x ∈ item or value, j∈ integer
  • Array Create(j,list) = return j 차원의 한 array
  • Item Retrieve(A,i) = if ( i ∈ index) then return 배열 A 인덱스 i 값의 item
  • Array Store(A,i,x) = if (i ∈ index) then return 새로운 <i,x> 쌍이 삽입된 배열 A

 

-C언어에서의 배열

: C에서 1차원 배열은 변수의 이름 끝에 중괄호를 추가하여 묵시적으로 선언함

: 1차원 배열의 구현은 컴파일러가 연속적인 메모리를 할당하며 이루어짐, 각 메모리 장소는 1개의 자료형을 수용할 수 있다.

: 배열 list의 list[0]의 주소는 기본주소(base address)라고 한다. 

: 사용하는 컴퓨터의 정수 크기 sizeof(int)라고 한다면 list[i]의 메모리 주소는 (기본주소)+i*sizeof(int)가 된다

 

: 배열이 함수의 매개변수로 사용될 때 C에서 이를 처리하는 방식

: C 함수의 모든 매개변수는 함수 내에서 선언이 되어야 하지만, 배열에 대해서는 새로운 저장 공간이 함수 내에 할당이 되지 않기 때문에 1차원 배열의 범위는 메인 프로그램에서만 정의된다. -> 매개변수로 함수에 전달하거나 전역변수로 접근해야함

---

2.2 동적으로 할당된 배열

 

-프로그램을 작성할 때 종종 사용할 배열의 크기를 결정하기에 곤란한 경우가 존재 -> 이 결정을 실행시간까지 미루었다가 필요한 배열의 크기의 적당한 추정치가 나올 때 배열을 할당하는 것 (malloc 사용)

 

-2차원 배열

: C언어에서는 다차원 배열을 표현하기 위해 소위 배열의 배열을 이용함

: 예를 들어, int x[3][5]의 경우 실제로 길이가 3인 1차원 배열 x가 생성이 되는데, x의 각 원소는 길이가 5인 1차원 배열이다

: C는 원소 x[i][j]을 찾을 때 제일 먼저 x[i]에 있는 포인터에 접근함, 이 포인터는 배열의 행 i의 0번째 원소의 메모리 주소를 제공하는데, 이 포인터에 j*sizeof(int)를 더하면 행 i의 [j]번째 원소, 즉 x[i][j]의 주소가 결정된다.

:C는 추가로 calloc과 realloc의 메모리 할당함수를 제공하는데, 이 두 가지는 동적할당 배열에 아주 유용

: 함수 calloc은사용자가 지정한 양의 메모리를 할당하고 할당된 메모리를 0으로 초기화 (할당된 비트가 모두 0으로 설정), 그리고 할당된 메모리의 시작에 대한 포인터를 반환한다.

: calloc으로 1차원 정수 배열 정의

int *x;

x=calloc(n,sizeof(int));

 

: 함수 realloc의 경우 malloc이나 calloc으로 이미 할당된 메모리 크기를 재조정하며, realloc(p,s)의 경우 포인터 p가 가리키는 메모리 블록의 크기를 s로 변경한다는 의미이다

---

2.3 구조와 유니언

 

-구조

: 배열이 같은 타입의 데이터 모임인 반면 C언어에서는 struct라고 표기하는 구조라는 개념을 이용해 서로 다른 타입의 데이터를 그룹화하는 방법을 제공한다.

: 각 항목은 타입과 이름으로 식별된다.

: 각각의 필드에 값을 할당하거나 변경할 경우 사용되는 연산자는 '.'이며, 이 연산자는 구조 내에서 특정 멤버를 선택하는데 사용된다.

: typedef 명령문을 사용하여 구조 데이터 타입을 생성할 수 있음

ex)

typedef struct humanBeing{

             char name[10];

             int age;

             float salary;

 }

 

or

 

typedef struct{

             char name[10];

             int age;

             float salary;

} humanBeing;

 

:여기서 humanBeing의 경우 구조의 정의를 통해 정의된 타입 이름이며, 이후 다음과 같이 변수 선언이 가능함

     -> humanBeing person1, person2;

+typedef키워드 없이 struct키워드만 이용할 경우 main 함수에서 구조체를 선언할 때 매번 struct를 쓸 필요가 없음

 

-유니언

: C언어에서 제공하는 union의 경우 선언은 구조와 유사하지만 union의 필드들은 그들의 메모리 공간을 공유해야함.

: union의 한 필드는 어느 한 시점에서 활성화되어 사용이 가능하다는 것을 의미한다.

:C