Н. Джехани - Язык Ада (1988) (1160771), страница 23
Текст из файла (страница 23)
Х, У, х.: РЕМСЕ РОК-ТТ; Операции семантически связаны с пакетом РЕ»ФСЕ РОК Т, а не с типом Т. Они должны быть квалифицированы именем пакета. Конечно, надобность в квалификации может быть устранена с помощью спецификатора использования няе РЕгФСЕ РОК Т', Однако операции остаются связанными с пакетом РЕХОЕ РОК Т, а не с типом Т. Тип ОКО ЯЕТ, описанный в предыдущем разделе, представляет собой пример описания абстрактного типа данных, использующий возможности языка Ада.
Его «ограждением» является пакет ОКОЕКЕО ЯЕТ2. 3.6. Примеры пакетов и программирование с пакетами Приведем несколько примеров для иллюстрации других возможностей использования пакетов. Первый пример, управление таблицей символов, представляет важную часть любого компилятора.
Таблица символов реализована сначала в виде массива, а затем в виде упорядоченного бинарного дерева. Спецификации пакета таблицы символов не изменяются при изменении реализации. Второй пример представляет пакет, который реализует множество очередей с приоритетами, которые могут быть использованы для планирования работ с различными приоритетами в операционной системе. Последние два примера, задача о несовпадвюиФих подпоследовательностлх и задача о восьми Фберзях, иллюстрируют метод паквгы проб и ошибок для нахождения решения задач.
Затруднение при этом подходе в том, что число возможных кандидатов при решении может быть очень велико. Следовательно„все кандидаты не должны генерироваться и проверяться на соответствие решению [%'1В71]. Множество возможных кандидатов должно быть значительно снижено без потери кандидатов, которые могут представлять требуемое решение. Читатель должен попытаться решить задачи до того, как эти решения ему будут предложены. 3.6.1. Управление таблицей символов Задача состоит в написании программы управления таблицей символов. Должны быть предусмотрены операции, выполняющие следующие действия: 1. Добавление элемента и связанной с ним информации в таблицу символов. 2.
Поиск информации, связанной с элементом в таблице символов. 3. Определение, заполнена или нет таблица символов. 4. Проверка присутствия элемента в таблице символов. 5. Восстановление таблицы символов. Только уникальные элементы будут заноситься в таблицу символов. Добавление не производится, если таблица символов заполнена.
Элементы представляют собой строки длиной 20 символов (заполненные, если необходимо, пробелами), а таблица символов должна хранить по крайней мере 200 элементов. С элементом таблицы символов связана только информация о том, представляет ли он собой идентификатор переменной, имя функции или процедуры, ключевое слово либо имя метки. Пример представляет упрощенную версию реальной таблицы символов, потому что отсутствует управление блочной структурой и связанная с элементами информация является явной. Спецификация пакета БУМВОЬ ТАВ1.Е МАХАОЕВ имеет вид рас)сайе БУМВОЬ ТАВ1.Е МА(чАОЕК В )Ч: сопя!апг:= 200; — размер таблицы символов (ТЕМ $1к.Е: сопзгап(:= 20; — задавать константы символическими — именами является хорошим стилем — программирования.
Это улучшает — удобочитаемость программы и упрощает ее — модификацию при изменении значений констант Гуре 1ТЕМ (я пезг ЯТВ1МО(1..1ТЕМ Б1УЕ); (уре 1ТЕМ ТУРЕ 1з (ЧАВ, НЛЧ, РКОС, КЕУ%Р, 1.АВЕ1.); ргоседпге АРО(Х: гп 1ТЕМ; 1: 1п 1ТЕМ ТУРЕ); (ппсйоп 1М ТАВЬЕ(Х: !п 1ТЕМ) геГпгп ВООЬЕА)Ч; 1ппсйоп ОЕТ(Х: (п 1ТЕМ) гегпгп 1ТЕМ ТУРЕ; )ппсйоп Н5ЬЬ ге(пгп ВООЬЕА)4; ргосейпге СЬЕАВ4 — пустая таблица епй ЯУМВОЬ ТАВ1.Е МА1ЧАОЕК; Таблица символов реализуется в виде массива. Поиск элементов происходит путем последовательного просмотра массива. Глава 3 рас)саре бог)у ЯУМВОЬ ТАВЬЕ МАХАСЕК !з гуре 1ТЕМ 1ХРО !з гесогй 1Вх 1ТЕМ; Т! 1ТЕМ ТУРЕ; епг! тесов!; ЯТ: аггау (1..Х) о1 !ТЕМ !ХААС; — представление таблицы символов ЬАБТ: 1ХТЕСЕК гапке О..Х:= О; — входы в таблицу символов есть БТ(1..ЬАБТ) ргоседпге АОО(Х: )п 1ТЕМ; 1: !п 1ТЕМ ТУРЕ) !з Ьея!п ЬАЯТ:= ЬАБТ + 1; — предполагается, что элемент добавляется, — только когда таблица символов — не заполнена и элемент не — присутствует в таблице ЯТ(ЬАБТ).11): = Х; БТ(ЬАБТ).Т: = 1; епг! А))Р; !ппсйоп 1Х ТАВЬЕ(Х: !п 1ТЕМ) ге!игл ВООЬЕАХ !з Ьерп 1ог ) !п 1..ЬАБТ !оор — поиск элемента — в таблице; — цикл не выполняется, — если ЬАЯТ равен О И ЯТ(Ю).11) = Х Феп ге!пгп ТЛЕ; епг! И; епд !оор; ге!пгп РАЬЯЕ; епг! 1Х ТАВ1.Е; 1нпсВоп СЕТ(Х: !п 1ТЕМ) ге!ига 1ТЕМ ТУРЕ !з — функция СЕТ должна вызываться — только после проверки присутствия элемента — Х в таблице Ьерп гог Я !п !..ЬАБТ !оор И ЯТ(Я).1О = Х Феп ге!пгп ЯТ())Т; епг! И; епг! 1оор; епд СЕТ; 1ппс!!оп НЛЛ.
ге!ига ВООЬЕАХ !з Пакеты Ьей!и ге!пгп 1 АКТ = Х; епй ГЫЬЬ; ргосеппге С1.ЕАК 1я Ьей(п ЬАБТ:= О; епй С1.ЕАК; епй БУМВОЬ ТАВ1.Е МАХАОЕК; Такое простое представление таблицы символов не будет эффективным при выполнении большого числа поисков элементов. Хеш-таблицы или представление в виде упорядоченных бинарных деревьев будут предпочтительными, потому что среднее время поиска элементов в таких таблицах намного меньше.
3.6.1.1. Другой вариант представления таблицы символов Пакет ЯУМВОЬ ТАВЬЕ МАХАОЕК сейчас будет реализован с использованием представления таблицы символов в виде упорядоченного бинарного дерева. Поскольку никакие изменения в спецификациях пакета ВУМВОЬ ТАВЬЕ МАХАОЕК или в семантике определенных в нем подпрограмм не производятся, то программные модули, используюшие пакет ЯУМВОЬ ТАВЬЕ МАХАОЕК, не нужно будет модифицировать. Представление таблицы символов в виде бинарного дерева иллюстрирует использование ссылочных типов и показывает, как с помошью генератора петт создаются и размещаются динамические объекты. Процедура !ХЯЕКТ для добавления элемента Х и связанной с ним информации в бинарное дерево с корнем К описывается как ргосейнге 1ХЯЕКТ(Х: !и 1ТЕМ; 1; !и 1ТЕМ ТУРЕ; К: !и оп( ХЕХТ Е1.ЕМЕХТ); которая абстрактно описывается как И К = ппй (Ьеп добавить элемент Х со связанной с ним информацией 1 к К е!яИ Х < К.ПЭ 1Ьеп 1ХЯЕКТ(Х, 1, К.ЬЕРТ); е1яе 1ХЯЕКТ(Х, 1, К.К1ОНТ); епо И Алгоритмы работы других процедур очевидны.
Для разнообразия в функциях 1Х ТАВЬЕ и ОЕТ вместо итерации используется рекурсия: рас)гаке Ьог!у БУМВОЬ ТАВЬЕ МАХАОЕК !я !уре !ТЕМ 1ХРО; — неполное описание типа (уре ХЕХТ Е1.ЕМЕХТ (я ассезз 1ТЕМ !ХА; Глава 8 1!О гуре 1ТЕМ 1ХРО !з — полное описание типа гесогй 1Вл 1ТЕМ; Т: 1ТЕМ ТУРЕ; ЬЕРТ, К1ОНТ: ХЕХТ Е1.ЕМЕХТ; епй гесогй; КООТ. ХЕХТ ЕЬЕМЕХТ', — указывает на корень таблицы — символов, реализованной в виде — бинарного дерева; она используется — как глобальная переменная. — К первоначально равен ппй, — который представляет начальное — значение по умолчанию. Х()М-ЕЬЕМЕХТБ: 1ХТЕОЕК гапйе О..Х:= О„ ргосейпге А1)О(Х: !и 1ТЕМ; 1: !п 1ТЕМ ТУРЕ) !з — процедура А1)О использует процедуру — !СЕКТ для реализации описанного выше — рекурсивного алгоритма.
— Повторно встречающиеся — элементы не должны — вставляться. Элементы могут — быть вставлены только — при условии, что таблица полностью — не заполнена рюсейпге !СЕКТ(Х: гп 1ТЕМ; 1: !п 1ТЕМ ТУРЕ; К: Ра ощ ХЕХТ-ЕЬЕМЕХТ) !з Ьея!и !Р К = ппй гйеп К:= пезч 1ТЕМ 1ХРО(Х, 1, ппй, ппй); — динамический объект явно — инициируется во время создания е!з!1 Х < К.1Р гйеп 1ХБЕКТ(Х, 1, К.ЬЕРТ) е1ае 1ХБЕКТ(Х, 1, К.К1ОНТ); епг! !1; епа 1ХЯЕКТ; Ьей!и 1ХБЕКТ (Х, 1, КООТ); ХОМ ЕЬЕМЕХТБ:= ХОМ ЕЬЕМЕХТЯ + 1; епг! А1И); (пас!!оп 1Х ТАВЬЕ(Х: !и 1ТЕМ) ге!игл ВООЬЕАХ !з К: ХЕХТ ЕЬЕМЕХТ:= КООТ; — временная переменная, используемая — для обхода дерева !11 ггаквгы Ьея)п згЬ1!е Кl= ппй !оор И Х = К.1О 1Ьеп гегнгп ТК)ЛЕ; е1зИ Х < КЛР гйеп К:= КЛ.ЕРТ, е!зе К:= К.К1ОНТ; епй И; епй 1оор; ге!пгп БАЕВЕ; епп' 1Х ТАВ1.Е; 1ппсг)оп ОЕТ(Х: !п !ТЕМ) гегпгп 1ТЕМ ТУРЕ В К: ХЕХТ Е1.ЕМЕХТ:= КООТ; — временная переменная, используемая — для обхода дерева Ьея)п зчЫ!е Кl= ппП 1еор И Х = К.Нэ гйеп гегпгп КТ; е!пИ Х < КЛР 1Ьеп К:= КЛ.ЕРТ,' е!зе К:= К.К1ОНТ, епй И; епп 1оор; епг! ОЕТ, 1ппсг!оп НЛЫ.
ге1пгп ВООЬЕАХ В Ьея!п гегпгп Х1)М ЕЬЕМЕХТЯ = Х; епй Р)ЛЫ.; ргосейпге СЬЕАК В Ьея)п КООТ:= пп!1; Х)ЛМ Е1.ЕМЕХТБ: = 0; епй С1.ЕАК; епй БУМВОЬ ТАВЕЕ МАХАОЕК; Число элементов, которое можно вставить в таблицу символов, было ограничено числом 200 при реализации упорядоченного бинарного дерева для соответствия спецификациям лаке'га таблицы символов. Необходимость в этом ограничении отпадает при реализации в виде бинарного дерева, потому что память под элементы отводится динамически, когда это необходимо.
Элементы можно вставлять в таблицу символов, пока имеется свободная память. Область памяти для бинарного дерева освобождается всякий раз, когда выполняется операция С1,ЕАК. Эта память будет доступна для повторного ис- »г Глава 3 пользования с помощью сборщика мусора, если реализация языка Ада предусматривает его. Если повторное использование памяти является существенным, а реализация не предусматривает сборщика мусора, то пользователь может использовать конкретизацию настраиваемой процедуры (Лх(СНЕСКЕ!) (эЕА1Л.ОСАТ1О!х(, предусмотренной в языке Ада" для явного освобождения неиспользуемой памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
