32) Перечислимые типы

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

Объявление перечисления начинается с ключевого слова enum и имеет два формата представления.

Формат 1. enum [имя-тега-перечисления] {список-перечисления} описатель[,описатель...];

Формат 2. enum имя-тега-перечисления описатель [,описатель..];

Объявление перечисления задает тип переменной перечисления и определяет список именованных констант, называемый списком-перечисления.

Значением каждого имени списка является некоторое целое число.

Переменная типа перечисления может принимать значения одной из именованных констант списка. Именованные константы списка имеют тип int.

Таким образом, память соответствующая переменной перечисления, это память необходимая для размещения значения типа int.

Переменная типа enum могут использоваться в индексных выражениях и как операнды в арифметических операциях и в операциях отношения.

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

Описатель именует переменную перечисления. В объявлении может быть задана более чем одна переменная типа перечисления.

Список-перечисления содержит одну или несколько конструкций вида: идентификатор [= константное выражение]

Каждый идентификатор именует элемент перечисления. Все идентификаторы в списке enum должны быть уникальными. В случае отсутствия константного выражения первому идентификатору соответствует значение 0, следующему идентификатору - значение 1 и т.д. Имя константы перечисления эквивалентно ее значению.

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

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

1. Переменная может содержать повторяющиеся значения.

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

4. Значение может следовать за последним элементом списка перечисления.

Пример:

enum week { SUB = 0, /* 0 */ VOS = 0, /* 0 */ POND, /* 1 */ VTOR, /* 2 */ SRED, /* 3 */ HETV, /* 4 */ PJAT /* 5 */ } rab_ned ;

В данном примере объявлен перечислимый тег week, с соответствующим множеством значений, и объявлена переменная rab_ned имеющая тип week.

Во втором формате используется имя тега перечисления для ссылки на тип перечисления, определяемый где-то в другом месте. Имя тега перечисления должно относится к уже определенному тегу перечисления в пределах текущей области видимости. Так как тег перечисления объявлен где-то в другом месте, список перечисления не представлен в объявлении.

Пример: enum week rab1;

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

33) Структуры

За одной переменной скрывается несколько переменных разных типов.

Struct person{

Int age;

Char name[20];}

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

размещения всех переменных.

Допустимые операции.

1)sizeof;

2)&-получение адреса

3)присваивание для одинакового типа

4).-доступ к полю структуры.

x.y //где х-имя переменной у-имя поля структуры.

Структура - это множество, состоящее из одного или более объектов, возможно

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

предоставляет удобный способ объединения различных элементов, связанных между

собой.

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

следовать необязательное имя, называемое именем типа структуры (здесь это date),

которое еще называется именем шаблона. Такое имя типа структуры может

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

структур.

За именем типа структуры идет заключенный в фигурные скобки список элементов

структуры, с описанием типа каждого элемента (элементом структуры может быть

переменная, массив, структура или объединение). Элементы структуры отделяются друг

от друга точкой с запятой. Например:

struct date

{

int day;

int month;

int year;

int yearday;

char mon_name[5];

};

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

объектов. Например, операторstruct date {...} x,y,z; определяет переменные x,y,z в

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

Изобразим распределение памяти для структуры x типа date:

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

Не следует полагать, что размер структуры равен сумме размеров ее членов.

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

безымянные "дыры". Так, например, если переменная типа char занимает один байт,

а int - четыре байта, то для структуры:

struct

{

char c;

int i;

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

операция sizeof.

Описание структуры, за которым не следует список объектов, не приводит к

выделению памяти (как в программе выше); оно только определяет шаблон (форму)

структуры. Однако, если такое описание снабжено именем типа (например, date), то это

имя типа может быть использовано позднее при определении фактических экземпляров

структур (определение структур d и f в программе).

Внешнюю или статическую структуру можно инициализировать, поместив вслед за ее

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

скобки. В программе таким образом инициализированы структуры d и f (они являются

внешними для функции main).

date d = { 0,0,1776,186,"июл" };

date f = { 1,9,1986,0,"сент" }; .

Автоматические структуры инициализации не подлежат!

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

<имя структуры>.<имя элемента>.

Структуры могут вкладываться одна в другую, но самовложение структур

запрещено!

34) Динамические структуры данных, основанные на структурах – двунаправленные списки.

Объявление:

Struct listnode{

Int key;

Char *data;

Struct listnode*prev,*next;

В поле структуры не может быть этой же самой структуры, может быть только указатель на эту структуру.

Чтобы в списках был удобный способ доступа к предыдущим элементам, добавим в каждый элемент списка

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

struct elem{

ETYPE data;

elem * next;

elem * pred;

elem ( ETYPE c, elem * n, elem * p ){ data = c; next = n; pred = p; }

};

С помощью элементов такого типа (рис. 6.) можно сформировать так называемый двунаправленный список

(с заглавным элементом):

Рис. 6. Двунаправленный список

Здесь в поле pred заглавного звена содержится пустой указатель NULL, означающий, что у заглавного

элемента нет предыдущего. Часто двунаправленные списки обобщают следующим образом (рис. 7, 8): в

качестве значения next последнего звена принимают указатель на заглавное (или первое) звено, а в качестве

значения поля pred заглавного (соответственно первого) звена - указатель на последнее звено:

Рис. 7. Первый вариант двунаправленного кольцевого списка

Рис. 8. Второй вариант двунаправленного кольцевого списка

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

В первом варианте (рис. 7) очень просто реализуется вставка нового звена как в начало списка (после

заглавного звена, так и в его конец, т.к. вставка звена в конец списка эквивалентна его вставке перед

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

не является ли очередное звено заглавным. Этого недостатка лишён второй вариант списка (рис. 8), но в этом

случае труднее реализуется добавление в конец списка.

Рассмотрим основные операции с кольцевыми двунаправленными списками в первом варианте (рис. 7).

Операции над кольцевыми списками

Вставка элемента

Пусть h, p, q - переменные типа elem*, а k - переменная типа int, значение которой должно содержаться в

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

p.

Эту вставку можно осуществить так:

q = new elem (k, p->next, p);

p->next->pred=q; p->next=q; // В таком порядке!

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

заглавного элемента списка: p=h;

Удаление элемента

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

указателем p непосредственно на само это звено:

p->next->pred = p->pred;

p->pred->next = p->next;

delete p;

Поиск элемента

Пусть h - указатель на заглавный элемент списка, r - указатель, ко-торый будет указывать на найденное

звено, содержащее k. Пусть также p, q - переменные типа elem*, b - типа int. Поиск элемента, содержащего

число k, осуществляется так:

b=1; h->data = k+1; // В информационную часть заглавного звена

// заведомо занесём число, отличное от k.

p=h->next; // Сначала p указывает на первое звено.

r=NULL;

q=p; // q указывает на первое звено.

do {

if (p->data= =k){

b=0;

r=p;

}

p=p->next;

}while ((p!=q) && b);

Заметим, что если в списке вообще нет звена, содержащего k, то после поиска значение b останется

равным единице, указатель r будет равен NULL, а p примет значение q, т.е. снова будет указывать на первое

звено (после заглавного).

35) Представление списков в программе. Основные операции над двунаправленными списками.

а этот вопрос лучше перечислить по пунктам:

1. присваивание полю структуры значение того же типа

2. можно получить адрес структуры. Не забываем операцию взятия адреса (&)

3. можно обращаться к любому полю структуры

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

операцию sizeof()

Для начала, вспомним (или впервые узнаем)), что динамический список представляет из себя некоторое

количество компонентов (узлов), содержащих непосредственно информационную часть (число, строка или более

сложные типы данных), а также ссылку на следующий компонент (возможно, что узел содержит 2 ссылки: на

следующий и на предыдущий, в таком случае, список называется двусвязным). Таким образом, получаем

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

struct comp {

char name[20]; // Имя переменной

char value[10]; // Значение переменной

comp* next; //Ссылка на следущий элемент списка

};

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

первый элемент и последний. Нередко, хватает и одной из этих ссылок, но в нашем случае удобнее будет

использовать обе. Итак, получаем структуру, описывающую наш список:

struct dyn_list {

comp* head; // Первый элемент (голова) списка

comp* tail; // Последний элемент (хвост) списка

};

Несложно понять, что значит создать пустой список. Фактически делать ничего не нужно, разве что присвоить

ссылке на первый элемент списка (head) значение NULL. Оформим это как функцию, параллельно создав еще

одну, проверяющую по этому условию, пуст ли список.

// Создание пустого списка