Array M. УЭИТ - Язык Си - руководство для начинающих

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

РИС. 14.9. Структура двоичного дерева.

Является ли эта разветвленная конструкция более эффективной чем массив? Рассмотрим случай дерева с 10 уровнями узлов. Если вы составите его, то найдете 1023 узла, в которых вы можете запомнить, скажем, 1023 слова. Если слова упорядочены, согласно некоторому разумному плану, вы можете начать с верхнего уровня и находить любое слово в лучшем случае за 9 перемещений, если ваш поиск идет сверху вниз с одного уровня на следующий. Если слова находятся в массиве, вам, может быть, придется перебрать все 1023 элемента, прежде чем вы найдете нужное слово.

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

Это наше последнее слово о структурах. Далее мы хотим вкратце ознакомить вас с двумя другими средствами языка Си для работы с данными: объединением и функцией typedef.

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

Объединения устанавливаются таким же способом, как и структуры. Есть шаблон объединения и переменные объединения. Они могут определяться одновременно или, если используется имя объединения, последовательно за два шага. Вот пример шаблона с именем объединения:

union holders {

int digit;

double bigf1;

char letter; };

А вот пример определения переменных объединения типа holdem:

union holdem fit; /* переменная объединения типа holdem */

union holdem save[10]; /* массив из 10 переменных объединения */

union holdem *pu; /* указатель на переменную типа holdem */

Первое описание создаст одну переменную fit. Компилятор выделяет достаточно памяти для размещения самой большой из описанных переменных. В этом случае наибольшей из возможных является переменная double, для которой требуется в нашей системе 64 разряда или 8 байтов. Массив saveимел бы 10 элементов, каждый по 8 байтов.

Вот как используется объединение:

fit.digit = 23; /* 23 записывается в fit; используется 2 байта */

fit.double = 2.0; /* 23 стирается, 2.0 записывается; используется 8 байтов */

fit.letter = 'h'; /* 2.0 стирается, h записывается; используется 1 байт */

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

Вы сами должны следить за типом данных, записываемых в данный момент в объединение; приведенная ниже последовательность операторов показывает, что нельзя делать:

fit.lеtter = 'A';

finum = 3.02*fit.double; /* ОШИБКА ОШИБКА ОШИБКА */

Ошибка заключается в том, что записано значение типа char, a следующая строка предполагает, что содержимое fitимеет тип double.

Можно использовать операцию - >с объединениями таким же образом, как это делалось для структур:

pu = &fit;

х = рu -> digit; /* то же, что и х=fit.digit */

Рассмотрим теперь еще одно средство языка для работы с данными.

Функция typedefпозволяет нам создать свое собственное имя типа. Это напоминает директиву #define, но со следующими тремя изменениями:

1. В отличие от #defineфункция typedefдает символические имена, но ограничивается только типами данных.

2. Функция typedefвыполняется компилятором, а не препроцессором.

3. В своих пределах функция typedefболее гибка, чем #define.

Посмотрим, как она работает. Предположим, вы хотите использовать термин realдля чисел типа float. Тогда вы определяете термин real, как если бы он был переменной типа float, и перед его определением ставите ключевое слово typedef:

typedef float real;

С этого момента вы можете использовать realдля определения переменных:

real х, у[25], *рr;

Область действия такого определения зависит от расположения оператора typedef. Если определение находится внутри функции, то область действия локальна и ограничена этой функцией. Если определение расположено вне функции, то область действия глобальна.

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

typedef float REAL;

В последнем примере можно было бы применить директиву #define. А здесь это делать нельзя:

typedef char *STRING;

Без ключевого слова typedefоператор определял бы STRINGкак указатель на тип char. С ключевым словом оператор делает STRING идентификатором указателей на тип char. Так,

STRING name, sign;

означает

char *name, *sign;

Мы можем использовать typedefи для структур. Вот пример:

typedef struct COMPLEX {

float real;

float imag; };

Кроме того, можно использовать тип COMPLEXдля представления комплексных чисел.

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

typedef char *FRPTC ( ) [5];

приводит к тому, что FRPTCобъявляет тип, являющийся функцией, которая возвращает указатель на пятиэлементный массив типа char. (См. "Причудливые описания".)

Третья причина использования typedefзаключается в том, чтобы сделать программы более мобильными. Предположим, например, что вашей программе нужно использовать 16-разрядные числа. В некоторых системах это был бы тип short, в других же он может быть типом int. Если вы использовали в ваших описаниях shortили int, то должны изменить все описания, когда перейдете от одной системы к другой. Вместо этого сделайте следующее, В файле директивы #includeесть такое определение: