75672

Ефективні методи програмування задач редагування і пошуку в послідовностях. Збалансовані дерева

Практическая работа

Информатика, кибернетика и программирование

Закріпити знання про динамічні структури даних. Сформувати навички обробки збалансованих дерев. Сформувати уміння застосовувати АВЛ-дерева для редагування і пошуку в послідовностях.

Украинкский

2015-01-24

180.05 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №8 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013


Тема: Ефективні методи програмування задач редагування і пошуку в послідовностях. Збалансовані дерева.

Мета:  Закріпити знання про динамічні структури даних. Сформувати навички обробки збалансованих дерев. Сформувати уміння застосовувати АВЛ-дерева для редагування і пошуку в послідовностях.

Завдання:

Варіант № 9.

  1.  Реалізувати описану схему збереження множин у виді збалансованого дерева, переконавшись, що вона також дозволяє обійтися C*log(n) діями для операцій включення, виключення і перевірки приналежності.

Опис алгоритму виконання

На початку програми дерева не існує (множина порожня). Користувач за допомогою клавіші Insert додає нові вузли. При цьому вони додаються рівномірно по рівнях (відбувається балансування дерева).  Вузол додається, дерево перевіряється на збалансованість. Якщо не збалансоване, то відбувається поворот дерева у протилежну дисбалансу сторону.

Складність алгоритму

Складність алгоритму дорівнює О(C*log(N)) від t,

де tчас виконання,

Nкількість вузлів дерева (елементів множини),

С – константа.


Блок-схема алгоритму


Лістинг фрагментів програми

//-----------------------------------------------------------------------------

#pragma once

class Node;

class Tree

{

public:

int num; int topY;

int leftX;

int rightX;

Node children;

Tree* parent;

Tree(int num=0);

Tree(Tree& tr);

~Tree(void);

void ShowTree(HDC hdc, int topY, int leftX, int rightX);

void Add(Tree * tr);

void addChild(Tree * tr);

void setParent(Tree * tr);

Tree* removeChild(int k);

void deleteChild(int k);

void deleteChild(Tree *tr);

int heightCount();

int Balance();

void balanceTree();

void Delete(int n);

bool insideCheck(int n);

};

class Node

{

private:

public:

Tree **arr;

int amount;

Node();

~Node();

void Push(Tree *el);

Tree* Pop(int n);

Tree* operator[](int n);

};

extern Tree *way;

//-----------------------------------------------------------------------------

#include "stdafx.h"

#include "Tree.h"

Tree *way=0;

Tree* Node::operator[](int n) {return arr[n];}

Tree::Tree(int num)

{

num=num;

parent=0;

}

Tree::Tree(Tree& tr)

{

num=tr.num;

children.arr[0]=tr.children[0];

children.arr[1]=tr.children[1];

}

Tree::~Tree(void)

{

}

void Tree::setParent(Tree * tr)

{

parent=tr;

}

void Tree::addChild(Tree * tr)

{

children.Push(tr);

tr->setParent(this);

}

Tree* Tree::removeChild(int k)

{

return children.Pop(k);

}

void Tree::deleteChild(int k)

{

delete children.Pop(k);

}

void Tree::deleteChild(Tree *tr)

{

for(int i=0;i<children.amount;++i)

{

 if(children[i]==tr)

 {

  delete children.Pop(i);

  return;

 }

}

}

const int spaceStep=40;

void Tree::ShowTree(HDC hdc,int top, int left, int right)

{

HPEN hNodePen, hrightPen, holdpen;

HBRUSH hNodeBrush, holdbrush;

hNodePen = CreatePen(PS_SOLID, 3, RGB(255, 128, 0));

hrightPen = CreatePen(PS_SOLID, 3, RGB(7, 100, 255));

holdpen = (HPEN)SelectObject(hdc, hNodePen);

 

hNodeBrush = CreateSolidBrush(RGB(255, 128, 0));

holdbrush = (HBRUSH)SelectObject(hdc, hNodeBrush);

if (this==0) return;

topY=top;

leftX=left;

rightX=right;

int x=left+(right-left)/2;

int y=top+spaceStep/2;

for(int i=0;i<children.amount;++i)

{

 if(children[i]!=0)

 {

  

  holdpen = (HPEN)SelectObject(hdc, hrightPen);

  POINT pnt;

  ::MoveToEx(hdc, x, y, &pnt);

  int x=left+(right-left)/children.amount*i+((right-(right-left)/children.amount*(children.amount-i-1))-(left+(right-left)/children.amount*i))/2;

  int y=top+spaceStep+spaceStep/2;

  ::LineTo(hdc, x, y);

 }

}

holdpen = (HPEN)SelectObject(hdc, hNodePen);

Ellipse(hdc, x-20, y-20, x+20, y+20);

char buf[50];

_itoa(num,buf,10);

::TextOutA(hdc, x-5, y-8, (LPCSTR) buf, strlen(buf) );

 

for(int i=0;i<children.amount;++i)

{

 if(children[i]!=0)

 {

  children[i]->ShowTree(hdc,top+spaceStep,left+(right-left)/children.amount*i,right-(right-left)/children.amount*(children.amount-i-1));

  

 }

}

::DeleteObject(hNodePen);

::DeleteObject(hrightPen);

::DeleteObject(hNodeBrush);

}

Node::Node()

{

amount=2;

arr=new Tree*[amount];

for(int i=0;i<amount;++i)arr[i]=0;

}

Node::~Node()

{

 

}

void Node::Push(Tree *el)

{

Tree ** tmp=new Tree*[amount+1];

for(int i=0;i<amount;++i)

{

 tmp[i]=arr[i];

}

tmp[amount]=el;

++amount;

delete [] arr;

arr=tmp;

}

Tree* Node::Pop(int n)

{

Tree ** tmp=new Tree *[amount-1];

int k=0;

Tree* temp;

for(int i=0;i<amount;++i)

{

 if(i!=n)

 {

  tmp[k]=arr[i];

  ++k;

 }

}

temp=arr[n];

delete [] arr;

arr=tmp;

--amount;

return temp;

}

int Tree::heightCount()

{

if(this==0)return 0;

return max(children[0]->heightCount(),children[1]->heightCount())+1;

}

int Tree::Balance()

{

return children[0]->heightCount()-children[1]->heightCount();

}

enum Rot

{

left=0,

right

};

void Rotate(Tree * parent,Rot direction)

{

if(direction==left)

{

 Tree *tmp=new Tree(*parent);

 parent->children.arr[0]=tmp;

 tmp->children.arr[1]=parent->children[1]->children[0];

 parent->num=parent->children[1]->num;

 tmp=parent->children.arr[1];

 parent->children.arr[1]=parent->children[1]->children[1];

 delete tmp;

 return;

}

 

if(direction==right)

{

 Tree *tmp=new Tree(*parent);

 parent->children.arr[1]=tmp;

 tmp->children.arr[0]=parent->children[0]->children[1];

 parent->num=parent->children[0]->num;

 tmp=parent->children.arr[0];

 parent->children.arr[0]=parent->children[0]->children[0];

 delete tmp;

 return;

}

}

void Tree::balanceTree()

{

while(Balance()<-1)Rotate(this,left);

while(Balance()>1)Rotate(this,right);

}

void Tree::Add(Tree * tr)

{

if(tr->num<this->num&&Balance()>0)

{

 Rotate(this,right);

}

else

{

 if(tr->num>this->num&&Balance()<0)

 {

  Rotate(this,left);

 }

}

if(tr->num<this->num)

{

 if(children[0]==0)children.arr[0]=tr;

 else

  children[0]->Add(tr);

 return;

}

if(tr->num>this->num)

{

 if(children[1]==0)children.arr[1]=tr;

 else

  children[1]->Add(tr);

 return;

}

 

}

void Tree::Delete(int n)

{

if(children[0]!=0&&children[0]->num==n)

{

 Tree*tmp=children[0];

 if(children[0]->children[0]!=0)

 {

  children.arr[0]=children[0]->children[0];

  if(tmp->children[1]!=0)children[0]->Add(tmp->children[1]);

 }

 else

 {

  children.arr[0]=children[0]->children[1];

  if(children[0]!=0&&tmp->children[0]!=0)children[0]->Add(tmp->children[0]);

 }

 balanceTree();

 return;

}

if(children[1]!=0&&children[1]->num==n)

{

 Tree*tmp=children[1];

 if(children[1]->children[0]!=0)

 {

  children.arr[1]=children[1]->children[0];

  if(tmp->children[1]!=0)children[1]->Add(tmp->children[1]);

 }

 else

 {

  children.arr[1]=children[1]->children[1];

  if(children[1]!=0&&tmp->children[0]!=0)children[1]->Add(tmp->children[0]);

 }

 balanceTree();

 return;

}

for(int i=0;i<children.amount;++i)if(children[i]!=0)children[i]->Delete(n);

}

bool Tree::insideCheck(int n)

{

if(this==0)return false;

if(num==n)return true;

if(children[0]->insideCheck(n))return true;

if(children[1]->insideCheck(n))return true;

return false;

}


Результат виконання

Висновки

Закріпили знання про динамічні структури даних. Сформували навички обробки збалансованих дерев. Сформували уміння застосовувати АВЛ-дерева для редагування і пошуку в послідовностях. У ході виконання практично роботи створено алгоритм балансування дерева для зберігання підмножин.


 

А также другие работы, которые могут Вас заинтересовать

1480. Проектирование металлических конструкций при строительстве здания 355.91 KB
  Расчет прокатных балок. Расчетная толщина сварочного углового шва. Расчетная нагрузка на вспомогательную балку. Требуемая площадь поясных горизонтальных листов. Расчет монтажного стыка сварной балки. Стык на высокопрочных болтах.
1481. ДЕРИВАЦИОННЫЕ ОСОБЕННОСТИ В СФЕРЕ СОВРЕМЕННОГО НАРЕЧНОГО ОБРАЗОВАНИЯ 342.23 KB
  Оценить продуктивность типов производства слов наречного класса, обратив внимание на изменение в этом аспекте по сравнению с прежними показателями. На основе изученного материала выявить наиболее активные процессы в современном наречном словообразовании. Установить специфику деривационных процессов при производстве слов наречного класса в сленге.
1482. Дискурсивно-лингвистические аспекты искусственного билингвизма 343.72 KB
  Проанализировать существующие точки зрения по проблематике исследования, уточнив соотношение понятия билингвизм со смежным понятием диглоссия. Определить содержание понятия дискурсивно-лингвистическая компетенция билингвов. Установить и описать генезис переводческих механизмов у студентов-билингвов на разных ступенях обучения посредством уточнения понятия единицы перевода.
1483. КОГНИТИВНЫЕ МОДЕЛИ СУБСТАНДАРТНОЙ СЕМАНТИЧЕСКОЙ ДЕРИВАЦИИ 344.53 KB
  Цель диссертационной работы заключается в определении семантической структуры субстандартных дериватов английского и русского языков и установлении системы когнитивных моделей субстандартных глаголов умственной деятельности указанных языков с точки зрения когнитивной лингвистики.
1484. СПЕЦИАЛИЗИРОВАННАЯ ПСИХОЛОГИЧЕСКАЯ ПОМОЩЬ ВЫПУСКНИКАМ КЛАССОВ КОРРЕКЦИОННО-РАЗВИВАЮЩЕГО ОБУЧЕНИЯ С КОНСТИТУЦИОНАЛЬНО-ТИПОЛОГИЧЕСКОЙ ПРЕДИСПОЗИЦИЕЙ ЛИЧНОСТИ 1018.64 KB
  Теоретическое обоснование проблемы конституционально-психотипологической предиспозиции личности в российской психологии. Материал, методы исследования и психологического сопровождения выпускников классов коррекционно-развивающего (компенсирующего) обучения, имеющих конституционально-психотипологическую предиспозицию личности. Сравнительный эмпирический и экспериментально-психологический анализ обследованных подростков.
1485. ПСИХОЛОГО-ПЕДАГОГИЧЕСКОЕ СОПРОВОЖДЕНИЕ ДЕТЕЙ-СИРОТ КАК СРЕДСТВО ИХ СОЦИАЛИЗАЦИИ 1017.35 KB
  Научно-теоретические основы психолого-педагогического сопровождения детей-сирот в условиях детского дома. Организационно-содержательные условия психолого- педагогического сопровождения детей-сирот в условиях детского дома. Модель психолого-педагогического сопровождения детей-сирот в условиях детского дома.
1486. СИМВОЛИКА АРХИТЕКТУРНОГО ЛАНДШАФТА МОСКОВСКОГО КРЕМЛЯ И ОСТРОВА СИТЕ (ПАРИЖ) В ВОСПРИЯТИИ ПРЕДСТАВИТЕЛЕЙ РОССИЙСКИХ И ФРАНЦУЗСКИХ СУБКУЛЬТУР ХIХ – НАЧАЛА ХХ ВВ. 1016.13 KB
  Восприятие символики архитектурных ландшафтов: теоретический обзор в контексте исследования Символика архитектурного ландшафта Московского Кремля в восприятии представителей французских субкультур начала - середины XIX в. Символика архитектурного ландшафта острова Сите в восприятии представителей российских субкультур начала ХIХ в.
1487. СОВЕРШЕНСТВОВАНИЕ ГОСУДАРСТВЕННОГО РЕГУЛИРОВАНИЯ ИННОВАЦИОННОЙ ДЕЯТЕЛЬНОСТИ В ПРОМЫШЛЕННОСТИ 1014.86 KB
  Инновационное развитие в современной экономике (теоретический аспект). Инновационное развитие в промышленности Хабаровского края. Формы и механизмы государственного регулирования инновационной деятельности.
1488. СОВЕРШЕНСТВОВАНИЕ БИОТЕХНОЛОГИИ ПРОИЗВОДСТВА ПИТАТЕЛЬНЫХ СРЕД ДЛЯ КУЛЬТИВИРОВАНИЯ ЧУМНОГО МИКРОБА НА ОСНОВЕ СЫРЬЯ ЖИВОТНОГО И РАСТИТЕЛЬНОГО ПРОИСХОЖДЕНИЯ 1010.59 KB
  Среды на основе сырья животного происхождения и их использование при культивировании чумного микроба. Разработка ускоренного способа приготовления ферментативных мясных гидролизатов. Оценка качества сред по пигменто- и индолообразованию тест-штаммов. Сравнительное изучение ростовых качеств питательных сред, приготовленных с использованием ферментативного гидролизата сои (бобов).