45940 (665245), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

ки не зависит от операций сравнения и перестановки, так что,

передавая в него различные функции сравнения и перестановки,

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

Именно такой подход используется в нашей новой программе

сортировки.

Как и прежде, лексикографическое сравнение двух строк

осуществляется функцией STRCMP, а перестановка функцией

SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки

на основе численного значения и возвращающая условное указа-

ние того же вида, что и STRCMP. Эти три функции описываются

в MAIN и указатели на них передаются в SORT. В свою очередь

функция SORT обращается к этим функциям через их указатели.

мы урезали обработку ошибок в аргументах с тем, чтобы сосре-

доточиться на главных вопросах.

• 125 -

#DEFINE LINES 100 /* MAX NUMBER OF LINES

TO BE SORTED */

MAIN(ARGC, ARGV) /* SORT INPUT LINES */ INT ARGC;

CHAR *ARGV[];

\(

CHAR LINEPTR[LINES]; / POINTERS TO TEXT LINES */

INT NLINES; /* NUMBER OF INPUT LINES READ */

INT STRCMP(), NUMCMP(); /* COMPARSION FUNCTIONS */

INT SWAP(); /* EXCHANGE FUNCTION */

INT NUMERIC = 0; /* 1 IF NUMERIC SORT */

IF(ARGC>1 && ARGV[1][0] == '-' && ARGV[1][1]=='N')

NUMERIC = 1;

IF(NLINES = READLINES(LINEPTR, LINES)) >= 0) \(

IF (NUMERIC)

SORT(LINEPTR, NLINES, NUMCMP, SWAP);

ELSE

SORT(LINEPTR, NLINES, STRCMP, SWAP);

WRITELINES(LINEPTR, NLINES);

\) ELSE

PRINTF(“INPUT TOO BIG TO SORT\N”);

\)

Здесь STRCMP, NIMCMP и SWAP - адреса функций; так как извес-

тно, что это функции, операция & здесь не нужна совершенно

аналогично тому, как она не нужна и перед именем массива.

Передача адресов функций организуется компилятором.

Второй шаг состоит в модификации SORT:

SORT(V, N, COMP, EXCH) /* SORT STRINGS V[0] ... V[N-1] */ CHAR V[]; / INTO INCREASING ORDER */ INT N;

INT (*COMP)(), (*EXCH)();

\(

INT GAP, I, J;

FOR(GAP = N/2; GAP > 0; GAP /= 2)

FOR(I = GAP; I < N; I++)

FOR(J = I-GAP; J >= 0; J -= GAP) \(

IF((*COMP)(V[J], V[J+GAP]) <= 0)

BREAK;

(*EXCH)(&V[J], &V[J+GAP]);

\)

\)

• 126 -

Здесь следует обратить определенное внимание на описа-

ния. Описание

INT (*COMP)()

говорит, что COMP является указателем на функцию, которая

возвращает значение типа INT. Первые круглые скобки здесь

необходимы; без них описание

INT *COMP()

говорило бы, что COMP является функцией, возвращающей указа-

тель на целые, что, конечно, совершенно другая вещь.

Использование COMP в строке

IF (*COMP)(V[J], V[J+GAP]) <= 0)

полностью согласуется с описанием: COMP - указатель на функ-

цию, *COMP - сама функция, а

(*COMP)(V[J], V[J+GAP])

• обращение к ней. Круглые скобки необходимы для правильного

объединения компонентов.

Мы уже приводили функцию STRCMP, сравнивающую две строки

по первому численному значению:

NUMCMP(S1, S2) /* COMPARE S1 AND S2 NUMERICALLY */ CHAR *S1, *S2;

\(

DOUBLE ATOF(), V1, V2;

V1 = ATOF(S1);

V2 = ATOF(S2);

IF(V1 < V2)

RETURN(-1);

ELSE IF(V1 > V2)

RETURN(1);

ELSE

RETURN (0);

\)

Заключительный шаг состоит в добавлении функции SWAP,

переставляющей два указателя. Это легко сделать, непосредст-

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

• 127 -

SWAP(PX, PY) /* INTERCHANGE *PX AND *PY */

CHAR *PX[], *PY[];

\(

CHAR *TEMP;

TEMP = *PX;

*PX = *PY;

*PY = TEMP;

\)

Имеется множество других необязятельных аргументов, ко-

торые могут быть включены в программу сортировки: некоторые

из них составляют интересные упражнения.

Упражнение 5-11.

Модифицируйте SORT таким образом, чтобы она работала с

меткой -R, указывающей на сортировку в обратном (убывающем)

порядке. Конечно, -R должна работать с -N.

Упражнение 5-12.

Добавьте необязательный аргумент -F, объединяющий вместе

прописные и строчные буквы, так чтобы различие регистров не

учитывалось во время сортировки: данные из верхнего и нижне-

го регистров сортируются вместе, так что буква 'а' прописное

и 'а' строчное оказываются соседними , а не разделенными це-

лым алфавитом.

Упражнение 5-13.

Добавьте необязательный аргумент -D (“словарное упорядо-

чивание”), при наличии которого сравниваются только буквы,

числа и пробелы. Позаботьтесь о том, чтобы эта функция рабо-

тала и вместе с -F.

Упражнение 5-14.

Добавьте возможность обработки полей, так чтобы можно

было сортировать поля внутри строк. Каждое поле должно сор-

тироваться в соответствии с независимым набором необязатель-

ных аргументов. (предметный указатель этой книги сортировал-

ся с помощью аргументов -DF для категории указателя и с -N

для номеров страниц).

• 128 -

6. Структуры.

Структура - это набор из одной или более переменных,

возможно различных типов, сгруппированных под одним именем

для удобства обработки. (В некоторых языках, самый известный

из которых паскаль, структуры называются “записями”).

Традиционным примером структуры является учетная карточ-

ка работающего: “служащий” описывается набором атрибутов та-

ких, как фамилия, имя, отчество (ф.и.о.), адрес, код соци-

ального обеспечения, зарплата и т.д. Некоторые из этих атри-

бутов сами могут оказаться структурами: ф.и.о. Имеет нес-

колько компонент, как и адрес, и даже зарплата.

Структуры оказываются полезными при организации сложных

данных особенно в больших программах, поскольку во многих

ситуациях они позволяют сгруппировать связанные данные таким

образом, что с ними можно обращаться, как с одним целым, а

не как с отдельными объектами. В этой главе мы постараемся

продемонстрировать то, как используются структуры. Програм-

мы, которые мы для этого будем использовать, больше, чем

многие другие в этой книге, но все же достаточно умеренных

размеров.

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

Давайте снова обратимся к процедурам преобразования даты

из главы 5. Дата состоит из нескольких частей таких, как

день, месяц, и год, и, возможно, день года и имя месяца. Эти

пять переменных можно объеденить в одну структуру вида:

STRUCT DATE \(

INT DAY;

INT MONTH;

INT YEAR;

INT YEARDAY;

CHAR MON_NAME[4];

\);

Описание структуры, состоящее из заключенного в фигурные

скобки списка описаний, начинается с ключевого слова STRUCT.

За словом STRUCT может следовать необязательное имя, называ-

емое ярлыком структуры (здесь это DATе). Такой ярлык именует

структуры этого вида и может использоваться в дальнейшем как

сокращенная запись подробного описания.

Элементы или переменные, упомянутые в структуре, называ-

ются членами. Ярлыки и члены структур могут иметь такие же

имена, что и обычные переменные (т.е. Не являющиеся членами

структур), поскольку их имена всегда можно различить по кон-

тексту. Конечно, обычно одинаковые имена присваивают только

тесно связанным объектам.

• 129 -

Точно так же, как в случае любого другого базисного ти-

па, за правой фигурной скобкой, закрывающей список членов,

может следовать список переменных.

Оператор

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]);

• 130 -

Структуры могут быть вложенными; учетная карточка служа-

щего может фактически выглядеть так:

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

будет ссылаться на месяц рождения. Операция указания члена

структуры “.” ассоциируется слева направо.

6.2. Структуры и функции.

В языке “C” существует ряд ограничений на использование

структур. Обязательные правила заключаются в том, что единс-

твенные операции, которые вы можете проводить со структура-

ми, состоят в определении ее адреса с помощью операции & и

доступе к одному из ее членов. Это влечет за собой то, что

структуры нельзя присваивать или копировать как целое, и что

они не могут быть переданы функциям или возвращены ими. (В

последующих версиях эти ограничения будут сняты). На указа-

тели структур эти ограничения однако не накладываются, так

что структуры и функции все же могут с удобством работать

совместно. И наконец, автоматические структуры, как и авто-

матические массивы, не могут быть инициализированы; инициа-

лизация возможна только в случае внешних или статических

структур.

Давайте разберем некоторые из этих вопросов, переписав с

этой целью функции перобразования даты из предыдущей главы

так, чтобы они использовали структуры. Так как правила зап-

рещают непосредственную передачу структуры функции, то мы

должны либо передавать отдельно компоненты, либо передать

указатель всей структуры. Первая возможность демонстрируется

на примере функции DAY_OF_YEAR, как мы ее написали в главе

5:

D.YEARDAY = DAY_OF_YEAR(D.YEAR, D.MONTH, D.DAY);

• 131 -

другой способ состоит в передаче указателя. если мы опишем

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 MONTH; I++)

DAY += DAY_TAB[LEAP][I];

RETURN(DAY);

\)

Описание

STRUCT DATE *PD;

говорит, что PD является указателем структуры типа DATE.

Запись, показанная на примере

PD->YEAR

является новой. Если P - указатель на структуру, то

P-> член структуры

обращается к конкретному члену. (Операция -> - это знак ми-

нус, за которым следует знак “>”.)

Так как PD указывает на структуру, то к члену YEAR можно

обратиться и следующим образом

(*PD).YEAR

но указатели структур используются настолько часто, что за-

пись -> оказывается удобным сокращением. Круглые скобки в

(*PD).YEAR необходимы, потому что операция указания члена

• 132 -

стуктуры старше , чем * . Обе операции, “->” и “.”, ассоции-

руются слева направо, так что конструкции слева и справа

зквивалентны

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.

• 133 -

6.3. Массивы сруктур.

Структуры особенно подходят для управления массивами

связанных переменных. Рассмотрим, например, программу подс-

чета числа вхождений каждого ключевого слова языка “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 \),

. . .

• 134 -

Но когда инициализаторы являются простыми переменными или

символьными строками и все они присутствуют, то во внутрен-

них фигурных скобках нет необходимости. Как обычно, компиля-

тор сам вычислит число элементов массива 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 каждый раз, как она находит слово,

и копирует это слово в свой первый аргумент.

• 135 -

Величина NKEYS - это количество ключевых слов в массиве

KEYTAB . Хотя мы можем сосчитать это число вручную, гораздо

легче и надежнее поручить это машине, особенно в том случае,

если список ключевых слов подвержен изменениям. Одной из

возможностей было бы закончить список инициализаторов указа-

нием на нуль и затем пройти в цикле сквозь массив KEYTAB,

пока не найдется конец.

Но, поскольку размер этого массива полностью определен к

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

Число элементов просто есть

SIZE OF KEYTAB / SIZE OF STRUCT KEY

дело в том, что в языке “C” предусмотрена унарная операция

SIZEOF, выполняемая во время компиляции, которая позволяет

вычислить размер любого объекта. Выражение

SIZEOF(OBJECT)

выдает целое, равное размеру указанного объекта. (Размер оп-

ределяется в неспецифицированных единицах, называемых “бай-

тами”, которые имеют тот же размер, что и переменные типа

Характеристики

Список файлов реферата