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! |
|
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: 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? |
|
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;) class SortedArrayList { public: int array[ MAX_SIZE ]; int actual_index = - 1; void push( int x ) { if( actual_index + 1 < MAX_SIZE ) { for( int n = actual_index; n >= 0; n-- ) { if( array[ n ] >= x ) { array[ n + 1 ] = array[ n ]; if( n == 0 ) array[ n ] = x; } else { array[ n + 1 ] = x; break; } } if( actual_index == - 1 ) array[ 0 ] = x; actual_index += 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. |
|
pekfos |
» 2018-11-23 13:35:59 Podaj cały kod związany z problemem. |
|
Spear Temat założony przez niniejszego użytkownika |
» 2018-11-23 14:00:13 #include <iostream> #define MAX_SIZE 1000000
using namespace std;
class SortedArrayList { public: int array[ MAX_SIZE ]; int actual_index = - 1; void push( int x ) { if( actual_index + 1 < MAX_SIZE ) { for( int n = actual_index; n >= 0; n-- ) { if( array[ n ] >= x ) { array[ n + 1 ] = array[ n ]; if( n == 0 ) array[ n ] = x; } else { array[ n + 1 ] = x; break; } } if( actual_index == - 1 ) array[ 0 ] = x; actual_index += 1; } } int pop() { if( actual_index >= 0 ) { int tmp = array[ 0 ]; for( int n = 0; n <= actual_index; n++ ) array[ n ] = array[ n + 1 ]; actual_index -= 1; return tmp; } else return - 1; } int find( int x ) { 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() { return actual_index + 1; } void print() { for( int i = 0; i < size(); i++ ) cout << array[ i ] << " "; cout << endl; } int erase( int pos ) { if( actual_index >= 0 ) { int deleted_item = array[ pos - 1 ]; for( int n = pos - 1; n <= actual_index; n++ ) array[ n ] = array[ n + 1 ]; actual_index -= 1; return deleted_item; } } void unique() { if( actual_index > 1 ) { 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 ) { 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; 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; } |
|
pekfos |
» 2018-11-23 15:05:59 1000000 to za dużo dla tablicy na stosie. |
|
« 1 » |