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

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

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

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

Ada

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

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

record

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

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

end record;

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

C

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

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

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

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

} node;

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

C++

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

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

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

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

}

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

C

while (current->data != key)

current = current->next;

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

while Current.Data /= Key loop

Ada

Current := Current.Next;

end loop;

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

Указатель null (пустой)

На рисунке 8.3 поле next последнего элемента списка не указывает ни на что. Обычно считается, что такой указатель имеет специальное значение — пус­тое, которое отличается от любого допустимого указателя. Пустое значение в Ada обозначается зарезервированным словом null. В предыдущем разделе, чтобы не пропустить конец списка, поиск фактически следовало бы запро­граммировать следующим образом:

Ada

while (Current /= null) and then (Current.Data /= Key) loop

Current := Current.Next;

end loop;

Обратите внимание, что укороченное вычисление (см. раздел 6.2) здесь существенно.

В языке С используется обычный целочисленный литерал «ноль» для обо­значения пустого указателя:

C

while ((current != 0) && (current->data != key))

current = current->next;

Нулевой литерал — это всего лишь синтаксическое соглашение; реальное зна­чение зависит от компьютера. При просмотре с помощью отладчика в пустом указателе все биты могут быть, а могут и не быть нулевыми. Для улучшения читаемости программы в библиотеке С определен символ NULL:

C

while ((current != NULL) && (current->data != key))

current = current->next;

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

Нужно быть очень осторожными, чтобы случайно не разыменовать пустой указатель, потому что значение null не указывает ни на что (или, вернее, ссы­лается на данные системы по нулевому адресу):

Ada

Current: Ptr := null;

Current := Current.Next;

В языке Ada эта ошибка будет причиной исключительной ситуации (см. гл. 11), но в С результат попытки разыменовывать null может привести к катастро­фе. Операционные системы, которые защищают программы друг от друга, смогут прервать «провинившуюся» программу; без такой защиты разыменова­ние могло бы вмешаться в другую программу или даже разрушить систему.

Указатели на подпрограммы

В языке С указатель может ссылаться на функцию. При программировании это чрезвычайно полезно в двух случаях:

• при передаче функции как параметра,

• при создании структуры данных, которая каждому ключу или индексу ставит в соответствие процедуру.

Например, один из параметров пакета численного интегрирования — это функция, которую нужно проинтегрировать. Это легко запрограммировать в С, создавая тип данных, который является указателем на функцию; функция получит параметр типа float и вернет значение типа float:

C

typedef float (*Func) (float);

Этот синтаксис довольно плох потому, что имя типа (в данном случае — Func) находится глубоко внутри объявления, и потому, что старшинство операций в С требует дополнительных круглых скобок.

Раз тип объявлен, он может использоваться как тип формального параметра:

C

float integrate(Func f, float upper, float lower)

{

float u = f (upper); float I = f(lower);

}

Обратите внимание, что раскрытие указателя делается автоматически, когда вы­зывается функция-параметр, иначе нам пришлось бы написать (*f )(upper). Те­перь, если определена функция с соответствующей сигнатурой, ее можно использовать как фактический параметр для подпрограммы интегрирова­ния:

C

float fun (float parm)

{

… /* Определение "fun" */

}

float x = integrate(fun, 1.0, 2.0); /* "fun" как фактический параметр */

Структуры данных с указателями на функции используются при создании интерпретаторов — программ, которые получают последовательность кодов и выполняют действия в соответствии с этими кодами. В то время как стати­ческий интерпретатор может быть реализован с помощью case-оператора и обычных вызовов процедур, в динамическом интерпретаторе соответствие между кодами и операциями будет устанавливаться только во время выполне­ния. Современные системы с окнами используют аналогичную методику про­граммирования: программист должен предоставить возможность обратного вызова (callback), т.е. процедуру, обеспечивающую выполнение соответствую­щего действия для каждого события. Это указатель на подпрограмму, которая будет выполнена, когда получен код, указывающий, что событие произошло:

typedef enum {Event1, ..., Event'10} Events;

C

typedef void (*Actions)(void);

/* Указатель на процедуру */

Actions action [10];

/* Массив указателей на процедуры */

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

void insta!l(Events e, Actions a)

C

{

action[e] = a;

}

Затем, когда событие происходит, его код может использоваться для индекса­ции и вызова соответствующей подпрограммы:

C

action [е] ();

Поскольку в Ada 83 нет указателей на подпрограммы, эту технологию нель­зя запрограммировать без использования нестандартных средств. Когда язык разрабатывался, указатели на подпрограммы были опущены, потому что предполагалось, что родовых (generics)* программных модулей (см. раз­дел 10.3) будет достаточно для создания математических библиотек, а мето­дика обратного вызова еще не была популярна. В Ada 95 этот недостаток устранен, и разрешены указатели на подпрограммы. Объявление математи­ческой библиотечной функции таково:

Ada

type Func is access function(X: Float) return Float;

-- Тип: указатель на функцию

function lntegrate(F: Func; Upper, Lower: Float);

-- Параметр является указателем на функцию

а обратный вызов объявляется следующим образом:

Ada

type Events is (Event'1,..., EventIO);

type Actions is access procedure;

-- Тип: указатель на процедуру

Action: array(Events) of Actions;

-- Массив указателей на процедуры

Указатели и массивы

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

int *ptr; /* Указатель на целое */

C

int а[100]; /* Массив целых чисел */

ptr = &а[0]; /* Явный адрес первого элемента

*/ ptr = а; /* Неявный тот же адрес */

два оператора присваивания эквивалентны, потому что имя массива рассмат­ривается всего лишь как указатель на первый элемент массива. Более того, ес­ли прибавление или вычитание единицы делается для указателя, результат бу­дет не числом, а результатом увеличения или уменьшения указателя на размер типа, на который ссылается указатель. Если для целого числа требуются четы­ре байта, а р содержит адрес 344, то р+1 равно не 345, а 348, т.е. адресу «следу­ющего» целого числа. Доступ к элементу массива осуществляется прибавле­нием индекса к указателю и разыменованием, следовательно, два следующих выражения эквивалентны:

C

*(ptr + i)

a[i]

Несмотря на эту эквивалентность, в языке С все же остается значительное

различие между массивом и указателем:

C

char s1[] = "Hello world";

char *s2 = "Hello world";

Здесь s1 — это место расположения последовательности из 12 байтов, содер­жащей строку, в то время как s2 — это переменная-указатель, содержащая адрес аналогичной последовательности байтов (см. рис. 8.4). Однако s1[i] —это то же самое, что и *(s2+i) для любого i из рассматриваемого диапазона, потому что массив при использовании автоматически преобразуется в ука­затель.

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