Реализация класса HashTableIterator

⇐ Предыдущая 1 23

Этот класс должен просматривать данные, разбросанные по хеш-таблице. Поэтому он более интересен и более сложен с точки зрения реализации, чем класс HashTable. Обход элементов таблицы начинается с поиска непустого блока в массиве списков. Обнаружив непустой блок, мы просматриваем все узлы этого списка, а затем продолжаем процесс, взяв другой непустой блок. Итератор заканчивает обход, когда просмотрен последний непустой блок. Итератор должен быть привязан к списку. В данном случае переменной hashTable присваивается адрес конкретного экземпляра класса HashTable. Поскольку класс HashTableIterator является дружественным по отношению к HashTable, он имеет доступ ко всем скрытым данным-членам последнего, включая массив buckets и его размер numBuckets.

Переменная currentBucket является индексом связанного списка, который просматривается в данный момент, а currBucketPtr – указателем этого списка. Обход каждого блока осуществляется итератором, встроенным в класс LinkedList. На рисунке 31 показано, как итератор обходит таблицу с четырьмя элементами.

Рис.7

Метод SearchNextNode вызывается для обнаружения очередного списка, подлежащего обходу. Просматриваются все блоки, начиная с cb, пока не встретится непустой список. Переменной currentBucket присваивается индекс этого списка, а переменной currBucketPtr – его адрес. Если непустых списков нет, происходит возврат с currentBucket = -1.

// начиная с cb, искать следующий непустой список для просмотраtemplate <class t>void HashTableIterator<T>::SearchNextNode(int cb){ currentBucket = -1; // если индекс cb больше размера таблицы, прекратить поиск if (cb > hashTable->numBuckets) return; // иначе искать, начиная с текущего списка до конца таблицы, // непустой блок и обновить скрытые элементы данных for (int i=cb; i<hashTable->numBuckets; i++) if (!hashTable->buckets[i].ListEmpty()) { // перед тем как вернуться, установить currentBucket равным i // и в currBucketPtr поместить адрес нового непустого списка currBucketPtr = &hashTable->buckets[i]; currBucketPtr ->Reset(); currentBucket = i; return; }}

Конструктор инициализирует базовый класс Iterator и присваивает скрытому указателю hashTable адрес хэш-таблицы. Непустой список обнаруживается с помощью вызова SearchNextNode с нулевым параметром.

// конструктор. инициализирует базовый класс и класс HashTable// SearchNextNode идентифицирует первый непустой блок в таблицеtemplate <class T>HashTableIterator<T>::HashTableIterator(HashTable<T>& hf): Iterator<T>(hf), HashTable(&hf){ SearchNextNode(0);}

С помощью метода Next осуществляется продвижение вперед по текущему списку на один элемент. По достижении конца списка функция SearchNextNode настраивает итератор на следующий непустой блок.

⇐ Предыдущая 1 23

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных