Cuprins

Laborator 01: Introducere

1. Reguli pentru laborator

Mai multe detalii pot fi găsite pe pagina Reguli de notare.

Reguli esenţiale pentru promovarea laboratorului


2. Desfășurarea laboratorului

Laboratorul de Structuri de Date și Algoritmi are drept scop aprofundarea conceptelor prezentate la curs. Un laborator va prezenta un anumit set de concepte și va conține următoarele activități:

Pentru o desfășurare cât mai bună a laboratorului și pentru o înțelegere cât mai bună a conceptelor vă recomandăm să parcurgeți conținutul laboratorului de acasă.

În cadrul acestui laborator vom lucra pe platforma Linux, mai precis vom lucra într-o mașină virtuală în care este instalat Lubuntu. Lubuntu este o distribuție de Linux care are la bază Ubuntu dar față de aceasta este mai lightweight.

2.1. Mașina virtuală SDA-AB în laborator

Pe stațiile de lucru din laborator a fost instalat VMware Player și adăugată mașina virtuală cu numele SDA-AB. Porniți mașina virtuală.

Credențialele sunt următoarele:

Utilizatorul student are drepturi de scriere doar în directorul /home/student. La repornirea mașinii virtuale conținutul acestui director este șters automat.

2.2. Mașina virtuală pentru acasă

Pentru a putea lucra de acasă la rezolvarea temelor, în cazul în care nu doriți să aveți instalată o distribuție de Linux, puteți găsi mașina virtuală de la laborator de aici Descărcați fișierul SDA-AB_VM.zip și dezarhivați-l. Fișierul are dimensiunea de 2.3GB (5.4GB dezarhivat).

Pentru a putea deschide mașina virtuală avem nevoie de VMware Workstation Player. Aceste este gratuit și poate fi descărcat de aici. Alegeți versiunea corespunzătoare sistemului de operare folosit.

După dezarhivarea mașinii virtuale și instalarea VMware Player, deschideți VMware Player → File → Open a Virtual Machine → Mergeți in directorul unde ați salvat mașina virtuală, SDA-AB, și selectați fișierul SDA-AB.vmx după care porniți mașina.

În cazul în care vă apare mesajul This virtual machine may have been moved or copied selectați I copied it.
Mașina virtuală pentru acasă păstrează conținutul directorului /home/student, iar utilizatorul student cu parola student are drepturi de administrare. Acest lucru nu este valabil pentru mașina virtuală de pe stațiile de lucru din laborator.

2.3. GNU Toolchain

În mașina virtulă este deja instalat toolchain-ul GNU. Acesta este o suită de tool-uri necesare dezvoltării programelor folosind C/C++ și conține:

2.3.1. Utilizare GCC

Pentru exemplificare vom folosi un program simplu care tipărește la ieșirea standard (stdout) un șir de caractere.

hello.c
#include <stdio.h>
 
int main()
{
   printf("SDA - Hello, World!\n");
 
   return 0;
}

GCC folosește pentru compilarea de programare C/C++ comanda gcc, respectiv comanda g++.

student@sda-ab-vm:~/Documents$ ls
hello.c
student@sda-ab-vm:~/Documents$ gcc hello.c
student@sda-ab-vm:~/Documents$ ls
a.out  hello.c
student@sda-ab-vm:~/Documents$ ./a.out 
SDA - Hello, World!

Prin urmare, comanda gcc hello.c a fost folosită pentru compilarea fișierului sursă hello.c. Rezultatul a fost obținerea fișierului executabil a.out (nume implicit utilizat de gcc). Dacă se dorește obținerea unui executabil cu un alt nume se poate folosi opțiunea -o.

student@sda-ab-vm:~/Documents$ gcc hello.c -o hello
student@sda-ab-vm:~/Documents$ ls
hello  hello.c
student@sda-ab-vm:~/Documents$ ./hello 
SDA - Hello, World!

Observăm că de data aceasta fișierul executabil rezultat se numește hello.

În mod similar se poate folosi g++ pentru compilarea unui program sursă C++.

2.3.2. Fișiere header și include guards

De cele mai multe ori nu vom lucra cu un singur fișier sursă ci vom încerca să modularizăm codul, spărgându-l în mai multe fișiere sursă, fiecare implementând o anumită funcționalitate.

Fișierele header .h nu implementează funcții ci conține doar definiții de funcții. Implementarea efectivă a acestora se realizează în fișierul asociat .c pentru C, sau .cpp pentru C++.

Să considerăm următorul scenariu: dorim să realizăm un modul care implementează funcțiile de adunare și inmulțire.

Creăm fișierul header cu numele my_math.h.

my_math.h
#ifndef MY_MATH_H
#define MY_MATH_H
 
int sum(int a, int b);
int multiply(int a, int b);
 
#endif

Prin folosirea #ifndef MY_MATH_H#endif ne asigurăm că acest fișier header nu este inclus de mai multe ori în același fișier sursă. Cu alte cuvinte, în cazul în care simbolul MY_MATH_H este deja definit de la prima includere, a doua operație de includere nu va avea niciun efect. Această tehnică se numește Include guard și folosește directivele de preprocesoare #ifndef, #define, #endif.

Apoi, creăm fișierul sursa cu numele my_math.c.

my_math.c
#include "my_math.h"
 
int sum(int a, int b)
{
   return a + b;
}
 
int multiply(int a, int b)
{
   return a * b;
}

Creăm și un fișier cu numele main.c în care vom utiliza funcțiile implementate de modulul nostru.

main.c
#include <stdio.h>
#include "my_math.h"
 
int main()
{
   int a = 10;
   int b = 20;
 
   printf("a + b = %d\n", sum(a, b));
   printf("a * b = %d\n", multiply(a, b));
 
   return 0;
}

Observăm modul în care am inclus header-ul my_math.h față de header-ul stdio.h. Atunci când ne dorim să includem un header din biblioteca standard folosim #include < ... .h>, iar atunci când dorim să includem un header creat de noi folosim #include ".... .h>".

Programul nostru are acum mai multe fișiere sursă .c. Compilarea din mai multe astfel de fișiere se face prin specificarea tuturor fișierelor sursă .c ca argumente utilitarului gcc.

student@sda-ab-vm:~/Documents$ ls
main.c  my_math.c  my_math.h
student@sda-ab-vm:~/Documents$ gcc main.c my_math.c -o main
student@sda-ab-vm:~/Documents$ ls
main  main.c  my_math.c  my_math.h
student@sda-ab-vm:~/Documents$ ./main 
a + b = 30
a * b = 200
Fișierele header .h nu trebuie date ca argumente utilitarului gcc. În etapa de compilare conținutul unui fișier .h este copiat în interiorul fișierului sursă care îl include.

2.3.2. GNU Make

Make este un utilitar din GNU Toolchain care permite automatizarea și eficientizarea sarcinilor. În mod particular este folosit pentru automatizarea compilării programelor. În cazul în care avem un proiect care are un număr foarte mare de fișiere sursă, compilarea întregului proiect de la zero poate dura foarte mult. Prin folosirea utilitarului make putem automatiza compilarea fiecărui fișier separat .c într-un fișier obiect (binar) .o, apoi unirea tuturor fișierelor obiect într-un singur fișier executabil. La o modificare se va recompila doar fișierul sursă modificat, rezultând un nou fișier obiect .o. Astfel, procesul de compilare este mult mai rapid.

Utilitarul make folosește un fișier de configurare denumit Makefile. Un astfel de fișier conține reguli și comenzi de automatizare.

Exemplu de utilizare

Makefile
all:
    gcc hello.c -o hello
clean:
    rm -f hello
student@sda-ab-vm:~/Documents$ ls
hello.c  Makefile
student@sda-ab-vm:~/Documents$ make
gcc hello.c -o hello
student@sda-ab-vm:~/Documents$ ls
hello  hello.c  Makefile
student@sda-ab-vm:~/Documents$ make clean
rm -f hello
student@sda-ab-vm:~/Documents$ ls
hello.c  Makefile
student@sda-ab-vm:~/Documents$ make all
gcc hello.c -o hello
student@sda-ab-vm:~/Documents$ ls
hello  hello.c  Makefile

Exemplul prezentat mai sus conține două reguli: all și clean. La rularea comenzii make se execută prima regulă din Makefile (în cazul de față all, nu contează în mod special denumirea). Comanda executată este gcc hello.c -o hello. Se poate preciza explicit ce regulă să se execute prin transmiterea ca argument comenzii make. (comanda make clean pentru a șterge executabilul hello și comanda make all pentru a obține din nou acel executabil).

Sintaxa unei reguli

Sintaxa unei reguli dintr-un fișier Makefile:

Un exemplu recomandat pentru un fișier Makefile este:

Makefile
all: hello
 
hello: hello.o
        gcc hello.o -o hello
 
hello.o: hello.c
        gcc -c hello.c
 
clean:
        rm -f *.o *~ hello

Observăm prezeța regulii all care va fi executată implicit.

La regula cu target-ul hello.o se observă folosirea opțiunii -c a utilitarului gcc. Aceasta opțiune se folosește pentru a obține doar fișierul obiect din codul sursă. Se oprește procesul de compilare inainte de obținerea executabilului. La final se continua compilarea cu unirea tuturor fișierelor obiect .o într-un fișier executabil.

Folosirea variabilelor

Un fișier Makefile permite folosirea de variabile. Astfel, un exemplu uzual de fișier Makefile este:

Makefile
CC = gcc
CFLAGS = -Wall -g
 
all: hello
 
hello: hello.o
        $(CC) $^ -o $@
 
hello.o: hello.c
        $(CC) $(CFLAGS) -c $<
 
clean:
        rm -f *.o *~ hello

În exemplul de mai sus au fost definite variabilele CC și CFLAGS. Variabia CC reprezintă compilatorul folosit, iar variabila CFLAGS reprezintă opțiunile de compilare utilizate; în cazul de față sunt afișarea tuturor warning-urilor (-Wall) cu suport de depanare (-g).

Variabilele predefinte sunt:

4. GDB

GDB (GNU Debugger) este unealta standard pentru debugging (depanare) din GNU. Este portabil şi poate fi folosit, printre altele, pentru a detecta instrucţiunea ce determina blocarea unui program la rulare (precum şi semnalul asociat erorii).

Exemplu de lansare:

gcc -Wall -g my_file.c -o my_file.exe
gdb my_file.exe

Câteva comenzi utile în timpul depanării:
list - arată conţinutul unui fişier (câteva rânduri, în jurul unui punct numit)
run - porneşte executia
n (sau next) - trece la instrucţiunea următoare (fără a intra în apeluri de funcţii)
s (sau step) - intră în apel de funcţie pentru a inspecta execuţia
b (sau break sau breakpoint) - setează un breakpoint ce va forţa oprirea execuţiei în punctul respectiv
continue - continuă execuţia până la următorul breakpoint
fin (sau finish) - iese din funcţia curentă

list şi breakpoint au nevoie de un parametru care să indice o instrucţiune („punctul“ dorit).

Exemple de identificare a instrucţiunilor (la fel pentru list) - funcţie, rândul din fişier, adresa din memorie (eventual cu explicitarea fişierului):

breakpoint my_function
breakpoint 13
breakpoint *0x401377

breakpoint my_file:10
breakpoint my_file:my_function

5. Exerciții

Exercițiul 1 - Hello world

Realizați un program un C/C++ care afișează mesajul Hello, World la ieșirea standard.

Exercițiul 2 - Makefile

Realizați un fișier Makefile pentru programul de la exercițiul 1 astfel încat:

Exercițiul 3 - Makefile cu surse multiple


6. Referințe