Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Sortowanie kubełkowe liczb naturalnych za pomocą kopca

Ostatnio zmodyfikowano 2014-11-20 14:26
Autor Wiadomość
Diegogo
Temat założony przez niniejszego użytkownika
[C++] Sortowanie kubełkowe liczb naturalnych za pomocą kopca
» 2014-11-19 23:09:10
Zadaniem było napisać sortowanie kubełkowe sortujące liczby naturalne mniejsze od 1000, tak żeby kubełkami były kopce i każdy kopiec miał zakres 100. Sortowanie miało zmieniać tablicę a nie zwracać nową.
C/C++
#include<iostream>
#include"heap.h"
#include<cmath>
using namespace std;
Heap * kubelki( int * tab, int n ) //wrzuca wartosci w kubelki
{ Heap kubel[ 11 ];
    int p;
    for( int k = 0; k < n; k++ )
    { p = tab[ k ] / 100;
        kubel[ p + 1 ].InsertHeap( tab[ k ] );
    }
   
    return kubel;
}
int * sort( Heap * kubel, int n ) //sortuje z kubelkow w tablice
{ int i = n - 1;
    int k = 10;
    int * tab = new int[ n ];
    for( k; k > 0; k-- )
    { while( kubel[ k ].HeapSize != 0 )
        { tab[ i ] = kubel[ k ].DeleteMax();
            i--;
        }
    }
    return tab;
}
void kubsort( int * tab, int n ) //uzywa poprzednich 2 funkcji by zmienic tablice wyjscowa
{ Heap * kubel = new Heap[ 11 ];
    kubel = kubelki( tab, n );
    tab = sort( kubel, n );
   
   
}
//Ten program wedlug mnie powinien dzialac, psuje się na 10 kubelku, mimo ze tablica tam istnieje
//Ja bledu znaleŸzc nie potrafie, cala idea wydaje się miec sen


int main() {
    int n = 23; //dla tab powyżej 50elementow zmienic n
    int * test = new int[ n ];
    cout << "Nieposortowane elementy tablicy" << endl;
    for( int i = 0; i < n; i++ )
    { test[ i ] = rand() % 1000;
        cout << test[ i ] << " ";
    }
    cout << endl;
    cout << "Nastepuje rozdzielenie do kubelkow" << endl;
    Heap * testkub = new Heap[ 11 ];
    testkub = kubelki( test, n );
    for( int i = 1; i <= 10; i++ )
    { cout << "Elementy kubelka nr " << i << endl;
        testkub[ i ].PrintHeap();
        cout << endl;
    }
    kubsort( test, n );
    for( int i = 0; i < n; i++ )
    { cout << test[ i ] << " ";
    }
    cout << endl;
    return 0;
}
Do tego klasa kopiec i jej funkcje
C/C++
#include <iostream>
using namespace std;

const static int Max = 200; // Maksymalny rozmiar kopca

class Heap
{
public:
    int HeapSize; // liczność kopca
    int H[ Max + 1 ]; // tablica reprezentujaca kopiec
   
    Heap()
        : HeapSize( 0 )
    { }
   
    void UpHeap( int k )
    // Poprawianie struktury kopca: element H[k] jest "przepychany" w górę
    {
        int x;
        int i =( int )( k / 2 ); // indeks ojca elementu H[k]
        x = H[ k ]; // element przepychany w górę
        while( i > 0 )
        if( H[ i ] < x ) // zaburzony warunek kopca, element ojca spuszczany w dół
        {
            H[ k ] = H[ i ];
            k = i;
            i =( int )( i / 2 );
        }
        else break;
       
        H[ k ] = x;
    }
    void InsertHeap( int x )
    // Wstawianie elementu x do kopca
    {
        HeapSize++;
        H[ HeapSize ] = x; // ustaw wstawiany element na końcu tablicy
        UpHeap( HeapSize ); // przepchij element wstawiany w górę
    }
Klasa ma zdefiniowane więcej funkcji, ale że nie są używane to ich nie wklejam
W mainie jest napisany test, w sortowaniu pojawiają się "śmieci" , a po wrzuceniu ich w kubełki program przestaje działać.
Sprawdzałem sortowania znajomych i opierają się na tym samym mechanizmie, szukałem błędu ja, szukali oni, mam nadzieję, że ktoś tutaj mnie oświeci.
Pozdrawiam
Diegogo
P-121036
Wgbg
» 2014-11-20 14:25:01
Podaj ciało metody DeleteMax.

C/C++
int * sort( Heap * kubel, int n ) //sortuje z kubelkow w tablice
{ int i = n - 1;
    int k = 10;
    int * tab = new int[ n ];
    for( k; k > 0; k-- )
    { while( kubel[ k ].HeapSize != 0 )
        { tab[ i ] = kubel[ k ].DeleteMax();
            i--;
        }
    }
P-121052
darko202
» 2014-11-20 14:26:47
w metodzie
Heap * kubelki( int * tab, int n ) //wrzuca wartosci w kubelki
{ Heap kubel[ 11 ];
....   
    return kubel;
}
a kubel jest zmienną lokalną

to prowadzi do błędu w linii
 testkub = kubelki( test, n );

P-121053
« 1 »
  Strona 1 z 1