Лабораторная работа №2 Вариант №21
.doc
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Лабораторная работа №2
по дисциплине
«Структуры и алгоритмы»
на тему:
«АВЛ и В-Деревья»
|
|
Студент |
|
|
|
|
|
||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
|
Группа |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
Принял |
|
|
|
|
|
||||||||
|
|
|
|
|
|
Журавлева М.Г. |
|
||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
Липецк 2010
-
Задание
Осуществить программную реализацию АВЛ- или B-дерева заданного порядка, с указанным типом ключа, выбрав из табл. 2 приложения соответствующие номеру варианта исходные параметры.
Программа должна предоставлять удобный пользовательский интерфейс, позволяющий создавать дерево (формировать пользователем или генерировать автоматически) и осуществлять предусмотренные виды его обработки.
Набор функций, необходимых для работы с деревом, должен включать, как минимум: генерацию дерева, поиск с включением узла, удаление узла, удаление дерева.
-
Листинг программы
#include <conio.h>
#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <locale.h>
#include <windows.h>
struct tree
{
int key;
int h;
tree *left;
tree *right;
};
tree* add(tree *root, int x)
{
if(!root)
{
root=(tree *)malloc(sizeof(tree));
root->key=x;
root->left=0;
root->right=0;
root->h=1;
}
else if(x < root->key)
{
root->left=add(root->left, x);
if(root->h<=root->left->h)
root->h=root->left->h+1;
}
else if(x > root->key)
{
root->right=add(root->right, x);
if(root->h<=root->right->h)
root->h=root->right->h+1;
}
return root;
}
void obhod(tree *root)
{
printf("%d[%d]",root->key,root->h);
printf("(");
if(root->left)
obhod(root->left);
printf(",");
if(root->right)
obhod(root->right);
printf(")");
}
tree *hight(tree *root)
{
if(!root->left && !root->right)
{
root->h=1;
return root;
}
if(root->left)
{
root->left=hight(root->left);
root->h=root->left->h+1;
}
if(root->right)
{
root->right=hight(root->right);
if(root->h <=root->right->h)
root->h=root->right->h+1;
}
return root;
}
tree *small_right_rotate(tree *root)
{
tree *a=root;
tree *b=root->right;
a->right=b->left;
b->left=a;
a->h=1;
b->h=1;
if(a->left)
a->h=a->left->h+1;
if(a->right)
a->h=a->right->h+1;
if(a->right && a->left)
if(a->right->h > a->left->h)
a->h=a->right->h+1;
else
a->h=a->left->h+1;
if(b->left)
b->h=b->left->h+1;
if(b->right)
b->h=b->left->h+1;
if(b->right && b->left)
if(b->right->h > b->left->h)
b->h=b->right->h+1;
else
b->h=b->left->h+1;
return b;
}
tree *small_left_rotate(tree *root)
{
tree *b=root->left;
tree *a=root;
a->left=b->right;
b->right=a;
a->h=1;
b->h=1;
if(a->left)
a->h=a->left->h+1;
if(a->right)
a->h=a->right->h+1;
if(a->right && a->left)
if(a->right->h > a->left->h)
a->h=a->right->h+1;
else
a->h=a->left->h+1;
if(b->left)
b->h=b->left->h+1;
if(b->right)
b->h=b->left->h+1;
if(b->right && b->left)
if(b->right->h > b->left->h)
b->h=b->right->h+1;
else
b->h=b->left->h+1;
return b;
}
tree *big_right_rotate(tree *root)
{
tree *a=root;
tree *b=root->right;
tree *c=b->left;
a->right=c->left;
b->left=c->right;
c->left=a;
c->right=b;
a->h=1;
b->h=1;
if(a->left)
a->h=a->left->h+1;
if(a->right)
a->h=a->right->h+1;
if(a->right && a->left)
if(a->right->h > a->left->h)
a->h=a->right->h+1;
else
a->h=a->left->h+1;
if(b->left)
b->h=b->left->h+1;
if(b->right)
b->h=b->right->h+1;
if(b->right && b->left)
if(b->right->h > b->left->h)
b->h=b->right->h+1;
else
b->h=b->left->h+1;
if(a->h > b->h)
c->h=a->h+1;
else
c->h=b->h+1;
return c;
}
tree *big_left_rotate(tree *root)
{
tree *a=root;
tree *b=root->left;
tree *c=b->right;
a->left=c->right;
b->right=c->left;
c->left=b;
c->right=a;
a->h=1;
b->h=1;
if(a->left)
a->h=a->left->h+1;
if(a->right)
a->h=a->right->h+1;
if(a->right && a->left)
if(a->right->h > a->left->h)
a->h=a->right->h+1;
else
a->h=a->left->h+1;
if(b->left)
b->h=b->left->h+1;
if(b->right)
b->h=b->right->h+1;
if(b->right && b->left)
if(b->right->h > b->left->h)
b->h=b->right->h+1;
else
b->h=b->left->h+1;
if(a->h > b->h)
c->h=a->h+1;
else
c->h=b->h+1;
return c;
}
tree *balance(tree *root)
{
if(root->left && root->left->h>2)
root->left=balance(root->left);
if(root->right && root->right->h>2)
root->right=balance(root->right);
int r=0,rr=0,rl=0,rll=0,rlr=0,rrl=0,rrr=0;
r=root->h;
if(root->right)
{
rr=root->right->h;
if(root->right->left)
rrl=root->right->left->h;
if(root->right->right)
rrr=root->right->right->h;
}
if(root->left)
{
rl=root->left->h;
if(root->left->left)
rll=root->left->left->h;
if(root->left->right)
rlr=root->left->right->h;
}
if((root->right && (rr-rl)==2 && (rrl <= rrr)))
root=small_right_rotate(root);
else
if((root->left && (rl-rr)==2 && (rlr <= rll)))
root=small_left_rotate(root);
else
if(root->right && root->right->left && (rr-rl)==2 && (rrl > rrr))
root=big_right_rotate(root);
else
if(root->left && root->left->right &&(rl-rr)==2 && (rlr > rll))
root=big_left_rotate(root);
return root;
}
tree *right_most_child(tree *root)
{
if(!root->right)
return root;
else
return right_most_child(root->right);
}
tree *parent(tree *root,int key)
{
if(root->left)
{
if(key==root->left->key)
return root;
if(key<root->key)
return parent(root->left, key);
}
if(root->right)
{
if(key==root->right->key)
return root;
if(key>root->key)
return parent(root->right, key);
}
return root;
}
tree *return_key(tree *root, int key)
{
if(root)
{
if(root->key==key)
return root;
if(key<root->key)
return return_key(root->left,key);
if(key>root->key)
return return_key(root->right,key);
}
else return NULL;
}
tree *udal(tree *root,int key)
{
tree *p,*k,*r;
k=return_key(root,key);
if(k)
{
if(k->left)
r=right_most_child(k->left);
else r=NULL;
p=parent(root,key);
if(root->key==key)
if(root->left)
{
tree *n;
n=right_most_child(root->left);
n->right=root->right;
root=root->left;
return root;
}
else
{
root=root->right;
return root;
}
if(p->right==k)
if(!k->left)
p->right=k->right;
else if(!k->right)
p->right=k->left;
else
{
r->right=k->right;
p->right=k->left;
return root;
}
if(p->left==k)
if(!k->right)
p->left=k->left;
else if(!k->left)
p->left=k->right;
else
{
r->right=k->right;
p->left=k->left;
return root;
}
return root;
}
else return NULL;
}
tree *del(tree *root)
{
tree *k;
int elem;
printf("\nКакой узел вы хотите удалить?");
scanf("%d",&elem);
root=udal(root,elem);
root=hight(root);
if(root->h>2)
root=balance(root);
return root;
}
tree *generation(tree *root)
{
int n;
printf("\nВведите количество элементов: ");
scanf("%d", &n);
srand(2);
for(int i=0;i<n;i++)
root=add(root,rand()%100);
return root;
}
void main()
{
setlocale(LC_ALL,"Rus");
tree *root=NULL, *dop;
int key;
char c='1';
while(c!='0')
{
system("cls");
printf("\n1.Добавить\n2.Удалить\n3.Вывести\n4.Генерация\n5.Удалить дерево\n0.Выход\n");
c=getch();
switch(c)
{
case '1':
printf("\nВведите ключ: ");
scanf("%d",&key);
root=add(root,key);
if(root && root->h>2)
root=balance(root);
break;
case '2':
root=del(root);
break;
case '3':
if(root)
obhod(root);
getch();
break;
case '4':
root=generation(root);
if(root && root->h>2)
root=balance(root);
break;
case '5':
free(root);
root=NULL;
break;
}
}}
-
Контрольный пример
-
Блок-схема
5. Вывод
При выполнении данной лабораторной работы я получил навыки программирования сильноветвящихся деревьев.
-
Список использованной литературы
-
Шилдт Г. Искусство программирования на C++. БХВ.2005
-
Шилдт Г. C++ Руководство для начинающих. Вильямс.2005
-
Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004