Kurs podstawy programowania UMCS, zdjęcie laptopa.

Podstawy programowania – Laboratorium 6

Tablice automatyczne: wiele wartości pod jedną nazwą

Tablica pozwala przechowywać uporządkowaną kolekcję elementów tego samego typu. Najważniejsze nie jest zapamiętanie nawiasów kwadratowych, lecz zrozumienie rozmiaru, zakresu indeksów, ciągłości pamięci i odpowiedzialności za każdą granicę.

Czego powinieneś nauczyć się na tych zajęciach?

  • traktować tablicę jako jeden obiekt zawierający elementy tego samego typu,
  • deklarować, inicjalizować, odczytywać i modyfikować elementy tablicy,
  • rozumieć zakres poprawnych indeksów 0…n-1,
  • wyznaczać rozmiar tablicy dostępnej w bieżącym zakresie,
  • przechodzić po tablicy bez wychodzenia poza jej granice,
  • stosować wyszukiwanie liniowe i modyfikację elementów w miejscu,
  • czytać indeksy tablicy dwuwymiarowej jako wiersz i kolumnę.

Najważniejsza zasada: tablica zna swój fizyczny rozmiar, ale operator [] nie sprawdza go za Ciebie. Każdy użyty indeks musi wynikać z algorytmu i należeć do poprawnego zakresu.


Tablica jako typ i obiekt w pamięci

Definicja int values[5]; tworzy jeden obiekt tablicowy zawierający pięć kolejnych elementów typu int. Elementy znajdują się w pamięci jeden za drugim, bez przerw pomiędzy nimi. Każdy ma własny indeks oraz można zmienić go niezależnie.

Indeks01234
Elementvalues[0]values[1]values[2]values[3]values[4]

Pierwszy indeks wynosi zero, dlatego ostatni indeks tablicy o pięciu elementach wynosi cztery. values[5] nie jest „szóstym poprawnym elementem” – odwołanie do niego wykracza poza tablicę i powoduje niezdefiniowane zachowanie. Program może pozornie działać, wypisać śmieci, uszkodzić inne dane albo zakończyć się błędem.

Automatyczny czas przechowywania: lokalna tablica utworzona wewnątrz bloku istnieje od wejścia do tego bloku do jego opuszczenia. Implementacje zwykle przechowują takie obiekty na stosie, ale język C definiuje przede wszystkim ich czas życia, a nie obowiązkowe miejsce w sprzętowej pamięci.

1. Prześledź zmiany elementów

Rdzeńpredict before runindeks

Bez uruchamiania programu zapisz zawartość całej tablicy po każdym przypisaniu. Następnie przewidź dokładny wynik. Zwróć uwagę, że prawa strona przypisania jest obliczana przed zmianą elementu po lewej stronie.

Program do analizy
#include <stdio.h>

int main(void) {
    int values[5] = {4, 7, 2, 7, 1};

    values[2] = values[0] + values[4];
    values[4] = values[1];

    for (size_t i = 0; i < 5; ++i) {
        printf("%d ", values[i]);
    }
    printf("\n");

    return 0;
}

Odpowiedź: po pierwszym przypisaniu tablica ma postać {4, 7, 5, 7, 1}, a po drugim {4, 7, 5, 7, 7}.


Definicja, inicjalizacja i rozmiar

ZapisZnaczenie
int a[5];pięć niezainicjalizowanych elementów automatycznych
int a[5] = {2, 4};pierwsze dwa elementy to 2 i 4, pozostałe są zerami
int a[5] = {0};wszystkie elementy są zerami
int a[] = {2, 4, 6};rozmiar zostaje wyznaczony jako trzy elementy

Odczyt niezainicjalizowanego elementu lokalnej tablicy jest błędem. Nie zakładaj, że pamięć „zaczyna się od zera”. Jeżeli wszystkie elementy mają otrzymać wartości z wejścia, pętla musi zapisać każdy z nich, zanim inna część programu go odczyta.

Dla rzeczywistej tablicy dostępnej w tym samym zakresie wyrażenie sizeof values zwraca liczbę bajtów zajmowanych przez cały obiekt, a sizeof values[0] – rozmiar jednego elementu. Ich iloraz daje liczbę elementów. W laboratorium 7 zobaczymy, dlaczego ten sposób nie działa wewnątrz funkcji otrzymującej tablicę jako parametr.

2. Wczytanie i opisanie pięciu elementów

Rdzeńsizeofsize_tpełna inicjalizacja

Utwórz pięcioelementową tablicę, wczytaj wszystkie wartości, a następnie wypisz każdą razem z indeksem. Typ size_t jest standardowym nieujemnym typem używanym dla rozmiarów i indeksów; w printf odpowiada mu format %zu.

Rozwiązanie
#include <stdio.h>

int main(void) {
    int values[5];
    size_t size = sizeof values / sizeof values[0];

    for (size_t i = 0; i < size; ++i) {
        scanf("%d", &values[i]);
    }

    for (size_t i = 0; i < size; ++i) {
        printf("values[%zu] = %d\n", i, values[i]);
    }

    return 0;
}

Dwie pętle mają celowo oddzielne role: pierwsza ustanawia zawartość tablicy, druga ją obserwuje. W większym programie taki podział ułatwia późniejsze przeniesienie operacji do osobnych funkcji.


Przechodzenie po tablicy

Najczęstszy schemat ma postać for (size_t i = 0; i < size; ++i). Przed każdą iteracją warunek gwarantuje, że i jest poprawnym indeksem. To właśnie <, a nie <=, odpowiada zakresowi od zera do size - 1.

W tablicy można przejść po danych wielokrotnie. To odróżnia ją od strumienia liczb z wcześniejszych laboratoriów: po wczytaniu nadal mamy wszystkie elementy i możemy wykonać kolejną analizę bez ponownego podawania danych. Ceną jest zajęta pamięć oraz konieczność pilnowania rozmiaru.

Algorytmy na tablicach

3. Suma, minimum i maksimum w jednym przejściu

Rdzeńakumulatorekstremajedno przejście

Dla gotowej tablicy policz sumę oraz znajdź najmniejszy i największy element. Przed kodem opisz znaczenie każdej zmiennej po przetworzeniu indeksów od 0 do i.

Rozwiązanie
#include <stdio.h>

int main(void) {
    int values[] = {7, -4, 12, 3, -1, 8};
    size_t size = sizeof values / sizeof values[0];

    long long sum = 0;
    int minimum = values[0];
    int maximum = values[0];

    for (size_t i = 0; i < size; ++i) {
        sum = sum + values[i];

        if (values[i] < minimum) {
            minimum = values[i];
        }
        if (values[i] > maximum) {
            maximum = values[i];
        }
    }

    printf("suma: %lld\n", sum);
    printf("minimum: %d\n", minimum);
    printf("maksimum: %d\n", maximum);
    return 0;
}

Minimum i maksimum rozpoczynają się od pierwszego prawdziwego elementu. Tutaj pętla ponownie uwzględnia indeks zero; jest to poprawne, choć porównanie pierwszego elementu z nim samym jest zbędne. Alternatywnie można rozpocząć od i = 1.

4. Pierwsze wystąpienie wartości

Rdzeńwyszukiwanie liniowewartość umowna

Wyszukaj pierwsze wystąpienie liczby w tablicy. Wartość size oznacza początkowo „jeszcze nie znaleziono”, ponieważ nie jest poprawnym indeksem. Warunek position == size zapobiega nadpisaniu pierwszej pozycji kolejnym wystąpieniem.

Rozwiązanie
#include <stdio.h>

int main(void) {
    int values[] = {8, 3, 11, 3, 5};
    size_t size = sizeof values / sizeof values[0];
    int target;
    scanf("%d", &target);

    size_t position = size;

    for (size_t i = 0; i < size; ++i) {
        if (values[i] == target && position == size) {
            position = i;
        }
    }

    if (position < size) {
        printf("pierwszy indeks: %zu\n", position);
    } else {
        printf("brak elementu\n");
    }

    return 0;
}
Pierwsze wystąpienie3 → 1
Początek8 → 0
Brak4 → komunikat

Modyfikacja tablicy w miejscu

Modyfikacja in place oznacza, że wynik zapisujemy w tej samej tablicy, bez tworzenia drugiej kolekcji. Trzeba wtedy pilnować, aby nie zniszczyć elementu, którego wartość będzie jeszcze potrzebna. Przy odwracaniu zamieniamy parami element pierwszy z ostatnim, drugi z przedostatnim i kończymy w połowie.

5. Odwrócenie kolejności elementów

Rdzeńmodyfikacja in placepary indeksów

Odwróć tablicę bez używania drugiej tablicy. Wyznacz indeks symetrycznego elementu jako size - 1 - left. Przetestuj osobno tablicę o parzystej i nieparzystej liczbie elementów.

Rozwiązanie
#include <stdio.h>

int main(void) {
    int values[] = {10, 20, 30, 40, 50, 60};
    size_t size = sizeof values / sizeof values[0];

    for (size_t left = 0; left < size / 2; left = left + 1) {
        size_t right = size - 1 - left;
        int temporary = values[left];
        values[left] = values[right];
        values[right] = temporary;
    }

    for (size_t i = 0; i < size; ++i) {
        printf("%d ", values[i]);
    }
    printf("\n");

    return 0;
}

Pętla wykonuje tylko size / 2 zamian. Środkowy element tablicy o nieparzystym rozmiarze pozostaje na swoim miejscu i nie wymaga specjalnej gałęzi.


Tablica dwuwymiarowa: wiersze i kolumny

Definicja int matrix[3][4]; tworzy trzy wiersze, z których każdy zawiera cztery liczby. Element wybieramy jako matrix[row][column]. W pamięci całe wiersze znajdują się kolejno po sobie, dlatego pętla po kolumnach jest naturalnie zagnieżdżona wewnątrz pętli po wierszach.

6. Wiersz o największej sumie

Rdzeńtablica 2Dzagnieżdżone pętle

Dla macierzy 3 × 4 znajdź indeks wiersza o największej sumie. Pierwszy wiersz służy do poprawnej inicjalizacji wyniku; pozostałe są z nim porównywane.

Rozwiązanie
#include <stdio.h>

int main(void) {
    int matrix[3][4] = {
        {2, 4, 1, 3},
        {7, 0, 5, 2},
        {1, 1, 8, 1}
    };

    size_t best_row = 0;
    int best_sum = 0;

    for (size_t column = 0; column < 4; column = column + 1) {
        best_sum = best_sum + matrix[0][column];
    }

    for (size_t row = 1; row < 3; row = row + 1) {
        int row_sum = 0;

        for (size_t column = 0; column < 4; column = column + 1) {
            row_sum = row_sum + matrix[row][column];
        }

        if (row_sum > best_sum) {
            best_sum = row_sum;
            best_row = row;
        }
    }

    printf("wiersz: %zu, suma: %d\n", best_row, best_sum);
    return 0;
}

Nie tworzymy tablicy sum, ponieważ wynik można aktualizować na bieżąco. Tablica wejściowa jest potrzebna, ale pomocnicze dane ograniczamy do indeksu najlepszego wiersza i jego sumy.

Audyt kodu AI: granica, której kompilator nie zna

Znajdź odwołanie poza tablicą

AI-auditundefined behavioroff-by-one

Kod miał zsumować pięć elementów. Kompilator może nie zatrzymać programu, a wynik może zmieniać się między uruchomieniami. Wskaż pierwszą iterację, w której algorytm łamie kontrakt tablicy.

#include <stdio.h>

int main(void) {
    int values[5] = {2, 4, 6, 8, 10};
    int sum = 0;

    for (size_t i = 0; i <= 5; ++i) {
        sum = sum + values[i];
    }

    printf("%d\n", sum);
    return 0;
}

Diagnoza: poprawne indeksy to 0…4. Dla i == 5 warunek i <= 5 nadal jest prawdziwy i następuje odczyt values[5]. Warunek powinien mieć postać i < 5.

Podsumowanie

  • tablica zawiera ustaloną liczbę elementów jednego typu, ułożonych kolejno w pamięci,
  • dla rozmiaru n poprawne indeksy należą do zakresu 0…n-1,
  • lokalne elementy bez inicjalizacji nie mają określonych wartości,
  • sizeof array / sizeof array[0] działa tylko tam, gdzie nazwa oznacza rzeczywistą tablicę,
  • tablica pozwala wielokrotnie wracać do tych samych danych,
  • tablica dwuwymiarowa wymaga osobnego indeksu wiersza i kolumny.

Co trzeba rozumieć, nawet używając AI: rzeczywisty rozmiar obiektu, poprawny zakres indeksów, stan inicjalizacji każdego elementu i to, czy algorytm modyfikuje dane, których będzie jeszcze potrzebował.

Dalsza część pracy odbywa się na Platformie do ćwiczeń. Zadania platformowe wykorzystują inne operacje: łączenie, rotację, podział, analizę powtórzeń i macierze.

Pytania kontrolne

  1. Dlaczego ostatnim indeksem tablicy o rozmiarze n jest n - 1?
  2. Co może się wydarzyć po odczycie elementu poza tablicą?
  3. Czym różni się rozmiar tablicy w bajtach od liczby jej elementów?
  4. Dlaczego minimum i maksimum inicjalizujemy elementem danych?
  5. Kiedy potrzebna jest druga tablica, a kiedy można zmodyfikować pierwszą w miejscu?
  6. Jak obliczyć liczbę odwiedzin elementów macierzy o r wierszach i c kolumnach?

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Wymagane pola są oznaczone *