• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Tablica asocjacyjna

    Przeczytaj także...
    AWK – interpretowany język programowania, którego główną funkcją jest wyszukiwanie i przetwarzanie wzorców w plikach lub strumieniach danych. Jest także nazwą programu początkowo dostępnego dla systemów operacyjnych będących pochodnymi UNIX-a, obecnie także na inne platformy.Perl – interpretowany język programowania autorstwa Larry’ego Walla początkowo przeznaczony głównie do pracy z danymi tekstowymi, obecnie używany do wielu innych zastosowań. Wzorowany na takich językach jak C, skryptowe: sed, awk i sh oraz na wielu innych.
    Lua − język skryptowy pierwotnie zaprojektowany dla rozszerzenia funkcjonalności różnych aplikacji, jednak często używany jako samodzielny język. Lua wiąże w sobie prostą składnię procedury (podobną do Pascala) z konstrukcjami opisu danych opartymi na tablicach asocjacyjnych i rozszerzalnej semantyce.

    Tablica asocjacyjna, tablica skojarzeniowa, mapa, słownik (ang. associative array, map, dictionary) – nazwa dla powszechnie stosowanego w informatyce abstrakcyjnego typu danych, który przechowuje pary (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza.

    Typ – w językach programowania opis rodzaju, struktury i zakresu wartości, jakie może przyjmować dany literał, zmienna, stała, argument, wynik funkcji lub wartość.OCaml znany pierwotnie jako Objective Caml to wielo-paradagmatowy język programowania oraz implementacja tego języka w postaci zestawu narzędzi i bibliotek.

    Formalnie typ tablicy asocjacyjnej odpowiada zbiorowi skończonych funkcji częściowych z typu klucza tablicy w typ wartości tablicy. Wiele złożonych danych jest naturalnie reprezentowanych przez tego typu tablice – np. drzewa plików, nagłówki poczty, a nawet wszystkie atrybuty obiektu czy przestrzeń nazw zmiennych.

    Abstrakcyjny typ danych (ang. Abstract data type - ADT) jest to tworzenie i opisywanie w formalny sposób typów danych tak, że opisywane są jedynie własności danych i operacji wykonywanych na nich (a nie przez reprezentację danych i implementację operacji).Drzewo AVL, nazywane również drzewem dopuszczalnym – zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielskij i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962.

    Tablice asocjacyjne realizowane są jako drzewa poszukiwań (BST, AVL, trie itp.) lub tablice mieszające. Typ danych klucza może być praktycznie dowolny. Najczęściej są to łańcuchy znaków (napisy), ale także liczby (całkowite, zmiennoprzecinkowe, zespolone), krotki itp.

    Cechy tablic asocjacyjnych[ | edytuj kod]

  • Najczęściej próba przypisania wartości do nieistniejącego klucza powoduje automatyczne utworzenie klucza i wówczas następuje zwykłe przypisanie.
  • Na ogół przypisanie nowej wartości do istniejącego klucza zastępuje poprzednią wartość, ale np. w języku OCaml z kluczami powiązane są listy wartości i przypisanie wartości do klucza powoduje tak naprawdę dopisanie jej na początek listy.
  • Sięgnięcie do nieistniejącego klucza zwykle kończy się błędem, ale np. w języku AWK zwracany jest pusty łańcuch znaków.
  • Istniejące implementacje tablic asocjacyjnych, bądź to dostępne bezpośrednio w danym języku programowania, bądź jako oddzielna biblioteka programistyczna na ogół oferują większą funkcjonalność niż tylko przypisanie wartości do klucza i pobranie wartości. Może ona obejmować następujące operacje:

    PHP – obiektowy język programowania zaprojektowany do generowania stron internetowych i budowania aplikacji webowych w czasie rzeczywistym.Tablica w informatyce to kontener danych dostępnych, w którym poszczególne komórki dostępne są za pomocą kluczy, które najczęściej przyjmują wartości numeryczne. Rozmiar tablicy jest albo ustalony z góry (tablice statyczne), albo może się zmieniać w trakcie wykonywania programu (tablice dynamiczne).
  • usunięcie pary (klucz, wartość);
  • stwierdzenie, czy dany klucz znajduje się w tablicy (bez pobierania wartości);
  • pobranie listy wszystkich kluczy lub przynajmniej możliwość iterowania po niej;
  • pobranie listy wszystkich wartości;
  • pobranie listy wszystkich par (klucz, wartość).
  • Tablice asocjacyjne w różnych językach programowania[ | edytuj kod]

    AWK[ | edytuj kod]

    W języku AWK tablica asocjacyjna nazywana jest tablicą (array). Kluczem może być pojedyncze wyrażenie (zamieniane zawsze na łańcuch znaków), albo lista wyrażeń, które są sklejane razem, a ciąg je separujący jest określony przez zmienną SUBSEP.

    Drzewo trie (wym. traj; od ang. retrieval, czyli odczyt) — drzewo poszukiwań przechowujące w węzłach fragmenty kluczy ("zwykłe" drzewa poszukiwań - np. BST, AVL - przechowują w węzłach całe klucze). To pozwala przyspieszyć wyszukiwanie, gdy koszt porównania całego klucza jest duży.W informatyce tablica mieszająca lub tablica z haszowaniem (ang. hash table, niekiedy błędnie tłumaczone jako "tablica haszująca") to struktura danych, która jest jednym ze sposobów realizacji tablicy asocjacyjnej, tj. abstrakcyjnego typu danych służącego do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp. Tablica mieszająca umożliwia również szybkie porównywanie danych, np. fragmentów tekstów, plików.
    tablica["Wikipedia"] = "Wolna encyklopedia";
    tablica[10, 12, 2006] = "środa";
    tablica[255] = 0xff;
    if ("Wikipedia" in tablica)
    	print tablica["Wikipedia"];
    

    C++[ | edytuj kod]

    W standardowej bibliotece języka C++ istnieje szablon map, który przyjmuje jako parametry dwa typy danych: typ klucza i typ wartości.

    JavaScript, JS – skryptowy język programowania, stworzony przez firmę Netscape, najczęściej stosowany na stronach internetowych. Pod koniec lat 90. XX wieku organizacja ECMA wydała na podstawie JavaScriptu standard języka skryptowego o nazwie ECMAScript. Głównym autorem JavaScriptu jest Brendan Eich.Krotka (ang. tuple) - struktura danych będąca odzwierciedleniem matematycznej n-ki, tj. uporządkowanego ciągu wartości. Krotki przechowują stałe wartości o różnych typach danych - nie można zmodyfikować żadnego elementu, odczyt natomiast wymaga podania indeksu liczbowego żądanego elementu.
    #include <iostream>
    #include <map>
    using namespace std;
    map<string, int> liczba_dni; // klucze typu string, wartości typu int
    
    liczba_dni["styczeń"] = 31; // wstawienie pary klucz, wartość
    liczba_dni["luty"]    = 28;
    liczba_dni["marzec"]  = 31;
    
    if (rok_przestępny)
       liczba_dni["luty"] = 29; // zmiana wartości związanej z kluczem "luty"
    
    // wyszukanie wartości klucza metodą 'find'
    if (liczba_dni.find("marzec") == liczba_dni.end())
        cout << "klucz 'marzec' nie występuje w tablicy";
    else
        cout << "liczba dni w marcu = " << liczba_dni["marzec"];
    

    | edytuj kod]

    $tablica = array("klucz" => "wartosc",
                     "nowy_klucz" => 2);
    // lub też:
    $tablica["klucz"] = "wartosc";
    $tablica["nowy_klucz"] = 2;
    
    //od PHP 5.4
    $tablica = ["klucz" => "wartosc", "inny_klucz" => 1];
    

    | edytuj kod]

    $tablica_asocjacyjna{"nazwa_elementu"}
    %kolejna_tablica_asocjacyjna = (apple  => "red", banana => "yellow", );
    

    JavaScript[ | edytuj kod]

    W języku JavaScript każdy obiekt jest tablicą asocjacyjną.

    Język programowania – zbiór zasad określających, kiedy ciąg symboli tworzy program komputerowy oraz jakie obliczenia opisuje.Python – język programowania wysokiego poziomu ogólnego przeznaczenia i rozbudowanym pakiecie bibliotek standardowych, którego ideą przewodnią jest czytelność i klarowność kodu źródłowego. Jego składnia cechuje się przejrzystością i zwięzłością.
    var tab_asoc = {};
    tab_asoc["klucz"]="wartość";
    //co jest równoważne
    tab_asoc.klucz="wartość";
    

    Python[ | edytuj kod]

    W języku Python tablice są nazywane słownikami (dictionary, dict). Kluczem może być dowolny obiekt, która posiada metodę __hash__. Jeśli chodzi o typy wbudowane, jako klucze mogą służyć liczby całkowite, zmiennoprzecinkowe, zespolone, łańcuchy znaków (zwykłe i unikodowe), niemodyfikowalne zbiory (immutable sets), krotki, a nawet funkcje. Natomiast listy, modyfikowalne zbiory ani słowniki nie mogą być kluczami.

    Biblioteka (w informatyce) – zbiór klas, funkcji (i ew. innych konstrukcji programistycznych), z których korzystają różne programy.Binarne drzewo poszukiwań (ang. Binary Search Tree (BST)) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz węzła a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. Dla pełnego drzewa BST o n węzłach pesymistyczny koszt każdej z podstawowych operacji wynosi O(log n). Złożoność obliczeniowa jest tak niska, ponieważ operacje wykonywane są wzdłuż drzewa. Z tego samego powodu w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do O(n). W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa h - wynosi on O(h). Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości posortowanych niemalejąco.
    tablica = {"Wikipedia": "Wolna encyklopedia",
               (10, 12, 2006): "środa",
               255: 0xff}
    
    # wypisanie wszystkich kluczy z tablicy
    for klucz in tablica:
     	print klucz
    
    # wypisanie wszystkich wartości z tablicy
    for wartosc in tablica.itervalues():
     	print wartosc
    
    # wypisanie jakie wartości są przypisane do jakich kluczy
    for klucz, wartosc in tablica.iteritems():
     	print klucz, '=>', wartosc
    
    # wyświetlenie wartości związanej z kluczem (łańcuchem) "Wikipedia"
    if "Wikipedia" in tablica:
     	print tablica["Wikipedia"]
    
    print tablica.get("Wikipedia", "brak klucza 'Wikipedia'")
    

    | edytuj kod]

    tablica = {
        klucz = 'wartość',
        innyklucz = 'innawartosc'
    }
    
    -- w przypadku kiedy klucz ma więcej niż jeden wyraz lub jest liczbą
    tablica = {
        ['klucz numer 1'] = 'wartosc',
        ['2'] = 'innawartosc'
    }
    
    -- lub inny zapis:
    
    tablica = {}
    tablica["klucz"] = "wartosc"
    -- lub
    tablica.klucz = 'wartosc'
    

    Zobacz też[ | edytuj kod]

  • tablica
  • Standard Template Library, STL (pol. standardowa biblioteka szablonów) – biblioteka C++ zawierająca algorytmy, pojemniki, iteratory oraz inne konstrukcje w formie szablonów, gotowe do użycia w programach.




    Reklama

    Czas generowania strony: 0.011 sek.