Кратко об указателях в Си: присваивание, разыменование и перемещение по массивам
Приветствую вас, дорогие читатели. В данной статье кратко описаны основные сведения об указателях в языке Си. Кроме основных операций с указателями (объявление, взятие адреса, разыменование) рассмотрены вопросы безопасности типов при работе с ними. К сожалению, в данной статье вы не найдёте информацию по операциям сравнений указателей. Однако, статья будет полезна новичкам, а также тем, кто работает с массивами. Все примеры в данной статье компилировались компилятором gcc (восьмой версии).
Введение
Указатель — переменная, которая хранит адрес сущностей (т.е. других переменных любого типа, будь то структура, или массив), и над которой возможно выполнять операцию разыменования (dereferencing). Адрес обычно выражен целым положительным числом. Диапазон адресов зависит от архитектуры компьютера. Указателю надо указать тип переменной, адрес которой он хранит, или же использовать ключевое слово void, для обозначения указателя, хранящего адрес чего-угодно (т.е. разрешён любой тип). Указатели объявляются как и обычные переменные, с той разницей, что имя типа переменной указателя имеет префикс, состоящий как минимум из одной звёздочки (*). Например:
int a = 12; /* usual variable */ int * ptr = &a; /* ptr-variable which contains address of variable a */ int **pptr = &ptr; /* ptr-variable which contains address of variable ptr */ int aval = **pptr; /* get value by adress which is contained in pptr. */ int aval2 = *ptr; /* get value of a by address (value of ptr) */Количество звёздочек лишь указывает на длину цепочек хранимых адресов. Поскольку указатель также является переменной и имеет адрес, то его адрес также можно хранить в другом указателе. В выше приведённом примере адрес переменной a сохраняется в переменной-указателе ptr. Адрес же самой переменной ptr сохраняется в другом указателе pptr. Чтобы получить адрес переменной, перед её именем надо поставить знак амперсанда (&). Наконец, чтобы выполнить обратную операцию, т.е. получить значение (содержимое) по адресу, хранимому в указателе, имя указателя предваряется звёздочкой, почти как при объявлении. Почти, потому что одной звёздочки достаточно чтобы «распаковать» указатель. Поскольку pptr указывает по адресу на значение, хранимое в ptr, то необходимо два раза применить операцию разыменования.
Указатели в предыдущем примере хранят адрес переменной определённого типа. В случае, когда применяются указатели типа void (любого типа), то прежде чем распаковать значение по адресу, необходимо выполнить приведение к типизированному указателю. Следующий пример является версией предыдущего, но с использованием указателя любого типа.
int b = 0xff; void *pb = &b; void **ppb = &pb; int bval1 = *((int *) pb); int bval2 = *((int *) *ppb);В данном примере адреса хранятся в указателе типа void. Перед получением значения по адресу, хранимым в pb, необходимо привести указатель pb к типу int*. Затем, воспользоваться стандартной операцией разыменования. Что касается указателя ppb, то он разыменовывается два раза. Первый раз до приведения к типу, для получения содержимого переменной pb, на которую он указывает. Второй раз — после приведения к типу int*.
Изменения значения переменной через указатель.
Так как указатель хранит адрес переменной, мы можем через адрес не только получить значение самой переменной, но также его изменить. Например:
char a = 'x'; char *pa = &a; /* save address of a into pa */ *pa = 'y'; /* change content of variable a */ printf("%c\n", a); /* prints: y */Как было сказано выше, указатели хранят адреса. Естественно, что адреса могут указывать не только на ячейки данных переменных в вашей программе, но и на другие вещи: адрес стека процедур, адрес начала сегмента кода, адрес какой-то процедуры ядра ОС, адрес в куче и т. д. Логично, что не все адреса можно использовать напрямую в программе, поскольку некоторые из них указывают на те участки памяти, которые нельзя изменять (доступ для чтения), или которые нельзя затирать. В случае, при обращении к участку, доступному только для чтения, при попытке изменить значение получим ошибку Segmentation Fault (SF).
Кроме того, в языке Си определён макрос с именем NULL, для обозначения указателя с нулевым адресом. Данный адрес обычно используется операционной системой для сигнала об ошибке при работе с памятью. При попытке что либо читать по этому адресу, программа может получить неопределённое поведение. Поэтому ни в коем случае не пытайтесь извлечь значение по пустому указателю.
И ещё, указатели могут указывать на один и тот же объект. Например:
int a = 123; int *p1 = &a; //Теперь p2 хранит тот же адрес, что и p1. int *p2 = &a; *p1 -= 3; // a = 123 - 3. printf("*p2 = %d\n", *p2); //Выведет 120Этот простой пример показывает, что через адреса можно менять содержимое простых переменных, а также остальных указателей, ссылающихся на тоже самое. Таким образом, указатель p2 как бы является псевдонимом (alias) для p1.
Передача параметров через указатели.
Параметры функций могут быть указателями. В случае вызова таких функций, они копируют значения аргументов в свои параметры как обычно. Единственное отличие здесь в том, что они копируют адреса, содержащиеся в указателях параметрах. И с помощью полученных адресов, можно изменять объекты, на которые указывают параметры. Ниже приведена стандартная процедура обмена значений между двумя целочисленными переменными.
int swap(int *a, int *b)
Здесь переменные а и b меняются своими значениями друг с другом (при условии, что параметры содержат не нулевой адрес). Отметим ещё раз, что мы можем изменить содержимое, указываемое по параметру-указателю методов. И, конечно, мы можем стереть данный адрес, присвоив параметру новое значение.
Проверка типов и массивы
Как было сказано, указатели хранят адреса переменных. Несмотря на указание типа для переменной указателя, это не мешает присвоить ему адрес переменной другого типа, если вы компилируете БЕЗ флагов. Например, следующий код не скомпилируется, если вы включили флаги -Werror -Wall .
#include #include int main(int argc, char **argv)
Конечно, компилятор gcc и без -Wall заметит недопустимую операцию в 7 строке кода. Флаг -Wall покажет все предупреждения компилятора. Главный флаг -Werror не позволит компилировать код, если есть предупреждения.
Что же касается массивов, то для массива не нужно предварять имя переменной амперсандом, поскольку компилятор автоматически при присваивании адреса массива присвоит адрес первого его элемента в указатель. Для многомерных массивов потребуются указатели на массивы, а не массивы указателей. Первые имеют форму объявления вида int (*arr)[] , а вторые вида int *arr[] . В квадратных скобках обязательно нужно указать размер массива. Для трёхмерных массивов потребуется уже две пары скобок, например int (*arr)[2][2] . Для четырёхмерных — три и так далее.
// В ПУСТОМ теле метода main. int A[2] = ; // A -> (int *) ptr to A[0] element, &A -> (int (*)[]) -> ptr to whole Array. int *ptr = A; printf("ptr -> A[1] = %d\n", *(ptr + 1)); // A[1] => 20. //Illegal usage of A. // int a_2 = ++A; //expected lvalue. //But with ptr you can do this. int b_2 = *++ptr; //Now ptr contains address of A[1]. (b_2 = A[1]); int (*ptr2)[2] = &A; //ptr to array, not to literal element. //*ptr2 => get array. //**ptr2 => get first element of array. //*ptr2 + 1 => get address of second element of array. printf("ptr2 -> A[1] = %d\n", *( *ptr2 + 1) ); int M[2][2] = < , >; // (*mp)[k] => (*mp)[k] => mp[0][k]. int (*mp)[2] = M; //again you must not add '&' to variable M. printf("M[0][0] = %d\n", **mp);//get array and extract it first element printf("M[1][0] = %d\n", **(mp + 1));//move to the address of second element printf("M[1][1] = %d\n", *( *(mp + 1) + 1));В выше приведённом коде даны примеры для работы с массивами (одномерными и двумерными). В квадратных скобках указывается размер последнего измерения. Важно помнить, что первое разыменование приводит вас ко всему массиву (т. е. к типу int * ). А второе разыменование распаковывает элемент данного массива. В случае одномерного массива, у нас всего одна ячейка, и указатель ссылается на неё. В случае двумерного массива, у нас две ячейки — массивы, а указатель ссылается на первую. Для перемещения на второй массив, достаточно прибавить единицу к адресу, хранимому в переменной mp, например, так mp + 1 . Чтобы получить первый элемент второго массива, надо два раза распаковать указатель с соответствующим адресом массива, т.е. **(mp + 1) .
Постоянные (const) и указатели.
Напомним, чтобы сделать переменную с постоянным, фиксированным значением, надо добавить ключевое слово const перед её именем (до имени типа или после). Например:
const int i1 = 10; int const i2 = 222; // Warning: variable e3 is unitialized. With -Werror it won't be compiled. // (Внимание: переменной e3 не присвоено значение. С флагом gcc -Werror // данный код не скомпилируется). // const int e3;Для объявления указателя на постоянное значение, ключевое слово const должно быть ПЕРЕД звёздочкой.
int A[2] = ; const int *a0 = A; printf("content of a0 = %d\n", *a0); //*a0 *= 10; //error: cannot change constant value. a0 = (A + 1); // A[1] printf("content of a0 = %d\n", *a0); //prints: A[1]В примере выше была создана переменная-указатель, ссылающееся на постоянное значение. Слово const перед звёздочкой указывает, что нельзя менять содержимое напрямую (путём разыменования, обращения к ячейке). Но сама переменная указатель постоянной не является. А значит, ей можно присвоить новый адрес. Например, адрес следующей ячейки в массиве.
Чтобы запретить менять адрес (значение переменной) указателя, надо добавить слово const ПОСЛЕ звёздочки. Кроме того, можно добавить ключевые слова const перед и после ‘*’ , чтобы сделать переменную фиксированной ещё сильнее, например так:
// Переменная с постоянным адресом и постоянным содержимым. const int *const ptr = A; // constant address with constant content // Переменная с постоянным адресом (содержимое можно менять) int *const ptr2 = A; // constant address only. // Переменная с постоянным содержимым, но с изменяемым адресом (значение справа) const int *ptr3 = A; // constant content only (can change address (rvalue))- Программирование
- Системное программирование
- C
Что обозначает запись int p1 x
Указатели поддерживают ряд операций: присваивание, получение адреса указателя, получение значения по указателю, некоторые арифметические операции и операции сравнения.
Присваивание адреса
Указателю можно присвоить адрес объекта того же типа, либо значение другого указателя. Для получения адреса объекта используется операция & :
int a ; int *pa ; // указатель pa хранит адрес переменной a
При этом указатель и переменная должны иметь один и тот же тип, в данном случае это тип int.
Разыменование указателя
Операция разыменования указателя представляет выражение в виде *имя_указателя . Эта операция позволяет получить объект по адресу, который хранится в указателе.
#include int main() < int a ; int *pa ; // хранит адрес переменной a std::cout #include int main() < int a ; int b ; int *pa ; // указатель на переменную a int *pb ; // указатель на переменную b std::cout pa: address=0x56347ffc5c value=10 pb: address=0x56347ffc58 value=2 pa: address=0x56347ffc58 value=2 b value=125
Нулевые указатели
Нулевой указатель (null pointer) - это указатель, который не указывает ни на какой объект. Если мы не хотим, чтобы указатель указывал на какой-то конкретный адрес, то можно присвоить ему условное нулевое значение. Для определения нулевого указателя можно инициализировать указатель нулем или константой nullptr :
int *p1; int *p2<>;
Ссылки на указатели
Так как ссылка не является объектом, то нельзя определить указатель на ссылку, однако можно определить ссылку на указатель. Через подобную ссылку можно изменять значение, на которое указывает указатель или изменять адрес самого указателя:
#include int main() < int a ; int b ; int *p<>; // указатель int *&pRef
; // ссылка на указатель pRef = &a; // через ссылку указателю p присваивается адрес переменной a std::cout &:
int a ; int *pa ; std::cout >, >=, , ,==, !=. Операции сравнения применяются только к указателям одного типа. Для сравнения используются номера адресов:
#include int main() < int a ; int b ; int *pa ; int *pb ; if(pa > pb) std::cout
Консольный вывод в моем случае:
pa (0xa9da5ffdac) is greater than pb (0xa9da5ffda8)
Приведение типов
Иногда требуется присвоить указателю одного типа значение указателя другого типа. В этом случае следует выполнить операцию приведения типов с помощью операции (тип_указателя *) :
#include int main() < char c ; char *pc ; // указатель на символ int *pd <(int *)pc>; // указатель на int void *pv ; // указатель на void std::cout std::cout
Переменные, адреса и указатели
Переменная — это область памяти, к которой мы обращаемся за находящимися там данными, используя идентификатор (в данном случае, имя переменной). При этом у этой помеченной именем области есть еще и адрес, выраженный числом и понятный компьютерной системе. Этот адрес можно получить и записать в особую переменную. Переменную, содержащую адрес области памяти, называют указателем.
Когда мы меняем значение обычной переменной, то, можно сказать, просто удаляем из конкретной области памяти данные и записываем туда новые. Когда мы меняем значение переменной-указателя, то начинаем работать с совершенно иным участком памяти, т.к. меняем содержащийся в ней адрес.
Тема указателей тесно связана с темой динамических типов данных. Когда программа компилируется, то под объявленные переменные так или иначе (в зависимости от того, где они были объявлены) выделяются участки памяти. Потом размер этих участков не меняется, может меняться только их содержимое (значения или данные). Однако именно с помощью указателей можно захватывать и освобождать новые участки памяти уже в процессе выполнения программы. Динамические типы данных будут рассмотрены позже.
Прежде чем перейти к рассмотрению объявления и определения переменных-указателей, посмотрим, что из себя представляет адрес любой переменной и как его получить.
int i = 0; printf ("i=%d, &i=%p \n", i, &i);
В результате выполнения данного программного кода на экране появляется примерно следующее (шестнадцатеричное число у вас будет другим):
i=0, &i=0x7fffa40c5fac
Знак амперсанда (&) перед переменной позволяет получить ее адрес в памяти. Для вывода адреса переменной на экран используется специальный формат %p . Адреса обычных переменных (не указателей) в процессе выполнения программы никогда не меняются. В этом можно убедиться:
int a = 6; float b = 10.11; char c = 'k'; printf("%5d - %p\n", a, &a); printf("%5.2f - %p\n", b, &b); printf("%5c - %p\n", c, &c); a = 2; b = 50.99; c = 'z'; printf("%5d - %p\n", a, &a); printf("%5.2f - %p\n", b, &b); printf("%5c - %p\n", c, &c);
6 - 0x7fff653532e0 10.11 - 0x7fff653532e4 k - 0x7fff653532df 2 - 0x7fff653532e0 50.99 - 0x7fff653532e4 z - 0x7fff653532df
Как мы видим, несмотря на то, что значения переменных поменялись, ячейки памяти остались прежними.
Зная адрес, можно получить значение, которое находится по этому адресу, поставив знак * перед адресом:
int a = 8; printf("%d \n", *&a);
На экране будет выведено число 8.
Однако запись типа &a не всегда возможна или удобна. Поэтому существует специальный тип данных — указатели, которым и присваивается адрес на область памяти.
Указатели в языке C, как и другие переменные, являются типизированными, т.е. при объявлении указателя надо указывать его тип. Как мы узнаем позже, с указателями можно выполнять некоторые арифметические операции, и именно точное определение их типа позволяет протекать им корректно. Чтобы объявить указатель, надо перед его именем поставить знак *. Например:
int *pi; float *pf;
Обратите внимание на то, что в данном случае * говорит о том, что объявляется переменная-указатель. Когда * используется перед указателем не при его объявлении, а в выражениях, то обозначает совсем иное — "получить значение (данные) по адресу, который присвоен указателю". Посмотрите на код ниже:
int x = 1, y, z = 3; int *p, *q; p = &x; printf("%d\n", *p); // 1 y = *p; printf("%d\n", y); // 1 *p = 0; printf("%d %d\n", x, y); // 0 1 q = &z; printf("%d\n", *q); // 3 p = q; *p = 4; printf("%d\n", z); // 4 printf("%p %p\n", p, q); // p == q
С помощью комментариев указаны текущие значения ячеек памяти. Подробно опишем, что происходит:
- Выделяется память под пять переменных: три типа int и два указателя на int . В ячейки x и z записываются числа 1 и 3 соответственно.
- Указателю p присваивается адрес ячейки x. Извлекая оттуда значение ( *p ), получаем 1.
- В область памяти, которая названа именем у, помещают значение равное содержимому ячейки, на которую ссылается указатель p. В результате имеем две области памяти (x и y), в которые записаны единицы.
- В качестве значения по адресу p записываем 0. Поскольку p указывает на x, то значение xменяется. Переменная p не указывает на y, поэтому там остается прежнее значение.
- Указателю q присваивается адрес переменной z. Извлекая оттуда значение ( *q ), получаем 3.
- Переменной p присваивается значение, хранимое в q. Это значит, что p начинает ссылаться на тот же участок памяти, что и q. Поскольку q ссылается на z, то и p начинает ссылаться туда же.
- В качестве значения по адресу p записываем 4. Т.к. p является указателем на z, следовательно, меняется значение z.
- Проверяем, p и q являются указателями на одну и туже ячейку памяти.
Под сам указатель (там, где хранится адрес) также должна быть выделена память. Объем этой памяти можно узнать с помощью функции sizeof() :
int *pi; float *pf; printf("%lu\n", sizeof(pi)); printf("%lu\n", sizeof(pf));
Под указатели всех типов выделяется одинаковый объем памяти, т.к. размер адреса не зависит от типа, а зависит от вычислительной системы. В таком случае, зачем при объявлении указателя следует указывать тип данных, на который он может ссылаться? Дело в том, что по типу данных определяется, сколько ячеек памяти занимает значение, на которое ссылается указатель, и через сколько ячеек начнется следующее значение.
Если указатель объявлен, но не определен, то он ссылается на произвольный участок памяти с неизвестно каким значением:
int *pa, *pb; float *pc; printf(" %p %p %p\n", pa, pc, pb); // может возникнуть ошибка printf(" %d %f\n", *pa, *pc);
Результат (в Ubuntu):
0x400410 0x7fff5b729580 (nil) -1991643855 0.000000
Использование неопределенных указателей в программе при вычислениях чревато возникновением серьезных ошибок. Чтобы избежать этого, указателю можно присвоить значение, говорящее, что указатель никуда не ссылается (NULL). Использовать такой указатель в выражениях не получится, пока ему не будет присвоено конкретное значение:
int a = 5; float c = 6.98; int *pa; float *pc; pa = NULL; pc = NULL; printf(" %15p %15p\n", pa, pc); // Error // printf(" %15d %15f\n", *pa, *pc); pa = &a; pc = &c; printf(" %15p %15p\n", pa, pc); printf(" %15d %15f\n", *pa, *pc);
Результат (в Ubuntu):
(nil) (nil) 0x7ffd8e77e550 0x7ffd8e77e554 5 6.980000
В данном случае, если попытаться извлечь значение из памяти с помощью указателя, который никуда не ссылается, то возникает "ошибка сегментирования".
На этом уроке вы должны понять, что такое адрес переменной и как его получить ( &var ), что такое переменная-указатель ( type *p_var; p_var = &var ) и как получить значение, хранимое в памяти, зная адрес ячейки ( *p_var ). Однако у вас может остаться неприятный осадок из-за непонимания, зачем все это надо? Это нормально. Понимание практической значимости указателей придет позже по мере знакомства с новым материалом.
Практически проверьте результат работы всех примеров данного урока, придумайте свои примеры работы с указателями.
Курс с решением части задач:
pdf-версия
Глава 6. Структуры
Структура — это одна или несколько переменных (возможно, различных типов), которые для удобства работы с ними сгруппированы под одним именем. (В некоторых языках, в частности в Паскале, структуры называются записями.) Структуры помогают в организации сложных данных (особенно в больших программах), поскольку позволяют группу связанных между собой переменных трактовать не как множество отдельных элементов, а как единое целое.
Распространенный пример структуры — строка платежной ведомости. Она содержит такие сведения о служащем, как его полное имя, адрес, номер карточки социального страхования, зарплата и т.д. Некоторые из этих характеристик сами могут быть структурами: например, полное имя состоит из нескольких компонент (фамилии, имени и отчества); аналогично адрес, и даже зарплата. Другой пример (более типичный для Си) — из области графики: точка есть пара координат, прямоугольник есть пара точек и т.д.
Главные изменения, внесенные стандартом ANSI в отношении структур, — это введение для них операции присваивания. Структуры могут копироваться, над ними могут выполняться операции присваивания, их можно передавать функциям в качестве аргументов, а функции могут возвращать их в качестве результатов. В большинстве компиляторов уже давно реализованы эти возможности, но теперь они точно оговорены стандартом. Для автоматических структур и массивов теперь также допускается инициализация.
6.1. Основные сведения о структурах
Сконструируем несколько графических структур. В качестве основного объекта выступает точка с координатами x и y , и пусть они имеют тип int .
Указанные две компоненты можно поместить в структуру, описанную, например, следующим образом:
struct point < int x; int y; >;
Описание структуры начинается с ключевого слова struct и содержит список деклараций, заключенный в фигурные скобки. За словом struct может следовать имя, называемое тегом (от английского слова tag — ярлык, этикетка. — Примеч. пер.) структуры ( point в нашем случае). Тег дает название структуре данного вида и далее может служить кратким обозначением той части декларации, которая заключена в фигурные скобки.
Перечисленные в структуре переменные называются членами. Имена членов и тегов без каких-либо коллизий могут совпадать с именами обычных переменных (т.е. не членов), так как они всегда различимы по контексту. Более того, одни и те же имена членов могут встречаться в разных структурах, хотя, если следовать хорошему стилю программирования, лучше одинаковые имена давать только близким по смыслу объектам.
Декларация структуры — это тип. За правой фигурной скобкой, закрывающей список членов, могут следовать переменные точно так же, как они могут быть указаны после названия любого базового типа. Таким образом, запись
struct < . >x, y, z;
с точки зрения синтаксиса аналогична записи
int x, y, z;
в том смысле, что каждая декларирует x , y и z как переменные указанного типа. Обе записи приведут к тому, что где-то будет выделена память соответствующего размера.
Декларация структуры, не содержащей списка переменных, не резервирует памяти: она просто описывает шаблон, или образец структуры. Однако если структура имеет тег, то этим тегом далее можно пользоваться при определении структурных объектов. Например, с помощью заданной выше декларации структуры point строка
struct point pt;
определяет структурную переменную pt типа struct point . Структурную переменную при ее определении можно инициализировать, формируя список инициализаторов ее членов в виде константных выражений:
struct point maxpt = < 320, 200 >;
Инициализировать автоматические структуры можно также присваиванием или обращением к функции, возвращающей результат в виде структуры соответствующего типа.
Доступ к отдельному члену структуры осуществляется посредством конструкции вида:
имя_структуры . член
Оператор доступа к члену структуры « . » соединяет имя структуры и имя члена. Чтобы напечатать, например, координаты точки pt , годится следующее обращение к printf :
printf("%d, %d", pt.x, pt.y); Другой пример: чтобы вычислить расстояние от начала координат (0, 0) до pt , можно написать
double dist, sqrt(double); dist = sqrt((double) pt.x * pt.x + (double) pt.y * pt.y);
Структуры могут быть вложены друг в друга. Одно из возможных представлений прямоугольника — это пара точек на углах одной из его диагоналей:
struct rect < struct point pt1; struct point pt2; >;
Структура rect содержит две структуры point . Если мы декларируем screen как
struct rect screen;
screen.pt1.x
ссылается на координату x точки pt1 из screen .
6.2. Структуры и функции
Чтобы лучше познакомиться со структурами, напишем несколько функций, манипулирующих точками и прямоугольниками. Возникает вопрос: а как передавать функциям названные объекты? Существует по крайней мере три подхода: передавать компоненты по отдельности, передавать всю структуру целиком и передавать указатель на структуру. Каждый подход имеет свои плюсы и минусы.
Первая функция, makepoint , получает два целых значения и возвращает структуру point .
/* makepoint: формирует точку по компонентам x и y */ struct point makepoint(int x, int y)
Заметим: никакой путаницы из-за того, что имя аргумента совпадает с именем члена структуры не возникает; более того, одно и то же имя подчеркивает родство обозначаемых им объектов.
Теперь с помощью makepoint можно выполнять динамическую инициализацию любой структуры или формировать структурные аргументы для той или иной функции:
struct rect screen; struct point middle; struct point makepoint(int, int); screen.pt1 = makepoint(0, 0); screen.pt2 = makepoint(XMAX, YMAX); middle = makepoint((screen.pt1.x + screen.pt2.x)/2, (screen.pt1.y + screen.pt2.y)/2);
Нам может понадобиться ряд функций, реализующих различные операции над точками. В качестве примера рассмотрим следующую функцию:
/* addpoint: сложение двух точек */ struct point addpoint(struct point p1, struct point p2)
Здесь оба аргумента и возвращаемое значение — структуры. Мы увеличиваем компоненты прямо в p1 и не используем для этого временной переменной, чтобы подчеркнуть, что структурные параметры передаются по значению так же, как и любые другие.
В качестве другого примера приведем функцию ptinrect , которая проверяет: находится ли точка внутри прямоугольника, относительно которого мы принимаем соглашение, что в него входят его левая и нижняя стороны, но не входят верхняя и правая.
/* ptinrect: возвращает 1, если p в r, и 0 в прот. случае */ int ptinrect(struct point p, struct rect r) < return p.x >= r.pt1.x && p.x < r.pt2.x && p.y >= r.pt1.y && p.y
Здесь предполагается, что прямоугольник представлен в стандартном виде, т.е. координаты точки pt1 меньше соответствующих координат точки pt2 . Следующая функция гарантирует получение прямоугольника в каноническом виде.
#define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) >(b) ? (a) : (b)) /* canonrect: канонизация координат прямоугольника */ struct rect canonrect ( struct rect r)
Если функции передается большая структура, то, чем копировать ее целиком, эффективнее передать указатель на нее. Указатели на структуры ничем не отличаются от указателей на обычные переменные. Декларация
struct point *pp;
сообщает, что pp есть указатель на структуру типа struct point . Если pp ссылается на структуру point , то *pp есть сама структура, а (*pp).x и (*pp).y — ее члены. Используя указатель pp , мы могли бы написать
struct point origin, *pp; pp = &origin; printf("origin: (%d,%d)\n", (*pp).x, (*pp).y); Скобки в (*pp).x необходимы, поскольку приоритет оператора выше, чем приоритет * . Выражение *pp.x будет проинтерпретировано как *(pp.x) , что неверно, поскольку pp.x не является указателем.
Указатели на структуры используются весьма часто, поэтому для доступа к ее членам была придумана еще одна, более короткая форма записи. Если p — указатель на структуру, то
p->член_структуры
есть ее отдельный член. (Оператор -> состоит из знака - , за которым сразу следует знак > .) Поэтому printf можно переписать в виде
printf("origin: (%d,%d)\n", pp->x, pp->y); Оба оператора и -> выполняются слева направо. Таким образом, при наличии декларации
struct rect r, *rp = r;
следующие четыре выражения будут эквивалентны:
r.pt1.x rp->pt1.x (r.pt1).x (rp->pt1).x
Операторы доступа к членам структуры . и -> вместе с операторами вызова функции () и индексации массива [] занимают самое высокое положение в иерархии приоритетов и выполняются раньше любых других операторов. Например, если задана декларация
struct < int len; char *str; >*p;
++p->len
увеличит на 1 значение члена структуры len , а не указатель p , поскольку в этом выражении как бы неявно присутствуют скобки: ++(p->len) . Чтобы изменить порядок выполнения операций, нужны явные скобки. Так, в (++p)->len , прежде чем взять значение len , программа продвинет указатель p . В (p++)->len указатель p увеличится после того, как будет взято значение len (в последнем случае скобки не обязательны).
По тем же правилам *p->str обозначает содержимое объекта, на который ссылается str ; *p->str++ продвинет указатель str после получения значения объекта, на который он указывал (как и в выражении вида *s++ ); ( *p->str)++ увеличит значение объекта, на который ссылается str ; *p++->str продвинет p после того, как будет получено то, на что указывает str .
6.3. Массивы структур
Рассмотрим программу, определяющую число вхождений каждого ключевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива стрингов и счетчики ключевых слов в виде массива целых. Один из возможных вариантов — это иметь два параллельных массива:
char *keyword[NKEYS]; int keycount[NKEYS];
Однако именно тот факт, что они параллельны, подсказывает нам другую организацию хранения — через массив структур. Каждое ключевое слово можно описать парой характеристик
char *word; int count;
Такие пары составляют массив. Декларация
struct key < char *word; int count; >keytab[NKEYS];
описывает структуру типа key и определяет массив keytab , каждый элемент которого есть структура этого типа и которому где-то будет выделена память. Это же можно записать и по-другому:
struct key < char *word; int count; >; struct key keytab[NKEYS];
Так как keytab содержит постоянный набор имен, его легче всего сделать внешним массивом и инициализировать один раз в момент определения. Инициализация структур аналогична ранее демонстрировавшимся инициализациям — за определением следует список инициализаторов, заключенный в фигурные скобки:
struct key < char *word; int count; >keytab[] = < "auto", 0, "break", 0, /* . */ "while", 0 >;
Инициализаторы задаются парами, чтобы соответствовать конфигурации структуры. Строго говоря, пару инициализаторов для каждой отдельной структуры следовало бы заключить в фигурные скобки, как, например, в
Однако, когда инициализаторы — простые константы или цепочки литер, и все они имеются в наличии, во внутренних скобках нет необходимости. Число элементов массива keytab будет вычислено по количеству инициализаторов, поскольку они представлены полностью, а внутри квадратных скобок [] ничего не задано.
Программа подсчета ключевых слов начинается с определения keytab . Программа main читает ввод, многократно обращаясь к функции getword и получая на каждом ее вызове очередное слово. Каждое слово ищется в keytab . Для этого используется функция бинарного поиска, которую мы написали в гл. 3. Список ключевых слов должен быть упорядочен в алфавитном порядке.
#include #include #include #define MAXWORD 100 int getword(char *, int); int binsearch(char *, struct key *, int); /* подсчет ключевых слов Си */ main() < int n; char word[MAXWORD]; while (getword(word, MAXWORD) != EOF) if (isalpha(word[0])) if ((n = binsearch(word, keytab, NKEYS)) >= 0) keytab[n].count++; for (n = 0; n < NKEYS; n++) if (keytab[n].count >0) printf("%d %s\n", keytab[n].count, keytab[n].word); return 0; > /* binsearch: найти слово в tab[0]. tab[n-1] */ int binsearch(char *word, struct key tab[], int n) < int cond; int low, high, mid; low = 0; high = n - 1; while (low 0) low = mid + 1; else return mid; > return -1; > Чуть позже мы рассмотрим функцию getword , а сейчас нам достаточно знать, что при каждом ее вызове получается очередное слово, которое запоминается в массиве, заданном первым аргументом.
NKEYS — количество ключевых слов в keytab . Хотя мы могли бы подсчитать число таких слов вручную, гораздо легче и безопасней сделать это с помощью машины, особенно если список ключевых слов может быть изменен. Одно из возможных решений — поместить в конец списка инициализаторов пустой указатель ( NULL ) и затем перебирать в цикле элементы keytab , пока не встретится концевой элемент.
Но возможно и более простое решение. Поскольку размер массива полностью определен во время компиляции и равен произведению количества элементов массива на размер его отдельного элемента, число элементов массива можно вычислить по формуле
размер keytab / размер struct key
В Си имеется унарный оператор sizeof , который работает во время компиляции. Его можно применять для вычисления размера любого объекта. Выражения
sizeof объект sizeof (имя типа)
выдают целые значения, равные размеру указанного объекта или типа в байтах. (Строго говоря. sizeof выдает беззнаковое целое, тип которого size_t определен в головном файле .) Что касается объекта, то это может быть переменная, массив или структура. В качестве имени типа может выступать имя базового типа ( int , double . ) или имя производного типа, например, структуры или указателя.
В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размер одного элемента. Указанное вычисление используется в инструкции #define для установки значения NKEYS :
#define NKEYS (sizeof keytab / sizeof(struct key))
Этот же результат можно получить другим способом — поделить размер массива на размер какого-то его конкретного элемента:
#define NKEYS (sizeof keytab / sizeof keytab[0])
Преимущество такого рода записей в том, что их не надо корректировать при изменении типа.
Поскольку препроцессор не обращает внимания на имена типов, оператор sizeof нельзя применять в #if . Но в #define выражение препроцессором не вычисляется, так что предложенная нами запись допустима.
Теперь поговорим о функции getword . Мы написали getword в несколько более общем виде, чем требуется для нашей программы, но она от этого не стала заметно сложнее. Функция getword берет из входного потока следующее «слово». Под словом понимается цепочка букв-цифр, начинающаяся с буквы, или отдельная непробельная литера. По концу файла функция выдает EOF , в остальных случаях ее значением является код первой литеры слова или код отдельной литеры, если она не буква.
/* getword: принимает следующее слово или литеру из ввода */ int getword(char *word, int lim) < int c, getch(void); void ungetch(int); char *w = word; while (isspace(c = getch())) ; if (c != EOF) *w++ = c; if (!isalpha(c)) < *w = '\0'; return c; >for ( ; --lim > 0; w++) if (!isalnum(*w = getch())) < ungetch(*w); break; >*w = '\0'; return word[0]; >
Функция getword обращается к getch и ungetch , которые мы написали в гл. 4. При завершении набора букв-цифр оказывается, что getword взяла лишнюю литеру. Обращение к ungetch позволяет вернуть ее назад во входной поток. В getword используются также isspace — для пропуска пробельных литер, isalpha — для идентификации букв и isalnum — для распознавания букв-цифр. Все они описаны в стандартном головном файле .
Упражнение 6.1.
Наша версия getword не обрабатывает должным образом знак подчеркивания, стринговые константы, комментарии и управляющие строки препроцессора. Напишите более совершенный вариант программы.
6.4. Указатели на структуры
Для иллюстрации некоторых моментов, касающихся указателей на структуры и массивов структур, перепишем программу подсчета ключевых слов, пользуясь для получения элементов массива вместо индексов указателями.
Внешняя декларация массива keytab остается без изменения, а main и binsearch нужно модифицировать.
#include #include #include #define MAXWORD 100 int getword(char *, int); struct key *binsearch(char *, struct key *, int); /* подсчет ключевых слов Си; версия с указателями */ main() < char word[MAXWORD]; struct key *p; while (getword(word, MAXWORD) != EOF) if (isalpha(word[0])) if ((p = binsearch(word, keytab, NKEYS)) != NULL) p->count++; for (p = keytab; p < keytab + NKEYS; p++) if (p->count > 0) printf("%4d %s\n", p->count, p->word); return 0; > /* binsearch: найти слово в tab[0]. tab[n-1] */ struct key *binsearch(char *word, struct key *tab, int n) < int cond; struct key *low = &tab[0]; struct key *high = &tab[n]; struct key *mid; while (low < high) < mid = low + (high-low) / 2; if ((cond = strcmp(word, mid->word)) < 0) high = mid; else if (cond >0) low = mid + 1; else return mid; > return NULL; > Некоторые детали этой программы требуют пояснений. Первое, описание функции binsearch должно отражать тот факт, что она возвращает указатель на struct key , а не целое; соответствующие изменения коснулись как прототипа функции, так и ее заголовка. Если binsearch находит слово, то она выдает указатель на него, в противном случае она возвращает NULL . Второе, к элементам keytab доступ осуществляется в нашей программе через указатели. Это потребовало значительных изменений в binsearch . Инициализаторами для low и high теперь служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы
mid = (low+high) / 2 /* НЕВЕРНО */
не годится, поскольку указатели нельзя складывать. Однако к ним можно применить операцию вычитания, и так как high-low есть число элементов, присваивание
mid = low + (high-low) / 2
установит в mid указатель на элемент, лежащий посередине между low и high .
Самое важное при переходе на новый вариант программы — сделать так, чтобы не генерировались неправильные указатели и не было попыток обращений за пределы массива. Проблема в том, что и &tab[-1] , и &tab[n] находятся вне границ массива. Первый адрес определенно неверен, нельзя также осуществить доступ и по второму адресу. По правилам языка, однако, гарантируется, что адрес ячейки памяти, следующей сразу за концом массива (т.е. &tab[n] ), в арифметике с указателями воспринимается правильно.
В главной программе мы написали
for (p = keytab; p < keytab + NKEYS; p++)
Если p — указатель на структуру, то при выполнении операций с p учитывается размер структуры. Поэтому p++ увеличит p на такую величину, чтобы выйти на следующий структурный элемент массива, а проверка условия вовремя остановит цикл.
Не следует, однако, полагать, что размер структуры равен сумме размеров ее членов. Вследствие выравнивания объектов разной длины в структуре могут появляться безымянные «дыры». Так, например, если переменная типа char занимает один байт, а int — четыре байта, то для структуры
struct < char c; int i; >;
может потребоваться восемь байт, а не пять. Оператор sizeof возвращает правильное значение.
Наконец, несколько слов относительно формата программы. Если функция возвращает значение сложного типа, как, например, в нашем случае указатель на структуру:
struct key *binsearch(char *word, struct key *tab, int n)
То имя функции «высмотреть» оказывается совсем не просто. В таких случаях иногда пользуются записью вида:
struct key * binsearch(char *word, struct key *tab, int n)
Какой форме отдать предпочтение — дело вкуса. Выберите ту, которая больше всего вам нравится.
6.5. Структуры со ссылками на себя
Предположим, что мы хотим решить более общую задачу — написать программу, подсчитывающую частоту встречаемости для любых слов входного потока. Так как список слов заранее не известен, мы не можем предварительно упорядочить его и применить бинарный поиск. Было бы неразумно пользоваться и линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет — в этом случае программа работала бы слишком медленно. (Более точная оценка: время работы такой программы пропорционально квадрату количества слов.) Как можно организовать данные, чтобы эффективно справиться со списком произвольных слов?
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Делать это передвижкой слов в линейном массиве не следует, — хотя бы потому, что указанная процедура тоже слишком долгая. Вместо этого мы воспользуемся структурой данных, называемой бинарным деревом.
В дереве на каждое отдельное слово предусмотрен «узел», который содержит:
указатель на текст слова счетчик числа встречаемости указатель на левый сыновний узел указатель на правый сыновний узел
У каждого узла может быть один или два сына, или узел вообще может не иметь сыновей.
Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое — слова, которые больше него. Вот как выглядит дерево, построенное для фразы «now is the time for all good men to come to the aid of their party» («настало время всем добрым людям помочь своей партии»), по завершении процесса, в котором для каждого нового слова в него добавлялся новый узел:
Чтобы определить, помещено ли уже в дерево вновь поступившее слово, начинают с корня, сравнивая это слово со словом из корневого узла. Если они совпали, то ответ на вопрос — положительный. Если новое слово меньше слова из дерева, то поиск продолжается в левом поддереве, если больше, то — в правом. Если же в выбранном направлении поддерева не оказалось, то этого слова в дереве нет, а пустующая ссылка, говорящая об отсутствии поддерева, как раз то место, куда нужно «подвесить» узел с новым словом. Описанный процесс по сути рекурсивен, так как поиск в любом узле использует результат поиска в одном из своих сыновних узлов. В соответствии с этим для добавления узла и печати дерева здесь наиболее естественно применить рекурсивные функции.
Вернемся к описанию узла, которое удобно представить в виде структуры с четырьмя компонентами:
struct tnode < /* узел дерева */ char *word; /* указатель на текст */ int count; /* число вхождений */ struct tnode *left; /* левый сын */ struct tnode *right; /* правый сын */ >
Приведенное рекурсивное определение узла может показаться рискованным, но оно правильное. Структура не может включать саму себя, но ведь
struct tnode *left;
определяет left как указатель на tnode , а не сам tnode .
Иногда возникает потребность во взаимоссылающихся структурах: двух структурах, ссылающихся друг на друга. Прием, позволяющий справиться с этой задачей, демонстрирует следующий фрагмент:
struct t < . struct s *p; /* p указывает на s */ >; struct s < . struct t *q; /* q указывает на t */ >;
Вся программа удивительно мала — правда, она использует вспомогательные программы типа getword , уже написанные нами. Главная программа читает слова с помощью getword и вставляет их в дерево посредством addtree .
#include #include #include #define MAXWORD 100 struct tnode *addtree(struct tnode *, char *); void treeprint(struct tnode *); int getword(char *, int); /* подсчет частоты встречаемости слов */ main()
Функция addtree рекурсивна. Первое слово функция main помещает на верхний уровень дерева (корень дерева). Каждое вновь поступившее слово сравнивается со словом узла и «погружается» или в левое, или в правое поддерево с помощью рекурсивного обращения к addtree . Через некоторое время это слово обязательно либо совпадет с каким-нибудь из имеющихся в дереве слов (в этом случае к счетчику будет добавлена 1), либо программа встретит пустую ссылку, что послужит сигналом для заведения нового узла и добавления его к дереву. Создание нового узла сопровождается тем, что addtree возвращает на него указатель, который вставляется в узел родителя.
struct tnode *talloc(void); char *strdup(char *); /* addtree: добавляет узел со словом w в p или ниже него */ struct tnode *addtree(struct tnode *p, char *w) < int cond; if (p == NULL) < /* слово встречается впервые */ p = talloc(); /* создается новый узел */ p->word = strdup(w); p->count = 1; p->left = p->right = NULL; > else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* это слово уже встречалось */ else if (cond < 0) /* < корня левого поддерева */ p->left = addtree(p->left, w); else /* > корня правого поддерева */ p->right = addtree(p->right, w); return p; >
Память для нового узла запрашивается с помощью программы talloc , которая возвращает указатель на свободное пространство, достаточное для хранения одного узла дерева, а копирование нового слова в отдельное место памяти осуществляется с помощью strdup . (Мы рассмотрим эти программы чуть позже.) В тот (и только в тот) момент, когда к дереву подвешивается новый узел, происходит инициализация счетчика и заполнение пустыми ссылками указателей на сыновей. Мы опустили (что неразумно) контроль ошибок, который должен выполняться при получении значений от strdup и talloc .
Функция treeprint печатает дерево в лексикографическом порядке; для каждого узла она печатает его левое поддерево (все слова, которые меньше слова данного узла), затем само слово и, наконец, правое поддерево (слова, которые больше слова данного узла).
/* treeprint: упорядоченная печать дерева p */ void treeprint (struct tnode *p) < if (p != NULL) < treeprint(p->left); printf("%4d %s\n", p->count, p->word); treeprint(p-> ri ght); > > Если вы не уверены, что досконально разобрались в том, как работает рекурсия, «проиграйте» действия treeprint на дереве, приведенном выше.
Практическое замечание: если дерево «несбалансировано» (что бывает, когда слова поступают не в случайном порядке), то время работы программы может сильно возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на вычисления будут такими же, как при линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем.
Прежде чем окончательно оставить этот пример, стоит сделать краткое отступление от темы и поговорить о механизме запроса памяти. Очевидно, хотелось бы иметь всего лишь одну функцию, выделяющую память, даже если эта память предназначается для разного рода объектов. Но если одна и та же функция обеспечивает память, скажем, и для указателей на char , и для указателей на struct tnode , то возникают два вопроса. Первый, как справиться с требованием большинства машин, в которых объекты определенного типа должны быть выровнены (например, целые часто должны размещаться, начиная с четных адресов)? И второе, как описать функцию, которая вынуждена в качестве результата выдавать указатели разных типов?
Вообще говоря, требования, касающиеся выравнивания, можно легко выполнить за счет некоторой потери памяти. Однако для этого возвращаемый указатель должен быть таким, чтобы удовлетворялись любые ограничения, связанные с выравниванием. Функция alloc , описанная в гл. 5, не гарантирует нам любое конкретное выравнивание, поэтому мы будем пользоваться функцией malloc из стандартной библиотеки, которая это делает. В гл. 8 мы покажем один из способов ее реализации.
Вопрос об описании типа таких функций, как malloc , является камнем преткновения в любом языке с жесткой проверкой типов. В Си вопрос решается естественным образом: malloc объявляется как функция, которая возвращает указатель на void . Полученный указатель затем явно приводится к желаемому типу. Описания malloc и связанных с ней функций находятся в стандартном головном файле . Таким образом, функцию talloc можно записать следующим образом:
#include /* talloc: создает tnode */ struct tnode *talloc(void)
Функция strdup просто копирует стринг, указанный в аргументе, в место, полученное с помощью malloc :
/* дублирует s */ char *strdup(char *s) < char *p; p = (char *) malloc(strlen(s) + 1); /* +1 для '\0' */ if (p != NULL) strcpy(p, s); return p; >
Функция malloc возвращает NULL , если свободного пространства нет; strdup передает это значение, оставляя заботу о выходе из ошибочной ситуации той программе, которая к ней обратилась.
Память, полученную с помощью malloc , можно освободить для повторного использования, обратившись к функции free (см. гл. 7 и 8).
Упражнение 6.2.
Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 литер, но последующие в чем-то различаются. Не обрабатывайте внутренности стрингов и комментариев. Число 6 сделайте параметром, задаваемым в командной строке.
Упражнение 6.3.
Напишите программу печати таблицы «перекрестных ссылок», которая будет печатать все слова документа и указывать для каждого из них номера строк, где оно встретилось. Программа должна игнорировать «шумовые» слова типа «и», «или» и т.д.
Упражнение 6.4.
Напишите программу, которая печатает весь набор различных слов, образующих входной поток, в порядке возрастания частоты их встречаемости. Перед каждым словом должно быть указано число вхождений.
6.6. Просмотр таблиц
В этом разделе, чтобы проиллюстрировать новые аспекты применения структур, мы напишем ядро пакета программ, осуществляющих вставку элементов: в таблицы и их поиск внутри таблиц. Этот пакет — типичный набор программ, с помощью которых работают с таблицами имен в любом макропроцессоре или компиляторе. Рассмотрим, например, инструкцию #define . Когда встречается строка вида
#define IN 1
имя IN и замещающий его текст 1 должны запоминаться в таблице. Если затем это имя IN встретится в инструкции, например, в
state = IN;
оно должно быть заменено на 1.
Существуют две программы, манипулирующие с именами и замещающими их текстами. Это install(s, t) , которая записывает имя s и замещающий его текст t в таблицу, где s и t — стринги, и lookup(s) , осуществляющая поиск s в таблице и возвращающая указатель на место, где имя s было найдено, или NULL , если s в таблице не оказалось.
Алгоритм основан на «хэшировании» (функции расстановки): поступающее имя свертывается в неотрицательное число (хэш-код), которое затем используется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем на начало связанного ссылками списка блоков, описывающих имена с данным хэш-кодом. Если элемент массива содержит NULL , это значит, что среди имен не встретилось ни одного с соответствующим хэш-кодом.
Блок в списке — это структура, содержащая указатели на имя, на замещающий текст и на следующий блок в списке; значение NULL в указателе на следующий блок означает конец списка.
struct nlist < /* элемент таблицы */ struct nlist *next; /* ук-ль на следующий элемент */ char *name; /* определяемое имя */ char *defn; /* замещающий текст */ >;
А вот как записывается определение массива указателей:
#define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* таблица ук-лей */
Хэш-функция, используемая в lookup и install , суммирует коды литер имени, тем самым «замешивая» их, и в качестве результата выдает остаток от деления полученной суммы на размер массива указателей. Это не самый лучший способ получения хэш-кода, но достаточно лаконичный и эффективный.
/* hash: получает хэш-код по стрингу s */ unsigned hash(char *s)
Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным.
Хэширование порождает стартовый индекс для массива hashtab ; если соответствующий стринг в таблице есть, он может быть обнаружен только в списке блоков, на начало которого указывает элемент массива hashtab с этим индексом. Поиск осуществляется с помощью lookup . Если lookup находит элемент с заданным стрингом, то он возвращает указатель на него, если не находит, то возвращает NULL .
/* lookup: ищет s */ struct nlist *lookup(char *s) < struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* нашли */ return NULL; /* не нашли */ >
В for -цикле функции lookup для просмотра списка используется стандартная конструкция
for (ptr = head; ptr != NULL; ptr = ptr->next) .
Функция install обращается к lookup , чтобы определить, имеется ли в наличии вставляемый стринг. Если это так, то старое определение будет заменено новым. В противном случае будет образован новый элемент. Если запрос памяти для нового элемента не может быть удовлетворен, функция install выдает NULL .
struct nlist *lookup(char *); char *strdup(char *); /* install: заносит (name, defn) в таблицу */ struct nlist *install(char *name, char *defn) < struct nlist *np; unsigned hashval; if ((np = (lookup(name)) == NULL) < /* не найден */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; > else /* уже имеется */ free((void *) np->defn); /* освобождаем прежн. defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; >
Упражнение 6.5.
Напишите функцию undef , удаляющую имя и определение из таблицы, организация которой поддерживается функциями lookup и install .
Упражнение 6.6.
Реализуйте простую версию #define -процессора (без аргументов), которая использовала бы программы этого раздела и годилась бы для Си-программ. Вам могут помочь программы getch и ungetch .
6.7. Средство typedef
Язык Си предоставляет средство, называемое typedef , позволяющее давать новые имена типам данных. Например, декларация
typedef int Length;
делает имя Length синонимом int . С этого момента тип Length можно применять в декларациях, в операторе приведения и т.д. точно так же, как тип int :
Length len, maxlen; Length *lengths[];
typedef char *String;
делает String синонимом char * , т.е. указателем на char , и правомерным будет, например, следующее его использование:
String p, lineptr[MAXLINES], alloc(int); int strcmp(String, String); p = (String) malloc(100);
Заметим, что объявляемый в typedef тип стоит на месте имени переменной в обычной декларации, а не сразу за словом typedef . С точки зрения синтаксиса слово typedef занимает место, где обычно располагается спецификатор класса памяти — extern , static и т.д. Имена типов записаны с заглавных букв для того, чтобы они выделялись.
Для демонстрации более сложных примеров применения typedef воспользуемся этим средством при задании узлов деревьев, с которыми мы уже встречались в данной главе.
typedef struct tnode *Treeptr; typedef struct node < /* узел дерева: */ char *word; /* указатель на текст */ int count; /* число вхождений */ Treeptr left; /* левый сын */ Treeptr right; /* правый сын */ >Treenode;
В результате создаются два новых названия типов: Treenode (структура) и Treeptr (указатель на структуру). Теперь программу talloc можно записать в следующем виде:
Treeptr talloc(void)
Следует подчеркнуть, что декларация typedef не создает новый тип, она лишь сообщает новое имя уже существующего типа. Никакого нового смысла эти новые имена не несут, они декларируют переменные в точности с теми же свойствами, как если бы они были объявлены напрямую без переименования типа. Фактически typedef аналогичен #define с тем лишь отличием, что, будучи интерпретируемым компилятором, он может справиться с такой текстовой подстановкой, которая не может быть обработана препроцессором. Например,
typedef int (*PHI)(char *, char *);
определяет тип PHI как «указатель на функцию (двух аргументов типа char * ), возвращающую int », который, например, в программе сортировки, описанной в гл. 5, можно использовать в таком контексте:
PHI strcmp, numcmp;
Помимо просто эстетических соображений, для привлечения typedef существуют две важные причины. Первая — параметризация программы, связанная с проблемой переносимости. Если с помощью typedef объявить типы данных, которые, возможно, являются машинно-зависимыми, то при переносе программы на другую машину потребуется внести изменения только в определения typedef. Одна из распространенных ситуаций — использование typedef -имен для варьирования целыми величинами. Для каждой конкретной машины это предполагает соответствующие установки short , int или long , которые делаются аналогично установкам стандартных типов, например, size_t и ptrdiff_t .
Вторая причина, побуждающая к применению typedef , — желание сделать более ясным текст программы. Тип, названный Treeptr (от английских слов tree — дерево и pointer — указатель) более понятен, чем тот же тип, записанный как указатель на некоторую сложную структуру.
6.8. Объединения
Объединение — это переменная, которая может содержать (в разные моменты времени) объекты различных типов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор. Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения в программу машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале.
Примером использования объединений мог бы послужить сам компилятор, заведующий таблицей символов, если предположить, что константы могут иметь тип int , float или являться указателем на стринговый литерал и иметь тип char * . Значение каждой конкретной константы должно храниться в переменной соответствующего этой константе типа. Работать с таблицей символов всегда удобнее, если значения занимают одинаковую по объему память и запоминаются в одном и том же месте независимо от своего типа. Цель введения в программу объединения — иметь переменную, которая бы на законных основаниях хранила в себе значения нескольких типов. Синтаксис объединений аналогичен синтаксису структур. Приведем пример объединения.
union u_tag < int ival; float fval; char *sval; >u;
Переменная u будет достаточно большой, чтобы в ней поместилась любая переменная из указанных трех типов; точный ее размер зависит от реализации. Значение одного из этих трех типов может быть присвоено переменной u и далее использовано в выражениях, если это правомерно, т.е. если тип взятого ею значения совпадает с типом последнего присвоенного ей значения. Выполнение этого требования в каждый текущий момент — целиком на совести программиста. В случае «рассогласованности» типов результат зависит от реализации.
Синтаксис доступа к членам объединения следующий:
имя_объединения . член
указатель_на_объединение -> член
т.е. в точности такой, как в структурах. Если для хранения типа текущего значения u использовать, скажем, переменную utype , то можно написать такой фрагмент программы:
if (utype == INT) printf("%d\n", u.ival); else if (utype == FLOAT) printf("%f\n", u.fval); else if (utype == STRING) printf("%s\n", u.sval); else printf("неверный тип %d в utype\n", utype); Объединения могут входить в структуры и массивы, и наоборот. Запись доступа к члену объединения, находящегося в структур (как и структуры, находящейся в объединении), такая же, как и для вложенных структур. Например, в массиве структур
struct < char *name; int flags; int utype; union < int ival; float fval; char *sval; >u; > symtab[NSYM];
на ival ссылаются следующим образом:
symtab[i].u.ival
а к первой литере стринга sval можно обратиться любым из следующих двух способов:
*symtab[i].u.sval symtab[i].u.sval[0]
Фактически объединение — это структура, все члены которой имеют нулевое смещение относительно ее базового адреса, размера, который позволяет поместиться в ней самому большому ее члену, и выравнивание которой удовлетворяет всем типам объединения. Операции, применимые к структурам, годятся и для объединений, т.е. законны присваивание объединения и копирование его как единого целого, взятие адреса от объединения и доступ к отдельным его членам.
Инициализировать объединение можно только значением, имеющим тип его первого члена; таким образом, упомянутую выше переменную u можно инициализировать лишь значением типа int .
В гл. 8 (на примере программы, заведующей выделением памяти) мы покажем, как, применяя объединение, можно добиться, чтобы расположение переменной было выровнено по соответствующей границе в памяти.
6.9. Поля битов
При дефиците памяти может возникнуть необходимость запаковать несколько объектов в одно слово машины. Одна из обычных ситуаций, встречающаяся в задачах обработки таблиц символов для компиляторов, — это объединение групп однобитовых флажков. Форматы некоторых данных могут от нас вообще не зависеть и диктоваться, например, интерфейсами с аппаратурой внешних устройств; здесь также возникает потребность адресоваться — к частям слова.
Вообразим себе фрагмент компилятора, который заведует таблицей символов. Каждый идентификатор программы имеет некоторую связанную с ним информацию, которая сообщает, например, представляет ли он собой ключевое слово и к какому классу, если это переменная, она принадлежит: внешняя и/или статическая и т.д. Самый компактный способ кодирования такой информации — расположить однобитовые флажки в одном слове типа char или int .
Один из распространенных приемов работы с битами основан на определении набора «масок», соответствующих позициям этих битов, как, например, в
#define KEYWORD 01 /* ключевое слово */ #define EXTERNAL 02 /* внешний */ #define STATIC 04 /* статический */
enum < KEYWORD = 01, EXTERNAL = 02, STATIC = 04 >;
Числа должны быть степенями двойки. Тогда доступ к битам становится делом «побитовых операций», описанных в гл. 2 (сдвиг, маскирование, взятие дополнения).
Некоторые виды записи выражений встречаются довольно часто. Так,
flags |= EXTERNAL | STATIC;
устанавливает 1 в соответствующих битах переменной flags ,
flags &= ~(EXTERNAL | STATIC);
if ((flags & (EXTERNAL | STATIC)) == 0)
оценивает условие как истинное, если оба бита нулевые.
Хотя научиться писать такого рода выражения не составляет труда, вместо побитовых логических операций можно пользоваться предоставляемым Си другим способом прямого определения и доступа к полям внутри слова. Поле_битов (или для краткости просто поле) — это некоторое множество битов, лежащих рядом внутри одной, зависящей от реализации, единице памяти, которую мы будем называть «словом». Синтаксис определения полей и доступа к ним базируется на синтаксисе структур. Например, строки #define , фигурировавшие выше при задании таблицы символов, можно заменить на определение трех полей:
struct < unsigned int is_keyword : 1; unsigned int is_extern : 1; unsigned int is_static : 1; >flags;
Эта запись определяет переменную flags , которая содержит три однобитовых поля. Число, следующее за двоеточием, задает ширину поля. Поля декларированы как unsigned int , чтобы они воспринимались как беззнаковые величины.
На отдельные поля ссылаются так же, как и на члены обычных структур: flags.is_keyword , flags.is_extern , и т.д. Поля «ведут себя» как малые целые и могут участвовать в арифметических выражениях точно так же, как и другие целые. Таким образом, предыдущие примеры можно написать более естественным образом:
flags.is_extern = flags.is_static = 1;
устанавливает 1 в соответствующие биты;
flags.is_extern = flags.is_static = 0;
if (flags.is_extern == 0 && flags.is_static == 0)
Почти все технические детали, касающиеся полей, в частности, может ли поле перейти границу слова, зависят от реализации. Поля могут не иметь имени; с помощью безымянного поля (задаваемого только двоеточием и шириной) организуется пропуск нужного количества разрядов. Особая ширина, равная нулю, используется, когда требуется выйти на границу следующего слова.
На одних машинах поля размещаются слева направо, на других — справа налево. Это значит, что при всей полезности работы с ними, если формат данных, с которыми мы имеем дело, дан нам свыше, то необходимо самым тщательным образом исследовать порядок расположения полей; программы, зависящие от такого рода вещей, не переносимы. Поля можно определять только с типом int , а для того, чтобы обеспечить переносимость, явно указывая signed или unsigned . Они не могут быть массивами и не имеют адресов, и, следовательно, оператор & к ним не применим.