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

Рассмотрим метку структуры student, описание которой было дано выше как

struct student {

char name[25];

int id, age;

char sex;

}

Указатель new_student определен как

struct student *new_student;

Предположим, что память выделена таким образом, чтобы new_student указывал на объект student. Тогда на компоненты этого объекта можно ссылаться следующим образом:

(*new_student).name

(*new_student).id

(*new_student).age

(*new_student).sex

Поскольку указатели часто используются для указания на структуры, в языке Си специально для ссылок на компоненты таких структур введен оператор выбора стрелка вправо ->. Например, ссылки на вышеприведенные компоненты структуры можно записать с использованием оператора стрелки вправо -> как:

new_student->name

new_student->id

new_student->age

new_student->sex

Массив структур

Процесс описания массива структур совершенно аналогичен описанию любого другого типа массива:

struct book libry[MAXBKS];

Этот оператор объявляет libry массивом, состоящим из MAXBKS-элементов. Каждый элемент массива представляет собой структуру типа book. Таким образом, libry[0] является book-структурой, libry[1] - второй book-структурой и т.д.

Определение элементов массива структур. При определении элементов массива структур мы применяем те же самые правила, которые используются для отдельных структур: сопровождаем имя структуры операцией получения элемента и имени элемента:

libry[0].value value - первый элемент массива

libry[4].title title - пятый элемент массива

Переименование типов

Формат

typedef старый_тип новый_тип

Примеры:

typedef long large;

/* определяется тип large, эквивалентный типу long */

typedef char *string;

/* тип string, эквивалентен типу char* */

Переименование типов используется для введения осмысленных или сокращенных имен типов, что повышает понятность программ, и для улучшения переносимости программ (имена одного типа данных могут различаться на разных ЭВМ).

Пример:

/* Реализован алгоритм, который позволяет определить

строки матриц, состоящие из одинаковых целых,

расположенных в различных столбцах. Используются

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

сортировка строк по возрастанию. Отсортированные

строки сравниваются и выводятся на экран номера

одинаковых строк */

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#include <conio.h>

#define n 4 /*количество строк */

#define m 4 /*количество столбцов*/

typedef struct mas{int i,i1;} mas;

int m1[n][m]; /*исходный массив*/

struct mas{int i,i1;};

mas a[n*2];

/*массив типа mas, где будут лежать одинаковые

строки, a[1].i и a[1].i1 - одинаковые строки*/

void main()

{

clrscr();

int i,j;

randomize();

for(i=0;i<n;i++)

for(j=0;j<m;j++)

m1[i][j]=random(2);

/*случайным образом в массив заносим целые*/

for(i=0;i<n;i++) {

printf("\n %d) ",i);

for(int j=0;j<m;j++)

printf(" %d",m1[i][j]);

}

int min, p;

/* индекс минимального элемента после s-го элемента

i-ой строки сортировка строк массива по возрастанию */

for(i=0;i<n;i++) { /* i-сортировка i-ой строки */

for(int s=0;s<m-1;s++) {

min=m1[i][s+1];

for(int j=s;j<m;j++)

if(m1[i][j]<=min) {

min=m1[i][j];p=j;

}

/* запоминаем минимальный элемент в ряду после

s-го элемента */

if(m1[i][s]>=min) {

m1[i][p]=m1[i][s];m1[i][s]=min;

}

/* меняем местами s-й и p-й элемент,если

s-й > p-го(минимального) */

}

}

printf("\n");

for(i=0;i<n;i++) {

printf("\n %d) ",i);

for(int j=0;j<m;j++)

printf(" %d",m1[i][j]);

/* выводим отсортированный массив */

}

int s,k=0;

/*сколько элементов в i-й строке совпадают с элементами i1 строки*/

/*сколько строк совпали*/

int i1;

for(i=0;i<n-1;i++) /* верхняя строка i */

for(i1=i+1;i1<n;i1++) { /* нижняя строка i1 */

s=0;

for(int j=0;j<m;j++)

/* сравнение идет по j-му столбцу */

if(m1[i][j]==m1[i1][j]) s++;

/* если соответствующие элементы в i-й и i1-й строки совпадают то кол-во совпавших увеличивается на 1 */

if(s==m) {a[k].i=i;a[k].i1=i1;k++;}

/* если все элементы i-й и i1-й строки совпали, то они одинаковые */

}

printf("\n Совпадающие строки :");

for(i=0;i<k;i++)

printf("\n %d и %d",a[i].i,a[i].i1);

/* распечатываем a[i].i-ю и a[i].i1-ю совпадающую

строку */

getch();

}

M. Уэйт, С. Прата, Д. Мартин

Язык Си

[Содержание] [Вниз]

14. Структуры и другие типы данных

СТРУКТУРЫ ДАННЫХ

СТРУКТУРНЫЕ ШАБЛОНЫ, ТЕГИ И ПЕРЕМЕННЫЕ

ДОСТУПНЫЕ ЧАСТИ СТРУКТУРЫ

СТРУКТУРНЫЕ УКАЗАТЕЛИ

СТРУКТУРНЫЕ МАССИВЫ

ФУНКЦИИ И СТРУКТУРЫ

ОБЪЕДИНЕНИЯ

СОЗДАНИЕ НОВЫХ ТИПОВ

КЛЮЧЕВЫЕ СЛОВА

struct, union, typedef

ОПЕРАЦИИ

->

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

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

ТИПОВАЯ ЗАДАЧА: ИНВЕНТАРИЗАЦИЯ КНИГ

Далее Содержание

Гвен Гленн хочет напечатать опись своих книг. Она хотела бы занести в нее различную информацию о каждой книге: ее название, фамилию автора, издательство, год издания, число страниц, тираж и цену. Теперь некоторые из этих элементов, такие, как название, можно записать в массив строк. Другие элементы требуют массив целого типа или массив типа float. Если работать с семью различными массивами и следить за веси содержащейся в них информацией, можно сойти с ума, особенно если Гвен желает иметь несколько списков - список, упорядоченный по названиям, список, упорядоченный по авторам, по цене и т. д. Гораздо лучше было бы использовать один массив, в котором каждый элемент содержал бы всю информацию о книге.

Но какой тип данных может содержать строки и числа одновременно и как-то хранить эту информацию раздельно? Ответом должна быть, конечно, тема данной главы - структура. Чтобы посмотреть, как создается структура и как она работает, начнем с небольшого примера. Для упрощения задачи введем два ограничения: первое - мы включим в опись только название книги, фамилию автора и цену; второе - ограничим опись до одной книги. Если у вас больше книг, не беспокойтесь; мы покажем, как расширить эту программу.

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

/* инвентаризация одной книги */

#include <stdio.h>

#define MAXTIT 41 /* максимальная длина названия + 1 */

#define MAXAUT 31 /* максимальная длина фамилии автора + 1 */

struct book { /* шаблон первой структуры: book

является именем типа структуры */

char title [MAXTIT]; /* символьный массив для названия */

char author [MAXAUT]; /* символьный массив для фамилии автора */

float value; /* переменная для хранения цены книги */

}; /* конец шаблона структуры */

main( )

{

struct book libry; /* описание переменной типа book */

printf(" Введите, пожалуйста, название книги.\n");

gets(libry. title); /* доступ к элементу title */

printf(" Теперь введите фамилию автора.\n");

gets(libry.author);

printf(" Теперь введите цену.\n");

scanf(" %f ", &libry.value);

printf("%s, %s: %p.2f \n", libry.title, libry.autor,

libry.value);

printf("%s: \" %s \" \(%p.2f\)\n", libry.author,

libry.title, libry.value);

}

Вот образец работы программы:

Введите, пожалуйста, название книги.

Искусство программирования для ЭВМ

Теперь введите фамилию автора.

Д. Кнут

Теперь введите цену.

5р.67

Искусство программирования для ЭВМ, Д. Кнут: 5р.67

Д. Кнут: "Искусство программирования для ЭВМ" (5р. 67)

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

1. Как устанавливать формат или "шаблон" для структуры.

2. Как объявлять переменную, соответствующую этому шаблону.

3. Как осуществлять доступ к отдельным компонентам структурной переменной.

УСТАНОВКА СТРУКТУРНОГО ШАБЛОНА

Далее Содержание

Структурный шаблон является основной схемой, описывающей как собирается структура. Наш шаблон выглядел бы так:

struct book {

char title [MAXTIT];

char author [MAXAUT];

float value;

};

Этот шаблoн описывает структуру, составленную из двух символьных массивов и одной переменной типа tloat. Давайте рассмотрим его детально.

Первым стоит ключевое слово struct; оно определяет, что все, что стоит за ним, является структурой. Далее следует необязательный "тег" (имя типа структуры) - слово book, являющееся сокращенной меткой, которую мы можем использовать позже для ссылки на эту структуру. Поэтому где-нибудь позже у нас будет описание:

struct book libry;

которое объявляет libry структурой типа book.

Далее у нас есть список "элементов" структуры, заключенный в парные фигурные скобки. Каждый элемент определяется своим собственным описанием. Например, элемент title является символьным массивом, состоящим из MAXTIT-элементов. Как мы уже отмечали, элементы могут быть данными любого типа, включая другие структуры! И наконец, мы ставим точку с запятой, завершающую определение шаблона.

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

struct book dickens;

и эта функция должна иметь переменную dickens, которая следует за нашим шаблоном.

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

ОПРЕДЕЛЕНИЕ СТРУКТУРНЫХ ПЕРЕМЕННЫХ

Далее Содержание

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

struct book libry;

На основании этого оператора компилятор создаст переменную libry. Согласно плану, устанопленному шаблоном book, он выделяет память для символьного массива, состоящего из MAXTIT-элементов, для символьного массива из MAXAUT-элемсентов и для переменной типа float. Эта память объединяется под именем libry. (В следующем разделе мы расскажем, как ее "разъединить", если понадобится.)

РИС. 14.1. Распределение памяти для структуры.

В этом описании struct book играет ту же роль, что и int или float в своих описаниях. Например, мы могли бы описать две переменные типа struct book или даже указатель на этот тип структуры:

struct book doyle panshin, *ptbook;

Каждая структурная переменная, doyle и panshin, имела бы части title, author и value. Указатель ptbook мог бы ссылаться на doyle, panshin или любую другую book-структуру. Для компьютера оператор нашей программы

struct book libry;

является сокращенной записью

struct book {

char title [MAXTIT];

char author [MAXAUT];

float value;

} libry; /* присоединяет имя переменной к шаблону */

Другими словами, процесс определения структурного шаблона и процесс определения структурной переменной можно объединить в один этап. Объединение шаблона и определений переменных является именно тем случаем, когда не нужно использовать имя типа структуры:

struct { /* без имени типа структуры */

char title [MAXTIT];

char author [MAXAUT];

float value;

} libry;

Форма с именем типа структуры удобнее, если вы используете структурный шаблон более одного раза.

Есть один аспект определения структурной переменной, который не нашел отражения в нашем примере - инициализация. Теперь мы хотим заняться этим вопросом.

Инициализация структуры

Далее Содержание

Мы видели, как инициализируются переменные и массивы:

int count = 0;

static int fibo[ ]={0, 1, 1, 2, 3, 5, 8};

Можно ли инициализировать и структурную переменную? Да, если структурная переменная будет внешней или статической. Здесь следует иметь в виду, что принадлежность структурной переменной к внешнему типу зависит от того, где определена переменная, а не где определен шаблон. В нашем примере шаблон book является внешним, а переменная libry - внутренней, так как она определена внутри функции и по умолчанию располагается в классе автоматической памяти. Предположим, мы создали такое описание:

static struct book libry;

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

static struct book libry={"Пират и девица",

"Рене Вивот",

1р.95 } ;

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

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

ДОСТУП К ЭЛЕМЕНТАМ СТРУКТУРЫ

Далее Содержание

Структура является разновидностью супермассива, в котором один элемент может быть массивом типа char, следующий - float и еще один int. Обычно можно обращаться к отдельным элементам массива, используя индекс. Как это сделать для отдельных элементов структуры? Для этого мы используем символ ".", обозначающий операцию получения элемента структуры. Например, libry .value является элементом value структуры libry. Можно применять libry.value точно так же, как вы использовали бы любую другую переменную типа float. Можно применять и libry.title точно-так же, как массив типа char. Поэтому мы могли бы использовать выражения, подобные

gets(libry.title)

и

scanf(" %f ", &libry.value);

В сущности .title, .author и .value играют роль индексов для структуры book.

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

struct book spiro; gerald;

gets (spiro.title);

gets (gerald.title);

.title ссылается на первый элемент структуры book.

Посмотрите, как в самой первой программе мы печатали содержимое структурной переменной libry в двух различных форматах; она демонстрирует нам возможность использования элементов структуры.

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

МАССИВЫ СТРУКТУР

Далее Содержание

Настроим нашу программу инвентаризации на обработку, если потребуется, двух или трех (или, может быть, даже большего числа) книг. Очевидно, каждую книгу можно описать структурной переменной типа book. Для описания двух книг нам нужны две такие переменные и т. д. Для обработки нескольких книг потребуется массив таких структур, и мы его создали в программе, показанной на рис. 14.2.

/* инвентаризация большого количества книг */

#include <stdio.h>

#define MAXTIT 40

#define MAXAUT 40

#define MAXBKS 100 /* максимальное количество книг */

#define STOP " " /* нулевая строка прекращает ввод */

struct book { /* создание шаблона типа book */

char title [MAXTIT];

char author [MAXAUT];

float value; };

main ( )

{

struct book libry[MAXBKS]; /* массив структур типа book */

int count = 0;

int index;

printf("Введите, пожалуйста, название книги.\n");

printf(" Нажмите клавишу [ввод] в начале строки для останова.\n");

while(strcmp(gets(libry [count].title), STOP) != 0 &&

count < MAXBKS)

{ printf("Введите теперь фамилию автора.\n");

gets(libry [count].author);

printf("Введите теперь цену.\n");

scanf(" %f", & libry [count++].value);

while(getchar()!='n'); /* очистите строку ввода */

if(counts < MAXBKS)

printf("Введите название следующей книги.\n");

} printf ("Вот список ваших книг: \n");

for(index = 0; index < count; index++)

printf("%s, %s: %p.2f\n", libry [index].title, libry[index].author,

libry[index].value);

}

РИC. 14.2. Программа инвентаризации большого количества книг.

Вот пример работы программы:

Введите, пожалуйста, название книги.

Нажмите клавишу [ввод] в начале строки для останова.

Искусство программирования

Введите теперь фамилию автора. Д.Кнут

Введите теперь цену.

5р.67

Введите название следующей книги.

... еще вводы...

Вот список ваших книг:

Искуство программирования для ЭВМ, Д.Кнут: 5р.67

ПЛ/1 для программистов, Скотт Р., Сондак Н: 1р.08

Программирование на языке Паскаль, П. Грогоно: 1р.30

Язык Фортран 77, Г. Кантан: 0р.80

Трансляция языков программирования, Ф. Вайнгартен: 0р.75

Язык Эсперанто, М.И. Исаев: 0р.60

Ассемблеры и загрузчики, Д.Баррон: 0р.30

Структурное программирование, У. Дал, Э. Дейкстра, К. Хоор: 1р.11

Операционные системы, Г. Катцан: 2р.25

Параллельные вычислительные системы, Б.А.Головкин: 2р.50

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

Описание массива структур

Далее Содержание

Процесс описания массива структур совершенно аналогичен описанию любого другого типа массива:

struct book libry [MAXBKS];

Этот оператор объявляет libry массивом, состоящим из MAXBKS-элементов. Каждый элемент массива представляет собой структуру типа book. Таким образом, libry[0] является book-структурой, libry[1] - второй book-структурой и т. д. Рис. 14.3 может помочь вам представить это. Имя libry само по себе не является именем структуры; это имя массива, содержащего структуры.

РИС. 14.3. Maccив структур.

Определение элементов массива структур

Далее Содержание

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

libry [0].value value - первый элемент массива

libry [4].title title - пятый элемент массива

Заметим, что индекс массива присоединяется к libry, а не к концу имени:

libry. value[2] /* неправильно */

libry[2].value /* правильно */

Мы используем libry[2].value, потому что libry[2] является именем структурной переменной точно так же, как libry[l] является именем другой структурной переменной, а ранее doyle было именем структурной переменной.

Между прочим, что бы это значило?

libry[2].title[4]

Это был бы пятый элемент элемента title (т. е. title[4]) структуры типа book, описанный третьей структурой (т.e. libry[2]). В нашем примере им был бы символ р. Это означает, что индексы, находящиеся справа от операции ".", относятся к отдельным элементам, в то время как индексы, расположенные слева от операции, относятся к массивам структур.

Теперь покончим с этой программой.

Детализация программы

Далее Содержание

Главное отличие ее от нашей первой программы заключается в том, что теперь создается цикл для считывания названий книг. Мы начинаем цикл с while-условия:

while(strcmp(gets(libry [count].title), STOP) != 0

&& count < MAXBKS)

Выражение gets(libry [count].title) считывает вводимую строку, содержащую название книги. Функция strcmp( ) сравнивает эту строку со STOP, которая является " " , т.e. пустой строкой. Если пользователь нажмет клавишу [ввод] в начале строки, то перепишется пустая строка и цикл закончится. Мы также должны проверять, не превысило ли число считанных на текущий момент книг предельного размера массива.

В программе есть странная строка while(getchar ( ) ! = '\n'); /* очистить строку ввода */

Она включена для того, чтобы использовать особенность функции scanf( ), которая игнорирует символы пробела и новой строки. Когда вы отвечаете на запрос об элементе value в структуре book, то вводите что-нибудь вроде

12.50 [ввод]

При этом передается последовательность символов

12.50\n

Функция scanf( ) собирает символы 1, 2, . , 5, 0, но опускает символ \n, стоящий там, и ожидает, что следом придет еще какой-нибудь оператор чтения. Если пропустить нашу странную строку, то следующим оператором чтения будет gets(libry [count].title) в операторе управления циклом. Он прочел бы оставшийся символ новой строки как первый символ, и программа решила бы, что мы послали сигнал останова. Поэтому мы и вставили такую странную строку. Если вы поняли это, то увидите, что она "проглатывает" символы до тех пор, пока не найдет и не получит символ новой строки. Функция ничего не делает с данным символом, только принимает его от устройства ввода. Это приводит к тому, что функция gets( ) снова начинает работать. Вернемся теперь к изучению структур.

ВЛОЖЕННЫЕ СТРУКТУРЫ

Далее Содержание

Иногда бывает удобно, чтобы одна структура содержалась или была "вложена" в другую. Например, Шалала Пироски строит структуру, содержащую информацию о ее друзьях. Один элемент структуры - это, конечно, имя друга. Однако имя можно представить самой структурой с разными элементами для имени и фамилии. На рис. 14.4 приведен сокращенный пример деятельности Шалалы.

/* пример вложенной структуры */

#define LEN 20

#define M1 "Спасибо за прекрасный вечер,"

#define M2 "Вы, конечно, правы, что"

#define M3 " -своеобразный парень. Мы должны собраться"

#define М4 " отведать очень вкусный"

#define M5 "и немного повеселиться."

struct names { /*первый структурный шаблон */

char first[LEN];

char last[LEN], };

struct guy { /* второй шаблон */

struct names handle; /* вложенная структура */

char favfood[LEN];

char job[LEN];

float income;

};

main( ) {

static struct guy fellow = { /*инициализация переменной */

{" Франко," " Уотэл"},

" баклажан",

" вязальщик половиков",

15435.00 };

printf("Дорогой %s, \n \n," fellow.handle.first);

printf(" %s %s.\n", M1, fellow.handle.first);

printf(" %s %s\n" , M2, fellow.job);

printf(" %s \n" , M3);

printf(" %s %s %s\n\n", M4, fellow.favfood, M5);

printf(" %40s %s \n", " " , " До скорой встречи" );

printf(" %40s %s\n", " ", Шалала");

}

РИС. 14.4. Программа вложенной структуры.

Вот результат работы программы:

Дорогой Франко,

Спасибо за прекрасный вечер, Франко.

Bы, конечно, правы. что вязальщик половиков - своеобразный парень.

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

До скорой встречи,

Шалала

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

struct names handle;

Это означает, что handle является переменной типа struct names. Конечно, файл должен также содержать шаблон для структуры типа names.

Во-вторых, следует рассказать, как мы получаем доступ к элементу вложенной структуры. Нужно дважды использовать операцию "." :

fellow.handle.first = = " Франко";

Мы интерпретируем эту конструкцию, перемещаясь слева направо;

(fellow.handle).first

То есть первым находим элемент fellow, далее элемент handle структуры fellow, а затем его элемент first. Теперь рассмотрим указатели.

УКАЗАТЕЛИ НА СТРУКТУРЫ

Далее Содержание

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

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

/* указатель на структуру */

#define LEN 20 struct names {

char first [LEN];

char last [LEN]; };

struct guy {

struct names handle;

char favfood [LEN];

char job [LEN];

float income; };

main( ) {

static struct guy fellow [2] = {

{ "Франко", "Уотэл" }

"баклажан",

" вязальщик половиков ",

15435.00},

{{"Родней", "Свилбели" },

"лососевый мусс", "декоратор интерьера",

35000.00 } };

struct guy *him; /* ЭТО - - указатель па структуру */

printf("адрес #1: %u #2 : %u\n", &fellow[0],

&fellow[1]);

him = &fellow[0]; /* сообщает указателю, на что ссылаться */

printf("указатель #1: %u #2: %u \n ", him, him + 1);

printf("him -> доход $ %.2f: (*him).доход $ %.2f \n",

him -> доход, (*him).доход);

him++; /* указывает на следующую структуру */

printf("him -> favfood is %s : him -> names.last is %s\n",

him-> favfood, him -> handle.last);}

РИС. 14.5. Программа с использованием указателя на структуру.

Вот, пожалуйста, ее выход:

адрес #1: 12 #2: 96

указатель #1: 12 #2: 96

him -> доход $15435.00: (*him).доход $15435.00

him -> favfood лососевый мусс: him -> names.last

- Свилбели

Сначала посмотрим, как мы создали указатель на структуру guy. Затем научимся определять отдельные элементы структуры при помощи указателей.

Описание и инициализация указателя на структуру

Далее Содержание

Вот самое простое описание, какое только может быть:

struct guy *him;

Первым стоит ключевое слово struct, затем слово guy, являющееся именем структурного шаблона, далее * и за нею имя указателя. Синтаксис тот же, как для описаний других указателей, которые мы видели.

Теперь можно создать указатель him для ссылок на любые структуры типа guy. Мы инициализируем him, заставляя его ссылаться нa fellow[0]; заметим, что мы используем операцию получения адреса:

him = &fellow[0];

Первые две выведенные строки показывают результат этого присваивания. Сравнивая две строки, мы видим, что him ссылается на fellow[0], a him+1 - на fellow[l]. Заметим, что добавление 1 к him прибавляет 84 к адресу. Это происходит потому, что каждая guy-структура занимает 84 байта памяти: первое имя - 20, последнее имя - 20, favfood - 20, job - 20 и income - 4 байта (размер элемента типа float в нашей системе).

Доступ к элементу структуры при помощи указателя

Далее Содержание

him ссылается на структуру fellow[0]. Каким образом можно использовать him для получения значения элемента структуры fellow[0]? Третья выведенная строка даст для этого два способа.

Первый способ, наиболее общий, использует новую операцию ->. Она заключается в вводе дефиса (-) и следующего за ним символа "больше чем" (>). Пример помогает понять смысл сказанного:

him -> income - это fellow[0].income,

если him = &fellow[0]

Другими словами, структурный указатель, за которым следует операция ->, работает так же, как имя структуры с последующей операцией ".". (Мы не можем сказать him.income, потому что him не является именем структуры.)

Очень важно отметить, что him-указатель, а him - > income - элемент структуры, на которую делается ссылка. Таким образом, в этом случае him - > income является переменной типа float.

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

если him == &fellow[0], то *him == fellow[0]. Это так, поскольку & и * - взаимообратные операции. Следовательно, после подстановки

fellow[0].income == (*him).income

Круглые скобки необходимы, поскольку операция "." имеет приоритет выше, чем *.

Отсюда можно сделать вывод, что если him является указателем на структуру fellow[0], то следующие обозначения эквивалентны:

fellow[0].income == (*him).income == him->income

Давайте теперь посмотрим, как взаимодействуют структуры и функции.

Резюме: операции над структурами и объединениями

Эта операция используется с именем структуры или объединения для определения элемента этой структуры или объединения. Если name является именем структуры, a member - элементом, определенным структурным шаблоном, то name.member обозначает этот элемент структуры. Операция получения элемента может использоваться таким же образом для объединений.

Примеры

struct {

int code;

float cost;

} item;

item.code = 1265;

Данный оператор присваивает значение элементу code структуры item.

II. ОПЕРАЦИЯ КОСВЕННОГО ПОЛУЧЕНИЯ ЭЛЕМЕНТА: ->

Эта операция используется с указателем на структуру или объединение для определения элемента структуры или объединения. Предположим, что ptrstr является указателем на структуру и что member элемент, определенный структурным шаблоном. Тогда

ptrstr -> member

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

Пример

struct {

int code

float cost;

} item, *ptrst;

ptrst = &item;

ptrst -> code = 3451;

Операторы присваивают значение элементу code структуры item. Следующие три выражения эквивалентны:

ptrst->code item.code (*ptrst).code

ПЕРЕДАЧА ИНФОРМАЦИИ О СТРУКТУРАХ ФУНКЦИЯМ

Далее Содержание

Вспомним, что аргументы функции передают значения в функцию. Каждое значение является либо числом типа int или float, либо ASCII-кодом или адресом. Структура гораздо сложнее, чем отдельная переменная, поэтому неудивительно, что саму структуру нельзя использовать в качестве аргумента функции. (Это ограничение снято в некоторых новых рeализациях.) Однако есть способы ввести информацию о структуре внутрь функции. Рассмотрим три способа (на самом деле два с вариациями).

Использование элементов структуры

Далее Содержание

Поскольку элемент структуры является переменной с единственным значением (т.е. типа int или одного из его "родственников" - char, float, double или указатель), он может быть передан как аргумент функции. Простая программа финансовых расчетов на рис. 14.6, которая прибавляет взнос клиента к его счету, иллюстрирует этот способ. Заметим, между прочим, что мы объединили определение шаблона, описание переменной и инициализацию в один оператор.

/* передача элементов структуры как аргументов функции */

struct funds {

char *bank;

float bankfund;

char *save;

float savefund; }

stan = { " Банк синьора Помидора",

1023.43,

" Сбережения и займы Снупи",

4239.87 };

main( )

{

float total, sum( );

extern struct funds stan; /* необязательное описание */

printf("У Стэна всего %.2f долл.\n", sum(stan.bankfund,

stan.savefund));

}

/* складывает два числа типа float */

float sum(x, у);

float x, у;

{ return( x + y); }

РИС. 14.6. Программа, передающая функции аргументы, являющиеся элементами структуры.

Результат выполнения этой программы:

У Стэна всего 5263.30 долл.

Вот это да, она работает. Заметим, что функция sum( ) "не знает", или же си безразлично, являются ли элементами структуры фактические аргументы; она только "требует", чтобы они имели тип float.

Конечно, если вы хотите, чтобы программа воздействовала на значение элемента в вызывающей программе, можно передать ей адрес этого элемента:

modify(&stan.bank fund);

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

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

Использование адреса структуры

Далее Содержание

Мы будем решать ту же самую задачу, что и прежде, но при этом использовать адрес структуры в качестве аргумента. Это хорошо, поскольку адрес представляет собой только одно число. Так как функция должна работать со структурой funds, она тоже должна использовать шаблон funds. См. рис. 14.7.

/* передача адреса структуры в функцию */

struct funds {

char *bank;

float bankfund;

char *save;

float savefund;

} stan = {

"Банк синьора Помидора" ,

1023.43,

" Сбережения и займы Снупи" ,

4239.87

};

main( )

{

float total, sum( );

printf(" У Стэна всего %.2f долл.\n", sum(&stan) );

}

float sum (money)

struct funds *money;

}

return( money-> bankfund + money-> savefund);

}

PИC. 14.7. Программа, передающая функции адрес структуры. Эта программа тоже выдает

У Стэна всего 5263.30 долл.

Функция sum( ) имеет указатель (money) на структуру fund. Передача адреса &stan в функцию заставляет указатель money ссылаться на структуру stan. Затем используем операцию - > для получения значений элементов stan.bankfund и stan.savefund.

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

Наш следующий способ применим к массивам структур и является вариантом данного способа.

Использование массива

Далее Содержание

Предположим, у нас есть массив структур. Имя массива является синонимом его адреса, поэтому его можно передать функции. С другой стороны, функции будет необходим доступ к структурному шаблону. Чтобы показать, как такая программа работает (рис. 14.8), мы расширим нашу программу таким образом, чтобы она обслуживала двух человек, а мы, следовательно, имели бы массив двух структур funds.

/* передача массива структур в функцию */

struct funds {

char *bank;

float bankfund;

char *save;

float savefund; }

jones[2] ={

{ " Банк синьора Помидора" ,

1023.43,

" Сбережения и займы Снупи" ,

4239.87 },

{ " Банк Честного Джека",

976.57,

"Накопления по предварительному плану",

1760.13 } };

main( )

{

float total, sum( );

printf("Джонсы имеют всего %.2f долл.\n", sum(jones));

}

float sum(money);

struct funds *money;

{

float total;

int i;

for( i = 0, total = 0; i < 2; i++, money++ )

total += money- > bankfund + money -> savefund;

return(total);

}

РИС. 14. 8. Программа, передающая функции массив структур.

Программа выдает

Джонсы имеют всего 8000.00 долл.

(Что за круглая сумма! Можно подумать, что эти цифры взяты с потолка.) Имя массива jones является указателем на массив. В частности, оно ссылается на первый элемент массива, который является структурой jones[0]. Таким образом, в начале указатель money за дается через

money = &jones[0];

Затем использование операции - > позволяет нам добавить два вклада для первого Джонса. Это действительно очень похоже на последний пример. Далее, цикл for увеличивает указатель money на 1. Теперь он ссылается на следующую структуру, jones[1], и остаток вкладов может быть добавлен к total.

Вот два основных замечания:

1. Имя массива можно использовать для передачи в функцию указателя на первую структуру в массиве.

2. Затем можно использовать арифметическую операцию над указателем, чтобы передвигать его на последующие структуры в массиве. Заметим, что вызов функции

sum(&jones[0])

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

СТРУКТУРЫ: ЧТО ДАЛЬШЕ?

Далее Содержание

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

Эти типы имеют такие названия, как очереди, двоичные деревья, неупорядоченные массивы, рандомизированные таблицы и графы. Многие из этих типов создаются из "связанных" структур. Обычно каждая структура будет содержать один или два типа данных плюс один или два указателя на другие структуры такого же типа. Указатели служат для связи одной структуры с другой и для обеспечения пути, позволяющего вам вести поиск по всей структуре. Например, на рис. 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 - КРАТКИЙ ОБЗОР

Далее Содержание

Функция 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 есть такое определение:

typedef short TWOBYTE;

Используйте TWOBYTE в ваших программах для переменных типа short, которые должны быть 16-разрядными. Тогда если вы перемешаете программу туда, где необходимо использовать тип int, то следует только изменить одно определение в вашем файле директивы #include:

typedef int TWOBYTE;

Это пример того, что делает язык Си столь мобильным. При использовании typedеf следует иметь в виду, что он не создаст новых типов, он только создает удобные метки.

ПРИЧУДЛИВЫЕ ОПИСАНИЯ

Язык Си позволяет вам создавать сложные формы данных. Обычно мы придерживаемся более простых форм, но считаем споим долгом указать ни потенциальные возможности языка. При создании описания мы используем имя (или "идентификатор"), которое можно изменять при помощи модификатора:

Модификатор

значение

*

указатель

( )

функция

[ ]

массив

Язык Си позволяет использовать одновременно более одного модификатора, что даст возможность создавать множество типов:

int board[8] [8]; /* массив массивов типа int */

int **ptr; /* указатель на указатель на тип int */

int *risks[10]; /* 10-элементный массив указателей на тип int */

int (*wisks) [10]; /* указатель на 10-элемснтный массив типа int */

int *oof[3] [4]: /* 3-элементныи массив указателей на 4-элементный

массив типа int */

int (*uuf) [3][4]; /* указатель на массив 3х4 типа int */

Для распутывания этих описаний нужно понять, в каком порядке следует применять модификаторы. Три правила помогут вам справиться с этим.

1. Чем ближе кодификатор стоит к идентификатору, тем выше его приоритет.

2. Модификатиры [ ] и ( ) имеют приоритет выше, чем *.

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

Давайте применим эти правила к описанию int *oof[3] [4];

* и [3] примыкают к oof и имеют более высокий приоритет, чем [4] (правило 1). [3] имеет приоритет более высокий, чем * (правило 2). Следовательно, oof является 3-элементным массивом (перпый МОДИФИКАТОР) указателей (второй модификатор) на 4-элементный массив (третий модификатор) типа int (описание типа).

В описании

int (*uuf)[3][4];

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

char *fump( ); /* функция, возвращающая указатель на тип char */

char (*frump) ( ); /* указатель на функцию, возвращающую тип char */

char *flump ( ) [3] /* функция, возвращающая указатель на 3-элементный

массив типа char */

char *flimp[3] ( ) /* 3-элементный массив указателей на функцию, которая

возвращает тип char */

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

Язык Си со структурами , объединениями и typedef дает нам средства для эффективной и мобильной обработки данных.

ЧТО ВЫ ДОЛЖНЫ БЫЛИ УЗНАТЬ В ЭТОЙ ГЛАВЕ

Далее Содержание

Что такое структурный шаблон, и как его определять

Что такое имя структуры и как оно используется

Как определить структурную переменную: struct car honda;

Как обратиться к элементу структуры: honda.mpg

Как обратиться к указателю на структуру: struct car *ptcar;

Как обратиться к элементу при помощи указателя: ptcar->mpg

Как передать в функцию элемент структуры: eval(honda.mpg)

Как сообщить функции о структуре: rate(&honda)

Как создать вложенную структуру

Как обратиться к элементу вложенной структуры: honda.civic.cost

Как создавать и использовать массивы структур: struct car gm[5];

Как создать объединение: подобно структуре

Как использовать typedef: typedef struct car CRATE;

ВОПРОСЫ И ОТВЕТЫ

Далее Содержание

Вопросы

1. Что неправильно в этом шаблоне?

structure {

char itible;

int num [20];

char *togs;

};

2. Вот фрагмент программы; что она напечатает?

struct house {

float sqft;

int rooms;

int stories;

char *address; };

main ( ) {

static struct house fruzt = { 1560.0, 6, 1, " 22 Spiffo Road";

struct house *sign;

sign = &fruzt;

printf(" %d %d\n" , fruzt.rooms, sign-> stories);

printf(" %s\n", frurt.address);

prinlf(" %c %c \n" sign- >address[3], fruzt.address[4]);

}

3. Придумайте структурный шаблон, который будет содержать название месяца, трехбуквенную аббревиатуру месяца, количество дней в месяце и номер месяца.

4. Определите массив, состоящий из двенадцати структур того же типа, что и в вопросе 3, и инициализируйте его для невисокосного года.

5. Напишите функцию, которая получает номер месяца, а возвращает общее число дней года вплоть до этого месяца. Считайте, что структурный шаблон и массив из вопросов 3 и 4 описаны как внешние.

6. Взяв за основу нижеследующую функцию typedet, опишите 10-элементный массив указанной структуры. Затем, используя присваивание отдельного элемента попытайтесь описать третьим элементом'массива линзу Ремаркатара с фокусным расстоянием 500 мм и апертурой f / 2.0.

typedef struct { /* описатель линзы */

float foclen; /* фокусное расстояние, мм */

float fstop; /* апертура */

char *brand; /* фирменная марка */ } LENS;

Ответы:

1. Должно быть ключевое слово struct, а не structure. Шаблон требует либо имени структуры перед открывающей скобкой или имени переменной после закрывающей скобки. Кроме того, точка с запятой должна стоять после *togs и в конце шаблона.

2.

6 1

22 Spiffo Road S p

Элемент fruzt.address является символьной строкой, а fruzt.address[4] является пятым элементом этого массива.

3.

struct month {

char name[10]; /* или char *name; */

char abbrev[4]; /* или char *abbrev; */

int days;

int monumb; };

4.

struct month months [12] = {

{" Январь" , " Янв" , 31, 1} , {" Февраль" , " Фев" , 28, 2} ,

и т. л. {"Декабрь", "Дек" , 31, 12}

5.

days(monlh);

inl month;

{

int index, tolal;

if(month < 1 || month > 12)

return (-1); /* признак ошибки */

else

for(index = 0, total = 0; index < month; index++)

total + = months [index].days;

return (total);}

Заметим, что index содержит номер месяца, уменьшенный на единицу, так как массивы начинаются с индекса 0; следовательно, мы используем выражение index < month вместо index <= month.

6.

ЛИНЗА tubby [10];

tubby [2].foclen = 300.0;

tubby [2].fstop = 2.0;

tubby [2].brand = "Рсмаркатар";

УПРАЖНЕНИЯ

1. Переделайте вопрос 5, используя в качестве аргумента написанное буквами название месяца вместо номера месяца. [Не забывайте о функции strcmp( ).]

2. Напишите программу, которая запрашивает у пользователя день, месяц и год. Месяц может обозначаться номером, названием месяца или его аббревиатурой. После работы программа выдает общее количество дней в году вплоть до данного дня.

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

[Содержание] [Вверх]

Язык Си

Структуры и другие типы данных

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

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

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

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

int getword(char *, int);

struct key *binsearch(char *, struct key *, int);

/* Подсчет ключевых слов Си, версия с указателями */

main()

{

char word[MAXWORD];

struct key *p;

while (getword(word, MAXWORD) != EOF)

if (isalpha(word[0]))

if ((p = binsearch(word, keytab, NKEYS)) != NULL)

p->count++;

for (p = keytab; p < keytab + NKEYS; p++)

if (p->count > 0)

printf("%4d %s\n", p->count, p->word);

return 0;

}

/* binsearch: поиск слова в массиве tab */

struct key *binsearch(char *word, struct key *tab, int n)

{

int cond;

struct key *low = &tab[0];

struct key *high = &tab[n];

struct key *mid;

while (low < high) {

mid = low + (high - low) / 2;

if ((cond = strcmp(word, mid->word)) < 0)

high = mid;

else if (cond > 0)

low = mid + 1;

else

return mid;

}

return NULL;

}

Некоторые детали этой программы требуют пояснений. Во-первых, описание функции binsearch должно отражать тот факт, что она возвращает указатель на struct key, а не целое число; это объявлено как в прототипе, так и в определении функции. Если binsearch находит слово, то она выдает указатель на него, в противном случае она возвращает NULL. Во-вторых, доступ к элементам keytab в нашей программе осуществляется через указатели. Это потребовало значительных изменений в binsearch. Инициализаторами для low и high теперь служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы

mid = (low + high) / 2 /* НЕВЕРНО */

не годится, поскольку указатели нельзя складывать. Однако к ним можно применить операцию вычитания, и так как high - low есть число элементов, присваивание

mid = low + (high - low) / 2

превратит mid в указатель на элемент, лежащий посередине между low и high.

Самое важное при переходе на новый вариант программы — сделать так, чтобы не генерировались неправильные указатели и не было попыток обратиться за пределы массива. Проблема в том, что и &tab[-1], и &tab[n] находятся вне границ массива. Первый адрес определенно неверен, нельзя также осуществить доступ и по второму адресу. По правилам языка, однако, гарантируется, что адрес ячейки памяти, следующей сразу за концом массива (т.е. &tab[n]), в арифметике с указателями воспринимается правильно.

В главной программе main мы написали

for (p = keytab; p < keytab + NKEYS; p++)

Если p — это указатель на структуру, то при выполнении операций с p учитывается размер структуры. Поэтому p++ увеличит p на такую величину, чтобы перейти к следующему структурному элементу массива, а проверка условия вовремя остановит цикл.

Не следует, однако, полагать, что размер структуры равен сумме размеров ее элементов. Вследствие выравнивания объектов разной длины в структуре могут появляться безымянные «дыры». Например, если переменная типа char занимает один байт, а int — четыре байта, то для структуры

struct {

char c;

int i;

};

может потребоваться восемь байтов, а не пять. Оператор sizeof возвращает правильное значение.

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

struct key *binsearch(char *word, struct key *tab, int n)

то «высмотреть» имя функции оказывается совсем не просто. В подобных случаях иногда пишут так:

struct key *

binsearch(char *word, struct key *tab, int n)

Какой форме отдать предпочтение — дело вкуса. Выберите ту, которая больше всего вам нравится, и придерживайтесь ее.

6.5. Структуры со ссылками на себя

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

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

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

указатель на текст слова;

счетчик числа встречаемости;

указатель на левый дочерний узел;

указатель на правый дочерний узел.

У каждого узла может быть один или два потомка, или узел вообще может не иметь потомков.

Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое — слова, которые больше него. Вот как выглядит дерево, построенное для фразы «now is the time for all good men to come to the aid of their party» («настало время всем добрым людям помочь своей партии»), по завершении процесса, в котором для каждого нового слова в него добавлялся новый узел:

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

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

struct tnode { /* узел дерева */

char *word; /* указатель на текст */

int count; /* число вхождений */

struct tnode *left; /* левый потомок */

struct tnode *right; /* правый потомок */

};

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

struct tnode *left;

объявляет left как указатель на tnode, а не сам tnode.

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

struct t {

...

struct s *p; /* p указывает на s */

};

struct s {

...

struct t *q; /* q указывает на t */

};

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

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *);

void treeprint(struct tnode *);

int getword(char *, int);

/* Подсчет частоты встречаемости слов */

main()

{

struct tnode *root;

char word[MAXWORD];

root = NULL;

while (getword(word, MAXWORD) != EOF)

if (isalpha(word[0]))

root = addtree(root, word);

treeprint(root);

return 0;

}

Функция addtree рекурсивна. Первое слово функция main помещает в корень дерева. Каждое вновь поступившее слово сравнивается со словом узла и «погружается» или в левое, или в правое поддерево с помощью рекурсивного обращения к addtree. Через некоторое время это слово обязательно либо совпадет с каким-нибудь из имеющихся в дереве слов (в этом случае к счетчику будет добавлена 1), либо программа встретит пустую позицию, что послужит сигналом для создания нового узла и добавления его к дереву. При создании нового узла addtree возвращает указатель на него, который вставляется в узел родителя.

struct tnode *talloc(void);

char *strdup(char *);

/* addtree: добавляет узел со словом w

в узел p или ниже его */

struct tnode *addtree(struct tnode *p, char *w)

{

int cond;

if (p == NULL) { /* слово встречается впервые */

p = talloc(); /* создается новый узел */

p->word = strdup(w);

p->count = 1;

p->left = p->right = NULL;

} else if ((cond = strcmp(w, p->word)) == 0)

p->count++; /* это слово уже встречалось */

else if (cond < 0) /* переходим к левому поддереву */

p->left = addtree(p->left, w);

else /* переходим в правое поддерево */

p->right = addtree(p->right, w);

return p;

}

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

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

/* treeprint: упорядоченная печать дерева p */

void treeprint(struct tnode *p)

{

if (p != NULL) {

treeprint(p->left);

printf("%4d %s\n", p->count, p->word);

treeprint(p->right);

}

}

Если вы не уверены, что досконально разобрались в том, как работает рекурсия, «проиграйте» действия treeprint на дереве, приведенном выше.

Практическое замечание: если дерево «несбалансировано» (что бывает, когда слова поступают не в случайном порядке), то время работы программы может сильно возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на вычисления будут такими же, как при линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем.

Прежде чем завершить обсуждение этого примера, сделаем краткое отступление от темы и поговорим о механизме запроса памяти. Очевидно, хотелось бы иметь всего лишь одну функцию, выделяющую память, даже если эта память предназначается для разного рода объектов. Но если одна и та же функция обеспечивает память, скажем, и для указателей на char, и для указателей на struct tnode, то возникают два вопроса. Первый: как справиться с требованием большинства машин, в которых объекты определенного типа должны быть выровнены (например, числа типа int часто должны размещаться, начиная с четных адресов)? И второе: как объявить функцию для распределения памяти, которая вынуждена в качестве результата возвращать указатели разных типов?

Вообще говоря, требования, касающиеся выравнивания, можно легко выполнить за счет некоторого перерасхода памяти. Однако для этого возвращаемый указатель должен быть таким, чтобы удовлетворялись любые ограничения, связанные с выравниванием. Функция alloc, описанная в главе 5, не гарантирует никакого выравнивания, поэтому мы будем пользоваться стандартной библиотечной функцией malloc, которая это делает. В главе 8 мы покажем один из способов ее реализации.

Вопрос об объявлении типа таких функций, как malloc, является камнем преткновения в любом языке с жесткой проверкой типов. В Си вопрос решается естественным образом: malloc объявляется как функция, которая возвращает указатель на void. Полученный указатель затем явно преобразуется к желаемому типу 1. Описания malloc и связанных с ней функций находятся в сандартном заголовочном файле <stdlib.h>. Таким образом, функцию talloc можно записать так:

#include <stdlib.h>

/* talloc: создает tnode */

struct tnode *talloc(void)

{

return (struct tnode *)malloc(sizeof(struct tnode));

}

Функция strdup просто копирует строку, указанную в аргументе, в место, полученное с помощью malloc:

char *strdup(char *s) /* делает дубликат s */

{

char *p;

p = (char *)malloc(strlen(s) + 1); /* +1 для '\0' */

if (p != NULL)

strcpy(p, s);

return p;

}

лава 6. Структуры

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

Традиционный пример структуры — строка платежной ведомости. Она содержит такие сведения о служащем, как его полное имя, адрес, номер карточки социального страхования, зарплата и т.д. Некоторые из этих характеристик сами могут быть структурами: например, полное имя состоит из нескольких компонент (фамилии, имени и отчества); аналогично адрес, и даже зарплата. Другой пример (более типичный для Си) — из области графики: точка есть пара координат, прямоугольник определяется парой точек и т.д.

Главные изменения, внесенные стандартом ANSI в отношении структур, — это введение для них оператора присваивания. Структуры могут копироваться, над ними могут выполняться операции присваивания, их можно передавать функциям в качестве аргументов, а функции могут возвращать их в качестве результатов. В большинстве компиляторов уже давно реализованы эти возможности, но теперь они точно оговорены стандартом. Для автоматических структур и массивов теперь также допускается инициализация.

6.1. Основные сведения о структурах

Сконструируем несколько графических структур. В качестве основного объекта выступает точка с координатами x и y целого типа.

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

struct point {

int x;

int y;

};

Объявление структуры начинается с ключевого слова struct и содержит список объявлений, заключенный в фигурные скобки. За словом struct может следовать имя, называемое тегом структуры (в нашем случае — point). Тег дает название структуре данного вида и далее может служить кратким обозначением той части объявления, которая заключена в фигурные скобки.

Перечисленные в структуре переменные называются членами (members). Имена членов структур и тегов без каких-либо коллизий могут совпадать с именами обычных переменных (т.е. не являющихся элементами структуры), так как они всегда различимы по контексту. Более того, одни и те же имена членов могут встречаться в разных структурах, хотя, если следовать хорошему стилю программирования, лучше одинаковые имена давать только близким по смыслу объектам.

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

struct { ... } x, y, z;

с точки зрения синтаксиса аналогично выражению

int x, y, z;

в том смысле, что и то и другое объявляет x, y и z переменными указанного типа; и то и другое приведет к выделению памяти соответствующего размера.

Объявление структуры, не содержащее списка переменных, не резервирует памяти; оно просто описывает шаблон, или образец структуры. Однако, если структура имеет тег, то этим тегом можно далее пользоваться при определении структурных объектов. Например, с помощью заданного выше описания структуры point строка

struct point pt;

определяет структурную переменную pt типа struct point. Структурную переменную при ее определении можно инициализировать, формируя список инициализаторов ее членов в виде константных выражений:

struct point maxpt = { 320, 200 };

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

Доступ к отдельному члену структуры осуществляется посредством конструкции вида:

имя-структуры.элемент

Оператор доступа к члену структуры . соединяет имя структуры и имя члена. Чтобы напечатать, например, координаты точки pt, годится следующее обращение к printf:

printf("%d,%d", pt.x, pt.y);

Другой пример: чтобы вычислить расстояние от начала координат (0, 0) до pt, можно написать

double dist, sqrt(double);

dist = sqrt((double)pt.x * pt.x + (double)pt.y * pt.y);

Структуры могут быть вложены друг в друга. Одно из возможных представлений прямоугольника — пара точек на углах одной из его диагоналей:

struct rect {

struct point pt1;

struct point pt2;

};

Структура rect содержит две структуры point. Если мы объявим screen как

struct rect screen;

то

screen.pt1.x

обращается к координате x точки pt1 из screen.

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

Единственно возможные операции над структурами — это их копирование, присваивание, получение адреса с помощью & и осуществление доступа к ее элементам. Копирование и присваивание также включают в себя передачу функциям аргументов и возврат ими значений. Структуры нельзя сравнивать. Инициализировать структуру можно списком константных значений ее элементов; автоматическую структуру также можно инициализировать присваиванием.

Чтобы лучше познакомиться со структурами, напишем несколько функций, манипулирующих точками и прямоугольниками. Возникает вопрос: а как передавать функциям названные объекты? Существует по крайней мере три подхода: передавать компоненты по отдельности, передавать всю структуру целиком и передавать указатель на структуру. Каждый подход имеет свои плюсы и минусы.

Первая функция, makepoint, получает два целых значения и возвращает структуру point:

/* makepoint: формирует точку по компонентам x и y */

struct point makepoint(int x, int y)

{

struct point temp;

temp.x = x;

temp.y = y;

return temp;

}

Заметим: никакого конфликта между именем аргумента и именем члена структуры не возникает; более того, сходство подчеркивает родство обозначаемых ими объектов.

Теперь с помощью makepoint можно выполнять динамическую инициализацию любой структуры или формировать структурные аргументы для той или иной функции:

struct rect screen;

struct point middle;

struct point makepoint(int, int);

screen.pt1 = makepoint(0, 0);

screen.pt2 = makepoint(XMAX, YMAX);

middle = makepoint((screen.pt1.x + screen.pt2.x) / 2,

(screen.pt1.y + screen.pt2.y) / 2);

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

/* addpoint: сложение двух точек */

struct point addpoint(struct point p1, struct point p2)

{

p1.x += p2.x;

p1.y += p2.y;

return p1;

}

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

В качестве другого примера приведем функцию ptinrect, которая проверяет находится ли точка внутри прямоугольника, относительно которого мы принимаем соглашение, что в него входят его левая и нижняя стороны, но не входят верхняя и правая.

/* ptinrect: возвращает 1, если точка p принадлежит

прямоугольнику r, и 0 в противном случае */

int ptinrect(struct point p, struct rect r)

{

return p.x >= r.pt1.x && p.x < r.pt2.x

&& p.y >= r.pt1.y && p.y < r.pt2.y;

}

Здесь предполагается, что прямоугольник представлен в стандартном виде, т.е. координаты точки pt1 меньше соответствующих координат точки pt2. Следующая функция гарантирует получение прямоугольника в каноническом виде.

#define min(a, b) ((a) < (b) ? (a) : (b))

#define max(a, b) ((a) > (b) ? (a) : (b))

/* canonrect: канонизация координат прямоугольника */

struct rect canonrect(struct rect r)

{

struct rect temp;

temp.pt1.x = min(r.pt1.x, r.pt2.x);

temp.pt1.y = min(r.pt1.y, r.pt2.y);

temp.pt2.x = max(r.pt1.x, r.pt2.x);

temp.pt2.y = max(r.pt1.y, r.pt2.y);

return temp;

}

Если функции передается большая структура, то эффективнее передать указатель на нее, а не копировать структуру целиком. Указатели на структуры ничем не отличаются от указателей на обычные переменные. Объявление

struct point *pp;

сообщает, что pp — это указатель на структуру типа struct point. Если pp указывает на структуру point, то *pp — это сама структура, а (*pp).x и (*pp).y — ее элементы. Используя указатель pp, мы могли бы написать

struct point origin, *pp;

pp = &origin;

printf("origin: (%d, %d)\n", (*pp).x, (*pp).y);

Скобки в (*pp).x необходимы, поскольку приоритет оператора . выше, чем приоритет *. Выражение *pp.x будет проинтерпретировано как *(pp.x), что неверно, поскольку pp.x не является указателем.

Указатели на структуры используются весьма часто, поэтому для доступа к элементам была придумана еще одна, более короткая форма записи. Если p — указатель на структуру, то

p -> элемент структуры

есть ее отдельный элемент. (Оператор -> состоит из знака -, за которым сразу следует знак >.) Поэтому printf можно переписать в виде

printf("origin: (%d, %d)\n", pp->x, pp->y);

Операторы . и -> выполняются слева направо. Таким образом, при наличии объявления

struct rect r, *rp = &r;

следующие четыре выражения будут эквивалентны:

r.pt1.x

rp->pt1.x

(r.pt1).x

(rp->pt1).x

Операторы доступа к элементам структуры . и -> вместе с операторами вызова функции () и индексации массива [] занимают самое высокое положение в иерархии приоритетов и выполняются раньше любых других операторов. Например, если задано объявление

struct {

int len;

char *str;

} *p;

то

++p->len

увеличит на 1 значение элемента структуры len, а не указатель p, поскольку в этом выражении как бы неявно присутствуют скобки: ++(p->len). Чтобы изменить порядок выполнения операций, нужны явные скобки. Так, в (++p)->len, прежде чем взять значение len, программа прирастит указатель p. В (p++)->len указатель p увеличивается после того, как будет взято значение len (в последнем случае скобки не обязательны).

По тем же правилам *p->str обозначает содержимое объекта, на который указывает str; *p->str++ прирастит указатель str после получения значения объекта, на который он указывал (как и в выражении *s++); (*p->str)++ увеличит значение объекта, на который указывает str; *p++->str увеличит p после получения того, на что указывает str.

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

Рассмотрим программу, определяющую число вхождений каждого ключевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива строк и счетчики ключвых слов в виде массива целых чисел. Один из возможных вариантов — это иметь два параллельных массива:

char *keyword[NKEYS];

int keycount[NKEYS];

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

char *word;

int count;

Такие пары составляют массив. Объявление

struct key {

char *word;

int count;

} keytab[NKEYS];

объявляет структуру типа key и определяет массив keytab, каждый элемент которого является структурой этого типа и для хранения которого где-то будет выделена память. Это же можно записать и по-другому:

struct key {

char *word;

int count;

};

struct key keytab[NKEYS];

Так как keytab содержит постоянный набор имен, его легче всего сделать внешним массивом и инициализировать один раз в момент определения. Инициализация структур аналогична ранее демонстрировавшимся инициализациям — за определением следует список инициализаторов, заключенный в фигурные скобки:

struct key {

char *word;

int count;

} keytab[] = {

"auto", 0,

"break", 0,

"case", 0,

"char", 0,

"const", 0,

"continue", 0,

"default", 0,

/* . . . */

"unsigned", 0,

"void", 0,

"volatile", 0,

"while", 0

};

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

{"auto", 0},

{"break", 0},

{"case", 0},

...

Однако когда инициализаторы — простые константы или строки символов и все они имеются в наличии, во внутренних скобках нет необходимости. Число элементов массива keytab будет вычислено по количеству инициализаторов, поскольку они представлены полностью, а внутри квадратных скобок [] ничего не задано.

Программа подсчета ключевых слов начинается с определения массива keytab. Функция main читает входные данные, многократно обращаясь к функции getword и получая при каждом ее вызове очередное слово. Каждое слово ищется в массиве keytab. Для этого используется функция бинарного поиска, которую мы написали в главе 3. Список ключевых слов должен быть упорядочен в алфавитном порядке.

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

int getword(char *, int);

int binsearch(char *, struct key *, int);

/* Подсчет ключевых слов Си */

main()

{

int n;

char word[MAXWORD];

while (getword(word, MAXWORD) != EOF)

if (isalpha(word[0]))

if ((n = binsearch(word, keytab, NKEYS)) >= 0)

keytab[n].count++;

for (n = 0; n < NKEYS; n++)

if (keytab[n].count > 0)

printf("%4d %s\n", keytab[n].count, keytab[n].word);

return 0;

}

/* binsearch: поиск слова в массиве tab */

int binsearch(char *word, struct key tab[], int n)

{

int cond;

int low, high, mid;

low = 0;

high = n - 1;

while (low <= high) {

mid = (low + high) / 2;

if ((cond = strcmp(word, tab[mid].word)) < 0)

high = mid - 1;

else if (cond > 0)

low = mid + 1;

else

return mid;

}

return -1;

}

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

Константа NKEYS — это количество ключевых слов в keytab. Хотя мы могли бы подсчитать число таких слов вручную, гораздо легче и безопасней сделать это с помощью машины, особенно если список ключевых слов может быть изменен. Одно из возможных решений — поместить в конец списка инициализаторов пустой указатель (NULL) и затем перебирать в цикле элементы keytab, пока не встретится концевой элемент.

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

размер keytab / размер struct key

В Си имеется унарный оператор sizeof, который работает во время компиляции. Его можно применять для вычисления размера любого объекта. Выражения

sizeof объект

и

sizeof (имя типа)

выдают целые значения, равные размеру указанного значения или типа в байтах. (Строго говоря, sizeof выдает беззнаковое целое, тип которого size_t определен в заголовочном файле <stddef.h>.) Что касается объекта, то это может быть переменная, массив или структура. В качестве имени типа может выступать имя базового типа (int, double, ...) или имя производного типа, например структуры или указателя.

В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размер одного элемента. Указанное вычисление используется в инструкции #define для установки значения NKEYS:

#define NKEYS (sizeof keytab / sizeof(struct key))

Этот же результат можно получить другим способом — поделить размер массива на размер какого-то его конкретного элемента:

#define NKEYS (sizeof keytab / sizeof keytab[0])

Преимущество такого рода записей в том, что их не надо корректировать при изменении типа.

Поскольку препроцессор не обращает внимания на имена типов, оператор sizeof нельзя применять в #if. Но в #define выражение препроцессором не вычисляется, так что предложнная нами запись допустима.

Теперь поговорим о функции getword. Мы написали getword в несколько более общем виде, чем требуется для нашей программы, но она от этого не стала заметно сложнее. Функция getword берет из входного потока следующее «слово». Под словом понимается цепочка букв и цифр, начинающаяся с буквы, или отдельный символ, отличный от символа-разделителя. В случае конца файла функция возвращает EOF, в остальных случаях ее значением является код первого символа слова или сам символ, если это не буква.

/* getword: принимает следующее слово или символ из ввода */

int getword(char *word, int lim)

{

int c, getch(void);

void ungetch(int);

char *w = word;

while (isspace(c = getch()))

;

if (c != EOF)

*w++ = c;

if (!isalpha(c)) {

*w = '\0';

return c;

}

for (; --lim > 0; w++)

if (!isalnum(*w = getch())) {

ungetch(*w);

break;

}

*w = '\0';

return word[0];

}

Функция getword обращается к getch и ungetch, которые мы написали в главе 4. По завершении набора букв и цифр оказывается, что getword взяла лишний символ. Обращение к ungetch позволяет вернуть его назад во входной поток. В getword используется также функции isspace (для пропуска символов-разделителей), isalpha (для идентификации букв) и isalnum (для распознавания букв и цифр). Все они описаны в стандартном заголовочнм файле <ctype.h>.

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

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

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

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

int getword(char *, int);

struct key *binsearch(char *, struct key *, int);

/* Подсчет ключевых слов Си, версия с указателями */

main()

{

char word[MAXWORD];

struct key *p;

while (getword(word, MAXWORD) != EOF)

if (isalpha(word[0]))

if ((p = binsearch(word, keytab, NKEYS)) != NULL)

p->count++;

for (p = keytab; p < keytab + NKEYS; p++)

if (p->count > 0)

printf("%4d %s\n", p->count, p->word);

return 0;

}

/* binsearch: поиск слова в массиве tab */

struct key *binsearch(char *word, struct key *tab, int n)

{

int cond;

struct key *low = &tab[0];

struct key *high = &tab[n];

struct key *mid;

while (low < high) {

mid = low + (high - low) / 2;

if ((cond = strcmp(word, mid->word)) < 0)

high = mid;

else if (cond > 0)

low = mid + 1;

else

return mid;

}

return NULL;

}

Некоторые детали этой программы требуют пояснений. Во-первых, описание функции binsearch должно отражать тот факт, что она возвращает указатель на struct key, а не целое число; это объявлено как в прототипе, так и в определении функции. Если binsearch находит слово, то она выдает указатель на него, в противном случае она возвращает NULL. Во-вторых, доступ к элементам keytab в нашей программе осуществляется через указатели. Это потребовало значительных изменений в binsearch. Инициализаторами для low и high теперь служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы

mid = (low + high) / 2 /* НЕВЕРНО */

не годится, поскольку указатели нельзя складывать. Однако к ним можно применить операцию вычитания, и так как high - low есть число элементов, присваивание

mid = low + (high - low) / 2

превратит mid в указатель на элемент, лежащий посередине между low и high.

Самое важное при переходе на новый вариант программы — сделать так, чтобы не генерировались неправильные указатели и не было попыток обратиться за пределы массива. Проблема в том, что и &tab[-1], и &tab[n] находятся вне границ массива. Первый адрес определенно неверен, нельзя также осуществить доступ и по второму адресу. По правилам языка, однако, гарантируется, что адрес ячейки памяти, следующей сразу за концом массива (т.е. &tab[n]), в арифметике с указателями воспринимается правильно.

В главной программе main мы написали

for (p = keytab; p < keytab + NKEYS; p++)

Если p — это указатель на структуру, то при выполнении операций с p учитывается размер структуры. Поэтому p++ увеличит p на такую величину, чтобы перейти к следующему структурному элементу массива, а проверка условия вовремя остановит цикл.

Не следует, однако, полагать, что размер структуры равен сумме размеров ее элементов. Вследствие выравнивания объектов разной длины в структуре могут появляться безымянные «дыры». Например, если переменная типа char занимает один байт, а int — четыре байта, то для структуры

struct {

char c;

int i;

};

может потребоваться восемь байтов, а не пять. Оператор sizeof возвращает правильное значение.

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

struct key *binsearch(char *word, struct key *tab, int n)

то «высмотреть» имя функции оказывается совсем не просто. В подобных случаях иногда пишут так:

struct key *

binsearch(char *word, struct key *tab, int n)

Какой форме отдать предпочтение — дело вкуса. Выберите ту, которая больше всего вам нравится, и придерживайтесь ее.

netlib.narod.ru

6.5. Структуры со ссылками на себя

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

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

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

указатель на текст слова;

счетчик числа встречаемости;

указатель на левый дочерний узел;

указатель на правый дочерний узел.

У каждого узла может быть один или два потомка, или узел вообще может не иметь потомков.

Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое — слова, которые больше него. Вот как выглядит дерево, построенное для фразы «now is the time for all good men to come to the aid of their party» («настало время всем добрым людям помочь своей партии»), по завершении процесса, в котором для каждого нового слова в него добавлялся новый узел:

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

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

struct tnode { /* узел дерева */

char *word; /* указатель на текст */

int count; /* число вхождений */

struct tnode *left; /* левый потомок */

struct tnode *right; /* правый потомок */

};

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

struct tnode *left;

объявляет left как указатель на tnode, а не сам tnode.

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

struct t {

...

struct s *p; /* p указывает на s */

};

struct s {

...

struct t *q; /* q указывает на t */

};

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

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *);

void treeprint(struct tnode *);

int getword(char *, int);

/* Подсчет частоты встречаемости слов */

main()

{

struct tnode *root;

char word[MAXWORD];

root = NULL;

while (getword(word, MAXWORD) != EOF)

if (isalpha(word[0]))

root = addtree(root, word);

treeprint(root);

return 0;

}

Функция addtree рекурсивна. Первое слово функция main помещает в корень дерева. Каждое вновь поступившее слово сравнивается со словом узла и «погружается» или в левое, или в правое поддерево с помощью рекурсивного обращения к addtree. Через некоторое время это слово обязательно либо совпадет с каким-нибудь из имеющихся в дереве слов (в этом случае к счетчику будет добавлена 1), либо программа встретит пустую позицию, что послужит сигналом для создания нового узла и добавления его к дереву. При создании нового узла addtree возвращает указатель на него, который вставляется в узел родителя.

struct tnode *talloc(void);

char *strdup(char *);

/* addtree: добавляет узел со словом w

в узел p или ниже его */

struct tnode *addtree(struct tnode *p, char *w)

{

int cond;

if (p == NULL) { /* слово встречается впервые */

p = talloc(); /* создается новый узел */

p->word = strdup(w);

p->count = 1;

p->left = p->right = NULL;

} else if ((cond = strcmp(w, p->word)) == 0)

p->count++; /* это слово уже встречалось */

else if (cond < 0) /* переходим к левому поддереву */

p->left = addtree(p->left, w);

else /* переходим в правое поддерево */

p->right = addtree(p->right, w);

return p;

}

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

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

/* treeprint: упорядоченная печать дерева p */

void treeprint(struct tnode *p)

{

if (p != NULL) {

treeprint(p->left);

printf("%4d %s\n", p->count, p->word);

treeprint(p->right);

}

}

Если вы не уверены, что досконально разобрались в том, как работает рекурсия, «проиграйте» действия treeprint на дереве, приведенном выше.

Практическое замечание: если дерево «несбалансировано» (что бывает, когда слова поступают не в случайном порядке), то время работы программы может сильно возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на вычисления будут такими же, как при линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем.

Прежде чем завершить обсуждение этого примера, сделаем краткое отступление от темы и поговорим о механизме запроса памяти. Очевидно, хотелось бы иметь всего лишь одну функцию, выделяющую память, даже если эта память предназначается для разного рода объектов. Но если одна и та же функция обеспечивает память, скажем, и для указателей на char, и для указателей на struct tnode, то возникают два вопроса. Первый: как справиться с требованием большинства машин, в которых объекты определенного типа должны быть выровнены (например, числа типа int часто должны размещаться, начиная с четных адресов)? И второе: как объявить функцию для распределения памяти, которая вынуждена в качестве результата возвращать указатели разных типов?

Вообще говоря, требования, касающиеся выравнивания, можно легко выполнить за счет некоторого перерасхода памяти. Однако для этого возвращаемый указатель должен быть таким, чтобы удовлетворялись любые ограничения, связанные с выравниванием. Функция alloc, описанная в главе 5, не гарантирует никакого выравнивания, поэтому мы будем пользоваться стандартной библиотечной функцией malloc, которая это делает. В главе 8 мы покажем один из способов ее реализации.

Вопрос об объявлении типа таких функций, как malloc, является камнем преткновения в любом языке с жесткой проверкой типов. В Си вопрос решается естественным образом: malloc объявляется как функция, которая возвращает указатель на void. Полученный указатель затем явно преобразуется к желаемому типу 1. Описания malloc и связанных с ней функций находятся в сандартном заголовочном файле <stdlib.h>. Таким образом, функцию talloc можно записать так:

#include <stdlib.h>

/* talloc: создает tnode */

struct tnode *talloc(void)

{

return (struct tnode *)malloc(sizeof(struct tnode));

}

Функция strdup просто копирует строку, указанную в аргументе, в место, полученное с помощью malloc:

char *strdup(char *s) /* делает дубликат s */

{

char *p;

p = (char *)malloc(strlen(s) + 1); /* +1 для '\0' */

if (p != NULL)

strcpy(p, s);

return p;

}

Функция malloc возвращает NULL, если свободного пространства нет; strdup возвращает это же значение, оставляя заботу о выходе из ошибочной ситуации вызывающей программе.

Память, полученную с помощью malloc, можно освободить для повторного использования, обратившись к функции free (см. главы 7 и 8).

6.8. Объединения

Объединение — это переменная, которая может содержать (в разные моменты времени) объекты различных типов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор. Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения в программу машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале.

Примером использования объединений мог бы послужить сам компилятор, заведующий таблицей символов, если предположить, что константа может иметь тип int, float или являться указателем на символ и иметь тип char *. Значение каждой конкретной константы должно храниться в переменной соответствующего этой константе типа. Работать с таблицей символов всегда удобнее, если значения занимают одинаковую по объему память и запоминаются в одном и том же месте независимо от своего типа. Цель введения в программу объединения — иметь переменную, которая бы на законных основаниях хранила в себе значения нескольких типов. Синтаксис объединений аналогичен синтаксису структур. Приведем пример объединения.

union u_tag {

int ival;

float fval;

char *sval;

} u;

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

Синтаксис доступа к элементам объединения следующий:

имя-объединения.элемент

или

указатель-на-объединение->элемент

т.е. в точности такой, как в структурах. Если для хранения типа текущего значения u использовать, скажем, переменную utype, то можно написать такой фрагмент программы:

if (utype == INT)

printf("%d\n", u.ival);

else if (utype == FLOAT)

printf("%f\n", u.fval);

else if (utype == STRING)

printf("%s\n", u.sval);

else

printf("Неверный тип %d в utype\n", utype);

Объединения могут входить в структуры и массивы, и наоборот. Запись доступа к элементу объединения, находящегося в структуре (как и структуры, находящейся в объединении), такая же, как и для вложенных структур. Например, в массиве структур

struct {

char *name;

int flags;

int utype;

union {

int ival;

float fval;

char *sval;

} u;

} symtab[NSYM];

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

symtab[i].u.ival

а к первому символу строки sval можно обратиться любым из следующих двух способов:

*symtab[i].u.sval

symtab[i].u.sval[0]

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

Инициализировать объединение можно только значением, имеющим тип его первого элемента; таким образом, упомянутую выше переменную u можно инициализировать лишь значением типа int.

В главе 8 (на примере программы, заведующей выделением памяти) мы покажем, как, применяя объединение, можно добиться, чтобы расположение переменной было выровнено по соответствующей границе в памяти.