Int dequeue(Queue *q, double *d) {

if(q->head == q->tail) return 0; // если очередь пуста

*d = q->v.elem[q->head++]; // извлекаем из «головы»

return 1;

}

Теперь займемся конструированием модульной структуры приложения, использующего абстракцию «очередь». По аналогии с абстракциями «вектор» и «стек» сначала сформируем интерфейс, в который поместим описание структуры Queue, а также описания клиентских функций для работы с очередями: init_q, enqueue и dequeue.

Как отмечалось ранее, интерфейс помещается в заголовочный файл, который назовем Queue.h :

// Queue.h

#include "Vector.h"

typedef struct Queue {

int head, tail;

Vector v;} Queue;

void init_q(Queue*);

void enqueue(Queue*, double);

int dequeue(Queue*, double*);

Лекция 15. Алгоритмы и структуры данных (продолжение).

Вопрос №77. Структура данных «пирамида»: основные характеристики и внутреннее устройство. Основное свойство пирамиды. Реализация пирамиды с помощью вектора.

Пирамида — это структура данных, представляющая собой объект-массив, который можно рассматривать как «почти полное бинарное дерево». Каждый узел этого дерева соответствует определенному элементу массива. На всех уровнях, кроме, может быть, последнего, дерево полностью заполнено (заполненный уровень — это такой, который содержит максимально возможное количество узлов). Последний (нижний) уровень заполняется слева направо до тех пор, пока в массиве не закончатся элементы.

Будем называть элементы массива с индексами i*2+1 и i*2+2 потомками элемента с индексом i, а элемент i будет называться предком этих элементов. Несложно заметить, что потомки двух разных элементов не пересекаются, и каждый элемент, кроме нулевого, является чьим-либо потомком.

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

• для неубывающих пирамид: «каждый элемент не меньше своих потомков»;

• для невозрастающих пирамид: «каждый элемент не больше своих потомков».

Следствием этого основного свойства пирамиды является утверждение:

• для неубывающих пирамид: «максимальный элемент находится в корне дерева (занимает первое место в массиве)»;

• для невозрастающих пирамид: «минимальный элемент находится в корне дерева (занимает первое место в массиве)».

В дальнейшем для определенности под «пирамидой» будем подразумевать максимальную пирамиду.

Как будет указано далее, пирамида является динамической структурой данных, поэтому её целесообразно реализовывать на базе ранее сконструированной структуры данных «вектор», а не на базе обычного массива.

Заметим, что в отличие от стека и очереди, пирамида не требует никаких дополнительных элементов, кроме тех, что есть у вектора, поэтому структура данных «пирамида» (Heap) является просто оболочкой над структурой данных Vector:

Typedef struct Heap {Vector V;} Heap;

В этих условиях функция инициализации пирамиды – init_h будет тривиальной: