Struktury danych/Podstawowe informacje

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

Podstawowe informacje na temat struktur danych

W informatyce bardzo ważnym zagadnieniem jest reprezentacja danych w komputerze. Biorąc pod uwagę fakt, że w przeciwieństwie do matematyki zbiory, na których się operuje w założeniu są dużo bardziej dynamiczne. Oznacza to, że bardzo często trzeba będzie je zwiększać lub pomniejszać, a co najważniejsze odczytywać z nich informacje.

W tym momencie okazuje się, że formalne określenie i opisanie pewnych abstrakcyjnych typów danych (ang. abstract data type) jest bardzo pomocne w pracy informatyka. Ważne są tylko pewne informacje na temat tego jak powinien wyglądać taki zbiór, a nie konkretna implementacja takiej kolekcji.

Przydałoby się więc opisać kilka operacji, które są uniwersalne dla każdego typu danych. W zależności od ich złożoności czasowej oraz pamięciowej będzie można dokonywać ich oceny pod kątem przydatności we własnych projektach informatycznych.

Operacje można podzielić ze względu na funkcje na dwie grupy: zapytania oraz operacje modyfikujące, które mogą zmieniać cały zbiór. Poniżej zamieszczamy listę typowych operacji na zbiorze dynamicznym. Nie wszystkie są jednak wymagane w większości ze struktur danych.

Dowolny zbiór dynamiczny

SEARCH (S, k)

Jest to zapytanie, które dla danego zbioru S oraz pewnego klucza k zwraca wskaźnik do elementu, który jest identyfikowany za pomocą k.

INSERT (S, d)

Jest to funkcja modyfikująca , służąca do zbioru S dodaje pewien element d

DELETE (S, d)

Jest to funkcja modyfikująca, za pomocą której ze zbioru S usuniemy pewien element x.

MINIMUM (S)

Jest to zapytanie, które zwraca wskaźnik, dla liniowo uporządkowanego zbioru S, do elementu o najmniejszej wartości klucza

MAXIMUM (S)

Zapytanie, które w liniowo uporządkowanym zbiorze S zwraca element o największym kluczu.

SUCCESSOR (S, d)

Zapytanie zwracające dla danego elementu d o kluczu z pewnego liniowo uporządkowanego zbioru S następnik tego elementu lub wartość odpowiadającą NULL, jeśli jest to wartość największą w zbiorze.

PREDECESSOR (S, d)

Zapytanie, które dla pewnego elementu d o kluczu z liniowo uporządkowanego zbioru S daje w wyniku poprzednika tego elementu lub wartość odpowiadającą NULL, jeśli jest to najmniejsza wartość w zbiorze.