Структура — это набор из одной или более переменных, возможно различных типов, сгруппированных под одним именем для удобства обработки. (В некоторых языках, самый известный из которых Паскаль, структуры называются «записями»).
Традиционным примером структуры является учетная карточка работающего: «служащий» описывается набором атрибутов таких, как фамилия, имя, отчество (ф.и.о.), адрес, код социального обеспечения, зарплата и т.д. Некоторые из этих атрибутов сами могут оказаться структурами: ф.и.о. Имеет несколько компонент, как и адрес, и даже зарплата.
Структуры оказываются полезными при организации сложных данных особенно в больших программах, поскольку во многих ситуациях они позволяют сгруппировать связанные данные таким образом, что с ними можно обращаться, как с одним целым, а не как с отдельными объектами. В этой главе мы постараемся продемонстрировать то, как используются структуры. Программы, которые мы для этого будем использовать, больше, чем многие другие в этой книге, но все же достаточно умеренных размеров.
Давайте снова обратимся к процедурам преобразования даты из главы 5. Дата состоит из нескольких частей таких, как день, месяц, и год, и, возможно, день года и имя месяца. Эти пять переменных можно объединить в одну структуру вида:
struct date {
int day;
int month;
int year;
int yearday;
char mon_name[4];
};
Описание структуры, состоящее из заключенного в фигурные скобки списка
описаний, начинается с ключевого слова struct. За словом struct может
следовать необязательное имя, называемое ярлыком структуры (здесь это date).
Такой ярлык именует структуры этого вида и может использоваться в дальнейшем
как сокращенная запись подробного описания.
Элементы или переменные, упомянутые в структуре, называются членами. Ярлыки и члены структур могут иметь такие же имена, что и обычные переменные (т.е. не являющиеся членами структур), поскольку их имена всегда можно различить по контексту. Конечно, обычно одинаковые имена присваивают только тесно связанным объектам.
Точно так же, как в случае любого другого базисного типа, за правой фигурной скобкой, закрывающей список членов, может следовать список переменных. Оператор
struct {...} x, y, z;
синтаксически аналогичен
int x, y, z;
в том смысле, что каждый из операторов описывает x, y и z в качестве
переменных соответствующих типов и приводит к выделению для них памяти.
Описание структуры, за которым не следует списка переменных, не приводит к
выделению какой-либо памяти; оно только определяет шаблон или форму
структуры. Однако, если такое описание снабжено ярлыком, то этот ярлык может
быть использован позднее при определении фактических экземпляров структур.
Например, если дано приведенное выше описание date, то
struct date d;
определяет переменную d в качестве структуры типа date. Внешнюю или
статическую структуру можно инициализировать, поместив вслед за ее
определением список инициализаторов для ее компонент:
struct date d = { 4, 7, 1776, 186, "Jul"};
Член определенной структуры может быть указан в выражении с помощью конструкции вида
<имя структуры>.<член>
Операция указания члена структуры «.» связывает имя структуры и имя члена. В
качестве примера определим leap (признак високосности года) на основе даты,
находящейся в структуре d,
leap = d.year % 4 == 0 && d.year % 100 != 0 || d.year % 400 == 0;
или проверим имя месяца
if(strcmp(d.mon_name, "aug") == 0) ...
Или преобразуем первый символ имени месяца так, чтобы оно начиналось со строчной буквы
d.mon_name[0] = lower(d.mon_name[0]);
Структуры могут быть вложенными; учетная карточка служащего может фактически выглядеть так:
struct person {
char name[namesize];
char address[adrsize];
long zipcode; /* почтовый индекс */
long ss_number; /* код соц. Обеспечения */
double salary; /* зарплата */
struct date birthdate; /* дата рождения */
struct date hiredate; /* дата поступления на работу */
};
Структура person содержит две структуры типа date. Если мы определим emp как
struct person emp;
то
emp.birthdate.month
будет ссылаться на месяц рождения. Операция указания члена структуры «.»
ассоциируется слева направо.
В языке C существует ряд ограничений на использование структур. Обязательные
правила заключаются в том, что единственные операции, которые вы можете
проводить со структурами, состоят в определении ее адреса с помощью операции
& и доступе к одному из ее членов. Это влечет за собой то, что структуры
нельзя присваивать или копировать как целое, и что они не могут быть переданы
функциям или возвращены ими. (В последующих версиях эти ограничения будут
сняты). На указатели структур эти ограничения однако не накладываются, так
что структуры и функции все же могут с удобством работать совместно. И
наконец, автоматические структуры, как и автоматические массивы, не могут
быть инициализированы; инициализация возможна только в случае внешних или
статических структур.
Давайте разберем некоторые из этих вопросов, переписав с этой целью функции
преобразования даты из предыдущей главы так, чтобы они использовали
структуры. Так как правила запрещают непосредственную передачу структуры
функции, то мы должны либо передавать отдельно компоненты, либо передать
указатель всей структуры. Первая возможность демонстрируется на примере
функции day_of_year, как мы ее написали в главе 5:
d.yearday = day_of_year(d.year, d.month, d.day);
другой способ состоит в передаче указателя. Если мы опишем hiredate как
struct date hiredate;
и перепишем day_of_year нужным образом, мы сможем тогда написать
hiredate yearday = day_of_year(&hiredate);
передавая указатель на hiredate функции day_of_year. Функция должна быть
модифицирована, потому что ее аргумент теперь является указателем, а не
списком переменных.
/* получить день года из месяца и дня */
day_of_year(pd)
struct date *pd;
{
int i, day, leap;
day = pd->day;
leap = pd->year % 4 == 0 && pd->year % 100 != 0 || pd->year % 400 == 0;
for(i = 1; i < pd->month; i++)
day += day_tab[leap][i];
return day;
}
Описание
struct date *pd;
говорит, что pd является указателем структуры типа date. Запись, показанная
на примере
pd->year
является новой. Если p — указатель на структуру, то
p-> <член структуры>
обращается к конкретному члену. (Операция -> — это знак минус, за которым
следует знак «>».)
Так как pd указывает на структуру, то к члену year можно обратиться и
следующим образом
(*pd).year
но указатели структур используются настолько часто, что запись -> оказывается
удобным сокращением. Круглые скобки в (*pd).year необходимы, потому что
операция указания члена структуры старше, чем *. Обе операции, -> и .,
ассоциируются слева направо, так что конструкции слева и справа эквивалентны
p->q->memb (p->q)->memb emp.birthdate.month (emp.birthdate).month
Для полноты ниже приводится другая функция, month_day, переписанная с
использованием структур.
/* получить месяц и день из дня года */
month_day(pd)
struct date *pd;
{
int i, leap;
leap = pd->year % 4 == 0 && pd->year % 100 != 0 || PD->YEAR % 400 == 0;
pd->day = pd->yearday;
for(i = 1; pd->day > day_tab[leap][i]; i++)
pd->day -= day_tab[leap][i];
pd->month = i;
}
Операции работы со структурами -> и . наряду со () для списка аргументов
и [] для индексов находятся на самом верху иерархии старшинства операций и,
следовательно, связываются очень крепко. Если, например, имеется описание
struct {
int x;
int *Y;
} *p;
то выражение
++p->x
увеличивает x, а не p, так как оно эквивалентно выражению ++(p->х). Для
изменения порядка выполнения операций можно использовать круглые скобки:
(++p)->x увеличивает p до доступа к x, а (p++)->x увеличивает p после.
(Круглые скобки в последнем случае необязательны. Почему?)
Совершенно аналогично *p->y извлекает то, на что указывает y; *p->y++
увеличивает y после обработки того, на что он указывает (точно так же, как и
*s++); (*p->y)++ увеличивает то, на что указывает y; *p++->y увеличивает p
после выборки того, на что указывает y.
Структуры особенно подходят для управления массивами связанных переменных.
Рассмотрим, например, программу подсчета числа вхождений каждого ключевого
слова языка C. Нам нужен массив символьных строк для хранения имен и массив
целых для подсчета. Одна из возможностей состоит в использовании двух
параллельных массивов keyword и keycount:
char *keyword [nkeys]; int keycount [nkeys];
Но сам факт, что массивы параллельны, указывает на возможность другой организации. Каждое ключевое слово здесь по существу является парой:
char *keyword; int keycount;
и, следовательно, имеется массив пар. Описание структуры
struct key {
char *keyword;
int keycount;
} keytab [nkeys];
определяет массив keytab структур такого типа и отводит для них память.
Каждый элемент массива является структурой. Это можно было бы записать и так:
struct key {
char *keyword;
int keycount;
};
struct key keytab [nkeys];
Так как структура keytab фактически содержит постоянный набор имен, то легче
всего инициализировать ее один раз и для всех членов при определении.
Инициализация структур вполне аналогична предыдущим инициализациям — за
определением следует заключенный в фигурные скобки список инициализаторов:
struct key {
char *keyword;
int keycount;
} keytab[] = {
"break", 0,
"case", 0,
"char", 0,
"continue", 0,
"default", 0,
/* ... */
"unsigned", 0,
"while", 0
};
Инициализаторы перечисляются парами соответственно членам структуры. Было бы более точно заключать в фигурные скобки инициализаторы для каждой «строки» или структуры следующим образом:
{ "break", 0 },
{ "case", 0 },
. . .
Но когда инициализаторы являются простыми переменными или символьными
строками и все они присутствуют, то во внутренних фигурных скобках нет
необходимости. Как обычно, компилятор сам вычислит число элементов массива
keytab, если инициализаторы присутствуют, а скобки [] оставлены пустыми.
Программа подсчета ключевых слов начинается с определения массива keytab.
Ведущая программа читает свой файл ввода, последовательно обращаясь к функции
getword, которая извлекает из ввода по одному слову за обращение. Каждое
слово ищется в массиве keytab с помощью варианта функции бинарного поиска,
написанной нами в главе 3. (Конечно, чтобы эта функция работала, список
ключевых слов должен быть расположен в порядке возрастания).
#define MAXWORD 20
/* подсчет ключевых слов языка C */
main()
{
int n, t;
char word[MAXWORD];
while((t = getword(word, MAXWORD)) != EOF)
if(t == LETTER)
if((n = binary(word, keytab, nkeys)) >= 0)
keytab[n].keycount++;
for(n = 0; n < nkeys; n++)
if(keytab[n].keycount > 0)
printf("%4d %s\n", keytab[n].keycount, keytab[n].keyword);
}
/* найти слово в tab[0]...tab[n-1] */
binary(word, tab, n)
char *word;
struct key tab[];
int n;
{
int low, high, mid, cond;
low = 0;
high = n - 1;
while(low <= high) {
mid = (low + high) / 2;
if((cond = strcmp(word, tab[mid].keyword)) < 0)
high = mid - 1;
else if(cond > 0)
low = mid + 1;
else
return mid;
}
return -1;
}
Мы вскоре приведем функцию getword; пока достаточно сказать, что она
возвращает LETTER каждый раз, как она находит слово, и копирует это слово в
свой первый аргумент.
Величина nkeys — это количество ключевых слов в массиве keytab. Хотя мы
можем сосчитать это число вручную, гораздо легче и надежнее поручить это
машине, особенно в том случае, если список ключевых слов подвержен
изменениям. Одной из возможностей было бы закончить список инициализаторов
указанием на нуль и затем пройти в цикле сквозь массив keytab, пока не
найдется конец.
Но, поскольку размер этого массива полностью определен к моменту компиляции, здесь имеется более простая возможность. Число элементов просто есть
size of keytab / size of struct key
дело в том, что в языке C предусмотрена унарная операция sizeof, выполняемая
во время компиляции, которая позволяет вычислить размер любого объекта.
Выражение
sizeof(object)
выдает целое, равное размеру указанного объекта. (Размер определяется в
неспецифицированных единицах, называемых «байтами», которые имеют тот же
размер, что и переменные типа char). Объект может быть фактической
переменной, массивом и структурой, или именем основного типа, как int или
double, или именем производного типа, как структура. В нашем случае число
ключевых слов равно размеру массива, деленному на размер одного элемента
массива. Это вычисление используется в утверждении #define для установления
значения nkeys:
#define nkeys (sizeof(keytab) / sizeof(struct key))
Теперь перейдем к функции getword. Мы фактически написали более общий вариант
функции getword, чем необходимо для этой программы, но он не на много более
сложен. Функция getword возвращает следующее «слово» из ввода, где словом
считается либо строка букв и цифр, начинающихся с буквы, либо отдельный
символ. Тип объекта возвращается в качестве значения функции; это — LETTER,
если найдено слово, EOF для конца файла и сам символ, если он не буквенный.
/* получить следующее слово из ввода */
getword(w, lim)
char *w;
int lim;
{
int c, t;
if(type(c = *w++ = getch()) != LETTER) {
*W = '\0';
return c;
}
while(--lim > 0) {
t = type(c = *w++ = getch());
if(t != LETTER && t != DIGIT) {
ungetch(c);
break;
}
}
*(w-1) - '\0';
return LETTER;
}
Функция getword использует функции getch и ungetch, которые мы написали в
главе 4: когда набор алфавитных символов прерывается, функция getword
получает один лишний символ. В результате вызова ungetch этот символ
помещается назад во ввод для следующего обращения.
Функция getword обращается к функции type для определения типа каждого
отдельного символа из файла ввода. Вот вариант, справедливый только для
алфавита ASCII.
/* возвращает тип ASCII символа */
type(c)
int c;
{
if(c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z')
return LETTER;
else if(c>= '0' && c<= '9')
return DIGIT;
else
return c;
}
Символические константы LETTER и DIGIT могут иметь любые значения, лишь бы
они не вступали в конфликт с символами, отличными от буквенно-цифровых, и с
EOF; очевидно возможен следующий выбор
#define LETTER 'A' #define DIGIT '0'
функция getword могла бы работать быстрее, если бы обращения к функции type
были заменены обращениями к соответствующему массиву type[]. В стандартной
библиотеке языка C предусмотрены макросы isalpha и isdigit, действующие
необходимым образом.
Сделайте такую модификацию функции getword и оцените, как изменится скорость
работы программы.
Напишите вариант функции type, не зависящий от конкретного набора символов.
Напишите вариант программы подсчета ключевых слов, который бы не учитывал появления этих слов в заключенных в кавычки строках.
Чтобы проиллюстрировать некоторые соображения, связанные с использованием указателей и массивов структур, давайте снова составим программу подсчета ключевых строк, используя на этот раз указатели, а не индексы массивов.
Внешнее описание массива keytab не нужно изменять, но функции main и binary
требуют модификации.
/* подсчет ключевых слов C; версия с указателями */
main()
{
int t;
char word[MAXWORD];
struct key *binary(), *p;
while((t = getword(word, MAXWORD;) !=EOF)
if(t == LETTER)
if((p = binary(word, keytab, nkeys)) != NULL)
p->keycount++;
for(p = keytab; p > keytab + nkeys; p++)
if(p->keycount > 0)
printf("%4d %s/n", p->keycount, p->keyword);
}
/* искать слово в tab[0]...tab[n-1] */
struct key *binary(word, tab, n)
char *word;
struct keytab[];
int n;
{
int cond;
struct key *low = &tab[0];
struct key *high = &tab[n-1];
struct key *mid;
while(low <= high) {
mid = low + (high - low) / 2;
if((cond = strcmp(word, mid->keyword)) < 0)
high = mid - 1;
else if(cond > 0)
low = mid + 1;
else
return mid;
}
return NULL;
}
Здесь имеется несколько моментов, которые стоит отметить. Во-первых, описание
функции binari должно указывать, что она возвращает указатель на структуру
типа key, а не на целое; это объявляется как в функции main, так и в binary.
Если функция binari находит слово, то она возвращает указатель на него; если
же нет, она возвращает NULL.
Во-вторых, все обращения к элементам массива keytab осуществляются через
указатели. Это влечет за собой одно существенное изменение в функции binary:
средний элемент больше нельзя вычислять просто по формуле
mid = (low + high) / 2
потому что сложение двух указателей не дает какого-нибудь полезного
результата (даже после деления на 2) и в действительности является
незаконным. Эту формулу надо заменить на
mid = low + (high-low) / 2
в результате которой mid становится указателем на элемент, расположенный
посередине между low и high.
Вам также следует разобраться в инициализации low и high. Указатель можно
инициализировать адресом ранее определенного объекта; именно так мы здесь и
поступили.
В функции main мы написали
for(p = keytab; p < keytab + nkeys; p++)
Если p является указателем структуры, то любая арифметика с p учитывает
фактический размер данной структуры, так что p++ увеличивает p на нужную
величину, в результате чего p указывает на следующий элемент массива
структур. Но не считайте, что размер структуры равен сумме размеров ее
членов, — из-за требований выравнивания для различных объектов в структуре
могут возникать «дыры».
И, наконец, несколько второстепенный вопрос о форме записи программы. Если возвращаемая функцией величина имеет тип, как, например, в
struct key *binary(word, tab, n)
то может оказаться, что имя функции трудно выделить среди текста. В связи с этим иногда используется другой стиль записи:
struct KEY *
binary(word, tab, n)
Это главным образом дело вкуса; выберите ту форму, которая вам нравится, и придерживайтесь ее.
Предположим, что нам надо справиться с более общей задачей, состоящей в подсчете числа появлений всех слов в некотором файле ввода. Так как список слов заранее не известен, мы не можем их упорядочить удобным образом и использовать бинарный поиск. Мы даже не можем осуществлять последовательный просмотр при поступлении каждого слова, с тем чтобы установить, не встречалось ли оно ранее; такая программа будет работать вечно. (Более точно, ожидаемое время работы растет как квадрат числа вводимых слов). Как же нам организовать программу, чтобы справиться со списком произвольных слов?
Одно из решений состоит в том, чтобы все время хранить массив поступающих до сих пор слов в упорядоченном виде, помещая каждое слово в нужное место по мере их поступления. Однако это не следует делать, перемещая слова в линейном массиве, — это также потребует слишком много времени. Вместо этого мы используем структуру данных, называемую двоичным деревом.
Каждому новому слову соответствует один «узел» дерева; каждый узел содержит:
указатель текста слова счетчик числа появлений указатель узла левого потомка указатель узла правого потомка
Никакой узел не может иметь более двух детей; возможно отсутствие детей или наличие только одного потомка.
Узлы создаются таким образом, что левое поддерево каждого узла содержит только те слова, которые меньше слова в этом узле, а правое поддерево только те слова, которые больше. Чтобы определить, находится ли новое слово уже в дереве, начинают с корня и сравнивают новое слово со словом, хранящимся в этом узле. Если слова совпадают, то вопрос решается утвердительно. Если новое слово меньше слова в дереве, то переходят к рассмотрению левого потомка; в противном случае исследуется правый потомок. Если в нужном направлении потомок отсутствует, то значит новое слово не находится в дереве и место этого недостающего потомка как раз и является местом, куда следует поместить новое слово. Поскольку поиск из любого узла приводит к поиску одного из его потомков, то сам процесс поиска по существу является рекурсивным. В соответствии с этим наиболее естественно использовать рекурсивные процедуры ввода и вывода.
Возвращаясь назад к описанию узла, ясно, что это будет структура с четырьмя компонентами:
/* начальный узел */
struct tnode {
char *word; /* указатель на текст */
int count; /* число вхождений */
struct tnode *left; /* левый потомок */
struct tnode *right; /* правый потомок */
};
Это «рекурсивное» описание узла может показаться рискованным, но на самом деле оно вполне корректно. Структура не имеет права содержать ссылку на саму себя, но
struct tnode *left;
описывает left как указатель на узел, а не как сам узел.
Текст самой программы оказывается удивительно маленьким, если, конечно, иметь
в распоряжении набор написанных нами ранее процедур, обеспечивающих нужные
действия. Мы имеем в виду функцию getword для извлечения каждого слова из
файла ввода и функцию alloc для выделения места для хранения слов.
Ведущая программа просто считывает слова с помощью функции getword и помещает
их в дерево, используя функцию tree.
#define MAXWORD 20
/* подсчет частоты вхождений слова */
main()
{
struct tnode *root, *tree();
char word[MAXWORD];
int t;
root = NULL;
while((t = getword(word, MAXWORD)) | = EOF)
if(t == LETTER)
root = tree(root, word);
treeprint(root);
}
Функция tree сама по себе проста. Слово передается функцией main к верхнему
уровню (корню) дерева. На каждом этапе это слово сравнивается со словом, уже
хранящимся в этом узле, и с помощью рекурсивного обращения к tree
просачивается вниз либо к левому, либо к правому поддереву. В конце концов
это слово либо совпадает с каким-то словом, уже находящимся в дереве (в этом
случае счетчик увеличивается на единицу), либо программа натолкнется на
нулевой указатель, свидетельствующий о необходимости создания и добавления к
дереву нового узла. В случае создания нового узла функция tree возвращает
указатель этого узла, который помещается в родительский узел.
/* установить w у или ниже p */
struct tnode *tree(p, w)
struct tnode *p;
char *w;
{
struct tnode *talloc();
char *strsave();
int cond;
if(p == NULL) { /* пришло новое слово */
p = talloc(); /* создать новый узел */
p->word = strsave(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 = tree(p->left, w);
else /* большее идет в правое поддерево */
p->right = tree(p->right, w);
return p;
}
Память для нового узла выделяется функцией talloc, являющейся адаптацией для
данного случая функции alloc, написанной нами ранее. Она возвращает указатель
свободного пространства, пригодного для хранения нового узла дерева. (Мы
вскоре обсудим это подробнее). Новое слово копируется функцией strsave в
скрытое место, счетчик инициализируется единицей, и указатели обоих потомков
полагаются равными нулю. Эта часть программы выполняется только при
добавлении нового узла к ребру дерева. Мы здесь опустили проверку на ошибки
возвращаемых функций strsave и talloc значений (что неразумно для практически
работающей программы).
Функция treeprint печатает дерево, начиная с левого поддерева; в каждом узле
сначала печатается левое поддерево (все слова, которые младше этого слова),
затем само слово, а затем правое поддерево (все слова, которые старше). Если
вы неуверенно оперируете с рекурсией, нарисуйте дерево сами и напечатайте его
с помощью функции treeprint; это одна из наиболее ясных рекурсивных
процедур, которую можно найти.
/* рекурсивная печать дерева p */
treeprint(p)
struct tnode *p;
{
if(p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}
Практическое замечание: если дерево становится «несбалансированным» из-за
того, что слова поступают не в случайном порядке, то время работы программы
может расти слишком быстро. В худшем случае, когда поступающие слова уже
упорядочены, настоящая программа осуществляет дорогостоящую имитацию
линейного поиска. Существуют различные обобщения двоичного дерева, особенно
2-3 деревья и AVL деревья, которые не ведут себя так «в худших случаях», но
мы не будем здесь на них останавливаться.
Прежде чем расстаться с этим примером, уместно сделать небольшое отступление
в связи с вопросом о распределении памяти. Ясно, что в программе желательно
иметь только один распределитель памяти, даже если ему приходится размещать
различные виды объектов. Но если мы хотим использовать один распределитель
памяти для обработки запросов на выделение памяти для указателей на
переменные типа char и для указателей на struct tnode, то при этом возникают
два вопроса. Первый: как выполнить то существующее на большинстве реальных
машин ограничение, что объекты определенных типов должны удовлетворять
требованиям выравнивания (например, часто целые должны размещаться в четных
адресах)? Второй: как организовать описания, чтобы справиться с тем, что
функция alloc должна возвращать различные виды указателей?
Вообще говоря, требования выравнивания легко выполнить за счет выделения
некоторого лишнего пространства, просто обеспечив то, чтобы распределитель
памяти всегда возвращал указатель, удовлетворяющий всем ограничениям
выравнивания. Например, на PDP-11 достаточно, чтобы функция alloc всегда
возвращала четный указатель, поскольку в четный адрес можно поместить любой
тип объекта. Единственный расход при этом — лишний символ при запросе на
нечетную длину. Аналогичные действия предпринимаются на других машинах. Таким
образом, реализация alloc может не оказаться переносимой, но ее использование
будет переносимым. Функция alloc из главы 5 не предусматривает никакого
определенного выравнивания; в главе 8 мы продемонстрируем, как правильно
выполнить эту задачу.
Вопрос описания типа функции alloc является мучительным для любого языка,
который серьезно относится к проверке типов. Лучший способ в языке C —
объявить, что alloc возвращает указатель на переменную типа char, а затем
явно преобразовать этот указатель к желаемому типу с помощью операции
перевода типов. Таким образом, если описать p в виде
char *p;
то
(struct tnode *) p
преобразует его в выражениях в указатель на структуру типа tnode.
Следовательно, функцию talloc можно записать в виде:
struct tnode *talloc()
{
char *alloc();
return (struct TNODE *) alloc(sizeof(struct TNODE));
}
это более чем достаточно для работающих в настоящее время компиляторов, но это и самый безопасный путь с учетом будущего.
Напишите программу, которая читает C-программу и печатает в алфавитном порядке каждую группу имен переменных, которые совпадают в первых семи символах, но отличаются где-то дальше. (Сделайте так, чтобы 7 было параметром).
Напишите программу выдачи перекрестных ссылок, т.е. программу, которая печатает список всех слов документа и для каждого из этих слов печатает список номеров строк, в которые это слово входит.
Напишите программу, которая печатает слова из своего файла ввода, расположенные в порядке убывания частоты их появления. Перед каждым словом напечатайте число его появлений.
Для иллюстрации дальнейших аспектов использования структур в этом разделе мы
напишем программу, представляющую собой содержимое пакета поиска в таблице.
Эта программа является типичным представителем подпрограмм управления
символьными таблицами макропроцессора или компилятора. Рассмотрим, например,
оператор #define языка C. Когда встречается строка вида
#define YES 1
то имя YES и заменяющий текст 1 помещаются в таблицу. Позднее, когда имя YES
появляется в операторе вида
inword = YES;
Оно должно быть замещено на 1.
Имеются две основные процедуры, которые управляют именами и заменяющими их
текстами. Функция install(s, t) записывает имя s и заменяющий текст t в
таблицу; здесь s и t просто символьные строки. Функция lookup(s) ищет имя s в
таблице и возвращает либо указатель того места, где это имя найдено, либо
NULL, если этого имени в таблице не оказалось.
При этом используется поиск по алгоритму хеширования — поступающее имя
преобразуется в маленькое положительное число, которое затем используется для
индексации массива указателей. Элемент массива указывает на начало цепочных
блоков, описывающих имена, которые имеют это значение хеширования. Если
никакие имена при хешировании не получают этого значения, то элементом
массива будет NULL.
Блоком цепи является структура, содержащая указатели на соответствующее имя, на заменяющий текст и на следующий блок в цепи. Нулевой указатель следующего блока служит признаком конца данной цепи.
struct nlist { /* базовый вход таблицы */
char *name;
char *def;
struct nlist *next; /* следующий вход в цепи */
};
Массив указателей это просто
#define HASHSIZE 100 static struct nlist *hashtab[HASHSIZE] /* таблица указателей */
Значение функции хеширования, используемой обеими функциями lookup и install,
получается просто как остаток от деления суммы символьных значений строки на
размер массива. (Это не самый лучший возможный алгоритм, но его достоинство
состоит в исключительной простоте).
/* сформировать хеш-значение для строки */
hash(s)
char *s;
{
int hashval;
for(hashval = 0; *s != '\0';)
hashval += *s++;
return hashval % HASHSIZE;
}
В результате процесса хеширования выдается начальный индекс в массиве
hashtab; если данная строка может быть где-то найдена, то именно в цепи
блоков, начало которой указано там. Поиск осуществляется функцией lookup.
Если функция lookup находит, что данный элемент уже присутствует, то она
возвращает указатель на него; если нет, то она возвращает NULL.
/* искать s в хеш-таблице */
struct nlist *lookup(s)
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; /* не найдено */
}
Функция install использует функцию lookup для определения, не присутствует ли
уже вводимое в данный момент имя; если это так, то новое определение должно
вытеснить старое. В противном случае создается совершенно новый элемент. Если
по какой-либо причине для нового элемента больше нет места, то функция
install возвращает NULL.
/* поместить (name, def) */
struct nlist *install(name, def)
char *name, *def;
{
struct nlist *np, *lookup();
char *strsave(), *alloc();
int hashval;
if((np = lookup(name)) == NULL) { /* не найден */
np = (struct nlist *) alloc(sizeof(*np));
if(np == NULL)
return NULL;
if((np->name = strsave(name)) == NULL)
return NULL;
hashval = hash(np->name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
}
else /* уже здесь */
free((np->def); /* освободить предыдущее определение */
if((np->def = strsave(def)) == NULL)
return NULL;
return np;
}
Функция strsave просто копирует строку, указанную в качестве аргумента, в
место хранения, полученное в результате обращения к функции alloc. Мы уже
привели эту функцию в главе 5. Так как обращение к функции alloc и free могут
происходить в любом порядке и в связи с проблемой выравнивания, простой
вариант функции alloc из главы 5 нам больше не подходит;
смотрите главы 7 и 8.
Напишите процедуру, которая будет удалять имя и определение из таблицы,
управляемой функциями lookup и install.
Разработайте простую, основанную на функциях этого раздела, версию процессора
для обработки конструкций #define, пригодную для использования с
C-программами. Вам могут также оказаться полезными функции getchar и ungetch.
Когда вопрос экономии памяти становится очень существенным, то может оказаться необходимым помещать в одно машинное слово несколько различных объектов; одно из особенно распространенных употреблений — набор однобитовых признаков в применениях, подобных символьным таблицам компилятора. Внешне обусловленные форматы данных, такие как интерфейсы аппаратных средств также зачастую предполагают возможность получения слова по частям.
Представьте себе фрагмент компилятора, который работает с символьной
таблицей. С каждым идентификатором программы связана определенная информация,
например, является он или нет ключевым словом, является ли он или нет внешним
и/или статическим и т.д. Самый компактный способ закодировать такую
информацию — поместить набор однобитовых признаков в отдельную переменную
типа char или int.
Обычный способ, которым это делается, состоит в определении набора «масок», отвечающих соответствующим битовым позициям, как в
#define KEYWORD 01 #define EXTERNAL 02 #define STATIC 04
(числа должны быть степенями двойки). Тогда обработка битов сведется к «жонглированию битами» с помощью операций сдвига, маскирования и дополнения, описанных нами в главе 2.
Некоторые часто встречающиеся идиомы:
flags |= EXTERNAL | STATIC;
включает биты EXTERNAL и STATIC в flags, в то время как
flags &= ~(EXTERNAL | STATIC);
их выключает, а
if((flags & (EXTERNAL | STATIC)) == 0) ...
истинно, если оба бита выключены.
Хотя этими идиомами легко овладеть, язык C в качестве альтернативы предлагает
возможность определения и обработки полей внутри слова непосредственно, а не
посредством побитовых логических операций. Поле — это набор смежных битов
внутри одной переменной типа int. Синтаксис определения и обработки полей
основывается на структурах. Например, символьную таблицу конструкций #define,
приведенную выше, можно бы было заменить определением трех полей:
struct {
unsigned is_keyword : 1;
unsigned is_extern : 1;
unsigned is_static : 1;
} flags;
Здесь определяется переменная с именем flags, которая содержит три 1-битовых
поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны
как unsigned, чтобы подчеркнуть, что они действительно будут величинами без
знака.
На отдельные поля можно ссылаться, как flags.is_static, flags.is_extern,
flags.is_keyword и т.д., то есть точно так же, как на другие члены структуры.
Поля ведут себя подобно небольшим целым без знака и могут участвовать в
арифметических выражениях точно так же, как и другие целые. Таким образом,
предыдущие примеры более естественно переписать так:
flags.is_extern = flags.is_static = 1;
для включения битов;
flags.is_extern = flags.is_static = 0;
для выключения битов;
if(flags.is_extern == 0 && flags.is_static == 0) ...
для их проверки.
Поле не может перекрывать границу int; если указанная ширина такова, что это
должно случиться, то поле выравнивается по границе следующего int. Полям
можно не присваивать имена; неименованные поля (только двоеточие и ширина)
используются для заполнения свободного места. Чтобы вынудить выравнивание на
границу следующего int, можно использовать специальную ширину 0.
При работе с полями имеется ряд моментов, на которые следует обратить внимание. По-видимому наиболее существенным является то, что отражая природу различных аппаратных средств, распределение полей на некоторых машинах осуществляется слева направо, а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы с внутренне определенными структурами данных, при разделении внешне определяемых данных следует тщательно рассматривать вопрос о том, какой конец поступает первым.
Другие ограничения, которые следует иметь в виду: поля не имеют знака; они
могут храниться только в переменных типа int (или, что эквивалентно, типа
unsigned); они не являются массивами; они не имеют адресов, так что к ним не
применима операция &.
Объединение — это переменная, которая в различные моменты времени может содержать объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера и требований выравнивания. Объединения представляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации.
В качестве примера, снова из символьной таблицы компилятора, предположим, что
константы могут быть типа int, float или быть указателями на символы.
Значение каждой конкретной константы должно храниться в переменной
соответствующего типа, но все же для управления таблицей самым удобным было
бы, если это значение занимало бы один и тот же объем памяти и хранилось в
том же самом месте независимо от его типа. Это и является назначением
объединения — выделить отдельную переменную, в которой можно законно хранить
любую одну из переменных нескольких типов. Как и в случае полей, синтаксис
основывается на структурах.
union u_tag {
int ival;
float fval;
char *pval;
} uval;
Переменная uval будет иметь достаточно большой размер, чтобы хранить
наибольший из трех типов, независимо от машины, на которой осуществляется
компиляция, — программа не будет зависеть от характеристик аппаратных
средств. Любой из этих трех типов может быть присвоен uvar и затем
использован в выражениях, пока такое использование совместимо: извлекаемый
тип должен совпадать с последним помещенным типом. Дело программиста —
следить за тем, какой тип хранится в объединении в данный момент; если
что-либо хранится как один тип, а извлекается как другой, то результаты будут
зависеть от используемой машины.
Синтаксически доступ к членам объединения осуществляется следующим образом:
<имя объединения>.<член>
или
<указатель объединения> -> <член>
то есть точно так же, как и в случае структур. Если для отслеживания типа,
хранимого в данный момент в uval, используется переменная utype, то можно
встретить такой участок программы:
if(utype == int)
printf("%d\n", uval.ival);
else if(utype == FLOAT)
printf("%f\n", uval.fval);
else if(utype == STRING)
printf("%s\n", uval.pval);
else
printf("Плохой тип в %d utype\n", utype);
Объединения могут появляться внутри структур и массивов и наоборот. Запись для обращения к члену объединения в структуре (или наоборот) совершенно идентична той, которая используется во вложенных структурах. Например, в массиве структур, определенным следующим образом
struct {
char *name;
int flags;
int utype;
union {
int ival;
float fval;
char *pval;
} uval;
} symtab[NSYM];
на переменную ival можно сослаться как
symtab[i].uval.ival
а на первый символ строки pval как
*symtab[i].uval.pval
В сущности объединение является структурой, в которой все члены имеют нулевое смещение. Сама структура достаточно велика, чтобы хранить «самый широкий» член, и выравнивание пригодно для всех типов, входящих в объединение. Как и в случае структур, единственными операциями, которые в настоящее время можно проводить с объединениями, являются доступ к члену и извлечение адреса; объединения не могут быть присвоены, переданы функциям или возвращены ими. Указатели объединений можно использовать в точно такой же манере, как и указатели структур.
Программа распределения памяти, приводимая в главе 8, показывает, как можно использовать объединение, чтобы сделать некоторую переменную выровненной по определенному виду границы памяти.
В языке C предусмотрена возможность, называемая typedef для введения новых
имен для типов данных. Например, описание
typedef int length;
делает имя length синонимом для int. «Тип» length может быть использован в
описаниях, переводов типов и т.д. Точно таким же образом, как и тип int:
length len, maxlen; length *lengths[];
Аналогично описанию
typedef char *string;
делает string синонимом для char*, то есть для указателя на символы, что
затем можно использовать в описаниях вида
string p, lineptr[lines], alloc();
Обратите внимание, что объявляемый в конструкции typedef тип появляется в
позиции имени переменной, а не сразу за словом typedef. Синтаксически
конструкция typedef подобна описаниям класса памяти extern, static и т.д.
Мы также использовали прописные буквы, чтобы яснее выделить имена.
В качестве более сложного примера мы используем конструкцию typedef для
описания узлов дерева, рассмотренных ранее в этой главе:
typedef struct tnode { /* основной узел */
char *word; /* указатель на текст */
int count; /* число вхождений */
struct tnode *left; /* левый потомок */
struct tnode *right; /* правый потомок */
} treenode, *treeptr;
В результате получаем два новых ключевых слова: treenode (структура) и
treeptr (указатель на структуру). Тогда функцию talloc можно записать в виде
treeptr talloc()
{
char *alloc();
return (treeptr) alloc(sizeof(treenode));
}
Необходимо подчеркнуть, что описание typedef не приводит к созданию нового в
каком-либо смысле типа; оно только добавляет новое имя для некоторого
существующего типа. При этом не возникает и никакой новой семантики:
описанные таким способом переменные обладают точно теми же свойствами, что и
переменные, описанные явным образом. По существу конструкция typedef сходна с
#define за исключением того, что она интерпретируется компилятором и потому
может осуществлять подстановки текста, которые выходят за пределы
возможностей макропроцессора языка C. Например,
typedef int (*pfi)();
создает тип pfi для «указателя функции, возвращающей значение типа int»,
который затем можно было бы использовать в программе сортировки из главы 5 в
контексте вида
pfi strcmp, numcmp, swap;
Имеются две основные причины применения описаний typedef. Первая причина
связана с параметризацией программы, чтобы облегчить решение проблемы
переносимости. Если для типов данных, которые могут быть машинно-зависимыми,
использовать описание typedef, то при переносе программы на другую машину
придется изменить только эти описания. Одна из типичных ситуаций состоит в
использовании определяемых с помощью typedef имен для различных целых величин
и в последующем подходящем выборе типов short, int и long для каждой
имеющейся машины. Второе назначение typedef состоит в обеспечении лучшей
документации для программы — тип с именем treeptr может оказаться более
удобным для восприятия, чем тип, который описан только как указатель сложной
структуры. И наконец, всегда существует вероятность, что в будущем компилятор
или некоторая другая программа, такая как lint, сможет использовать
содержащуюся в описаниях typedef информацию для проведения некоторой
дополнительной проверки программы.