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;

}


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

Висновки

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


 

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

72559. К ВОПРОСУ ОБ ОПРЕДЕЛЕНИИ ОБЪЕКТА УПРОЩЕННОЙ СИСТЕМЫ НАЛОГООБЛОЖЕНИЯ 192 KB
  Популярность упрощенной системы налогообложения УСНО возрастает с каждым днем. Например если у налогоплательщика сумма остаточной стоимости основных средств и нематериальных активов довольно большая в качестве объекта налогообложения выбирать доходы не выгодно так как организация...
72560. ДИДАКТИЧЕСКИЕ ПРОБЛЕМЫ ПРЕПОДАВАНИЯ СПЕЦКУРСА «ГОСУДАРСТВЕННАЯ СЛУЖБА В ОРГАНАХ ВНУТРЕННИХ ДЕЛ» 82 KB
  Государственно-служебное отношение как отношение специального характера с одной стороны налагает на сотрудников органа внутренних дел милиции особые обязанности а с другой предоставляет им определенные права. В своей совокупности взаимные права и обязанности государства и сотрудников органов внутренних дел...
72561. ГРАЖДАНСКИЙ ПРОЦЕСС В ДРЕВНЕРУССКОМ ГОСУДАРСТВЕ 117 KB
  Гражданско-процессуальное право как отрасль права сформировалось гораздо позднее на другом этапе развития российской системы права. Об их наличии свидетельствуют источники древнерусского права. Дювернуа отмечал: В суде гражданском лицо ищет или восстановления своего вещного права или требует...
72562. Правовые системы России и Белоруссии и правовая культура 94 KB
  Одна из актуальных задач юридической науки исследование закономерностей и тенденций культурно-правового прогресса в исторической ретроспективе. Союзное государство должно стать наследником и продолжателем российской государственности новым звеном в цепи: Русь Российская Империя Российская Советская...
72563. КОНСТИТУЦИОННО-ПРАВОВОЙ СТАТУС ЦЕНТРАЛЬНОГО БАНКА РОССИЙСКОЙ ФЕДЕРАЦИИ 128 KB
  В статье 75 Конституции где говорится о Центральном банке устанавливается что денежная эмиссия осуществляется исключительно Центробанком России. Таким образом Конституция во-первых выделяет основную функцию Банка России и во-вторых причисляет его к органам государственной власти.
72564. ГРАЖДАНСКО-ПРАВОВАЯ ПРИРОДА ДОГОВОРА АРЕНДЫ 145 KB
  По договору аренды имущественного найма арендодатель наймодатель обязуется предоставить арендатору нанимателю имущество за плату во временное владение и пользование или во временное пользование. Договор аренды входит в группу договоров регулирующих отношения по передаче имущества во временное пользование.
72565. ПРОБЛЕМЫ ПРИМЕНЕНИЯ МЕР ГОСУДАРСТВЕННОГО ПРИНУЖДЕНИЯ (ВОЗДЕЙСТВИЯ) ЗА НАРУШЕНИЕ БЮДЖЕТНОГО ЗАКОНОДАТЕЛЬСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ 104.5 KB
  Указанное обстоятельство в свете известных организационных политических криминалистических и других проблем функционирования бюджетной системы Российской Федерации и развития системы бюджетного федерализма подчеркивает насущность задачи совершенствования механизма правовой...
72566. ПРАВОВЫЕ МОДЕЛИ ПОСТРОЕНИЯ СИСТЕМ БЮДЖЕТНОГО КОНТРОЛЯ В ЕВРОПЕЙСКИХ СТРАНАХ 104 KB
  Специальные контрольные органы призванные проводить мероприятия направленные на защиту бюджетных интересов созданы и функционируют в большинстве стран мира но далеко не во всех. Ранее же вопросами бюджетного контроля занималась королевская полиция островов.
72567. СОВРЕМЕННЫЕ ТЕНДЕНЦИИ РАЗВИТИЯ ЖИЛИЩНЫХ ПРАВООТНОШЕНИЙ 185.5 KB
  До принятия Жилищного кодекса РСФСР под жилищными правоотношениями обычно понимались лишь гражданско-правовые отношения по пользованию гражданами жилыми помещениями и эти отношения регулировались гражданским законодательством.