2. Записи. Организация, размещение. Записи с вариантами.??????

Билет № 30

1.Двухсвязные линейные списки и кольца, операции над ними.

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

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

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

Рассмотрим особенности работы с двухсвязным списком.

1. Как и в случае с односвязным списком, создадим две структуры. Тексты этих структур расположим в начале программы (до main() и других функций). Вот возможная реализация структур:

struct Data

{ int a; // данные };

struct List2

{ Data d;

List2 *prev; // указатель на предшествующий элемент

List2 *next; // указатель на последующий элемент };

2. Затем создаём два указателя:

List2 *Begin = NULL; // Начало списка

List2 *End = NULL; // Конец списка

3. Теперь можно формировать какой-то начальный список. Делаем это по аналогии с тем, как делали при работе с односвязными списками. Начнём формировать список из трёх чисел 3, 5 и 1:

// Создаём первый элемент

List2 *t = new List2;

t->d.a = 3;

t->prev = NULL;

t->next = NULL;

// Настроим на него оба указателя

Begin = t;

End = t;

// Создаём второй элемент

t->next = new List2;

List2 *p = t;

t = t->next;

t->prev = p;

t->d.a = 5;

t->next = NULL;

End = t;

// Создаём третий элемент

t->next = new List2;

p = t;

t = t->next;

t->prev = p;

t->d.a = 1;

t->next = NULL;

End = t;

1.Обход списка в прямом направлении и его вывод на экран монитора:

void print_forward(List2 *Begin)

{List2 *p = Begin;

cout << "Spisok (forward):" << endl;

while(p)

{cout << p->d.a << endl;

p = p->next;}}

Возможный вызов функции:

print_forward(Begin);

Как видим, полученная реализация по сути является копией функции print() для печати односвязного списка.

2.Обход списка в обратном направлении и его вывод на экран монитора:

void print_back(List2 *End)

{List2 *p = End;

cout << "Spisok (back):" << endl;

while(p)

{cout << p->d.a << endl;

p = p->prev;}}

Возможный вызов функции:

print_back(End);

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

Используем те же структуры (Data и List), что применяли для односвязного списка. Точно так же определяем указатель на начало будущего списка:

List *u = NULL;

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

x->next = u;

В итоге будет получен кольцевой список.

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

void printC(List *u)

{if(u != NULL)

{List *p = u;

cout << "Kolcevoj Spisok:" << endl;

cout << p->d.a << endl;

p = p->next;

while(p != u)

{cout << p->d.a << endl;

p = p->next;}}

else

cout << "Spisok pust." << endl;}

Возможный вызов функции:

printC(u);