Структура — это одна или несколько переменных (возможно, различных типов), которые для удобства работы с ними сгруппированы под одним именем. (В некоторых языках, в частности в Паскале, структуры называются записями.) Структуры помогают в организации сложных данных (особенно в больших программах), поскольку позволяют группу связанных между собой переменных трактовать не как множество отдельных элементов, а как единое целое.
Распространенный пример структуры — строка платежной ведомости. Она содержит такие сведения о служащем, как его полное имя, адрес, номер карточки социального страхования, зарплата и т.д. Некоторые из этих характеристик сами могут быть структурами: например, полное имя состоит из нескольких компонент (фамилии, имени и отчества); аналогично адрес, и даже зарплата. Другой пример (более типичный для Си) — из области графики: точка есть пара координат, прямоугольник есть пара точек и т.д.
Главные изменения, внесенные стандартом ANSI в отношении структур, — это введение для них операции присваивания. Структуры могут копироваться, над ними могут выполняться операции присваивания, их можно передавать функциям в качестве аргументов, а функции могут возвращать их в качестве результатов. В большинстве компиляторов уже давно реализованы эти возможности, но теперь они точно оговорены стандартом. Для автоматических структур и массивов теперь также допускается инициализация.
Сконструируем несколько графических структур. В качестве основного объекта
выступает точка с координатами 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.
Единственно возможные операции над структурами — это их копирование,
присваивание, взятие адреса с помощью & и осуществление доступа к ее членам.
Передача структур функциям в качестве аргументов и возврат их от функций в
виде результата также относятся к операциям копирования и присваивания.
Структуры нельзя сравнивать. Инициализировать структуру можно списком
константных значений ее членов; автоматическую структуру можно
инициализировать также присваиванием.
Чтобы лучше познакомиться со структурами, напишем несколько функций, манипулирующих точками и прямоугольниками. Возникает вопрос: а как передавать функциям названные объекты? Существует по крайней мере три подхода: передавать компоненты по отдельности, передавать всю структуру целиком и передавать указатель на структуру. Каждый подход имеет свои плюсы и минусы.
Первая функция, makepoint, получает два целых значения и возвращает структуру
point.
/* makepoint: формирует точку по компонентам x и y */
struct point makepoint(int x, int y)
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
Заметим: никакой путаницы из-за того, что имя аргумента совпадает с именем члена структуры не возникает; более того, одно и то же имя подчеркивает родство обозначаемых им объектов.
Теперь с помощью 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.x += p2.x;
p1.y += p2.y;
return p1;
}
Здесь оба аргумента и возвращаемое значение — структуры. Мы увеличиваем
компоненты прямо в 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 < r.pt2.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 rect temp;
temp.pt1.x = min(r.pt1.x, r.pt2.x);
temp.pt1.y = min(r.pt1.y, r.pt2.y);
temp.pt2.x = max(r.pt1.x, r.pt2.x);
temp.pt2.y = max(r.pt1.y, r.pt2.y);
return temp;
}
Если функции передается большая структура, то, чем копировать ее целиком, эффективнее передать указатель на нее. Указатели на структуры ничем не отличаются от указателей на обычные переменные. Декларация
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.
Рассмотрим программу, определяющую число вхождений каждого ключевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива стрингов и счетчики ключевых слов в виде массива целых. Один из возможных вариантов — это иметь два параллельных массива:
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
};
Инициализаторы задаются парами, чтобы соответствовать конфигурации структуры. Строго говоря, пару инициализаторов для каждой отдельной структуры следовало бы заключить в фигурные скобки, как, например, в
{ "auto", 0 },
{ "break", 0 },
...
Однако, когда инициализаторы — простые константы или цепочки литер, и все они
имеются в наличии, во внутренних скобках нет необходимости. Число элементов
массива keytab будет вычислено по количеству инициализаторов, поскольку они
представлены полностью, а внутри квадратных скобок [] ничего не задано.
Программа подсчета ключевых слов начинается с определения keytab. Программа
main читает ввод, многократно обращаясь к функции getword и получая на каждом
ее вызове очередное слово. Каждое слово ищется в keytab. Для этого
используется функция бинарного поиска, которую мы написали в гл. 3. Список
ключевых слов должен быть упорядочен в алфавитном порядке.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#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 <= high) {
mid = (low + high) / 2;
if ((cond = strcmp(word, tab[mid].word)) < 0)
high = mid - 1;
else if (cond > 0)
low = mid + 1;
else
return mid;
}
return -1;
}
Чуть позже мы рассмотрим функцию getword, а сейчас нам достаточно знать, что
при каждом ее вызове получается очередное слово, которое запоминается в
массиве, заданном первым аргументом.
NKEYS — количество ключевых слов в keytab. Хотя мы могли бы подсчитать число
таких слов вручную, гораздо легче и безопасней сделать это с помощью машины,
особенно если список ключевых слов может быть изменен. Одно из возможных
решений — поместить в конец списка инициализаторов пустой указатель (NULL) и
затем перебирать в цикле элементы keytab, пока не встретится концевой
элемент.
Но возможно и более простое решение. Поскольку размер массива полностью определен во время компиляции и равен произведению количества элементов массива на размер его отдельного элемента, число элементов массива можно вычислить по формуле
размер keytab / размер struct key
В Си имеется унарный оператор sizeof, который работает во время компиляции.
Его можно применять для вычисления размера любого объекта. Выражения
sizeof объект sizeof (имя типа)
выдают целые значения, равные размеру указанного объекта или типа в байтах.
(Строго говоря. sizeof выдает беззнаковое целое, тип которого size_t
определен в головном файле <stddef.h>.) Что касается объекта, то это может
быть переменная, массив или структура. В качестве имени типа может выступать
имя базового типа (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 — для распознавания букв-цифр. Все они описаны в
стандартном головном файле <ctype.h>.
Наша версия getword не обрабатывает должным образом знак
подчеркивания, стринговые константы, комментарии и управляющие строки
препроцессора. Напишите более совершенный вариант программы.
Для иллюстрации некоторых моментов, касающихся указателей на структуры и массивов структур, перепишем программу подсчета ключевых слов, пользуясь для получения элементов массива вместо индексов указателями.
Внешняя декларация массива keytab остается без изменения, а main и binsearch
нужно модифицировать.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#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)
Какой форме отдать предпочтение — дело вкуса. Выберите ту, которая больше всего вам нравится.
Предположим, что мы хотим решить более общую задачу — написать программу, подсчитывающую частоту встречаемости для любых слов входного потока. Так как список слов заранее не известен, мы не можем предварительно упорядочить его и применить бинарный поиск. Было бы неразумно пользоваться и линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет — в этом случае программа работала бы слишком медленно. (Более точная оценка: время работы такой программы пропорционально квадрату количества слов.) Как можно организовать данные, чтобы эффективно справиться со списком произвольных слов?
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Делать это передвижкой слов в линейном массиве не следует, — хотя бы потому, что указанная процедура тоже слишком долгая. Вместо этого мы воспользуемся структурой данных, называемой бинарным деревом.
В дереве на каждое отдельное слово предусмотрен «узел», который содержит:
указатель на текст слова счетчик числа встречаемости указатель на левый сыновний узел указатель на правый сыновний узел
У каждого узла может быть один или два сына, или узел вообще может не иметь сыновей.
Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое — слова, которые больше него. Вот как выглядит дерево, построенное для фразы «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 <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
/* подсчет частоты встречаемости слов */
main()
{
struct tnode *root;
char word[MAXWORD];
root = NULL;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
treeprint (root);
return 0;
}
Функция 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 и связанных с ней функций находятся в стандартном
головном файле <stdlib.h>. Таким образом, функцию talloc можно записать
следующим образом:
#include <stdlib.h>
/* talloc: создает tnode */
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
Функция 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 литер, но последующие в чем-то различаются. Не обрабатывайте внутренности стрингов и комментариев. Число 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)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным.
Хэширование порождает стартовый индекс для массива 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;
}
Напишите функцию undef, удаляющую имя и определение из
таблицы, организация которой поддерживается функциями lookup и install.
Реализуйте простую версию #define-процессора (без
аргументов), которая использовала бы программы этого раздела и годилась бы
для Си-программ. Вам могут помочь программы getch и ungetch.
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)
{
return (Treeptr) malloc(sizeof(Treenode));
}
Следует подчеркнуть, что декларация 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 — указатель) более понятен, чем тот же тип, записанный как
указатель на некоторую сложную структуру.
Объединение — это переменная, которая может содержать (в разные моменты времени) объекты различных типов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор. Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения в программу машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале.
Примером использования объединений мог бы послужить сам компилятор,
заведующий таблицей символов, если предположить, что константы могут иметь
тип 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 (на примере программы, заведующей выделением памяти) мы покажем, как, применяя объединение, можно добиться, чтобы расположение переменной было выровнено по соответствующей границе в памяти.
При дефиците памяти может возникнуть необходимость запаковать несколько объектов в одно слово машины. Одна из обычных ситуаций, встречающаяся в задачах обработки таблиц символов для компиляторов, — это объединение групп однобитовых флажков. Форматы некоторых данных могут от нас вообще не зависеть и диктоваться, например, интерфейсами с аппаратурой внешних устройств; здесь также возникает потребность адресоваться — к частям слова.
Вообразим себе фрагмент компилятора, который заведует таблицей символов.
Каждый идентификатор программы имеет некоторую связанную с ним информацию,
которая сообщает, например, представляет ли он собой ключевое слово и к
какому классу, если это переменная, она принадлежит: внешняя и/или
статическая и т.д. Самый компактный способ кодирования такой информации —
расположить однобитовые флажки в одном слове типа 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. Они не
могут быть массивами и не имеют адресов, и, следовательно, оператор & к ним
не применим.