Форум программистов, компьютерный форум CyberForum.ru

Пирамидальная сортировка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Mokona
0 / 0 / 0
Регистрация: 04.07.2013
Сообщений: 9
04.07.2013, 18:44     Пирамидальная сортировка #1
Здравствуйте! Хотела попросить помощи. Мне нужно отсортировать дерево пирамидальной сортировкой. Создание дерева у меня есть, но сортировка не получается. Вот код.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <conio.h>
#include <stdio.h>
#include <locale>
 
 
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if (*t==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>=(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u) 
{
    if (t==NULL)  //Если дерево пустое, то отображать нечего, выходим
    return;
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) printf ("  ");
    printf ("%d\n",t->info); //И показываем элемент
    u--;
    }
    print(t->r,++u); //С помощью рекурсии посещаем правое поддерево
}
 
void main ()
{   
    setlocale (LC_ALL, "Russian");
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    printf ("Введите количество элементов:  ");
    scanf ("%d", &n); //Вводим количество элементов
    for (int i=0;i<n;++i)
    {
    printf ("Введите число  ");
    scanf ("%d", &s); //Считываем элемент за элементом
    push(s,&tree); //И каждый кладем в дерево
    }
    printf ("Ваше дерево\n");
    print(tree,0);
    getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2013, 18:44     Пирамидальная сортировка
Посмотрите здесь:

Пирамидальная сортировка C++
Пирамидальная сортировка C++
пирамидальная сортировка C++
C++ Пирамидальная сортировка
C++ Пирамидальная сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2185 / 1868 / 187
Регистрация: 03.07.2012
Сообщений: 6,640
Записей в блоге: 1
04.07.2013, 19:23     Пирамидальная сортировка #2
Во-первых код неотформатирован. Во-вторых- где сама сортировка?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.07.2013, 21:59     Пирамидальная сортировка #3
Цитата Сообщение от Mokona Посмотреть сообщение
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
для пирамидальной сортировки не нужно бинарное дерево. Там используется структура heap (или куча/пирамида, по-разному называют ее). Изучайте
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
04.07.2013, 23:05     Пирамидальная сортировка #4
ya_noob, куча и пирамида -- это и есть двоичное (бинарное) дерево с некоторыми свойствами.
Mokona, лучше хранить ваше деревце в виде массива размера 2n+1
Хранится оно так : сначала идёт слой из 1 элемента после него слой из 2 элементов, потом n/(2^2) и т.д. до n. Всего LogN слоёв, это высотой дерева называется.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.07.2013, 23:10     Пирамидальная сортировка #5
не допишешь одно слово и сразу придирки начинаются
Ternsip, ТС реализует бинарное дерево поиска. Я имел ввиду что такое дерево не нужно.
Цитата Сообщение от Ternsip Посмотреть сообщение
лучше хранить ваше деревце в виде массива размера 2n+1
Хранится оно так : сначала идёт слой из 1 элемента после него слой из 2 элементов, потом n/(2^2) и т.д. до n.
Для пирамиды достаточно n элементов.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
04.07.2013, 23:15     Пирамидальная сортировка #6
ya_noob, а! точно, спутал с деревом отрезков Спасибо. Достаточно n элементов. Но проблема в том, что ТС хочет именно своё дерево отсортировать
Цитата Сообщение от Mokona Посмотреть сообщение
Мне нужно отсортировать дерево пирамидальной сортировкой
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.07.2013, 23:23     Пирамидальная сортировка #7
bst не обладает свойствами пирамиды, следовательно с помощью него требуемой сортировки не получится
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
04.07.2013, 23:33     Пирамидальная сортировка #8
ya_noob, у ТС просто дерево, оно даже не волшебное, ей просто нужно сделать из него пирамиду.
Кстати, Mokona, отсортировать дерево и сделать и него кучу -- разные вещи.

Подкреплю слова примером. Вот example для обычного массива. Тут осуществляется пирамидальная сортировка двумя способами. И оба они скрыты в библиотеке STL
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int main() {
    freopen ("input.txt", "rt", stdin);
    freopen ("output.txt", "wt", stdout);  
    int n;
    scanf ("%d", &n);
    vector <int> a(n);
    for (int i = 0; i < n; ++i)
        scanf ("%d", &a[i]);
    make_heap(a.begin(), a.end());
    /* можно вот так
    for (int i = 0; i < n; ++i)
        printf("%d ", a.front()), pop_heap(a.begin(), a.end()), a.pop_back();
    */
    /* или вот так
    sort_heap(a.begin(), a.end());
    for (int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    */
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2013, 19:12     Пирамидальная сортировка
Еще ссылки по теме:

C++ Пирамидальная сортировка
Пирамидальная сортировка C++
Пирамидальная сортировка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Mokona
0 / 0 / 0
Регистрация: 04.07.2013
Сообщений: 9
10.07.2013, 19:12  [ТС]     Пирамидальная сортировка #9
Спасибо всем за помощь! Я смогла разобраться и сделать задание))))
Yandex
Объявления
10.07.2013, 19:12     Пирамидальная сортировка
Ответ Создать тему
Опции темы

Текущее время: 21:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru