Matura - programowanie w C++

Definicja tablicy jest podobna do definicji zwykłej zmiennej, lecz zawiera dodatkowy element: liczbę komórek, którą podaje się w klamerkach kwadratowych:

Dostęp do poszczególnych komórek uzyskuje się poprzez nazwę tablicy oraz indeks komórki w klamerkach kwadratowych. Indeksy rozpoczynają się od 0, ostatnia komórka ma indeks o wartości liczba_komórek - 1.

int T[5]; // Komórki: T[0], T[1], T[2], T[3] i T[4]
          // W tablicy nie ma komórki T[5]!

Komórki tablicy zachowują się jak normalne zmienne i można z nimi robić w programie wszystko to, co ze zmiennymi. Indeksy komórek tablicy mogą być dowolnymi wyrażeniami, co pozwala je prosto wyliczać. Uruchom poniższy program:

// Tablice
//--------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int T[10]; // Tablica 10-komórkowa
    int i;

    // Definiujemy kolejne komórki

    for(i = 0; i < 10; i++)
        T[i] = (i + 1) * (i + 1);

    // Wypisujemy tablicę

    cout << "Zawartość komórek:" << endl
         << "------------------" << endl << endl;

    for(i = 0; i < 10; i++)
        cout <<"T[" << i << "] = "
             << setw(3) << T[i] << endl;

    cout << endl;

    return 0;
}

Zawartość komórek:
------------------

T[0] =   1
T[1] =   4
T[2] =   9
T[3] =  16
T[4] =  25
T[5] =  36
T[6] =  49
T[7] =  64
T[8] =  81
T[9] = 100

W programie zostaje utworzona tablica o nazwie T, która zawiera 10 komórek: T[0], T[1], T[2], ..., T[8], T[9].

int T[10];

Pierwsza pętla for tworzy indeksy przechodzące przez kolejne wartości 0, 1, 2, ..., 9. Wartości te są wykorzystywane do adresowania komórek tablicy oraz do wyznaczania kwadratów kolejnych liczb naturalnych 1, 2, 3, ..., 10, które zostają umieszczone w adresowanych komórkach:

for(i = 0; i < 10; i++)
    T[i] = (i + 1) * (i + 1);

Druga pętla for wyświetla zawartości komórek tablicy:

for(i = 0; i < 10; i++)
    cout <<"T[" << i << "] = "
         << setw(3) << T[i] << endl;

Do zapamiętania:

• Definiowanie tablicy.
• Dostęp do komórek.

Uruchom poniższy program:

// Tablice
//--------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int T[] = {11,7,83,99,-2,0,26,3,1,4}, i;

    // Wypisujemy tablicę

    cout << "Zawartość komórek:" << endl
         << "------------------" << endl << endl;

    for(i = 0; i < 10; i++)
        cout <<"T[" << i << "] = "
             << setw(3) << T[i] << endl;

    cout << endl;

    return 0;
}

Zawartość komórek:
------------------

T[0] =  11
T[1] =   7
T[2] =  83
T[3] =  99
T[4] =  -2
T[5] =   0
T[6] =  26
T[7] =   3
T[8] =   1
T[9] =   4

Zwróć uwagę na definicję tablicy.

int T[] = {11,7,83,99,-2,0,26,3,1,4}, i;

Definiujemy ją razem ze zmienną i. W jednej definicji może wystąpić wiele zmiennych, jeśli są tego samego typu:

double T[5], b[12], c[]={3.14,6.28,5.5}, x, y, z;

Jednak dla przejrzystości należy raczej unikać takich kombinacji. Nic nie kosztuje dopisane paru wierszy, a program stanie się bardziej czytelny.

Przy zadaniach maturalnych może się zdarzyć, iż musimy wprowadzić do tablicy ciąg danych, np. z pliku tekstowego. Ciąg ten będzie się składał z liczb, które mają trafić do kolejnych komórek tablicy. Umówmy się, iż pierwsza liczba nie będzie należała do danych, tylko będzie określać ich ilość, np:

15 7 4 12 19 86 32 1 9 5 65 73 92 101 44 3

Poszczególne liczby są rozdzielone spacjami, znakami tabulacji lub znakami końca wiersza (inne znaki są niedozwolone). Dane będziemy odczytywać poprzez okno konsoli. Poniższy program pokazuje odpowiednią procedurę odczytu. Po uruchomieniu programu skopiuj dane do schowka, po czym wróć do okna konsoli i wklej dane ze schowka:

// Tablice
//--------

#include <iostream>
#include <iomanip>

using namespace std;


int main()
{
    setlocale(LC_ALL,"");

    cout << "Wklej dane ze schowka" << endl << endl;

    int n;    // Ilość danych
    cin >> n; // Odczytujemy ilość danych

    int T[n]; // Tworzymy tablicę na dane
    int i;

    // Odczytujemy dane do tablicy
    for(i = 0; i < n; i++) cin >> T[i];

    // Wypisujemy tablicę

    cout << endl << endl
         << "Zawartość komórek:" << endl
         << "------------------" << endl << endl;

    for(i = 0; i < n; i++)
        cout <<"T[" << setw(2) << i << "] = "
             << setw(3) << T[i] << endl;

    cout << endl;

    return 0;
}

Wklej dane ze schowka

15 7 4 12 19 86 32 1 9 5 65 73 92 101 44 3


Zawartość komórek:
------------------

T[ 0] =   7
T[ 1] =   4
T[ 2] =  12
T[ 3] =  19
T[ 4] =  86
T[ 5] =  32
T[ 6] =   1
T[ 7] =   9
T[ 8] =   5
T[ 9] =  65
T[10] =  73
T[11] =  92
T[12] = 101
T[13] =  44
T[14] =   3

Przeanalizujmy początek programu.

Na samym początku tworzymy zmienną n na liczbę danych (czyli liczbę komórek tablicy), po czym odczytujemy do niej pierwszą liczbę z okna konsoli:

int n;    // Ilość danych
cin >> n; // Odczytujemy ilość danych

W drugim kroku tworzymy tablicę o n komórkach:

int T[n]; // Tworzymy tablicę na dane

Uwaga: Ten sposób definicji tablicy nie jest standardowy w C++ i działa tylko z kompilatorem GCC (Code::Blocks) posiadającym wbudowane rozszerzenia, standardowym sposobem jest utworzenie tablicy dynamicznej lub skorzystanie z biblioteki STL, ale o tym powiemy w dalszej części kursu. Jeśli w swoim kompilatorze nie możesz utworzyć tablicy o dynamicznym rozmiarze, to utwórz zwykłą o ilości komórek na pewno większej od n, np.int T[1000].

Gdy mamy przygotowaną tablicę, odczytujemy kolejne dane i umieszczamy je w komórkach tablicy:

for(i = 0; i < n; i++) cin >> T[i];

Zwróć uwagę, iż pętla for wykonuje się n razy, czyli tyle, ile jest danych i komórek w tablicy. Po odczytaniu danych do tablicy możemy je przetwarzać.

Do zapamiętania:

• Określanie zawartości tablicy w jej definicji.
• Odczyt danych do tablicy.

Wypełnianie tablicy

Operacja polega na wpisaniu wybranej wartości do każdej komórki tablicy.

Lista kroków
K01: Dla i = 0, 1, ..., n - 1:
     wykonuj T[i] ← a
K02: Zakończ

// Wypełnianie tablicy
//--------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int n;
    cout << "Liczba komórek w tablicy: ";
    cin >> n;
    int a;
    cout << "Wartość do ustawienia   : ";
    cin >> a;
    cout << endl;

    int T[n]; // Tworzymy tablicę

    // Ustawiamy komórki tablicy
    for(int i = 0; i < n; i++) T[i] = a;

    // Wypisujemy tablicę
    cout << "Zawartość komórek:" << endl
         << "------------------" << endl << endl;
    for(int i = 0; i < n; i++)
        cout <<"T[" << setw(2) << i << "] = "
             << setw(3) << T[i] << endl;
    
    cout << endl;

    return 0;
}

Liczba komórek w tablicy: 12
Wartość do ustawienia   : -54

Zawartość komórek:
------------------

T[ 0] = -54
T[ 1] = -54
T[ 2] = -54
T[ 3] = -54
T[ 4] = -54
T[ 5] = -54
T[ 6] = -54
T[ 7] = -54
T[ 8] = -54
T[ 9] = -54
T[10] = -54
T[11] = -54

Wstawianie elementu do tablicy

Operacja polega na dodaniu nowego elementu do tablicy na wybranej pozycji. Elementy obecne w tablicy powinny w niej pozostać, za wyjątkiem ostatniego, który zostaje utracony. Wygląda to następująco. Załóżmy, iż mamy tablicę 10-cio elementową T o następującej zawartości:

Na pozycji elementu T[3] chcemy wstawić nowy element o wartości 100. W tym celu musimy najpierw rozsunąć elementy tablicy tak, aby na pozycji T[3] powstało miejsce na nowy element. Rozsuwanie rozpoczynamy od przedostatniego elementu T[8], który przesuwamy w górę do T[9]:

Zawartość elementu T[9] zostaje zastąpiona zawartością T[8]. Poprzednia zawartość 99 zostaje utracona.

Cofamy się do elementu T[7] i przenosimy go do T[8]:

Operacje kontynuujemy, aż dojdziemy do elementu T[3]:

Elementy zostały przesunięte w górę tablicy i pozycja T[3] może być zapisana nową wartością. Wstawiamy tu wartość 100:

Dlaczego rozsuwanie rozpoczęliśmy od końca tablicy, a nie od elementu T[3]? Spójrz poniżej:

Wynik jest nieprawidłowy. Elementy tablicy od T[4] do T[9] zostały nadpisane poprzednią zawartością elementu T[3].

Przejdźmy do algorytmu.

Lista kroków:
K01: Dla i = n-2, n-3,...,p:
     wykonuj T[i + 1] ← T[i]
K02: T[i] ← x
K03: Zakończ

// Wstawianie elementu do tablicy
//-------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int T[] = {1,5,8,12,21,39,45,60,83,99};
    int n = 10, p = 12, x = 100;

    cout << "Wstawianie wartości " << x
         << " na pozycję " << p << endl << endl;

    cout << "Zawartość tablicy przed wstawieniem:" << endl;
    for(int i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(3) << T[i] << endl;

    if((p >= 0) && (p < n)) // Jeśli pozycja w tablicy
    {
        // Najpierw rozsuwamy elementy
        for(int i = n - 2; i >= p; i--)
            T[i + 1] = T[i];

        // Na zwolnioną pozycję wstawiamy x
        T[p] = x;
    }

    cout << "Zawartość tablicy po wstawieniu:" << endl;
    for(int i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(3) << T[i] << endl;

    cout << endl;

    return 0;
}

Wstawianie wartości 100 na pozycję 3

Zawartość tablicy przed wstawieniem:
T[0] =   1
T[1] =   5
T[2] =   8
T[3] =  12
T[4] =  21
T[5] =  39
T[6] =  45
T[7] =  60
T[8] =  83
T[9] =  99
Zawartość tablicy po wstawieniu:
T[0] =   1
T[1] =   5
T[2] =   8
T[3] = 100
T[4] =  12
T[5] =  21
T[6] =  39
T[7] =  45
T[8] =  60
T[9] =  83

Usuwanie elementu z tablicy

Jest to operacja odwrotna do wstawiania elementu do tablicy. Opiszemy ją na podobnym przykładzie, jak poprzednio. Mamy tablicę 10-cio elementową a o następującej zawartości:

Chcemy z niej usunąć element 12 leżący na pozycji T[3]. W tym celu przesuwamy w dół tablicy o jedną pozycję wszystkie kolejne komórki od pozycji T[4] do T[9]:

Zwróć uwagę, że ostatnia wartość tablicy 99 jest powtórzona dwa razy. Na ostatniej pozycji T[9] umieszczamy zero:

Lista kroków:
K01: Dla i = p, p + 1, ..., n - 2:
     wykonuj T[i] ← T[i + 1]
K02: T[n - 1] ← 0
K03: Zakończ

// Usuwanie elementu z tablicy
//----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int T[] = {1,5,8,12,21,39,45,60,83,99};
    int n = 10, p = 3;

    cout << "Usuwanie elementu z pozycji " << p << endl << endl;

    cout << "Zawartość tablicy przed usuwaniem:" << endl;
    for(int i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(2) << T[i] << endl;

    if((p >= 0) && (p < n))
    {
        // Najpierw przesuwamy elementy
        for(int i = p; i <= n - 2; i++)
            T[i] = T[i + 1];

        // Na koniec wstawiamy 0
        T[n - 1] = 0;
    }

    cout << "Zawartość tablicy po usunięciu:" << endl;
    for(int i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(2) << T[i] << endl;

    cout << endl;

    return 0;
}

Usuwanie elementu z pozycji 3

Zawartość tablicy przed usuwaniem:
T[0] =  1
T[1] =  5
T[2] =  8
T[3] = 12
T[4] = 21
T[5] = 39
T[6] = 45
T[7] = 60
T[8] = 83
T[9] = 99
Zawartość tablicy po usunięciu:
T[0] =  1
T[1] =  5
T[2] =  8
T[3] = 21
T[4] = 39
T[5] = 45
T[6] = 60
T[7] = 83
T[8] = 99
T[9] =  0

Odwrócenie kolejności elementów tablicy

Naszym zadaniem jest zmiana kolejności elementów w tablicy na przeciwną. Np:

Rozpoczynamy od ustawienia dwóch indeksów w tablicy: pierwszego i oraz ostatniego j:

Wymieniamy ze sobą zawartości komórek o indeksach i oraz j:

Indeks i zwiększamy o 1, a indeks j zmniejszamy o 1:

Dopóki i < j, operację powtarzamy:

Lista kroków:
K01: i ← 0
K02: j ← n - 1
K03: Dopóki i < j:
     wykonuj kroki K04...K06
K04:     T[ i ] ↔ T[ j ]
K05:      i ← i + 1
K06:      j ← j - 1
K07: Zakończ

// Odwrócenie kolejności elementów tablicy
//----------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int T[] = {1,5,8,12,21,39,45,60,83,99};
    int n = 10,i,j;

    cout << "Odwrócenie kolejności elementów tablicy"
         << endl << endl;

    cout << "Zawartość tablicy przed operacją:" << endl;
    for(i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(2) << T[i] << endl;

    i = 0;
    j = n - 1;
    while(i < j) swap(T[i++],T[j--]);

    cout << "Zawartość tablicy po operacji:" << endl;
    for(i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(2) << T[i] << endl;

    cout << endl;

    return 0;
}

Odwrócenie kolejności elementów tablicy

Zawartość tablicy przed operacją:
T[0] =  1
T[1] =  5
T[2] =  8
T[3] = 12
T[4] = 21
T[5] = 39
T[6] = 45
T[7] = 60
T[8] = 83
T[9] = 99
Zawartość tablicy po operacji:
T[0] = 99
T[1] = 83
T[2] = 60
T[3] = 45
T[4] = 39
T[5] = 21
T[6] = 12
T[7] =  8
T[8] =  5
T[9] =  1

Liczby Fibonacciego

Pamiętasz wyznaczanie kolejnych liczb Fibonacciego algorytmem rekurencyjnym? Algorytm miał bardzo niekorzystną klasę złożoności obliczeniowej O(2ⁿ) . Wyznaczenie 50 liczb Fibonacciego zajęło około 300 sekund (5 minut). Poniższy program wyznacza 50 kolejnych liczb Fibonacciego wykorzystując tablicę do przechowywania liczb już obliczonych. Przeanalizuj go dokładnie.

// Odwrócenie kolejności elementów tablicy
//----------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int T[] = {1,5,8,12,21,39,45,60,83,99};
    int n = 10,i,j;

    cout << "Odwrócenie kolejności elementów tablicy"
         << endl << endl;

    cout << "Zawartość tablicy przed operacją:" << endl;
    for(i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(2) << T[i] << endl;

    i = 0;
    j = n - 1;
    while(i < j) swap(T[i++],T[j--]);

    cout << "Zawartość tablicy po operacji:" << endl;
    for(i = 0; i < n; i++)
        cout << "T[" << i << "] = "
             << setw(2) << T[i] << endl;

    cout << endl;

    return 0;
}

Liczby Fibonacciego:

fib( 0) =          0
fib( 1) =          1
fib( 2) =          1
fib( 3) =          2
fib( 4) =          3
fib( 5) =          5
fib( 6) =          8
fib( 7) =         13
fib( 8) =         21
fib( 9) =         34
fib(10) =         55
fib(11) =         89
fib(12) =        144
fib(13) =        233
fib(14) =        377
fib(15) =        610
fib(16) =        987
fib(17) =       1597
fib(18) =       2584
fib(19) =       4181
fib(20) =       6765
fib(21) =      10946
fib(22) =      17711
fib(23) =      28657
fib(24) =      46368
fib(25) =      75025
fib(26) =     121393
fib(27) =     196418
fib(28) =     317811
fib(29) =     514229
fib(30) =     832040
fib(31) =    1346269
fib(32) =    2178309
fib(33) =    3524578
fib(34) =    5702887
fib(35) =    9227465
fib(36) =   14930352
fib(37) =   24157817
fib(38) =   39088169
fib(39) =   63245986
fib(40) =  102334155
fib(41) =  165580141
fib(42) =  267914296
fib(43) =  433494437
fib(44) =  701408733
fib(45) = 1134903170
fib(46) = 1836311903
fib(47) = 2971215073
fib(48) = 4807526976
fib(49) = 7778742049

Do zapamiętania:

• Wypełnianie tablicy
• Wstawianie do tablicy
• Usuwanie z tablicy
• Zmiana kolejności zawartości elementów tablicy

Tablicę dwuwymiarową (ang. two dimentional array) często nazywa się macierzą (ang. matrix). Możemy ją potraktować jak tablicę tablic, czyli tablicę, której każdy element jest tablicą niższego poziomu, czyli podtablicą (ang. subarray). Definicja tablicy dwuwymiarowej wygląda następująco:

Na przykład definicja:

double x[3][2];

utworzy tablicę dwuwymiarową liczb typu double o nazwie x, która będzie zawierała 3 podtablice, a każda z tych podtablic będzie posiadała dwie komórki. Dostęp do komórek w tablicy dwuwymiarowej wymaga dwóch indeksów. Pierwszy indeks wybiera podtablicę, drugi indeks wybiera komórkę w tej podtablicy. Nasza tablica posiada zatem następującą strukturę:

x[0][0]

x[0][1]

: podtablica 0

x[1][0]

x[1][1]

: podtablica 1

x[2][0]

x[2][1]

: podtablica 2

Tablicę dwuwymiarową możemy inicjować listą wartości. Lista ta będzie składała się z podlist dla każdej z podtablic. Poniższy program demonstruje ten sposób inicjalizacji:

// Tablica dwuwymiarowa
// Inicjalizacja #1
//---------------------

#include <iostream>

using namespace std;

int main()
{
    int i,j; // indeksy

    int T[][5] ={{1,2,3,4,5},
                 {6,7,8,9,8},
                 {7,6,5,4,3},
                 {2,1,0,1,2}};


    // Wyświetlamy zawartości kolejnych podtablic:
    
    for(i = 0; i < 4; i++)
    {
        for(j = 0; j < 5; j++) cout << T[i][j] << " ";
        cout << endl;
    }
    cout << endl << endl;

    return 0;
}

1 2 3 4 5
6 7 8 9 8
7 6 5 4 3
2 1 0 1 2

Zwróć uwagę, iż przy inicjalizacji tablicy listą można pominąć pierwszy wymiar, czyli liczbę podtablic. Komputer sam sobie określi ich ilość z listy.

Tablicę dwuwymiarową możemy również potraktować jako strukturę zbudowaną z wierszy i kolumn. Pierwszy wymiar określa numer wiersza, drugi wymiar określa numer kolumny:

int T[4][5]; // 4 wiersze, 5 kolumn:

kolumna 0

kolumna 1

kolumna 2

kolumna 3

kolumna 4

wiersz 0

T[0][0]

T[0][1]

T[0][2]

T[0][3]

T[0][4]

wiersz 1

T[1][0]

T[1][1]

T[1][2]

T[1][3]

T[1][4]

wiersz 2

T[2][0]

T[2][1]

T[2][2]

T[2][3]

T[2][4]

wiersz 3

T[3][0]

T[3][1]

T[3][2]

T[3][3]

T[3][4]

Poniższy program tworzy dwie tablice dwuwymiarowe o 8 wierszach i 8 kolumnach. Następnie w pierwszej wypełnia kolumny ich numerami, a w drugiej wypełnia wiersze ich numerami, po czym obie tablice odpowiednio wyświetla.

// Tablica dwuwymiarowa
// Wiersze i kolumny
//---------------------

#include <iostream>

using namespace std;

int main()
{
    int w,k; // indeksy wierszy i kolumn

    int a[8][8],b[8][8];

    // Kolumny w tablicy a, wiersze w b

    for(w = 0; w < 8; w++)
        for(k = 0; k < 8; k++)
        {
            a[w][k] = k;
            b[w][k] = w;
        }
    // Wyświetlamy:

    cout << "tablica a: kolumny" << endl << endl;
    for(w = 0; w < 8; w++)
    {
        for(k = 0; k < 8; k++)
            cout << a[w][k] << " ";
        cout << endl;
    }
    cout << endl;

    cout << "tablica b: wiersze" << endl << endl;
    for(w = 0; w < 8; w++)
    {
        for(k = 0; k < 8; k++)
            cout << b[w][k] << " ";
        cout << endl;
    }

    cout << endl << endl;

    return 0;
}

tablica a: kolumny

0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7

tablica b: wiersze

0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7

Do zapamiętania:

• Tworzenie tablicy dwuwymiarowej
• Inicjalizacja tablicy dwuwymiarowej
• Interpretacja tablicy dwuwymiarowej jako tablicy tablic jednowymiarowych
• Interpretacja tablicy dwuwymiarowej jako wierszy i kolumn