To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
STRUKTURY DANYCH
Struktury liniowe
Tablica
Opis:
określamy zwarty obszar pamięci, gdzie każda komórka przechowuje informacje określonego typu i do każdej z nich jest bezpośredni dostęp poprzez jej indeks.
Budowa:
Komórka: pojedyncza wartość, pole dwuelementowe, struktura Złożoność obliczeniowa
Pobranie:
Dostęp do określonego elementu: natychmiastowy, ze względu na indeksowanie każdej komórki tablicy _ O(1).
Wyszukanie:
Wyszukanie elementu o określonej wartości: w najgorszym wypadku będziemy musieli odczytać wszystkie n komórek _ O(n).
Wstawienie:
Wstawienie nowego elementu na określoną pozycję: wstawienie nowego elementu na koniec tablicy wymaga po prostu powiększenia rozmiaru tablicy o 1 i wpisania wartości do ostatniej komórki (zatem jest to stała liczba operacji, niezależna od liczby elementów, czyli O(1)), jednak wstawienie nowego elementu w środek tablicy wymaga powiększenia rozmiaru tablicy o 1 oraz przesunięcia wszystkich elementów leżących na prawo od wstawianego o 1 pozycję w prawo, czyli w najgorszym wypadku (wstawienie elementu na pierwszą pozycję): stała liczba operacji zwiększania rozmiaru tablicy + n przesunięć + 1 zapisanie= O(1) + O(n) + O(1) = O(n).
Usunięcie:
Usunięcie elementu: analogicznie do wstawiania, w najgorszym wypadku (usunięcie pierwszego elementu) trzeba przesunąć n−1 elementów o 1 pozycję w lewo (n − 1 operacji) i zmniejszyć rozmiar tablicy o 1 (stała liczba operacji) _ O(n).
Lista jednokierunkowa
Opis:
jest to struktura wykorzystująca wskaźniki, gdzie każda komórka składa się z dwóch pól
Budowa:
każda komórka składa się z dwóch pól: pola danych (mogącego być _ jak w przypadku tablicy _ rozbudowaną strukturą) oraz wskaźnika na następny element. Ponadto, lista musi mieć (co najmniej) jedną wyszczególnioną komórkę zawierającą wyłącznie wskaźnik na pierwszy element , tzw. głowę.
Cechy charakterystyczne:
W porównaniu do tablicy, lista posiada tę zaletę , że nie musi być zwartym obszarem pamięci.
Złożoność obliczeniowa
Pobranie:
Dostęp do elementu: jeżeli element jest umieszczony na końcu listy, to aby do niego dotrzeć, trzeba przejrzeć wszystkie pozostałe n−1 elementów - O(n).
Wyszukanie:
Wyszukanie elementu: jak wyżej _ O(n).
Wstawienie:
Wstawienie elementu: należy utworzyć nową komórkę O(1), wypełnić wartość pola danych O(1), pole wska¹nika wypełnić wartością głowy O(1), a wartość głowy wypełnić wartością wskazującą na nowy element O(1) _ całkowity czas omawianej operacji wynosi zatem O(1).
(…)
…
Pobranie: Wstawienie:
tak jak w przypadku kolejki _ złożoność operacji dostępu (pobrania) oraz dodania elementu wynosi O(1),
Wyszukanie: Usunięcie:
dla wyszukania i usunięcia konkretnego elementu to O(n).
Struktury nieliniowe
Drzewo ukorzenione
Opis:
Drzewo ukorzenione jest strukturą hierarchiczną,
Drzewo binarne- każdy element (nie będący liściem) posiada
co najwyżej dwóch potomków. Rozpatrzmy drzewo…
…, który nie posiada rodzica (istnieje dokładnie jeden taki element). Z kolei elementy nie posiadające potomków zwane są liściami.
Cechy charakterystyczne:
Wychodząc od spostrzeżenia, że w każdym kolejnym poziomie drzewa jest dwa razy więcej elementów niż w poprzednim, liczbę wszystkich elementów można wyznaczyć jako sumę nast. ciągu geometrycznego, a0=1, q=2: 20 + 21 + 22 + . . . + 2k−1 = 2k − 1= =n. Korzystając teraz z definicji logarytmu otrzymamy:
k = log2(n + 1), a zatem k = O(log n).
Kopiec
Opis:
takie drzewo binarne (prawie) pełne , w którym wartość rodzica jest zawsze nie mniejsza (nie większa) od obu potomków (w przypadku elementu bn/2c i nieparzystej liczby elementów _ od jedynego potomka).
Cechy charakterystyczne:
w korzeniu mamy zawsze element maksymalny (minimalny).
Biorąc pod uwagę powyższe, utworzenie…
… ma być z jednakowym prawdopodobieństwem odwzorowywana na każdą z m pozycji.
Kolejka i Stos są strukturami o specyficznych zastosowaniach i tylko dzięki nałożonym ograniczeniom posiadają korzystniejsze czasy dostępu lub wstawiania elementu (w stosunku do Tablicy i Listy).
• Kopiec ma korzystne czasy wstawiania i usuwania elementów w stosunku do pozostałych struktur (wprawdzie czasy wstawiania dla Listy, Kolejki…
... zobacz całą notatkę
Komentarze użytkowników (0)