arrayTable

이번에는 table 중에서 array로 만든 table을 만들어 보도록 하겠습니다. 

 

 

 

arrayTable의 ADT를 살펴봅시다. ADT와 class 선언은 영상을 보면서 따라쳐 봅시다. [영상첨부]

---

* 템플릿을 적용했기 때문에 메서드의 선언 및 정의를 하나의 헤더파일(ex. arrayTable.h)에 몰아주세요 

 

template <class tableKeyType, class tableDataType>
int
Table<tableKeyType, tableDataType>
::search(tableKeyType key)
{
    int pos;
    for (pos = 0; pos < entries && T[pos].key != key; pos++);

    return pos;
}

---

template <class tableKeyType, class tableDataType>
Table<tableKeyType, tableDataType>
::Table()
{
    entries = 0; // entries를 0으로 초기화
}

template <class tableKeyType, class tableDataType>
void
Table<tableKeyType, tableDataType>
::insert(tableKeyType key, tableDataType data)
{
    assert(entries < MAX_TABLE); // full이 아니면, ((!isFull())
    int pos(search(key)); // key값을 주고 search results

    if (pos == entries) // 존재 안하면
        entries++;
    T[pos].key = key;
    T[pos].data = data;
}

---

// lookup은 쉬우니 그림은 생략하겠습니다

template <class tableKeyType, class tableDataType>
bool
Table<tableKeyType, tableDataType>
::lookup(tableKeyType key, tableDataType& data)
{
    int pos(search(key));
    if (pos == entries) // data가 존재하지 않으면
        return false;
    else // data가 존재하면
    {
        data = T[pos].data;
        return true;
    }
}

---

원래 insert와 delete에는 policy(정책)가 존재합니다. 프로그램 마다 insert와 delete하는 방식이 다르기 때문입니다. 여기에서 insert에 대한 policy는 언급하지 않았지만 delete에서 어떤 policy가 적용되었는지 살펴봅시다. (이후에 insert, delete policy가 또 등장합니다.)

delete policy:

1. vaild 필드를 만들어 1이면 의미 있는 데이터, 0이면 의미 없는 데이터로 나눔

2. 어차피 해당 필드는 쓸모 없으므로 밑에 있는 데이터 끌어 올리기

... 여러가지 생각해볼 수 있는데 우리는 "2번"을 적용해 봅시다. (1번을 적용 안한 이유는 관리하기 힘들어서 !!)

template <class tableKeyType, class tableDataType>
void
Table<tableKeyType, tableDataType>
::deleteKey(tableKeyType key)
{
    int pos(search(key));
    if (pos < entries) // data 존재하면
    {
        --entries;
        T[pos] = T[entries]; // 덮어쓰기
    }

}