C. Глава 6. Структурные типы данных
"Структура - это одна или несколько переменных (возможно, различных типов), которые для удобства работы с ними сгруппированы под одним именем. Структуры помогают в организации сложных данных (особенно в больших программах), поскольку позволяют группу связанных между собой переменных трактовать не как множество отдельных элементов, а как единое целое."
"Единственно возможные операции над структурами - это их копирование, присваивание, взятие адреса с помощью & и осуществление доступа к ее элементам. Копирование и присваивание также включают в себя передачу функциям аргументов и возврат ими значений. Структуры нельзя сравнивать. Инициализировать структуру можно списком константных значений ее элементов; автоматическую структуру также можно инициализировать присваиванием."
(Б. Керниган, Д. Ритчи "Язык программирования C")
1. Группировка данных
Про структуры уже почти все сказано в цитатах к этой главе. Но давайте рассмотрим один полезный пример. Обычно в литературе идет пример с записью из таблицы базы данных: имя, должность, зарплата… или что-то в таком духе, просто, чтобы объяснить синтаксис объявлений и способы обращения со структурами. Но лучше взять какой-нибудь более полезный пример. Базы данных - штука весьма непростая и бесполезный пример будет неинтересным.
Возьмем такую вещь, как парсер выражений с инфиксными операторами. Если у нас есть произвольное выражение, состоящее из чисел и арифметических операций, то мы не имеем права выполнять операции подряд, начиная, допустим, слева. Вот простой пример: 1 + 2 * 3. Очевидно, что в таком случае результат получится 9, но любой младший школьник заметит, что он неверен. На самом деле, как учит любая марьиванна по математике, надо сначала умножить, а потом сложить. Тогда получится верный ответ 7.
Пример посложнее: 1 + 2 * 3 ^ 4. Здесь есть возведение в степень и его придется выполнить первым. Начнем со случая попроще. Алгоритм разбора выражения можно сделать очень простым именно с помощью структур:
//struct.c - структуры в C
struct infix // структура, описывающая операцию
{
int left; // левый операнд
int right; // правый операнд
char op; // код операции
char priority; // приоритет
};
struct infix left = { 1, 2, '+', 1 },
right = { 2, 3, '*', 2 };
Лст. 6-1. Пример объявления структуры в языке C и создания двух экземпляров.
Структура объявляется ключевым словом struct, за которым идет блок (последовательность инструкций в фигурных скобках) объявлений ее членов. Каждый член объявляется обычным образом: указание типа, имени, и возможной инициализации. После слова struct можно указать тег структуры, который будет полезным для ссылок при дальнейших объявлениях. Если после объявления структуры с тегом ничего не указано, то память для нее не будет выделена. Если мы хотим создать парочку экземпляров объявленной структуры, то следует снова указать struct, затем ее тег, затем имя конкретного экземпляра структуры и затем можно инициализировать созданный экземпляр, подобно тому, как это принято для массивов.
Мы можем посмотреть, что сделал компилятор, выполнив команду c -r struct:
.file "struct.c"
.globl left
.data
.align 4
.size left, 12
left:
.long 1
.long 2
.byte 43
.byte 1
.zero 2
.globl right
.align 4
.size right, 12
right:
.long 2
.long 3
.byte 42
.byte 2
.zero 2
Лст. 6-2. Распределение памяти для структур (файл struct.s).
Для каждого экземпляра структуры выделяется по 12 байтов: 8 для двух переменных типа int (несмотря на long было выделено по 4 байта), два байта для маленьких чисел и осталось еще по два нулевых байта. Нетрудно представить, из уже известного, как они будут выглядеть в памяти.
Обе структуры могли бы быть созданы и более топорно:
//struct.c - структуры в C
struct
{
int left;
int right;
char op;
char priority;
} left;
struct
{
int left;
int right;
char op;
char priority;
} right;
Лст. 6-3. Другой способ объявления и определения структур.
Поскольку на этот раз мы их не инициализировали, то компилятор выделит для них память в сегменте неинициализированных данных:
.file "struct.c"
.comm left,12,4
.comm right,12,4
Лст. 6-4. Пустые структуры.
Можно объявить массив структур, как объявляют массивы любых других типов. Но язык C дает возможность задать новое имя для любого типа данных, в том числе, и для данных структурного типа. Фактически это создание нового типа, хотя и на логическом уровне. (Физический уровень, понятно, ограничен байтами, словами разной ширины, и размерами данных числового процессора. Все это аппаратно задано в режимах счетчика адресов.) Новый тип объявляется ключевым словом typedef. Попробуем создать тип infix:
//struct.c - структуры в C
typedef struct
{
int left;
int right;
char op;
char priority;
} infix;
infix left, right;
Лст. 6-5. Новый тип данных.
Если выполнить c -r struct, то листинг будет точно таким же как 6-4. Теперь о том, как работать со структурами или типами на их основе.
2. Доступ к членам структур
Присваивание членам структур отличается от того, что у нас было при инициализации в листинге 6-1. Пример в следующей программе (которая ничего не делает):
//struct.c - структуры в C
typedef struct
{
int left;
int right;
char op;
char priority;
} infix;
infix left, right;
infix *iptr = &right; // получим адрес структуры
main()
{
left.left = 1; // непосредственный доступ
// к члену структуры
iptr->right = 2; // косвенный, к члену right
// объекта right типа infix
}
Лст. 6-6. Присваивание членам структур.
В первом случае … кстати, как называть переменные составного типа infix? В объектно-ориентированных языках, ближайший пример C++, их называют объектами. Мы можем договориться называть их так же, используя на равных правах название структура.
Итак, в первом случае, члену объекта left с именем left присваивается значение. После имени объекта употребляется точка, затем имя члена объекта. Во втором случае используется оператор -> , косвенного указания. Вот как это выглядит в ассемблере:
.file "struct.c"
.comm left,12,4
.comm right,12,4
.globl iptr
.data
.align 8
.size iptr, 8
iptr:
.quad right
.text
.globl main
main:
pushq %rbp
movq %rsp, %rbp
movl $1, left(%rip) | left.left = 1;
movq iptr(%rip), %rax | iptr->right = 2;
movl $2, 4(%rax) |
popq %rbp
ret
Лст. 6-7. Присваивание членам структур (с точки зрения ассемблера).
Что можно делать с созданным типом infix? Он не так бесполезен, как может показаться. Мы можем написать несколько функций, выполняющих полезную работу. А чтобы увидеть эту работу, давайте сначала напишем парсер для математического выражения не содержащего скобок. Выражение может содержать числа и четыре арифметических оператора. Затем мы напишем код, автоматически разбирающий приоритеты операторов и вычисляющий выражения.
//struct.c - структуры в C
#include
#include
char expr[] = " 1 + 2*3 -12 +14/2*7 ";
char buff[256]; // копия строки для разбора
char val[20][10]; // таблица значений
char ops[2][10]; // таблица операций
char *ptr,
*numlist = "0123456789 ", // списки
*oplist = "+-*/ "; // разделителей
int i,j,k;
#define NULL 0
main()
{
i = j = k = 0;
strcpy( buff, expr );
ptr = strtok( buff, oplist );
while( ptr ) {
strcpy( val[i++], ptr );
ptr = strtok( NULL, oplist );
}
strcpy( buff, expr );
ptr = strtok( buff, numlist );
while( ptr ) {
strcpy( ops[j++], ptr );
ptr = strtok( NULL, numlist );
}
puts( "values:" );
for( k = 0; k < i; k++ ) puts( val[k] );
puts( "operators:" );
for( k = 0; k < j; k++ ) puts( ops[k] );
}
Лст. 6-8. Лексический разбор простого математического выражения.
Мы разбираем достаточно небрежно записанное выражение expr при помощи функции strtok и своеобразного суррогата регулярных выражений в списках разделителей numlist и oplist. Поскольку strtok портит исходную строку, то мы сначала создаем копию в буфере buff. Результаты попадают в два массива: val и ops. Первый двумерный массив состоит из 10 строк по 20 байтов (достаточных для записи строк, представляющих числа long). Второй массив состоит из 10 строк длиной 2 байта - первый байт для знака арифметической операции, второй - для завершающего нуля.
Поскольку пробелы входят в оба списка, то они очищаются для чисел и для знаков операций. Алгоритм состоит из двух одинаковых частей: разбор строки с выделение операндов, и разбор той же строки с выделением операций. Было бы неплохо просто подменять списки разделителей между вызовами strtok, но функция использует только один набор статических данных, и мы вынуждены использовать ее дважды.
NULL используется "в назидательных" целях. Вообще-то он определен в stddef.h и притом уже не в стиле стандарта K&R, которого мы более-менее (за исключением однажды упоминавшегося enum) придерживаемся в наших простых примерах.
Получив разбор, давайте распечатаем его на экране:
$ struct
values:
1
2
3
12
14
2
7
operators:
+
*
-
+
/
*
$
Лст. 6-9. Выражение, разобранное на лексические элементы.
Теперь, обращаясь к этим массивам, мы можем инициализировать объекты left и right:
main()
{
lexer(); // весь разбор строки expr
left.left = atoi( val[0] );
left.right = atoi( val[1] );
left.op = ops[0][0];
right.left = atoi( val[1] );
right.right = atoi( val[2] );
right.op = ops[0][1];
}
Лст. 6-10. Инициализация объектов операций.
lexer - это просто функция, куда переехал почти весь код из функции main предыдущего листинга. Так как мы используем глобальные переменные, то никаких аргументов ей не требуется. Так что, это просто полка, куда мы переложили код, чтобы он не мешал под руками.
Несколько слов нужно сказать по поводу обращения с двухмерными массивами, в данном случае, массивами строк. Первый индексный оператор (первая пара скобок) указывает на байт строки, а второй - на индекс самой строки, ее номер в массиве. Обращаясь по адресу [0][n] мы всегда берем нулевой байт n-ной строки, а это у нас как раз знак операции: + - * или /.
Для вычисления значений операции мы можем написать функцию execute:
int execute( infix o )
{
switch( o.op )
{
case '+':
return o.left + o.right;
case '-':
return o.left - o.right;
case '*':
return o.left * o.right;
case '/':
return o.left / o.right;
default:
return 0;
}
}
Лст. 6-11. "Метод", работающий с объектом.
Чтобы не плодить зря листинги, достаточно заметить, что execute( left ) вернет 3, а execute( right ) вернет 6. Но у нас есть еще один неинициализированный член, это priority. Так как мы знаем приоритеты операций, то можем написать функцию, опять-таки, работающую с объектом типа infix (в cpp сказали бы классом), которая смотрит, что за операция прочитана и устанавливает ее приоритет в соответствующей переменной:
int setp( infix *o )
{
switch( o->op )
{
case '+':
case '-':
o->priority = 1;
break;
case '*':
case '/':
o->priority = 2;
break;
default:
o->priority = 0;
}
return o->priority;
}
Лст. 6-12. Функция определяющая приоритет операции.
В предыдущую функцию, execute, структура передавалась целиком. Точнее, передавалась ее копия по значению. Функция setp получает указатель на структуру и, таким образом, может ее изменить, чего не в состоянии сделать execute, так как она полностью теряет связь с оригинальным объектом.
setp( &left );
setp( iptr ); // iptr указывал на right
puts( itoa( left.priority, 10 ) );
puts( itoa( right.priority, 10 ) );
Лст. 6-13. Проверка работы setp.
Если компилятор начнет жаловаться на тип возвращаемой функции, включите в программу файл stdlib.h, я не сделал это в листингах этой главы.
В setp можно передавать адрес двумя способами: либо получая его на месте оператором &, либо используя указатель. Если мы захотим написать и использовать очевидную функцию int getp, возвращающую приоритет операции, то безопаснее будет передавать объект по значению, так как мы случайно не изменим приоритет, хотя это слишком простой случай для таких опасений.
Вместо выяснения самого значения приоритета, можно написать функцию, которая возвращает разность приоритетов:
int compare( infix *l, infix *r )
{
return l->priority - r->priority;
}
Лст. 6-14. Функция сравнения.
Структуры нельзя сравнивать в обычном смысле, но можно сравнивать их отдельные члены.
Но что теперь делать со всем этим богатством, спросит читатель? Давайте решим произвольное выражение из двух операций, используя начало строки expr. Вот вся функция main:
main()
{
lexer(); // весь разбор строки expr
left.left = atoi( val[0] );
left.right = atoi( val[1] );
left.op = ops[0][0];
right.left = atoi( val[1] );
right.right = atoi( val[2] );
right.op = ops[1][0];
setp( &left );
setp( iptr ); // iptr указывал на right
if( compare( &left, &right ) >= 0 ) {
// приоритет левой части не меньше правой
// выполняем левую операцию
i = execute( left );
// подставляем результат в левую часть
// правой операции
right.left = i;
// и и выполняем ее
i = execute( right );
} else {
// иначе действуем наоборот
i = execute( right );
left.right = i;
i = execute( left );
}
puts( itoa( i, 10 ) );
}
Лст. 6-15. Выбор операции для выполнения.
Как бы мы не меняли начало выражения expr, результат будет правильным, потому, что сначала будет выполняться операция с большим или равным приоритетом. Но это справедливо только для выражения из трех членов, содержащее две операции. Если у нас есть 1 + 2 * 3 / 4, то результат окажется неверным. Поскольку приоритетов всего два, то достаточно взять три операции подряд. Тогда найдется пара соседних операций, имеющих одинаковый приоритет.
Мы могли бы использовать три структуры infix: left, middle, right, или op1, op2, op3 и написать алгоритм для вычисления произвольного выражения и даже произвольной длины из четырех основных арифметических операций. Если оформить его как функцию, то для скобки можно просто использовать рекурсивный вызов этой же самой функции и затем передать результат вызывающей функции. Но у нас пока еще нет даже дробных чисел! Так что пока оставим эту тему в покое.
Целью этой главы было простое ознакомление с данными структурного типа и способам обращения с ними. Можно заметить, что структуры дают большие возможности для создания разнообразных абстракций, уровней описания и т.д. Например, если добавить операцию возведения в степень, то пришлось бы всего лишь немного изменить функцию execute, а весь остальной код остался бы неизменным. Правда, это только для однократного возведения в степень, общее выражение потребовало бы заметно менять правила игры. Но все равно, польза от структурных типов очевидна, они хорошо помогают упорядочивать множество имен в программе.
Благодаря структурам появились и объектные языки, тот же C++, например. К данным добавились функции и получились классы. В C++ наш infix стал бы классом, а execute, setp и compare - его методами, и писались через точку или -> в точности, как и данные.
Однако, не стоит преувеличивать ценность структур и объектного подхода. Он может как сильно помочь, сделав сложную программу простой и ясной, так и сильно навредить, сделав простую программу сложной и запутанной. Судьей тут может быть только здравый смысл в конкретном случае. Если задача хорошо разобрана, то структуры данных очень четко определяются и код становится намного проще. Если начинают работать по принципу: "а чего тут думать, надо программировать", то не помогут никакие чудо-языки и компиляторы. (А за использование C++ вас выгонит из своей команды даже Линус Торвальдс.)
Так чего там у нас не хватает? Чисел с плавающей запятой. В следующей главе займемся ими.
. . . продолжение следует . . .