Tema 1.

Subprograme
Fişa de documentare 1.1. Subprograme şi tipuri de subprograme
Subprogramele sunt părţi ale unui program, identificabile prin nume, care se pot activa la cerere prin intermediul
acestor nume.
În construirea unei aplicaţii folosirea subprogramelor oferă următoarele avantaje:
Permite economisirea de memorie şi de timp alocat
Permite lucrul în echipă la rezolvarea unor sarcini complexe pentru aplicaţiile mari
Detectarea şi corectarea erorilor se face cu uşurinţă
Depanarea şi actualizarea aplicaţiei se fac mai uşor
Permite descompunerea unei probleme de mari dimensiuni
Elaborarea algoritmilor devine mai uşoară deoarece problema este descompusă
Permite reutilizarea cu uşurinţă a programelor
Creşte portabilitatea programelor
O parte din subprogram se contruieşte ca subprogram dacă un algoritm cuprinde în mai multe locuri aceeaşi
secvenţă de operaţii executabilă pentru aceleaşi date sau pentru date diferite. În loc ca subprogramul să cuprindă în
acelaşi loc, acelaşi grup de instrucţiuni, concepând grupul de intrucţiuni ca subprogram, el va apărea în program o
singură dată şi se va activa de mai multe ori. Partea respectivă de program rezolvă o subproblemă din cele în care se
descompune problema complexă.
De exemplu, considerăm următoarea secvenţă de program care memorează în variabila max valoarea maximă dintre
valorile variabilelor întregi a, b, c:

max=a;
if (max<b)
max=b;
if (max<c)
max=c;
cout << "max= "<<max;
Cele două instrucţiuni condiţionale realizează, de fapt, acelaşi lucru: determină valoarea maximă dintre valorile
memorate în două variabile. Procesul de calcul este acelaşi, diferă doar valorile concrete ale variabilelor pentru care
acest proces se execută.
Deoarece determinarea maximului dintre două valori poate fi modelată matematic ca o funcţie şi descrierea
subprogramului are o structură asemănătoare cu cea a funcţiei:

int Maxim (int p, int q)

{
if (p>q)
return p;
else
return q;
}

atunci pentru exemplul considerat, secţiunea de program care calculează maximul dintre trei valori, poate fi rescrisă
astfel:
max = Maxim (a,b);
max = Maxim (max,c);

Clasificarea subprogramelor:
 Subprograme standard (subprograme de sistem) – utilizarea lor presupune includerea fişierului ce conţine
prototipul dorit şi apelarea subprogramului
 Subprograme definite de utilizator – sunt descrise de progamator pentru rezolvarea unor cerinţe specifice.
Utilizarea lor presupune precizarea prototipului, definirea şi apelul.
 Subprograme apelate ca instrucţiuni procedurale – returnează sau nu o valoare prin intermediul parametrilor.
Apelul se face prin nume şi parametri
 Subprograme apelate ca operanzi – returnează un rezultat chiar prin numele său şi eventual alte rezultate prin
parametri. Apelul se face în interiorul unei expresii.

Sarcina de lucru: Căutaţi şi modificaţi conform enunţurilor, erorile apărute în definiţiile date.
Fiecare grupă trebuie să se documenteze în legătură cu avantajele folosirii subprogramelor. Pentru acest lucru aveţi la
dispoziţie 10 minute. După aceea rearanjaţi cuvântul/cuvintele incorecte pentru fiecare definiţie în parte, astfel încât
la final să regăsiţi definiţiile din fişa de documentare:
1. Permite economisirea de memorie şi de portabilitate a programelor
2. Permite lucrul în echipă la rezolvarea unor sarcini complexe pentru aplicaţiile mari
3. Detectarea şi actualizarea erorilor se face cu uşurinţă
4. Depanarea şi corectarea aplicaţiei se fac mai uşor
5. Permite descompunerea algoritmilor unei probleme de mari dimensiuni
6. Elaborarea aplicaţiilor mari devine mai uşoară deoarece problema este descompusă
7. Permite reutilizarea cu uşurinţă a programelor
8. Creşte timpul alocat

Sarcina de lucru: Căutaţi, identificaţi şi precizaţi diferenţele dintre tipurile de subprograme

Pornind de la clasificarea subprogramelor, precizaţi tipurile de subprograme şi diferenţele dintre acestea.
Evaluare: Câte 1 p pentru fiecare tip de subprogram. 3 p – pentru fiecare diferenţă găsită.
Fişa de documentare 1.2. - Structura subprogramelor şi transmiterea parametrilor
Un subprogram (funcţie) are o definiţie şi atâtea apeluri câte sunt necesare. Definiţia unui subprogram reprezintă
de fapt descrierea unui proces de calcul cu ajutorul variabilelor virtuale (parametri formali), iar apelul unui
subprogram înseamnă execuţia procesului de calcul pentru cazuri concrete (cu ajutorul parametrilor reali, (efectivi,
actuali) ).
Parametri formali apar în antetul subprogramului şi sunt utilizaţi de subprogram pentru descrierea abstractă a unui
proces de calcul .
Parametri actuali apar în instrucţiunea de apelare a unui subprogram şi sunt folosiţi la execuţia unui proces de calcul
pentru valori concrete.
Parametrii formali nu sunt variabile. O variabilă este caracterizată de nume, tip, şi adresă. Legarea unui parametru
formal la o adresă se realizează în timpul execuţiei instrucţiunii de apelare a subprogramului.
Definiţia unei funcţii are forma generală:
Tip_returnat Reprezintă tipul rezultatului calculat şi returnat de funcţie şi poate fi: int,
tip_returnat nume_funcţie (lista parametrilor formali)
char, char*, long, float, void, etc.
{ instrucţiune;// corpul funcţiei
În cazul } rezultatului este diferit de void, corpul funcţiei
în care tipul
{ instrucţiune; // corpul
trebuiefuncţiei
să conţină} cel puţin o instrucţiune return. Instrucţiunea return va
specifica
{ instrucţiune; // corpul valoarea} calculată şi returnată de funcţie care trebuie să fie de
funcţiei
acelaşi tip ca şi tip_returnat.
Reprezintă numele dat funcţiei de către cel ce o defineşte, pentru a o
Nume_funcţie
putea apela.
Reprezintă o listă de declaraţii de variabile separate prin virgulă. Această
Lista_parametrilor_formali listă poate să fie şi vidă.

Este o instrucţiune vidă sau o instrucţiune simplă sau o instrucţiune

Instrucţiune
compusă.

Construirea subprogramelor se face prin :

Antet – conţine date despre : tipul rezultatului, nume şi parametrii efectivi. Dacă funcţia nu returnează nimic, tipul
este void()
Corp – este un bloc de instrucţiuni declarative şi imperative (de execuţie) ce definesc modul de acţiune al
subprogramului
Prototip – pentru a putea fi apelată, funcţia trebuie declarată. Conţine date despre: tipul rezultatului, nume şi
parametrii efectivi.
Apel – este modul prin care subprogramul e pus în execuţie. Apelul poate fi făcut ori de câte ori este nevoie.
Parametrii – datele care circulă între modulul apelant şi apelat se introduc între paranteze, după numele
subprogramului.
Modul apelant – blocul ce conţine apelul subprogramului
Modul apelat – blocul ce conţine funcţia (subprogramul apelat).
De exemplu, modelul cum arată un subprogram:
# include <iostream.h>
# include <conio.h>
int max (int, int); PROTOTIPUL FUNŢIEI
void main (void)
{
clrscr();
cout << max(15, 30);
getch();
}

int max (int a, int b=3) APELUL FUNCŢIEI

{
if (a>b)
return a; DEFINIŢIA FUNCŢIEI
else antetul funcţiei şi corpul funcţiei
return b;
}
Transmiterea datelor între apelant şi apelat se poate face fie prin parametri, fie prin variabile [Link] utilizarea
variabilelor globale nu se face un transfer propriu-zis, ci se folosesc în comun anumite zone de memorie.
Transferul se poate face prin valoare sau prin referinţă/adresă.
Datele care se transferă între apelant şi apelat se introduc între paranteze, după identificatorul subprogramului.
-În antetul subprogramului parametrii se înscriu prin tip şi nume, separaţi prin virgulă, fără a fi grupaţi. Ei se numesc
parametri formali.
-În apelul subprogramului se înscriu separaţi prin virgulă, în aceeaşi ordine ca în antet, prin valori [Link] se
numesc parametri efectivi (actuali).
-Regula de corespondenţă notifică o anumită concordanţă între numărul, ordinea şi tipul parametrilor formali şi a
parametrilor efectivi.
Numărul parametrilor formali poate să difere de numărul parametrilor efectivi în cazul funcţiilor cu număr de
parametri variabil, respectiv în cazul supraîncărcării funcţiilor.
Tipul parametrilor formali poate să difere de tipul parametrilor efectiviîn cazul conversiei implicite a
parametrilor efectivi în tipul parametrilor formali, ca o operaţie de atribuire, respectiv în cazul supraîncărcării
funcţiei.
Numele parametrilor formali poate să difere de numele parametrilor efectivi.
Parametrii sunt memoraţi în segmentul de stivă în ordinea înscrierii lor.
Transmiterea prin referinţă/adresă - se transmite adresa parametrului actual.
Este utilizată la prelucrarea unei variabile în interiorul unei funcţii, astfel încât, la revenirea din funcţie, variabila să
reţină valoarea modificată, nu valoarea de intrare. Parametrii transmişi prin referinţă vor fi precedaţi de caracterul
ampersand “&”, atât la declararea, cât şi la definirea funcţiei.În apel, parametrii efectivi corespunzători parametrilor
formali transmişi prin referinţă trebuie să fie variabile de memorie. Transmiterea prin referinţă înseamnă că
parametrii sunt transmişi prin referinţă atunci când ne interesează ca la revenirea din subprogram, variabila
transmisă să reţină valoarea stabilită în timpul execuţiei subprogramului.
Transmiterea prin valoare – se transmite o copie a parametrului actual.
Este utilizată la prelucrarea unei variabile în interiorul unei funcţii. La revenirea din funcţie, variabila nu reţine
valoarea modificată, ci valoarea de intrare.
Parametrii transmişi prin valoare se folosesc doar ca parametri de intrare. Pentru parametrii de ieşire se va folosi
instrucţiunea return().
În apel, parametrii efectivi corespunzători parametrilor formali transmişi prin valoare pot fi : valori, variabile, expresii
sau alte funcţii.
Transmiterea prin valoare se utilizează atunci când suntem interesaţi ca subprogramul să lucreze cu acea valoare, dar
în prelucrare, nu ne interesează ca parametrul efectiv, cel din blocul apelant, să reţină valoarea modificată în
subprogram.
Se pot transmite prin valoare:
Valorile reţinute de variabile : parametrii efectivi trebuie să fie numele variabilelor care se trimit prin valoare.
Expresii, care pot conţine şi funcţii : parametrii efectivi sunt expresii care mai întâi se evaluează.
Sarcina de lucru: Căutaţi, identificaţi şi precizaţi elementele definitorii ale unui subprogram.
Enunţ: Precizaţi elementele subprogramelor şi caracteristicile acestora.
Faţa cub Cerinţele
1. Descrieţi elementele din definiţia unei funcţii
2. Comparaţi parametrii utilizaţi în subprograme
3. Analizaţi modul de construire a subprogramelor
4. Asociaţi fiecărui element de subprogram, caracteristicile sale
5. Aplicaţi fiecare element de subprogram într-un exemplu
6. Argumentaţi rolul fiecărui element de subprogram

Evaluare: Realizarea unui proiect prin care se evidenţiază şi se caracterizează elementele unui subprogram.

Sarcina de lucru: Căutaţi şi completaţii spaţiile libere , conform enunţurilor.

1. Transmiterea datelor între apelant şi apelat se poate face fie prin………………, fie prin
……………………………………….
2. În antetul subprogramului parametrii se înscriu prin tip şi nume, separaţi prin .................., fără a fi grupaţi. Ei
se numesc ...........................................
3. Regula de corespondenţă notifică o anumită ........................ între numărul, ordinea şi tipul
parametrilor ...................... şi a parametrilor ....................
4. Parametrii sunt memoraţi în .............................................. în ordinea înscrierii lor.
5. În apel, parametrii efectivi corespunzători parametrilor formali transmişi prin ……………… trebuie să fie
…………………………………………….
6. Transmiterea prin referinţă înseamnă că parametrii sunt transmişi prin …………………. atunci când ne
interesează ca la revenirea din subprogram, variabila transmisă să reţină ……………………………. în timpul
execuţiei subprogramului.
7. Parametrii transmişi prin valoare se folosesc doar ca parametrii ……………………….
8. Transmiterea prin valoare se utilizează atunci când suntem interesaţi ca ………………… să lucreze cu acea
valoare, dar în prelucrare, nu ne interesează ca …………………………., cel din blocul apelant, să reţină valoarea
modificată în subprogram.
9. În apelul subprogramului se înscriu separaţi prin ..................., în aceeaşi ordine ca în antet, prin valori
concrete şi se numesc parametrii ..................... (actuali).
10. Parametrii transmişi prin referinţă vor fi precedaţi de caracterul ....................................., atât la declararea,
cât şi la definirea funcţiei.

Evaluare: La final fiecare elev va primi 1 p pentru fiecare răspuns corect şi 0p pentru răspunsul greşit..
Apelul subprogramului este modul prin care subprogramul este pus în execuţie. Apelul subprogramului se poate
realiza în două moduri:
Printr-o instrucţiune de apel
Ca operand într-o expresie.
Instrucţiunea de apel a unui subprogram are următorul format general:
 nume (lista_parametrilor_actuali);
unde nume: reprezintă numele subprogramului. Lista parametrilor actuali este formată dintr-o succesiune de
expresii, separate prin virgulă.
Se utilizează instrucţiuni de apel atunci când subprogramul nu returnează nici o valoare sau când nu se doreşte
utilizarea valorii returnate de subprogram, ci doar efectuarea prelucrărilor descrise de subprogram.
În cazul în care se doreşte utilizarea valorii returnate de subprogram ca operand într-o expresie, se va apela
subprogramul în cadrul expresiei astfel:
nume (lista_parametrilor_actuali)
În această situaţie lipseşte caracterul „;”, care marchează sfârşitul instrucţiunii de apel.
La apelul unui subprogram, valorile parametrilor actuali sunt atribuite, în ordine, parametrilor formali corespunzători.
Atât procedurile, cât şi funcţiile, trebuie definite înainte de a fi apelate.
Apelarea unei funcţii nu este o instrucţiune de sine stătătoare , ea trebuie inclusă ca operant în cadrul unei expresii
O funcţie recursivă este o funcţie care se apelează pe ea însăşi. Există două tipuri de funcţii recursive:
- Funcţii cu un singur apel recursiv, ca ultimă instrucţiune, care se pot rescrie sub formă nerecursivă (iterativă)
- Funcţii cu unul sau mai multe apeluri recursive, a căror formă trebuie să folosească o stivă pentru memorarea unor
rezultate intermediare.
Recursivitatea este posibilă deoarece, la fiecare apel al funcţiei, adresa de revenire, variabilele locale şi parametrii
formali sunt memorate într-o stivă, iar la ieşirea din funcţie, se scot din stivă toate datele puse la intrarea în funcţie.
O funcţie recursivă trebuie să conţină cel puţin o instrucţiune if, de obicei la început, prin care se verifică dacă este
necesar un apel recursiv sau se iese din funcţie.
Apelul unei funcţii care nu returnează nici o valoare are forma generală:
nume_funcţie (lista parametrilor efectivi);
 parametru efectiv = parametru actual = parametru real = parametru de apel
 lista parametrilor efectivi = fie vidă, fie o expresie sau mai multe despărţite prin virgulă
La apelul unei funcţii, valorile parametrilor efectivi se atribuie parametrilor formali corespunzători. În cazul în care
unul din tipul unui paramatru efectiv diferă de tipul parametrului formal corespunzător, parametrul efectiv va fi
convertit spre parametru formal (dacă este posibil, altfel compilatorul generează eroare).
În momentul în care se întâlneşte un apel de funcţie, controlul execuţiei programul este transferat primei instrucţiuni
din funcţie, urmând a se executa secvenţial instrucţiunile funcţiei.
Revenirea dintr-o funcţie se face în unul din următoarele cazuri:
 după execuţia ultimei instrucţiuni din corpul funcţiei
 la întâlnirea unei instrucţiuni return
Pentru a apela o funcţie, aceasta trebuie mai întâi definită. Astfel apelul unei funcţii trebuie precedat de definiţia
funcţiei respective.
O a doua posibilitate de apelare a funcţiei constă în scrierea prototipului funcţiei înainte ca aceasta să fie apelată.
Prototipul funcţiei conţine informaţii asemănătoare cu cele din antetul funcţiei. Pot lipsi numele parametrilor formali
(contează doar tipul şi ordinea acestora), în plus acesa este urmat de “;”.

Tema [Link] programelor

Variabilele pot fi definite în C++ în orice poziţie a [Link] unde a fost definită o variabilă determină
domeniul de vizibilitate a acesteia. Acest domeniu începe în locul unde variabila este definită şi se sfârşeşte în locul
de încheiere a blocului ce o conţine.
Prin domeniul de vizibilitate se înţelege zona de program în care e valabilă declararea sau definirea unui identificator.
Variabilele globale sunt declarate la începutul programului, în afara funcţiilor, inclusv în afara rădăcinii. Acestea sunt
vizibile şi pot fi utilizate în orice punct al programului.
Sunt iniţilizate în mod automat cu zero. Durata lor de viaţă este pe tot parcursul executării programului.
Variabilele declarate într-o funcţie se numesc locale şi pot fi referite numai din funcţia respectivă. Sunt vizibile doar în
interiorul funcţiei. Nu sunt iniţializate automat. Durata lor de viaţă este pe tot parcursul executării funcţiei în care au
fost definite. Domeniul de valabilitate a unei variabile locale este funcţia sau instrucţiunea compusă în care a fost
definită.
Observaţii:
Variabilele globale pot fi modificate în interiorul subprogramelor, dar trebuie acordată mare atenţie
prelucrării acestora;
 Utilizarea variabilelor globale trebuie să fie limitată deoarece creează dependenţe între subprograme;
Utilizarea variabilelor locale asigură portabilitatea programelor;
Utilizarea constantelor globale permite modificarea, la nevoie, într-un singur loc a unei valori ce afectează
întregul program şi subprogramele sale;
Un program care are mai mulţi parametri, adică foloseşte mai puţine variabile globale, este mai flexibil şi mai
portabil;
Un program care are mai mulţi parametri, adică foloseşte mai puţine variabile globale, este mai uşor de
înţeles, de depanat şi de apelat;
Se vor declara subprogramele prin prototip la începutul fişierului sursă, iar definirea lor se va face după
funcţia rădăcină main().
În cazul în care există o variabilă locală care are acelaşi nume cu al unei variabile globale, aceste două variabile se
numesc variabile omonime. Variabilele locale sunt prioritare variabilelor globale omonime.
Plasarea subprogramelor în cadrul programului
 A defini un subprogram înseamnă a-l scrie efectiv, după o anumită structură. A declara un subprogram
înseamnă a-l anunţa. Un subprogram nedeclarat nu poate fi folosit. Definiţia unui subprogram ţine loc şi de
declaraţie.
Orice program trebuie să conţină:
Instrucţiuni imperative, prin care se comandă executarea anumitor acţiuni;
Declaraţii de variabile, de funcţii, etc. necesare compilatorului, dar fără efect la execuţie;
Comentarii, ignorate de compilator, necesare utilizatorului.
Instrucţiunile executabile sunt grupate în subprograme. În C++ trebuie să existe cel puţin o funcţie “main“ cu care
începe execuţia unui program. Celelalte funcţii sunt apelate din funcţia “main“ sau din alte funcţii activate direct sau
indirect de “main“.
 Acoladele sunt necesare pentru a delimita definiţia unei funcţii, care este un bloc de instrucţiuni şi declaraţii.
Un program descrie procedurile de obţinere a unor rezultate pe baza unor date iniţiale şi foloseşte rezultate
intermediare. Toate aceste date sunt memorate în variabile ale programului. Pot exista şi date constante, ale
căror valoari nu se pot modifica în cursul execuţiei. Toate variabilele folosite într-un program trebuie definite
sau declarate prin declaraţii ale limbajului de programare.
 Un program C este compus în general din mai multe funcţii, dintre care funcţia "main" nu poate lipsi,
deoarece cu ea începe execuţia programului.
 Definiţia unei funcţii C are un antet şi un bloc de instrucţiuni încadrat de acolade.
În interiorul unei funcţii existã de obicei şi alte blocuri de instrucţiuni, încadrate de acolade, şi care pot conţine
declaraţii de variabile.
Motivele utilizãrii de subprograme sunt multiple:
- Un program mare poate fi mai uşor de scris, de înţeles şi de modificat dacã este modular, deci format din module
funcţionale relativ mici.
- Un subprogram poate fi reutilizat în mai multe aplicaţii, ceea ce reduce efortul de programare al unei noi aplicaţii.
- Un subprogram poate fi scris şi verificat separat de restul aplicaţiei, ceea ce reduce timpul de punere la punct a unei
aplicaţii mari (deoarece erorile pot apare numai la comunicarea între subprograme corecte).
- Întreţinerea unei aplicaţii este simplificatã, deoarece modificãrile se fac numai în anumite subprograme şi nu
afecteazã alte subprograme (care nici nu mai trebuie recompilate).
Utilizarea de funcţii permite dezvoltarea progresivã a unui program mare, fie de jos în sus (“bottom up”), fie de sus în
jos (“top down”), fie combinat.

Sarcina de lucru: Căutaţi şi completaţii spaţiile libere, conform enunţurilor.

1. Locul unde a fost definită o variabilă determină ......................................... a acesteia.
2. Prin ………………………………….. se înţelege zona de program în care e valabilă declararea sau definirea unui
identificator.
3. Variabilele ........................ sunt declarate la începutul programului, în afara funcţiilor, inclusv în afara
rădăcinii.
 4. Variabilele declarate într-o funcţie se numesc ............................... şi pot fi referite numai din funcţia
respectivă.
5. Domeniul de valabilitate a unei variabile locale este ..........................sau........................................... în care a
fost definită.
6. Utilizarea variabilelor globale trebuie să fie limitată deoarece creează dependenţe
între .....................................
7. Un program care are mai mulţi parametri, adică foloseşte mai puţine variabile globale, este
mai ........................ şi mai ..........................
8. În cazul în care există o variabilă locală care are acelaşi nume cu o variabilă globală, aceste două variabile se
numesc .....................................................
Evaluare: La final fiecare elev va primi 1p pentru răspunsul corect şi 0p pentru răspunsul greşit.

Tema 3. Alocarea memoriei

Fiecărui program i se alocă trei zone distincte în memoria internă în care se găsesc memorate variabilele programului:

Segment de date

Segment de stivă

Heap
Există posibilitatea ca variabilele să fie memorate într-un anumit registru al microprocesorului. În acest caz, timpul de
acces la astfel de variabile este foarte mic, deci se pot obţine programe optimizate.
O variabilă se caracterizează prin 4 atribute. Acestea sunt:
Clasa de memorare
Vizibilitate
Durata de viaţă
Tipul variabilei.
Clasa de memorare precizează locul unde este memorată variabila respectivă. O variabilă poate fi memorată în
segmentul de date, în cel de stivă, în heap sau într-un registru al microprocesorului.

Vizibilitatea precizeză liniile textului sursă din care variabila respectivă poate fi accesată. Există:
Vizibilitate la nivel de bloc (instrucţiune compusă).
Vizibilitate la nivel de fişier – în cazul în care programul ocupă un singur fişier sursă.
Vizibilitate la nivel de clasă - în cazul programării pe obiecte.

Durata de viaţă reprezintă timpul în care variabila respectivă are alocat spaţiu în memoria internă. Există:
Durata statică – variabila are alocat spaţiu în tot timpul execuţiei programului.
Durata locală – variabila are alocat spaţiu în timpul în care se execută instrucţiunile blocului respectiv.
Durata dinamică – alocarea şi dezalocarea spaţiului necesar variabilei respective se face de către
programator prin operatori sau funcţii speciale.

 Atributele variabilelor globale sunt:

1. Clasa de memorare – este segmentul de date
2. Vizibilitatea – în cazul în care declaraţiile acestora sunt înaintea tuturor funcţiilor, acestea sunt
vizibile la nivelul întregului program sau fişier. Dacă anumite funcţii se află plasate înaintea
declaraţiilor acestor variabile, atunci ele sunt vizibile doar pentru funcţiile care sunt plasate după
aceste declaraţii.
3. Durata de viaţă – este statică. Variabilele globale au spaţiu rezervat în tot timpul execuţiei
programului.

 Atributele variabilelor locale sunt:

1. Clasa de memorare – este implicit segmentul de stivă. Există posibilitatea ca acestea să fie alocate
în registrele microprocesorului, caz în care declaraţia lor trebuie precedată de cuvântul cheie
“register”.
2. Vizibilitatea – este la nivelul blocului în care au fost declarate.
 3. Durata de viaţă – este atât timp cât durează execuţia blocului respectiv.

Fişa de documentare 3.2. – Implementarea structurilor dinamice de date

 Pointerii sunt variabile care conţin adresa de memorie a unei alte variabile. Din aceste considerente, pointerii
se numesc şi variabile de adresă.
Un pointer este o variabilă care păstrează adresa unei date, nu valoarea datei. Un pointer poate fi utilizat pentru
referirea diferitelor date şi structuri de date. Schimbând adresa memorată în pointer, pot fi manipulate informaţii
situate la diferite locaţii de memorie. Pointerii permit de asemenea crearea de noi variabile în timpul execuţiei
programului, prin alocare dinamică.
Un pointer poate fi utilizat doar după iniţializare: prin atribuirea adresei unei variabile sau prin alocare dinamică.
Numele unui tablou este un pointer constant spre primul său element.
Memoria internă poate fi privită ca o serie de octeţi. Pentru a-i distinge aceştia sunt numerotaţ[Link]ărul de ordine al
unui octet se numeşte adresă. Adresa primului octet al variabilei se numeşte adresa variabilei. Variabilele de tip
pointer se caracterizează prin faptul că valorile pe care le pot memora sunt adrese ale altor variabile.
Există adrese ale variabilelor de tip int, adrese ale variabilelor de tip float, adrese ale variabilelor de tip char, etc.
Din acest motiv şi tipul variabilelor de tip pointer este diferit. Anumite variabile pot fi declarate dinamic. Asta
înseamnă că:
 Spatiul necesar memorării este rezervat într-un segment special acestui scop, numit HEAP.
 În memorie se rezervă spaţiu în timpul executării programului, atunci când se utilizează un anumit
operator.

 Atunci când variabila respectivă nu mai este utilă, spaţiul din memorie este eliberat, pentru a fi rezervat,
dacă este cazul, pentru alte variabile.

Mecanismul alocării dinamice este următorul :

 Se declară o variabilă de tip pointer, s-o numim P, care permite memorarea unei adrese.
 Se alocă variabila dinamică prin operatorul NEW aplicat asupra unui tip, iar rezultatul este atribuit
variabilei P. În urma acestei operaţii variabila P reţine adresa variabilei alocate dinamic.
Prin structură de date se înţelege un ansamblu de date caracterizat prin relaţiile existente între ele şi prin operaţiile
care pot fi efectuate cu datele respective.
Vom numi nod, o variabilă de un anumit tip, care de obicei, este structurat. Ansamblul de date care formează
structura este alcătuit dintr-o mulţime cu un număr variabil de noduri.
 Tipul variabilei care alcătuieşte nodul nu caracterizează structura de date.
Structura de date este un concept abstract. Adică, conceptul în sine nu precizează locul unde structura respectivă va
fi memorată, adică clasa de memorare şi nici detaliile de implementare.
 Structurile dinamice de date sunt date structurate ale căror componente se alocă în mod dinamic.
Avantajele alocării dinamice sunt:
- memorie suplimentară pentru programe
- posibilitatea de a utiliza această memorie
Alocarea dinamica a componentelor structurii impune un mecanism prin care o nouă componentă apărută este
legată în succesiune logică de corpul structurii deja format până atunci. Rezultă că fiecare componentă, pe lângă
informaţia propriu-zisă pe care o deţine, trebuie să conţină şi o informaţie de legatură cu componenta cu care se
leagă logic în succesiune. Această informaţie de legătură va fi adresa componentei spre care se realizează
succesiunea logică, iar mecanismul se mai numeşte şi alocare înlănţuită dupa adrese.

În HEAP, structura respectivă va avea zone alocate componentelor sale în locurile găsite disponibile, care nu se succed
întotdeauna în ordinea în care este realizată înlănţuirea logică.

Sarcina de lucru: Căutaţi, identificaţi şi precizaţi valoarea logică a definiţiilor de mai jos.
Enunţ: Precizaţi valoarea logică a definiţiilor de mai jos.
1. Un pointer este o variabilă care nu păstreaza adresa unei date, ci valoarea datei.
 2. Schimbând adresa memorată în pointer, nu pot fi manipulate informaţii situate la diferite locaţii de memorie.
3. Numele unui tablou este un pointer constant spre primul său element.
4. Memoria internă poate fi privită ca o serie de biţi.
5. Structura de date nu este un ansamblu de date caracterizat prin relaţiile existente între ele şi prin operaţiile
care pot fi efectuate cu datele respective.
6. Tipul variabilei care alcătuieşte nodul caracterizează structura de date.
7. Structurile dinamice de date sunt date structurate ale căror componente se alocă în mod static.
8. Alocarea dinamica a componentelor structurii nu impune un mecanism prin care o nouă componentă
apărută este legată în succesiune logică de corpul structurii deja format până atunci.
9. O variabilă nu poate fi memorată în segmentul de date, în cel de stivă, în heap sau într-un registru al
microprocesorului.
Evaluare: Câte 1 p pentru fiecare răspuns corect 0 p – pentru fiecare răspuns greşit.

Fişa de documentare 3.3. – Structra dinamică de tip listă

O listă este o colecţie de elemente de informaţie (noduri) aranjate într-o anumită ordine. Lungimea unei liste este
numărul de noduri din listă. Structura corespunzătoare de date trebuie să ne permită să determinăm eficient care
este primul/ultimul nod în structură şi care este predecesorul/succesorul (dacă există) unui nod dat. De exemplu, aşa
arată cea mai simpla listă, lista liniară:

O listă circulară este o listă în care, după ultimul nod, urmează primul, deci fiecare nod are succesor şi predecesor.
O listă liniară este o colecţie de n noduri, n≥0, aflate într-o relaţie de ordine.
Operaţiile permise sunt :
accesul la oricare nod al listei pentru citirea sau modificarea informaţiei conţinute de acesta ;
adăugarea unui nod, indiferent de poziţia pe care o ocupă în listă ;
ştergerea unui nod, indiferent de poziţia pe care o ocupă în listă ;
schimbarea poziţiei unui nod în cadrul listei.

Structură liniară înseamnă faptul că fiecare nod, cu excepţia ultimului, are un nod succesor, adică care îi urmează în
listă, şi, cu excepţia primului nod, are un singur predecesor, adică care se află imediat înaintea lui în listă.
O listă liniară simplu înlănţuită este caracterizată prin faptul că relaţia de ordine definită pe mulţimea elementelor
este unică şi totală. Ordinea elementelor pentru o astfel de listă este specificată exclusiv printr-un câmp de informaţie
care este parte componentă a fiecărui element şi indică elementul următor, conform cu relaţia de ordine definită pe
mulţimea elementelor listei. Deci, fiecare element de listă simplu înlănţuită are următoarea structură:
Informaţie utilă Informaţie de legatura

data leg
Pe baza informaţiei de înlănţuire(păstrată în câmpul leg) trebuie să poată fi identificat următorul element din listă.
Dacă există un ultim element în listă, atunci lista se numeşte liniară. Dacă nu, există un element care să conţină în
câmpul informaţie valoarea null.
Listele pot fi organizate sub formă statică, de tablou, caz în care ordinea este implicit dată de tipul tablou
unidimensional, sau cel mai des, sub formă de liste dinamice, în care ordinea nodurilor este stabilită prin pointeri.
Nodurile listelor dinamice sunt alocate în memoria heap. Listele dinamice se numesc liste înlănţuite, putând fi simplu
sau dublu înlănţuite.
Modelul listei simplu înlănţuite este prezentat în fig.1:

Fig. 1Model de listă simplu înlănţuită

 Operaţii cu lista simplu înlănţuită:

[Link] unei liste simplu înlănţuite

Crearea unei liste simplu înlănţuite se va face astfel:
a) Iniţial lista este vidă:
b) Se generează nodul de introdus:
c) Se fac legăturile corespunzătoare:

[Link] la un nod al unei liste simplu înlănţuite

În funcţie de cerinţe, nodurile listei pot fi accesate secvenţial, extrăgând informaţia utilă din ele.

[Link] unui nod într-o listă simplu înlănţuită

Nodul de inserat va fi generat ca la paragraful 1; se presupune că are pointerul p.
Dacă lista este vidă, acest nod va fi singur în listă:
Dacă lista nu este vidă, inserarea se poate face astfel:
a) înaintea primului nod
b) după ultimul nod:
c) înaintea unui nod precizat printr-o cheie “key”:
- se caută nodul de cheie “key”:
- se inserează nodul de pointer p, făcând legăturile corespunzătoare:

d) după un nod precizat printr-o cheie “key”:

- se caută nodul având cheia “key”:
- se inserează nodul de adresă p, făcând legăturile corespunzătoare.

4. Ştergerea unui nod dintr-o listă simplu înlănţuită

La ştergerea unui nod se vor avea în vedere următoarele probleme: lista poate fi vidă, lista poate conţine un singur
nod sau lista poate conţine mai multe noduri.
De asemenea se poate cere ştergerea primului nod, a ultimului nod sau a unui nod dat printr-o cheie “key”.
a) Ştergerea primului nod
b) Ştergerea ultimului nod
c) Ştergerea unui nod de cheie “key”
5. Ştergerea unei liste simplu înlănţuite
În acest caz, se şterge în mod secvenţial fiecare nod.
O listă liniară dublu înlănţuită este caracterizată prin faptul că pe mulţimea elementelor sunt definite două relaţii de
ordine totală, inverse una celeilalte, înainte şi înapoi. Rezultă două secvenţializări ale listei.
Ordinea elementelor pentru o astfel de listă este specificată exclusiv prin două câmpuri de informaţie care sunt
parte componentă precedent, conform cu relaţiile de ordine definite pe mulţimea elementelor listei. Deci, fiecare
element de listă dublu înlănţuită are următoarea structură:

Informaţie utilă Informaţii de legatura

data urm prec

Pe baza informaţiilor de înlănţuire păstrate în câmpurile urm şi prec trebuie să poată fi identificate următorul element
din listă, respectiv elementul precedent.
Lista dublu înlănţuită este lista dinamică între nodurile căreia s-a definit o dublă relaţie: de succesor şi de predecesor.

Modelul listei dublu înlănţuite, este prezentat în figura 2.

 Fig.2 Model de listă dublu înlănţuită
Ca şi la lista simplu înlănţuită, principalele operaţii sunt:
 crearea;
 accesul la un nod;
 inserarea unui nod;
 ştergerea unui nod,
 ştergerea listei.
[Link] unei liste dublu înlănţuite
a)Iniţial lista este vidă:
După alocarea de memorie şi citirea datelor în nod, introducerea nodului de pointer în listă se va face astfel:
b) Se generează nodul de introdus:
c) Se fac legăturile corespunzătoare:

[Link] la un nod
Accesul la un nod se poate face:
 secvenţial înainte (de la „prim” spre „ultim”):
 secvenţial înapoi ( de la „ultim” spre „prim”):
 pe baza unei chei. Căutarea unui nod de cheie dată key se va face identic ca la lista simplu înlănţuită.

[Link] unui nod

Inserarea unui nod într-o listă dublu înlănţuită se poate face astfel:
a) înaintea primului nod:
b) după ultimul nod:
c) înaintea unui nod de cheie dată key;
d) după un nod de cheie dată key:

4.Ştergerea unui nod

Există următoarele cazuri de ştergere a unui nod din listă:
 ştergerea primului nod;
 ştergerea ultimului nod:
 ştergerea unui nod precizat printr-o cheie key.
5.Ştergerea listei
Ştergerea întregii liste se realizează ştergând nod cu nod.
O stivă se defineşte ca o listă liniară simplu înlănţuită în care toate intrările şi ieşirile se fac pe la un singur capăt al ei.
Stiva este o o structură de tip LIFO (Last In First Out), adică ultimul nod introdus este primul scos. Rezultă că,
înregistrarea de pe nivelul k reţine înregistrarea de pe nivelul k-1. În cazul stivei se reţine doar elementul din vârful
stivei.

Fig.3. Model de stivă

Fiind o structură particulară a unei liste simplu înlănţuite, operaţiile principale asupra unei stive sunt:
- push = adăugare - pune un element pe stivă; funcţia se realizează prin inserarea unui nod înaintea
primului;
- pop = eliminare - scoate elementul din vârful stivei; funcţia se realizează prin ştergerea primului nod;
- clear - ştergerea stivei;
Numărul de noduri care pot fi memorate la un moment dat este mai mic decât în cazul alocării dinamice înlănţuite, în
funcţie de gradul de ocupare al segmentului de date.
Pe un anumit nivel se reţine, de regulă, o singură informaţie, însă este posibil să existe şi mai multe informaţii pe un
nivel.
O coadă este o listă pentu care toate inserările sunt făcute la unul din capete, toate ştergerile, consultările,
modificările la celălalt capăt. Coada este o structură de tip FIFO (First In, First Out), adică primul nod introdus este
primul scos.

Se introduce
un element
nou
Fig. 4. Model de coadă

Operaţiile importante sunt:

 introducerea unui element în coadă - funcţia se realizează prin inserarea după ultimul nod;
 scoaterea unui element din coadă – funcţia se realizează prin ştergerea primului nod;
 ştergerea cozii – se şterge secvenţial fiecare nod

Sarcina de lucru: Folosind anumite cuvinte din cele date mai jos, descrieţi diferenţele dintre stivă şi coadă.
Listă liniară simplu înlănţuită, LIFO, înregistrare, push, pop, clear, noduri, FIFO,
Tema [Link] structurilor dinamice de date
Fişa de documentare 4.1. – Grafuri - prezentare
Se numeşte graf sau graf neorientat o pereche de mulţimi G = (A,B) în care A este mulţimea nodurilor (este finită şi
nevidă) şi B e mulţimea relaţiilor/muchiilor.
B = { (x,y) / x  A, y  A }
Exemplu1: un graf neorientat

A = {1,2,3,4,5}
B = {(1,2),(1,3),(2,3),(2,5)}
o Două noduri distincte pot fi unite prin cel mult o muchie.
o Nu există o muchie care uneşte un nod cu el însuşi (o muchie uneşte două noduri distincte).
o O muchie în care extremităţile coincid se numeşte buclă.

Un graf G se numeşte simplu dacă oricare două noduri ale sale sunt extremităţi pentru cel mult o muchie.

Un graf G = (V,E) este finit dacă V şi E sunt finite.

Se numeşte graf orientat o multime ordonată G = (V,E) în care V este

mulţimea nodurilor (finită şi nevidă), iar E este mulţimea arcelor.
Exemplu2:
V = {1,2,3,4,5}
E = {(1,2),(2,1),(2,3),(3,1),(5,2)}

Explicaţii:
Dacă (x,y) aparţine de B atunci:
- x şi y sunt noduri adiacente
- x şi y sunt extremităţile arcului (x,y)
- x şi y sunt incidente cu (x,y)
- în cazul grafurilor orientate:
- x este extremitatea iniţială a (x,y)
- y este extremitatea finală a (x,y)
Exemplu:
 1 este adiacent cu 2 şi 3
 1 şi 2 sunt extremităţile (1,2)
 nodul 1 este incident cu (1,2)
 (5,2) şi (2,3) sunt incidente
Gradul unui nod: numărul de muchii incidente cu el
d(x) - gradul nodului x
1: d(1) = 2
2: d(1) = 3
Pentru grafurile orientate, se definesc:
 Gradul exterior al lui x: d+(x) = numărul arcelor care pleacă din x
 Gradul interior al lui x: d-(x) = numărul arcelor care intră în x
Exemplu:
 pentru 2: d(1)=3; d+(1)=1; d-(1)=2;
Nodurile de grad 0 se numesc noduri izolate. Nodurile de grad 1 se numesc noduri terminale.
A. Pentru grafuri neorientate
Se numeşte lanţ o succesiune de noduri x 1 ... xk, cu proprietatea că oricare două noduri vecine (x i,xi+1) aparţin de B.
x1, xk sunt extremităţile lanţului.
Lungimea lanţului este egală cu numărul de muchii care îl compun, k-1.
Dacă nodurile din lanţ sunt distincte, atunci lanţul este elementar.

Exemplu3:
1,2,3,1,4 - Lanţ neelementar (lungime 4)
1,2,3,4 - Lanţ elementar (lungime 3)
1,2,3,1,2,5 - Lanţ neelementar (lungime 5)
1,2,3,5 - Nu este lanţ

B. Pentru grafuri orientate

Se numeşte lanţ o succesiune de arce u 1, u2 ... uk, cu proprietatea că oricare două arce de pe poziţii consecutive au un
nod comun.
Observaţie: nu contează ordinea de parcurgere
Se numeşte drum o succesiune de noduri x1, x2 ... xk cu proprietatea că (xi,xi+1) este arc.
Observaţie: contează ordinea de parcurgere
Dacă nodurile sunt distincte, drumul se numeşte elementar.

Exemplu4:

Lanţuri Drumuri
(1,2),(2,3),(3,4) - Da 1,2,3,1,2 - Drum neelementar
(1,2),(5,2),(2,3) - Da 1,2,3,4 - Drum elementar
(1,2),(2,1),(1,3) - Nu 3,1,2,5 - Nu este drum
(1,2),(2,3),(1,5),(5,2) - Nu
Cicluri. Circuite
A. Pentru grafuri neorientate
Se numeşte ciclu într-un graf neorientat un lanţ x 1,x2 ... xk şi oricare 2 muchii (xi,xi+1) sunt distincte.
Dacă un ciclu are toate nodurile distincte 2 câte 2 cu excepţia capetelor, atunci el se numeşte ciclu elementar.
Exemplu5:
1,2,3,4,1 - Ciclu elementar
2,3,4,1,2 - Ciclu elementar
1,2,3,4,2,3,1 - Nu este ciclu
1,2,3,4,2,5,1 - Ciclu neelementar

B. Pentru grafuri orientate

Se numeşte circuit într-un graf un drum x1,x2 ... xk cu proprietatea că x1 = xk şi arcele (xi,xi+1) să fie distincte 2 câte 2.
Un circuit în care toate nodurile sunt distincte cu excepţia capetelor se numeşte circuit elementar.
Exemplu6:
1,2,3,1 - Circuit elementar
2,3,1,2 - Circuit elementar
1,2,3,1,2,1 - Nu este circuit
2,1,2,3,1,5,2 - Circuit neelementar

Sarcina de lucru: Asociaţi definiţiilor din prima coloană noţiunile din cea de a doua coloană.
Coloana 1 Coloana 2
O muchie în care extremităţile coincid Graf neorientat
O mulţime ordonată G = (V,E) în care V este mulţimea nodurilor (finită şi Graf simplu
nevidă), iar E este mulţimea arcelor.
Numărul de muchii incidente cu el Noduri izolate
Nodurile de grad 1 Buclă
Numărul arcelor care pleacă din x Gradul unui nod
Dacă oricare două noduri ale sale sunt extremităţi pentru cel mult o muchie. Graf orientat
Nodurile de grad 0 Noduri terminale
O pereche de mulţimi G = (A,B) în care A este mulţimea nodurilor (este finită Gradul exterior al lui x
şi nevidă) şi B e mulţimea relaţiilor/muchiilor.
Fişa de documentare 4.2. – Reprezentarea grafurilor în memorie

Reprezentarea grafurilor în memorie

1. Reprezentarea prin matrice de adiacenţă

2. Liste de adiacenţă
3. Vector de muchii
4. Matrice arce-noduri

1. Matricea de adiacenţă
A. Pentru grafuri neorientate
 a[i,j] = 1, dacă între i şi j este muchie
 a[i,j] = 0 altfel.
0 1 1 1 1
1 0 1 1 1
1 1 0 1 0
1 1 1 0 0
1 1 0 0 0
Observaţie: Pe diagonala principală toate elementele sunt 0 (nu avem bucle).
Matricea este simetrică faţă de diagonala principală, deci: a[i,j] = a[j,i].
B. Pentru grafuri orientate
 a[i,j] = 1, dacă există arcul (i,j);
 a[i,j] = 0, altfel.
0 1 0 0 1
1 0 1 0 0
1 0 0 1 0
0 0 0 0 0
0 1 0 0 0
2. Liste de adiacenţă
Pentru fiecare nod se memorează o listă a vecinilor săi.
Pentru întregul graf este necesar un vector de liste (P) în care P i este adresa primului element al listei asociate lui i.
Exemplu7:

Nod Lista de adiacenţă asociată

1 2,3,5
2 1,3
3 1,2
4 -
5 1
Exemplu8:
Nod Lista de adiacenţă asociată
1 2,3
2 1,3
3 2
4 -
5 1
Observaţie: pentru grafurile orientate se memorează în lista lui i, nodurile k, pentru care exista arcul (i,k).
struct elem {
int nod;
elem *next;
};
elem *p[100];
int n;
3. Vector de muchii
struct muchie{
int x,y; // capetele arcului
} v[100];
int n,m;
4. Matricea noduri-arce
Este folosită în special pentru grafurile orientate

Exemplu9:

Matricea noduri-arce aferentă:

Sarcina de lucru: Realizaţi pentru un graf dat reprezentarea în memorie prin fiecare metodă.

Fişa de documentare 4.3. – Parcurgerea grafurilor

Metoda Breadth First (în lăţime)
A. Pentru grafuri neorientate
Exemplu10:
x= 1
1, 2, 3, 4, 6, 7, 8, 9, 5
Se porneşte de la un nod oarecare x.
Se vizitează toţi vecinii direcţi ai nodului x dacă nu au fost deja vizitaţi.
Fiecare dintre nodurile vizitate la pasul anterior devine nod curent şi
este prelucrat la fel ca nodul x.
Structuri de date necesare pentru implementare sunt:
 Matrice de adiacenţă (sau alte variante de reprezentare): a
 Coada (în care se memorează în ordinea parcursă nodurile
vizitate): c
o p, u - indicatorii primului şi ultimului element din
coadă
 Vectorul nodurilor vizitate: v
o v[i]=1, dacă i a fost vizitat;
o v[i]=0, altfel.
Parcurgerea BF se efectuează prin utilizarea structurii numită coadă, având grijă ca un nod să fie vizitat o singură dată.
Atunci când un nod a fost introdus în coadă, se marchează ca vizitat.
B. Pentru grafuri orientate
Observaţie: algoritmul se adaptează astfel încât să poată fi luaţi în considerare toţi vecinii unui nod.
Exemplu11:
x=1
1, 2, 3, 4, 5

Metoda Depth First(în adâncime)

A. Pentru grafuri neorientate

x=1
1, 2, 4, 5, 10, 9, 7, 8, 6, 3
Se porneşte de la un nod oarecare x.
Se alege primul vecin al lui x care nu a fost încă vizitat.
Pentru nodul ales se reia procedeul.
Dacă un nod nu are nici un vecin nevizitat se revine la nodul
vizitat anterior acestuia.
Structuri de date necesare implementării:
 Matrice de adiacenţă (sau alte variante): a
 Stiva: s (în care se memorează nodurile în ordinea
parcurgerii)
Dacă se implementează varianta recursivă, se va folosi
stiva procesorului
 Vectorul nodurilor vizitate: v

B. Pentru grafuri orientate

Exemplu13:
x = 10
10, 4, 2, 1, 3, 6, 8, 7, 9
Parcurgerea este similară, punându-se condiţia de parcurgere a
tuturor vecinilor unui nod indiferent de sens.

Sarcina de lucru: Prezentaţi diferenţele şi asemănările care apar la parcurgerea în lăţime, respectiv în adâncime
pentru grafurile neorientate, respectiv orientate.

Fişa de documentare 4.4. – Tipuri de grafuri

1. Graf partial
Fie G=(A,B) si G1=(A1,B1).
Spunem că G1 este un graf parţial al lui G dacă A=A 1 şi B1 este inclus sau egal cu B.
Un graf parţial se obţine dintr-un graf, îndepărtând o parte dintre muchiile sale şi păstrând toate nodurile acestuia.
Exemplu14:
2. Subgraful unui graf
Fie G=(A,B) şi G1=(A1,B1);
A1 inclus sau egal cu A; B1 inclus sau egal cu B.
B1 = {(x,y) / oricare x,y aparţine A1 dacă (x,y) aparţine de B => (x,y) aparţine de B 1}
Subgraful se obţine din graful iniţial selectând o parte din nodurile sale şi o parte din nodurile adiacente cu acesta.
Exemplu15:

Graful iniţial Nu (nu are toate muchiile)

Da
3. Graf complet
Un graf este complet dacă oricare două vârfuri distince sunt adiacente.
Exemplu16:

Un graf neorientat cu n noduri are n(n-1)/2 muchii.

Există un singur graf complet neorientat cu n noduri.
Există mai multe grafuri orientate complete cu n noduri.

4. Grafuri bipartite
Fie G=(A,B) neorientat.
G este bipartit dacă există două mulţimi, A1 şi A2 astfel încât A1 ∩ A2 = Ø şi A1 U A2 = A, iar oricare muchie (x,y)
aparţinând lui B are un capăt în mulţimea A1 şi celălalt în A2.
Exemplu17:
Un graf bipartit este bipartit complet dacă fiecare nod din mulţimea A 1 este adiacent cu toate nodurile din A2 şi
reciproc.
Exemplu18:

5. Grafuri conexe
Un graf este conex dacă este format dintr-un singur nod sau dacă între oricare două noduri ale sale există cel puţin un
lanţ.
A. Pentru grafuri neorientate
Exemplu19:

Da Nu

B. Pentru grafuri orientate

Exemplu20:

Da Nu
Se numeşte componentă conexă a unui graf un subgraf al său care este conex şi care este maximal în raport cu
această proprietate (dacă i se adaugă un nod îşi pierde această proprietate).
Observaţie: pentru grafurile orientate nu se ţine cont de orientarea arcelor.

6. Grafuri tare conexe

Un graf este tare conex dacă are un singur nod sau dacă oricare ar fi (x,y) există drum de la x la y şi există drum de la y
la x.
Determinarea componentelor tare conexe
Se poate realiza prin 3 metode:
1. Utilizând metoda DF/BF
2. Utilizând matricea drumurilor
3. Algoritmul +/-
O componentă tare conexă este un subgraf al său care este tare conex şi care este maximal în raport cu această
proprietate.
Observaţie: reunind toate arcele din componentele tare conexe se poate obţine o mulţime mai mică decât mulţimea
arcelor grafului iniţial.
Se poate construi un graf al componentelor tare conexe în care fiecare componentă tare conexă formează un nod, iar
arcele simuleaza legăturile dintre ele.
Exemplu21:

Da Nu
Determinarea componentelor tare conexe utilizând matricea drumurilor
d(i,j) = 1, dacă există drum de la i la j
d(i,j) = 0, altfel

1 1 0 1 0
1 1 0 1 0
1 1 1 1 1
1 1 0 1 0
1 1 1 1 1

[Link] hamiltoniene
Lanţ hamiltonian: lanţ elementar care conţine toate nodurile grafului.
Ciclu hamiltonian: ciclu elementar care conţine toate nodurile grafului.
Graf hamiltonian: graf care conţine un ciclu hamiltonian.

Teorema lui Dirac: Fie G dat prin perechea (A,B). Dacă G are un număr de cel puţin 3 vârfuri astfel încât gradul fiecărui
nod respectă condiţia d(x)≥n/2, atunci graful este hamiltonian.
8. Grafuri euleriene
Ciclu eulerian: ciclu care trece prin toate muchiile unui graf exact o dată.
Graf eulerian: graf care conţine cel puţin un ciclu eulerian.
Da (1,2,3,4,5,3,1) Da
Fişa de documentare 4.6. – Arbori

Un arbore este un graf neorientat, conex şi fără cicluri. Arborii reprezintă grafurile cele mai simple ca structură din
clasa grafurilor conexe, ei fiind cel mai frecvent utilizaţi în practică. Un arbore cu n varfuri are n-1 muchii.

Un arbore este o mulţime de elemente numite noduri sau vârfuri pentru care:
1. există un nod cu destinaţie specială (rădăcina arborelui);
2. celelalte noduri sunt repartizate în n≥0 seturi disjuncte A1, A2, ..., An fiecare set constituind la rândul său un
arbore.
În structura ierarhica a arborelui, fiecare nod (mai puţin rădăcina) este subordonat unui alt nod (relaţie fiu-părinte).
Dacă un nod nu are fi, el se numeşte terminal (sau frunză).
Fiind dat un graf neorientat conex, se numeşte arbore parţial al grafului un graf parţial cu proprietatea că este
arbore. Intuitiv, un arbore parţial este un arbore obţinut prin eliminarea unor muchii din graf.
Un arbore parţial al unui graf neorientat conex poate fi definit ca un graf parţial conex cu număr minim de muchii,
sau un graf parţial aciclic cu număr maxim de muchii.

Corolar: Un arbore cu n vârfuri are n - 1 muchii.

De exemplu :

dacă alegem 2 ca fiind rădăcină, reprezentarea arborelui pe nivele este:

iar nodul 2 este tatăl nodurilor 6, 1, 3, şi 7; 5 este fiul lui 6; 4 este fiul lui 3; iar 8 este fiul lui 7. Nodurile 5, 4, 8, şi 1 nu
au nici un fiu. Nodurile care nu au fii se mai numesc frunze sau noduri terminale, iar muchiile dintre noduri, ramuri.
Nodurile 6, 1 , 3 şi 7 sunt fraţi. Nodurile 6, 1 , 3 şi 7 sunt urmaşii lui 2. De asemenea, nodurile 5, 4 şi 8 sunt urmaşii lui
2, iar nodul 2 este strămoşul tuturor nodurilor (mai puţin el însuşi), 2 fiind rădăcina aborelui. 2 adică rădăcina este
singurul nod care nu are tată.
În general, un nod al unui arbore poate avea un număr arbitrar de fii. Dacă orice nod al unui arbore nu are mai mult
de n fii atunci arborele se numeşte arbore n-ar.
Se numeşte înălţime a unui arbore lungimea celui mai lung drum de la rădăcină la un nod terminal din arbore. Pentru
arborele de mai sus înălţimea este [Link] observă că între orice nod şi rădăcină există exact un singur drum.
Observaţii:
 În orice nod intră cel mult un arc;
 În nodul rădăcină nu intra nici un arc;
 Nodurile pot fi etichetate sau nu.

Înaltimea unui arbore este maximum dintre nivelele nodurilor terminale sau echivalent 1+ maximul dintre înălţimile
subarborilor săi.
Exemplu: Arborele prezentat în figura de mai sus are înălţimea 5.
Reprezentarea în memorie a arborilor poate fi statică sau dinamică. În cazul static arborii se pot simula cu ajutorul
tablourilor.
Exemplu: În tabloul arbore cu n componente, arbore(i) (i=1...n) reprezintă tatăl nodului i. Astfel, arborele din figura
de mai sus se poate reprezenta sub forma:

Avantajul acestei implementari este urmatorul: fiecărui nod având cel mult un tată, îi ataşăm în tablou o singură
informaţie (Luăm arbore(i)=0 dacă nodul i este rădăcină).
Datorită dinamismului structurilor modelate printr-un arbore, varianta de implementare dinamică este preferabilă
variantei statice.
Operaţiile fundamentale asupra arborilor includ: parcurgerea arborelui, ştergerea, căutarea sau adăugarea unui nod.
Două tipuri de parcurgere a unui arbore sunt folosite frecvent: parcurgerea în lăţime şi parcurgerea în înălţime.
În cazul parcugerii în lăţime se vizitează şi prelucrează nodurile în ordinea: rădăcina, nodurile de la stânga spre
dreapta de pe primul nivel, de pe al doilea nivel etc.

Sarcina de lucru: Căutaţi şi completaţii spaţiile libere, conform enunţurilor.

1. Un arbore este o multime de elemente numite ................... sau ............................
2. În structura ................. a arborelui, fiecare nod (mai putin radacina) este ................ unui alt nod (relatie fiu-
parinte).
3. Un arbore …………… al unui graf neorientat conex poate fi definit ca un graf parţial conex cu număr minim de
muchii, sau un graf parţial ……………. cu număr maxim de muchii.
4. Un arbore cu n ………………… are n - 1 muchii.
 5. Se numeste …………….. a unui arbore lungimea celui mai lung drum de la radacina la un nod terminal din
arbore.
6. Reprezentarea în memorie a arborilor poate fi ............... sau ...................
7. Un arbore este un graf …………….., conex şi fără ………………
[Link] consideră graful din figura următoare. Determinaţi toţi arborii parţiali ai acestui graf.

Evaluare: La final fiecare elev va primi 1p pentru fiecare răspuns corect din partea I, respectiv 2p pentru fiecare
arbore parţial găsit la partea a II-a.

Fişa de documentare 4.7. – Arbori binari

Un arbore în care orice nod nu are mai mult de 2 fii se numeşte arbore binar.
Un arbore binar este un arbore în care orice nod are cel mult doi descendenţi făcându-se distincţie clară între
descendentul drept şi descendentul stâng. Rădăcina unui arbore binar are doi subarbori, subarborele stâng, cel care
are drept rădăcina fiul stâng şi subarborele drept, cel care are ca rădăcină fiul drept. Orice subarbore al unui arbore
binar este el însuşi arbore binar. De exemplu, arborele de mai jos este un arbore binar; rădăcina 10, are drept fiu
stâng nodul 4, iar fiu drept nodul 21, nodul 21 are subarborele stâng format din nodul 15 şi subarborele drept format
din nodurile 23 şi 28.

Notă: Un arbore binar poate fi şi vid (adică fără nici un nod).

Un arbore binar pentru care orice nod neterminal are exact doi fii se numeşte arbore plin ("full").
Arborele binar este arborele în care un nod are cel mult doi fii. În aceasta situaţie se poate vorbi (pentru un arbore
nevid) de cei doi subarbori (stâng şi drept) ai unui arbore. Schematic avem:

Arbore binar

Reprezentare
De obicei, nodurile unui arbore, în particular binar, conţin, pe lângă informaţia corespunzatoare, şi informaţii despre
cei doi fii stâng şi drept. În calculator, arborii binari se pot reprezenta în două moduri.
 Reprezentarea secvenţială: Pentru fiecare nod al arborelui se precizează informaţia şi descendenţii direcţi ca
elemente a trei vector diferiţi, INFO[i], ST[i] şi DR[i], unde i este indicele asociat unui nod. Cei trei vectori au
dimensiunea egală cu numărul de noduri din arbore.
 Reprezentarea înlănţuită:Pentru fiecare nod al arborelui se precizează informaţia şi descendenţii direcţi ca
elemente ale unei structuri. Pentru arborele de mai sus, reprezentarea înlănţuită este:

Traversare
De multe ori dorim să accesăm ("vizităm") nodurile unei structuri (listă sau arbore). Pentru arbori această accesare,
examinare a unui nod, sau, mai exact, examinarea tuturor nodurilor unui arbore se numeşte traversare şi se poate
face:
o în preordine: întâi vizităm rădăcina arborelui, apoi subarborele stâng urmat de subarborele drept
o în inordine (simetrică): întâi vizităm subarborele stâng, , apoi rădăcina arborelui şi apoi subarborele
drept
o în postordine: întâi vizităm subarborele stâng şi subarborele drept şi ultima dată rădăcina arborelui.
Acţiunea explicită de vizitare a unui nod depinde de scopul traversării (de exemplu, aflarea numărului de elemente
ale arborelui, găsirea unei valori date în arbore). Pentru arborele de mai sus, de exemplu, traversările sunt:
o preordine: 10, 4, 1, 9, 21, 15, 23, 28
o inordine (simetrică): 1, 4, 9, 10, 15, 21, 23, 28
o postordine: 1, 9, 4, 15, 28, 23, 21.

Operaţii pe arbori binari:

Operaţiile pe arbori se grupează în următoarele categorii:
Operaţii de creare a arborilor binari.
Crearea arborilor binari presupune construirea în memorie a unui arbore binar folosind informaţii din mediul extern,
sursele cele mai frecvente fiind introducerea de la tastatura de către utilizator sau fişierele.
Algoritmii de creare ai unui arbore binar presupun a cunoaşte relaţiile în care se află un nod cu celelate noduri din
arbore. O metodă simplă de a specifica aceste relaţii este ca după crearea unui nod să se specifice fiul stâng şi fiul
drept, dacă ei există.
Operaţii cu elemente (noduri), categorie din care cele mai importante sunt operaţiile de inserare şi ştergere de
noduri în şi din arbore.
Deoarece operaţia de inserare a unui nod necesită specificarea relaţiei în care se află nodul respectiv cu celelate
noduri din arbore, iar ştergerea unui nod implică formarea unor noi relaţii între noduri, aceste operaţii sunt uşor de
definit în cazul în care peste mulţimea informaţiilor din noduri există o relaţie de ordine.
Traversări de arbori atât pentru prelucrarea informaţiei utile cât şi pentru căutare de informaţie în arbore.
Cele mai frecvente moduri de traversare utilizate în cazul arborilor binari sunt:
- preordine: traversarea se face prin rădăcina arborelui, apoi se traversează subarborele stâng, iar apoi
subarborele drept;
- inordine: traversarea se face începând cu subarborele stâng, apoi prin rădăcină, iar apoi se traversează
subarborele drept;
- postordine: traversarea se face începând cu subarborele stâng, apoi se traversează subarborele drept, iar
apoi rădăcina.
Se numeşte arborescenţă un arbore caracterizat astfel:
 -are un vârf special numit rădăcină;
-celelalte noduri pot fi grupate în p>=0 mulţimi disjuncte, astfel
încât fiecare dintre aceste mulţimi să conţină un nod adiacent cu rădăcina iar subgrafurile generate
de acestea să fie la rândul lor arborescenţe.
OBSERVAŢII!
1. Dacă o arborescenţă este formată dintr-un singur nod spunem că este formată doar din nodul
rădăcină.
2. Dacă ordinea relativă a arborescenţelor, are importanţă, arborescenţa se numeşte arbore ordonat.
Informaţia din fiecare nod este mai mare decât informaţia din nodul fiului stâng şi mai mică sau egală cu cea din
nodul fiului drept. Un astfel de arbore se poate reprezenta printr-o structură de date înlănţuită, în care fiecare nod
este un obiect. Pe lângă un câmp cheie şi date adiţionale, fiecare obiect nod conţine câmpurile stânga, dreapta şi p
care punctează spre nodurile corespunzătoare fiului stâng, fiului drept şi respectiv părintelui nodului.
Înt-un arbore binar de căutare, cheile sunt întotdeauna astfel memorate încât ele satisfac proprietatea arborelui
binar de căutare:
Fie x un nod dintr-un arbore binar de căutare. Dacă y este un nod din subarborele stâng al lui x, atunci cheie[y] 
cheie[x]. Dacă y este un nod din subarborele drept al lui x, atunci cheie[x]  cheie[y].
Proprietatea arborelui binar de căutare ne permite să afişăm toate cheile în ordine crescătoare, parcurgînd nodurile
arborelui în inordine.
Exemple:

(a) (b)
Sarcina de lucru: Pornind de la informaţiile date, realizaţi un eseu de aproximativ 10 rânduri în care să dezvoltaţi
ideile conţinute în enunţuri.
"Rădăcina unui arbore binar are doi subarbori, subarborele stâng, cel care are drept rădăcină fiul stâng şi
subarborele drept, cel care are ca rădăcină fiul drept. Orice subarbore al unui arbore binar este el însuşi arbore binar.
"…………..
" Crearea arborilor binari presupune construirea în memorie a unui arbore binar folosind informaţii din
mediul extern, sursele cele mai frecvente fiind introducerea de la tastatură de către utilizator sau fişierele.
"………………….

Tema [Link]ţii / metode predefinite

Un program scris în limbajul C/C++ este un ansamblu de funcţii, fiecare dintre acestea efectuând o activitate bine
definită.
Funcţiile comunică prin argumente: ele primesc ca parametri (argumente) datele de intrare, efectuează prelucrările
descrise în corpul funcţiei asupra acestora şi pot returna o valoare (rezultatul, datele de ieşire). Execuţia programului
începe cu funcţia principală, numită main. Funcţiile pot fi descrise în cadrul aceluiaşi fişier, sau în fişiere diferite, care
sunt testate şi compilate separat, asamblarea lor realizându-se cu ajutorul link-editorului de legături.

O funcţie este formată din antet şi corp:

antet_funcţie
{
corpul_funcţiei
}
Orice mediu de programare este prevăzut cu una sau mai multe biblioteci de funcţii predefinite. Orice bibliotecă este
formată din:
 fişierele header (conţine prototipurile funcţiilor, declaraţiile de variabile);
 biblioteca (arhiva) propriu-zisă (conţine definiţii de funcţii).
Pentru ca funcţiile predefinite să poată fi utilizate, fişierele header în care se găsesc prototipurile acestora trebuie
inclus în funcţia (programul) apelant printr-o directivă preprocesor (exemplu #include <stdio.h>). Deasemenea,
utilizatorul îşi poate crea propriile headere proprii. Pentru a putea utiliza funcţiile proprii, el trebuie să includă aceste
headere în programul apelant (exemplu #include "my_header.h").
Pentru funcţiile predefinite, au fost create fişiere header orientate pe anumite numite tipuri de aplicaţii. De exemplu,
funcţiile matematice se găsesc în headerul <math.h>. Headerul <stdlib.h> care conţine funcţii standard. Headerul
<values.h> defineşte o serie de constante simbolice (exemplu MAXINT, MAXLONG) care reprezintă, în principal,
valorile maxime şi minime ale diferitelor tipuri de date.
Funcţii matematice (headerul <math.h>)
Funcţii aritmetice
Funcţii de rotunjire
Funcţii trigonometrice
Funcţii trigonometrice inverse
Funcţii exponenţiale şi logaritmice
Funcţii de generare a numerelor aleatoare

Funcţii de clasificare (testare) a caracterelor

Au prototipul în headerul <ctype.h>. Toate aceste funcţii primesc ca argument un caracter şi returnează un număr
întreg care este pozitiv dacă argumentul îndeplineşte o anumită condiţie, sau valoarea zero dacă argumentul
nu îndeplineşte condiţia.
Funcţii de conversie a caracterelor (prototip în <ctype.h>) int tolower(int c);
Funcţii de conversie din şir în număr (de citire a unui număr dintr-un şir)
Funcţii de intrare/ieşire (prototip în <stdio.h>)
În limbajul C, operaţiile asupra fişierelor se realizează cu ajutorul unor funcţii din biblioteca standard (stdio.h).
Transferurile cu dipozitivele periferice (tastatură, monitor, disc, imprimantă, etc.) se fac prin intermediul unor
dispozitive logice identice numite stream-uri (fluxuri) şi prin intermediul sistemului de operare. Un flux de date este
un fişier sau un dispozitiv fizic tratat printr-un pointer la o structură de tip FILE (din header-ul stdio.h).
În abordarea limbajului C (impusă de stdio.h), toate elementele care pot comunica informaţii cu un program sunt
percepute - în mod unitar - ca fluxuri de date. Datele introduse de la tastatură formează un fişier de intrare (fişierul
standard de intrare). Datele afişate pe monitor formează un fişier de ieşire (fişierul standard de ieşire). Sfârşitul
oricărui fişier este indicat printr-un marcaj de sfârşit de fişier (end of file). De obicei, schimbul de informaţii dintre
programe şi periferice se realizează folosind zone tampon. O zonă tampon păstrează una sau mai multe înregistrări.
Prin operaţia de citire, înregistrarea curentă este transferată de pe suportul extern în zona tampon care îi
corespunde, programul având apoi acces la elementele înregistrării din zona tampon. În cazul operaţiei de scriere,
înregistrarea se construieşte în zona tampon, prin program, fiind apoi transferată pe suportul extern al fişierului. În
cazul monitoarelor, înregistrarea se compune din caracterele unui rând. De obicei, o zonă tampon are lungimea
multiplu de 512 octeţi. Orice fişier trebuie deschis inainte de a fi prelucrat, iar la terminarea prelucrării lui, trebuie
închis.
Fluxurile pot fi de tip text sau de tip binar. Fluxurile de tip text împart fişierele în linii separate prin caracterul ’\n’
(newline=linie nouă), putând fi citite ca orice fişier text. Fluxurile de tip binar transferă blocuri de octeţi (fără nici o
structură), neputând fi citite direct, ca fişierele text.

Sarcina de lucru: Căutaţi şi modificaţi conform enunţurilor, erorile apărute în definiţiile date.
1. Un program scris în limbajul C/C++ este un ansamblu de parametri, fiecare dintre acestea efectuând o
activitate bine definită.
2. Funcţiile comunică prin argumente: ele primesc ca biblioteca datele de intrare, efectuează prelucrările
descrise în fişierul funcţiei asupra acestora şi pot returna o valoare (rezultatul, datele de ieşire).
3. Funcţiile pot fi create în cadrul aceluiaşi fişier, sau în fişiere diferite, care sunt testate şi analizate separat,
asamblarea lor realizându-se cu ajutorul link-editorului de legături.
4. Orice mediu de funcţii este prevăzut cu una sau mai multe biblioteci de funcţii predefinite.
 5. Pentru ca bibliotecile predefinite să poată fi utilizate, fişierele header în care se găsesc prototipurile acestora
trebuie exclus în funcţia (programul) apelant printr-o directivă preprocesor (exemplu #include <stdio.h>).
6. Pentru funcţiile predefinite, au fost şterse fişiere header orientate pe anumite numite tipuri de aplicaţii.
7. În limbajul C, operaţiile asupra parametrilor se realizează cu ajutorul unor funcţii din biblioteca standard
(stdio.h).
8. În abordarea limbajului C (impusă de stdio.h), toate funcţiile care pot comunica informaţii cu un program
sunt percepute - în mod unitar - ca fluxuri de date.
9. Începutul oricărui fişier este indicat printr-un marcaj de sfârşit de fişier (end of file).
10. O zonă tampon păstrează una sau mai multe variabile.

Evaluare: La final fiecare elev va primi 1p pentru fiecare răspuns corect şi 0p pentru răspunsul greşit la partea I,
respectiv 10p pentru partea a II-a

Tema [Link]ăţi şi tehnici de utilizare a funcţiilor / metodelor predefinite

Limbajul C posedă o bibliotecă de funcţii C care pot fi utilizate în cadrul programului. În bibliotecile standard ale
limbajului C şi C++ există funcţii predefinite care pot fi uşor folosite de către utilizatori. Apelul lor implică existenţa
prototipului lor. Pentru aceste funcţii standard există anumite fişiere standard, headere, de tip *.h, (stdio.h, string.h,
etc.) care conţin prototipul unor funcţii înrudite. Aceste fişiere headere se includ printr-o directivă preprocesor.
 stdio.h - conţine funcţii de introducere - extragere a datelor. Funcţiile utilizate până în acest moment (de ex:
getchar, printf, gets, etc.) operează cu fişierele standard de introducere şi extragere: stdin(implicit tastatura) şi stdout
(implicit monitorul). Prin redirectare aceste fişiere standard se pot asocia cu alte fişiere.
Un fişier este o structură dinamică, situată în memoria secundară ( pe flopyy disk-uri sau harddisk-uri ); numărul de
elemente ale unui fişier este variabil, chiar nul.
Limbajul C permite operarea cu fişiere:
 de tip text - un astfel de fişier conţine o succesiune de linii, separate prin NL ('\n')
 de tip binar - un astfel de fişier conţine o succesiune de octeţi, fără nici o structură.
Prelucrarea unui fişier presupune asocierea acestuia cu un canal de I/E ( numit flux sau stream ). Există două canale
predefinite, care se deschid automat la lansarea unui program:
 stdin - fişier de intrare, text, este intrarea standard - tastatura
 stdout - fişier de ieşire, text, este ieşirea standard - ecranul monitorului.
Pentru a prelucra un fişier, trebuie parcurse urmatoarele etape:
 se defineşte o variabilă de tipFILE *pentru accesarea fişierului; FILE * este un tip structură definit în stdio.h,
care conţine informaţii referitoare la fişier şi la tamponul de transfer de date între memoria centrala şi fişier
( adresa, lungimea tamponului, modul de utilizare a fişierului, indicator de sfârşit, de poziţie în fişier )
 se deschide fişierul pentru un anumit mod de acces, folosind funcţia de bibliotecă fopen, care realizează şi
asocierea între variabila fişier şi numele extern al fişierului
 se prelucrează fişierul în citire/scriere cu funcţiile specifice
 se închide fişierul folosind funcţia de bibliotecă fclose.
Practic, nu există program care să nu apeleze funcţii din bibliotecile existente şi care să nu conţină definiţii de funcţii
specifice aplicaţiei respective. În limbajul C există numai funcţii, dar pentru funcţiile fără rezultat direct (asociat
numelui funcţiei) s-a introdus tipul void. Pentru o funcţie cu rezultat direct tipul funcţiei este tipul rezultatului.

Argumentele folosite la apelul funcţiei se numesc argumente efective şi pot fi orice expresii (constante, funcţii etc.).
Argumentele efective trebuie să corespundă ca număr şi ca ordine (ca semnificaţie) cu argumentele formale (cu
excepţia unor funcţii cu număr variabil de argumente Este posibil ca tipul unui argument efectiv să difere de tipul
argumentului formal corespunzator, cu condiţia ca tipurile să fie "compatibile" la atribuire.
Conversia de tip (între numere sau pointeri) se face automat, la fel ca şi la atribuire. Tipul unei funcţii C poate fi orice
tip numeric, orice tip pointer, orice tip structură (struct) sau void. În lipsa unei declaraţii de tip explicite se consideră
ca tipul implicit al funcţiei este int. Funcţia "main" poate fi declarată fie de tip void, fie de tip int, explicit sau implicit.

Variabilele definite într-o funcţie pot fi folosite numai în funcţia respectivă, cu excepţia celor declarate extern. Pot
exista variabile cu aceleaşi nume în funcţii diferite, dar ele se referă la adrese de memorie diferite. O funcţie are în
general un număr de argumente formale (fictive), prin care primeşte datele iniţiale necesare şi poate transmite
rezultatele funcţiei. Aceste argumente pot fi doar nume de variabile (nu orice expresii) cu tipul declarat în
lista de argumente, pentru fiecare argument în parte.

Standardul limbajului C conţine şi o serie de funcţii care trebuie să existe în toate implementarile limbajului.
Declaraţiile acestor funcţii sunt grupate în fişiere antet cu acelaşi nume pentru toate implementarile. În afara acestor
funcşii standard, există şi alte funcţii specifice sistemului de operare, precum şi funcţii utile pentru anumite aplicaţii
(grafica pe calculator, baze de date, aplicaţii de reţea s.a.
Uneori, aceleaşi operaţii se pot realiza cu funcţii universale sau cu funcţii dependente de sistem: obţinere/modificare
timp, operaţii cu directoare s.a. Utilizarea funcţiilor standard din biblioteci reduce timpul de dezvoltare a
programelor, măreşte portabilitatea lor şi contribuie la reducerea diversităţii programelor, cu efect asupra uşurinţei
de citire şi de înţelegere a lor. Funcţiile de biblioteca nestandard utilizate ar trebui marcate prin comentarii.
Informaţii complete asupra funcţiilor de bibliotecă pot fi obţinute prin ajutor (Help) oferit de orice mediu IDE sau prin
examinarea fişierelor antet, de tip H.

În definirea funcţiilor se folosesc pointeri pentru:

- Transmiterea de rezultate prin argumente;
- Transmiterea unei adrese prin rezultatul funcţiei;

De obicei, schimbul de informaţii dintre programe şi periferice se realizează folosind zone tampon. O zonă tampon
păstrează una sau mai multe înregistrări. Prin operaţia de citire, înregistrarea curentă este transferată de pe suportul
extern în zona tampon care îi corespunde, programul având apoi acces la elementele înregistrării din zona tampon. În
cazul operaţiei de scriere, înregistrarea se construieşte în zona tampon, prin program, fiind apoi transferată pe
suportul extern al fişierului. În cazul monitoarelor, înregistrarea se compune din caracterele unui rând. De obicei, o
zonă tampon are lungimea multiplu de 512 octeţi. Orice fişier trebuie deschis inainte de a fi prelucrat, iar la
terminarea prelucrării lui, trebuie închis.

Fluxurile pot fi de tip text sau de tip binar. Fluxurile de tip text împart fişierele în linii separate prin caracterul ’\n’
(newline=linie nouă), putând fi citite ca orice fişier text. Fluxurile de tip binar transferă blocuri de octeţi (fără nici o
structură), neputând fi citite direct, ca fişierele text.

Prelucrarea fişierelor se poate face la două niveluri:

 Nivelul superior de prelucrare a fişierelor în care se utilizează funcţiile specializate în prelucrarea fişierelor.
 Nivelul inferior de prelucrare a fişierelor în care se utilizează direct facilităţile oferite de sistemul de operare,
deoarece, în final, sarcina manipulării fişierelor revine sistemului de operare. Pentru a avea acces la informaţiile
despre fişierele cu care lucrează, sistemul de operare foloseşte câte un descriptor (bloc de control) pentru fiecare
fişier.

După deschiderea unui fişier, toate operaţiile asupra fişierului vor fi efectuate cu pointerul său. Operaţiile de citire şi
scriere într-un fişier text pot fi:
 intrări/ieşiri la nivel de caracter (de octet);
 intrări/ieşiri la nivel de cuvânt (2 octeţi);
 intrări/ieşiri de şiruri de caractere;
 intrări/ieşiri cu formatare.

Comunicarea de informaţie de la un fişier către un program este asigurată prin funcţii de citire care transferă o
cantitate de octeţi (unitatea de măsură în cazul nostru) din fişier într-o variabilă-program pe care o vom numi buffer,
ea însăşi având sensul unei înşiruiri de octeţi prin declaraţia void *buf. Comunicarea de informaţie de la un program
către un fişier este asigurată prin funcţii de scriere care transferă o cantitate de octeţi dintr-o variabilă-program de tip
buffer în fişier.

Fişierele sunt percepute în limbajul C ca fiind, implicit, secvenţiale (informaţia este parcursă succesiv, element cu
element). Pentru aceasta, atât fluxurile de date cât şi indicatorii de fişier au asociat un indicator de poziţie curentă în
cadrul fişierului. Acesta este iniţializat la 0 în momentul deschiderii, iar operaţiile de citire, respectiv scriere, se referă
la succesiunea de octeţi care începe cu poziţia curentă. Operarea asupra fiecărui octet din succesiune determină
incrementarea indicatorului de poziţie curentă.