32. Структура данных – очередь.

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

С очередью работают 2 указателя: head и tail (голова и хвост). Голова указывает на первый занятый элемент, а хвост – на первый свободный. Когда голова совпадает с хвостом, очередь считается пустой.

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

Задачи: в листе клетчатой бумаги вырезали некоторые клетки. Определить, на сколько частей распадётся лист. Решение с помощью очереди. Заносим первую клетку в очередь. далее из очереди выбирается первый элемент, в очередь заносятся все клетки, которые находятся рядом с первой и не отмечены как вырезанные. Далее просматриваем следующую клетку и смежные с ней. Как только очередь стала пустой, то мы нашли одну область. Далее исчем незанесённую клетку и создаём новую очередь и заносим в неё все смежные клетки, помечая их. Затем продолжаем идти по матрице. Можно включать счётчик при обнулении очереди. Таким образом, мы считаем, сколько областей получилось при разделении листа.

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

32. Деревья.

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

Бинарные деревья – деревья, из каждого узла которых выходит ровно 2 дуги или одна. При применении в программировании структуру данных дерево необходимо моделировать. Чаще всего их моделируют при помощи динамических структур, поскольку при моделировании при помощи массива необходимо использовать двухмерные и трёхмерные массивы. Основные задачи: добавление элемента, удаление элемента, балансировка.

Построим дерево сортировки на основе бинарного дерева: 8 6 10 4 9 5 1 7 12

8

6. 10

4 7 9 12

1 5

Обходя дерево, получим отсортированный массив: 1 4 5 6 7 8 9 10 12.

32. Наследование

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

Синтаксически наследование между двумя классами определяется следующим образом:

Class имя_производного_класса : public имя_базового_класса

{ тело_класса

};

При таком наследовании произвольного к членам базового класса, которые объявлены в разделах класса и protected базового класса. Но запрещен доступ к членам базового класса, которые объявлены в разделе private базового класса.

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