[ Arrays for search, insert, delete ] Packed unsorted

Array (배열)

: 연속된 주소, 같은 타입

array는 에를 들어, 8개의 자리가 있어도 꽉 차있지 않을 수도 있음 > 빈 칸이 있을 수도 있다는 것

 

how to store items in an array? (배열에 데이터를 어떻게 저장하는가)

packed vs unpacked

• 빈 자리를 한 쪽으로 모으는지 여부에 따른 것
• packed : 사용하는 칸을 한 쪽으로 뭉쳐놓기
• unpacked : 사용하지 않는 칸과 사용하는 칸이 섞여 산발적으로 데이터가 흩어져있음

sorted vs unsorted 

• item들이 정렬된 상태를 유지하는지의 여부에 따른 것
• 같은 값들이 없다는 전제 하에 이루어짐
• sorted : 정렬된 상태
• unsorted : 정렬되지 않은 상태

 

Packed Unsorted 

index	0	1	2	3	4	5	6
value	3	0	2	7	8	4	1

• 가장 간단한 방법
• item의 개수를 표시하는 변수가 따로 필요함 : 한 쪽에 데이터가 몰려있기 때문에 유의미한 데이터의 개수를 세주면, 그것이 유효한 배열의 size라고 볼 수 있다.

 

#include <stdio.h>

int a[100] = {0};
int size = 0;

int arr_search(int a[], int n, int x){
    // 존재 하면 index를, 존재하지 않으면 -1을 리턴함
    if(n == 0) return -1;
    else{
        for(int i = 0; i < n; i ++){
            if(a[i] == x) return i;
        }
    }
    return -1;
}
void arr_insert(int a[], int n, int x){
    // search 를 먼저 수행 > 존재하지 않으면 insert
    if(arr_search(a, n, x) == -1){
        //맨 끝에 값을 추가함
        a[n] = x;
        printf("%d is inserted in index %d\n", x, n+1);
        size++;
    }
    else printf("%d already exists\n", x);
    
}
void arr_delete(int a[], int n, int x){
    
    //search를 먼저 수행 > 존재하면 delete
    int check = arr_search(a, n, x);
    if(check == -1) printf("There is no %d\n", x);
    else{
        //끝에 있는 값을 삭제할 값으로 옮기고 배열의 크기를 줄임
        a[check] = a[n-1];
        printf("deleted %d\n", x);
        size--;
    }
}

int main(int argc, const char * argv[]) {
    
    int x;
    char choose;
    while(1){
        // 배열 출력
        for(int i = 0; i < size; i++) printf("%2d ", i);
        printf("\n");
        for(int i = 0; i < size; i++) printf("%2d ", a[i]);
        printf("\n");
        
        scanf(" %c", &choose);
        //search
        if (choose == 's'){
            scanf("%d", &x);
            int check = arr_search(a, size, x);
            if(check == -1) printf("there is no data %d\n", x);
            else{
                printf("Data is at index %d\n", check);
            }
        }
        
        //insert
        if (choose == 'i'){
            scanf("%d", &x);
            arr_insert(a, size, x);
            
        }
        
        //delete
        if (choose == 'd'){
            scanf("%d", &x);
            arr_delete(a, size, x);
            
        }
        
        //quit
        if (choose == 'q'){
            break;
        }
    }
}

실행결과

• search : O(n) - Linear search
• insert : [search, O(n)] O(1) - insert 전에 search를 실행해야함 (같은 값 중복 방지)
• delete : [search, O(n)] O(1) - delete 전에 search를 실행해야함 

size : 현재 배열의 크기, insert 시 들어가야할 위치라고 볼 수 있다. 배열의 크기 -1 = 배열의 인덱스이기 때문에

* delete할 때 마지막 값은 size -1 임을 잊지 말자!