Войти
Nebula CommunityСтатьи

Разбор кода Nebula Device2. Часть3. Контейнеры (статья 3 - Строковый список и хэш-таблица)

Автор:

Строковый список и хэш-таблица


У небулы есть класс строкового нода, строкового списка и хэш-таблицы. Их и рассмотрим в этой статье.

Класс nStrNode отличается от класса nNode наличием объекта типа nString с названием, говорящим само за себя, name. По всей видимости, разработчикам понадобился класс списка, к элементам которого можно обращаться по именам. Рассмотрим операции. В конструктор можно передать сишную строку - это инициализирует внутренний объект name. Можно передать сразу и C-строку, и указатель на void:

struct Dummy{} dummy;
nStrNode n1;
nStrNode n2(&dummy);
nStrNode n3(“Unknown”);
nStrNode n4(“I am dummy”, &dummy);

Если нужно изменить имя нода или задать его позже, то для этого предназначен метод SetName(), принимающий сишную строку и не возвращающий никаких значений. Чтобы узнать имя нода, вызовите через его объект или указатель метод GetName(), который и возвратит вам сишную строку с именем нода или нуль, если имя еще не было задано.

nStrNode n;
n.SetName(“Hello, world”);
printf(n.GetName());
> “Hello, World”

Методы GetSucc()/GetPred() претерпели несущественные изменения, заключающиеся в преобразовании указателя, возвращаемого одноименными методами класса nNode, в указатель на nStrNode.

Класс nStrList - это расширение класса nList для работы с именнованными нодами. Методы GetHead(), GetTail(), RemHead(), RemTail() - это обертки над одноименными методами класса nList, которые перед возвращением указателя преобразовывают его в указатель на nStrNode. Для поиска элемента по имени, предназначен метод Find(), который заключается в неэффективном переборе элементов и сравнении их имен с заданной C-строкой. Ну с точки зрения понятности и уменьшения количества кода эффективность то возросла. Позже будет рассмотрен специальный вид списка, в котором разработчики решили в какой-то степени проблему неэффективного поиска элементов по их имени.


Демо1:
+ Показать

Класс nHashTable прелставляет собой хэш-таблицу. Реализован как массив списков nStrList. Размер таблицы можно задавать только в конструкторе. Хэш-таблица типа nHashTable позволяет хранить объекты типа nStrNode, но имеется возможность более быстро находить их по содержащейся в них строке. Это происходит следующим образом: по си-строке вычисляется хэш, который играет роль индекса в массиве htable списков типа nStrList. По этому хэш-индексу берется соответствующий элемент массива - объект типа nStrList, в который помещается или в котором ищется нод с заданным именем. Класс довольно прост. Для добавления нода используется метод Add(), для поиска - Find().

Демо2:

+ Показать

17 мая 2016