Циклы для каждого и итераторы
Часто бывает необходимо перебрать все элементы структуры данных и для каждого элемента выполнить некоторое действие. Обычно при записи алгоритмов на неформальном языке используется конструкция цикл для каждого; например, в случае множества M можно записать следующий фрагмент программы:
цикл для каждого элемента x из множества M | действие(x); конец цикла
В большинстве структур данных такой цикл можно реализовать, пользуясь другими действиями, возможными для структуры этого типа. Например, для списка можно использовать следующий фрагмент программы:
установить указатель в начало списка; цикл пока указатель не в конце списка | действие(элемент за указателем); | передвинуть указатель вперед; конец цикла
Множество отличается от всех других структур данных тем, что цикл для каждого невозможно смоделировать, пользуясь другими предписаниями множества. Поэтому выполнение такого цикла должно быть обеспечено реализацией множества. Метод построения цикла для каждого в сильной степени зависит от используемого языка программирования и от конкретной библиотеки классов или подпрограмм. Как правило, создается некоторый объект, позволяющий последовательно перебирать элементы структуры. Внутреннее устройство такого объекта зависит от структуры данных и скрыто от программиста. Объект такого типа обычно называют итератором или энумератором. С итератором возможны два действия:
- проверить, есть ли еще элементы структуры данных, которые не были перебраны на предыдущих шагах;
- получить следующий элемент структуры данных.
Реализация структуры данных должна обеспечить реализацию предписания, которое создает и инициализирует объект типа итератор, предназначенный для перебора элементов структуры.
В случае множества М цикл для каждого записывается с помощью итератора примерно так:
итератор := начать перебор элементов множества M; цикл пока итератор.есть еще элементы | x := итератор.получить следующий элемент множества; | действие(x); конец цикла
Мы рассмотрели наиболее важные структуры данных, используемые в программировании, и методы их реализации. Конечно, этими примерами не исчерпывается все многообразие структур данных. Однако, большинство реальных примеров либо аналогичны рассмотренным, либо получаются комбинацией нескольких элементарных структур — например, реализация массива множеств может использовать списки или деревья. Искусство программиста состоит в том, чтобы выбрать структуру данных, наиболее подходящую для решаемой задачи, чтобы в ней отсутствовали массовые операции, память расходовалась экономно и поиск выполнялся быстро. И, пожалуй, один из главных критериев — это простота и изящество программы, которая получается в результате.
