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

Implementacja SortedArrayList problem ze static

Ostatnio zmodyfikowano 2018-11-23 15:05
Autor Wiadomość
Spear
Temat założony przez niniejszego użytkownika
Implementacja SortedArrayList problem ze static
» 2018-11-23 03:50:14
Witam, mam problem z implementacja funkcji  merge. Ma zostac zaimplementowana wg. Tego interfejsu:

class SortedArrayList {
    ...
    void push(int x);   // Wstawia element 'x'
    int pop();          // Zwraca i usuwa pierwszy (najmniejszy) element
    int erase(int i);   // Usuwa element na pozycji 'i' i zwraca jego wartość
    int find(int x);    // Zwraca pozycję elementu o wartości 'x' lub -1 gdy nie znaleziono
    int size();         // Zwraca liczbę elementów w liście
    void remove(int x); // Usuwa wszystkie elementy równe 'x'
    static SortedArrayList merge(const SortedArrayList& a, const SortedArrayList& b);
                        // Scala dwie posortowane listy i zwraca posortowaną listę
    void unique();      // Usuwa sąsiadujące duplikaty
    void print();       // Wypisuje elementy listy w porządku rosnącym
};

Funkcja merge() ma być statyczna i nie rozumiem jak ma się stworzyć lista wynikowa - zwracana przez funkcje merge. W ciele funkcji próbowałem powołać nowa tablice typu SortedArrayList, kod sie kompiluje, ale przy wywolaniu mam naruszenie pamięci. Jak to kompiluje być zrobione, czy takiej deklaracji. Przeszukalem wszystko w google i dalej nie wiem. Bede wdzieczny za pomoc!
P-172951
garlonicon
» 2018-11-23 06:22:06
nie rozumiem jak ma się stworzyć lista wynikowa - zwracana przez funkcje merge
Masz scalić dwie posortowane listy. Przykład:
KrokLista ALista BWynik
0
{ 1, 2, 3, 4, 5 }
{ 2, 3, 5, 7, 11 }
{ }
1
{ 2, 3, 4, 5 }
{ 2, 3, 5, 7, 11 }
{ 1 }
2
{ 3, 4, 5 }
{ 2, 3, 5, 7, 11 }
{ 1, 2 }
3
{ 3, 4, 5 }
{ 3, 5, 7, 11 }
{ 1, 2, 2 }
4
{ 4, 5 }
{ 3, 5, 7, 11 }
{ 1, 2, 2, 3 }
5
{ 4, 5 }
{ 5, 7, 11 }
{ 1, 2, 2, 3, 3 }
6
{ 5 }
{ 5, 7, 11 }
{ 1, 2, 2, 3, 3, 4 }
7
{ }
{ 5, 7, 11 }
{ 1, 2, 2, 3, 3, 4, 5 }
8
{ }
{ 7, 11 }
{ 1, 2, 2, 3, 3, 4, 5, 5 }
9
{ }
{ 11 }
{ 1, 2, 2, 3, 3, 4, 5, 5, 7 }
10
{ }
{ }
{ 1, 2, 2, 3, 3, 4, 5, 5, 7, 11 }
Jak widać, wystarczy za każdym razem sięgać po pierwszy element jednej z list i dokładać go do listy wynikowej. Oczywiście skoro obie listy są oznaczone jako
const
, to nie należy ich zmieniać - wystarczy jednoznacznie zapamiętywać, w którym miejscu której listy się obecnie znajdujemy.

przy wywolaniu mam naruszenie pamięci
Bez kodu można tylko zgadywać, więc zgaduję: przekroczenie zakresu tablicy?
P-172952
Spear
Temat założony przez niniejszego użytkownika
» 2018-11-23 12:27:09
Bardzo dizękuję za odpowiedź. Załączę kod, który robi problem.

Pustość tablicy oznaczyłem, jako -1 (actual_index = -1;)
C/C++
class SortedArrayList
{
public:
   
   
    int array[ MAX_SIZE ];
    int actual_index = - 1;
   
    void push( int x ) { // wstawia element
        if( actual_index + 1 < MAX_SIZE ) { //sprawdzenie czy element zmieści się w tablicy
            for( int n = actual_index; n >= 0; n-- ) { //przesunięcie wszystkich elementów o jeden do góry
                if( array[ n ] >= x ) { //Jeśli element array[n] jest większy od x to go przesuń
                    array[ n + 1 ] = array[ n ];
                    if( n == 0 )
                         array[ n ] = x;
                   
                }
                else {
                    array[ n + 1 ] = x; //Ten element jest mniejszy, więc wstawmy za nim
                    break;
                }
            }
            if( actual_index == - 1 )
                 array[ 0 ] = x;
           
            actual_index += 1; //zwiększa informacje o ilości danych o +1
        }
    }
   
   
    static SortedArrayList merge( const SortedArrayList & a, const SortedArrayList & b ) {
       
        SortedArrayList array_to_merge;
       
        if( a.actual_index > - 1 ) {
            for( int i = 0; i <= a.actual_index; i++ )
                 array_to_merge.push( a.array[ i ] );
           
        }
        if( b.actual_index > - 1 ) {
            for( int i = 0; i <= b.actual_index; i++ )
                 array_to_merge.push( b.array[ i ] );
           
        }
       
        return array_to_merge;
    }
   
};

Potem deklaruję

    SortedArrayList L1, L2;

Metoda push() działa dla obiektów SortedArrayList L1 oraz L2, tak samo jako inne stworzone funkcje zadeklarowane w pierwszym poście.

W dalszej części programu wywołuję tą funkcję:

   SortedArrayList::merge( L1, L2);

Jeszcze przed wywołaniem funkcji - funkcja wywołuje się dopiero po podaniu na wejście określonej litery -  (zaraz po uruchomieniu programu), występuje naruszenie ochrony pamięci.

Myślę, że źle rozumiem działanie statycznej funkcji, zadeklarowałem w niej tablicę (wynikową - potem zwracaną), do której wrzucam kolejne elementy z obu tablic składowych, ale czy tak można. Kompilator to przepuszcza ale potem mam błąd.
P-172954
pekfos
» 2018-11-23 13:35:59
Podaj cały kod związany z problemem.
P-172955
Spear
Temat założony przez niniejszego użytkownika
» 2018-11-23 14:00:13
C/C++
#include <iostream>
#define MAX_SIZE 1000000



using namespace std;


class SortedArrayList
{
public:
   
   
    int array[ MAX_SIZE ];
    int actual_index = - 1;
   
    void push( int x ) { // wstawia element
        if( actual_index + 1 < MAX_SIZE ) { //sprawdzenie czy element zmieści się w tablicy
            for( int n = actual_index; n >= 0; n-- ) { //przesunięcie wszystkich elementów o jeden do góry
                if( array[ n ] >= x ) { //Jeśli element array[n] jest większy od x to go przesuń
                    array[ n + 1 ] = array[ n ];
                    if( n == 0 )
                         array[ n ] = x;
                   
                }
                else {
                    array[ n + 1 ] = x; //Ten element jest mniejszy, więc wstawmy za nim
                    break;
                }
            }
            if( actual_index == - 1 )
                 array[ 0 ] = x;
           
            actual_index += 1; //zwiększa informacje o ilości danych o +1
        }
    }
   
    int pop() { // Usuwa najmniejszy element z początku listy i zwraca jego wartość
        if( actual_index >= 0 )
        {
            int tmp = array[ 0 ];
            for( int n = 0; n <= actual_index; n++ ) // Przesunięcie wszystkich elementów o jeden w dół
                 array[ n ] = array[ n + 1 ];
           
            actual_index -= 1;
            return tmp;
        }
        else
             return - 1;
       
    }
   
    int find( int x ) { // Wyszukuje element o wartości x i zwraca jego pozycję
        int return_value = - 1;
        for( int n = 0; n <= actual_index; n++ )
        if( x == array[ n ] ) {
            return_value = n;
            break;
        }
        return return_value;
    }
   
    int size() { // Zwraca liczbę elementów w liście
        return actual_index + 1;
    }
   
    void print() {
        for( int i = 0; i < size(); i++ )
             cout << array[ i ] << " ";
       
        cout << endl;
    }
   
    int erase( int pos ) { // Usuwa element z pozycji pos i zwraca jego wartość
        if( actual_index >= 0 )
        {
            int deleted_item = array[ pos - 1 ];
            for( int n = pos - 1; n <= actual_index; n++ ) //przesunięcie wszystkich elementów o jeden w dół
                 array[ n ] = array[ n + 1 ];
           
            actual_index -= 1;
            return deleted_item;
        }
       
    }
   
    void unique() {
        if( actual_index > 1 ) { //Minimum 2 elementy w liscie
            int index_to_insertion = 1;
            int last_value = array[ 0 ];
            int count_deleted = 0;
           
            for( int i = 1; i < size(); i++ )
            if( array[ i ] != last_value ) {
                last_value = array[ i ];
                array[ index_to_insertion ] = last_value;
                index_to_insertion += 1;
            }
            else
                 count_deleted += 1;
           
            actual_index -= count_deleted;
        }
    }
   
    void remove( int x ) {
        if( actual_index > 1 ) { //Minimum 2 elementy w liscie
            int shift_index = 0;
            int count_deleted = 0;
            int amount_fo_x = 0;
            for( int i = 1; i < size(); i++ )
            if( array[ i ] != x ) {
                shift_index += 1;
                count_deleted += 1;
            }
            else
                 array[ i - shift_index ] = array[ i ];
           
            actual_index -= count_deleted;
        }
    }
   
    static SortedArrayList merge( const SortedArrayList & a, const SortedArrayList & b ) {
       
        SortedArrayList array_to_merge;
       
        if( a.actual_index > - 1 ) {
            for( int i = 0; i <= a.actual_index; i++ )
                 array_to_merge.push( a.array[ i ] );
           
        }
        if( b.actual_index > - 1 ) {
            for( int i = 0; i <= b.actual_index; i++ )
                 array_to_merge.push( b.array[ i ] );
           
        }
       
        return array_to_merge;
    }
};


auto main()->int
{
    SortedArrayList sorted_array_list;
    SortedArrayList sal2;
   
    //Obsługa zdarzeń
    int m, k, tmp;
    char c;
   
   
    cin >> k;
    for( int i = 1; i <= k; ++i )
    {
        cin >> c;
        switch( c )
        {
        case 'F':
            cin >> m;
            sorted_array_list.push( m );
            break;
        case 'B':
            cin >> m;
            sal2.push( m );
            break;
        case 'f':
            cout << sorted_array_list.pop() << endl;
            break;
        case 'C':
            cin >> m;
            cout << sorted_array_list.find( m ) << endl;
            break;
        case 'S':
            cout << sorted_array_list.size() << endl;
            break;
        case 'P':
            sorted_array_list.print();
            sal2.print();
            break;
        case 'E':
            cin >> m;
            cout << sorted_array_list.erase( m ) << endl;
            break;
        case 'U':
            sorted_array_list.unique();
            break;
        case 'R':
            cin >> m;
            sorted_array_list.remove( m );
            break;
        case 'M':
            SortedArrayList::merge( sorted_array_list, sal2 );
            break;
        }
    }
   
    return 0;
}
P-172956
pekfos
» 2018-11-23 15:05:59
1000000 to za dużo dla tablicy na stosie.
P-172957
« 1 »
  Strona 1 z 1