AiSD (index)

AiSD (3) - ADT LIST (implementacja tablicowa)

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie.

WPROWADZENIE

ADT LIST reprezentuje skończoną liczbę uporządkowanych elementów, które mogą się powtarzać. 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. 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 [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 [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
// To jest dobre przy kopiowaniu w lewo przy nakładaniu się zakresów.

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
// To jest dobre przy kopiowaniu w prawo przy nakładaniu się zakresów.

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

Przygotować implementację realizującą ADT LIST na bazie tablicy o stałym rozmiarze, 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

Przygotować implementację realizującą ADT LIST na bazie tablicy o zmieniającym się rozmiarze. Będzie to klasa ArrayList umieszczona w pliku arraylist.h. Początkowy rozmiar tablicy (min_size) może wynosić 2 lub 4. Po zapełnieniu tablicy rozmiar może się powiększać o stałą wartość lub może się podwajać (wybrać jedną możliwość). Po usunięciu pewnej liczby elementów tablica może się zmniejszać, aż do osiągnięcia początkowego rozmiaru minimalnego.

AiSD (index)