Билет №29

1. Статические переменные в функциях. Понятие. Свойства. Использование.

2. Вложенные структуры. Понятие. Синтаксис. Пример применения.

3. Списки. Понятие. Использование. Синтаксис.

1. Статические переменные

Статические переменные представляют собой третий класс памяти, в дополнении к автоматическим переменным и extern, с которыми мы уже встречались. Статические переменные могут быть либо внутренними, либо внешними. Внутренние статические переменные точно так же, как и автоматические, являются локальными для некоторой функции, но, в отличие от автоматических, они остаются существовать, а не появляются и исчезают вместе с обращением к этой функции. Это означает, что внутренние статические переменные обеспечивают постоянное, недоступное извне хранение внутри функции. Символьные строки, появляющиеся внутри функции, как, например, аргументы printf , являются внутренними статическими. Внешние статические переменные определены в остальной части того исходного файла, в котором они описаны, но не в каком-либо другом файле. Таким образом, они дают способ скрывать имена, подобные buf и bufp в комбинации getch-ungetch, которые в силу их совместного использования должны быть внешними, но все же не доступными для пользователей getch и ungetch , чтобы исключалась возможность конфликта. Если эти две функции и две переменные объеденить в одном файле следующим образом

static char buf[bufsize]; /* buffer for ungetch */

static int bufp=0; /*next free position in buf */

getch() {...}

ungetch() {...}

то никакая другая функция не будет в состоянии обратиться к buf и bufp; фактически, они не будут вступать в конфликт с такими же именами из других файлов той же самой программы. Статическая память, как внутренняя, так и внешняя, специфицируется словом static , стоящим перед обычным описанием. Переменная является внешней, если она описана вне какой бы то ни было функции, и внутренней, если она описана внутри некоторой функции.

Нормально функции являются внешними объектами; их имена известны глобально. возможно, однако, объявить функцию как static ; тогда ее имя становится неизвестным вне файла, в котором оно описано. В языке "C" "static" отражает не только постоянство, но и степень того, что можно назвать "приватностью". Внутренние статические объекты определены только внутри одной функции; внешние статические объекты /переменные или функции/ определены только внутри того исходного файла, где они появляются, и их имена не вступают в конфликт с такими же именами переменных и функций из других файлов. Внешние статические переменные и функции предоставляют способ организовывать данные и работающие с ними внутренние процедуры таким образом, что другие процедуры и данные не могут прийти с ними в конфликт даже по недоразумению. Например, функции getch и ungetch образуют "модуль" для ввода и возвращения символов; buf и bufp должны быть статическими, чтобы они не были доступны извне. Точно так же функции push, pop и clear формируют модуль обработки стека; var и sp тоже должны быть внешними статическими.

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

struct UDC {char class, subclass;

tnt number;};

struct BOOK{ struct UDC udk_clcss;

char name [20];

char title[44];

int year; float price; } first_book, child_book, dog_book;

В данном примере описывается шаблон структуры, имеющей вложенную структуру, и три структурные переменных по шаблону BOOK, т. е. и для вложенных структур действуют те же правила описания полей: задается шаблон (в данном примере это struct UDC) и имя поля (в шаблоне BOOK это udk_dass).
Ссылка на поле вложенной структуры формируется из имени структурной переменной, имени структурного поля и имени поля вложенной структуры. Перечисленные имена разделяются символом '.' операции точка. Например, если сделано описание структурных переменных по приведенному ранее шаблону BOOK с вложенной структурой UDK, будут корректны следующие выражения:

first_book.udc_class.class = 'А';

dog_book.udc_class.number = 681;

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

struct BOOK { struct BOOK my_own; /* это ошибка */

char name [20];

char title[44];

int year; float price; };

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

struct BOOK {

struct BOOK * my_own; /* это разрешается */

char name f 20J;

char title[44];

int year, floatprice; };

  Иногда бывает удобно, чтобы одна структура содержалась или была "вложена" в другую. Например, Джейн строит структуру, содержащую информацию о ее друзьях. Один элемент структуры - это, конечно, имя друга. Однако имя можно представить самой структурой с разными элементами для имени и фамилии. На рис. 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", " ", Джейн ");

}

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

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

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

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

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

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

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

Джейн

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

struct names handle;

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

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

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

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

(fellow.handle).first

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

3. Списки – это сложная структура данных.

Списки

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

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

На рис. 1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Рис. 1: Представление односвязного списка в памяти

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

Рис. 2: Представление двусвязного списка в памяти

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

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

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

Рис. 3: Структура кольцевого двухсвязного списка

Описываемые ниже АТД могут быть организованы на базе

• массива: выделяется место под N элементов разом, а затем описываются операции над данным типом данных в терминах операций над элементами массива.

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

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