IMG960 (3)

Użyteczność algorytmu:

• klasa złożoności 0(m+n) gdzie *m" ilość możliwych wartości a „n" ilość sortowanych elementów

Dynamiczne struktury danych - zespół elementów inaczej węzły które są reprezentowane przez rekordy, zmieniają skład, wymiary i strukturę podczas wykonywania programu. Przykładem są: listy i drzewa. Do konstrukcji dynamicznych struktur danych stosuję się wskaźniki. Typy wskaźnikowe nie są strukturalne więc należą do typów skalarny.

Liść - to element nie mający potomków

Węzeł wewnętrzny - to każdy węzeł w strukturze drzewa nie będący korzeniem ani liściem.

Stopniem węzła - określamy liczbę przyporządkowanych mu potomków

Długość ścieżki wewnętrznej drzewa określamy jako sumę długości ścieżek wszystkich elementów drzewa.

USTA JEDNOKIERUNKOWA:

Każdy element jest pojedynczym rekordem składający się z co najmniej dwóch wartości pól: pola wartości i wskaźnika. Nie jest możliwy bezpośredni dostęp do dowolnego jej elementu. Dotarcie do n-tego elementu listy wymaga wcześniejszego przejścia przez n-1 poprzedników.

Możliwość operacji na liście:

	•	wstawanie na początek
Ur	•	wstawanie elementu na koniec
Śch	0	usunięcie pierwszego
	0	odczyt pierwszego
Wyr
	USTA DWUKIERUNKOWA:

Jedr

Dla każdego składnika poza pierwszym i ostatnim jest określony składnik poprzedni i następny.

Kotn

STOS: możliwe wstawianie, odczytywanie i usuwanie pierwszego (UFO)

Skońi

KOLEJKA(pojedyncza, jednokierunkowa).wstawianie elementu na koniec listy, odczyt i usuwanie pierwszegofFIFO)

Najszybsze sortowania:

1.    szybkie

2.    kubełkowe

3.    wybór

4.    bąbelkowe

Drzewo binarne

• drzewem drugiego stopnia każdy jego węzeł może mieć co najwyżej dwóch potomków.