Массивы представляют структуры, индексированные целыми числами. Что, если нам нужны другие виды ключей? Строки являются типичным примером. Нам могут понадобиться контейнеры, в которых критерием доступа является строка символов, такие как:
Предположим на минуту, что в первом случае все персоны, собранные в каталоге, имеют имена, отличающиеся первой буквой: Annie, Bertrand, Caroline … Тогда можно было бы использовать массив из 26 элементов, где индекс соответствовал бы коду буквы: 1 – для А, 2 – для В и так далее.
(рис 7.1) Совершенный хеш
Мы хешировали ключи (строки, представляющие имена) в целые числа из интервала 1...26. "Хеширование" понимается здесь по аналогии с приготовлением котлет – мясо пропускается через мясорубку и разделяется на порции. Более точно:
К возможных ключей называется функция h, которая отображает К в некоторый целочисленный интервал a…b.Другими словами, для любого key ∈ K функция дает значение i = h(key), такое, что a ≤ i ≤ b.
На практике обычно интервал задается в форме 0… capacity – 1 для некоторого целого capacity. h(key) задается в форме f(key) Mod(capacity) (по модулю емкости контейнера), где функция f возвращает целочисленное значение, приводимое к нужному интервалу взятием по модулю. Массив, применяемый для хранения данных, имеет размерность capacity.
В нашем примере используется примитивная capacity.
count – это размерность нашей задачи, то время, затрачиваемое на вычисление функции, есть O(1) или O(l), если учитывается длина ключа – l, но можно предположить, что K символов ключа, где К – константа.
Предположение, что в нашем примере все имена различаются по первой букве, приводит к тому, что
В большинстве случаев мы не можем получить совершенную хеш-функцию, даже с описанной выше функцией, вычисляющей сумму кодов всех символов. Для несовершенных функций встречаются коллизии, когда разные ключи дают одно и то же значение функции. Хорошая capacity. Реализация хеш-функций должна уметь справляться с коллизиями.
Одним из методов является так называемое открытое хеширование, когда массив комбинируется со связным списком. На последнем приведенном рисунке с совершенным хешированием массив непосредственно содержит все элементы и мог быть объявлен как
ARRAY[G]
При открытом хешировании мы могли бы использовать массив, элементами которого были бы связные списки:
ARRAY[LINKED_LIST[G]]
Каждый элемент массива с индексом i представляет список объектов, для которых i:
(рис 7.2) Открытое хеширование, использующее массив связных списков
При поиске или вставке элемента в хеш-таблицу с открытым хешированием первым делом ключ преобразуется в индекс, дающий вход в список, а затем производится последовательный просмотр списка. Первая операция имеет стоимость O(1), а вторая – O(c), где c – фактор коллизии – среднее число ключей, хешируемых на данный индекс. Если емкость массива capacity считать константой, то значение с для больших count и хорошо распределенной хеш-функции будет O(count/ capacity), а с учетом нашего предположения – O(count). Чтобы избежать линейной зависимости, необходимо периодически перестраивать массив, но тогда лучше использовать другую технику, называемую закрытым хешированием.
Закрытое хеширование, применяемое в классе HASH_TABLE библиотеки EiffelBase, не использует связных списков, а работает с массивом ARRAY[G]. В любой момент времени некоторые его позиции заняты, а некоторые – свободны:
(рис 7.3) Массив, реализующий хеш-таблицу при закрытом хешировании
Если при вставке i, как показано на следующем рисунке, то применяемый механизм последовательно будет испытывать другие позиции – i1, i2, i3, пока не найдет свободную ячейку:
(рис 7.4) Поиск свободной ячейки
Общий прием состоит в следующем: если i = f(key) Mod(capacity), то последующие позиции определяются как i + increment, i +2 * increment, i +3 * increment и так далее, все по модулю capacity. Величина increment вычисляется как f(key) Mod (capacity -1). Такой алгоритм используется в классе HASH_TABLE библиотеки EiffelBase (смотри метод search_for_insertion для изучения деталей).
Гарантирование завершения процесса поиска означает, что цикл имеет вариант и алгоритм всегда способен найти пустую ячейку. Это достигается подходящим подбором параметров и политикой перестройки массива при его заполнении. Фактически, мы не ждем до последней минуты, – перераспределение начинается, когда коэффициент заполнения достигает граничного значения – 80% в классе HASH_TABLE.
Поразительно, но такая политика в сочетании с хорошим выбором хеш-функции приводит к тому, что практически вставка и поиск требуют O(1) затрат (смотри ссылку в конце этой лекции на теоретический анализ сложности).
Такое поведение означает, что для практических целей хеш-таблицы почти так же хороши, как и массивы, но позволяют иметь произвольные ключи, так что хеш-таблицу с элементами, идентифицируемыми строковым ключом, можно рассматривать как массив, индексируемый строками, а не целыми.
Нахождение хеш-функций, приводящих к такому эффективному поведению, является в некотором роде искусством. Образцом и источником вашего вдохновения может послужить функция, используемая в классе HASH_TABLE.
Класс HASH_TABLE[G, KEY] является первым примером, где появляются два родовых параметра типа, а не один, как было ранее: G задает тип элементов, а KEY – тип ключей этих элементов. Этот класс можно использовать, например, для хранения объектов, которые представляют персоны, идентифицируемые именами:
personnel_directory: HASH_TABLE [PERSON, STRING ]
У этого класса есть несколько фундаментальных методов. Класс имеет единственную процедуру создания make. Для создания хеш-таблицы можно применить вызов:
create personnel_directory.make (initial_size)
Здесь initial_size – это некоторое положительное целое. Не имеет большого значения, каким его выбрать. Как следует из его названия, это просто некоторая подсказка для начального выделения памяти. Если вы зададите число много ниже реальной потребности, то это приведет во время выполнения к нескольким дополнительным перестройкам массива.
Рассмотрим запросы, существующие в классе. Чтобы узнать, есть ли в классе элемент с заданным ключом, используйте запрос
has (k: KEY ): BOOLEAN
Для получения элемента, ассоциированного с заданным ключом, если таковой есть:
item (k: KEY ) alias "[]": G assign put
— Элемент, ассоциированный с заданным ключом, если таковой есть,
— в противном случае – значение по умолчанию для типа G
ensure
default_value_if_not_present:
not (has (k)) implies (Result = computed_default_value)
Постусловие показывает, что если нет элемента с заданным ключом, то результатом является значение по умолчанию типа G (ноль для целых, false – для булевских, void – для ссылок). Это не лучший способ тестирования наличия элемента в таблице, так как там может существовать элемент, имеющий значение по умолчанию, так что предварительно стоит использовать запрос has в таких ситуациях.
Спецификация alias "[]" показывает, что так же, как и для элементов массива, возможно применение квадратных скобок для элементов хеш-таблиц, что позволяет писать:
personnel_directory ["Isabelle"]
Эта запись является синонимом:
personnel_directory.item ("Isabelle")
Форма с квадратными скобками короче и привычнее, так что она будет использоваться в дальнейшем.
Для вставки элемента в таблицу нужно задать как сам элемент, так и его ключ:
personnel_directory.put (that_person, "Isabelle") [8]
Это справедливо и тогда, когда ключ является атрибутом элемента:
personnel_directory.put (that_person, that_person.name)
Класс предлагает четыре операции вставки с одной и той же сигнатурой:
put (new: G; k: KEY ) — Команда-присваиватель для элемента.
forse (new: G; k: KEY )
extend (new: G; k: KEY )
require
not_present: not has (k)
replace (new: G; k: KEY )
Среди них extend имеет предусловие, устанавливающее применимость только тогда, когда элемента с заданным ключом нет в таблице; остальные три всегда применимы. Предложение "note" в начале класса объясняет, когда следует использовать тот или иной вариант. Я воспроизведу его здесь, опуская некоторые детали.
put, если вы хотите, чтобы вставка происходила только тогда, когда в таблице нет элемента с данным ключом, в противном случае ничего делаться не будет.force, если вы хотите делать вставку в любом случае. Это означает, что существующий элемент с данным ключом будет удален.extend, если вы уверены, что в таблице нет элемента с заданным ключом, – это обеспечит более быструю вставку.replace, если вы хотите заменить существующий элемент с заданным ключом, ничего не делая в противном случае.В первых двух случаях процедура будет устанавливать значение булевского запроса found, позволяющего узнать после вставки, был ли уже в таблице элемент с заданным ключом.
Объявление элемента с заданием псевдонима и команды-присваивателя выглядит так:
item (k: KEY ) alias "[]": G assign put
В результате доступна
personnel_directory ["Isabelle"]:= that_person
Фактически, это краткая форма записи вызова put, более простая, чем рассмотренная в примере 7.8 . Для удаления элемента с заданным ключом используйте:
remove (k: KEY )
Команда не имеет эффекта, если элемента с заданным ключом в таблице нет. Выяснить, что фактически происходило, может запрос removed.
Для удаления всех элементов служит процедура clear_all.
Выполняя эти операции, нет необходимости заботиться о размере структуры данных. Благодаря перестраиваемым массивам Eiffel, сами методы заботятся о выделении достаточного пространства для всех текущих элементов.
accommodate(n:INTEGER), который добавит в таблицу новые ячейки, не меняя уже существующие.Вот обзор стоимости операций хеш-таблицы.
| Операция | Метод класса HASH_TABLE | Сложность |
|---|---|---|
| Доступ по ключу | item, has |
O(1) |
| Вставка по ключу | put, force, extend |
O(count) |
| Замена по ключу | replace |
O(1) |
| Удаление по ключу | remove |
O(1) |
При работе с большими системами с большим числом объектов вы обнаружите, что хеш-таблицы станут одним из ваших любимых инструментов.
Массивы и хеш-таблицы являются индексируемыми структурами.
Структуры, к изучению которых мы приступаем, следуют другой политике. Они не используют ключей или другой идентифицирующей информации. Вы просто вставляете элемент, применяя для этого обычную процедуру:
put (x: G)
— Добавить x в текущую структуру.
Сравните c put(x:G, i:INTEGER) для массивов или с put(x:G, k:KEY) для хеш-таблиц. Когда же приходится получать элемент, у вас нет возможности его выбора. Вы делаете запрос
item: G
— Элемент, полученный из текущей структуры
require
not is_empty
У запроса нет аргументов (сравните с запросом item(i:INTEGER):G для массивов или с item( k:KEY):G для хеш-таблиц). Мы называем такие структуры распределителями по аналогии с автоматом, выдающим банки с напитком. Автомат, а не покупатель, решает, какую банку выдать покупателю.
(рис 7.5) Торговый автомат
Распределители отличаются политикой, используемой для выбора выдаваемого элемента.
У всех распределителей существуют четыре базисных метода: put и item с сигнатурами и предусловиями, показанными выше, а также булевский запрос
is_empty: BOOLEAN
— Правда, что элементов нет?)
и команда для удаления элемента:
remove
— Удалить элемент из текущей структуры.
require
not is_empty
Точно так же, как item не позволяет выбирать получаемый элемент, remove не позволяет выбирать удаляемый элемент. Удаляется тот элемент, который можно получить по запросу item, если выполнить его непосредственно перед вызовом remove.
Хорошая реализация распределителей должна выполнять все эти операции за время O(1). Примеры вскоре будут даны.
В некоторых библиотеках можно найти операции, которые комбинируют эффект item и remove: функцию, скажем, get, которая удаляет элемент, а в качестве результата выдает удаленный элемент. Такую функцию можно реализовать в терминах item и remove:
get: G
— Функция с побочным эффектом, нарушающая принципы методологии!
do
Result:= item
remove
end
Мы не будем использовать такие функции, так как они меняют структуру и возвращают результат, нарушая правило, что только команды, но не запросы, могут менять состояние структуры (принцип разделения команд и запросов). По причинам, объясненным в предыдущих лекциях, предпочтительнее позволять клиентам получать доступ и удалять элементы двумя разными методами – запросом, свободным от побочного эффекта, и командой.
В следующих двух разделах рассматриваются стеки и очереди. Мы не будем рассматривать очереди с приоритетами, но всегда можно обратиться к библиотеке EiffelBase и ознакомиться с классом PRIORITY_QUEUE.
Стек – это распределитель с политикой LIFO: элемент, к которому можно получить доступ, есть элемент, поступивший последним из существующих в распределителе. Этот элемент располагается в "вершине" стека, что соответствует естественному образу стека в обыденном смысле этого термина. Примером может служить множество словарей, громоздящихся на моем столе в предположении, что первым я могу взять словарь, находящийся на вершине этой груды (стека).
(рис 7.6) Стек
Операции над стеком часто известны как:
put);remove);item).Эти операции можно визуализировать.
(рис 7.7) Концептуальный образ стека
Стеки имеют множество применений в компьютерной науке. Два примера из реализации языка программирования: один – статический (разбор, иллюстрируемый в простейшем случае обработкой "польской нотации"), другой – динамический, управление вызовами программ в период выполнения.
Предположим, что вы хотите вычислить математическое выражение в "польской нотации" – форме, часто применяемой в калькуляторах, а иногда и во внутреннем представлении компиляторов и интерпретаторов. Преимущество этой нотации в том, что устраняется неопределенность порядка вычислений без использования скобок – каждый знак операции применим к операндам, непосредственно предшествующим знаку. Результат операции над операндами является операндом следующей операции.
Рассмотрим для примера выражение
2 + (a + b) * (c – d)
В польской записи оно выглядит так
2 a b + c d – * +
Как будет происходить вычисление этого выражения? Первым знаком операции является +, так что выполнится сложение операндов a и b, предшествующих плюсу. Затем выполнится операция вычитания, затем умножение двух вычисленных операндов, последним выполнится сложение полученного результата с константой 2. Для простоты все операции бинарны, но схема легко адаптируется на произвольную "-
Следующий алгоритм, использующий стек операндов s, вычисляет общее выражение в польской записи с бинарными операциями:
from — Инициализация пуста
until
"Все термы выражения уже прочитаны"
loop
"Чтение очередного терма выражения - x"
if "x является операндом" then
s.put (x)
else — x является знаком бинарной операции
— Получить два верхних операнда
op1:= s.item; s.remove
op2:= s.item; s.remove
— Применить операцию к операндам и поместить результат в стек:
s.put (application (x, op1, op2))
end
end
В алгоритме используются две локальные переменные op1 и op2, представляющие операнды. Функция application вычисляет результат применения бинарной операции к ее операндам, например, application('+', 2, 3) возвращает значение 5. На следующем рисунке показана ключевая операция алгоритма, соответствующая предложению else, – обрабатывается знак умножения для выражения нашего примера.
(рис 7.8) Вычисление выражения, записанного в польской нотации
Корректная реализация алгоритма должна справляться с ошибочным вводом (проверяя s.is_empty перед вызовом item и remove и проверяя, что x является знаком операции); необходимо также предусматривать возможность операций различной "-арности".
Наш второй пример лежит в основе поддержки исполняемой среды при реализации каждого современного языка программирования и присутствует в каждой операционной системе (это, конечно, сильное утверждение, но ни один контрпример не приходит на ум). Рассмотрим язык программирования, позволяющий методу вызывать другой метод, который, в свою очередь, может вызывать метод, и ситуация может повторяться. В результате появляется цепочка вызовов:
(рис 7.9) Вызов метода
В любой момент времени в период выполнения несколько методов – от p до t на рисунке – были вызваны, начали свою работу, но еще ее не завершили. Последний вызванный метод в этом случае называется текущим методом. Рассмотрим одну из его команд, например, присваивание x:= y + z. Если только x, y, z не являются атрибутами охватывающего класса, то они должны принадлежать текущему методу и быть либо его аргументами (но не x, поскольку аргументу нельзя присваивать значения), либо локальными переменными. Будем использовать термин "локальные" для обеих категорий. Для выполнения операторов программы, таких как присваивание, код, генерируемый компилятором, должен иметь доступ ко всем локальным переменным. Решением этой проблемы является создание для каждого вызова метода активирующей записи, содержащей его локальные переменные:
(рис 7.10) Стек периода выполнения и куча
Структура справа называется "кучей", она содержит объекты, получаемые в результате вызова процедуры создания или ее эквивалента. Для нашего обсуждения интерес представляет стек вызовов, также называемый стек периода выполнения (чаще всего просто стек), содержащий активирующие записи для всех текущих активных методов. Поскольку метод не может завершиться, пока не завершатся методы, вызовы которых он инициировал, и стартовавшие позже него, подходящей схемой активации является стратегия LIFO и стек будет подходящей структурой.
В момент вызова метода механизм создает новую активизационную запись с локальными переменными метода, инициализированными значениями по умолчанию, и аргументами метода, которые инициализируются значениями фактических аргументов, переданных в точку вызова. Эта запись размещается в вершине стека. При завершении работы метода запись удаляется из стека и на вершину поднимается следующая в стеке запись.
Преимущество использования стека в том, что записи представляют не различные методы, а только различные сеансы выполнения. Как результат, эта техника позволяет поддерживать
Как и для некоторых других структур этой лекции, существуют две общие категории реализации стеков, основанные на массивах и на связных списках. Наиболее общая реализация использует массив rep типа ARRAY[G] и целочисленную переменную count с инвариантом
count >= 0 ; count <= rep.capacity
Здесь емкость capacity представляет число элементов массива (upper – lower + 1). Для массивов, индексируемых с 1, элементы стека, если они есть, хранятся в позициях от 1 до count.
(рис 7.11) Реализация стека на массиве
ARRAY число элементов массива известно как count и как capacity, инвариант свидетельствует, что значения этих атрибутов эквивалентны. Не следует путать атрибут count для массивов с count для стеков – атрибутом, который задает число элементов стека, разворачиваемого на массиве.
Мы уже сталкивались с этим различием, когда рассматривали список, реализованный на массиве. В обоих случаях реализация построена на массиве, в то время как спецификация задает другой контейнерный тип.
В этой реализации запрос item, который дает элемент, расположенный в вершине стека, просто возвращает rep[count] – элемент массива в позиции count. Достаточно просто может быть реализована и команда remove: count:= count -1, а команда put(x) – как
count:= count + 1 [9]
rep.force (x, count)
Здесь используется команда force для массивов, заставляющая перестроить массив, если отведенной памяти становится недостаточно.
Более подробно с реализацией можно познакомиться, изучая класс ARRAYED_STACK из библиотеки EiffelBase (фактически классу не нужен rep, поскольку он наследуется от ARRAY, но концептуально это эквивалентно, а мы все же формально наследование еще не изучали). Использование force в алгоритме для put означает, что можно не беспокоиться о размере массива – массив будет создаваться с установками по умолчанию, а потом подстраиваться под нужный размер данных.
Конечно,
Перестройка массива, применяемая в Eiffel, не является общедоступной в других программных средах, поэтому там часто стеки, базируемые на массиве, имеют ограниченную емкость. Соответствующий класс есть и в Eiffel – BOUNDED_STACK. Для такого стека наряду с count используется и запрос capacity, и булевский запрос is_full, чье значение дается выражением count = capacity. В этом случае, так же, как существует предусловие для команды remove, будет существовать предусловие и для команды put – is_full. Реализация этой команды для такого стека использует put для массива, а не force, как в вышеприведенном примере 7.9. Выполнение предусловия гарантирует корректность выполнения put.
Все рассмотренные выше операции имеют сложность O(1).
Вариантом стека ограниченной емкости, реализованного на массиве, является стек, растущий вниз:
(рис 7.12) Реализация на массиве стека, растущего вниз
В этом представлении count более не является атрибутом, вместо этого появляется скрытый атрибут free, задающий индекс первой свободной ячейки. Запрос count по-прежнему остается доступным, но реализуется он теперь функцией, возвращающей значение capacity – free.
Инвариант теперь устанавливает, что free >= 0 и free <= capacity. Сравните этот инвариант с инвариантом для count в предыдущем представлении стека.
Случай free = 0 соответствует is_full, а free = capacity соответствует is_empty. Элементы стека, если они есть, располагаются в позициях от capacity до free +1. Метод remove реализуется просто: free = free +1, а put реализуется как
rep.force (x, free)
free:= free – 1
Если память ограничена и приходится одновременно работать с двумя стеками, то можно оба стека располагать на одном массиве, но на разных его концах; один растет вверх, другой вниз, что отражено на следующем рисунке:
(рис 7.13) Два стека на одном массиве
Преимущество этого подхода в том, что оптимальным образом используется память, если только оба стека не достигают своего максимума одновременно, поскольку
max (count1 + count2) ≤ max (count1) + max (count2)
В упражнении вас попросят написать реализацию класса TWO_STACK, воплощающего эту идею.
Наряду с реализацией на массивах вполне допустимо строить стек на связном списке. Действительно, связный список, изученный ранее в этой лекции, содержит готовую реализацию стека. Рисунок ниже иллюстрирует этот подход: первая ячейка является вершиной стека, а остальные – телом стека.
(рис 7.14) Связный стек
Операция put(x) реализуется просто как rep.put_front(x), где rep задает связный список. Аналогично, item реализуется как rep.first и так далее. Класс LINKED_STACK в EiffelBase обеспечивает такую реализацию. Все базисные операции имеют сложность O(1), хотя чуть медленнее, чем их двойники на массивах, например, put_front из класса LINKED_LIST, а следовательно, и put из LINKED_STACK должны сперва создать и отвести память ячейке LINKABLE.
Все базисные операции над стеком во всех рассмотренных реализациях выполняются за константное время, за исключением, как отмечалось, редкой операции force в перестраиваемом массиве, реализующем стек.
| Операция | Метод в классе стека | Сложность | Комментарий |
|---|---|---|---|
| Доступ к вершине | item |
O(1) | |
| Вталкивание на вершину | put |
O(1) | При автоматической перестройке иногда O(count) |
| Удаление с вершины | remove |
O(1) |
Очереди с их политикой FIFO ("первый пришел – первый ушел") полезны во многих приложениях. Вот типичные примеры.
(рис 7.15) Поставщик – потребитель, взаимодействие через буфер
Последний рисунок может служить концептуальным представлением любой очереди, а не только буфера – элементы поступают с одного конца, а удаляются с другого.
Как и для стеков, реализация может использовать для представления либо массив, либо связный список. В последнем случае очередь выглядит так:
(рис 7.16) Очередь на связном списке
Операция put(v) реализуется просто как rep.put_front(v) (здесь, как обычно, rep задает item возвращает remove – удаляет его. Класс LINKED_QUEUE из EiffelBase сопровождается инвариантом
is_always_after: not empty implies rep.after
Выполнение инварианта гарантирует, что курсор всегда находится в конце списка.
Представление очереди массивом немного изощреннее, чем для стеков, поскольку необходимо добавлять элементы на одном конце, а удалять на другом. В этом случае требуются два указателя, которые в классе ARRAYED_ QUEUE называются in_index и out_index, и оба являются закрытыми атрибутами. Запрос count по-прежнему дает число элементов очереди. Естественным, но не лучшим решением является хранение элементов очереди в интервале in_index .. out_index, как показано на рисунке:
(рис 7.17) Возможное состояние до очереди на массиве
Реализация для такого представления очевидна:
remove: out_index = out_index + 1,
put(v): rep[in_index]:= v; in_index:= in_index +1
При таком подходе память, отведенная массиву, может быть быстро исчерпана при добавлении элементов, даже если происходит их удаление, поскольку пространство в начале массива останется неиспользованным:
(рис 7.18) Очередь на массиве в момент достижения правого конца массива
Решение: когда маркер in_index превосходит емкость capacity, то операция put должна по кругу возвращаться в начало массива, аналогично должна вести себя remove. Концептуально массив превращается в круг:
(рис 7.19) Массив как бублик
Вот пример реализации put в классе ARRAYED_QUEUE:
put (v: G)
— Добавить v как новый элемент.
do
if count + 1 = rep.count then grow end
rep [in_index]:= v
in_index:= (in_index + 1) \\ capacity
if in_index = 0 then in_index:= capacity end
end
Первый оператор выделяет массиву дополнительную память, если ее действительно не хватает. Процедура grow просто вызывает resize для нашего массива. Увеличение in_index выполняется по модулю capacity (i \\ j дает остаток от деления i на j, а i // j дает целую часть от деления нацело). Реализация настраиваемая (смотри заключительный if…), массив rep может индексироваться от 1 до capacity, но может – рекомендованное упражнение – индексироваться, начиная с нуля.
Очереди при подходящей реализации столь же эффективны, как и стеки.
| Операция | Метод в классе очереди | Сложность | Комментарий |
|---|---|---|---|
| Доступ к старейшему элементу | item |
O(1) | |
| Добавление элемента | put |
O(1) | При автоматической перестройке иногда O(count) |
| Удаление старейшего элемента | remove |
O(1) |
Контейнерные структуры данных, вроде тех, что рассматривались в данной лекции, являются хранилищами объектов. Зачастую на таких структурах одно и та же операция применяется поочередно ко всем объектам структуры. Этот процесс называется итерированием структуры данных. В дополнение к этому термину механизм, осуществляющий итерирование, также имеет собственное имя.
Мы уже видели многие примеры итерирования контейнерных структур. Все они соответствуют общему образцу: если your_list относится к типу LINKED_LIST [T] или к более общему типу LIST [T] (для любой реализации списка) и есть процедура
some_opereation(x: T)
то следующая схема итерирует операцию над списком
from
your_list.start
invariant
— Все операции перед курсором уже подверглись операции some_operation
until
your_list.after
loop
some_operation (your_list.item)
your_list.forth
variant
your_list.count – your_list.index + 1
end
Как альтернатива, операция применяется только к элементам, которые удовлетворяют условию, заданному функцией your_condition (x:T): BOOLEAN. В этом случае тело цикла следует изменить следующим образом:
if your_condition (your_list.item) then
some_operation (your_list.item)
end
Другие варианты итерирования включают:
Выделение общих схем является правильной стратегией. Еще лучше создать повторно используемый код, чтобы не приходилось каждый раз писать его заново. И на самом деле, на Eiffel можно применять итерационный механизм без написания циклов, используя такие методы, как do_all и do_if, которые применимы ко всем классам, задающим списки. Они раз и навсегда охватывают все предшествующие циклические структуры, так что два последних примера можно записать гораздо проще:
your_list.do_all (agent your_operation)
your_list.do_if (agent your_operation, agent your_condition)
Здесь agent your_operation обозначает объект, который представляет процедуру your_operation, готовую к применению к каждому элементу, а agent your_condition аналогично задает запрос. Для понимания деталей следует дождаться рассмотрения агентов в последующих лекциях.
Структуры данных, рассмотренные нами, относятся к наиболее важным в программировании, но они далеко не единственные. Мы уже упоминали о деревьях, и в следующих лекциях поговорим о них подробнее. Обобщением деревьев является полезное во многих приложениях, например, в сетях, понятие графа, ориентированного или неориентированного, а также понятие
 (рис 7.20) Дональд Кнут (2005) |
 (рис 7.21) Альфред Ахо (2007) |
Широко известный учебник по структурам данных и алгоритмам. Часть из задуманного 7-томного выпуска, из которого вышли в печать три тома (некоторые главы четвертого известны в виде отдельных выпусков).
Компактный обзор наиболее важных алгоритмов и структур данных. До сих пор остается великолепным обзором в этой области.
Великолепный современный учебник.
Изложение принципов проектирования, применяемых при построении качественных, повторно используемых библиотек; сопровождается примерами из EiffelBase.
| Abstract complexity | Абстрактная сложность | Activation record | Активизационная запись |
| Actual generic parameter | Фактический родовой параметр | Array | Массив |
| Complexity | Сложность | Call chain | Цепочка вызовов |
| Cursor | Курсор | Correctness | Корректность |
| Dynamic typing | Dispenser | Распределитель | |
| Formal generic parameter | Формальный родовой параметр | FIFO | Первый пришел – первый ушел |
| Generic derivation | Родовое порождение | Generic class | Универсальный (родовой) класс |
| Hash table | Хеш-таблица | Genericity | Универсальность |
| Linked list | Связный ( |
Heap | Куча |
| List | Список | LIFO | Последний пришел – первый ушел |
| Priority queue | Очередь с приоритетами | Parameter | Параметр |
| Stack | Стек | Queue | Очередь |
| Static typing | Run-time stack | Стек периода выполнения | |
| Validity | Правильность |
Дайте точные определения всем терминам словаря.
Добавьте новые термины в карту концепций, построенную в предыдущих лекциях.
Напишите класс DOUBLE_STACK [G], реализующий два стека на одном массиве. Вы можете назвать соответствующие методы put1, put2, remove1, remove2 и так далее. Стеки имеют ограниченный размер, так что позаботьтесь включить правильные предусловия и инварианты класса.
Реализация, которую мы рассматривали для очередей, построенных на массиве, подобна классу ARRAYED_QUEUE из библиотеки EiffelBase, но без наследования, использует массив rep, индексируемый начиная с единицы.
put, данную в тексте, напишите процедуру remove и процедуру создания make, задающую пустую очередь.Напишите процедуру обращения списка для двусвязного списка и списка, построенного на массиве, поместив их в класс, наследующий от соответствующих классов EiffelBase: TWO_WAY_LIST или ARRAYED_LIST.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.