Study & Dev | Blog Archive | Структуры данных и алгоритмы. Практика. Контейнеры

Структуры данных и алгоритмы. Практика. Контейнеры

January 19, 2007

1. В методическом пособии раздел посвященный принципам проектирования контейнеров и собственных структур данных начинался с того, что я привел интерфейс класса множества.

```
template <class T>
```
```
 class Set {}
```

Вам необходимо продолжить данный код. Написав реализацию для всех методов класса множества. Напоминаю, что в программировании множество считается конечным набором элементов имеющих один тип, которые содержатся в множестве не повторяясь. Операции над множеством вспомните из курса математики. И только если будет очень плохо, то обращайтесь ко мне.

2. Особый интерес представляет собой такая структура данных как MAP (ассоциативный массив). В данном массиве для обращения к хранимым элементам используются как индексы не целые числа, а произвольные типы данных: строки, числа: целые и вещественные, даже пользователем определенные структуры и классы. Вам необходимо создать код класса MAP. Класс должен быть шаблонным, в качестве его параметров будут выступать тип индекса и тип значения хранящегося в MAP. Для этого контейнера необходимо определить следующие операции.

ValueType & operator [] (const KeyType & key); // оператор индексирования.

Swap (Map<KeyType, ValyeType> & anm); // функция для перемены местами содержимого двух MAP-ов;

Для реализации внутреннего устройства попробуйте использовать линейный список, каждый узел подобного списка должен состоять из двух информационных компонент: ключ и значение, и разумеется необходимо наличие ссылки на следующий элемент, что впрочем обязательно для любого использования линейного списка.

В общем случае когда мы говорим о MAP, то понятие порядка следования элементов не определено, однако на практике все разработки MAP выполняют автоматическое упорядочение всех помещаемых внутрь этого контейнера пар (Ключ, Значение) по Ключу для ускорения процесса поиска. Поэтому вам необходимо при реализации оператора индексирования предусмотреть подобную сортировку при добавлении нового элемента в MAP, а при поиске использовать метод половинного деления;

a) разработайте функцию

append (const Map<KeyType, ValyeType> & another)

данная функция должна выполнять добавление к нашему контейнеру (this) содержимое контейнера another;

b) также разработайте функцию

remove (const Map<KeyType, ValyeType> & another)

,

которая будет служить для удаления из нашего контейнера (от имени которого была вызвана данная фунция)

всех элементов которые содержатся внутри контейнера another;

c) обязательно реализуйте функцию проверки того есть ли в заданном контейнере элемент с заданным значением ключа:

```
bool containsKey (KeyType & kt);
```

d) разработайте класс итератора для map: данный итератор должен позволять перемещаться по парам (ключ-значение)

хранящимся внутри MAP. Код должен быть написан так, чтобы созданный вами итератор можно было использовать, например, так:

Map<string, string>::iterator I = my_map.begin ();

Map<string, string>::iterator eom = my_map.end ();

```
 
```
```
while (I != eom)
```
```
{
```

 cout <<  I->key << “ = ” << I->value << endl;

```
 I++;
```
```
}
```

Разумеется, что вам необходимо будет предусмотреть методы: begin(), end().

'''3)''' Данное задание является развитием предыдущего примера. Необходимо создать класс ''Hash_map'' – ключевое отличие данного контейнера от предыдущего в том, что хотя в качестве ключа может быть использован произвольный тип данных, но для этого типа данных существует понятие ''Hash_function'' (''Хеш-функции''). Данная функция получает на вход как параметр объект типа ''KeyValue'', а возвращает некоторое целое число. Очень важно, что вычисление этого целого значения должно идти очень быстро. В качестве внутреннего устройства для данного контейнера используется hash-таблица. Подумайте над тем, как ее можно реализовать. Обычно делается так: результат вычисления хеш-функции – это индекс элемента в этой hash-таблице. Такая модель накладывает ограничения на тип объектов, которые могут выступать как ключ hash. Давайте создадим базовый класс Hashable с ''чисто виртуальной функцией''

```
int getHashCode (void)
```

. Также все остальные типы данных, которые мы захотим использовать как ключ должны быть производными от этого класса.

Categories: Структуры данных и алгоритмы

Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Контейнеры

Поиск

Недавнее

Архив

Разделы