Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.05.2013, 16:07   #1
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию Деревья, прям целый лес (сбалансированные и пирамидальные)

Добрый день\вечер, уважаемые программисты!

Вот какие у меня вопросы...


ВОПРОС 1
Вообще, мне нужно написать сбалансированное бинарное дерево, (heapsort вроде бы сделала), но пока читала в интерете про сбалансированные, наткнулась на странную вещь.

Чтобы сделать дерево, пусть это будет пирамидальная сортировка, нужно взять корень. А потом там сыновей выбирать. А потом их сравнивать, а если что-то не так, то вызывать функцию ещё раз, ещё раз... (т.е., использовать где-то там рекурсию).

А я сделала пирамидальную сортировку (надеюсь, что это всё-таки пирамидальная сортировка) без рекурсии. Нашла алгоритм в интернете (псевдокод) и по нему написала алгоритм. Суть алгоритма, что берёшь не с середины корень, а прям с первого элемента. И наращивание на 2*i и 2*i+1. Но у меня нет рекурсии. Я строю из половины массива "дерево", потом "добавляю" в него новые элементы, меняя его с головой, будто бы наращивая размер массива (а по сути, просто двигаюсь по i>n/2). Но отсутствие рекурсии меня, мягко говоря, очень и очень смущает.
Может, алгоритм будет не столь эффективным?

Вообще, это пирамидальная сортировка?


Код:
#include "stdafx.h"
#include <conio.h>
#include <iostream> 
#include <Windows.h> 
#include <time.h> 

using namespace std;

void hss(int *mas, int t); //пирамидальная сортировка
void trippp(int *mas,int j,int n); //j - индекс "родителя"


void main ()
{
	setlocale (0,""); 
	srand(time(0)); //привязка "генератора случ.чисел" ко времени
	int i,t,a,n; // i - для счётчика, t - для размера динам. массива, а - переменная для выбора сортировки, n - размер массива (t) для П сортировки
	cout << "Введите размер массива: ";
	cin >> t; //вводим переменную для размера дин. массива
	//создаём дин. массив
	int *mas=new int[t];
	cout << "\n\nМассив до сортировки: ";
	for (i=0; i<t; i++)
	{
		mas[i]=rand() % 50;
		cout << mas[i] << " ";
	}

	int l=0, r=t-1; //для быстрой сортировки, верхняя и нижняя границы

	cout << "\n\nКакой сортировкой его будем мучить?\n\n4 - пирамидальная сортировка\n\n";
	cin >> a;
	switch (a) 
	{
		case 4: 
		{
			//сортируем пирамидальной сортировкой
			 n=t;
			hss(mas,n);
			cout << "\n\nМассив после сортировки: ";
			//выводим массив после сортировки
			
               break;
		}
        default:
		{
			system("cls");
            cout << "ERROR!";
            break;
		}
	}


	for (i=0; i<t; i++)
			{
				cout << mas[i] << " ";
			}
	
	cin.get();
	cin.get();
}



//пирамидальная сортировка
void hss(int *mas,int n)
{
	int i,j;
	int r;
	r=n;
	//построение "пирамиды" в первой половине
	for (i=n/2; i>=0; i--)
	{
		trippp(mas, i, n);
	}

	

	for (i=n-1; i>0; i--)
	{
		// меняем первый элемент массива с последним, чтобы опускать "новые элементы" на нужные уровни
		//пирамиду строим с 0-элемента и идём вверх до i элемента.
		 //"добавление нового элемента" в пирамиду.
		int www=mas[0];
		mas[0]=mas[i];
		mas[i]=www;

		trippp(mas, 0, i-1);//перестраиваем (сортируем) "пирамиду"
	}
	
   

}

//перестройка "пирамиды"
void trippp(int *mas,int j,int n)
{
	int b=0;
	
	int ILC, IRC, IME; //индекс левого\правого ребёнка, IME - индекс максимального элемента из детей
	if (n!=0)
	{
		//j - индекс "нового" элемента
		int copy=mas[j];
		while (j<=n/2)
		{
			b++;
			ILC=2*j;
			IRC=ILC+1;
			IME=ILC;
			//находим индекс максимального детёныша, изначально берём левого за "максимальный".
			if ((ILC<n)&&(mas[ILC]<mas[IRC]))
			{
				IME++;
			}
	
			if(copy>=mas[IME]) //если родитель старше, то выходим из цикла и функции.
			{
				break;
			}
			else //если нет, то
			{
				mas[j]=mas[IME];
				j=IME; //меняем родителя с детёнышем, меняем их индексы
				mas[j]=copy;
				
			}
		}
	}
}


ВОПРОС 2
Как лучше (и как вообще) реализовать сбалансированное бинарное дерево, если нужно будет ещё написать функции для вставки и удаления элемента?



Была бы очень признательна за помощь!

Последний раз редактировалось Fanyuus; 15.05.2013 в 16:27.
Fanyuus вне форума Ответить с цитированием
Старый 15.05.2013, 16:29   #2
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Я не знаю, кто писал этот бред. Но к "быстрой сортировке" он не имеет никакого отношения.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Старый 15.05.2013, 16:32   #3
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

Smitt&Wesson, ужс :D
*надо срочно переделать хип.
Fanyuus вне форума Ответить с цитированием
Старый 15.05.2013, 16:35   #4
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Прочитал оба вопроса, не пойму как свяазно с темой:
Цитата:
Деревья, прям целый лес (сбалансированные и пирамидальные)
под пирамидальным деревом имеешь ввиду пирамиду (которая сортирующее дерево?)
причем тут лес (который множество непересекающихся деревьев) я тоже непонял.

дальше читаю внимательно:
Цитата:
Чтобы сделать дерево, пусть это будет пирамидальная сортировка, нужно взять корень.
дерево - структура данных, а сортировка - процедура, определенная над этими данными. Вы пишите, примерно так "пусть деревом будет пирамидальная сортировка", или я ниче не понял.

Цитата:
А я сделала пирамидальную сортировку (надеюсь, что это всё-таки пирамидальная сортировка) без рекурсии. Нашла алгоритм в интернете (псевдокод) и по нему написала алгоритм. Суть алгоритма, что берёшь не с середины корень, а прям с первого элемента. И наращивание на 2*i и 2*i+1. Но у меня нет рекурсии. Я строю из половины массива "дерево", потом "добавляю" в него новые элементы, меняя его с головой, будто бы наращивая размер массива (а по сути, просто двигаюсь по i>n/2). Но отсутствие рекурсии меня, мягко говоря, очень и очень смущает.
Может, алгоритм будет не столь эффективным?

Вообще, это пирамидальная сортировка?
да, это пирамидальная сортировка, все в порядке (если все работает, я не проверял и не вникал особо, но что-то похоже на правду), отсутствие рекурсии - это хорошо.

Цитата:
Как лучше (и как вообще) реализовать сбалансированное бинарное дерево, если нужно будет ещё написать функции для вставки и удаления элемента?
В основном функции вставки и удаления вам и нужны. При вставке и удалении должна выполняться балансировка, про это, можно почитать в любой книжке по алгоритмам, у Кнута или Скиены, например.
rrrFer вне форума Ответить с цитированием
Старый 15.05.2013, 16:42   #5
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

Цитата:
причем тут лес
это был сарказм С:

Курсовая работа. 4-ая задача в 1-ой лабораторной - heapsort, а в 3-ей лабораторной надо написать сбалансированное бинарное дерево. А времени мало. А я тут вдруг увидела, что "нет рекурсии", аж испугалась.
*Нашла сейчас на http://algolist.manual.ru/sort/pyramid_sort.php всё, успокоилась, лабораторная норм, а то Smitt&Wesson напугал

Цитата:
В основном функции вставки и удаления вам и нужны. При вставке и удалении должна выполняться балансировка, про это, можно почитать в любой книжке по алгоритмам, у Кнута или Скиены, например.
У меня такой вопрос. А как в динамический массив добавить элемент\удалить? Или ... ? *Идею, достаточно идеи **или проще сделать через списки?

Последний раз редактировалось Fanyuus; 15.05.2013 в 18:06.
Fanyuus вне форума Ответить с цитированием
Старый 15.05.2013, 17:33   #6
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Цитата:
У меня такой вопрос. А как в динамический массив добавить элемент\удалить? Или ... ? *Идею, достаточно идеи **или проще сделать через списки?
как бэ элементы массива храняца последовательно, и когда ты выделяешь память кто-то ищет тебе незанятую область памяти подходящего размера. Никто не гарантирует, что когда ты захочишь добавить элемент за последним элементом массива память будет не занята. Короче это сделать нельзя.

Но можно выделить память с запасом и хранить где-то количество реально занятых элементов - тогда добавить элемент ты сможешь очень просто. Но когда запас будет исчерпан тебе придеца создавать новый массив (наверное опять с запасом), копировать туда элементы старого массива, а затем, добавлять элемент. (примерно так стандартные вектора работают, т.е. это нормальный ход, с говнокодом при правильном использовании не связанный).

Но лучше списки, может быть использовать, да.
rrrFer вне форума Ответить с цитированием
Старый 15.05.2013, 18:04   #7
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

Пока искала в интернете как добавить и удалить элемент из динамического массива, наткнулась на такую наиползенейшую вещь, как вектор. Он ведь динамический массив, только класс. И удалять умеет. И расширяться по мере необходимости.

Думаю, это отличная идея.
потому что до сих пор не поняла работу списков, но желаю летом с этим разобраться))


Теперь у меня вот какой вопрос: Вектор не будет работать медленнее, чем (простой) динамический массив? *Хотя вектор, это и есть динамический массив, только с кучей доп.функций, класс, но... он действительно упростит работу))

Последний раз редактировалось Stilet; 16.05.2013 в 07:53.
Fanyuus вне форума Ответить с цитированием
Старый 16.05.2013, 06:24   #8
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Цитата:
наткнулась на такую наиползенейшую вещь, как вектор.
я писал тебе про вектор в посте #6

добавление/удаление элемента в вектор имеет сложность O(N), в список O(1)
время произвольного доступа (когда ты пишешь a[34], например) для вектора O(1), для списка O(N) и так далее.
В зависимости от того, что там ты будешь с ним делать выбирай между std::list и std::vector
rrrFer вне форума Ответить с цитированием
Старый 16.05.2013, 16:59   #9
Fanyuus
Форумчанин
 
Аватар для Fanyuus
 
Регистрация: 07.05.2011
Сообщений: 169
По умолчанию

rrrFer, а я пока писала свой ответ, читала про эти вектора, соответственно, ваш ответ не видела, но это да - хорошая идея.

Теперь у меня возникли другие вопросы, по поводу сбалансированного дерева.

Я уже придумала\нашла связь с "родитель\потомок", реализовать её, думаю, будет не так сложно, это при условии, что массив заполняется по порядку, и 2 условия по поводу "разница не больше одного в уровнях и листах" выполняется преспокойно. Другой вопрос: как бы более корректно реализовать добавление нового элемента и перестраивать всё дерево?

В общем, вопрос встал по поводу перестройки дерева и уложения его в известные индексы.

Госспади, если я сделаю это сбалансированное дерево, я куплю себе торт от счастья С:
Fanyuus вне форума Ответить с цитированием
Старый 17.05.2013, 09:30   #10
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Код:
struct node {
  node *left, *rigth;
};
так описать узел дерева гораздо проще

при вставке для балансировки там чето кудато поворачивается, я деталей не помню.

мне кажеца я уже предлагал почитать про АВЛ-деревья всякие и красно-черные, ты не реагируешь, я загуглил за тебя (вторая ссылка с гугла: http://algolist.manual.ru/ds/rbtree.php )
и там уже реализовано сбалансированное дерево, бери код и пользуй )

Цитата:
Госспади, если я сделаю это сбалансированное дерево, я куплю себе торт от счастья С:
я тоже хочу торт
rrrFer вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
нужно прям сейчас ( элементарно ) ll0nl1ne Общие вопросы C/C++ 12 20.12.2011 17:22
Графика в TurboPascal: Процедуры, рисующие на экране смешанный лес (лес состоит из елей) по курсору GreenDay Помощь студентам 2 04.05.2011 13:31
Лес в паскале GreenDay Помощь студентам 2 19.04.2011 09:20
деревья( Маргоша1993 Паскаль, Turbo Pascal, PascalABC.NET 1 10.04.2011 12:38