Cтраница 4
Например, если BM CTU стека задействовать очередь, то получится ширину ч который а нал oi и ч ей обходу лсрсна но уровням. Программа 5.11 - иня этого метода ( при условии, что используется рс изация с применением очереди, подобная вгрограмме 4.12); пример этого алгоритма и дсй тани показак ка рнс, 5 35, В части 6 будет исследоваться множество алгоритмов обработки фнс юнэ основанных на более сложных обобщен км к абстрактных типах данных очереди. [46]
Абстрактный тип данных очереди гарантирует целостность своей внутренней структуры данных. Клиенты не могут непосредственно манипулировать этой структурой. Только сам абстрактный тип очереди имеет доступ к своим внутренним данным. Клиенты могут инициировать выполнение только допустимых операций над представлением данных: операции, не предусмотренные открытым интерфейсом абстрактного типа данных, отвергаются некоторым адекватным образом. Это может означать выдачу сообщения об ошибке, завершение выполнения программы или просто игнорирование запроса этой операции. [47]
Широко применяемое в ЭВМ базирование данных делает целесообразным использование в языках переменных типа указателей, значения которых равны адресу области памяти. В описании базируемых величин указывается имя указателя, по которому осуществляется базирование. Применение абстрактного типа доступа [62] позволяет соотнести указатель с конкретным типом данных, что уменьшает вероятность ошибок обращения к памяти. [48]
В некоторых ситуациях процедура, привязанная к типу, может вызываться только для расширений типа, переопределяющих ее. Это обычно происходит в случае, когда привязанная к типу процедура не имеет естественной реализации или реализации по умолчанию, а имеет только хорошо определенные назначение и интерфейс. В этом случае объявляется абстрактный тип с отложенной привязкой. Для привязанной к типу процедуры требуется абстрактный интерфейс. [49]
В предыдущем примере диапазоны значений абстрактной функции sum и ее конкретной версии concsum совпадали, а именно представляли собой множество чисел, и, формулируя иначе результат, мы могли бы убедиться, что отображение аб стракции между типами диапазонов значений есть функция тождества В следующей главе мы увидим, что подобный вид преобразования можно рассматривать как треугольный, вершинам треугольника соответствуют абстрактный тип области определения, конкретный тип области определения и общий тип диапазона значений функции. В этом примере мы рассматриваем полный квадрат, хотя типы области определения и диапазона значений абстрактной функции ( а следовательно, также связанной с ней конкретной функции) совпадают. Однако полностью общий пример, включающий различные абстрактные типы области определения и диапазона значений, которые отличаются также от их конкретных партнеров, был бы гораздо утомительнее, но не дал бы более глубокого проникновения в проблему. [50]
Развивая дальше эту точку зрения, приходим к абстрактному типу данных дек ( double-ended queue, двухсторонняя очередь), в котором и вставки, и удаления разрешаются с обеих сторон. Его реализацию мы оставляем в качестве упражнений ( см. упр. [51]