1611678431-0e68e83522cb9d960ac896aa5d90854d (826635), страница 21

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

Текст из файла (страница 21)

Но для реализации операций с очередью необходимы уже две переменные:указатель First на начало очереди и указатель Last на конец очереди.Приведенная ниже схема элементов очереди отражает логический порядок следованияэлементов, физически же элементы могут находиться в любых свободных областях памяти.Основные операции с динамической очередью: проверка отсутствия элементов в очереди добавление нового элемента в конец очереди удаление элемента из начала очереди проход по очереди от начала к концуДобавление нового элемента немного по-разному реализуется для пустой и непустойочереди. Аналогично, по-разному выполняется удаление из очереди, содержащей один или болееодного элемента. Для того, чтобы эти операции во всех случаях выполнялись единообразно, частоиспользуется следующий прием: в начало очереди вводится фиктивный элемент-заголовок, которыйНИКОГДА не удаляется и всегда содержит адрес первого элемента очереди.В этом случае создание пустой очереди включает в себя: выделение памяти для заголовка с помощью указателя First занесение в ссылочную часть заголовка пустого указателя NULL установка указателя конца очереди Last = FirstСхемы пустой и непустой очереди приводятся на следующих рисунках:Необходимые описания типов и переменных:struct QueueItem { /*структура элемента очереди*/int Info; /*информационная часть*/QueueItem *Next; /*ссылочная часть: адрес следующего элемента*/};QueueItem *First,*Last;Тогда условие пустой очереди можно записать следующим образом:First->Next=NULL;Для прохода по очереди от первого реального элемента к последнему необходимо: ввести вспомогательную ссылочную переменную Current установить Current в адрес первого реального элемента:Current=First->Next организовать цикл по условию достижения конца очереди в цикле обработать очередной элемент с помощью указателя Current и изменить этотуказатель:Current=Current->NextДобавление элемента в конец очереди выполняется следующим образом: выделить память для нового элемента с помощью стандартной функции new ивспомогательной ссылочной переменной Tmp:QueueItem *Tmp = new QueueItem; заполнить поля нового элемента, в частности в связующую часть установить значениеNULL:Tmp->Next = NULL; изменить связующую часть бывшего последнего элемента таким образом, чтобы онаадресовала новый добавленный элемент:Last->Next = Tmp; изменить значение указателя Last так, чтобы он указывал новый последний элемент:Last = Tmp;Удаление элемента из начала очереди (но после заголовка!) выполняется следующимобразом: адресуем удаляемый элемент с помощью вспомогательной переменной Tmp:Tmp = First->Next; изменить связующую часть заголовка так, чтобы она указывала на второй элементочереди, который теперь должен стать первым: First->Next = Tmp->Next; если после удаления в списке не остаётся реальных элементов, то необходимоизменить указатель Last:Last = First; обработать удаленный элемент, например – освободить занимаемую им память спомощью стандартной подпрограммы delete:delete Tmp;или включить его во вспомогательную очередь удаленных элементовСравнение двух способов реализации очереди полностью аналогично стеку.

Интереснойразновидностью очереди являются приоритетные очереди, в которых элементы выстраиваются нетолько в порядке поступления, но и в соответствии с их приоритетами: сначала идут болееприоритетные элементы, потом – все менее приоритетные. Одноприоритетные элементырасполагаются в порядке поступления. Это требует изменения процедуры добавления элемента вочередь: надо прежде всего найти место в очереди, куда должен вставиться новый элемент всоответствии с его приоритетом, а потом уже выполнить саму вставку. Фактически, приоритетнуюочередь можно рассматривать как разновидность упорядоченного линейного списка.Реализация на массиве (с кодом)Плюсы: прост в разработке по сравнению с реализацией на списке, есть незначительная экономия памятиМинусы: количество элементов в очереди ограничено размером массива (исправляется написаниемфункции расширения массива) - при переполнении очереди требуется перевыделение памяти и копирование всех элементов вновый массивРеализация на спискеДля данной реализации очереди необходимо создать список (list) и операции работы насозданном списке.Реализация очереди на односвязном списке list:o x.value- поле, в котором хранится значение элементаo x.next - указатель на следующий элемент очередиМинусы:Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди можетбыть ощутимо медленнее, нежели итерация по очереди реализованной на массиве40.

Бинарные деревья, способы их задания и реализацииЛекции: фото 34, 35Деревом называется связный граф без циклов (у него p вершин и p-1 ребро).Корневое дерево - это дерево с выделенной вершиной, называемой корнем. Все вершиныкорневого дерева распадаются на уровни по величине их расстояния от корня, так, что все ребрасоединяют вершины соседних уровней. Рассматривая каждое ребро <u,v> корневого дерева как дугу(u,v) от вершины меньшего уровня к вершине большего уровня, получаем понятие ориентированногодерева (или ордерева). Это - связный орграф без циклов, удовлетворяющий следующим условиям:а) имеется ровно одна вершина, называемая корнем, к которой не ведет ни одна дуга;б) к каждой вершине, отличной от корня, ведет ровно одна дуга; говорят, что она соединяетотца с сыном.В упорядоченном ордереве на множестве всех вершин, достижимых из данной (ее потомков),задано линейное упорядочение, при котором все потомки одного сына предшествуют всем потомкамлюбого более младшего.

Вершины ордерева, не имеющие сыновей, называются листьями.Двоичное (или бинарное) дерево - это ордерево, в котором каждая вершина имеет не болеедвух преемников, называемых левым и правым преемниками (или сыновьями).Бинарное дерево целых чисел D – это либо пустое дерево (без вершин), либо тройка D = <R,Dl, Dr>, - где R – целое число – корень дерева, Dl, Dr, - бинарные деревья целых чисел - левое и правоеподдеревья.Структуру данных – дерево можно представить как в статической, так и в динамической памяти. Встатической памяти дерево можно представить массивом, для которого определено понятие пустогоэлемента:struct stree{ type elem [ N ]; }stree d;илиtype d [ N ];01.

. .2N-1корень левый правыйпотомок потомоккорня корняВершины двоичного дерева располагаются в массиве следующим образом: если k – индексвершины дерева, то ее потомки находятся в элементах массива с индексами 2k + 1 и 2(k + 1); кореньдерева находится в элементе с индексом 0 (при индексации в массиве от 1 до N индексы потомков kой вершины: 2k и 2k + 1, корень имеет индекс 1).В динамической памяти дерево представляется иерархическим списком.

Задать элементдвоичного дерева можно как элемент списка с тремя полями: два ссылочных поля, содержащиеуказатели на его левое ( L ) и правое ( R ) поддеревья, и информационное поле ( E ):ELRОпределение типа элемента бинарного динамического дерева(C/C++):struct btree{type elem;btree *left, *right;}Здесь type – тип информационного поля (если информационное поле имеет сложнуюструктуру, то type может быть типом - указатель на объект, содержащий значение элемента дерева).Чтобы определить дерево как единую структуру, надо задать указатель на корень дерева:btree*d;На рис.4.3 представлено двоичное динамическое дерево d в cоответствии с определениемтипа элемента, сделанным выше. Элементы дерева со степенью 0 и 1 имеют два или одно ссылочноеполе со значением равным пустому указателю (NULL).dNULLNULLNULLNULLNULLNULLNULLNULLРис.4.3Пример описания полей и элементов, необходимых для построения дерева (Pascal).TypeNd = ^ node;Node = recordInf1 : integer;Inf2 : string ;Left : nd;Right : nd;End;VarRoot, p,q : nd;Приведенный пример описания показывает, что описание элемента списка и узла дерева посути ничем не отличаются друг от друга.

Различия в технологии действий тоже невелики - основныедействия выполняются над ссылками, адресами узлов. Основные различия - в алгоритмах.При работе с двоичным деревом возможны следующие основные задачи:1)2)3)создание элемента, узла дерева,включение его в дерево по алгоритму двоичного поиска,нахождение в дереве узла с заданным значением ключевого признака,4)5)6)7)определение максимальной глубины дерева,определение количества узлов дерева,определение количества листьев дерева,ряд других задач.Пример процедуры, реализующей задачу 1 (Pascal).Procedure CREATE_EL_T(var q:ND; nf1:integer; inf2:string);beginnew(q);q^.inf1:=inf1;q^.inf2:=inf2;{значения полей передаются в качестве параметров}q^.right:=nil;q^.left:=nil;end;41.

Характеристики

Список файлов ответов (шпаргалок)