C Data Structure - 테이블

자 오늘은 테이블과 해시이다.

자료구조는 자료를 저장하는 구조를 나타내는 것이지만, 그 구조 속에 들어 있는 값을 찾아서 꺼내는 것 또한 자료 구조의 영역 범위 내이다.

그래서 배열 리스트, 연결 리스트, 스택, 큐, 그래프, 트리 등에서 탐색에 해당하는 부분을 구현해왔다. 그 중 테이블이라는 자료구조에 대해 볼 것인데, 이 구조는 특별하다. 탐색 속도가 어마어마하게 빠르다. 기록해보자.

테이블이란 무엇인가?

이것이 테이블 자료구조이다. 키와 값으로 구성되어 있는 구조를 테이블 자료구조이다. 보통 언어에 따라 다르지만 키와 값으로 구성되어있는 자료구조를 사전(Dictionary), 맵(Map) 구조라고도 한다.

테이블 자료 구조에서의 핵 중요한 규칙

1. 테이블 자료구조에서는 키와 값이 한 쌍의 형태로 이루어 저장이 된다.
이 때 값은 뭐 하나가 되어도 좋고 여럿이 되어도 좋다.

2. 테이블 자료구조에서는 키 값은 중복되어서는 아니 된다.
아래의 그림을 보자

학생을 관리하는 테이블이다. 소위 말하는 학번이라는 것은 각 학생들에게 부여되는 고유 번호이다. 그러니까 학번 1번을 외치는 것만으로도 수 많은 학생들 중에서 '나루토'를 특정 지을 수 있어야한다. 이것이 실생활에서 적용되는 예이다. 

그런데 위의 테이블에서 학번 3번을 부르면 네! 하고 손을 드는 학생이 에렌과 아르민으로 두 명인 상황이 만들어졌다. 이런 경우에는 학번을 부르고 나서 이름까지 불러야 그제서야 에렌과 아르민을 특정 지을 수 있는 것이다.

만약 이런 상황에서 3번으로 중복되는 에렌과 아르민이 포함되어 있는 전교생 수천명이 시험을 본다고 생각하자. 그러면 자동적으로 OMR 채점을 진행할텐데 이 때 기계는 각 학생들을 구분할 때, 학번을 이용하여 학생을 특정 짓지만 에렌과 아르민 자식들이 포함되어 있는 경우가 존재하기 때문에 모든 학생들을 대상으로 학번과 이름을 한 번에 확인해야한다.

테이블 자료구조에는 보통 키 값을 이용하여 데이터를 특정짓기 때문에 위와 같은 경우를 만들지 않기 위해서 키의 중복을 허용하지 않도록 하겠다. (뭐 허용을 시키는 경우도 있긴 하지만 말이다.)

3. 키가 없으면 값을 저장할 수 없다.

키를 활용해 값을 특정 지어야 하기 때문에 키를 비울 수는 없다.

4. 값을 특정 짓는다는 것의 의미.

위 그림을 봤을 때, 3번이라는 학번을 통해 에렌을 특정 지었는데 달리 말하면 탐색이 완료되었다는 소리이다. 

이 개념들을 숙지한 채로 아래의 예시를 보면 된다.

기본적인 테이블 예시

테이블이 될 구조체 정의

구조체 정의를 이용하여 배열로 선언하면 테이블 형태의 구조를 만들 수 있다.

테이블에 데이터를 등록하는 함수

인덱싱이 특이하다는 것을 확인할 수 있다.

메인 함수 실행 부분

임의로 입력된 값을 키 값으로 활용한다.

49번 줄에서는 키 값을 이용해 원하는 값을 바로 뽑아낸다. 이런 것이 가능한 이유가 무엇인가? 

데이터를 삽입할 때, 키의 값 '번째'에 해당하는 배열 칸에 넣었으니,

값을 뽑아올 때에도 키를 인덱스로 던져주면 키의 값 '번째'에 해당하는 배열 칸에서 뽑아온다.

말이 탐색이지, 사실 탐색이라고 할 것도 없이 그냥 인덱싱일 뿐이다. 그냥 *(배열이름+인덱스(키값)) 이렇게 연산해주면 접근 가능하기 때문에 포스팅 초반에 겁나 빠르다고 한 것이다.

전체 코드 및 실행 결과

#include <stdio.h>
#include <string.h>
 
#pragma warning(disable:4996)
 
struct user
{
    int useruid;
    char username[20];
    int age;
};
 
typedef struct user user;
 
void RegisterUser(user* u, int useruid, char* username, int age)
{
    u[useruid].useruid = useruid;
    strcpy(u[useruid].username, username);
    u[useruid].age = age;
    return;
}
 
int main(void)
{
    user acc[100];
    user search;
 
    int uid = 0, age = 0;
    char name[20] = { 0, };
 
    // 유저 정보 입력
    printf("유저의 등록 번호를 입력하세요(0~100) : ");
    scanf("%d", &uid);
    printf("유저의 이름을 입력하세요 : ");
    scanf("%s", name);
    printf("유저의 나이를 입력하세요 : ");
    scanf("%d", &age);
 
    // 유저 등록
    RegisterUser(acc, uid, name, age);
 
    // 유저 조회
    printf("찾고자 하는 유저의 등록 번호를 입력하세요(0~100) : ");
    scanf("%d", &uid);
 
    // 등록 번호를 통해 한 번에 검색 -> 키를 인덱스로 바로 쓰기 때문이다. 계산만 한 뒤 접근하면 끝ㄷㄷ
    search = acc[uid]; // 값이 구조체 구조 그대로 복사됨(얕은 복사)
 
    // 조회 결과 출력
    printf("조회 결과 --- \n");
    printf("유저 등록 번호 : %d \n", search.useruid);
    printf("유저 이름 : %s \n", search.username);
    printf("유저 나이 : %d \n", search.age);
 
 
    return 0;
}

 

문제점

근데 위와 같은 테이블은 빠른건 빠른거지만 중요한 문제가 있다.

1. 학번이 원래 0부터 100까지의 자리였지만 갑자기 년도+번호와 같은 식으로 변해버리면 분명히 문제가 된다.
원래 99번이었던 번호가 20210099로 바뀐다면 이 또한 문제가 될 것이다. 

기존의 방법대로라면 user acc[20210100]; 이렇게 선언을 해야, 20210099 같은 인덱스가 먹혀도 먹힐 것이다. 그런데 이러한 크기의 배열 선언이 과연 정상일까?

모든 키가 0부터 시작해서 뭐 적절히 1,000 값으로 끝나면 좋겠지만 실제로는 그렇지가 않다. 학번은 보통 해당 년도와 고유 번호를 합쳐서 만든다. 군번은 말할 것도 없다 이런 번호 키들을 수용하기 위해서 user acc[20210100]; 이렇게 비정상적인 배열 선언을 할 수도 없는 노릇이다.

이를 다음 포스팅 때 해결하고자 한다.