Wprowadzenie

Podobnie jak funkcje, tablice do języków programowania trafiły z matematyki. Stanowią realizację obiektu, który w algebrze nazywa się macierzą. W matematyce macierz ma zazwyczaj dwa rozmiary (ale można to uogólniać). W fizyce występują obiekty zwane wektorami. Matematyka zna obiekty, które potocznie nazywane są macierzą wierszową lub macierzą kolumnową.

Języki programowania wszystko to wrzucają do wora zwanego tablice.

Zmienne złożone

Zmienna prosta to taka zmienna, w której przechowywać można jedną wartość zadanego typu.

Tablice to zmienne złożone, czyli obiekty, które mogą przechowywać wiele wartość jednego typu. Wszystkie wartości tablicy są „ponumerowane”, co umożliwia niezależny dostęp do każdej z nich.

Podobnie jak w przypadku macierzy operuje się indeksami, określającymi dokładne miejsce wartości w tablicy.

1. W przypadku tablicy jednowymiarowej indeks, to, po prostu, numer elementu.
2. W przypadku tablicy dwuwymiarowej indeksy są dwa: numer wiersza i numer kolumny.
3. I tak dalej.

Deklaracja tablicy mieści się w ogólnej zasadzie deklarowania różnych rzeczy.

• zmienna: typ nazwa;
• funkcja: typ nazwa( );¹
• tablica: typ nazwa[ ];²

W nawiasach kwadratowych podczas deklaracji tablicy podaje się jej rozmiar czyli liczbę elementów.

W przypadku tablic dwuwymiarowych deklaracja jest taka: typ nazwa[ ][ ]; w pierwszym nawiasie kwadratowym jest liczba wierszy, w drugim — liczba kolumn. Tablica trójwymiarowa to typ nazwa[ ][ ][ ]. W trzecim nawiasie to liczba warstw? I tak dalej.

Elementy tablicy numerowane są kolejnymi liczbami startując od zera. Zatem w tablicy o 5 elementach numerowane są one: 0, 1, 2, 3, 4. Trzeba o tym pamiętać.

Żeby przejrzeć wszystkie elementy tablicy używa się (najczęściej) pętli for.

int N = 10;
int tablica[N];
for (i = 0; i < N; i = i + 1)
	tablica[i] = i;

Powyższy program wypełnia tablicę tablica kolejnymi liczbami całkowitymi.

Tak, można zadeklarować tablicę której rozmiar określony jest zmienną, ale wartość tej zmiennej musi być określona w tym miejscu, gdzie deklarujemy tablicę.

Warto też pamiętać, że indeksem tablicy może być (w języku C) tylko i wyłącznie zmienna, stałą albo wyrażenie typu int. Nie będą dokonywane żadne automatyczne rzutowania ani konwersje.

Zakres indeksu tablicy

Deklarując tablicę o 10 elementach, możemy zadać pytanie: Co się stanie gdy użyta wartość indeksu tablicy będzie spoza zakresu 0–9?

Pierwsza odpowiedź jest bardzo prosta: Wartość indeksu tablicy o N elementach nie może przekraczać N-1 (ani być mniejsza od zera)!

Co jednak się stanie, gdy przekroczymy tę wartość? Popatrzmy na poniższy program:

#include <stdio.h>

int main(int argc, char **argv)
{
	int tab[100];
	int i=0;
	while (1)
	{
		printf("tab[%d] = %d\n", i, tab[i]);
		i++;
	}
	return 0;
}

Uruchomienie tego programu kończy się jakoś tak:

tab[1865] = 3236449
tab[1866] = 0
tab[1867] = 0
Segmentation fault (core dumped)

Przy czym, co jest ciekawe, numer elementu przy którym program kończy pracę za każdym razem jest inny: 1867, 1667, 2291, 2523,…

Wartości początkowe tablicy

Uruchomienie powyższego programu pozwala również zauważyć, że zadeklarowana tablica nie ma żadnych ustalonych wartości. Są one przypadkowe i odwzorowują pierwotną zawartość tego miejsca pamięci operacyjnej, w której jest tablica.

Deklarując tablicę można nadać jej wartości:

int tablica[5] = { 1, 2, 3, 4, 5};

pamiętać trzeba, że liczba wartości musi być mniejsza lub równa od zadeklarowanej liczby elementów tablicy. Nie można w ten sposób nadawać wartości tablicom o liczbie elementów zadawanej z użyciem zmiennej. Nie jest poprawne:

int N = 3;
int tab[N] = {1, 2, 3}

Gdy liczba elementów nadających wartości początkowe tablicy jest mniejsza niż rozmiar tablicy, pozostałe wartości otrzymują wartość zero. W szczególności najprostsza metoda „wyzerowania” tablicy na początku obliczeń jest taka:

double x[1000] = {0.0};

Wyszukiwanie binarne

Tematem kolejnych zajęć jest wyszukiwanie binarne. Założenia są następujące:

1. Mamy tablicę (dowolnego typu) o N elementach wypełnioną liczbami ułożonymi w kolejności rosnącej (albo malejącej)³.
2. Zadaniem jest sprawdzenie czy wielkość x (tego samego typu co tablica) znajduje się wśród elementów tablicy.
   1. najprostszy wariant pytanie — odpowiedź tak, nie;
   2. wariant bardziej rozbudowany: odpowiedź na który miejscu w tablicy wartość się znajduje, albo informacja, że jej tam nie ma;
   3. wariant najbardziej zaawansowany: albo informacja, że wartość znajduje się w tablicy, albo informacja w którym miejscu tablicy należy ją dopisać; samo dopisanie wartości nie musi być realizowane.
3. Instrukcja do tego zadania zatytułowana jest Laboratorium 5: Tablice. Wyszukiwanie binarne, ale realizujemy ją w okrojonym zakresie bez budowania funkcji rozwiązującej zadanie⁴.
4. Całą „trudność” zadania polega na tym, że problem ma być rozwiązany z użyciem metody wyszukiwania binarnego. Metoda jest właściwie identyczna jak w zadaniu poprzednim (Metoda połowienia). Tablicę można potraktować jak funkcję. Podstawowa różnica polega na tym, że indeksy tablicy (spełniają rolę zmiennej niezależnej $x$ funkcji $f(x)$) są nieciągłe — przyjmują kolejne wartości całkowite: 0, 1, 2,…
5. Algorytm wyszukiwania binarnego opisany jest na slajdach do przedmiotu Technologia Informacyjne; wykład „Złożoność obliczeniowa. «Trudne» zadania” (slajd 91 i następne).

Wersja PDF…

…jest również dostępna.