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