Szyk

Tablica (zwana również wektorem lub macierzą ) w informatyce wskazuje złożoną, statyczną i jednorodną strukturę danych .

Tablice, obecne praktycznie we wszystkich językach programowania lub skryptów , inspirowane są matematycznym pojęciem wektora (w przypadku jednowymiarowych) lub macierzy (w przypadku tablic dwuwymiarowych). Tablica jest ogólnie klasyfikowana jako konstruktor typu : innymi słowy, pozwala na definiowanie nowych typów danych, począwszy od istniejących typów, poprzez agregację różnych obiektów tego samego typu. Każdy obiekt składowy jest identyfikowany za pomocą indeksu całkowitoliczbowego w przypadku jednowymiarowym lub za pomocą indeksów całkowitoliczbowych D w przypadku D- wymiarowym.

Funkcje

Wektor n liczb całkowitych z numeracją indeksów od 0

Tablicę można traktować jako rodzaj kontenera, którego pola nazywane są komórkami (lub elementami ) samej tablicy. Każda z komórek zachowuje się jak tradycyjna zmienna ; wszystkie komórki są zmiennymi tego samego, istniejącego wcześniej typu, zwanego typem podstawowym tablicy. Będziemy więc mówić o typach takich jak „tablica liczb całkowitych”, „tablica ciągów”, „tablica znaków” i tak dalej. To, co uzyskuje się przez zadeklarowanie go, jest więc statycznym i jednorodnym kontenerem wartości, zmiennych lub obiektów . W niektórych językach rozmiar tablicy (tj. liczba komórek, z których się składa) jest uważany za część definicji typu tablicy; w tym przypadku będziemy mówić dokładniej o typach takich jak „tablica 100 znaków” lub „tablica 10 liczb całkowitych”.

Każda z komórek w tablicy jest identyfikowana przez wartość indeksu . Indeks jest na ogół liczbowy, a wartości, które indeksy mogą przyjmować, są ciągłymi liczbami całkowitymi zaczynającymi się od 0 lub 1 lub, rzadziej, od dowolnej wartości, jak w Pascalu. Możemy więc mówić o komórce o indeksie 0, indeksie 1 i ogólnie o indeksie N, gdzie N jest liczbą całkowitą z przedziału od 0 (lub 1) do maksymalnej wartości indeksów tablicy.

Możliwość dostępu do elementów poprzez indeks jest główną cechą tablicy. Możliwe jest uzyskanie indywidualnego dostępu do jednej z jego ogólnych pozycji („dostęp losowy”, jak w przypadku pamięci), a także przewijanie jej sekwencyjnie w obu kierunkach przez cykl iteracyjny we wszystkich jego elementach lub zaczynając od niektórych z nich.

Oto przykład, który używa składni C (podobnej jednak do wielu innych języków) do zdefiniowania tablicy i przypisania wartości jej elementom:

 wektor int [ 10 ]; / * definiuje zmienną o nazwie "vector" jako tablicę 10 liczb całkowitych * /  
 wektor [ 0 ] = 0 ; / * przypisuje wartość "0" do komórki indeksu 0 * /    
 wektor [ 1 ] = 1 ;  
 wektor [ 2 ] = 1 ;  
 wektor [ 3 ] = 2 ;  
 wektor [ 4 ] = 3 ;  

(Wektor wskazany powyżej zawiera pierwsze pięć liczb ciągu Fibonacciego ).

Niektóre języki dopuszczają indeksy nieliczbowe, na przykład łańcuchy. W tym przypadku mówimy o hash table lub associative array , ponieważ każda wartość ciągu użyta jako indeks jest powiązana z wartością tablicy. Zobaczmy przykład w języku PHP :

$ osoba [ "imię" ]  =  "Jan" ; 
$ osoba [ "nazwisko" ]  =  "Kowalski" ; 
$ osoba [ "wiek" ]  =  32 ;

Jak widać, przykład jest bardzo podobny do poprzedniego; jedyną istotną różnicą (poza niewielką różnicą czysto syntaktyczną między językami) jest to, że indeksem tablicy jest łańcuch. Co więcej, doświadczony czytelnik będzie mógł zaobserwować, że w PHP nie ma ustalonego ograniczenia "typu podstawowego" dla wszystkich komórek tablicy: pierwszym dwóm został przypisany łańcuch , a trzecim liczba całkowita .

Tablice wielowymiarowe

Na koniec należy zauważyć, że tablica (czy to asocjacyjna, jak w PHP, czy nie) może mieć więcej niż jeden wymiar. Jeśli tablica ma wiele wymiarów, a zwłaszcza w przypadku dwuwymiarowym, często nazywa się ją „matrycą”, odnosząc się do matematycznego pojęcia macierzy, z którego czerpie inspirację. Różnica polega na tym, że macierz ma dwa (lub więcej) indeksy, z których każdy indeksuje wymiar, a każdy element jest identyfikowany przez kombinację wartości wszystkich indeksów wektora w określonej kolejności. Oto przykład:

[ 0 ] [ 0 ] = 1 ;  
[ 0 ] [ 1 ] = 2 ;  
[ 1 ] [ 0 ] = -1 ;  
[ 1 ] [ 1 ] = 1 ;  

W tym przykładzie liczbowym podaliśmy czterem elementom dwuwymiarowej tablicy A pewne wartości liczbowe. Każdy element jest jednoznacznie zidentyfikowany, a zatem dostępny, tylko poprzez określenie obu indeksów. Ponadto nie jest możliwa zamiana pozycji indeksów: w rzeczywistości element A [0] [1], który jest równy 2, różni się od elementu A [1] [0], który jest równy - 1.

W poniższym przykładzie widzimy jednak przypadek indeksowania za pomocą ciągów:

$ osoba [ 0 ] [ "imię" ]  =  "Samuel" ; 
$ osoba [ 0 ] [ "nazwisko" ]  =  "Rossi" ; 
$ osoba [ 1 ] [ "imię" ]  =  "George" ; 
$ osoba [ 1 ] [ "nazwisko" ]  =  "Biały" ;

W tym przypadku każda wartość odpowiada charakterystyce określonej osoby. Pierwszy indeks, w tym przypadku liczbowy (na przykład student pierwszego roku), identyfikuje osobę. Drugi indeks, w tym przypadku łańcuch, wskazuje daną cechę. W konsekwencji pierwszy indeks nie jest wystarczający, aby uzyskać dostęp do elementu, ponieważ nie wskazuje, której cechy potrzebujemy; ale nawet nie drugiego, ponieważ nie wskazuje, do której osoby się odnosimy. Jest to zatem połączenie obu wskaźników w celu zidentyfikowania wartości.

Dwuwymiarową tablicę można oglądać jako tabelę, w której pierwsza kolumna zawiera wartości indeksu, pierwszy wiersz wartości innego indeksu, a poszczególne komórki poszczególne elementy. Na tych samych zasadach, jeśli ma trzy wymiary, jest widziany jako sześcian. Macierz może również zawierać więcej niż trzy indeksy, ale dzieje się tak tylko w bardzo szczególnych przypadkach, na przykład w aplikacjach naukowych lub hurtowni danych . Macierz o trzech lub więcej wymiarach jest dokładniej zdefiniowana jako tensor .

Tablice i struktury kontrolne

Większość programów używających tablic używa struktury kontrolnej " pętle for " do przechodzenia przez tablice , to znaczy do sekwencyjnego dostępu do komórek . Pętla for nadaje się bardzo naturalnie do łącznego użycia tablicy właśnie dlatego, że pozwala na określenie konkretnego typu iteracji pewnego zestawu instrukcji, kontrolowanego przez indeks, który przyjmuje zestaw zwykle całkowitych i ciągłych wartości. Na przykład kod Java do drukowania zawartości tablicy n liczb całkowitych może wyglądać następująco:

 for ( int  i = 0 ;  i < wektor . length ;  i ++ )  // for i rosnące w kroku 1 od 0 do długości wektora 
     System . się . println ( wektor [ i ] );  // drukuj i-tą komórkę

Oto prosty algorytm obliczania maksimum, minimum i średniej wektora liczb całkowitych napisany przy użyciu języka programowania Java:

if ( vector . length  ! =  0 )  // sprawdź, czy wektor zawiera co najmniej jeden 
{    double  media ; 
    int  max  =  wektor [ 0 ] ,  min  =  wektor [ 0 ] ,  suma  =  0 ; 
    for ( int  i = 1 ; i < wektor . length ; i ++ )  // skanowanie w kroku 1 od 0 do długości wektora 
    {    if ( wektor [ i ] > max ) 
            max  =  wektor [ i ] ; 
        if ( wektor [ i ] < min ) 
            min  =  wektor [ i ] ; 
        suma  + =  wektor [ i ] ; 
    } 
    średnia  =  (( podwójna ) suma ) / wektor . długość ; 
    System . się . println ( "Minimum:" + min ); 
    System . się . println ( "Maks:" + max ); 
    System . się . println ( "Media:" + media ); 
} 
inny { 
    System . się . println ( "Wektor nie zawiera elementów" ); 
}

Aspekty wdrożeniowe

Tablice są zazwyczaj alokowane w ciągłych obszarach pamięci komputera . Tablica zajmie obszar pamięci, którego całkowity rozmiar jest określony przez rozmiar typu podstawowego pomnożony przez całkowitą liczbę komórek. Pobranie elementu na podstawie indeksu następuje poprzez dodanie początkowego adresu pamięci tablicy (znanego kompilatorowi lub interpreterowi ) wartości indeksu pomnożonej przez rozmiar typu bazowego. Tak więc, jeśli tablica liczb całkowitych jest przypisana do adresu pamięci 1000, na maszynie, w której liczby całkowite zajmują 4 bajty, jej piąty element (o indeksie 4) zostanie przydzielony na pozycji 1000+ (4 * (5-1 )) = 1016 . Ta reguła pozwala na uzyskanie wydajnego dostępu do komórek tablicy pod względem czasu spędzonego, poprzez pośrednie mechanizmy adresowania, które są dostarczane przez wszystkie procesory (a więc przez wszystkie języki maszynowe) lub poprzez numeryczne manipulacje wskaźnikami wewnątrz programu.

Sprawdź limity

Niektóre języki, zwłaszcza kompilowane , nie narzucają środowisku wykonawczemu kontroli poprawności indeksów używanych do dostępu do określonej komórki tablicy. W konsekwencji, w programie napisanym w C, jeśli tablica 20 elementów o rozmiarze 2 bajtów jest przydzielona do adresu 1000, ostatnia ważna komórka ma indeks 19 i adres 1038; ale jeśli programista przez pomyłkę spróbuje uzyskać dostęp do czterdziestej komórki (która nie istnieje), język nie wykryje błędu i zapewni niepoprawny dostęp do komórki pamięci 1078.

Zazwyczaj te języki programowania nie określają dokładnego wyniku odczytu lub zapisu poza granicami tablic, co czyni ten mechanizm źródłem błędów w programach obliczających nieprawidłową wartość indeksu. Powodem jest to, że rozmieszczenie i wyrównanie danych przechowywanych w programie (a więc zgodność komórek pamięci z komórkami tablic i zmiennych) zależy zarówno od implementacji przyjętego kompilatora, jak i od implementacji architektury programu. system, na którym będzie działać program.

W najlepszym przypadku, jeśli pamięć, do której próbujesz uzyskać dostęp, nie została zaalokowana przez program, wynikiem będzie odczytanie losowej wartości lub zapisanie do miejsca w pamięci, które nie jest używane nigdzie indziej w programie; w najgorszym przypadku możliwe jest, że ten obszar pamięci został zamiast tego przydzielony dla zmiennej lub innej tablicy, a w konsekwencji program nadpisze jej dane, zmieniając jego wykonanie w nieprzewidywalny sposób.

Tego typu błędy w indeksowaniu tablic są, obok błędów wskaźników, jedną z najczęstszych przyczyn nieprawidłowego działania programów napisanych w językach C i C++ . Inne języki (np . Java ) wymagają, aby środowisko wykonawcze, w którym uruchamiany jest program, blokowało dostęp do tablic poza ustalonymi limitami i ewentualnie sygnalizuje ten problem błędem w programie.

Powiązane pozycje

• Struktura danych
• Tablica dynamiczna
• Tablica asocjacyjna
• Tablica postrzępiona
• Wektor narkotyków

Inne projekty

Inne projekty

• Wikimedia Commons

• Wikimedia Commons zawiera obrazy lub inne pliki na tablicach

Linki zewnętrzne

• Tablice i iteratory w „Nauce programowania”, bezpłatnej książce o podstawach programowania.