1. Написать программу передвижения элемента на n позиций.
2. Создать копию списка.
3. Добавить элемент в начало списка.
4. Склеить два списка.
5. Удалить n-ый элемент из списка.
6. Вставить элемент после n-го элемента списка.
7. Создать список содержащий элементы общие для двух списков.
8. Упорядочить элементы в списке по возрастанию.
9. Удалить каждый второй элемент списка.
10. Удалить каждый третий элемент списка.
11. Упорядочить элементы списка по убыванию.
12. Очистить список.
Кольцевые списки
13. Дан кольцевой список, содержащий 20 фамилий игроков футбольной команды. Разбить игроков на 2 группы по 10 человек. Во вторую группу попадает каждый 2-й человек.
14. Даны 2 кольцевых списка, содержащие фамилии спортсменов двух фехтовальных команд. Произвести жеребьевку. В первой команде выбирается каждый n-й игрок, а во второй - каждый m-й.
15. Задача Джозефуса: n воинов из одного войска убивают каждого m-го из другого. Требуется определить номер k начальной позиции воина, который должен будет остаться последним.
16. Даны 2 кольцевых списка, содержащие фамилии участников лотереи и наименования призов. Выиграет N человек (каждый К-й). Число для пересчета призов - t. Вывести фамилии выигравших.
17. Даны 2 списка, содержащих фамилии учащихся и номера экзаменационных билетов. Число пересчета для билетов - Е, для учащихся - К. Определить номера билетов, вытащенных учащимися.
18. Дан список, содержащий перечень товаров. Из элементов 1-го списка (товары изготовленные фирмой SONY) создать новый список.
19. Даны 2 списка, содержащие фамилии студентов 2-х групп. Перевести L студентов из 1-й группы во вторую. Число пересчета -К.
20. Даны 2 списка, содержащие перечень товаров, производимых концернами BOSH и FILIPS. Создать список товаров, выпускаемых как одной, так и другой фирмой.
21. Даны 2 списка, содержащие фамилии футболистов основного состава команды и запасного. Произвести К замен.
22. Даны 2 списка, содержащие фамилии солдат 1-го и 2-го взводов. Во время атаки М человек из 1-го взвода погибли. Произвести пополнение солдатами 2-го взвода.
23. Даны 2 списка, содержащие перечень товаров и фамилии покупателей. Каждый N-й покупатель покупает М-й товар. Вывести список покупок.
24. Даны 2 списка, содержащие наименования товаров, выпускаемых фирмами SONY и SHARP. Создать список конкурирующих между собой товаров.
Составить отчет по лабораторной работе, и защитить его у преподавателя
Рекурсивные структуры данных
Лабораторная работа №3 (4 часа). Бинарные деревья (создание и обход)
Цель работы:
- исследовать и изучить основные процедуры, используемые при работе с бинарными (двоичными) деревьями;
- овладеть умениями и навыками написания программ по исследованию бинарных деревьев на языке программирования С++.
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к работе с бинарными деревьями;
- ответить на контрольные вопросы по знанию теории;
- получить задание на выполнение конкретного варианта лабораторной работы у преподавателя и разработать алгоритм решения задачи;
- написать и отладить программу решения задачи на языке С++;
- подготовить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
Дерево - это нелинейная связанная структура данных, характеризуемая следующими признаками:
· дерево имеет один элемент, на который нет ссылок от других элементов. Этот элемент, или "узел", называется корнем дерева;
· в дереве можно обратиться к любому элементу путем прохождения конечного числа ссылок (указателей);
· каждый элемент дерева связан только с одним предыдущим элементом.
Каждый узел дерева может быть промежуточным (элементы 2,3,5,7) либо терминальным ("листом" дерева) (элементы 4,9,10,11,8,6). Характерной особенностью терминальных узлов является отсутствие ветвей.
Элемент Y, находящийся непосредственно ниже элемента X, называется непосредственным потомком X, если X находится на уровне i , то говорят, что Y лежит на уровне i+1. Считается, что корень лежит на уровне 0.
Число непосредственных потомков элемента называется его степенью исхода, в зависимости от степени исхода узлов деревья классифицируют:
A. Если степень исхода узлов - М, то дерево называется М-арным ;
B. Если степень исхода узлов - М или 0, то - полное М-арное дерево;
C. Если степень исхода узлов дерева равна 2, то дерево называется бинарным ;
D. Если степень исхода равна 2 или 0, то - полное бинарное дерево.
Особенно важную роль играют бинарные деревья, поэтому далее мы будем рассматривать их более подробно.
Представление деревьев в памяти ЭВМ
Деревья наиболее удобно представлять в памяти ЭВМ в виде связанных нелинейных списков. Элемент должен содержать INFO-поле, где содержится характеристика узла. Следующее поле определяет степень исхода узла и количество полей указателей равное степени исхода. Каждый указатель элемента ориентирует данный элемент-узел с его сыновьями. Узлы, в которые входят стрелки от исходного элемента, называются его сыновьями.
INFO-поле содержит два поля : поле записи (rec) и поле ключа (key). Ключ задается числом, по ключу определяют место элемента в дереве.
Сведение m-арного дерева к бинарному
1. В каждом узле дерева отсекают все ветви, кроме крайних левых, соответствующих старшим сыновьям;
2. Соединяют горизонтальными линиями сыновей одного родителя (узла);
3. Старшим сыном в каждом узле полученной структуры будет узел под обрабатываемым узлом.
Построение бинарных деревьев. Согласно представлению деревьев в памяти ЭВМ каждый элемент (узел бинарного дерева) будет записью, содержащей четыре поля. Значением этих полей будут соответственно
- ключ записи,
- ссылка
· на элемент влево-вниз,
· на элемент вправо-вниз и
· на текст записи.
При построении необходимо помнить, что левый сын имеет ключ меньше чем отец (родитель). Значение ключа правого сына больше значения ключа отца.
Если узлы дерева имеют значения 6, 21, 48, 49, 52, 86, 101, то бинарное дерево может иметь вид, изображенный на рисунке ниже. Это упорядоченное бинарное дерево с минимальным числом уровней. Идеально сбалансированное дерево - это дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не больше, чем на единицу.
Алгоритмы
Алгоритм создания бинарного дерева (псевдокод)
Для построения дерева необходимо создать в памяти ЭВМ элемент следующего типа:
P, Q - рабочие указатели
V=maketree(key,rec) - процедура, которая создает сегмент ключа и записи
P=getnode - генерация нового элемента
r=rec
k=key
V=P
left=nil
right=nil
tree - указатель на корень дерева
Введем сначала первое значение ключа, потом процедурой maketree сгенерируем сам элемент узла дерева. Далее идем по циклу до тех пор, пока указатель не передвинется на нулевое значение.
read (key, rec)
tree = maketree(key, rec)
while not eof do
p = tree
q = tree
read (key, rec)
v = maketree(key, rec)
while p <> nil do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if p=nil then writeln (‘ Это корень ’)
tree=v
else
if key < k(q) then
left(q) = v
else
right(q) = v
endif
endif
endwhile
return
Если по этому алгоритму строить упорядоченное бинарное дерево, то при поступлении ключей в последовательности 14, 18, 6, 21, 1, 13, 15 получим дерево, изображенное на рисунке ниже.
Для того, чтобы просмотреть элементы созданного дерева, необходимо выполнить его обход.
Алгоритм "обхода" дерева
Пусть задано бинарное дерево:
Существуют три принципа обхода бинарных деревьев. Рассмотрим их на примере заданного дерева:
1) Обход сверху вниз (корень посещается ранее, чем поддеревья): A, B, C;
2) Слева направо: B, A, C;
3) Снизу вверх (корень посещается после поддеревьев): B, C, A.
Наиболее часто применяется 2-ой способ, узлы посещаются в порядке возрастания значения их ключа.
Рекурсивные процедуры обхода дерева:
1) PROCEDURE pretrave (tree)
IF tree<>nil
THEN PRINT info (tree)
tree=left (pretrave (tree))
tree=right (pretrave (tree))
END IF
RETURN
2) PROCEDURE intrave (tree)
IF tree<>nil
THEN tree=left (intrave (tree))
PRINT info (tree)
tree=right (intrave (tree))
END IF
RETURN
3) PROCEDURE postrave (tree)
IF tree<>nil
THEN tree=left (postrave (tree))
tree=right (postrave (tree))
PRINT info (tree)
END IF
RETURN
Контрольные вопросы по теории (бинарные деревья /создание и обход/)
1. Для включения новой вершины в дерево нужно найти узел, к которому её можно присоединить. Узел будет найден, если очередной ссылкой, определяющей ветвь дерева, в которой надо продолжать поиск, окажется ссылка:
- p=right(p);
- p=nil;
- p=left(p).
2. Для написания процедуры над двумя деревьями необходимо описать элемент типа запись, который содержит поля:
- Element=Запись
Left,Right : Указатели
Rec : Запись;
- Element=Запись
Left : Указатель
Key : Ключ
Rec : Запись;
- Element=Запись
Left, Right : Указатели
Кеу : Ключ
Rec : Запись.
3. В памяти ЭВМ бинарное дерево удобно представлять в виде:
- связанных линейных списков;
- массивов;
- связанных нелинейных списков.
4. Элемент t, на который нет ссылок:
- корнем;
- промежуточным;
- терминальным (лист).
5. Дерево называется полным бинарным, если степень исходов вершин равна:
- 2 или 0;
- 2;
- m или 0;
- m.
Примеры алгоритмов конкретных задач
Рассмотрим, как операции создания бинарного сбалансированного дерева и его обхода реализуются на языке программирования С++. Для упрощения примера будем использовать дерево, поле записи которого содержит только ключи, являющиеся вещественными числами, тогда элемент дерева описывается следующим образом:
struct element
{ double k;
element* left;
element * right ;
};
Далее необходимо ввести указатель вершины дерева и рабочие указатели для реализации функции создания дерева.
element *tree=NULL,*P,*Q;
Пока дерево не создано, указатель корня нулевой (*tree=NULL).
Ниже представлена функция создания бинарного дерева
void maketree(double a) //создание дерева
{ if(!tree)
{ tree=new element;
tree->k=a;
tree->right=tree->left=NULL;
P=tree;
Q=NULL;
return;
};
P=Q=tree;
while (P!=NULL)
{ Q=P;
if(a<P->k) P=P->left; else P=P->right;
};
if(a<Q->k) { Q->left=new element;
Q->left->k=a;
Q->left->left=Q->left->right=NULL;
}
else { Q->right=new element;
Q->right->k=a;
Q->right->left=Q->right->right=NULL;
};
}
В теоретической части лабораторной работы были рассмотрены 3 вида обхода бинарного дерева. Алгоритм наиболее часто используемого вида обхода слева-направо на С++ для созданного выше дерева будет иметь следующий вид:
void printree(element* tree) //просмотр и печать дерева
{ if(tree)
{ printree(tree->left);
cout<<tree->k<<" ";
printree(tree->right);
};
}
Теперь рассмотрим листинг готовой программы, которая позволяет создать описанное выше бинарное и выполнить его обход слева направо.
//Листинг программы на С++.
#include<iostream.h>
#include<conio.h>
struct element
{ double k;
element* left;
element* right;
};
element *tree=NULL,*P,*Q;
void maketree(double a) // создание дерева
{ if(!tree)
{ tree=new element;
tree->k=a;
tree->right=tree->left=NULL;
P=tree;
Q=NULL;
return;
};
P=Q=tree;
while (P!=NULL)
{ Q=P;
if(a<P->k) P=P->left; else P=P->right;
};
if(a<Q->k) { Q->left=new element;
Q->left->k=a;
Q->left->left=Q->left->right=NULL;
}
else { Q->right=new element;
Q->right->k=a;
Q->right->left=Q->right->right=NULL;
};
}
void printree(element* tree) // просмотр и печать дерева
{ if(tree)
{ printree(tree->left);
cout<<tree->k<<" ";
printree(tree->right);
};
}
void main()
{ clrscr();
double a,key;
cout <<"Введите элеметы дерева , 0 - конец ввода: "; cin >> a ;
while(a)
{ maketree(a);
cin>>a;
};
printree ( tree );
getch ();
}
Данный листинг позволяет создавать бинарное дерево с вещественными ключами до того момента, пока мы не прервем процесс ввода его элементов, после чего выполняет обход дерева слева направо с выдачей ключей на экран.
На практике часто может возникать необходимость добавления и удаления элементов в уже существующее дерево, что не является возможным при использовании вышеописанной программы. Функции поиска, вставки и удаления элементов из бинарного дерева будут рассмотрены в лабораторной работе № 6.
Задания
1. Описать процедуру или функцию, которая:
a) присваивает параметру Е запись из самого левого листа непустого дерева Т (лист-вершина, из которого не выходит ни одной ветви);
b) определяет число вхождений записи Е в дерево Т.
2. Вершины дерева вещественные числа. Описать процедуру или функцию, которая:
a) вычисляет среднее арифметическое всех вершин дерева;
b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).
3. Записи вершин дерева - вещественные числа. Описать процедуру, которая выбирает все вершины с отрицательными записями и строит из них новое дерево.
4. Записи вершин дерева - вещественные числа. Описать процедуру или функцию, которая:
a) находит максимальное или минимальное значение записей вершин непустого дерева;
b) печатает записи из всех листьев дерева.
5. Описать процедуру или функцию, которая:
a) определяет, входит ли вершина с записью Е в дерево Т;
b) если такая запись не найдена, то она добавляется.
6. Описать процедуру или функцию, которая:
a) находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с записью Е; если Е не входит в Т, то за ответ принять - 1.
b) определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.
7. Описать процедуру СОРY(Т,Т1), которая строит Т1 - копию дерева Т.
8. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям другого дерева).
9. Описать процедуру, которая:
a) присваивает переменной b типа char значение:
К - если вершина - корень,
П - если вершина - промежуточная вершина,
Л - если вершина - лист;
b) распечатывает атрибуты всех вершин дерева.
10. Описать процедуру, которая:
a) находит максимальное или минимальное значение записей листьев непустого дерева;
b) добавляет элемент с данной записью в дерево.
11. Описать процедуру или функцию, которая:
а) вставляет узел с записью Е в дерево, если ранее такой не было;
b) считает и выдает на экран сумму значений всех ключей, если такая запись есть.
12. Описать процедуру или функцию, которая:
а) печатает запись, встречающуюся в дереве один раз;
b) печатает запись, встречающееся в дереве максимальное число раз.
Дата: 2019-12-10, просмотров: 750.
