Zajęcia 4 (2025-03-17)

Zadania

Dla zadania algorithm.h zdefiniowano pakiet testów: test_algorithm.c. Możesz go wykorzystać by zweryfikować tworzone przez siebie implementacje.

algorithm.h, algorithm.c: rozszerz bibliotekę algorithm (z poprzednich zajęć) o:
1. funkcję int* da_index(int **array, int *size, int index);, która:
  1. dla wywołania int *a = NULL, n = 0; da_index(&a, &n, k); zwróci wskaźnik do elementu o indeksie k wewnątrz nowo stworzonej tablicy dynamicznej, a zmienne a i n będą wskazywały odpowiednio początek tablicy i rozmiar
  2. dla kolejnych wywołań da_index(&a, &n, k) zwróci wskaźnik do wcześniej istniejącego elementu jeśli k < n; w przeciwnym wypadku (k >= n) powiększy rozmiar tablicy (wykorzystując funkcję realloc) i odpowiednio zmodyfikuje zmienne a i n
  3. wykorzystuje w swojej implementacji funkcję realloc
  4. nowo zaalokowane fragmenty tablicy są zaincjalizowane wartością 0
  5. (opcjonalnie) wykorzystuje optymalne rozmiary pamięci w przypadku konieczności realokacji
text.c: przygotuj program, który przyjmuje podkomendę, a następnie ciąg znaków. W zależności od podkomendy:
1. bytes: wyznacza długość tekstu w bajtach (wykorzystując strlen)
2. length: wyznacza długość tekstu w znakach UTF-8 (wykorzystując algorytm opisany poniżej)
3. words: liczy wyrazy (wykorzystując strpbrk, strspn)
4. tokenize: dzieli tekst na tokeny (słowa rozdzielone spacją lub znakiem interpunkcyjnym (wykorzystując strtok)

Przykładowe wywołania text.c:

$ ./text bytes "Kraków"
7
$ ./text length "Kraków"
6
$ ./text words "Kraków to miasto w Polsce"
5
$ ./text tokenize "Kraków to miasto w Polsce"
Kraków
to
miasto
w
Polsce
$ ./text tokenize "Moje ulubione liczby to 10,20,30"
Moje
ulubione
liczby
to
10
20
30

Upewnij się, że alokujesz odpowiedni rozmiar tablicy! Alokacja 3 intów to malloc(3 * sizeof(int)), a nie malloc(3)

Alokacja pamięci

malloc(rozmiar) - alokuje rozmiar charów (bajtów) i zwraca wskaźnik na zaalokowaną pamięć (lub NULL)
free(wskaźnik) - dealokuje dynamicznie zaalokowaną pamięć
realloc(wskaźnik, nowy_rozmiar) - próbuje rozszerzyć pamięć do nowy_rozmiar - jeśli nie uda się zrobić tego w miejscu to alokuje nową pamięć o rozmiarze nowy_rozmiar, kopiuje zawartość starej do nowej, dealokuje starą i zwraca wskaźnik na nową
calloc(liczba, rozmiar) - alokuje pamięć dla tablicy liczba elementowej, w której każdy element ma rozmiar rozmiar

Należy manualnie określać rozmiar pamięci! Jeśli potrzebujemy 1 zmienną liczbową typu int, to alokujemy malloc(sizeof(int))!

Przykład:

alokacja 30 elementowej tablicy liczb: int *xs = malloc(sizeof(int) * 30); assert(xs != NULL);
realokacja do 20: int* xs2 = realloc(xs, sizeof(int) * 20); assert(xs2 != NULL);
zwolnienie pamięci: free(xs2);

Brak dealokacji pamięci niekoniecznie jest błędem - system operacyjny zwolni całą pamięć zajętą przez program w przypadku zakończenia procesu. Niektóre rodzaje programów wykorzystują ten mechanizm w celu ułatwienia implementacji. Utrudnia to jednak analizę poprawności programu narzędziami zewnętrznymi.

Łańcuchy znaków (ang. strings)

Literały łańcuchów znaków w języku C są wskaźnikami na pierwszy znak łańcucha. Zakończone są zawsze znakiem '\0', oznaczającym koniec łańcucha. Jest to dzisiaj forma używana wyłącznie przez język C - większość popularnych języków programowania reprezentuje łańcuchy znaków jako parę wskaźnik + długość.

Literały łańcuchów znaków zazwyczaj są zaalokowane w pamięci globalnej programu przez kompilator - są dostępne wtedy przez cały czas życia programu. Można jednak wybrać lokalizację łańcucha przez przypisanie do deklaracji tablicy:

#include <stdio.h>

void test()
{
	char local[] = "goodbye";
	printf("test global: %p\n", "hello, world");
	printf("test local:  %p\n", local);
}

int main()
{
	char local[] = "goodbye";
	printf("main global: %p\n", "hello, world");
	printf("main local:  %p\n", local);

	test();

	return 0;
}

To, że dwa literały współdzielą tą samą lokalizację jest optymalizacją wprowadzoną przez kompilator! Algorytm: String intering

Trzecim miejscem przechowywania stringów są tworzone w ramach potrzeb tablice dynamiczne. Wykorzystują ten mechanizm m.in. wbudowane funkcje operujące na ciągach znaków w języku C:

#include <stdio.h>
#include <string.h>

int main()
{
	char *foo = strdup("foo");
	printf("%s\n", foo); // wypisuje foofoo
	free(foo);
	return 0;
}

Sekwencje ucieczki (ang. escape sequences)

Unicode

Standard określający liczbową wartość dla znaków z alfabetów świata. Jest rozszerzeniem standardu ASCII.

UTF-8

Uproszczone sprawdzanie długości tekstu UTF-8

Wczytaj bajt (uint8_t)
1. Zwiększ licznik o 1
2. Jeśli bajt <= 127 jest to znak ASCII zajmujący 1 bajt. Znak = bajt. Przejdź do kroku 1
3. Jeśli bajt <= 223 jest to znak Unicode zajmujący 2 bajty. Wczytaj kolejny bajt, sprawdź czy jest mniejszy od 191 i przejdź do kroku 1
4. Jeśli bajt <= 239 jest to znak Unicode zajmujący 3 bajty. Wczytaj 2 kolejne bajty, sprawdź czy oba są mniejsze od 191 i przejdź do kroku 1
5. Wczytaj 3 kolejne bajty, sprawdź czy każdy z nich jest mniejszy od 191 i przejdź do kroku 1

Licznik = długość tekstu

Opis dokładny

Konwencja: 10xxxxxxx oznacza, że dwa bity początkowe mają wartość 10, a kolejne mają wartość dowolną.

Wczytaj bajt (uint8_t) i spróbuj przypasować go do jednego z wzorców pierwszego bajtu. Na podstawie wybranego wzorca wczytaj kolejne n kontynuacji, które odpowiada wspólnemu wzorcowi kontynuacji 10xxxxxxx.

Wzorzec pierwszego bajtu	Liczba kontynuacji
0xxxxxxx	0
110xxxxx	1
1110xxxx	2
11110xxx	3

Znaki x oznaczają bity wartości znaku - zapisz je w jeden ciąg bitów by odczytać zapisany znak.

Argumenty programu w C

Aby uzyskać dostęp do argumentów programu należy zdefiniować argumenty funkcji main. Zwyczajowe nazwy to argc odpowiadające liczbie argumentów oraz argv będące tablicą łańcuchów znaków.

Program wypisujący przekazane argumenty:

#include <stdio.h>

int main(int argc, char **argv)
{
	for (int i = 0; i < argc; ++i) {
		printf("argv[%d] = %s\n", i, argv[i]);
	}

	return 0;
}

Obsługa plików

FILE *fopen(char const* filename, char const* mode); - funkcja pozwalająca na otworzenie pliku. Zwraca NULL w przypadku błędu otwarcia pliku.
int fclose(FILE *f); - funkcja zamykająca plik
fprintf - odpowiednik printf, przyjmujący jako pierwszy argument dostęp do pliku, potem jak printf
fscanf - odpowiednik scanf, przyjmujący jako pierwszy argument dostęp do pliku, potem jak scanf
fwrite - funkcja pozwalająca na zapis do pliku
fread - funkcja pozwalająca na odczyt z pliku

Należy pamiętać o manalnym zamknięciu!