AiSD (3) - ADT LIST (implementacja tablicowa)

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie.

Ogólne zalecenia do przesyłanych programów.
(1) Katalog z programem powinien zawierać Makefile i pliki źródłowe.
(2) Program powinien kompilować się poleceniem make.
(3) Nie używać deklaracji using namespace std;.
(4) Zalecane są testy automatyczne z assert().

WPROWADZENIE

ADT LIST reprezentuje skończoną liczbę uporządkowanych elementów, które mogą się powtarzać. Elementy są uporządkowane (niekoniecznie posortowane!), czyli każdy element ma określoną pozycję (indeks) na liście. Jeżeli liczba uporządkowanych elementów może być potencjalnie nieskończona, to używa się pojęcia strumienia. Lista to podstawowy przykład kontenera do przechowywania elementów, przy czym w ogólności elementy nie muszą być tego samego typu. Typowe operacje dla ADT LIST są następujące:

konstruktor tworzący pustą listę,
testowanie, czy lista nie jest pusta [empty()],
odczyt liczby elementów na liście, to jest długość listy [size()],
odczyt największej możliwej liczby elementów (capacity) [max_size()],
dołączanie elementu na początek listy [push_front(item)],
dołączanie elementu na koniec listy [push_back(item)],
dostęp do głowy (head), czyli pierwszego (lewego skrajnego) elementu [front()],
dostęp do ogona (tail), czyli ostatniego (prawego skrajnego) elementu [back()],
usunięcie elementu pierwszego [pop_front()],
usunięcie elementu ostatniego [pop_back()],
czyszczenie listy, czyli usunięcie wszystkich elementów [clear()],
dostęp do elementu o danym indeksie i,
dołączanie elementu przed element na pozycji i [insert()],
usunięcie elementu o danym indeksie i [erase()],
sortowanie listy [sort()],
łączenie dwóch posortowanych list w jedną [merge()].

ADT LIST jest typowo implementowany jako lista powiązana (liniowa lub cykliczna) lub tablica, zwykle o zmiennej długości.

W STL indeksowany dostęp do elementów zapewniają kontenery std::vector (ciągły obszar pamięci) i std::deque (sekwencja indywidualnie alokowanych tablic o stałym rozmiarze).

// Kontenery w STL realizujące w pewnym stopniu ADT LIST.

// https://en.cppreference.com/w/cpp/container/vector

// https://en.cppreference.com/w/cpp/container/forward_list

// https://en.cppreference.com/w/cpp/container/list

// https://en.cppreference.com/w/cpp/container/deque

// Przy kopiowaniu szeregu elementów tablicy przydają się funkcje z STL.

// https://en.cppreference.com/w/cpp/algorithm/copy
// Funkcja odpowiednia przy kopiowaniu w lewo przy nakładaniu się zakresów.
// Podajemy tylko początek zakresu docelowego (d_first).

It2 copy( It1 first, It1 last, It2 d_first );

// Przykład. Kopiowanie w obrębie jednej tablicy a.
// +--+--+--+--+--+--+--+--+--+--+
// |a0|a1|a2|a3|a4|a5|a6|a7|a8|a9| stan początkowy
// +--+--+--+--+--+--+--+--+--+--+
// std::copy(a+5, a+9, a+3); // kopiowanie 4 elementów: a5, a6, a7, a8
// +--+--+--+--+--+--+--+--+--+--+
// |a0|a1|a2|a5|a6|a7|a8|a7|a8|a9| stan końcowy
// +--+--+--+--+--+--+--+--+--+--+

// https://en.cppreference.com/w/cpp/algorithm/copy_backward
// Funkcja odpowiednia przy kopiowaniu w prawo przy nakładaniu się zakresów.
// Podajemy tylko koniec zakresu docelowego (d_last).

It2 copy_backward( It1 first, It1 last, It2 d_last );

// Przykład. Kopiowanie w obrębie jednej tablicy a.
// +--+--+--+--+--+--+--+--+--+--+
// |a0|a1|a2|a3|a4|a5|a6|a7|a8|a9| stan początkowy
// +--+--+--+--+--+--+--+--+--+--+
// std::copy_backward(a+2, a+6, a+7); // kopiowanie 4 elementów: a5, a4, a3, a2
// +--+--+--+--+--+--+--+--+--+--+
// |a0|a1|a2|a3|a2|a3|a4|a5|a8|a9| stan końcowy
// +--+--+--+--+--+--+--+--+--+--+

ZADANIE 3.1 (TABLICA STATYCZNA)

Przygotować implementację realizującą ADT LIST na bazie tablicy o stałym rozmiarze (tablica statyczna), ustalanym w czasie tworzenia listy. Będzie to klasa ArrayList umieszczona w pliku arraylist.h. Uzupełnić plik arraylist.h, stworzyć funkcję main() i testy sprawdzające działanie interfejsu list.

ZADANIE 3.2 (TABLICA DYNAMICZNA)

https://chalmersgu-data-structure-courses.github.io/OpenDSA/Published/ChalmersGU-DSABook/html/ListArrayDynamic.html

Przygotować implementację realizującą ADT LIST na bazie tablicy o zmieniającym się rozmiarze (tablica dynamiczna). Będzie to klasa ArrayList umieszczona w pliku arraylist.h. Początkowy rozmiar tablicy (min_size) może wynosić 1, 2 lub 4. Po zapełnieniu tablicy rozmiar może się powiększać o stały czynnik, np. może się podwajać. Powiększanie tablicy o stałą liczbę miejsc nie jest dobrym rozwiązaniem, ze względu na wielokrotne kopiowanie elementów. Po usunięciu pewnej liczby elementów tablica może się zmniejszać, aż do osiągnięcia początkowego rozmiaru minimalnego.

Zbadajmy liczbę kopiowań elementów podczas powiększania tablicy o czynnik 2. Zakładamy, że elementy są kolejno wstawiane do tablicy.
resize(2), kopiowany 1 element
resize(4), kopiowane 2 elementy
resize(8), kopiowane 4 elementy
resize(16), kopiowane 8 elementów
resize(32), kopiowane 16 elementów
resize(64), kopiowane 32 elementy
resize(128), kopiowane 64 elementy
resize(2^k), kopiowane 2^{k-1} elementów

Załóżmy najbardziej niekorzystny przypadek, że liczba elementów wstawionych do tablicy wynosi n = 2^k + 1. Tablica rozszerzy się do rozmiaru 2^{k+1}. Łączna liczba kopiowań elementów wynosi
1 + 2 + 4 + ... + 2^k = (1 - 2^{k+1}) / (1 - 2) = 2^{k+1} -1 = 2 * 2^k -1 = 2 (n-1) -1 = 2n -3.
Pokazaliśmy, że stosując strategię podwajania rozmiaru tablicy, wstawianie do tablicy n elementów wymaga mniej niż 2n kopiowań elementów. Inaczej mówiąc, wstawienie jednego elementu do tablicy kosztuje co najwyżej dwa kopiowania elementów.

Osobnym zagadnieniem jest zmniejszanie rozmiaru tablicy przy zmniejszającej się liczbie elementów. Załóżmy, że aktualny rozmiar tablicy wynosi 2^k. Dobrą strategią jest zmniejszanie rozmiaru do 2^k / 2, jeżeli liczba elementów zmaleje do 2^k / 4 lub 2^k / 3, a nie do 2^k / 2. Unikamy wtedy częstego powiększania i zmniejszania rozmiaru tablicy, kiedy liczba elementów oscyluje koło 2^k / 2.

AiSD (index)