Структуры оказываются полезными при организации сложных
данных особенно в больших программах, поскольку во многих
ситуациях они позволяют сгруппировать связанные данные таким
образом, что с ними можно обращаться, как с одним целым, а
не как с отдельными объектами. В этой главе мы постараемся
продемонстрировать то, как используются структуры. Програм-
мы, которые мы для этого будем использовать, больше, чем
многие другие в этой книге, но все же достаточно умеренных
размеров.
Давайте снова обратимся к процедурам преобразования даты
из главы 5. Дата состоит из нескольких частей таких, как
день, месяц, и год, и, возможно, день года и имя месяца. Эти
пять переменных можно объеденить в одну структуру вида:
STRUCT DATE \(
INT DAY;
INT MONTH;
INT YEAR;
INT YEARDAY;
CHAR MON_NAME[4];
\);
Описание структуры, состоящее из заключенного в фигурные
скобки списка описаний, начинается с ключевого слова STRUCT.
За словом STRUCT может следовать необязательное имя, называ-
емое ярлыком структуры (здесь это DATе). Такой ярлык именует
структуры этого вида и может использоваться в дальнейшем как
сокращенная запись подробного описания.
Элементы или переменные, упомянутые в структуре, называ-
ются членами. Ярлыки и члены структур могут иметь такие же
имена, что и обычные переменные (т.е. Не являющиеся членами
структур), поскольку их имена всегда можно различить по кон-
тексту. Конечно, обычно одинаковые имена присваивают только
тесно связанным объектам.
Точно так же, как в случае любого другого базисного ти-
па, за правой фигурной скобкой, закрывающей список членов,
может следовать список переменных.
Оператор
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
увеличивает х, а не р, так как оно эквивалентно выражению
++(P->х). Для изменения порядка выполнения операций можно
использовать круглые скобки: (++P)->х увеличивает P до дос-
тупа к х, а (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
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[ ]. В стандартной библиотеке языка "C" предус-
мотрены макросы 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 на нужную величину, в результате чего P указы-
вает на следующий элемент массива структур. Но не считайте,
что размер структуры равен сумме размеров ее членов, - из-за
требований выравнивания для различных объектов в структуре
могут возникать "дыры".
И, наконец, несколько второстепенный вопрос о форме за-
писи программы. Если возвращаемая функцией величина имеет
тип, как, например, в
STRUCT KEY *BINARY(WORD, TAB, N)
Tо может оказаться, что имя функции трудно выделить среди
текста. В связи с этим иногда используется другой стиль за-
писи:
STRUCT KEY *
BINARY(WORD, TAB, N)
Это главным образом дело вкуса; выберите ту форму, которая
вам нравится, и придерживайтесь ее.
Предположим, что нам надо справиться с более общей зада-
чей, состоящей в подсчете числа появлений всех слов в неко-
тором файле ввода. Так как список слов заранее не известен,
мы не можем их упорядочить удобным образом и использовать
бинарный поиск. Мы даже не можем осуществлять последователь-
ный просмотр при поступлении каждого слова, с тем чтобы ус-
тановить, не встречалось ли оно ранее; такая программа будет
работать вечно. (Более точно, ожидаемое время работы растет
как квадрат числа вводимых слов). Как же нам организовать
программу, чтобы справиться со списком произвольных слов?
Одно из решений состоит в том, чтобы все время хранить
массив поступающих до сих пор слов в упорядоченном виде, по-
мещая каждое слово в нужное место по мере их поступления.
OДнако это не следует делать, перемещая слова в линейном
массиве, - это также потребует слишком много времени. Вместо
этого мы используем структуру данных, называемую доичным де-
ревом.
Каждому новому слову соответствует один "узел" дерева;
каждый узел содержит:
указатель текста слова
----------------------
счетчик числа появлений
-----------------------
указатель узла левого потомка
-----------------------------
указатель узла правого потомка
------------------------------
Никакой узел не может иметь более двух детей; возможно от-
сутсвие детей или наличие только одного потомка.
Узлы создаются таким образом, что левое поддерево каждо-
го узла содержит только те слова, которые меньше слова в
этом узле, а правое поддерево только те слова, которые боль-
ше. Чтобы определить, находится ли новое слово уже в дереве,
начинают с корня и сравнивают новое слово со словом, храня-
щимся в этом узле. Если слова совпадают, то вопрос решается
утвердительно. Если новое слово меньше слова в дереве, то
переходят к рассмотрению левого потомка; в противном случае
исследуется правый потомок. Если в нужном направлении пото-
мок отсутствует, то значит новое слово не находится в дереве
и место этого недостающего потомка как раз и является мес-
том, куда следует поместить новое слово. Поскольку поиск из
любого узла приводит к поиску одного из его потомков, то сам
процесс поиска по существу является рекурсивным. В соответс-
твии с этим наиболее естественно использовать рекурсивные
процедуры ввода и вывода.
Возвращаясь назад к описанию узла, ясно, что это будет
структура с четырьмя компонентами:
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 */
\);
Это "рекурсивное" описание узла может показаться рискован-
ным, но на самом деле оно вполне корректно. Структура не
имеет права содержать ссылку на саму себя, но
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, а затем явно преоб-
разовать этот указатель к желаемому типу с помощью операции
перевода типов. Таким образом, если описать P в виде
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;
Oно должно быть замещено на 1.
Имеются две основные процедуры, которые управляют имена-
ми и заменяющими их текстами. Функция INSTALL(S,T) записыва-
ет имя S и заменяющий текст T в таблицу; здесь S и T просто
символьные строки. Функция LOOKUP(S) ищет имя S в таблице и
данных особенно в больших программах, поскольку во многих
ситуациях они позволяют сгруппировать связанные данные таким
образом, что с ними можно обращаться, как с одним целым, а
не как с отдельными объектами. В этой главе мы постараемся
продемонстрировать то, как используются структуры. Програм-
мы, которые мы для этого будем использовать, больше, чем
многие другие в этой книге, но все же достаточно умеренных
размеров.
Давайте снова обратимся к процедурам преобразования даты
из главы 5. Дата состоит из нескольких частей таких, как
день, месяц, и год, и, возможно, день года и имя месяца. Эти
пять переменных можно объеденить в одну структуру вида:
STRUCT DATE \(
INT DAY;
INT MONTH;
INT YEAR;
INT YEARDAY;
CHAR MON_NAME[4];
\);
Описание структуры, состоящее из заключенного в фигурные
скобки списка описаний, начинается с ключевого слова STRUCT.
За словом STRUCT может следовать необязательное имя, называ-
емое ярлыком структуры (здесь это DATе). Такой ярлык именует
структуры этого вида и может использоваться в дальнейшем как
сокращенная запись подробного описания.
Элементы или переменные, упомянутые в структуре, называ-
ются членами. Ярлыки и члены структур могут иметь такие же
имена, что и обычные переменные (т.е. Не являющиеся членами
структур), поскольку их имена всегда можно различить по кон-
тексту. Конечно, обычно одинаковые имена присваивают только
тесно связанным объектам.
Точно так же, как в случае любого другого базисного ти-
па, за правой фигурной скобкой, закрывающей список членов,
может следовать список переменных.
Оператор
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
увеличивает х, а не р, так как оно эквивалентно выражению
++(P->х). Для изменения порядка выполнения операций можно
использовать круглые скобки: (++P)->х увеличивает P до дос-
тупа к х, а (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
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[ ]. В стандартной библиотеке языка "C" предус-
мотрены макросы 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 на нужную величину, в результате чего P указы-
вает на следующий элемент массива структур. Но не считайте,
что размер структуры равен сумме размеров ее членов, - из-за
требований выравнивания для различных объектов в структуре
могут возникать "дыры".
И, наконец, несколько второстепенный вопрос о форме за-
писи программы. Если возвращаемая функцией величина имеет
тип, как, например, в
STRUCT KEY *BINARY(WORD, TAB, N)
Tо может оказаться, что имя функции трудно выделить среди
текста. В связи с этим иногда используется другой стиль за-
писи:
STRUCT KEY *
BINARY(WORD, TAB, N)
Это главным образом дело вкуса; выберите ту форму, которая
вам нравится, и придерживайтесь ее.
Предположим, что нам надо справиться с более общей зада-
чей, состоящей в подсчете числа появлений всех слов в неко-
тором файле ввода. Так как список слов заранее не известен,
мы не можем их упорядочить удобным образом и использовать
бинарный поиск. Мы даже не можем осуществлять последователь-
ный просмотр при поступлении каждого слова, с тем чтобы ус-
тановить, не встречалось ли оно ранее; такая программа будет
работать вечно. (Более точно, ожидаемое время работы растет
как квадрат числа вводимых слов). Как же нам организовать
программу, чтобы справиться со списком произвольных слов?
Одно из решений состоит в том, чтобы все время хранить
массив поступающих до сих пор слов в упорядоченном виде, по-
мещая каждое слово в нужное место по мере их поступления.
OДнако это не следует делать, перемещая слова в линейном
массиве, - это также потребует слишком много времени. Вместо
этого мы используем структуру данных, называемую доичным де-
ревом.
Каждому новому слову соответствует один "узел" дерева;
каждый узел содержит:
указатель текста слова
----------------------
счетчик числа появлений
-----------------------
указатель узла левого потомка
-----------------------------
указатель узла правого потомка
------------------------------
Никакой узел не может иметь более двух детей; возможно от-
сутсвие детей или наличие только одного потомка.
Узлы создаются таким образом, что левое поддерево каждо-
го узла содержит только те слова, которые меньше слова в
этом узле, а правое поддерево только те слова, которые боль-
ше. Чтобы определить, находится ли новое слово уже в дереве,
начинают с корня и сравнивают новое слово со словом, храня-
щимся в этом узле. Если слова совпадают, то вопрос решается
утвердительно. Если новое слово меньше слова в дереве, то
переходят к рассмотрению левого потомка; в противном случае
исследуется правый потомок. Если в нужном направлении пото-
мок отсутствует, то значит новое слово не находится в дереве
и место этого недостающего потомка как раз и является мес-
том, куда следует поместить новое слово. Поскольку поиск из
любого узла приводит к поиску одного из его потомков, то сам
процесс поиска по существу является рекурсивным. В соответс-
твии с этим наиболее естественно использовать рекурсивные
процедуры ввода и вывода.
Возвращаясь назад к описанию узла, ясно, что это будет
структура с четырьмя компонентами:
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 */
\);
Это "рекурсивное" описание узла может показаться рискован-
ным, но на самом деле оно вполне корректно. Структура не
имеет права содержать ссылку на саму себя, но
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, а затем явно преоб-
разовать этот указатель к желаемому типу с помощью операции
перевода типов. Таким образом, если описать P в виде
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;
Oно должно быть замещено на 1.
Имеются две основные процедуры, которые управляют имена-
ми и заменяющими их текстами. Функция INSTALL(S,T) записыва-
ет имя S и заменяющий текст T в таблицу; здесь S и T просто
символьные строки. Функция LOOKUP(S) ищет имя S в таблице и