Czas cofnąć się w czasie na lekcję. Chociaż dzisiaj nie myślimy o tych rzeczach w naszych fantazyjnych językach zarządzanych, są one oparte na tym samym fundamencie, więc spójrzmy, jak zarządza się pamięcią w C.
Zanim się zanurzę, krótkie wyjaśnienie znaczenia terminu „ wskaźnik ”. Wskaźnik to po prostu zmienna, która „wskazuje” miejsce w pamięci. Nie zawiera rzeczywistej wartości w tym obszarze pamięci, zawiera adres pamięci. Pomyśl o bloku pamięci jak o skrzynce pocztowej. Wskaźnik będzie adresem tej skrzynki pocztowej.
W C tablica jest po prostu wskaźnikiem z przesunięciem, przesunięcie określa, jak daleko w pamięci szukać. Zapewnia to czas dostępu O (1) .
MyArray [5]
^ ^
Pointer Offset
Wszystkie inne struktury danych albo się na tym opierają, albo nie używają sąsiedniej pamięci do przechowywania, co powoduje skrócenie czasu wyszukiwania losowego dostępu (chociaż istnieją inne korzyści z nieużywania pamięci sekwencyjnej).
Załóżmy na przykład, że mamy tablicę z 6 liczbami (6,4,2,3,1,5), w pamięci wyglądałoby to tak:
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
W tablicy wiemy, że każdy element znajduje się obok siebie w pamięci. Tablica AC (nazywana MyArraytutaj) jest po prostu wskaźnikiem do pierwszego elementu:
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
^
MyArray
Gdybyśmy chcieli spojrzeć w górę MyArray[4], dostęp byłby możliwy w następujący sposób:
0 1 2 3 4
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
^
MyArray + 4 ---------------/
(Pointer + Offset)
Ponieważ możemy bezpośrednio uzyskać dostęp do dowolnego elementu w tablicy, dodając przesunięcie do wskaźnika, możemy wyszukać dowolny element w tym samym czasie, niezależnie od wielkości tablicy. Oznacza to, że uzyskanie MyArray[1000]zajmie tyle samo czasu, co uzyskanie MyArray[5].
Alternatywna struktura danych to połączona lista. Jest to liniowa lista wskaźników, z których każdy wskazuje na następny węzeł
======== ======== ======== ======== ========
| Data | | Data | | Data | | Data | | Data |
| | -> | | -> | | -> | | -> | |
| P1 | | P2 | | P3 | | P4 | | P5 |
======== ======== ======== ======== ========
P(X) stands for Pointer to next node.
Zauważ, że utworzyłem każdy „węzeł” we własnym bloku. Wynika to z faktu, że nie ma gwarancji, że będą (i najprawdopodobniej nie będą) przylegać do pamięci.
Jeśli chcę uzyskać dostęp do P3, nie mogę uzyskać bezpośredniego dostępu, ponieważ nie wiem, gdzie jest w pamięci. Wiem tylko, gdzie jest root (P1), więc zamiast tego muszę zacząć od P1 i podążać za każdym wskaźnikiem do pożądanego węzła.
Jest to czas wyszukiwania O (N) (Koszt wyszukiwania rośnie wraz z dodawaniem każdego elementu). Dostanie się do P1000 jest znacznie droższe niż dotarcie do P4.
Struktury danych wyższego poziomu, takie jak tabele skrótów, stosy i kolejki, wszystkie mogą wewnętrznie korzystać z tablicy (lub wielu tablic), natomiast listy połączone i drzewa binarne zwykle używają węzłów i wskaźników.
Można się zastanawiać, dlaczego ktokolwiek użyłby struktury danych wymagającej przejścia liniowego w celu wyszukania wartości zamiast po prostu użycia tablicy, ale ma to swoje zastosowanie.
Weź ponownie naszą tablicę. Tym razem chcę znaleźć element tablicy, który ma wartość „5”.
=====================================
| 6 | 4 | 2 | 3 | 1 | 5 |
=====================================
^ ^ ^ ^ ^ FOUND!
W tej sytuacji nie wiem, jakie przesunięcie dodać do wskaźnika, aby go znaleźć, więc muszę zacząć od 0 i podążać w górę, aż go znajdę. Oznacza to, że muszę wykonać 6 kontroli.
Z tego powodu wyszukiwanie wartości w tablicy jest uważane za O (N). Koszt wyszukiwania rośnie, gdy tablica się powiększa.
Pamiętasz wyżej, gdzie powiedziałem, że czasami użycie niesekwencyjnej struktury danych może mieć zalety? Wyszukiwanie danych jest jedną z tych zalet, a jednym z najlepszych przykładów jest Drzewo Binarne.
Drzewo binarne to struktura danych podobna do listy połączonej, jednak zamiast łączenia z pojedynczym węzłem, każdy węzeł może łączyć się z dwoma węzłami potomnymi.
==========
| Root |
==========
/ \
========= =========
| Child | | Child |
========= =========
/ \
========= =========
| Child | | Child |
========= =========
Assume that each connector is really a Pointer
Gdy dane są wstawiane do drzewa binarnego, używa kilku reguł, aby zdecydować, gdzie umieścić nowy węzeł. Podstawową koncepcją jest to, że jeśli nowa wartość jest większa niż rodzice, wstawia ją w lewo, a jeśli jest niższa, wstawia ją w prawo.
Oznacza to, że wartości w drzewie binarnym mogą wyglądać następująco:
==========
| 100 |
==========
/ \
========= =========
| 200 | | 50 |
========= =========
/ \
========= =========
| 75 | | 25 |
========= =========
Szukając drzewa binarnego o wartości 75, musimy odwiedzić tylko 3 węzły (O (log N)) z powodu tej struktury:
- Czy 75 jest mniejsze niż 100? Spójrz na Right Node
- Czy 75 jest większe niż 50? Spójrz na lewy węzeł
- Jest 75!
Mimo że w naszym drzewie znajduje się 5 węzłów, nie musieliśmy patrzeć na pozostałe dwa, ponieważ wiedzieliśmy, że oni (i ich dzieci) nie mogą zawierać wartości, której szukaliśmy. Daje nam to czas wyszukiwania, który w najgorszym przypadku oznacza, że musimy odwiedzić każdy węzeł, ale w najlepszym przypadku musimy odwiedzić tylko niewielką część węzłów.
To tam tablice pobierają rytm, zapewniają liniowy czas wyszukiwania O (N), pomimo czasu dostępu O (1).
Jest to niezwykle ogólny przegląd struktur danych w pamięci, pomijający wiele szczegółów, ale mam nadzieję, że ilustruje siłę i słabość tablicy w porównaniu do innych struktur danych.