Cтраница 4
Как отмечалось выше, в задачах рассматриваемого здесь типа таблица обычно постоянно хранится в памяти машины. Однако для того, чтобы составляемую нами программу можно было достаточно удобно выполнить на машине, а также ради тренировки в работе с динамическими структурами данных ( чему и посвящена настоящая глава) схему автобусных маршрутов и ее характеристики будем считать одним из элементов исходных данных, вводимых с перфокарт. [46]
В Модуле-2 указательные типы обычно используют для создания динамических структур данных. Предыдущая декларация УказСим соответствует тривиальной структуре данных: либо литера, на которую указывает УказСим, существует, либо нет. Динамические структуры данных обычно содержат записи. [47]
В этом разделе мы вводим тип указателя. Применяя динамические структуры данных, мы можем создавать данные, которые расширяются и сжимаются в соответствии с нашими потребностями в процессе выполнения программы. [48]
Несмотря на все описанные преимущества, имеется одно важное обстоятельство, которым мы пренебрегли при рассмотрении использования BST-деревьев, patricia - деревьев или TST-деревьев для типичных приложений индексирования текста: сам по себе текст фиксирован, поэтому нет необходимости поддерживать динамические операции insert, как мы привыкли это делать. То есть, как правило, индекс строится один раз, а затем без каких-либо изменений используется для выполнения огромного объема поисков. Следовательно, динамические структуры данных типа BST-деревьев, patricia - деревьев или TST-деревьев могут оказаться вообще не нужными. [49]
Статические типы данных недостаточно гибки, чтобы работать в ситуациях, в которых требования относительно количества и точного состава заданной переменной неизвестны до выполнения программы. Например, если мы разрабатываем файл служащих, содержащий по одной записи на каждого служащего, то сколько записей следует запланировать. Тип указателя и динамические структуры данных предоставляют один из способов решения подобных проблем. Во время выполнения программы размер и форма файла служащих может расширяться и сужаться по мере необходимости. [50]
Модула-2 позволяет только три действия над указателями: присваивание, сравнение на равенство и неравенство и раскрытие ссылки. Обратите внимание на то, что арифметические операции и сравнения общего вида над указателями недопустимы. Такие операции не требуются для работы с динамическими структурами данных. В языках, использующих указатели в более общих ситуациях, имеется и более широкий набор операций над ними. Спартанский набор операций с указателями в Модуле-2 отражает их ограниченное применение в программах на этом языке. [51]
В этой главе мы обсудим один из наиболее мощных элементов языка С - указатели. Овладение техникой работы с указателями - дело достаточно трудное. Указатели дают возможность программам генерировать вызов по ссылке, создавать и управлять динамическими структурами данных, которые могут увеличиваться и уменьшаться в размере, - это могут быть, например, связанные списки, очереди, стеки и деревья. Эта глава посвящена основам работы с указателями. В главе 10 будет рассказано о роли указателей в работе со структурами. В главе 12 будут представлены динамические методы управления памятью с примерами создания и использования динамических структур данных. [52]
Некоторые вопросы, связанные с этим языком, обсуждаются в других главах. Так, массивам посвящены разд. Некоторые средства Паскаля не затронуты вовсе, например множественный тип, обработка файлов, записи, указатели, динамические структуры данных, форматный ввод-вывод и вопросы зависимости языка от средств реализации. Средства реализации языка Паскаль для конкретной системы состоят из компилятора и программных модулей, используемых во время выполнения программы. [53]