Struktury danych/Listy

Z Wikibooks, biblioteki wolnych podręczników.

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Tablice haszujące - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Spis treści 1 Listy 1.1 Budowa listy 1.2 Implementacja 1.3 Ćwiczenia 1.3.1 Podstawowe 1.3.2 Zaawansowane

[edytuj] Listy

Poznane w poprzednim rozdziale tablice doskonale nadają się do przechowywania nieznacznie zmieniających się danych. Jednak weźmy na warsztat program do odtwarzania muzyki. Zazwyczaj wyposażony jest on w playlistę będącą zbiorem naszych ulubionych utworów, które chcemy odsłuchiwać. Playlista może mieć dowolną długość: można na niej trzymać zarówno 20, jak i 2000 piosenek, w dodatku w każdej chwili mamy możliwość dodania dowolnej ilości nowych. Ciężko sobie wyobrazić, by program przydzielał przy uruchomieniu kilka megabajtów "na wszelki wypadek", aby zabezpieczyć się przed sytuacją braku miejsca. Jednym ze sposobów rozwiązania tego problemu jest wykorzystanie nowej struktury danych - list. Ich zasadniczą cechą jest to, że zawsze zajmują w pamięci dokładnie tyle miejsca, ile potrzeba i zawsze można bezproblemowo dodać do nich nowe elementy.

[edytuj] Budowa listy

Każdy rekord w liście, oprócz przechowywanych przez siebie danych, zawiera również przynajmniej jedno dodatkowe pole zawierające adres/położenie następnego w kolejności rekordu. Powstaje w ten sposób łańcuch, w którym rekordy znają jedynie swoje następniki. Ilustruje to poniższy schemat:

Oprócz tego musimy wydzielić też specjalny rekord zawierający tzw. korzeń listy, czyli odnośnik do pierwszego elementu. Ostatni rekord na liście posiada pusty wskaźnik, dzięki czemu możliwe jest powiadomienie o końcu łańcucha. Zauważmy, że w takiej strukturze bezpośredni dostęp do dowolnego elementu jest niemożliwy. Odszukanie interesującego nas rekordu zajmuje rosnącą liniowo ilość czasu. Najpierw musimy ustawić się na początku listy, a następnie przechodzić do kolejnych elementów, dopóki nie natrafimy na nasz właściwy.

Pokazana powyżej lista jest w zasadzie tylko jedną z jej odmian, zwaną listą jednokierunkową, ponieważ możemy po niej poruszać się tylko w jednym kierunku: do przodu. Inne rodzaje list to:

• Listy dwukierunkowe - każdy rekord zawiera dodatkowo drugi wskaźnik pokazujący poprzedni element listy.
• Listy cykliczne - pierwszy i ostatni rekord listy są ze sobą połączone, tworząc zamknięty cykl.

Na liście można wykonywać następujące operacje:

• CREATE(l: List) - tworzy nową listę
• INSERT(l: List; d: Data) - dodaje na końcu listy l rekord d. Zauważmy, że w przedstawionej powyżej naiwnej implementacji listy operacja ta wymaga czasu liniowego, ponieważ tyle zajmuje dotarcie na jej koniec. Istnieje jednak możliwość zaimplementowania tej operacji działającej w stałym czasie. Wystarczy, aby nagłówek listy przechowywał także adres ostatniego z rekordów.
• DELETE(l: List; n: Integer) - usuwa n-ty w kolejności rekord z listy. Usunięcie pierwszego i ostatniego rekordu można wykonać w czasie stałym. Dla pozostałych będzie to czas liniowy.
• FIND(l: List; n: Integer) - pobiera n-ty w kolejności rekord z listy.
• RESET(l: List, n: Integer) - ustawia kursor na podanym rekordzie listy.
• NEXT(l: List) - zwraca rekord, na którym aktualnie ustawiony jest kursor, po czym przesuwa się na kolejny element listy.
• PREV(l: List) - analogiczna operacja do NEXT() dla list dwukierunkowych umożliwiająca przesuwanie się w tył.
• MAKENULL(l: List) - czyści listę, usuwając wszystkie rekordy.

W operacjach wyszukiwania elementów na liście przyjmujemy, że 1 identyfikuje pierwszy rekord na liście, 2 drugi (itd.), n-1 przedostatni, n ostatni.

Operacje RESET(), NEXT() oraz PREV() umożliwiają samodzielne poruszanie się po liście. Na początek musimy ustawić się tam, gdzie potrzebujemy, a następnie dwoma pozostałymi operacjami przesuwamy się w żądanym przez nas kierunku, pobierając po kolei wszystkie napotkane tam rekordy.

Lista jednokierunkowa o n rekordach zajmuje w pamięci n(4 + d) + h bajtów przy założeniu, że d oznacza wielkość danych rekordu, h wielkość nagłówka listy, a wskaźniki są czterobajtowe (długość charakterystyczna dla 32-bitowych aplikacji).

[edytuj] Implementacja

Pierwszą z omówionych implementacji list będzie implementacja tablicowa. Do przechowywania rekordów wykorzystywane są tu poznane w poprzednim rozdziale tablice. Wskaźniki rekordów są tutaj zwyczajnymi indeksami wskazującymi komórkę, pod którą znajduje się kolejny rekord. Nasuwa się tutaj pytanie, jaki jest sens implementacji listy za pomocą tablic. Wbrew pozorom pomysł ten jest całkiem sensowny. Przypomnij sobie zaproponowane w poprzednim rozdziale sposoby na oznaczanie w tablicach "wolnych" komórek. Listy na tablicach to jedna z metod rozwiązania tego problemu.

Alternatywą dla tablic jest implementacja wskaźnikowa, gdzie wykorzystuje się wskaźniki z prawdziwego zdarzenia oraz dynamiczny przydział pamięci dla nowych rekordów. Posiada ona wszystkie opisane wyżej cechy: zajmuje dokładnie tyle pamięci, ile potrzebujemy, oraz umożliwia przechowywanie dowolnie dużej ilości danych. Aby prawidłowo wybrać metodę implementacji, zastanówmy się, jakie są nasze potrzeby. Listy na tablicach są często wybierane przez uczestników olimpiad informatycznych. Pojawiające się tam zadania dokładnie precyzują rozmiar maksymalnych danych oraz dostępną do wykorzystania pamięć. Nie bez znaczenia jest tu również fakt, że alokacja pamięci dla jednego ogromnego bloku jest znacznie szybsza, niż dla setek małych o identycznym sumarycznym rozmiarze.

Do zrobienia: Pokazać przykładowe implementacje najważniejszych operacji (na wskaźnikach)

[edytuj] Ćwiczenia

[edytuj] Podstawowe

Ćwiczenie 1: Napisz program wypisujący wszystkie elementy listy.

Ćwiczenie 2: Napisz pełną implementację listy:

1. Na tablicach
2. Na wskaźnikach

Ćwiczenie 3: Zastanów się, jak w liście dwukierunkowej o długości n zmniejszyć pesymistyczny czas wyszukiwania rekordu x z czasu n do n/2. Wprowadź stosowne poprawki do implementacji.

Do zrobienia: Ułożyć jeszcze trochę ćwiczeń podstawowych

[edytuj] Zaawansowane

Do zrobienia: Ułożyć ćwiczenia zaawansowane