Kurs podstawy programowania UMCS, zdjęcie laptopa.

Podstawy programowania – Laboratorium 9

Wejściówka – wskaźniki

Napisz funkcję w języku C++, która przyjmuje następujące argumenty: wskaźnik na początek tablicy liczb całkowitych – begin, wskaźnik na koniec tablicy liczb całkowitych – end oraz referencję na zmienną typu logicznego. Funkcja powinna sprawdzić, czy w tablicy znajduje się wartość 5 i za pomocą ostatniego argumentu zwrócić odpowiedź. Napisz program w języku C++, który sprawdzi działanie tej funkcji.

Rozwiązanie:
#include <iostream>
using namespace std;

void f(int *begin, int *end, bool &result) {
    result = false;
    for(int *it = begin; it < end; ++it)
        if(*it == 5) {
            result = true;
            return;
        }
}

int main() {
    bool c;
    int arr[7] = {1, 4, 3, 8, 2, 7, 9};
    f(arr, arr + 7, c);
    cout << c << endl;
    return 0;
}

Zadanie 1

Napisz funkcję w języku C++, która przyjmuje jako argumenty wskaźniki do dwóch zmiennych typu int. Funkcja powinna zwrócić wskaźnik do mniejszej wartości z liczb wskazywanych przez argumenty, jeśli argumenty mają taką samą wartość funkcja powinna zwracać wskaźnik na pierwszy argument.

Rozwiązanie:
#include <iostream>

int *f(int *a, int *b) {
	return *a > *b ? b : a;
}

int main() {
    int a = 7, b = 6;
    int *result = f(&a, &b);
    std::cout << result << " " << &a << " " << &b << " " << *result << std::endl;
    return 0;
}

Zadanie 2 – dynamiczna alokacja pamięci

Napisz program w języku C++, który wczyta od użytkownika liczbę całkowitą n, a następnie dynamicznie zaalokuje pamięć dla n elementowej tablicy liczb całkowitych. Program powinien wypełnić tablicę dowolnymi wartościami, a następnie wyświetlić wszystkie elementy tej tablicy.

Rozwiązanie:
#include <iostream>

int main() {
	int n, *arr;
	std::cin >> n;
	arr = new int[n];
	
	for(int i = 0; i < n; ++i)
		arr[i] = i * i;

	for(int i = 0; i < n; ++i)
		std::cout << arr[i] << " ";

	std::cout << std::endl;
		
	delete[] arr;
	return 0;
}
Omówienie:

Zmienne programu przechowywane są na stosie (ang. stack). Zmienne te powstają, gdy program wchodzi do bloku, w którym zmienne są definiowane a zwalniane w momencie, kiedy program opuszcza ten blok. W sytuacji, gdy definiujemy w ten sposób tablicę, to ich rozmiar musi być znany w momencie kompilacji (tablice automatyczne) – żeby kompilator wygenerował kod rezerwujący odpowiednią ilość pamięci.

Drugi rodzaj rezerwacji pamięci to alokacja na stercie (ang. heap). Sterta to obszar pamięci wspólny dla całego programu. Przechowywane są w nim zmienne, których czas życia nie jest związany z poszczególnymi blokami. Czas życia tych zmiennych zależy od programisty, to on odpowiada za rezerwacje i zwalnianie pamięci dla tych zmiennych – dynamiczna alokacja pamięci. Tym samym można to zrobić w dowolnym momencie działania programu. Należy pamiętać, że rezerwowanie i zwalnianie pamięci na stercie zajmuje więcej czasu niż analogiczne działania na stosie. Dodatkowo, zmienna zajmuje na stercie więcej miejsca niż na stosie – sterta utrzymuje specjalną strukturę, w której trzymane są wolne partie.

Tak więc zaleca się używać dynamiczną alokację tam, gdzie jest potrzebna – dla danych, których rozmiaru nie jesteśmy w stanie przewidzieć na etapie kompilacji lub ich czas życia ma być niezwiązana z blokiem, w którym zostały zaalokowane.


Operatory służące do dynamicznego zarządzania pamięcią to new i delete.

new jest operatorem dynamicznej alokacji pamięci. Zwraca adres lokalizacji pamięci, której możemy od teraz używać do przechowywania wartości jakiegoś typu, a także rezerwują odpowiednią ilość pamięci na tego typu dane.

int *ptr = new int;
*ptr = 123;

Zrób „nowy int” i zapisz adres. Tak utworzona zmienna będzie istnieć tak długo, aż zostanie ręcznie zwolniona lub program się zakończy. Do zwolnienia pamięci służy operator delete.

delete ptr;

Po wykonaniu tej instrukcji, wartość wskaźnika ptr pozostaje bez zmiany, ale nie można już robić niczego z pamięcią pod tym adresem – nie jest już „nasza„. Należy pamiętać, że błędna niezerowa wartość wskaźnika jest nieodróżnialna od poprawnej, więc dobrą praktyką jest wyzerowanie wskaźnika po usunięciu pamięci:

delete ptr;
ptr = nullptr;

Każda zaalokowana pamięć powinna zostać zwolniona. Jeśli program w jakimś przypadku nie zwalnia pamięci, mamy wówczas do czynienia z wyciekiem pamięci (memory leak). Niezwalnianie pamięci może doprowadzić do wyczerpania zasobów komputera i problemów.

#include <iostream>

int main() {
    int *ptr = new int;
    *ptr = 123;

    std::cout << *ptr << std::endl;

    delete ptr;
    ptr = nullptr;

    std::cout << *ptr << std::endl;

    return 0;
}

Do dynamicznej alokacji pamięci dla tablicy używamy operatora new[], zaś do usunięcia tablicy należy użyć delete[].

int *arr = new int[100];
arr[42] = 123;

delete[] arr;

Do delete/delete[] można bezpiecznie podać pusty wskaźnik (nullptr, NULL) i nie powoduje to zwolnienia żadnej pamięci new int i new int[1] nie są równoważne. Alokacja jednej zmiennej nie jest alokacją jednoelementowej tablicy, więc delete[] nie jest „uniwersalniejszą” wersją delete. delete i delete[] nie mogą być stosowane zamiennie.


Warto dodać, że w języky C++ oprócz operatorów new i delete, możemy także korzystać z funkcji malloc i free, które pochodzą z języka C i również służą do dynamicznej alokacji i zwalniania pamięci. Warto jednak zwrócić uwagę na różnice między tymi mechanizmami mimo, że w nowoczesnym C++ preferuje się używanie new i delete lub inteligentnych wskaźników (std::unique_ptr, std::shared_ptr) z biblioteki standardowej, ponieważ lepiej integrują się z obiektowym charakterem C++ (stąd też bardzo rzadko będziemy używać malloc i free w ramach tego kursu).

Funkcja malloc (ang. memory allocation) alokuje blok pamięci o określonym rozmiarze w bajtach i zwraca wskaźnik do tej pamięci. Jeśli alokacja nie powiedzie się, malloc zwraca nullptr. malloc nie wywołuje konstruktora obiektów (w przypadku alokacji obiektów), a także nie inicjalizuje alokowanej pamięci. Pamięć może więc zawierać losowe dane.
Składnia:
void* malloc(size_t size);
Przykład użycia:
int *arr = (int*)malloc(10 * sizeof(int)); // Alokacja pamięci na tablicę 10 elementów typu int

Funkcja free służy do zwalniania pamięci zaalokowanej za pomocą malloc (lub innych podobnych funkcji z języka C jak calloc czy realloc).
void free(void* ptr);
Przykład użycia:
free(arr); // Zwolnienie pamięci

Ciekawostka: Kluczowe różnice między malloc/free a new/delete:
Inicjalizacja:
new inicjalizuje pamięć, np. dla typów wbudowanych, takich jak int, ustawia wartości początkowe.
malloc alokuje tylko pamięć, nie inicjalizuje jej. Pamięć może zawierać niezdefiniowane dane.

Obsługa obiektów:
new wywołuje konstruktor obiektu, jeśli alokujemy pamięć dla obiektów.
malloc nie wywołuje konstruktora ani nie tworzy obiektów, tylko przydziela blok pamięci.

Zwalnianie pamięci:
delete zwalnia pamięć i wywołuje destruktor, jeśli został zaalokowany obiekt.
free jedynie zwalnia pamięć, ale nie wywołuje destruktora obiektu.

Obsługa typów:
new jest typowy dla C++ i nie wymaga rzutowania wskaźników.
malloc jest funkcją z języka C i zwraca wskaźnik typu void*, co wymaga rzutowania do odpowiedniego typu.

Zadanie 3

Napisz program w języku C++, który wczyta od użytkownika nieujemną liczbę całkowitą n, a następnie dynamicznie zaalokuje pamięć dla n elementowej tablicy liczb rzeczywistych. Program powinien wypełnić tablicę zerami, a następnie wyświetlić wszystkie elementy tej tablicy. Na koniec program powinien zmienić rozmiar tablicy na 10 i wypełnić ją jedynkami.

Rozwiązanie:
#include <cstdio>

typedef unsigned int uint;

void print_arr(float *arr, uint n) {
    for(uint i = 0; i < n; ++i)
        printf("%f ", arr[i]);
    printf("\n");
}

void fill_arr(float *arr, uint n, float value) {
    for(uint i = 0; i < n; ++i) 
        arr[i] = value;
}

int main() {
    uint n;
    float *arr;

    scanf("%u", &n);
    arr = new float[n];
    printf("%p\n", arr);
    fill_arr(arr, n, 0.f);
    print_arr(arr, n);
    delete[] arr;
    
    arr = new float[10];
    printf("%p\n", arr);
    fill_arr(arr, 10, 1.f);
    print_arr(arr, 10);
    delete[] arr;
    
    return 0;
}
Omówienie:

Nowa tablica pojawi się pod innym adresem, jeśli wolny blok pamięci będzie zbyt mały.

Zadanie 4

Napisz funkcję w języku C++, która przyjmie jako argumenty tablicę wartości zmiennoprzecinkowych, jej rozmiar, dwie wartości zmiennoprzecinkowe – minimum i maksimum, oraz wskaźnik na uprzednio zaalokowaną wartość całkowitą. Funkcja powinna zaalokować i zwrócić tablicę, w której znajdą się liczby z lewostronnie domkniętego przedziału od minimum do maksimum. Pod wartością wskaźnika z argumentu należy zapisać rozmiar nowoutworzonej tablicy.

Rozwiązanie:
#include <iostream>

float *insert(float arr[], int n, float min, float max, int *value) {
    float *result = nullptr;
    *value = 0;

    for(int i = 0; i < n; ++i)
        if(arr[i] >= min && arr[i] < max)
            (*value)++;

    if(*value) {
        result = new float[*value]; //Uwaga! dla value == 0 tablica jest niezdefiniowana

        for(int i = 0, j = 0; i < n; ++i)
            if(arr[i] >= min && arr[i] < max)
                result[j++] = arr[i];
    }

    return result;
}

int main() {
    int n = 10;
    float arr[] = {0.5f, 0.7f, 1.25f, 6.25f, 9.3f, 1.13f, 2.23f, 3.2f, 6.23f, 1.78f};
    int* value = new int;
    float *result = insert(arr, n, 1.13f, 6.3f, value);
    
    if(result)
        for(int i = 0; i < *value; ++i)
            std::cout << result[i] << " ";
    else 
        std::cout << "Brak danych\n";
        
    
    delete value;
    delete[] result;
    return 0;
}
Omówienie:

Powinno się unikać zwracania pamięci zaalokowanej w funkcji, ponieważ rozmywa się odpowiedzialność za ten obszar pamięci. Jest to błąd architektury programu, złego zaprojektowania rozwiązania problemu, lepszym rozwiązaniem tego zadania jest kod przedstawiony poniżej:

#include <iostream>

int get_size(float arr[], int n, float min, float max) {
    int result = 0;
    for(int i = 0; i < n; ++i)
            if(arr[i] >= min && arr[i] < max)
                result++;
    return result;
}

void insert(float arr[], int n, float min, float max, float *result) {
    for(int i = 0, j = 0; i < n; ++i)
        if(arr[i] >= min && arr[i] < max)
            result[j++] = arr[i];
}

void print_arr(float arr[], int n) {
    for(int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

int main() {
    int n = 10;
    float *result = nullptr;
    float min = 1.13f, max = 6.3f;
    float arr[] = {0.5f, 0.7f, 1.25f, 6.25f, 9.3f, 1.13f, 2.23f, 3.2f, 6.23f, 1.78f};

    int size = get_size(arr, n, min, max);
    if(size) {
        result = new float[size];
        insert(arr, n, min, max, result);
        print_arr(result, size);
    } else std::cout << "Brak danych.\n";
    delete[] result;
    return 0;
}

Zadanie 5

Napisz program w języku C++, który wczytuje od użytkownika liczbę całkowitą n, następnie dynamicznie alokuje pamięć dla n-elementowej tablicy liczb zmiennoprzecinkowych. Napisz funkcję f1, która uzupełni tą tablicę dowolnymi wartościami oraz funkcję f2, która przyjmuje rozmiar tablicy oraz tablicę liczb zmiennoprzecinkowych. Funkcja f2 ma wyświetlić na standardowym wyjściu kolejne wyrazy ciągu od 1 do n zdefiniowanego wzorem:
F0 = 0
Fn = (-1)n * arr[n-1]+Fn-1, n > 0

Rozwiązanie:
#include <iostream>
#include <cmath>

void f1(float *arr, int n) {
    for(int i = 0; i < n; ++i)
        arr[i] = i + 1;
}

void f2(float *arr, int n) {
    float a = 0.f;
    for(int i = 1; i <= n; ++i) {
        a += pow(-1, i) * arr[i - 1];
        std::cout << a << std::endl;
    }
}

int main() {
    int n;
    std::cin >> n;
    float *arr = new float[n];

    f1(arr, n);
    f2(arr, n);

    delete[] arr;
    return 0;
}

Zadanie 6

Napisz funkcję w języku C++, która przyjmuje w argumentach: tablicę liczb zmiennoprzecinkowych arr1, rozmiar tablicy arr1, tablicę liczb całkowitych arr2 oraz rozmiar tablicy arr2. Wartości elementów w tablicy arr2 to indeksy dla tablicy arr1. Niech funkcja wyświetli wszystkie elementy tablicy arr1 o indeksach, których wartości znajdują się w tablicy arr2. Jeżeli w arr1 nie ma odpowiedniego indeksu to wyświetla dla niego wartość NAN. Napisz program w języku C++, który dynamicznie zaalokuje pamięć dla obu tablic, a następnie arr1 wypełni dowolnymi wartościami, zaś wartości tablicy arr2 wczyta od użytkownika.

Rozwiązanie:
#include <iostream>
#include <cmath>

void f1(float *arr, int n) {
    for(int i = 0; i < n; i++)
        arr[i] = i + 0.1f;
}

void f(float *values, int n_v, int *ids, int n_i) {
    for(int i = 0; i < n_i; ++i)
        std::cout << (ids[i] >= 0 && ids[i] < n_v ? values[ids[i]] : NAN) << std::endl;
}

int main() {
    int n, m;
    std::cin >> n >> m;
    float *values = new float[n];
    int *ids = new int[m];

    f1(values,n);
    for(int i = 0; i < m; ++i)
        std::cin >> ids[i];

    f(values, n, ids, m);

    delete[] values;
    delete[] ids;
    return 0;
}

Zadanie 7 – wskaźnik na void

Napisz uniwersalną funkcję swap w języku C++ oraz program, który sprawdzi jej działanie dla różnych typów zmiennych.

Rozwiązanie:
#include <iostream>

void my_memcpy(void *dst, void *src, size_t n) {
    char *csrc = (char *)src;
    char *cdst = (char *)dst;

    for(size_t i = 0; i < n; ++i)
        cdst[i] = csrc[i];
}

void my_swap(void *a, void *b, size_t size) {
    char *tmp = new char[size];

    my_memcpy(tmp, b, size);
    my_memcpy(b, a, size);
    my_memcpy(a, tmp, size);

    delete[] tmp;
}

int main() {
    int a = 1, b = 2;
    std::cout << a << " " << b << std::endl;
    my_swap(&a, &b, sizeof(a));
    std::cout << a << " " << b << std::endl;
    return 0;
}
Omówienie:

W sytuacji, gdy nie znany jest typ na jaki wskazuje wskaźnik, stosujemy typ void*. Sam void nie znaczy nic, natomiast void* oznacza wskaźnik na obiekt w pamięci niewiadomego typu. Można, więc uznać, że jest to wskaźnik specjalny, który wskazuje na obiekt dowolnego typu, stąd inna nazwa – wskaźnik generyczny. Wskaźnik na void pozwala na generyczne podejście do programowania w języku C/C++. Wskaźniki tego typu są szczególnie przydatne w sytuacjach, gdy potrzebujemy wskaźnika na dane o nieznanym w czasie kompilacji typie. Są one często wykorzystywane w niskopoziomowych operacjach na pamięci lub w przypadku bardziej ogólnych, generycznych implementacji funkcji, na przykład w bibliotekach dynamicznego zarządzania pamięcią (jak malloc i free).

Dereferencja to proces pobierania danych z lokalizacji pamięci wskazywanej przez wskaźnik. Konwertuje surowy blok bajtów na znaczące dane (dane są znaczące, jeśli są powiązane z typem).

Podczas dereferencji wskaźnika typu void, kompilator języka C++ nie ma pojęcia o typie wartości wskazywanym przez ten wskaźnik. Dlatego odwołanie do wskaźnika void jest zabronione w C++. Jednakże wskaźnik stanie się bezużyteczny, jeśli nie można użyć na nim dereferencji. W związku z tym aby dostać się do wartości wskazywanej przez wskaźnik typu void należy rzutować go do właściwego typu.

int num = 10;
void * v_ptr = &num;  // wskaźnik typu void

int value = *((int *) v_ptr); // dereferencja
#include<cstdio> 
int main() { 
    int a = 10; 
    void *ptr = &a; 
    printf("%d", *ptr); //Nie zadziała!
    return 0; 
}
#include<cstdio> 
int main() { 
    int a = 10; 
    void *ptr = &a; 
    printf("%d", *(int *)ptr); 
    return 0; 
} 

Oczywiście arytmetyka wskaźników typu void jest zabroniona, wynika to z braku typu, więc nie wiemy o ile bajtów się przesuwać (to samo próba usunięcia, bo kompilator nie wie ile bajtów usunąć). Jednakże niektóre kompilatory pozwalają na arytmetykę wskaźników typu void traktując je jako wskaźniki typu char. Aby wykonać jakąkolwiek arytmetykę na wskaźnikach typu void należy wcześniej je w odpowiedni sposób rzutować.

int arr[] = {10, 20, 30, 40, 50};
void * v_ptr = &arr;  // wskaźnik typu void na arr

v_ptr = ((int *) v_ptr + 1);  // dodanie 1 do rzutowanego wskaźnika typu void
#include<cstdio> 
int main() { 
    int a[2] = {1, 2}; 
    void *ptr = &a; 
    ptr = ptr + sizeof(int); //Dostaniemy warning
    printf("%d", *(int *)ptr); 
    return 0; 
} 

Zadanie 8

Napisz program w języku C++, który stworzy dwuwymiarową tablicę (NxM) w postaci tablicy wskaźników do tablicy wartości liczb całkowitych. Napisz funkcję f1, która wypełni tą tablicę dowolnymi wartościami, a następnie funkcję f2, która wyświetli wartości z tej tablicy.

Rozwiązanie:
#include <iostream>

void f1(int **arr, int n, int m) {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            arr[i][j] = i * j;
}

void f2(int **arr, int n, int m) {
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j)
            std::cout << arr[i][j] << " ";
        std::cout << "\n";
    }
}

int main() {
    int n, m;

    std::cin >> n >> m;
    int **arr = new int*[n];
    for(int i = 0; i < n; ++i)
        arr[i] = new int[m];

    f1(arr,n,m);
    f2(arr,n,m);

    for(int i = 0; i < n; ++i)
        delete[] arr[i];
    delete[] arr;
    return 0;
}

Zadanie 9

Napisz program w języku C++, który wczytuje od użytkownika trzy liczby całkowite n, m, o, a następnie dynamicznie alokuje pamięć dla n-elementowej, m-elementowej i o-elementowej tablicy liczb całkowitych. W kolejnym kroku program powinien uzupełnić tablice losowymi wartościami z przedziału <0;5> i je posortować. Na koniec z tak posortowanych tablic algorytm powinien wypisać elementy powtarzające się we wszystkich tablicach.

Rozwiązanie:
#include <iostream>
#include <cstdlib>
#include <ctime>

const int MIN = 0;
const int MAX = 5;

void fill_arr(int *arr, int n) {
    for(int i = 0; i < n; ++i) 
        arr[i] = MIN + rand() / (RAND_MAX / (MAX - MIN + 1));
}

void print_arr(int *arr, int n) {
    for(int i = 0; i < n; ++i) 
        std::cout << arr[i] << " "; 
    std::cout << std::endl;
}

void bubble_sort(int *arr, int n) {
    for(int i = 0; i < n - 1; ++i)
        for(int j = 0; j < n - i - 1; ++j)
            if(arr[j] > arr[j + 1])
                std::swap(arr[j], arr[j + 1]);
}

void f(int *arr1, int n, int *arr2, int m, int *arr3, int o) {
    int i = 0, j = 0, k = 0;
    while(i < n && j < m && k < o) {
        if(arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            std::cout << arr1[i] << " ";
            i++; j++; k++;
        } else if(arr1[i] < arr2[j]) {
            i++;
        } else if(arr2[j] < arr3[k]) {
            j++;
        } else {
            k++;
        }
    }
}

int main() {
    srand(time(0));
    int n, m, o;
    std::cin >> n >> m >> o;
    int *arr1 = new int[n], *arr2 = new int[m], *arr3 = new int[o];

    fill_arr(arr1, n), fill_arr(arr2, m), fill_arr(arr3, o);
    bubble_sort(arr1, n), bubble_sort(arr2, m), bubble_sort(arr3, o);
    print_arr(arr1, n), print_arr(arr2, m), print_arr(arr3, o);

    f(arr1, n, arr2, m, arr3, o);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    return 0;
}

Zadanie 10

Napisz program w języku C++, który wczytuje od użytkownika dwie liczby całkowite n, m, a następnie dynamicznie alokuje pamięć dla n-elementowej tablicy liczb całkowitych. W kolejnym kroku program powinien uzupełnić tablicę losowymi wartościami z przedziału <-50;50> i je posortować. Na koniec program powinien znaleźć wszystkie pary liczb całkowitych, których suma jest równa liczbie m, wyświetlić je i podać ich ilość.

Rozwiązanie:
#include <iostream>
#include <cstdlib>
#include <ctime>

const int MIN = -50;
const int MAX = 50;

void fill_arr(int *arr, int n) {
    for(int i = 0; i < n; ++i) 
        arr[i] = MIN + rand() / (RAND_MAX / (MAX - MIN + 1));
}

void print_arr(int *arr, int n) {
    for(int i = 0; i < n; ++i) 
        std::cout << arr[i] << " "; 
    std::cout << std::endl;
}

void bubble_sort(int *arr, int n) {
    for(int i = 0; i < n - 1; ++i)
        for(int j = 0; j < n - i - 1; ++j)
            if(arr[j] > arr[j + 1])
                std::swap(arr[j], arr[j + 1]);
}

void f(int *arr, int n, int m) {
    int count = 0;
    for(int i = 0; i < n - 1; ++i)
        for(int j = i + 1; j < n; ++j)
            if(arr[i] + arr[j] == m) {
                ++count;
                std::cout << arr[i] << "," << arr[j] << std::endl;
            }
    std::cout << "Count: " << count << std::endl;
}

int main() {
    srand(time(0));
    int n, m;
    std::cin >> n >> m;

    int *arr = new int[n];

    fill_arr(arr, n);
    bubble_sort(arr, n);
    print_arr(arr, n);
    f(arr, n, m);

    return 0;
}

Zadanie 11

Napisz program w języku C++, który wczytuje od użytkownika trzy liczby całkowite n, m, o, a następnie dynamicznie alokuje pamięć dla tablicy wskaźników na n-elementową, m-elementową i o-elementową tablicę liczb zmiennoprzecinkowych. W kolejnym kroku program powinien uzupełnić tablice losowymi wartościami z przedziału <2.5f;5.4f>. Program powinien wyświetlić ten wiersz tablicy wskaźników, którego suma elementów jest największa.

Rozwiązanie:
//Version 1.0
#include <iostream>
#include <cstdlib>
#include <ctime>

const float MIN = 2.5f;
const float MAX = 5.4f;

void fill_arr(float *arr, int n) {
    for(int i = 0; i < n; ++i) 
        arr[i] = MIN + rand() / (RAND_MAX / (MAX - MIN + 1));
}

float sum(float *arr, int n) {
    float result = 0;
    for(int i = 0; i < n; ++i) 
        result += arr[i];
    return result;
}

void print_arr(float *arr, int n) {
    for(int i = 0; i < n; ++i) 
        std::cout << arr[i] << " "; 
    std::cout << "\n";
}

int main() {
    srand(time(0));
    float max = 0.f;
    int idx, sizes[3];
    std::cin >> sizes[0] >> sizes[1] >> sizes[2];

    float **array = new float*[3];
    for (int i = 0; i < 3; ++i) {
        array[i] = new float[sizes[i]];
        fill_arr(array[i], sizes[i]);
        print_arr(array[i], sizes[i]);
    }

    for (int i = 0; i < 3; ++i) {
        float result = sum(array[i], sizes[i]);
        if(max < result) 
            max = result, idx = i;
    }
    
    std::cout << "Result:\n";
    print_arr(array[idx], sizes[idx]);

    return 0;
}
//Version 2.0
#include <iostream>
#include <cstdlib>
#include <ctime>

const float MIN = 2.5f;
const float MAX = 5.4f;
const int N = 3;

void fill_arr(float *arr, int n) {
    for(int i = 0; i < n; ++i) 
        arr[i] = rand() / (1.f * RAND_MAX) * (MAX - MIN) + MIN;
}

float sum(float *arr, int n) {
    float result = 0;
    for(int i = 0; i < n; ++i) 
        result += arr[i];
    return result;
}

void print_arr(float *arr, int n) {
    for(int i = 0; i < n; ++i) 
        std::cout << arr[i] << " "; 
    std::cout << std::endl;
}

int main() {
    srand(time(0));
    float max = 0.f;
    int idx = -1, sizes[N];
    for(int i = 0; i < N; ++i)
        std::cin >> sizes[i];

    float **arr = new float*[N];
    for(int i = 0; i < N; ++i) {
        arr[i] = new float[sizes[i]];
        fill_arr(arr[i], sizes[i]);
        print_arr(arr[i], sizes[i]);
    }

    for(int i = 0; i < N; ++i) {
        float result = sum(arr[i], sizes[i]);
        if(result > max) 
            max = result, idx = i;
    }
    std::cout << "Result: " << max << '\n';
    print_arr(arr[idx], sizes[idx]);

    for(int i = 0; i < N; ++i)
        delete[] arr[i];
    delete[] arr;

    return 0;
}

Zadanie 12

Napisz funkcję w języku C++, która przyjmie jako parametry wskaźniki na pierwszy i ostatni element tablicy. Bez użycia operatora subskryptowego [], a jedynie korzystając z arytmetyki wskaźników, wyświetl zawartość tablicy.

Rozwiązanie:
#include <iostream>

void print_arr(int *begin, int *end) {
    for(;begin <= end; ++begin) std::cout << *begin << " ";
    std::cout << std::endl;
}

int main() {
    const int n = 5;
    int arr[n] = {1, 2, 3, 4, 5};
    print_arr(arr, arr + 4);
    return 0;
}

Zadanie 13

Rozbuduj poprzednie rozwiązanie tak, aby program obliczył sumę wszystkich liczb nieparzystych w stworzonej tablicy, a następnie wyświetli wynik na standardowym wyjściu. Na koniec program powinien stworzyć nową tablicę, do której przepisze wartości nieparzyste i wyświetlić tą tablicę.

Rozwiązanie:
#include <iostream>

void print_arr(int *begin, int *end) {
    for(;begin < end; ++begin) std::cout << *begin << " ";
    std::cout << std::endl;
}

int odd_sum(int *begin, int *end) {
    int result = 0;
    for(;begin < end; ++begin)
        if(*begin % 2)
            result += *begin;
    return result;
}

int count_odd_ones(int *src_b, int *src_e) {
	int result = 0;
	for(;src_b < src_e; ++src_b)
            if(*src_b % 2)
		++result;
	return result;
}

void rewrite_odd_ones(int *src_b, int *src_e, int *dst_b) {
    for(;src_b < src_e; ++src_b)
        if(*src_b % 2)
            *(dst_b++) = *src_b;
}

int main() {
    const int n = 5;
    int *odd_arr = nullptr, odd_n = 0;
    int arr[n] = {1, 2, 3, 4, 5};
    std::cout << odd_sum(arr, arr + n) << std::endl;
    odd_n = count_odd_ones(arr, arr + n);
    if(odd_n) {
        odd_arr = new int[odd_n];
        rewrite_odd_ones(arr, arr + n, odd_arr);
        print_arr(odd_arr, odd_arr + odd_n);
        delete[] odd_arr;
        odd_arr = nullptr;
    }
    return 0;
}

Zadanie 14

Rozmiar pamięci zaalokowanej za pomocą funkcji malloc można zmienić funkcją realloc. Dla pamięci zaalokowanej operatorem new nie ma odpowiednika funkcji realloc. Napisz funkcję w języku C++, która spełni takie zadanie dla tablicy typu int. Funkcja powinna przyjąć jako parametry: wskaźnik na dynamicznie zaalokowaną tablicę oraz dwie liczby całkowite s i n określające stary i nowy rozmiar tablicy. Funkcja powinna dynamicznie utworzyć nową tablicę. Jeżeli s > n, do nowej tablicy należy przepisać n początkowych komórek starej tablicy. Jeżeli n > s, należy przepisać wszystkie komórki, a w pozostałych komórkach nowej tablicy pozostawić przypadkowe wartości. Funkcja powinna skasować starą tablicę oraz zwrócić wskaźnik na nową tablicę.

Rozwiązanie:
#include <iostream>

void resize_array(int *&ptr, int s, int n) {
    int *new_ptr = new int[n]();
    for(int i = 0; i < std::min(s, n); ++i)
        new_ptr[i] = ptr[i];
    delete [] ptr;
    ptr = new_ptr;
}

void print_arr(int *b, int *e) {
    for(;b < e; ++b) std::cout << *b << " ";
    std::cout << std::endl;
}

void print_arr_address(int *arr) {
    std::cout << static_cast<void*>(arr) << std::endl;
}

int main() {
    const int n = 5, k = 10;
    int *arr = new int[n]{1, 2, 3, 4, 5};
    print_arr_address(arr); 
    resize_array(arr, n, k);
    print_arr_address(arr);
    print_arr(arr, arr + k);
    delete [] arr;
    arr = nullptr;
    return 0;
}

Zadanie 15

Napisz program w języku C++, który w nieskończonej pętli dynamicznie alokuj 10000-elementową tablicę liczb całkowitych bez jej zwalniania. W dowolnym programie do badania aktywności systemu (np. menedżerze zadań) obserwuj zwiększające się zapotrzebowanie programu na pamięć operacyjną będącej skutkiem wycieku pamięci. Przerwij działanie programu przed zawieszeniem systemu.

Rozwiązanie:
#include <iostream>

int main() {
    const int n = 10000;
    int *ptr = nullptr;
    while(true) ptr = new int[n];
    return 0;
}

Zadanie 16

Niektóre implementacje kompilatorów C++ przechowują wielkość dynamicznie zaalokowanej tablicy w postaci wartości typu long tuż przed tą tablicą. Napisz program w języku C++, który zaalokuje dynamicznie dwie tablice zmiennoprzecinkowe o wielkości m i n. Sprawdź jaka jest wartość komórki pamięci leżąca o jeden element typu long przed każdą z tych tablic. Sprawdź jaka jest różnica adresów obu tablic. Czy możesz na tej podstawie wysnuć jakieś wnioski. (Uwaga: wynik zadania może być zależny od kompilatora).

Rozwiązanie:
#include <iostream>

int main() {
    const int n = 10, m = 20;
    int *arr_0 = new int[n], *arr_1 = new int[m];
    std::cout << *(reinterpret_cast<long*>(arr_0) - 1) << " " << *(reinterpret_cast<long*>(arr_1) - 1) << std::endl;
    //std::cout << *((long *)arr_0 - 1) << " " << *((long *)arr_1 - 1) << std::endl;
    std::cout << static_cast<void*>(arr_0) << " " << static_cast<void*>(arr_1) << std::endl;
    std::cout << arr_1 - arr_0 << std::endl;
    return 0;
}

Przygotuj się na kolejne laboratorium!

W celu przygotowania się na kolejne zajęcia, spróbuj wykonać poniższe zadania samodzielnie.

Zadanie 1

Napisz program w języku C++, który zaalokuje dynamicznie tablicę wskaźników na liczby całkowite o rozmiarze n. Program do każdej komórki tej tablicy powinien przypisać wskaźnik do dynamicznie zaalokowanej tablicy liczb całkowitych o rozmiarze m. Następnie program powinien wypełnić tablicę danymi indeksując ją tak, jakby była dwuwymiarową tablicą liczb całkowitych. Na koniec należy zwrócić uwagę na odpowiednie zwalnianie pamięci zajmowanej przez te tablice.

Zadanie 2

W analogiczny sposób jak w poprzednim zadaniu utwórz tablicę reprezentującą macierz górnotrójkątną. Liczba n powinna odpowiadać liczbie wierszy, a w przypadku pierwszego wiersza, także kolumn. Każdy kolejny wiersz powinien mieć o jeden element mniej niż poprzedni. Napisz dwie funkcje w języku C++, które przyjmą jako parametr wskaźnik na tę tablicę oraz rozmiar n. Jedna z funkcji powinna zapisać w tablicy niepowtarzającą się część tabliczki mnożenia. Druga funkcja powinna wyświetlić tabliczkę mnożenia z tablicy, tworząc jednak pełny kwadrat. Do indeksowania tablic używaj operacji dereferencji i arytmetyki wskaźników. Pamiętaj o zwolnieniu pamięci zajmowanej przez tablice.

Zadanie 3

Napisz funkcję w języku C++, która przyjmie tablicę napisów (wskaźników na znaki), z których część ma wartość nullptr. Jeżeli taka wartość się pojawi, funkcja powinna:
(1) dynamicznie utworzyć napis,
(2) przepisać tam napis z poprzedniego wiersza pomijając co drugi znak,
(3) przypisać powstały napis do komórki tablicy wskaźników.
Rozmiar utworzonego napisu powinien być optymalny. Zakładamy, że pierwsza komórka tablicy nie zawiera nullptr.

Zadanie 4

Napisz program w języku C++, który wyświetli parametry wiersza poleceń, z którymi został uruchomiony.

Zadanie 5

Zapoznaj się z funkcją strtol z biblioteki standardowej. Uruchom i przeanalizuj przykład z dokumentacji.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *