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;

}


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

Висновки

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


 

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

43254. Разработка импульсного источника вторичного электропитания электронно-вычислительной аппаратуры 1014.5 KB
  Источники вторичного электропитания предназначены для получения заданной мощности в нагрузке при определённом заранее преобразования энергии. Требуемая мощность часто оказывается значительной, и поэтому повышение плотности упаковки электронных элементов не оказывает прямого и решающего влияния на миниатюризацию ИВЭП. Миниатюризация потребителей энергии не приводит к увеличению относительного объёма ИВЭП в системе, если их миниатюризация не осуществляется одновременно и с такой же эффективностью.
43255. Исследование методов сортировки с поиском минимума и деревом 211 KB
  Простейшая задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием. Обычно в качестве такого критерия выступают значения определенной функции, аргументами которой выступают элементы массива. В работе приводится постановка задачи сортировки и поиска данных, описание алгоритмов, описание программы и правила ее использования, а также прилагается текст программы, решающей поставленную задачу.
43256. Расчет гидропривода 486 KB
  Под гидроприводом понимают совокупность устройств, предназначенных для приведения в движение механизмов и машин посредством рабочей жидкости под давлением. В качестве рабочей жидкости в станочных гидроприводах используется минеральное масло.
43257. Схема для живлення переговорного пристрою 624.5 KB
  Аналізуючи ці схеми, можна впевнитися, що дана схема є найбільш актуальною у розробці, порівняно з її аналогами, приведеними нижче. Схема, що розробляється, призначена для живлення, як потужної так і малопотужної апаратури, залежно від максимально допустимого рівня пульсації на вході. З точки зору схемотехнічного проектування виробу, дана схема є найбільш простою, так як має найменшу кількість елементів, та не має потужних елементів схеми, які присутні в двох аналогічних схемах.
43258. Разработка и расчет законченного электронного устройства 669 KB
  Датчиком температуры описываемого прибора служит кремниевый диод. При этом используется линейная зависимость паления напряжения на нем от температуры при фиксированном прямом токе смешения. Температурный коэффициент напряжения (ТКН) для кремниевых диодов практически постоянен в диапазоне -60...+ 100°С и составляет -2...-2,5 мВ/°С — в зависимости от типа диода и значения тока смешения. Как показали исследования, практически любой кремниевый диод или транзистор может быть использован как линейный температурный преобразователь в диапазоне от -55-С до+125°С.
43259. Разработка усилителя низкой частоты 5.43 MB
  Рассчитаем максимальное напряжение в нагрузке по формуле: В Определим максимальный ток протекающий через нагрузку: Рассчитаем требуемый коэффициент усиления усилителя по формуле: Определим ориентировочное количество каскадов предварительного усиления по следующей формуле: Полученное по формуле количество каскадов округляют до ближайшего целого нечетного числа так как схема с ОЭ дает сдвиг фаз 180 n = 3 Выходной каскад ставится на выходе усилителя и обеспечивает усиление мощности полезного сигнала в нагрузку.4...
43260. Проектирование усилительного устройства 205 KB
  Курсовая работа содержит 12 листов текста 2 чертежа 3 источника литературы Содержание Предварительный расчет Структурная схема усилителя Расчет элементов схемы Расчет усилителя мощности Описание схемы электрической принципиальной Выбор схемы блока питания Список используемой литературы Введение Основной задачей курсового проекта является разработка схемы электрической принципиальной усилительного устройства по заданным параметрам а так же освоение практических навыков в области проектирования для более...
43261. Проектирование усилительного устройства 224.5 KB
  Основной задачей курсового проекта является разработка схемы электрической принципиальной усилительного устройства по заданным параметрам, а так же освоение практических навыков в области проектирования, для более близкого знакомства со всеми этапами разработки электрической схемы
43262. Розрахунок та побудова кривих швидкості і часу ходу поїзда 833.5 KB
  Перевірка розрахункової маси поїзда на можливість надійного подолання підйому крутість якого перевищує крутість розрахункового підйому. Перевірка розрахованої маси поїзда на зрушення з місця. Перевірка маси поїзда по довжині колій станцій Спрямлення профілю колії. Розрахунок та побудова кривих швидкості і часу ходу поїзда.