[자료구조] 배열

안녕하세요! 오늘은 배열에 대해서 알아볼텐데요!

후.. C는 배열과 포인터 그리고 메모리만 잘쓰면 정말 날라다닌다고 말할 수 있을거라고 생각하는 사람중 한명입니다!

 

아래 첨부된 예제코드를 보면서 같이 따라해보셔도 좋습니다!

 

배열은 허접한 위의 그림처럼 연속된 메모리 공간이라고 생각하시면 편할듯합니다!

 

그러므로 시작주소를 알고있다면 어디든 무려 O(1)에 접근 가능합니다! 굉장히 빠르죠?

        // array
        int intArray[11] = {0,};

        // Random access is possible because the array data is stored sequentially
        // in the logical and physical memory.
        // access O(1)
        int i = 0, j = 0;
        for(;i < 10; i++) {
                intArray[i] = i+1;
                printf("intArray[%d] = %d\n", i, intArray[i]);
        }

 

그럼 사람들은 생각할거에요! "그럼 모든 자료구조는 배열로 만들면 되겠군요!"

 

하지만 아쉽게도 그건아니에요! ㅠㅠ

 

배열은 연속된 데이터 공간이므로 중간에 삽입이나 삭제를 원하면 shift연산을 해주어야합니다!

        // array insert
        // insert O(n)
        for(i = 10; i > 5; i--) {
                intArray[i] = intArray[i-1];
        }
        intArray[5] = 100;

        for(i = 0; i < 10; i++) {
                printf("intArray[%d] = %d\n", i, intArray[i]);
        }

        // array delete
        // insert O(n)
        for(i = 5; i < 10; i++) {
                intArray[i] = intArray[i+1];
        }

 

한칸씩 다 움직여줘야하기 때문에 무려 O(n)이나 걸리죠 ㅠ

 

이것만 단점이 아닙니다!

 

중간에 배열의 크기를 변경시켜주려면 배열을 다시 만들어야하거든요!

 

그래서 처음에 배열 크기를 매우 크게잡으면 메모리 낭비가 심하고 너무 조금잡으면 시간낭비가 심하죠?

 

참으로 애매합니다!

 

그래서 삽입과 해제가 자유로운편인 링크드리스트가 등장했던거죠 ㅎㅎ 이건 다음시간에 같이알아봐요!

 

배열은 또한 배열이름이 포인터와 유사하게(절대 같지 않아요! size 찍어보시면 아실 수 있습니다! 꼭 해보세요) 사용할 수 있습니다!

 

        // access by pointer
        for(i = 0; i < 10; i++) {
                printf("*intArray+%d = %d\n", i, *intArray+i);
        }

 

그리고 배열은 배열의 배열을 만들 수 있습니다!

 

배열의 배열의 배열의 배열의..... 배열도 만들 수 있죠!

 

그리고 컴파일러가 배열의 배열도 다연속적인 메모리 공간에 잡아주기 때문에 어디든 O(1)에 접근 가능합니다!

 

        // high-order arrays
        // Also, Random access is possible because the array data is stored sequentially 
        // in the logical and physical memory.
        int _2DIntArray[100][100] = {0,};
        for(i = 0; i < 10; i++) {
                for(j = 0; j < 10; j++){
                        _2DIntArray[i][j] = 100*i + 2*j;
                        printf("%d\t", _2DIntArray[i][j]);
                }
                printf("\n");
        }

또한, 다차원 배열도 포인터로 접근가능하죠?

 

다만 주의하셔야하는게 괄호를 매우 조심히 쓰셔야합니다! 안그러면 원인 모를 버그를 만나실 수도 있거든요!

 

연속된 숫자를 넣다가 연속되지 않은 숫자를 배열에 넣었을때 갑자기 달라지시는 것을 볼 수 있거든요! 조심하세요!

        // access by pointer
        for(i = 0; i < 10; i++) {
                for(j = 0; j < 10; j++){
                        printf("%d\t", *(*(_2DIntArray+i)+j));
                }
                printf("\n");
        }

        for(i = 0; i < 10; i++) {
                for(j = 0; j < 10; j++){
                        printf("%d\t", *(_2DIntArray[i]+j));
                }
                printf("\n");
        }

여기까지 우선 배열에 대해서 설명하고 다음시간에 링크드리스트로 찾아 뵙도록 하겠습니다!

 

감사합니다!

---

전체 코드입니다!

 /*
data structure test
*/
#include <stdio.h>

int main() {
        // array
        int intArray[11] = {0,};

        // Random access is possible because the array data is stored sequentially
        // in the logical and physical memory.
        // access O(1)
        int i = 0, j = 0;
        for(;i < 10; i++) {
                intArray[i] = i+1;
                printf("intArray[%d] = %d\n", i, intArray[i]);
        }

        // array insert
        // insert O(n)
        for(i = 10; i > 5; i--) {
                intArray[i] = intArray[i-1];
        }
        intArray[5] = 100;

        for(i = 0; i < 10; i++) {
                printf("intArray[%d] = %d\n", i, intArray[i]);
        }

        // array delete
        // insert O(n)
        for(i = 5; i < 10; i++) {
                intArray[i] = intArray[i+1];
        }

        for(i = 0; i < 10; i++) {
                printf("intArray[%d] = %d\n", i, intArray[i]);
        }

        // access by pointer
        for(i = 0; i < 10; i++) {
                printf("*intArray+%d = %d\n", i, *intArray+i);
        }

        // high-order arrays
        // Also, Random access is possible because the array data is stored sequentially 
        // in the logical and physical memory.
        int _2DIntArray[100][100] = {0,};
        for(i = 0; i < 10; i++) {
                for(j = 0; j < 10; j++){
                        _2DIntArray[i][j] = 100*i + 2*j;
                        printf("%d\t", _2DIntArray[i][j]);
                }
                printf("\n");
        }

        // access by pointer
        for(i = 0; i < 10; i++) {
                for(j = 0; j < 10; j++){
                        printf("%d\t", *(*(_2DIntArray+i)+j));
                }
                printf("\n");
        }

        for(i = 0; i < 10; i++) {
                for(j = 0; j < 10; j++){
                        printf("%d\t", *(_2DIntArray[i]+j));
                }
                printf("\n");
        }


        return 0;
}