М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 25

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

Поскольку в С нет контроля соответствия типов, указателю может быть при­своено произвольное выражение. Нет никакой гарантии, что указуемый объ­ект имеет ожидаемый тип; фактически значение указателя могло бы даже не быть адресом в отведенной программе области памяти. В лучшем случае это приведет к аварийному сбою программы из-за неправильной адресации, и вы получите соответствующее сообщение от операционной системы. В худшем случае это может привести к разрушению данных операционной системы. Ошибки в указателях очень трудно выявлять при отладке, потому что сложно разобраться в абсолютных адресах, которые показывает отладчик. Решение состоит в более строгом контроле соответствия типов для указателей, как это делается в Ada и C++.

Синтаксис

Синтаксические конструкции, связанные с указателями, иногда могут вводить в заблуждение, поэтому очень важно хорошо их понимать. Раскрытие указателей, индексация массивов и выбор полей записей — это средства до­ступа к данным внутри структур данных. В языке Pascal синтаксис самый яс­ный: каждая из этих трех операций обозначается отдельным символом, кото­рый пишется после переменной. В следующем примере Ptr объявлен как ука­затель на массив записей с целочисленным полем:

type Rec_Type =

record

Field: Integer;

end;

type Array_Type = array[1 ..100] of Rec_Type;

type Ptr_Type = Array_Type;

Ptr: Ptr_Type;

Ptr (*Указатель на массив записей с целочисленным полем *)

Ptrt (*Массив записей с целочисленным полем *)

Ptrt [78] (*3апись с целочисленным полем *)

Ptrt [78].Field ("Целочисленное поле *)

В языке С символ раскрытия ссылки (*) является префиксным оператором, поэтому приведенный пример записывался бы так:

typedef struct {

int field;

} Rec_Type;

typedef Rec_Type Array_Type[ 100];

Array_Type *ptr;

ptr /* Указатель на массив записей с целочисленным полем */

*ptr /* Массив записей с целочисленным полем */

(*ptr)[78] /* Запись с целочисленным полем */

(*ptr)[78].field /* Целочисленное поле */

Здесь необходимы круглые скобки, потому что индексация массива имеет бо­лее высокий приоритет, чем раскрытие указателя. В сложной структуре дан­ных это может внести путаницу при расшифровке декомпозиции, которая ис­пользует разыменование как префикс, а индексацию и выбор поля как пост­фикс. К счастью, наиболее часто используемая последовательность операций, в которой за разыменованием следует выбор поля, имеет специальный, про­стой синтаксис. Если ptr указывает на запись, то ptr->field — это краткая за­пись для (*ptr).field.

Синтаксис Ada основан на предположении, что за разыменованием почти всегда следует выбор поля, поэтому отдельная запись для разыменования не нужна. Вы не можете сказать, является R.Field просто выбором поля обычной записи с именем R, или R — это указатель на запись, который раскрывается перед выбором. Хотя такой подход и может привести к путанице, но он имеет то преимущество, что в структурах данных мы можем перейти от использования самих записей к использованию указателей на них без других изменений программы. В тех случаях, когда необходимо только разыменова­ние, используется довольно неуклюжий синтаксис, как показывает вышеупо­мянутый пример на языке Ada:

type Rec_Type is

record

Field: Integer;

end record;

type Array_Type is array( 1 .. 100) of Rec_Type;

type Ptr_Type is access Array_Type;

Ptr: Ptr_Type;

Ptr -- Указатель на массив записей с целочисленным полем

Ptr.all -- Массив записей с целочисленным полем

Ptr.all[78] -- Запись с целочисленным полем

Ptr.all[78].Field --Целочисленное поле

Обратите внимание, что в Ada для обозначения указателей используется клю­чевое слово access, а не символ. Ключевое слово all используется в тех немно­гих случаях, когда требуется разыменование без выбора.

Реализация

Для косвенного обращения к данным через указатели требуется дополнитель­ная команда в машинном коде. Давайте сравним прямой оператор присваива­ния с косвенным присваиванием, например:

int i,j;

int*p = &i;

int *q = &j;

i=j; /* Прямое присваивание */

*p = *q; /* Косвенное присваивание */

Машинные команды для прямого присваивания:

load R1J

store R1,i

в то время как команды для косвенного присваивания:

load R1,&q Адрес (указуемого объекта)

load R2,(R1) Загрузить указуемый объект

load R3,&p Адрес (указуемого объекта)

store R2,(R3) Сохранить в указуемом объекте

При косвенности неизбежны некоторые издержки, но обычно не серьезные, поскольку при неоднократном обращении к указуемому объекту оптимизатор может гарантировать, что указатель будет загружен только один раз. В опера­торе

p->right = p->left;

раз уж адрес р загружен в регистр, все последующие обращения могут вос­пользоваться этим регистром:

load R1 ,&p Адрес указуемого объекта

load R2,left(R1) Смещение от начала записи

store R2,right(R1) Смещение от начала записи

Потенциальным источником неэффективности при косвенном доступе к данным через указатели является размер самих указателей. В начале 1970-х го­дов, когда разрабатывались языки С и Pascal, компьютеры обычно имели только 16 Кбайт или 32 Кбайт оперативной памяти, и для адреса было доста­точно 16 разрядов. Теперь, когда персональные компьютеры и рабочие стан­ции имеют много мегабайтов памяти, указатели должны храниться в 32 раз­рядах. Кроме того, из-за механизмов управления памятью, основанных на кэше и страничной организации, произвольный доступ к данным через указате­ли может обойтись намного дороже, чем доступ к массивам, которые распола­гаются в непрерывной последовательности ячеек. Отсюда следует, что опти­мизация структуры данных для повышения эффективности сильно зависит от системы, и ее никогда не следует делать до измерения времени выполнения с помощью профилировщика.

Типизированные указатели в Ada предоставляют одну возможность для оптимизации. Для набора указуемых объектов, связанных с конкретным типом доступа, т. е. для так называемой коллекции (collection), можно задать размер:

type Node_Ptr is access Node;

for Node_Ptr'Storage_Size use 40_000;

Поскольку объем памяти, запрошенный для Node, меньше 64 Кбайт, указате­ли относительно начала блока могут храниться в 16 разрядах, при этом эконо­мятся и место в структурах данных, и время центрального процессора для за­грузки и сохранения указателей.

Указатели и алиасы в Ада 95

Указатель в языке С может использоваться для задания алиаса (альтерна­тивного имени) обычной переменной:

inti;

int *ptr = &i;

Алиасы бывают полезны; например, они могут использоваться для создания связанных структур во время компиляции. Так как в Ада 83 структуры, осно­ванные на указателях, могут быть созданы только при выполнении, это может привести к ненужным издержкам и по времени, и по памяти.

В Ada 95 добавлены специальные средства создания алиасов, названные типами обобщенного доступа (general access types), но на них наложены ограни­чения для предотвращения создания повисших ссылок (см. раздел 8.3). Пре­дусмотрен и специальный синтаксис как для объявления указателя, так и для

переменной с алиасом:

type Ptr is access all Integer; -- Ptr может указывать на алиас

I: aliased Integer; -- I может иметь алиас

P: Ptr := I'Access; -- Создать алиас

Первая строка объявляет тип, который может указывать на целочисленную переменную с алиасом, вторая строка объявляет такую переменную, и третьястрока объявляет указатель и инициализирует его адресом переменной. Такие типы обобщенного доступа и переменные с алиасом могут быть компонента­ми массивов и записей, что позволяет построить связанные структуры, не об­ращаясь к администратору памяти во время выполнения.

* Привязка к памяти

В языке С привязка к памяти тривиальна, потому что указателю может быть присвоен произвольный адрес:

int * const reg = Ox4fOO; /* Адрес (в шестнадцатеричной системе) */

*reg = Ox1f1f; /* Присваивание по абсолютному адресу */

Благодаря использованию указателя-константы мы уверены, что адрес в reg не будет случайно изменен.

В Ada используется понятие спецификации представления для явного ус­тановления соответствия между обычной переменной и абсолютным адресом:

Reg: Integer;

for Reg use at 16#4fOO#; -- Адрес (в шестнадцатеричной системе)

Reg := 16#1 f1 f#; -- Присваивание по абсолютному адресу

Преимущество метода языка Ada состоит в том, что не используются явные указатели.

8.2. Структуры данных

Указатели нужны для реализации динамических структур данных, таких как списки и деревья. Кроме элементов данных узел в структуре содержит один или несколько указателей со ссылками на другие узлы (см. рис. 8.3).

Попытка определить узел неизбежно ведет к рекурсии в определении типа, а именно: запись типа node (узел) должна содержать указатель на свойсобственный тип node. Для решения этой проблемы в языках допускается задавать частичное объявление записи, в котором указывается имя ее типа. Объявление сопровождается объявлением указателя, ссылающегося на это имя, а далее следует полное объявление записи, в котором уже можно ссы­латься на тип указателя. В языке Ada эти три объявления выглядят так:

type Node; -- Незавершенное объявление типа

type Ptr is access Node; -- Объявление типа указателя

type Node is -- Полное объявление

record

Data: Integer; -- Данные в узле

Next: Ptr; -- Указатель на следующий узел

end record;

Язык С требует использования тега структуры и альтернативного синтаксиса для объявления записи:

typedef struct node *Ptr; /* Указатель на структуру с тегом */

typedef struct node { /* Объявление структуры узла*/

int data; /* Данные в узле */

Ptr next; /* Указатель на следующий узел */

} node;

В C++ нет необходимости использовать typedef, поскольку struct определяет как тег структуры, так и имя типа:

typedef struct node *Ptr; /* Указатель на структуру с тегом */

struct node { /* Объявление структуры узла */

int data; /* Данные в узле */

Ptr next; /* Указатель на следующий узел */

}

Алгоритмы для прохождения (traverse) структур данных используют перемен­ные-указатели. Следующий оператор в С — это поиск узла, поле данных кото­рого содержит key:

while (current->data != key)

current = current->next;

Аналогичный оператор в Ada (использующий неявное раскрытие ссылки) та­ков:

while Current.Data /= Key loop

Current := Current.Next;

end loop;

Структуры данных характеризуются числом указателей, хранящихся в каждом узле, тем, куда они указывают, и алгоритмами, используемыми для прохож­дения структур и их обработки. Все алгоритмы, излагаемые в учебных курсах по структурам данных, достаточно просто программируются на языках С или Ada с использованием записей и указателей.

Характеристики

Список файлов книги