Struktury danych : Tablice

Nie będzie żadnych zaskoczeń, wybuchów i zwrotów akcji. Tablica to podstawowa struktura danych
dostępna praktycznie w każdym języku programowania. Tym samym powinna być wszystkim
doskonale znana :). Niemniej myślę, że warto usystematyzować informacje na jej temat.

Krótka charakterystyka:
Tablica może przechowywać określoną liczbę elementów, z których wszystkie są tego samego typu.
Do każdego elementu można się odwołać poprzez indeks, który reprezentuje adres elementu w
tablicy (nie mylić z adresem w pamięci :)) Oczywiście indeks pierwszego elementu tablicy jest
równy 0. Mówiąc, że tablica może przechowywać określoną liczbę elementów, mam na myśli to że
nie da się zmienić rozmiaru tablicy jako takiej – w niektórych rodzajach tablic zmiana rozmiaru
w czasie działania programu jest dla użytkownika możliwa, nie zmienia to jednak faktu, że pod
maską tworzona jest nowa tablica, o nowym rozmiarze, i do której są kopiowane elementy starej
tablicy.Także trzeba mieć to na uwadze – jak można się domyślić taka operacja kosztuje czas.

arrayRep

Reprezentacja tablicy w pamięci komputera:
Powyższy obrazek ilustruje sposób w jaki można wyobrażać sobie tablice w pamięci komputera.
Traktujac to szare coś jako pamięć, łatwo mozna zrozumieć, że elementy tablicy zajmuja miejsca
obok siebie i mają stały rozmiar (są w końcu tego samego typu).

Podstawowe operacje i ich wydajność:
Dostęp do elementu:
Do elementu tablicy można dostać się bardzo szybko (O(c)). Przyczyną takiego stanu rzeczy
jest to, że kolejne komórki zajmują miejsca obok siebie, tym samym znając rozmiar typu,
którego elementy przechowuje tablica i indeks szukanego elementu, możliwe jest bardzo szybkie
odnalezienie pożadanego adresu
Wstawianie elementu:
W tym wypadku wiele zależy od miejsca w które chcemy wstawić element. Jeżeli jest to ostatni
indeks to złożoność będzie wynosiła O(c). W wypadku gdy chcemy wstawić element gdzieś między
pierwszym i ostatnim to przyjmuje się, że średnia złożoność wynosi O(n). Wynika to z faktu
,że elementy muszą być przesunięte w taki sposób aby możliwe było wstawienie nowego.
Usuwanie elementu:
Sytuacja wygląda podobnie co przy wstawianiu. W wielu językach usuwając element z tablicy,
automatycznie pozostałe elementy są „przesuwane”.


Na koniec chciałbym pokazać jak małe są różnice w tworzeniu tablicy i dostępu do jej elementu
w kilku różnych językach. (tablice w Javascript i Python, są dosyć specyficzne, ale nie o tym jest ten
materiał :)). Tworzymy tablicę, taką jak na wspomnianym już obrazku i staramy się przypisać do
zmiennej jej trzeci element:

C#:

int[] exampleArray = new int[] {12, 14, -3, 32, 1, 44};
int thrid = exampleArray[2];

C++:

int exampleArray[6] = {12, 14, -3, 32, 1, 44};
int thrid = exampleArray[2]; 

Java:

int[] exampleArray = new int[] {12, 14, -3, 32, 1, 44};
int thrid = exampleArray[2];

Javascript:

var exampleArray = [12, 14, -3, 32, 1, 44];
var thrid = exampleArray[2];

Python:

exampleArray = [12, 14, -3, 32, 1, 44];
thrid = exampleArray[2];

 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *