массива (к первому элементу), если есть свободные позиции в начале массива. Таким образом, освобождаемся от псевдопереполнения очереди; г) циклическая очередь – линейный массив с двумя указателями (аналогично
варианту а), в котором при достижении каким-либоуказателем конца массива (последнего элемента) значение этого указателя очереди округляется по модулю N, где N – размер массива. Таким образом, в циклической очереди при достижении конца массива (end =N-1)и наличии свободных позиций в начале (begin > 0), новый элемент помещается в массив на место с индексом 0, при этом указателю end присваивается значение 0.
конец
начало
data
0
1
N-1
э3
э4
• • •
э1
э2
N-2
1
begin
end
Очередь будет полна, если поле end = N-1,а поле begin = 0 или поле end = K, а begin = K+1. Здесь 0 < K <N-1.
В динамической памяти очередь можно представить: а) линейным односвязным списком с двумя указателями:
struct list1
{type pole1; list1 *pole2; }
struct ch3
{ list1
*beg, *end ; }
beg
начало
конец
. . .
NULL
end
Задать динамическую очередь -
это определить переменную типа ch3:
ch3
Q1;
Чтобы инициировать очередь достаточно указателю на начало Q1.beg и/или на конец Q1.end присвоить значение NULL. При взятии единственного элемента из очереди она должна стать пустой; б) линейным двусвязным циклическим списком с одним указателем:
struct list2
{type pole1;
list2 *pole1, *pole2; }
…
Здесь начало или конец очереди можно сделать как в начале, так и в конце списка. Кроме рассмотренных вариантов простых очередей существует понятие очереди
с приоритетом. Элемент такой очереди имеет не только значение, но и вес или приоритет этого значения. При включении элемента в очередь с приоритетом сначала отыскивается место элемента в соответствии с его приоритетом. Элемент с наивысшим приоритетом помещается в начало очереди, элемент с низшим весом в конец очереди. Такой очереди наилучшим образом отвечает двусвязный циклический список.
Основные операции над очередью аналогичны операциям со стеком (с учетом особенностей этой структуры).
Еще одной разновидностью этих структур данных является дек. Дек это список, у которого обе позиции: начало и конец списка доступны для добавления и взятия элемента. Таким образом, дек может быть и стеком, и очередью, и комбинацией этих структур. Наиболее часто дек представляется структурой с ограничением на вход или выход: дек с ограниченным входом (только одна позиция доступна для добавления элемента) и дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека).
2.Контрольные вопросы
1.Понятие структуры данных стек, очередь, дек.
2.Представление в памяти структур данных стек, очередь, дек.
3.Задание структур данных стек, очередь, дек.
4.Основные операции над структурами данных стек, очередь, дек.
5.Достоинства и недостатки различного представления в памяти структур данных стек, очередь, дек.
6.Использование структур данных стек, очередь для решения задач.
3.Варианты задания
Данная лабораторная работа состоит в выполнении варианта задания из пункта 1 и пункта 2.
1. Написать операции работы с заданной структурой данных, включив их в один модуль (файл). К основным операциям (см. таблицу 1) добавить операцию, показывающую содержимое структуры после выполнения какого-либодействия с ней. Эту операцию реализовать на основе базовых операций:
а) основные операции над статическим стеком; б) основные операции над динамическим стеком;
в) операция “принадлежит ли заданный элемент ” статическому стеку; г) операция “принадлежит ли заданный элемент ” динамическому стеку; д) основные операции над статической очередью (вид очереди: а, б, в, г); е) основные операции над динамической очередью (вид очереди: а, б); ж) операция “добавить элемент в очередь” для статической очереди с
приоритетом (вид очереди: а, б, в, г). На вход такой очереди подается элемент и
его приоритет, определяющий место элемента в очереди. В очереди с приоритетом элементы должны располагаться в порядке возрастания или убывания приоритетов; з) операция “добавить элемент в очередь” для динамической очереди с приоритетом (вид очереди: а, б) см. 1.ж; и) операция “принадлежит ли заданный элемент ” статической очереди (вид очереди а, б, в, г);
к) операция “принадлежит ли заданный элемент ” динамической очереди (вид очереди: а, б); л) основные операции над статическим деком;
м) основные операции над динамическим деком.
2. Написать программу, демонстрирующую выполнение операций, над заданной структурой данных. Эту программу надо поместить в свой модуль (файл). Модуль с основными операциями включать в программу, используя директиву include.
Л А Б О Р А Т О Р Н А Я Р А Б О Т А № 4
СТРУКТУРЫ ДАННЫХ: ДЕРЕВЬЯ
Цель работы: изучить основные алгоритмы работы с деревьями; получить практические навыки разработки и использования этих структур и алгоритмов для решения задач.
1. Методические указания
1.1.Понятие дерева. Виды деревьев
Дерево – это конечное множество T , возможно пустое, в противном случае, состоящее из одного или более элементов (узлов или вершин дерева) таких, что:
а) имеется один специально обозначенный элемент, называемый корнем данного дерева;
б) остальные элементы содержатся в m >0 попарно непересекающихся множествах T1 , . . . ,Tm , каждое из которых в свою очередь является деревом; деревья T1 , . . . , Tm называются поддеревьями данного корня (рис.4.1.а).
A
B C
D E F
G H J
а
б
Рис.4.1
Если имеет значение относительный порядок поддеревьев T1, . . . ,Tm , то говорят, что дерево является упорядоченным. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом (или листом или терминальным узлом), все остальные элементы – внутренние узлы (нетерминальные). Максимальная степень всех вершин называется степенью дерева. Корень дерева имеет уровень равный 0. Остальные вершины имеют уровень на единицу больше уровня непосредственного предка. Максимальный уровенькакой-либоиз вершин называется глубиной или высотой дерева. Минимальная высота при заданном числе вершин достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число вершин. Максимальное число вершин в дереве высотой h достигается в том случае, если из каждой вершины, за исключением уровня h, исходят d поддеревьев, где d –
степень дерева: на 0-муровне 1 вершина, на1-м– d потомков, на2-м– d2 потомков, на3-муровне d3 потомков и т.д.
Наиболее широко используются двоичные (бинарные) деревья (рис.4.1.б). Бинарное дерево это конечное множество элементов, которое либо пусто, либо состоит из корня и из двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Таким образом, каждый элемент бинарного дерева имеет 0, 1 или 2 поддерева. Бинарное дерево – упорядоченное дерево, так как в нем различают левое и правое поддеревья.
Дерево поиска – это двоичное дерево, в котором выполняются следующие условия (см. рис.4.2):
а) l(u) < l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – левый преемник v;
б) l(u) > l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – правый преемник v;
в) для всякого значения a S существует единственная вершина v, для которой l(v) = a (S – множество значений, допускающих сравнения).
S
M T 
A N Z
D X
Рис.4.2
Определение структуры дерева, данное выше, является рекурсивным и отражает рекурсивную природу самой структуры.
Структуру данных – дерево можно представить как в статической, так и в динамической памяти. В статической памяти дерево можно представить массивом, для которого определено понятие пустого элемента:
struct stree
{ type elem [ N ]; } stree d;
или
type
d [ N ];
0
1
2
N-1
. . .
корень левый правый потомок потомок корня корня
Вершины двоичного дерева располагаются в массиве следующим образом: если k – индекс вершины дерева, то ее потомки находятся в элементах массива с индексами 2k + 1 и 2(k + 1); корень дерева находится в элементе с индексом 0 (при индексации в массиве от 1 до N индексы потомков k-ойвершины: 2k и 2k + 1, корень имеет индекс 1).
В динамической памяти дерево представляется иерархическим списком. Задать элемент двоичного дерева можно как элемент списка с тремя полями: два ссылочных поля, содержащие указатели на его левое ( L ) и правое ( R ) поддеревья, и информационное поле ( E ):
E L R
Определение типа элемента бинарного динамического дерева: struct btree
{type elem;
btree *left, *right;}
Здесь type – тип информационного поля (если информационное поле имеет сложную структуру, то type может быть типом - указатель на объект, содержащий значение элемента дерева).
Чтобы определить дерево как единую структуру, надо задать указатель на корень дерева:
btree * d ;
На рис.4.3 представлено двоичное динамическое дерево d в cоответствии с определением типа элемента, сделанным выше. Элементы дерева со степенью 0 и 1 имеют два или одно ссылочное поле со значением равным пустому указателю
(NULL).
d
NULL
NULL
NULL
NULL
NULL NULL
NULL NULL
Рис.4.3
Обрабатывая дерево, приходится просматривать его элементы – эта операция называется обход дерева (или прохождение дерева).
Обход дерева – это способ методичного исследования его узлов, при котором каждый узел проходится точно один раз. Полное прохождение динамического дерева дает линейную расстановку его узлов.
Возможны два способа прохождения бинарного дерева (если дерево не пусто): а) в глубину:
- прямой (префиксный) порядок: корень, левое поддерево в прямом порядке, правое поддерево в прямом порядке (линейная расстановка узлов дерева, представленного на рис.4.1.б: ABDCEGFHJ );
Алгоритм прямого обхода: { S = NULL;
while ( d != NULL) { обработка ( d );
if ( d->left!= NULL &&d->right!= NULL) {встек (S,d->right);d =d->left;}
else if ( d->left= = NULL &&d->right= =NULL)
if ( S!= NULL) изстека (S, d); else d = NULL; else if (d->left!= NULL) d =d->left;
else d = d->right;
}
}
Рекурсивное описание алгоритма прямого обхода:
пр_обход ( btree *d)
{ if ( d != NULL ) { обработка ( d ); пр_обход ( d->left); пр_обход (d->right); }
}
- обратный (инфиксный) порядок: левое поддерево в обратном порядке, корень, правое поддерево в обратном порядке (линейная расстановка узлов дерева, представленного на рис.4.1.б: DBAEGCHFJ);
Алгоритм обратного обхода:
{S = NULL; F = 1; while ( F )
{while ( d != NULL )
{встек ( S, d ); d = d->left;} if ( S != NULL ) { изстека ( S, d );
обработка ( d ); d = d-right;}
else F = 0;
}
}
Рекурсивное описание алгоритма обратного обхода:
обр_обход ( btree *d )
{ if ( d != NULL ) { обр_обход ( d->left); обработка ( d ); обр_обход (d->right); }
}
- концевой (постфиксный) порядок: левое поддерево в концевом порядке, правое поддерево в концевом порядке, корень (линейная расстановка узлов дерева, представленного на рис.4.1.б: DBGEHJFCA);
Алгоритм концевого обхода:
{S = NULL; do
while ( d != NULL )
{встек ( S, d, 0 ); d = d->left;} if ( S != NULL )
{ do
изстека ( S, d, F ); if ( F ) обработка ( d ); while ( F && S != NULL );
if ( ! F ) { встек ( S, d, 1 ); d = d->right;} while ( S != NULL );
}
Рекурсивное описание алгоритма концевого обхода:
конц_обход ( btree *d )
{ if ( d != NULL ) { конц_обход ( d->left); конц_обход (d->right);
обработка ( d ); }
}
б) в ширину: узлы дерева посещаются слева направо, уровень за уровнем вниз от корня (линейная расстановка узлов дерева, представленного на рис.4.1.б: ABCDEFGHJ).
Алгоритм обхода в ширину: { Q = NULL;
if ( d != NULL ) { в_очередь ( Q, d ); do
из_очереди ( Q, d ); обработка ( d );
if ( d->left!= NULL ) в_очередь ( Q,d->left); if (d->right!= NULL ) в_очередь ( Q,d->right);
while ( ! пуста_очередь ( Q ) );
}
}
Основные операции при работе с деревьями:
а) поиск элемента в дереве. Операция заключается в прохождении узлов дерева в одном из рассмотренных выше порядке. При прохождении дерева поиска достаточно пройти только то поддерево, которое возможно содержит искомый элемент; б) включение элемента в дерево. Операция заключается в добавлении листа
(исключая сбалансированное дерево – включение элемента в сбалансированное дерево приводит, как правило, к его перестройке) в какое-топоддерево, если такого элемента нет в исходном дереве. При включении нового элемента в дерево поиска лист добавляется в то поддерево, в котором не нарушается отношение порядка;
в) удаление элемента из дерева. Операция заключается в изменении связей между дочерними и родительскими, по отношению к удаляемому, элементами (исключая сбалансированное дерево – удаление элемента из сбалансированного дерева приводит, как правило, к его перестройке); здесь необходимо рассматривать три случая: удаление листа (см. рис.4.4.а), удаление элемента с одним потомком (см. рис.4.4.б), удаление элемента с двумя потомками (см. рис.4.4.в).
При удалении элемента степени 2 из дерева поиска изменять связи необходимо так, чтобы не нарушалось установленное в дереве отношение порядка. Лучшим вариантом в этом случае будет перемещение на место удаляемого элемента либо самого правого листа из левого поддерева удаляемого элемента, либо самого левого листа из правого поддерева удаляемого элемента;
x
x
x
а
б
в
Рис.4.4
г) сравнение деревьев (проверка деревьев на равенство). Операция заключается в прохождении обоих деревьев в одном порядке до тех пор, пока либо не будут пройдены оба дерева, либо одно из них, либо соответствующие элементы окажутся не равными, либо в одном из деревьев не будет обнаружено отсутствие соответствующего элемента. Только в случае равенства деревьев оба дерева будут пройдены одновременно; д) копирование дерева. Операция заключается в прохождении исходного дерева
и построении нового дерева с элементами, информационные поля которых равны информационным полям соответствующих элементов исходного дерева.
1.2. Ввод дерева
Чтобы ввести дерево надо выбрать какой-тоспособ перечисления его узлов. Одним из возможных способов является так называемая списочная запись (представление). Список – это конечная последовательность атомов либо списков, число которых, может быть и равно нулю (атом – это понятие, определяющее элемент из любого множества предметов). Используя скобки, список можно задать перечислением через запятую его атомов (порядок перечисления атомов
определяет их упорядочение). Таким образом, дерево, представленное на рис.4.1.б можно записать в виде следующего списка:
( A, ( B, ( D, 0, 0 ), 0 ), ( C, ( E, 0, ( G, 0,0 ) ), ( F, ( H, 0, 0 ), ( I, 0, 0 ) )))
Ввод дерева, представленного таким списком, можно описать рекурсивной функцией (тип дерева btree описан выше, здесь type – тип информационного поля элемента – сhar):
btree * build_tree ( )
{char sym; btree *d;
scanf (“%c”, &sym ); switch ( sym )
{case ‘ (‘ : { d = new btree;
scanf (“%c”, &sym ); d->elem= sym;d->left= build_tree ( );
d->right= build_tree ( ); scanf( “%c”, &sym );
return d ; }
case
‘0’
: return NULL ;
case
‘,’
: d = build_tree ( ); break ;
}
}
2.Контрольные вопросы
1.Понятие дерева, двоичного дерева, упорядоченного дерева, дерева поиска.
2.Способы задания дерева.
3.Способы обхода дерева (в глубину: прямой, обратный, концевой; в ширину).
4.Показать, что бинарное дерево можно построить, если заданы прямой и обратный порядки расположения его узлов. Можно ли это сделать, если заданы прямой и концевой порядки? Если заданы обратный и концевой порядки?
5.Найдите все бинарные деревья, узлы которых располагаются точно в одной и той же последовательности а) в прямом и обратном порядках; б) в прямом и концевом порядках; в) в обратном и концевом порядках.
6.Каково наибольшее число вершин, находящихся одновременно в стеке при обходе двоичного дерева, содержащего n элементов: а) в прямом, б) обратном, в) концевом порядках?
2.Варианты задания
Во всех задачах тип значений элементов дерева простой. Исходное дерево после ввода распечатать в одном из порядков.
1.В заданном бинарном дереве подсчитать число его листьев и напечатать их значения:
а) при прямом обходе дерева;
