Przesuwanie Elementów Tablicy

Wstęp

Obrót tablicy w prawo oznacza przeniesienie ostatni element na początek listy. Do takie operacji można zastosować algorytm przesuwania elementów tablicy, który wykona taką operację w czasie liniowym. Wpierw przeprowadźmy analizę zagadnienia.

Problem

Przypuśćmy, że mamy następującą tablicę danych:

W celu przesunięcia elementów o 3 miejsca w prawo należałoby dopisać dodatkowe trzy miejsca za tablicą, a następnie przepisać je w wolne miejsce na początku tablicy. Oznacza to kolejno:

W podobny sposób działa przekręcanie elementów w lewo. Przykładowo przesunięcie wyjściowej tablicy o -2 zwraca następującą tablice:

Jest to dokładnie taka sama tablica jak w przypadku przesunięcia w prawo o 3. Nie jest to przypadek, ponieważ tablica ma dokładnie 5 elementów (-2 + 5 = 3).

Wskazówki do implementacji

Każde przesunięcie można zamienić na przesunięcie z przedziału [0, n - 1]. W tym celu należy wziąć resztę z dzielenia przesunięcia p przez n dla dodatnich przesunięć, a w przypadku ujemnych tak długo dodawać n, aż uzyska się wartość dodatnią.

Implementacja

Zadanie polega na napisaniu funkcji obroc(), która daną tablicę obróci o dowolne przesunięcie. Przedstawione zostaną dwie metody, które działają bardzo podobnie, ale różnią się złożonością pamięciową.

Proste rozwiązanie

Proste rozwiązanie polega na utworzeniu dodatkowej tablicy. Następnie dla każdego elementu należy wyliczyć pozycję na której ma się znaleźć w ostatecznej tablicy. Tego typu rozwiązanie wymaga dodatkowego miejsca w pamięci na dodatkową tablicę długości n. Oto przykładowa funkcja obroc():

1. int* obroc(int* tab, int n, int przes) {
2.   przes = (przes + n) % n;
3.   int* w = new int[n];
4.   for (int i = 0; i < n; i++)
5.     w[i] = tab[(i - przes + n) % n];
6.   return w;
7. }

(2.) Normalizuj przesunięcie, a następnie (3.) przygotuj tablice wynikową. W dalszej części (4.) dla każdego jej elementu: (5.) oblicz, który element z tablicy wejściowej powinien znaleźć się na i-tej pozycji. (6.) Wynikiem działania funkcji jest obrócona tablica.

Optymalne rozwiązanie

Optymalne rozwiązanie eliminuje problem potrzebnej dodatkowej pamięci. Jedyne czego będzie wymagać to dodatkowej zmiennej do przechowania elementu w celu zamiany dwóch elementów. Otóż zamianę rozpoczynamy od indeksu 0. Dla wybranego indeksu obliczamy, gdzie powinien się znaleźć. Następnie podmieniamy go z elementem na wyliczonej pozycji. Dla nowo ustawionego elementu powtarzamy proces, aż wrócimy do początkowego indeksu.

Przykład

Weźmy nastepującą tablicę L:={1, 2, 3, 4, 5}. Przyjmujemy, że rozpoczynamy działanie od pierwszego elementu. W tabeli zostały wyjaśnione kolejne operacje dla przesunięcia p = 3:

Tablica po przesunięci elementów o p = 3 to L':={3, 4, 5, 1, 2}.

Rozwiązanie

Oto przykładowy kod:

1. void obroc(int* tab, int n, int przes) {
2.   przes = (przes + n) % n;
3.   int indeks = 0, temp = tab[0];
4.   do {
5.     int poz = (indeks + przes + n) % n;
6.     swap(temp, tab[poz]);
7.     indeks = poz;
8.   } while (indeks != 0);
9. }

(2.) Normalizuj przesunięcie, a następnie (3.) rozpocznij zamiany od indeksu 0 i pobierz z tablicy element 0 i zapisz w zmiennej tymczasowej temp. Następnie (5.) oblicz gdzie wstawić element zapisany w temp i (6.) zamień go z elementem na wyliczonej pozycji poz. Przed zakończeniem iteracji (7.) zaktualizuj indeks pobranego elementu i (8.) wykonaj następną iterację jeśli wciaż istnieją elementy do zamiany.

Testowanie funkcji

W celu przetestowania kodu funkcji obroc() można skorzystać z poniższego fragmentu kodu. W zależności od wersji funkcji istnieje potrzeba dostosowania linijek wywołujące funkcję i wypisujące wynik.

1. int main() {
2.   int n, k;
3.   cout << "Podaj ile elementow ma tablica:\n n = ";
4.   cin >> n;
5.   cout << "Podaj elementy tablicy:" << endl;
6.   int* tab = new int[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   cout << "O ile przesunac?\n k = ";
10.   cin >> k;
11.   obroc(tab, n, k);
12.   for (int i = 0; i < n; i++)
13.     cout << tab[i] << " ";
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Proste rozwiązanie
• Kod źródłowy Optymalne rozwiązanie