[Data Structure] CHAP 2. Arrays (배열) - C언어 ver.

지난 챕터 linear list에 이어 이번 챕터에서는 배열에 대한 내용을 기록하려고 한다.

✅ 배열의 ADT
✅ 실행 함수(add, remove 등)에 따른 big-O() 차이
위 내용에 대해 정리하고, Structures and Unions에 대해 간단하게 정리하려고 한다.

---

1. 배열의 ADT

저번 list의 ADT와 마찬가지로 배열도 ADT로 나타낼 수 있다. 배열의 main method로는

• get(int i) >> index i인 요소를 삭제하지 않고 값만 리턴
• set(int i, obj o) >> index i인 요소의 값을 o로 대체하고 대체 전 값 리턴
• add(int i, obj o) >> index i에 새로운 요소 o 추가
• remove(int i) >> index i값 제거 후 index i값 리턴

이 있다. Additioanl method로는 size(), isEmpty()도 있다.

 

ADT Array is
	objects : A set of pairs <index,value> where for each value of index there is a value from the set item.
    Index is a finite ordered set of one or more dimensions, for example,
    {0,...,n-1} for one dimension, {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}
    for two dimensions,etc.
    
    functions :
    	for all A ∈ Array, i ∈ index, x ∈ item,j,size∈integer
        
    Array Create(j,list) ::= return an array of j dimensions where list
    						is a j-tuple whose ith element is the size of
                            the ith dimension. Items are undefined.
    Item Retrieve(A,i) ::= if(i∈index) return the item associated with 
    						index value i in array A
    Array Store(A,i,x) ::= if(i in index)
    						return array that is identical to array A except the
                            new pair<i,x> has been inserted else return error

이런 식으로 ADT를 쓸 수 있고, objects 부분은 역시 바꿀 수 없다. functions는 접근 방법을 알려주고있고 저기에 나온 세 개의 함수는 사용해줘야 한다.

---

2. 배열 실행 (Big-O)

배열에 다양한 함수를 실행시켜 값을 얻거나 중간 요소 삭제를 할 수 있다. 이런 것들을 Big-O rotation으로 나타낼 수 있다.

 

2-1. O(1)의 예시 _ get(i), set(i), size, isEmpty

main method중 get(i)를 실행한다고 해보자. get()은 index i인 값을 return하는 함수이므로 원하는 인덱스에 가서 값을 추출하는 한 번의 과정만 거치면 된다. 그러므로 O(1)로 표기한다.

2-2. O(2)의 예시 _ add(i,o), remove(i,o)

add를 실행한다고 해보면, add는 index i에 값이 o인 값을 추가하는 것이므로 index i 이후의 요소를 뒤로 한 칸씩 밀어낸 후 빈 자리에 o를 삽입하는 것이다. Worst case는 i가 0인 경우로, index의 크기가 n이라면 밀어내는 과정을 n번 한 뒤에야 값을 추가할 수 있게 된다. n+1이라고 볼 수 있겠지만 최고차항만 남기므로 n이라고 해야한다. 따라서 O(n)으로 나타내게 된다.

2-3 add, remove가 O(1)인 경우 _ circular array(환형 배열)

환형 배열은 시작과 끝이 이어져있는게 특징이라서 add(0,x)나 remove(0,x)의 경우 맨 뒤에 붙여넣는 것과 같게 되므로 중간에 끼워넣을 때처럼 다른 값들을 이동시킬 필요가 없어진다. 따라서 O(1)이 된다.

---

3. 구조체와 공용체 (Structure and Union)

구조체와 공용체는 자료구조를 C로 배울 때에만 다루고 JAVA로 배울 땐 다루지 않는다고 하셨다. 1학년 전공에서 간단하게 배웠던 부분이라 리마인드만 했다.

• arrays(배열) : 배열은 같은 타입의 요소들만 같은 배열에 담을 수 있다.
• Structures(구조체) : 구조체는 다른 타입의 요소들을 담을 수 있다. 구조체 값을 꺼낼 때에는 .으로 연결한다.

typedef struct {
	char name[5];
    int age;
    float salary;
   }person;

구조체는 위 코드와 같이 선언하며, 만약 age에 2라는 값을 넣고 싶다면, person.age = 2 로 작성한다.

• Unions(공용체) : 다른 자료형들에게 한 장소를 빌려주는 느낌으로 이해하면 될 것 같다.

union int_or_float {
	int i;
    char f;
}

공용체는 위 코드와 같이 쓰며, 위와 같이 쓰면 int와 char 중 사이즈가 최대인 sizeof(int)만큼의 메모리가 할당된다. 한 번에 한 자료형에게만 메모리를 할당해준다.

 

즉, union 속 요소들 중 byte size가 가장 큰 타입에 맞춰 메모리를 할당한다.