Przejdź do zawartości

Struktury danych/Podstawowe informacje

Z Wikibooks, biblioteki wolnych podręczników.
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

[edytuj]

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.