Tablice – wprowadzenie

TablicetablicaTablice są kontenerami służącymi do przechowywania dużej ilości danych tego samego typu. W tym e‑materiale zajmiemy się tablicami statycznymitablica statycznatablicami statycznymi.

Podczas tworzenia tablicy statycznej należy podać jej rozmiar; nie można go później zmienić na mniejszy ani większy. Niezbędne jest również określenie, jakiego typu dane będą przechowywane w tablicy. Podobnie jak to się dzieje w przypadku rozmiaru, typ danych nie może zostać zmieniony.

Gdy tworzymy tablicę, podajemy jej nazwę, rozmiar oraz wskazujemy typ danych, które chcemy przechowywać. Definicja tablicy zapisana w pseudokodzie ma następującą postać:

Linia 1. zbior otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości tablica liczb całkowitych o rozmiarze 5 kropka.

W przedstawionym przykładzie tablica nosi nazwę zbior, ma rozmiar równy 5 oraz będzie służyć do przechowywania liczb całkowitych. Określenie ma rozmiar równy 5 oznacza, że w tablicy jest miejsce na zapisanie pięciu wartości.

Rhcxq4b3M9ZGK
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Każdy prostokąt na rysunku wyżej reprezentuje jeden element w tablicy zbior. Tablica nie zawiera jeszcze żadnych danych. Przyjmijmy, że chcielibyśmy w niej zapisać liczbę 10. Jak to zrobić?

Każde miejsce w tablicy ma własny numer, nazywany indeksem. Indeksy są kolejnymi liczbami naturalnymi. W wielu językach programowania (np. C++ lub Java) indeksowanie miejsc w tablicy zaczyna się od zera.

Jeżeli zapisujemy algorytm w postaci pseudokodu, mamy dowolność co do wyboru sposobu numerowania elementów tablic (nie istnieje określająca to jednoznacznie reguła). Możemy rozpoczynać indeksowanie od liczby 0 lub 1. My będziemy indeksować tablice zaczynając od 0; poszczególnym przechowywanym elementom odpowiadają zatem następujące indeksy:

RXiReReMvbR45
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Zapiszemy liczbę 10 na pierwszym wolnym miejscu. Tablica jest pusta, więc będzie to element o indeksie równym 0. Żeby zapisać wartość w tablicy, musimy odwołać się do jej nazwy (w tym przypadku jest nią zbior), a następnie wewnątrz pary nawiasów kwadratowych podać numer pola, do którego chcemy się dostać. Na końcu wpisujemy znak równości oraz liczbę, którą chcemy umieścić wybranym miejscu tablicy:

Linia 1. zbior otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 10.

Po wykonaniu polecenia zawartość tablicy będzie wyglądała następująco:

R1N2HCrIUXqoz
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Umieśćmy w tablicy jeszcze kilka liczb:

Linia 1. zbior otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości 66. Linia 2. zbior otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości 23. Linia 3. zbior otwórz nawias kwadratowy 3 zamknij nawias kwadratowy znak równości 89.
RTvw83fIsKtD5
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

W jaki sposób z kolei odczytywać wartości zapisane już w tablicy? Należy podać nazwę tablicy oraz indeks elementu, który chcemy odczytać. A zatem wydanie polecenia:

Linia 1. wypisz zbior otwórz nawias kwadratowy 2 zamknij nawias kwadratowy.

spowoduje wypisanie liczby 23.

Oczywiście dane w tablicy można nadpisywać. Jeżeli na miejscu o indeksie 2 nie chcemy przechowywać już liczby 23, lecz 15, postępujemy tak samo, jakby miejsce to było puste:

Linia 1. zbior otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości 15.
RQK0matCcUVpz
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Poruszanie się po tablicy

Wiemy już, czym są tablice. Teraz zastanówmy się, w jaki sposób można się po nich poruszać, czyli przechodzić od jednego elementu do innego.

Do przeglądania i przetwarzania tablic zazwyczaj wykorzystywana jest pętla licznikowa dla. Jeżeli chcemy odczytać lub zapisać elementy zbioru o znanym rozmiarze, taka pętla sprawdzi się idealnie. Ponieważ liczba elementów tablicy statycznej jest z góry określona, a indeksy są kolejnymi liczbami naturalnymi, dzięki pętli dla możemy z łatwością przechodzić od jednego elementu zbioru do innego.

Najprostszym przykładem takiej operacji jest wypisanie wszystkich liczb znajdujących się w tablicy.

Linia 1. tablica otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias kwadratowy 1 przecinek 2 przecinek 4 przecinek 5 przecinek 7 zamknij nawias kwadratowy. Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka przecinek długość otwórz nawias okrągły tablica zamknij nawias okrągły minus 1 wykonuj. Linia 4. wypisz tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy.

Używając pętli dla musimy pamiętać o dwóch ważnych rzeczach. Po pierwsze, indeksy tablic w pseudokodzie mogą zaczynać się zarówno od zera, jak i jedynki. My zadecydowaliśmy, że tablica będzie indeksowana od wartości 0.

Drugie zagadnienie jest związane z pierwszym. Skoro indeksy zaczynają się od zera, ostatni element tablicy nie jest oznaczony numerem takim jak rozmiar tablicy, lecz mniejszym od tej wartości o 1. Jeżeli spróbujemy dostać się do elementu o nieistniejącym indeksie (większym niż długość tablicy minus 1), działanie programu zakończy się komunikatem o błędzie.

Słownik

najdłuższy spójny podciąg rosnący
najdłuższy spójny podciąg rosnący

fragment ciągu składający się z elementów ułożonych bezpośrednio po sobie, w kolejności rosnącej, czyli w ten sposób, że każdy kolejny element jest większy od poprzedniego

podciąg spójny
podciąg spójny

ciąg powstały przez wybranie określonej liczby elementów z ciągu występujących bezpośrednio po sobie

tablica
tablica

kontener (struktura danych) służący do przechowywania danych (wartości) tego samego typu; każdy element ma określony indeks (kolejny numer); w pamięci komputera elementy tablicy są ułożone kolejno jeden obok drugiego

tablica statyczna
tablica statyczna

tablica, której rozmiar jest definiowany w programie; rozmiar ten musi więc być podany jako wartość liczbowa, nazwa stałej (const) lub jako wyrażenie zbudowane z wartości liczbowych i stałych