Очереди. Основные операции над очередью.
Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.
Изобразим очередь графически:
При программировании на Паскале также считается, что для очереди не существует обход элементов. Доступ возможен только к нижнему элементу структуры.
Итак, очередь – это вид связанного списка, в котором извлечение элементов происходит с начала списка, а добавление новых элементов – с конца.
Очередь является динамической структурой – с течением времени изменяется и ее длина, и набор составляющих ее элементов.
Опишем очередь на языке программирования:
Type EXO = ^O; O = record Data : integer; Next : EXO; end;
Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.
В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:
Var BeginO, EndO : EXO;
где BeginO – соответствует началу очереди и будет использоваться для вывода элемента из очереди, EndO – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.
Занесение элемента в очередь
Занесение элемента в очередь соответствует занесению элемента в конец списка. Рассмотрите процедуру, описанную ниже.
Procedure writeO(Var BeginO, EndO : EXO; c : integer); Var u : EXO; Begin new(u); u^.Data := c; u^Next := Nil; if BeginO =Nil {проверяем пуста ли очередь} then BeginO := u {ставим указатель начала очереди на первый созданный элемент} else EndO^.Next := u; {ставим созданный элемент в конец очереди} EndO := u; {переносим указатель конца очереди на последний элемент} End;
23.Дерево. Назначение, варианты реализации и примеры применения.
Граф – это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.
Если на каждом ребре задать направление, то граф будет ориентированным.
Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем.
Замкнутый путь, состоящий из различных ребер, называется циклом.
Граф называется связным, если любые две его вершины соединены путем.
Связный граф без циклов называется деревом.
С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.
Рассмотрите пример дерева, в узлах которого располагаются символы.
Для дальнейшей работы с деревьями необходимо определить ряд понятий.
Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.
Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.
Количество непосредственных потомков внутренней вершины называется ее степенью.
Степенью дерева называется максимальная степень всех вершин.
Например,
вершины F, D, E являются непосредственными потомками вершины В;
вершины F, D, E являются листьями;
вершины C, G, H – внутренние;
степень вершины В – 3, а вершины Н – 1;
степень дерева равна 3.
Определение. Двоичное дерево – это дерево, в котором из каждой вершины исходит не более двух ребер.