Исходный текст разбивается на лексемы (идентификаторы, конс-
танты, знаки операций). Лексемы заносятся в таблицы, а в тексте
лексема заменяется ссылкой на элемент таблицы, таким образом
текст программы заменяется на последовательность лексем. Для
того, чтобы один и тот же идентификатор заменялся ссылкой на
один и тот же элемент таблицы, необходлимо для каждого анализи-
руемого идентификатора просматривать все встретившиеся ранее.
Для ускорения этого поиска применяются: упорядочение элементов
таблицы (сортировка) для дальнейшего бинарного поиска, хеш-ад-
ресация и некоторые другие способы.Для хранения последователь-
ности лексем используют массивы и списки.
Следующим этапом после замены текста программы на цепочку
лексем является синтаксический анализ, при котором широко ис-
пользуются стеки, таблицы и строки.
В операционных системах распространены такие сложные струк-
туры данных, как очереди. Операционная система вынуждена под-
держивать несколько очередей: очередь процессов готовых к вы-
полнению, очередь на свопинг на диск и очереди к устройствам
(например к принтеру).
Сложные структуры данных используются также в системах уп-
равления базами данных (СУБД). СУБД могут накапливать информа-
цию о большом числе объектов, описание которых содержат разные
сведения.
Свойства объектов могут выступать в роли ключей (например
фамилия служащего) и тогда по этим свойствам объекты могут быть
отсортированы, что значительно убыстряет поиск.
Для описания объектов обычно используют записи, которые в
свою очередь могут содержать ссылку на список из записей.
Наконец,еще одной областью применения являются задачи с ис-
пользованием разреженных матриц (с относительно небольшим чис-
лом ненулевых элементов).Иногда при нехватке оперативной памяти
бывает выгодно хранить только ненулевые элементы, применяя раз-
личные методы упаковки (в три массива, в один массив, с помощью
связного списка и т.д.).
Язык Pascal предоставляет весьма гибкие возможности в отно-
шении используемых структур данных. Удачный выбор структуры
данных влияет на простоту алгоритма, и следовательно уменьшает
трудоемкость разработки и повышает надежность.
2.10 С П И С О К И С П О Л Ь З О В А Н Н Ы Х
И С Т О Ч Н И К О В
1. В.М.Брябрин. Программное обеспечение персональных
ЭВМ, М., "Наука", 1990.
2. Н.Вирт. Програмирование на языке Модула-2,
М., "Мир", 1987.
3. К.Кристиан. Введение в операционную систему UNIX,
М., "Финансы и статистика", 1985.
4. М.И.Беляков, Ю.И.Рабовер, А.Л.Фридман.
Мобильная операционная система,М.,"Радио и связь",
1991.
5. Ф.Л.Бауэр, Г.Гооз, Информатика, т.2, М., "Мир",
1990.
6. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова,
Введение в язык паскаль,М., "Наука",1988.
7. И.З.Луговая, Л.Н.Чернышов, С.М.Юдин,
Динамические структуры данных языка паскаль, М.,
издательство МАИ, 1988.
8. Л.Н.Чернышов, С.М.Юдин, Инструментальная система
ИНФОРТ и работа с динамическими структурами данных,
М., издательство МАИ, 1984.
9. Лекции, семинары, консультации по АЯП.