	Навигация
	Обратная связь Последние публикации

	Вход для пользователей
	Имя пользователя: * Пароль: * Запросить новый пароль

	Кто на сайте
	Сейчас на сайте 0 пользователей и 2 гостя.

Kernighan, B. W. and Ritchie, D. M. "The 'C' Programming Language"; Chapter 6

Структуры.

Структура - это набор из одной или более переменных, возможноразличных типов, сгруппированных под одним именем для удобстваобработки. (в некоторых языках, самый известный из которых паскаль,структуры называются "записями").

Традиционным примером структуры является учетная карточка работающего:"служащий" описывается набором атрибутов таких, как фамилия, имя,отчество (ф.и.о.), адрес, код социального обеспечения, зарплата и т.д.некоторые из этих атрибутов сами могут оказаться структурами: ф.и.о.Имеет несколько компонент, как и адрес, и даже зарплата.

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

Основные сведения.

Давайте снова обратимся к процедурам преобразования даты изглавы 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) /* set day of year from month, day */ 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) /* set month and day from day of year */ 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->x). Дляизменения порядка выполнения операций можно использовать круглые скобки:(++p)->x увеличивает р до доступа к x, а (p++)->x увеличивает р после.(Круглые скобки в последнем случае необязательны. Почему?)

Совершенно аналогично *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 main() /* count "C" keywords */ {        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); } binary(word, tab, n) /* find word in tab[0]...tab[n-1] */ 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) /* get next word from input */ 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.

 type(c) /* return type of ascii character */ 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[ ]. В стандартной библиотеке языка "Си" предусмотрены макросыisalpha и isdigit, действующие необходимым образом.

Упражнение 6-1.: Сделайте такую модификацию функции getword иоцените, как изменится скорость работы программы.
Упражнение 6-2.: Напишите вариант функции type, не зависящий отконкретного набора символов.
Упражнение 6-3.: Напишите вариант программы подсчета ключевыхслов, который бы не учитывал появления этих слов в заключенныхв кавычки строках.

Указатели на структуры.

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

Внешнее описание массива keytab не нужно изменять, но функцииmain и binary требуют модификации.

 main() /* count c keyword; pointer version */ {        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); } struct key *binary(word, tab, n) /* find word */ char *word /* in tab[0]...tab[n-1] */ struct key tab []; 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 указываетна следующий элемент массива структур.Но не считайте, что размер структуры равен сумме размеров ее членов,- из-за требований выравнивания для различных об'ектов в структуремогут возникать "дыры".

И, наконец, несколько второстепенный вопрос о форме записи программы.Если возвращаемая функцией величина имеет тип, как, например, в

struct key *binary(word, tab, n)

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

struct key *binary(word, tab, n)

Это главным образом дело вкуса; выберите ту форму, которая вамнравится, и придерживайтесь ее.

Структуры, ссылающиеся на себя.

Предположим, что нам надо справиться с более общей задачей, состоящейв подсчете числа появлений всех слов в некотором файле ввода. Так каксписок слов заранее не известен, мы не можем их упорядочить удобнымобразом и использовать бинарный поиск. Мы даже не можем осуществлятьпоследовательный просмотр при поступлении каждого слова, с тем чтобыустановить, не встречалось ли оно ранее; такая программа будет работатьвечно. (более точно, ожидаемое время работы растет как квадрат числавводимых слов). Как же нам организовать программу, чтобы справиться сосписком произвольных слов?

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

Каждому новому слову соответствует один "узел" дерева; каждый узелсодержит:

указатель текста слова
счетчик числа появлений
указатель узла левого потомка
указатель узла правого потомка

Никакой узел не может иметь более двух детей; возможноотсутсвие детей или наличие только одного потомка.

Узлы создаются таким образом, что левое поддерево каждого узласодержит только те слова, которые меньше слова в этом узле, аправое поддерево только те слова, которые больше. Чтобы определить,находится ли новое слово уже в дереве, начинают с корня и сравниваютновое слово со словом, хранящимся в этом узле. Если слова совпадают,то вопрос решается утвердительно. Если новое слово меньше слова вдереве, то переходят к рассмотрению левого потомка; в противном случаеисследуется правый потомок. Если в нужном направлении потомокотсутствует, то значит новое слово не находится в дереве и место этогонедостающего потомка как раз и является местом, куда следует поместитьновое слово. Поскольку поиск из любого узла приводит к поиску одного изего потомков, то сам процесс поиска по существу является рекурсивным. Всоответствии с этим наиболее естественно использовать рекурсивныепроцедуры ввода и вывода.

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

 struct tnode {                 /* the basic node */        char *word;             /* points tq the text */        int count;              /* number of occurrences */        struct tnode *left;     /* left child */        struct tnode *right;    /* right child */ };

Это "рекурсивное" описание узла может показаться рискованным, но насамом деле оно вполне корректно. Структура не имеет права содержатьссылку на саму себя, но

 struct tnode *left;

описывает left как указатель на узел, а не как сам узел.

Текст самой программы оказывается удивительно маленьким, если,конечно, иметь в распоряжении набор написанных нами ранее процедур,обеспечивающих нужные действия. Мы имеем в виду функцию getword дляизвлечения каждого слова из файла ввода и функцию alloc для выделенияместа для хранения слов.

Ведущая программа просто считывает слова с помощью функции getword ипомещает их в дерево, используя функцию tree.

 #define maxword 20 main() /* word freguency count */ {        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 возвращает указательэтого узла, который помещается в родительский узел.

 struct tnode *tree(p, w)  /* install w at or below p */ struct tnode *p; char *w; {        struct tnode *talloc();        char *strsave();        int cond;        if (p == NULL) {        /* a new word has arrived */                p == talloc();  /* make a new node */                p->word = strsave(w);                p->count = 1;                p->left = p->right = NULL;        } else if ((cond = strcmp(w, p->word)) == 0)                p->count++;  /* repeated word */        else if (cond < 0)   /* lower goes into left subtree */                p->left = tree(p->left, w);        else                    /* greater into right subtree */                p->right = tree(p->right, w);        return(p); }

Память для нового узла выделяется функцией talloc, являющейся адаптациейдля данного случая функции alloc, написанной нами ранее. Она возвращаетуказатель свободного пространства, пригодного для хранения нового узладерева. (мы вскоре обсудим это подробнее). Новое слово копируетсяфункцией strsave в скрытое место, счетчик инициализируется единицей, иуказатели обоих потомков полагаются равными нулю. Эта часть программывыполняется только при добавлении нового узла к ребру дерева. Мы здесьопустили проверку на ошибки возвращаемых функций strsave и tallocзначений (что неразумно для практически работающей программы).

Функция treeprint печатает дерево, начиная с левого поддерева; в каждомузле сначала печатается левое поддерево (все слова, которые младше этогослова), затем само слово, а затем правое поддерево (все слова, которыестарше). Если вы неуверенно оперируете с рекурсией, нарисуйте деревосами и напечатайте его с помощью функции treeprint ; это одна изнаиболее ясных рекурсивных процедур, которую можно найти.

 treeprint (p) /* print tree p recursively */ 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, а затем явно преобразовать этот указатель к желаемому типу спомощью операции перевода типов. Таким образом, если описать р в виде

 char *p;

то

 (struct tnode *) p

преобразует его в выражениях в указатель на структуру типа tnode .Следовательно, функцию talloc можно записать в виде:

 struct tnode *talloc() {        char *alloc();        return ((struct tnode *) alloc(sizeof(struct tnode))); }

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

Упражнение 6-4.: Напишите программу, которая читает "C"-программу и печатает в алфавитномпорядке каждую группу имен переменных, которые совпадают в первых семисимволах, но отличаются где-то дальше. (сделайте так, чтобы 7 былопараметром).
Упражнение 6-5.: Напишите программу выдачи перекрестных ссылок, т.е. программу, котораяпечатает список всех слов документа и для каждого из этих слов печатаетсписок номеров строк, в которые это слово входит.
Упражнение 6-6.: Напишите программу, которая печатает слова из своего файла ввода,расположенные в порядке убывания частоты их появления. Перед каждымсловом напечатайте число его появлений.

Поиск в таблице.

Для иллюстрации дальнейших аспектов использования структур в этомразделе мы напишем программу, представляющую собой содержимое пакетапоиска в таблице. Эта программа является типичным представителемподпрограмм управления символьными таблицами макропроцессора иликомпилятора. Рассмотрим, например, оператор #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 {                 /* basic table entry */        char *name;        char *def;        struct nlist *next;     /* next entry in chain */ };

массив указателей это просто

#define hashsize 100static struct nlist *hashtab[hashsize] /* pointer table */

Значение функции хеширования, используемой обеими функциями lookup иinstall, получается просто как остаток от деления суммы символьныхзначений строки на размер массива.(Это не самый лучший возможный алгоритм, но его достоинство состоит висключительной простоте).

 hash(s) /* form hash value for string */ char *s; {        int hashval;        for (hashval = 0; *s != '\0'; )                hashval += *s++;        return(hashval % hashsize); }

В результате процесса деширования выдается начальный индекс в массивеhashtab ; если данная строка может быть где-то найдена, то именно в цепиблоков, начало которой указано там. Поиск осуществляется функциейlookup. Если функция lookup находит, что данный элемент ужеприсутствует, то она возвращает указатель на него; если нет, то онавозвращает NULL.

 struct nlist *lookup(s) /* look for s in hashtab */ char *s; {        struct nlist *np;        for (np = hashtab[hash(s)]; np != NULL;np=np->next)                if (strcmp(s, np->name) == 0)                        return(np);  /* found it */        return(NULL); /* not found */

Функция install использует функцию lookup для определения, неприсутствует ли уже вводимое в данный момент имя; если это так, то новоеопределение должно вытеснить старое. В противном случае создаетсясовершенно новый элемент. Если по какой-либо причине для нового элементабольше нет места, то функция install возвращает NULL.

 struct nlist *install(name, def) /* put (name, def) */ char *name, *def; {        struct nlist *np, *lookup();        char *strsave(), *alloc();        int hashval;        if((np = lookup(name)) == NULL) {        /* not found */                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                                   /* already there */                free((np->def);    /* free previous definition */        if ((np->def = strsave(def)) == NULL)                return (NULL);        return(np); }

Функция strsave просто копирует строку, указанную в качестве аргумента,в место хранения, полученное в результате обращения к функции alloc. Мыуже привели эту функцию в главе 5. Так как обращение к функции alloc иfree могут происходить в любом порядке и в связи с проблемойвыравнивания, простой вариант функции alloc из главы 5 нам больше неподходит; смотрите главы 7 и 8.

Упражнение 6-7.: Напишите процедуру, которая будет удалять имя и определение из таблицы,управляемой функциями lookup и install.
Упражнение 6-8.: Разработайте простую, основанную на функциях этого раздела, версиюпроцессора для обработки конструкций #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) ...

Истинно, если оба бита выключены.

Хотя этими идиомами легко овладеть, язык "Си" в качестве альтернативыпредлагает возможность определения и обработки полей внутри слованепосредственно, а не посредством побитовых логических операций.Поле - это набор смежных битов внутри одной переменной типа int.Синтаксис определения и обработки полей основывается на структурах.Например, символьную таблицу конструкций #define, приведенную выше,можно бы было заменить определением трех полей:

 struct {        unsigned is_keyword : 1;        unsigned is_extern : 1;        unsigned is_static : 1; } flags;

Здесь определяется переменная с именем flags, которая содержиттри 1-битовых поля. Следующее за двоеточием число задает ширинуполя в битах. Поля описаны как unsigned, чтобы подчеркнуть, чтоони действительно будут величинами без знака.

На отдельные поля можно ссылаться, как flags.is_statie, 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("bad type %d in 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 {         /* the basic node */        char *word;             /* points to the text */        int count;              /* number of occurrences */        struct tnode *left;     /* left child */        struct tnode *right;    /* right child */ } treenode, *treeptr;

В результате получаем два новых ключевых слова: treenode (структура)и treeptr (указатель на структуру). Тогда функцию talloc можнозаписать в виде

 treeptr talloc() {        char *alloc();        return((treeptr) alloc(sizeof(treenode))); }

необходимо подчеркнуть, что описание typedef не приводит ксозданию нового в каком-либо смысле типа; оно только добавляетновое имя для некоторого существующего типа. При этом невозникает и никакой новой семантики: описанные таким способомпеременные обладают точно теми же свойствами, что и переменные,описанные явным образом. По существу конструкция typedef сходна с#define за исключением того, что она интерпретируется компилятором ипотому может осуществлять подстановки текста, которые выходят запределы возможностей макропроцессора языка "Си". Например,

 typedef int (*pfi) ();

создает тип pfi для "указателя функции, возвращающей значение типаint", который затем можно было бы использовать в программе сортировкииз главы 5 в контексте вида

 pfi strcmp, numcmp, swap;

Имеются две основные причины применения описаний typedef. Перваяпричина связана с параметризацией программы, чтобы облегчить решениепроблемы переносимости. Если для типов данных, которые могут бытьмашинно-зависимыми, использовать описание typedef, то при переносепрограммы на другую машину придется изменить только эти описания.Одна из типичных ситуаций состоит в использовании определяемых спомощью typedef имен для различных целых величин и в последующемподходящем выборе типов short, int и long для каждой имеющейся машины.

Второе назначение typedef состоит в обеспечении лучшей документации дляпрограммы - тип с именем treeptr может оказаться более удобным длявосприятия, чем тип, который описан только как указатель сложнойструктуры.

И наконец, всегда существует вероятность, что в будущем компиляторили некоторая другая программа, такая как lint, сможет использоватьсодержащуюся в описаниях typedef информацию для проведения некоторойдополнительной проверки программы.

Навигация

Вход для пользователей

Кто на сайте

Kernighan, B. W. and Ritchie, D. M. "The 'C' Programming Language"; Chapter 6

Структуры.

Содержание