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;

}


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

Висновки

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


 

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

29982. Восприятие. Общая характеристика 88 KB
  Восприятие – это отражение в сознании человека предметов или явлений при их непосредственном воздействии на органы чувств. Маклаков Восприятие включает в себя ощущение и основывается на нём. Поэтому восприятие очень часто называют перцептивной системой человека. из гештальта пр восприятие мелодии 4.
29983. Основные подходы к изучению восприятия в зарубежной психологии 57 KB
  Основные подходы к изучению восприятия в зарубежной психологии. Помимо ощущений в процессе восприятия задействован предыдущий опыт процессы осмысления того что воспринимается т. Мир восприятия состоит из: 1ощущений которые возникают когда раздражается отдельный рецептор и 2 образов памяти которые представляют собой следы прежних ощущений Если 2 ощущения повторялись совместно много раз и если затем возникает ощущение или образ памяти то сразу же появляется образ памяти другого ощущения. И для того чтобы объяснить все виды...
29984. Внимание. Общая характеристика 61.5 KB
  Виды внимания. Добрынин О теории и воспитании внимания Свойства внимания. Концентрированность внимания – выделение сознанием объекта и направление на него внимания. Объем внимания можно увеличить если осмысленно связать и структурировать материал.
29985. Основные подходы к изучению памяти в зарубежной психологии 67 KB
  Основные подходы к изучению памяти в зарубежной психологии. Ассоциативная теория памяти: Ассоциация осн. Этот метод предоставляет возможности для изучения ассоциативных механизмов памяти. Метод разработан для изучения динамики изменения памяти и особенно забывания во времени.
29986. Основные факты и закономерности памяти 54.5 KB
  Основные факты и закономерности памяти Память запечатление сохранение последующее узнавание и воспроизведение следов прошлого опыта. Классические методы и основные результаты исследования памяти Первые экспериментальные методы изучения мнемических процессов были предложены Эббингаузом 19 век. Этот метод предоставляет возможности для изучения ассоциативных механизмов памяти. Метод разработан для изучения динамики изменения памяти и особенно забывания во времени.
29987. Память и деятельность 43.5 KB
  Подавляющее большинство наших систематических знаний возникает в результате специальной деятельности цель которой запомнить соответствующий материал чтобы сохранить в памяти. Исследование мнемической деятельности – одна из ЦЕНТРАЛЬНЫХ ПРОБЛЕМ В ПСИХОЛОГИИ. Произвольное запоминание – основа мнемической деятельности. Переход от одной сферы деятельности в которую включено намерение к другой – может привести за собой забывание этого намерения.
29988. РЕШЕНИЕ ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ 5.23 MB
  Эти значения x называются корнями уравнения 3. ak например для уравнения вида ax2 bx c = 0 его корни выражаются формулой: . В большинстве же случаев аналитическую запись корней уравнения найти очень сложно или в принципе невозможно такие уравнения называются трансцендентными и поэтому приходится решать уравнение численным способом. Отделение корней На данном этапе определяются те интервалы области изменения переменной x в каждом из которых расположен один и только один корень уравнения 3.
29989. Таинственное похищение Первого звонка. Сценарий праздника 1 сентября 179.11 KB
  Сценарий праздника 1 сентября Действующие лица Первый звонок Витя Петя Четверка Пятерка Двойка Единица Клякса Маша Флеш моб танец Первый ведущий. На сцену выходит Первый звонок. Первый звонок. Здравствуйте ребята вы меня я надеюсь узнали Да я ваш добрый знакомый Первый Школьный Звонок.
29990. СЦЕНАРІЙ СВЯТА ПЕРШОГО ДЗВОНИКА 130.46 KB
  Зріє жито молодеДружно з квітами до школиЗнову молодість іде Ведучий 2:Вересень немов учительДвері школи відчинивШколярів дзвінком врочистимДо навчання запросив Ведучий 1: Здрастуй школо здрастуй ріднаЗдрастуй любий класВ першовересень привітноТи стрічаєш нас Ведучий 2: Пахнуть фарбою класи просторіОй як хочеться вже до книжокМи від степу і синього моряВсі злетілись на перший урок Ведучий 1: Я не знаю хвилини врочистішеЩасливіших не бачив очей.Подивіться як урочистоМалюки зустрічають цей день Ведучий 1: На лінійку запрошуються...