Int year;

sextype sex;

union

{

Int children;

ranktype rang;

};

}s1;

cout<<"Enter fio ";

cin.getline(s1.fio,40);

cout<<"Enter sex ";

cin>>int(s1.sex);

switch(s1.sex)

{

case male: { cout<< "Enter rank ";

cin>>int (s1.rang);

cout<<"\n"<<s1.fio;

cout<< " male, rank="<<s1.rang;

break;

}

case female:{cout<< "Enter number of children ";

cin>>s1.children;

cout<<"\n"<<s1.fio;

cout<< " female, children ="<<s1.children;

break;

}

}

getch();

}

Вернемся к рассмотрению динамических структур данных. Элемент любой динамической структуры данных представляет собой структуру (в смысле struct), содержащую по крайней мере два поля: для хранения данных и для указателя на этуже структуру. Полей данных и указателей может быть несколько. Например, элемент списка целых чисел имеет вид

struct el

{

int a;

el *b;

}

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

• каким образом может расти и сокращаться данная структура;

• каким образом можно включить в структуру новый и удалить существующий элемент;

• как можно обратиться к конкретному элементу структуры для выполнения над ним определенной операции. (Доступ по индексу здесь, очевидно, менее удобен, чем это было в случае массивов, так как любой элемент при изменении размеров структуры может изменить свою позицию. Поэтому обычно доступ к элементам динамической структуры относительный: найти следующий (предыдущий) элемент по отношению к текущему, найти последний элемент и т.п.)

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

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

struct student

{

char *fio;

int mark;

student *next;

}

Для формирования списка требуется иметь по крайней мере один указатель – на начало списка (голова списка).

student * begin=NULL;

и один вспомогательный указатель student *adr;.

Опишем процедуру создания списка

void vvod ()

{

int n;

cout<< “Введите количество студентов ”;

cin>>n;

const int dlin=20;

char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента

for (int i=1;i<=n; i++)

{

if (begin==NULL) // выделение памяти под первый элемент списка

{

begin=new (student);

adr=begin;

}

else // выделение памяти под очередной элемент списка

{

adr->next=new(student);

adr=adr->next;

}

//заполнение элементов списка

cout<< “Введите фамилию ”;

cin.getline(f,dlin);

adr->fio=new (char [strlen(f)+1]);

strcpy(adr->fio,.f);

cout<< “Введите оценку ”;

cin>>(adr->mark);

adr->next=NULL;

}

}

В данном случае мы создали список студентов как очередь. Очередь – это частный случай списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип FIFO (firs in – first out, первым пришел – первым вышел). В нашем примере указатель begin указывает на начало списка, и не изменяется во время выполнения программы. Добавление элементов происходит в конец списка. Очевидно, что обработка элементов для списка, сформированного таким образом, может происходить только с первого введенного.

Другим частным случаем однонаправленного списка является стек, добавление в который и выборка из которого выполняется с одного конца. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек реализует принцип LIFO (last in – first out, последним пришел – первым вышел). Создадим список студентов как стек, постоянно передвигая указатель begin и последний созданный элемент делая головой списка.

.

void vvod1 ()

{

int n;

cout<< “Введите количество студентов ”;

cin>>n;

const int dlin=20;

char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента

for (int i=1;i<=n; i++)

{

adr=new(student);

cout<< “Введите фамилию ”;

cin.getline(f,dlin);

adr->fio=new (char [strlen(f)+1]);

strcpy(adr->fio,.f);

cout<< “Введите оценку ”;

cin>>(adr->mark);

adr->next=begin;

begin=adr;

}

}

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

void vivod()

{

adr=begin;

while (adr!=NULL)

{

cout<<"\n "<<(adr->fio)<<" "<<adr->mark;

adr=adr->next;

}

}

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

• добавления элемента в конец списка;

• поиска заданного элемента;

• вставка элемента до или после заданного элемента;

• сортировка списка;

• удаления заданного элемента;

• удаление списка.

Каждому студенту рекомендуется выполнить хотя бы одно из упражнений 1-12 заданий 1-4.