Date, variabile, expresii Datele cu care lucreaza algoritmii se pot clasifica dupa urmatoarele criterii: 1. in functie de posibilitatea de a-si modifica valoarea avem constante si variabile; 2. dupa tipul datelor: numerice(naturale, intregi, reale), logice(booleene), alfabetice 3. organizarea datelor: simple, structurate Variabilele inmagazineaza o valoare ce poate fi modificata pe parcursul executiei algoritmului. Ele se caracterizeaza prin: - nume (succesiune de litere si cifre, primul caracter fiind litera) - tip - valoare - adresa zonei de memorie rezervata variabilei Expresiile sunt utilizate in scopul efectuarii calculelor. O expresie este alcatuita din unul sau mai multi operanzi legati intre ei prin operatori. Operanzii pot fi constante, variabile sau expresii incadrate intre paranteze rotunde. Operatorii desemneaza operatii care se executa asupra operanzilor. Evaluarea unei expresii presupune inlocuirea variabilelor din expresie cu valorile lor curente si efectuarea calculelor. In procesul de evaluare al unei expresii se respecta regulile de baza invatate la matematica (se tine cont de prioritatea operatorilor si de asociativitatea acestora). In urma evaluarii unei expresii se obtine o valoare rezultat, tipul acestei valori indicand tipul expresiei.
Transcript
Date, variabile, expresii
Datele cu care lucreaza algoritmii se pot clasifica dupa urmatoarele criterii:1. in functie de posibilitatea de a-si modifica valoarea avem constante si variabile;2. dupa tipul datelor: numerice(naturale, intregi, reale), logice(booleene), alfabetice3. organizarea datelor: simple, structurate
Variabilele inmagazineaza o valoare ce poate fi modificata pe parcursul executiei algoritmului. Ele se caracterizeaza prin:- nume (succesiune de litere si cifre, primul caracter fiind litera)- tip - valoare - adresa zonei de memorie rezervata variabilei
Expresiile sunt utilizate in scopul efectuarii calculelor. O expresie este alcatuita din unul sau mai multi operanzi legati intre ei prin operatori.Operanzii pot fi constante, variabile sau expresii incadrate intre paranteze rotunde.Operatorii desemneaza operatii care se executa asupra operanzilor.Evaluarea unei expresii presupune inlocuirea variabilelor din expresie cu valorile lor curente si efectuarea calculelor. In procesul de evaluare al unei expresii se respecta regulile de baza invatate la matematica (se tine cont de prioritatea operatorilor si de asociativitatea acestora).In urma evaluarii unei expresii se obtine o valoare rezultat, tipul acestei valori indicand tipul expresiei.Operatorii utilizati in limbajul C sunt:- aritmetici: +, -, *, /, %(restul impartirii intregi)- relationali: <, >, <=, >=, =, !=(diferit)- logici: !(negatia), && (conjunctia), ||(disjunctia)Operatorii sunt impartiti in patru grupe de prioritate:1. operatori unari (au un singur operand): !, +, -2. operatori multiplcativi: *, /, %, && 3. operatori aditivi: ||, +, - 4. operatori relationali: <, >, <=, >=, =, !=(diferit)
Operatiile efectuate de un algoritm sunt:- operatii de intrare/iesire - operatii de atribuire - operatii de decizie Setul de caractere utilizat in limbajul C este:- litere mari si mici ale alfabetului englez: a, b, ..., z, A, B, ..., Z
Prin identificator intelegem un nume asociat unei constante, variabile, funtii, etc. Un identificator poate contine numai litere, cifre si caracterul special "_", primul caracter fiind obligatoriu o litera mare sau mica sau caracterul "-".
Cuvintele cheie ale limbajului sunt identificatori cu semnificatie fixata, care nu pot fi folositi in alt context decat cel precizat in definirea limbajului.
Comentariile sunt succesiuni de caractere incadrate intre caracterele: /* si */ sau intre // si sfarsitul liniei.
Constante. Identificatori
Constantele sunt valori ce nu se modifica in cadrul programului.Variabilele sunt date ale caror valori se pot modifica la fiecare executie a programului sau chiar in timpul unei executii.Constantele intregi sunt numere intregi exprimate in:zecimal - succesiuni de cifre zecimale (ex: 100)octal - succesiuni de cifre octale precedate de 0 (ex: 024)hexazecimal - succesiuni de cifre hexazecimale precedate de 0x sau 0X (ex: 0xFF1)
Constantele reale pot fi specificate in notatia uzuala sau in format exponential (stiintific). In forma uzuala cuprind partea intreaga si partea zecimala, separate de caracterul .(punct). In format exponential se specifica in plus un exponent al lui 10, precedat de e sau E. In acest caz valoarea numarului se obtine inmultind numarul (corespunzator constructiei din fata literei e/E) cu 10 la puterea specificata de exponent.
Constantele sir de caractere sunt constituite dintr-o succesiune de caractere incadrate intre ghilimele. Sunt reprezentate intern prin codurile ASCII ale caracterelor si terminate cu '\0' (terminatorul sirurilor de caractere sau caracterul NULL).
O constanta simbolica este o constanta desemnata printr-un identificator. Poate fi predefinita sau definita de utilizator.
Exemple de constante simbolice predefinite in C/C++:
- MAXINT cu valoarea 32767- MAXLONG cu valoarea 2147483647
Notiunea de tip de data. Operatori aritmetici, logici, relationali
Un tip de date defineste multimea valorilor pe care le pot lua datele de tipul respectiv, modul de reprezentare a acestora in memorie, precum si operatiile care se pot efectua cu datele respective.Multimea valorilor unui tip de data reprezinta constantele tipului respectiv. Tipul unei constante este determinat implicit de valoarea ei.Orice limbaj de programare dispune de un set de tipuri predefinite (standard).
Tip Domeniu de valoriMod de
reprezentarechar [-128, 127] 1 octet cu semnunsigned char [0, 255] 1 octet fara semnint [-32768, 32767] 2 octeti cu semnunsigned int [0, 65535] 2 octeti fara semn
long int[-2147483648, 2147483647]
4 octeti cu semn
unsigned long int
[0, 4294967295] 4 octeti fara semn
Observatie:Pentru a specifica explicit tipul unei constante intregi se pot utiliza sufixele u/U pentru unsigned int, l/L pentru long int, ul/Ul/uL/UL pentru unsigned long int.
Asupra datelor numerice se pot aplica urmatorii operatori:
+ (adunare)
- (scadere)* (inmultire)/ (impartire reala daca cel putin un operand este real)/ (impartire intreaga daca ambii operanzi sunt intregi)% (restul impartirii intregi)
Exemple de expresii in care intervin operatori aritmetici:
21/2 va da valoarea 1021%2 va da valoarea 121./2 va da valoarea 10.5
Operatori relationali:
< (mai mic)> (mai mare)<= (mai mic sau egal)>= (mai mare sau egal)== (egal)!= (diferit)
Exemple de expresii in care intervin operatorii relationali
5>=7 va da valoarea 05==7 va da valoarea 05!=7 va da valoarea 1
Operatori pe biti (pentru datele intregi):
~ (negati pe biti: se transforma bitii astfel: 0 in 1 si 1 in 0& (SI aritmetic pe biti (se face conjunctia bit cu bit intre operanzi)| (SAU aritmetic pe biti (se face disjunctia bit cu bit intre operanzi)^ (SAU exclusiv pe biti (se executa SAU exclusiv bit cu bit intre operanzi)<< (deplasare la stanga (bitii primului operand se deplaseaza spre stanga cu valoarea celui de-al doilea operand)>> (deplasare la dreapta (bitii primului operand se deplaseaza spre dreapta cu valoarea celui de-al doilea operand)
Exemple de expresii in care intervin operatori pe biti:
8>>1 va da valoarea 4~8 va da valoarea -9
In C nu exista tipul logic insa, orice valoare diferita de 0 are semnificatia adevarat, valoarea logica fals fiind asociata valorii 0.
Operatorii logici sunt:! (negatie logica)&& (SI logic sau conjunctie logca )|| (SAU logic sau disjunctie logica )
Exemple de expresii in care intervin operatorii logici:
(a==b) && (a!=b) are valoarea 0!(2>5) are valoarea 1
In C++ exista tipul void care se utilizeaza pentru a indica absenta oricarei valori.
Definirea tipurilor de date
Definirea unor noi tipuri de date se face astfel:
typedef descriere_tip nume_tip;
Exemplu:typedef float real;
Un tip enumerat defineste o multime ordonata de valori prin enumerarea identificatorilor care desemneaza valorile. Un tip enumerat poate primi un nume:
identificator 1 desemneaza cea mai mica valoare, avand numarul de ordine 0; ceilalti identificatori au numerele de ordine urmatoare; in C se pot specifica si alte valori pentru constantele din lista.
Exemple:
enum disciplina{informatica=1, fizica, chimie, biologie};informatica, fizica, chimie, biologie au numerele de ordine 1, 2, 3, 4.
Declararea variabilelor si definirea constantelor
Variabile. Declararea variabilelor
Inainte de a utiliza o variabila intr-un program, ea trebuie declarata:
tip nume_variabila [=expresie];
Observatie:Se pot declara mai multe variabile de acelasi tip, separand numele lor prin virgula; pentru declararea de variabile avand tipuri diferite se reia constructia anterioara.
Exemplu:
float x, y, z;unsigned int m, n=100;
Definirea constantelor
Pentru definirea constantelor simbolice se foloseste constructia:#define nume valoare
sau folosind modificatorul const astfel:const tip nume=valoare;
Exemplu:#define nr_pi 3.14;
Structura programelor
Un program C este alcatuit din una sau mai multe functii, functia main fiind prima care se executa si ea nu poate lipsi. Celelalte functii sunt definite de utilizator. Orice astfel de functie este formata din:
Parametrii formali sunt identificatori de variabile pe care urmeaza sa le foloseasca functia atunci cand se va executa. Pentru a comanda executia unei functii, trebuie sa o apelam. Daca functia are parametri formali atunci la apel trebuie sa furnizam valori concrete ale acestora, numiti parametri actuali. O functie poate sa returneze o valoare de un anumit tip (tip_rezultat) sau sa nu returneze nici o valoare, caz in care tip_rezultat este void.
- corp { declaratii; instructiuni }In C exista si functii predefinite, care isi au prototipul (definitia) in fisiere antet (headere). Pentru a putea apela o anumita functie predefinita, trebuie ca la inceputul programului sa scriem o directiva preprocesor: #include < nume_header>.Pentru a include in fisierul sursa al unui program, fisiere header create de utilizator sau alte fisiere sursa folosim include "nume_fisier_creat_de_utilizator".O alta directiva preprocesor care poate fi scrisa la inceputul programului este #define pentru definirea constantelor simbolice.
Exemplu de program C pentru a va face o idee despre cum arata codul unui program si iesirea produsa de program. Acest program nu va fi inteles de incepatori deoarece inca nu au fost prezentate toate instructiunile folosite in acest program.Programul cere utilizatorului sa introduca de la tastatura un sir de numere pana la intalnirea unei valori care tot va fi data de utilizator si va afisa cifra maxima a fiecarui numar. Programul are ca scop prezentarea structurii generale a unuia dintre cele mai simple programe ce poate fi realizat cu ajutorul limbajului C.
#include< stdio.h>#include <conio.h>int main(){long end, nr, val; int uc, max=0;printf("Dati valoarea care va incheia citirea: ");scanf("%d", &end);printf("Dati sirul de valori: \n");do{scanf("%d", &nr);val=nr;while(val!=0){uc=val%10;if(uc>max) max=uc;val=val/10;}printf("Cifra maxima a valorii %ld este %d\n", nr, max);
max=0;}while(nr!=end);printf("\n\nApasa o tasta pentru a inchide programul...");getch();}
Programul a fost compilat cu MinGW Developer Studio si a produs urmatorul rezultat pentru datele de intrare 345, 234, 678, 900, 100:
Expresii. Instructiunea de atribuire
O expresie contine operanzi (constante, variabile, functii) legati prin operatori specifici limbajului. Cand se evalueaza o expresie se tine cont de prioritatea operatorilor si de asociativitate. In general, asociativitatea se face de la stanga la dreapta.In C, operatorii pot fi impartiti in urmatoarele grupe in ordinea descrescatoare a prioritatii lor:
Grupa
Operatori Semnificatie
1 ( ) [ ] -> . apel de functie, operatori de selectie
3 * / % inmultire, impartire, rest4 + - adunare, scadere5 <<>> deplasare biti la stanga, respectiv la dreapta6 < > <= >= operatori relationali7 == != operatori de egalitate8 & SI pe biti9 ^ SAU exclusiv pe biti10 | SAU pe biti11 && SI logic12 || SAU logic13 ?: operator conditional
14= *= /= %= += -= &= ^= != <<= >>=
atribuire simpla, atribuirea "var op=expresie" echivalenta cu "var=var op expresie"
15 , operator virgula
Pentru grupele 2, 13, 14, asociativitatea este de la dreapta la stanga.Cateva dintre functiile mai des folosite, a caror prototipuri se gasesc in fisierul antet math.h sunt:
Numele functiei Tipul argumentului Semnificatia rezultatuluipow(x, y) x, y de tip double x la puterea yabs(i), fabs(r) int, double valoarea absoluta a argumentuluisqrt(r) Double radical din r (r>=0)sin(r) Double sinusul lui rcos(r) Double cosinusul lui rarctg(r) Double unghiul a carui tangenta este rlog(r) Double logaritm natural din r (r>0)exp(r) Double valoarea functiei exponentiale pentru rceil(r) Real cel mai mic intreg >=rfloor(r) Real cel mai mare intreg <=r
Exemple de expresii in C: m=n=p=10 - m, n, p primesc valoarea 10; este permisa atribuirea multipla, dar nu la
declararea variabilelor.i++ sau ++i - determina cresterea cu 1 a valorii variabilei i; deosebirea apare atunci cand una din cele doua forme este folosita intr-o alta expresie: pentru i++ se evalueaza expresia in cauza si pe urma creste valoarea lui i, iar pentru ++i, mai intai creste valoarea lui i si pe urma se evalueaza expresia.- sunt echivalente i+=1 si i=i+1(a+b)%2==1 - verifica daca unul din numerele naturale a si b este par, iar celalalt impara=a+b, b=a-b, a=a-b - determina interschimbarea valorilor lui a si b si este echivalenta cu secventa aux=a, a=b, b=auxmax=x > y ? x : y - variabila max memoreaza maximul dintre x si y(float)(abs(a) + abs(b))/2 - daca a si b sunt variabile intregi, expresia determina media aritmetica a valorilor absolute ale lui a si b si forteaza conversia rezultatului la tipul float (altfel rezultatul este de tip intreg).s*=3 - se inmulteste cu 3 valoarea lui sa-- - scade cu 1 valoarea lui agetch() - apel de functie necesar pentru citirea unui caracter care nu va fi afisat, prototipul ei gasindu-se in fisierul antet conio.h
Citirea si scrierea datelor
Citirea datelor se poate face cu scanf; prototipul ei se gaseste in stdio.h.int scanf(format, adr_var1, adr_var2, ..., adr_varn);
Functia parcurge succesiunea de caractere introdusa de la tastatura si extrage valorile de citit conform formatului specificat. Valorile citite sunt memorate in ordine in variabilele specificate prin adresa lor. Adresa unei variabile se obtine cu operatorul & care precede identificatorul variabilei.Functia intoarce numarul de valori citite corect.Parametrul format contine specificatori de format, caractere albe si alte caractere. Caracterele albe sunt ignorate, iar celelalte trebuie sa fie prezente la intrare in pozitiile corespunzatoare. Specificatorii de format au sintaxa %[*][lg][l\L] litera_tip
litera_tip
semnificatie
d numar intreg zecimal memorat in variabila de tip intO numar intreg octal memorat in variabila de tip intu numar intreg zecimal memorat in variabila de tipul unsigned intx numar intreg hexazecimal memorat in variabila de tip int
e, f sau g numar real zecimal memorat intr-o variabila de tip floatc caracter (caractere albe prezente la intrare nu se ignora)
ssir de caractere (sirul incepe cu primul caracter care nu este alb si continua pana la primul caracter alb intalnit sau pana la epuizarea dimensiunii lg
d, o, u, x precedate de l determina conversia la tipul longe, f, g precedate de l determina conversia la tipul doublee, f, g precedate de L determina conversia la tipul long double* are semnificatia ca valoarea de la intrare nu va fi atribuita nici uneia dintre variabilele specificateCitirea unui caracter se poate face si cu:int getch(void); sau int getche(void);Functiile intorc codul ASCII al caracterului citit. In cazul lui getch, caracterul tastat nu este afisat.
Exemplu:
Fie declaratiile de variabile:int x; unsigned y; unsigned long z; double v; char w;
Daca se introduc de la tastatura valorile -2 100 5000000 -4.35 a, atunci apeland functia:scanf("%d%u%lu%lf%c", &x, &y, &z, &v, &w);variabilele x, y, z, w vor avea valorile -2, 100, 5000000, -4.35, caracterul spatiu. Pentru aceleasi valori introduse de la tastatura, in urma apelului:scanf("%d %u %lu %lf %c", &x, &y, &z, &v, &w);
variabilele x, y, z, w vor avea valorile -2, 100, 5000000, -4.35, 'a'.
Scrierea datelor se poate face cu: int printf(format, expresie1, expresie2, ..., expresien);
Se evalueaza expresiile si se scriu in ordine valorile acestora in forma specificata de parametrul format.In caz de succes, functia returneaza numarul de caractere afisate.Parametrul format contine specificatori de format si alte caractere. Pentru fiecare expresie din lista trebuie sa existe un specificator de format. Celelalte caractere vor fi afisate pe ecran in pozitiile corespunzatoare.Specificatorii de format au sintaxa %[+ sau - ][lg][.prec][#][l\L]litera_tip
litera_tip
semnificatie
d expresia se converteste din tipul int si se afiseaza in baza 10o expresia se converteste din tipul int si se afiseaza in baza 8
uexpresia se converteste din tipul unsigned int si se afiseaza in baza 10
x, Xexpresia se converteste din tipul int si se afiseaza in baza 16 (in cazul lui x literele pentru 10-15 sunt mici, iar in cazul lui X sunt mari
fexpresia se converteste din tipul float si se afiseaza parte_intreaga.parte_zecimala
e, Eexpresia se converteste din tipul float si se afiseaza in format exponential parte_intreaga.parte_zecimala(+ sau -)exponent sau cu E
gse aplica una din conversiile corespunzatoare literei f sau e (cea care se reprezinta cu numar minim de caractere).
cexpresia are ca valoare codul ASCII al unui caracter si se afiseaza caracterul corespunzator
s expresia este un sir de caractere care va fi afisat pe ecran
d, o, u, x, X precedate de l determina conversia din tipul long inte, E, f, g precedate de l determina conversia din tipul doublee, E, f, g precedate de L determina conversia din tipul long double+ indica afisarea semnului expresiei- indica aliniere la stanga (implicit alinierea se face la dreapta)lg reprezinta numarul minim de caractere pe care se realizeaza afisareaprec indica numarul de zecimale sau numarul de caractere din sir care se afiseaza# afiseaza baza in fata numarului
Afisarea caracterelor se poate face si cu:int putchar(int c);
Afisarea sirurilor de caractere se poate face si cu:int puts(char *s)
Exemplu de program:
#include#include
int main(void){char car='d';double r=98.7654321;
int i=20, j;printf("caracterul %c are codul ASCII %d;\n", car, car); // afiseaza codul ASCII al caracterului 'd'
j=2*i--; //este echivalent cu j=2*20 (dupa ce se va face aceasta atribuire i va scadea cu 1 deoarece este decrementat:i--)
printf("j=%d i=%d", j, i); // afiseaza valorile obtinute pentru j si i
getch(); // asteapta sa se introduca un caracter care nu va fi afisat pe ecran pentru a putea inchide programul
return 0;}
}
Programul va afisa:
Structuri de control
In C exista mai multe tipuri de structuri de control: structura alternativa, structura repetitiva cu test initial, structura repetitiva cu test final, structura repetitiva cu numar cunoscut de pasi.Pentru inceput vom incepe cu structura alternativa:
if (expresie)instructiune1;elseinstructiune2;
Efect: Se evalueaza expresia; daca este diferita de 0 se executa instructiune 1, altfel se executa instructiune 2.
Structura alternativa mai poate fi scrisa si cu ajutorul functiei switch():
Observatie:Expresie 1, 2, ...n, sunt expresii constante.
Efect:Se evalueaza expresie; daca valoarea ei coincide cu una din valorile expresiilor specificate se executa secventa corespunzatoare si toate secventele care urmeaza pana la intalnirea instructiunii break sau pana la intalnirea '}'; altfel se executa default: instructiune;
Observatie:expresie1, expresie2, ..., expresien pot simboliza orice instructiune a limbajului, inclusiv instructiunea compusa sau instructiunea vida.
Exemple de structuri alternative:
- structura alternativa ce determina minimul dintre doua valori reale x si y:
varianta 1:
min=x; // minimul dintre cele doua valori initial este xif (min>y) // daca minimul este mai mare decat y (x > y)min=y; // minimul este y; altfel minimul ramanane x
varianta 2:
if(x < y)min=x;else min=y;
- catul impartirii intregi dintre 2 valori intregi a si b, daca este posibil:
if(b!=0)printf("a/b = %d", a/b);else printf("impartire la 0!");
O alta structura de control este structura repetitiva. Aceasta este de mai multe feluri: structura repetitiva cu test initial, structura repetitiva cu test final si structura repetitiva cu numar cunoscut de pasi.
Structura repetitiva cu test initial:
while (expresie)instructiune
Efect:Cat timp valoarea expresiei este diferita de 0 se executa instructiune.
Structura repetitiva cu test final:
do instructiune while (expresie);
Efect:Se executa instructiune cat timp valoarea expresiei este diferita de 0.
Structura repetitiva cu numar cunoscut de pasi:
for (expresie_init; expresie_test; expresie_modif)instructiune
Efect:
1. se evalueaza expresie_init;2. se evalueaza expresie_test;3. daca expresie_test are valoarea 0, se termina instructiune for; in caz contrar:- se executa instructiune;- se evalueaza expresie_modif;- se revine la 2.
- cel mai mare divizor comun (cmmdc) al numerelor intregi a si b:
r=a%b;while(r!=0) do{a=b;b=r;r=a%b;}cmmdc=b;
Exemplu de structura repetitiva cu test final:
- suma cifrelor unui numar natural n
suma=0;m=n;
/* pentru a pastra valoarea lui n se foloseste m in structura repetitiva */
do{suma+=m%10; // prin m%10 se extrage ultima cifra a numarului mm=m/10;}while(m!=0);
Exemplu de structura repetitiva cu numar cunoscut de pasi:
- suma primelor n numere pare ( n numar natural diferit de 0):
s=0;for (i=0; i < n; i++)s=s+2*i;
Program propus spre rezolvare:
1.La un concurs au fost inscrisi un numar de participanti. Stiind numarul de participanti care s-au prezentat si numarul de participanti care au castigat concursul, sa se realizeze un program care va cere sa se introduca de la tastatura numarul de participanti inscrisi, numarul de participanti care s-au prezentat si numarul de participanti care au trecut concursul. Apoi programul va afisa numarul de participanti care nu s-au prezentat la concurs si procentajul de participanti care au trecut concursul.
#include <stdio.h>#include <conio.h>
int main(void){int nr_participanti, nr_prezenti, nr_promovati;printf("Introduceti numarul de participanti: ");scanf("%d", &nr_participanti);printf("Numarul de participanti prezenti: ");scanf("%d", &nr_prezenti);printf("Numarul de participanti ce au trecut concursul: ");scanf("%d", &nr_promovati);printf("\n\n\nNumarul de participanti care nu s-au prezentat la concurs este %d\n\n", nr_participanti - nr_prezenti);printf("Procentajul de participanti ce au trecut concursul este %.2f \n\n", (float)nr_promovati/(nr_participanti * 100));printf("Apasa o tasta pentru a inchide...");getch();return 0;}
Dupa compilarea programului in MinGW Developer Studio si introducerea datelor de intrare obtinem:
Notiunea de subprogram. Structura unei functii
Un subprogram este un ansamblu alcatuit din tipuri de date, variabile si instructiuni care rezolva o anumita sarcina si care poate fi utilizat doar daca este apelat de un program sau de un alt subprogram.In limbajul C, subprogramele sunt de tip functie. Exista trei elemente implicate in utlizarea unui subprogram:- Prototipul subprogramului- Definitia subprogramului- Apelul subprogramuluiSubprogramul nu este o entitate independenta. El trebuie "asamblat" in interiorul programului, trebuie stabilite legaturi intre modulul apelat si cel apelant. In procesul de prelucrare dintr-un subprogram, sunt necesare date care trebuie prelucrate (date de intrare) pentru obtinerea rezultatului dorit sau date care trebuie prelucrate in vederea modificarii valorilor acestora (date de iesire). In concluzie, functiile comunica prin intermediul argumentelor (a parametrlor); ele primesc ca parametri (argumente) datele de intrare, efectueaza prelucrarile descrise in corpul functiei asupra acestora si pot returna o valoare (rezultatul, datele de iesire). Executia programului incepe cu functia principala, numita main. Functiile pot fi descrise in cadrul aceluiasi fisier, sau in fisiere diferite, care sunt testate si compilate separat, asamblarea lor ralizandu-se cu
Prima linie reprezinta antetul functiei, in care se indica: tipul functiei, numele functiei si lista declaratiilor rparametrilor formali. Antetul specifica inceputul subprogramului. La fel ca un operand sau o expresie, o functie are un tip, care precizeaza tipul valorii returnate de functie in functia apelanta. Daca functia nu intoarce nici o valoare, in locul tip_valoare_returnata se specifica void. Daca tip_valoare_returnata lipseste, se considera, implicit, ca acesta esteint.Nume_functie este un identificator.Lista_declaratii_parametri_formali consta intr-o enumerare care contine tipul si identificatorul fiecarui parametru de intrare, despartite prin virgula. Tipul unui parametru poate fi oricare, chiar si tipul pointer. Daca lista parametrilor formali este vida, in antet, dupa numele functiei, apar doar parantezele (), sau(void).
Corpul functiei este un bloc, care implementeaza algoritmul de calcul folosit de catre functie. La fel ca orice bloc C, el este incapsulat intr-o instructiune compusa, delimitat de caracterele {......}, si este alcatuit din doua parti: partea declarativa si partea executabila, care contine instructiunile prin care sunt descrise actiunile realizate de functie. In corpul functiei apar (in orice ordine) declaratii pentru variabilele locale si instructiuni. Daca functia intoarce o valoare, se foloseste instructiunea return valoare.In limbajul C, se utilizeaza declaratii si definitii de functii.
Orice functie trebuie declarata si definitaDeclaratia contine antetul functiei si informeaza compilatorul asupra tipului, numelui functiei si a listei parametrilor formali (in care se poate indica doar tipul parametrilor formali, nu si numele acestora). Declaratiile de functii se numesc prototipuri, si sunt constituite din antetul functiei, din care pot lipsi numele parametrilor formali.
Definitia contine antetul functiei si corpul acesteia. Nu este admisa definirea unei functii in corpul altei functii.
Apelul si prototipul functiilor
O functie poate fi apelata printr-o constructie urmata de punct si virgula, numita instructiune de apel, de forma:nume_functie(lista_parametri_efectivi);
Parametrii efectivi trebuie sa corespunda cu cei formali ca ordine si tip. La apel, se atribuie parametrilor formali valorile parametrilor efectivi, dupa care se executa
instructiunile din corpul functiei. La revenirea din functie, controlul este redat functiei apelante, si executia continua cu instructiunea urmatoare instructiunii de apel, dn functia apelanta. O alta posibilitate de a apela o functie este aceea in care apelul functiei constituie operandul unei expresii. Acest lucru este posibil doar in cazul in care functia returneaza o valoare, folosita in calculul expresiei.
Parametrii care se gasesc in antetul unei functii se numesc parametri formali. Atunci cand scriem o functie nu se cunoaste valoarea propriu-zisa a parametrilor. Functia trebuie sa intoarca rezultatul corect, oricare ar fi valoarea lor. De aceea ei se numesc formali. Parametrii formali se concretizeaza la executie prin apelurile functiei.
Parametrii folositi la apelul unei functii sunt parametri efectivi, ale caror valori sunt cunoscute. Aceste valori vor fi atribuite parametrilor formali, la executie. Utilizarea parametrilor formali la implementarea functiilor si atribuirea de valori concrete pentru ei, la executie, reprezinta un prim nivel de abstractizare in programare.
Intre parametrii formali si cei efectivi trebuie sa existe a anumita concordanta, descrisa de urmatoarele reguli:
1. Numarul parametrilor formali trebuie sa coincida cu numarul parametrilor efectivi.2. Tipul parametrilor formali trebuie sa coincida cu tipul parametrilor efectivi sau tipul parametrilor efectivi sa poata fi convertit implicit catre tipul parametrilor formali (ca in cazul operatiei de atribuire).3. Nu este obligatoriu ca numele parametrilor formali sa coincida cu numele parametrilor efectivi.
Exemplu:Programul urmator contine o functie care returneaza maximul dintre doua numere intregi:
Dupa fiecare apel al functiei se tipareste maximul dintre valorile parametrilor efectivi.Variabilele declarate in interiorul unei functii, cat si parametrii formali ai acesteia nu pot fi accesati decat in interiorul acesteia. Aceste variabile sunt numitevariabile locale si nu pot fi accesate din alte functii. Domeniul de vizibilitate a unei variabile este portiunea de cod la a carei executie variabila respectiva este accesibila. Deci, domeniul de vizibilitate a unei variabile locale este functia in care ea a fost definita.Daca in interiorul unei functii exista instructiuni compuse (blocuri) care contin declaratii de variabile, aceste variabile nu sunt vizible in afara blocului.Prototipurile functiilor din biblioteci(predefinite) se gasesc in headere. Utilizarea unei astfel de functii impune doar includerea in program a headerului asociat, cu ajutorul directivei preprocesor #include.Programatorul isi poate crea propriile headere, care sa contina declaratii de functii, tipuri globale, macrodefinitii, etc.Similar cu declararea de variabile, domeniul de vizibilitate a unei functii este:- fisierul sursa, daca declaratia functiei apare in afara oricarei functii (la nivel global);- functia sau blocul in care apare declaratia
Transferul parametrilor unei functii
Functiile comunica intre ele prin intermediul parametrilor si a variabilelor globale. Exista urmatoarele moduri de transfer a parametrilor catre functiile apelate:- transfer prin valoare;- transfer prin pointeri- transfer prin referinta
Transferul parametrilor prin valoare
De la modulul apelant catre modulul apelat, prin apel, se transmit valorile parametrilor efectivi. Aceste valori vor fi atribuite, la apel, parametrilor formali. Deci, procedeul da transmitere a parametrilor prin valoare consta in incarcarea valorii parametrilor efectivi in zona de memorie a parametrilor formali (n stiva). La apelul unei functii, parametrii reali trebuie sa corespunda - ca ordine si tip - cu cei formali.Fiecare argument efectiv utilizat la apelul functiei este evaluat, iar valoarea este atribuita parametrului formal corespunzator. In interiorul functiei, o copie locala a acestei valori va fi memorata in parametrul formal. O modificare a valorii paramaetrului formal in interiorul functiei (printr-o operatie din corpul functiei), nu va modifica valoarea parametrului efectiv, ci doar valoarea parametrului formal, deci a copiei locale a parametrului efectiv. Faptul ca variabila din modulul apelant (parametrul efectiv) si parametrul formal sunt obiecte distincte, poate constitui un mijloc util de protectie: valoarea parametrului formal poate fi modificata (alterata) prin prelucrarile din corpul functiei. Valoarea parametrului efectiv din functia apelanta, ramane nemodificata (la revenirea in modulul apelant, continutul variabilelor memorate in stiva se pierde).In cazul transmiterii parametrilor prin valoare, parametrii efectivi pot fi chiar expresii. Acestea sunt evaluate, iar valoarea lor va initializa, la apel, parametrii formali.Transferul valorii este insotit de eventuale conversii de tip. Aceste conversii sunt realizate automat de compilator, in urma verificarii apelului de functie, pe baza informatiilor despre functie, sau sunt conversii explcite, specificate de programator, prin operatorul "cast".De fiecare data cand o functie transmite argumente unei functii apelate, este transmisa, de fapt, o copie a parametrilor efectivi. In acest mod, daca valoarea parametrilor formali (initializati cu valorile parametrilor efectivi) se modifica in interiorul functiei apelate, valorile parametrilor efectivi din functia apelanta nu vor fi afectate.
Transferul parametrilor prin pointeri
In unele cazuri, parametrii transmisi unei functii pot fi pointeri (variabile care contin adrese). In aceste cazuri, parametrii formali ai functiei apelate vor fi initializati cu valorile parametrilor efectivi, deci cu valorile unor adrese. Astfel, functia
apelata poate modifica continutul locatiilor spre care pointeaza argumentele (pointerii).
Transferul parametrilor prin referinta
In acest mod de transmitere a parametrilor, unui parametru formal i se poate asocia (atribui) chiar obiectul parametrului efectiv. Astfel, parametrul efectiv poate fi modificat direct prin operatiile din corpul functiei apelate.In cazul transmiterii prin referinta, parametrii efectivi trebuie sa fie referinte la variabile iar subprogramul retine in stiva, adresa variabilei.Comparand cele trei moduri de transmitere a parametrilor catre o functie, se poate observa:1. La apelul prin valoare transferul datelor este unidirectional, adica valorile se transfera numai de la functia apelanta catre cea apelata. La apelul prin referinta transferul datelor este bidirectional, deoarece o modificare a parametrilor formali determina modifiacarea parametrilor efectivi, care sunt sinonime (au nume diferite, dar refera aceeasi locatie de memrie).2. La transmiterea parametrilor prin valoare, ca parametrii efectivi pot apare expresii sau nume de variabile. La transmiterea parametrilor prin referinta, ca parametri efectivi nu pot apare expresii, ci doar nume de variabile. La transmiterea parametrilor prin pointeri, ca parametri efectivi pot apare expresii de pointeri.3. Transmiterea paramtrilor unei functii prin referinta este specifica limbajului C++.4. Limbajul C este numit limbajului apelului prin valoare. Apelul poate deveni, insa, apel prin referinta in cazul variabilelor simple, folosind pointeri, sau in cazul in care parametrul efectiv este un tablou.
Transferul parametrilor catre functia main()
In situatiile in care se doreste transmiterea unor informatii (optiuni, date initiale, etc.) catre un program, la lansarea in executie a acestuia, este necesara definirea unor parametri catre functia main. Se utilizeaza trei parametri speciali: argc, argv si env. Trebuie inclus headerul stdarg.h.Prototipul functiei main cu parametri in linia de comanda este:main (int argc, char *argv[], char *env[])
Daca nu se lucreaza cu un mediu de programare integrat, argumentele transmise catre functia main trebuie editate (specificate) in linia de comanda prin care se
lanseaza in executie programul respectiv. Linia de comanda tastata la lansarea in executie a programului este formata din grupuri de caractere delimitate de spatiu sau tab. Fiecare grup este memorat intr-un sir de caractere. Daca se lucreaza cu un mediu integrat (de exemplu, BorlandC), selectia comenzii Arguments... din meniul Run determina afisarea unei casete de dialog in care utilizatorul poate introduce argumentele functiei main.- Adresele de inceput ale acestor siruri sunt memorate in tabloul de pointeri argv[], in ordinea in care apar in linia de comanda (argv[0] memoreaza adresa sirului care constituie numele programului, argv[1] - adresa primului argument, etc.);- Parametrul intreg argc memoreaza numarul de elemente din tabloul argv(argc>=1);- Parametrul env[] este un tablou de pointeri catre siruri de caractere care pot specifica parametri ai sistemului de operare.
Functia main poate returna o valoare intreaga. In acest caz in antetul functiei se specifica la tipul valorii returnate int, sau nu se specifica nimic (implicit, tipul este int), iar in corpul functiei apare instructiunea return valoare_intreaga. Numarul returnat este transferat sistemului de operare (programul apelant) si poate fi tratat ca un cod de eroare sau de succes al incheierii executiei programului.
Tablouri ca parametri
In limbajul C, cazul parametrilor tablou constituie o exceptie de la regula transferului parametrilor prin valoare. Numele unui tablou reprezinta, de fapt, adresa tabloului, deci a primului element din tablou.
Exemplu:Program care afla suma elementelor unui tablou unidimensional (vector) cu maxim 100 elemente intregi.Se vor scrie doua functii: de citire a elementelor tabloului si de calcul al sumei.
#include <stdio.h>#include <conio.h>
int suma(int a[], int dimensiune_vector_a){int s=a[0], i;for(i=1; i < dimensiune_vector_a; i++)
s+=a[i];return s;}
void citire(int v[], int dimensiune_vector_v){int i;for(i=0; i < dimensiune_vector_v; i++){printf("\nelementul %d: ", i+1);scanf("%d", &v[i]);}}
int main(){int v[100], nr_elemente;do{printf("Dati numarul de elemente ce vor fi citite (n>0 si n<=100): ");scanf("%d", &nr_elemente);}while(nr_elemente<=0 || nr_elemente>100);citire(v, nr_elemente);printf("\n\nSuma elementelor vectorului este %d.", suma(v, nr_elemente));printf("\n\nApasa o tasta...");getch();return 0;}
Pentru tablourile unidimensionale, la apel, nu trebuie specificat numarul de elemente. Dimensiunea tabloului trebuie sa fie cunoscuta in functia care il primeste ca parametru. De obicei, dimensiunea tabloului se transfera ca parametru separat (nr_elem).Pentru tablourile multidimensionale, pentru ca elementele tabloului sa poata fi referite in functie, compilatorul trebuie informat asupra modului de organizare a tabloului.Pentru tablourile bidimensionale (vectori de vectori), poate fi omisa doar precizarea numarului de linii, deoarece pentru a adresa elementul mat[i][j], undemat este un tablou bidimensional cu tipul de baza tip, compilatorul utilizeaza relatia: &mat[i][j] = &mat + (i * N + j) * sizeof(tip), in care N reprezinta numarul de coloane, iar tip reprezinta tipul tabloului.
Functii cu numar variabil de parametri
In limbajul C se pot defini functii cu numar variabi de parametri. Parametrii care trebuie sa fie prezenti la orice apel al functiei se numesc parametri ficsi, ceilalti se numesc parametri variabili. Parametrii ficsi preced parametrii variabili. Prezenta parametrilor variabili se indica in antetul functiei prin trei punctecare se scriu dupa
ultimul parametru fix al functiei.
De exemplu, fie antetul functiei numite exemplu:
void exemplu (int n, double a, ...)
Functia exemplu are doi parametri ficsi (n si a) si parametri variabili, pentru care nu se precizeaza in prealabil numarul si tipul; numarul si tipul parametrilor variabili difera de la un apel la altul.Functiile cu numar variabil de parametri sunt, de obicei, functiile de biblioteca (ex: printf, scanf) si se definesc folosind niste macrouri speciale care permit accesul la parametrii variabili si se gasesc in headerul starg.h
Functii predefinite
Orice mediu de programare este prevazut cu una sau mai multe biblioteci de functii predefinite. Orice biblioteca este formata din:- fisierele header (contine prototipurile functiilor, declaratiile de variabile);- biblioteca (arhiva) propriu-zisa (contine definitii de functii).
Pentru ca functiile predefinite sa poata fi utilizate, fisierele header in care se gasesc prototipurile acestora trebuie incluse in functia (programul) apelant printr-o directiva preprocesor (exemplu #include <stdio.h> ). Deasemenea, utilizatorul isi poate crea propriile headere. Pentru a putea utiliza functiile proprii, el trebuie sa includa aceste headere in programul apelant (exemplu #include "my_header.h").
Pentru functiile predefinite, au fost create fisiere header orientate pe anumite tipuri de aplicatii. De exemplu, functiile matematice se gasesc in headerul<math.h>. Headerul <stdlib.h> contine functii standard. Headerul <values.h> defineste o serie de constante simbolice (exemplu MAXINT, MAXLONG) care reprezinta, in principal, valorile maxime si minime ale diferitelor tipuri de date.
Functii matematice
- Au prototipul in headerul
<math.h>
Functii aritmetice:
Valori absolute
int abs( int x);Returneaza un intreg care reprezinta valoarea absoluta a argumentului.
long int labs( long int x );Analog cu functia abs, cu deosebirea ca argumentul si valoarea returnata sunt de tip long int .
double fabs ( double x);Returneaza un real care reprezinta valoarea absoluta a argumentului real.
Functii de rotunjire
double floor( double x);Returneaza un real care reprezinta cel mai apropiat numar, fara zecimale, mai mic sau egal cu x (retunjire prin lipsa).
double ceil( double x);Returneaza un real care reprezinta cel mai apropiat numar, fara zecimale, mai mare sau egal cu x (rotunjire prin adaos).
Functii trigonometrice
double sin (double x)Returneaza valoarea lui sin(x), unde x este dat in radiani. Numarul real returnat se afla in intervalul [-1, 1].
double cos (double x)Returneaza valoarea lui cos(x), unde x este dat in radiani. Numarul real returnat se
afla in intervalul [-1, 1].
double tan( double x)Returneaza valoarea lui tg(x), unde x este dat in radiani.
Functii trigonometrice inverese
double asinReturneaza valoarea lui arcsin(x), unde x se afla in intervalul [-1, 1]. Numarul real returnat (in radiani) se afla in intervalul [-pi/2, pi/2].
double acos( double x)Returneaza valoarea lui arccos(x), unde x se afla in intervalul [-1, 1]. Numarul real returnat se afla in intervalul [0, pi].
double atan(double x)Returneaza valoarea lui arctg(x), unde x este dat in radiani. Numarul real returnat se afla in intervalul [0, pi].
double atan2(double y, double x)Returneaza valoarea lui tg(y/x), cu exceptia faptului ca semnele argumentelor x si y permit stabilirea cadranului si x poate fi zero. Valoarea returnata se afla in intervalul [-pi, pi]. Daca x si y sunt coordonatele unui punct in plan, functia returneaza valoarea unghiului format de dreapta care uneste originea axelor carteziene cu punctul, fata de axa absciselor. Functia foloseste, deasemenea, la transformarea coordonatelor carteziene in coordonate polare.
Functii exponentiale logaritmice
double exp (double x)long double exp( long double x)Returneaza valoarea lui e la puterea x.
double ldexp(double a, int b); long double ldexpl(long double a, int b)Returneaza valoarea lui 2 la puterea (a*b).
double frexp(double x, int *y); long double frexp(long double x, int *y)Returneaza valoarea x*2y calculand deasemenea si valoara lui y.Exemplu: Daca x=8, operatia k=frexp(x, y), calculeaza numarul real k, care trebuie inmultit cu 2y pentru a primi rezultatul egal cu x=8, determinandu-l in acelasi timp si pe y (valoarea puterii la care va trebui ridicata cifra 2). Pentru x=8 si k=frexp(x, y) vom obtine urmatoarele rezultate: y=4, k=0,5; adica 0,5=8/(2 la puterea 4).
double log( double x)Returneaza logaritmul natural al argumentului (ln(x)).
double log10( double x)Returneaza logaritmul zecimal al argumentului (lg(x)).
double pow (double baza, double exponent);long double pow(long double baza, long double exponent)Returneaza un real care reprezinta rezultatul ridicarii bazei la exponent (baza la puterea exponent).
double pow10(int x); long double pow101(int x)Returneaza valoarea lui 10 la puterea x.
double fmod(double x, double y); long double fmod(long double x, long double y)Returneaza valoarea restului de la impartirea lui x la y.
double sqrt(double x)Returneaza radacina patrata a argumentului x.
Functii de generare a numerelor aleatoare
Functia randomize. Initializator de generator al numerelor aleatoare.
Prototip: void randomize( void );Initializeaza generatorul de numere aleatoare. Este necesara includerea bibliotecii <stdlib.h>; Se foloseste impreuna cu functia random().
int random(int x)Returneaza o valoare aleatoare in intervalul de la 0 la (x-1); Este necesara includerea bibliotecii <stdlib.h>
int rand( void ) Genereaza un numar aleator in intervalul [0, RAND_MAX]. Este necesara includerea bibliotecii <stdlib.h>; Nu este necesara initializarea.
Functii de clasificare (testare) a caracterelor
Au prototipul in headerul <ctype.h>. Toate aceste functii primesc ca argument un caracter si returneaza un numar intreg care este pozitiv daca argumentul indeplindeste o anumita conditie, sau valoarea zero daca argumentul nu indeplineste conditia.
int isalnum(int c)
Returneaza o valoare intreaga pozitiva daca argumentul este litera sau cifra. Echivalenta cu: isalpha(c) || isdigit(c).
int isalpha(int c)Testeaza daca argumentul este litera mare sau mica. Echivalenta cu isupper(c) || islower(c).
int iscntrl(int c)Testeaza daca argumentul este caracter de control (neimprimabl).
int isdigit(int c)Testeaza daca argumentul este cifra hexagesimala(0-9, a-f, A-F).
int islower(int c)Testeaza daca argumentul este litera mica.
int isupper(int c)
Testeaza daca argumentul este litera mare.
int ispunct(int c)Testeaza daca argumentul este caracter de punctuatie (caracter imprimabil, dar nu litera sau spatiu).
int ispace(int c)Testeaza daca argumentul este spatiu alb (' ', '\n', '\t', '\v', '\r')
int isprint(int c)Testeaza daca argumentul este caracter imprimabil, inclusiv blancul.
Functii de conversie a caracterelor - au prototipul in headerul <ctype.h>
int tolower(int c)Functia schimba caracterul primit ca argument din litera mare, in litera mica si returneaza codul ASCII al literei mici. Daca argumentul nu este litera mare, codul returnat este chiar codul argumentului.
int toupper(int c)Functia schimba caracterul primit ca argument din litera mica, in litera mare si returneaza codul acesteia. Daca argumentul nu este litera mica, codul returnat este chiar codul argumentului.
Functii de conversie din sir in numar ( de citire a unui numar dintr-un sir)
- Au prototipul in headerul <stdlib.h>
long int atol(const char *npr)Funtia converteste sirul transmis ca argument (spre care pointeaza npr) intr-un numar cu semn, care este returnat ca o valoare de tipul long int. Sirul poate contine caracterele '+' sau '-'. Se considera ca numarul este in baza 10 si functia nu semnalizeaza eventualele erori de depasire care pot apare din conversia din sir in numar.
int atoi(const char *sir)
Converteste sirul spre care pointeaza sir intr-un numar intreg.
double atof(const char *sir)Functia converteste sirul transmis ca argument intr-un numar real cu semn (returneaza valoare de tipul double). In secventa de cifre din sir poate apare litera 'e' sau 'E' (exponentul), urmata de caracterul '+' sau '-' si o alta secventa de cifre. Functia nu semnalizeaza eventualele erori de depasire ce pot sa apara.
Functii folosite la prelucrarea sirurilor de caractere - au prototipul in headerul <string.h>
int strcmp(const char *S1, const char *S2)Compara doua siruri (S1 si S2). Returneaza valoare nula, daca sirurile sunt identice, sau o valoare diferita de zero, in caz ca sirurile nu coincid. Dupa executarea functiei strcmp(), va fi intoarsa o valoare intreaga care va fi: ma mica ca 0 daca S1 < S2; mai mare ca 0 daca S1 > S2; egala cu 0 daca S1==S2; (comparatia celor doua siruri se realizeaza in sens lexicographic).
int strcmp(const char *S1, const char *S2)Compara doua siruri fara a face diferenta intre litere mari si litere mici.
int strncmp(const char *S1, const char *S2, size_t k)Compara primele k caractere din cele doua siruri, furnizand un rezultat la fel ca si functia strcmp().
int strncmpi(const char *S1, const char *S2, size_t k)Compara un numar de k caractere, incepand cu primul, din cele doua siruri de caractere fara a face diferenta intre caracterele minuscule si cele majuscule.
size_t strlen(const char *S)Determina lungimea sirului de caractere S si returneaza o valoare de tip intreg egala cu numarul de caractere ce se afla in sir.
char *strcpy(char *S1, const char *S2)Copie sirul S2 in sirul S1; sirul S1 isi va pierde valoarea initiala si va avea valoarea noua din S2 iar S2 va ramane neschimbat.
size_t strcspn(const char *S1, const char *S2)Determina pozitia caracterului din sirul S1 care a fost intalnit primul in sirul S2. Returneaza o valoare de tip intreg egala cu pozitia acestui caracter in sir.
size_t strspn(const char *S1, const char *S2)Determina pozitia caracterului din sirul S1 incepand cu care S1 difera de S2. Returneaza o valoare de tip intreg egala cu pozitia acestui caracter.
char *strdup(const char *S)Dubleaza sirul de caractere S. In caz de succes functia strdup() returneaza ca valoare indicatorul adresei de memorie ce contine sirul dublat si returneaza valoare nula in caz de eroare. Functia strdup(S) face o copie a sirului S, obtinand spatiu prin apelul functiei malloc. Dupa folosirea sirului dublat programatorul trebuie sa elibereze memoria alocata pentru el. Functia free() elibereaza memoria ocupata de sirul dublat.
char *strlwr(char *S)Transforma toate caracterele din sirul S in echivalentul lor minuscule. Ca parametru functia foloseste o variabila de tip sir de caractere. Daca sirul contine caractere majuscule, ele se vor transforma in echivalentul lor minuscule.
char *strupr(char *S)Transforma toate caracterele litere mici din sir in majuscule.
char *strupr(char *S)Transforma toate caracterele litere mici din sir in majuscule.
char *strncat(char *dest, const char *sursa, size_t k) Adauga un numar de k caractere de la inceputul sirului sursa la sfarsitul sirului destinatie.
char *strncpy(char *dest, const char *sursa, size_t n)Copie un numar de n caractere din sirul sursa la inceputul sirului destinatie. Daca sirul destinatie va avea lungimea mai mare ca n, atunci rezultatul va avea inceputul egal cu caracterele copiate, iar sfarsitul initial.
char *strset(char *s, int ch, size_t n)Copie caracterul ch pe primele n pozitii din sirul *s. Daca n>strlen(s), atunci n va deveni egal cu strlen(s). Functia returneaza o valoare de tip sir de caractere, care va fi retinuta in sirul destinatie.
char *strrev(char *s)Inverseaza sirul de caractere s, fara a lua in consideratie caracterul null.
char *strstr(const char *s1, const char *s2)Determina daca sirul s2 este continut in sirul s1. Functia returneaza un indicator la caracterul din s1 incepand cu care a fost gasit in sirul s2. Daca s2 nu este subsir al lui s1, functia returneaza valoarea null.
char *strchr(const char *S, int c)Cauta prima aparitie a caracterului c in sirul S. In caz de succes functia returneaza un pointer catre acesta. In caz de eroare (daca asa caracter nu exista in sirul S) functia returneaza valoarea NULL.
char *strpbrk(const char *s1, const char *s2)Determina in sirul s1 primul caracter ce exista si in sirul s2. In caz de succes functia returneaza un pointer catre primul caracter din s1 ce se gaseste si in s2.
char *strrchr(const char *s, int c)Determina ultima aparitie a caracterului c in sirul s. In caz de succes functia returneaza un pointer catre ultimul caracter din s identic cu caracterul c.
char *strset(char *s, int ch)Schimba toate caracterele din sirul s cu caracterul c. Rezultatul final se va pastra in sirul s.
Functii de terminare a unui proces (program) - au prototipul in headerul <process.h>
void exit(int status)Termina executia unui program. Codul returnat de terminarea corecta este memorat in constanta simbolica EXIT_SUCCES, iar codul de eroare in EXIT_FAILURE.
void abort()Termina fortat executia unui program.
int system(const char *comanda)Are prototipul in <system.h> si permite executia unei comenzi DOS, specificate prin sirul de caractere transmis ca parametru.
Functii de intrare/iesire (prototip in <stdio.h>)
Streamurile (fluxurle de date) implicite sunt: stdin(fisierul, dispozitivul standard de intrare), stdout(fisierul, dispozitivul standard de iesire), stderr(fisier standard pentru erori), stdprn(fisier standard pentru imprimanta) si stdaux(dispozitivul auxiliar standard). De cate ori este executat un program, streamurile implicite sunt deschise automat de catre sistem. In headerul <stdio.h> sunt definite si constantele NULL (definita ca 0) si EOF(sfarsit de fisier, definita ca -1, CTRL/Z).
int getchar(void)Citeste un caracter (cu ecou) din fisierul standard de intrare (tastatura).
int putchar(int c)Afiseaza caracterul primit ca argument in fisierul standard de iesire (monitor).
char *gets(char *sir)Citeste un sir de caractere din fisierul standard de intrare (pana la primul blank sau linie noua). Returneaza pointerul catre sirul citit.
int puts (const char *sir)Afiseaza sirul argument in fisierul standard de iesire si adauga terminatorul de sir. Returneaza codul ultimului caracter al sirului (caracterul care precede NULL) sau -1 in caz de eroare.
int printf (const char *format, ...)Functia permite scrierea in fisierul standard de iesire (pe monitor) a datelor, intr-un anumit format. Functia returneaza numarul de octeti (caractere) afisati, sau -1 in cazul unei erori.1. Parametrul fix al functiei contine:- Succesiuni de caractere afisate ca atare;- Specificatori de format care definesc conversiile ce vor fi realizate asupra datelor de iesire, din formatul intern, in cel extern (de afisare).2. Parametrii variabili ai functiei sunt expresii. Valorile obtinute in urma evaluarii acestora sunt afisate corespunzator specificatorilor de format care apar in parametrul fix. De obicei, parametrul fix contine atat specificatori de format, cat si alte caractere. Numarul si tipul parametrilor variabili trebuie sa corespunda specificatorului de format.
Un specificator de format care apare in parametrul fix poate avea urmatoarea forma:%[-|c|][sir_cifre_eventual_punct_zecimal] una_sau_doua_litere- Implicit, datele se cadreaza (aliniaza) la dreapta campului in care se scriu. Prezenta caracterului '-' determina cadrarea la stanga.Sirul de cifre defineste dimensiunea campului in care se scrie data. Daca scrierea datei necesita un camp de lungime mai mare, lungimea indicata in specificator este ignorata. Daca scrierea datei necesita un camp de lungime mai mica, data se va scrie in camp, cadrata la dreapta sau la stanga (daca apare semnul '-'), completandu-se restul campului cu caracterele nesemnificative implicite, adica spatii. Sirul de cifre aflate dupa punct definesc precizia (numarul de zecimale cu care este afisat un numar real - implicit sunt 6 zecimale).Literele definesc tipul conversiei aplicat datei afisate:c - Afiseaza un caracters - Afiseaza un sir de caractered - Afiseaza date intregi; cele negative sunt precedate de semnul '-'.o - Afiseaza date de tip int sau unsigned int in octalx sau X - Afiseaza date de tip int sau unsigned int in hexagesimalf - Afiseaza date de tip float sau double in forma:parte_intreaga.parte_fractionara exponentExponentul incepe cu e sau E si defineste o putere a lui zece care inmultita cu restul
numarului da valoarea reala a acestuia.g sau G - Afiseaza o data reala fie ca in cazul specificatorului terminat cu f, fie ca in cazul specificatorului terminat cu e. Criteriul de afisare se alege automat, astfel incat afisarea sa ocupe un numar minim de pozitii in campul de afisare.l - Precede una din literele d, o, x, X, u. La afisare se fac conversii din tipul long sau unsigned long.L - precede una din literele f, e, E, g, G. La afisare se fac conversii din tipul long double.
int scanf(const char *format, ...)
Functia citeste din fisierul standard de intrare valorile unor variabile si le depune in memorie, la adresele specificate. Functia returneaza numarul campurilor citite corect.1. Parametrul fix al functiei contine:Specificatorii de format care definesc conversiile aplicate datelor de intrare, din formatul extern, in cel intern (in care sunt memorate). Specificatorii de format sunt asemanatori celor folositi de functia printf: c, s, d, o, x sau X, u, f, l, L.2.Parametrii variabili reprezinta o lista de adrese ale variabilelor care vor fi citite, deci in aceasta lista, numele unei variabile simple va fi precedat de operatorul de adresa &.
int sprintf(char *sir_cu_format, const char *format, ...)Functia permite scrierea unor date in sirul transmis ca prim argument, intr-un anumit format. Valoarea returnata reprezinta numarul de octeti (caractere) scrise in sir, sau -1 in cazul unei erori.
int sscanf(char *sir_cu_format, const char *format, ...)Functia citeste valorile unor variabile din sirul transmis ca prim argument si le depune in memorie, la adresele specificate. Returneaza numarul campurilor citite corect.
Exemplu de program:Programul cere utilizatorului sa introduca de la tastatura un sir de numere pana la intalnirea unei valori ce este ceruta la inceputul programului si apoi afiseaza numerele care sunt egale cu patratul sumei cifrelor.
long patrat_suma_cifre(long nr){int s=0;while(nr!=0){s+=(nr%10);nr/=10;}s=pow(s, 2);return s;}
int main(){long end, nr, v[100];int ok=0, i=0, j;printf("Valoarea care va incheia citirea numerelor: ");scanf("%d", &end);do{printf("\nnr = ");scanf("%ld", &nr);if(nr==patrat_suma_cifre(nr)){v[i++]=nr;ok=1;}}while(nr!=end);if(ok==1){printf("Numerele care sunt egale cu patratul sumei cifrelor sunt:\n");for(j=0; j < i; j++)printf("\n%ld", v[j]);}elseprintf("Nu exista numere care sa fie egale cu patratul sumei cifrelor!");printf("\n\nApasa o tasta pentru a inchide...");getch();
return 0;}
Tabloul de memorie. Tablouri unidimensionale
Tabloul de memorie (array) este o structura de date interna formata dintr-o multime ordonata de elemente, ordonarea facandu-se cu un ansamblu de indici.In functie de numarul indicilor utilizati pentru a referi elementele tabloului, putem intalni tablouri unidimensionale (vectorii) sau multidimensionale (matricile sunt tablouri bidimensionale).
Tablouri in C
Modul de declarare:tip nume_tablou[dim_1][dim_2]...[dim_n];
unde: tip reprezinta tipul elementelor tabloului; dim_1, dim_2, ..., dim_n sunt numere intregi sau expresii constante intregi (a caror valoare este evaluata de compilator) care reprezinta limitele superioare ale indicilor tabloului.
Exemple:- int v[10]; am declarat un vector cu 10 componente de tip intregcare au indici intre 0 si 9, v[0], v[1], ....., v[9];float a[10], b[20]; am declarat doi vectori a si b care au 10 respectiv 20 de componente de tip real;- int a[10][20]; am declarat o matrice cu 10 linii si 20 coloane;
Referirea la o componenta a tabloului se face astfel:numa_tablou[i1][i2]...[ik];
Tablouri unidimensionale
Tablourile unidimensionale sunt tablouri cu un singur indice (vectori). Daca tabloul contine dim_1 elemente, indicii elementelor au valori intregi din intervalul [0, dim_1-1]. Variabilele tablou pot fi initializate in momentul declararii:declaratie_tablou=lista_valori;
Valorile din lista de valori sunt separate prin virgula, iar intreaga lista este inclusa intre acolade.
Exemple:1. int vector[6]={100, 101, 102, 103, 104, 1r.05};
Adresa elementului de indice i intr-un tablou unidimensional poate fi calculata astfel:adresa_elementului_i=adresa_de_baza + i * lungime_element
Operatii cu tablouri unidimensionale
1. Citirea elementelor unui vector:
int a[5];int i;for(i=0; i < 5; i++);{
printf("a[%d] = ", i+1); // afisarea unui mesaj prealabil citirii fiecarui element
scanf("%d", &a[i]);// citirea valorii elementului de indice i
}
Sau:
int a[20];int i, n;printf("Dim. Max = ");scanf("%d", &n);for(i=0; i < n; i++){printf("a[%d]= ");scanf("%d", &a[i]);}
2. Afisarea elementelor unui vector:
printf("Vectorul introdus este:\n");for(i=0; i < n; i++)printf("%d ", a[i]);
3. Afisarea elementelor unui vector in ordine inversa:
printf("Elementele vectorului n ordine inversa:\n");for(i=n-1; i >= 0; i--)printf("%d ", a[i]);}
3. Vectorul suma (c) a vectorilor a si b, cu acelasi numar de elemente:
for(i=0; i < n; i++)c[i]=a[i]+b[i];
Vectorul diferenta (c) a vectorilor a si b, cu acelasi numar de elemente:
for(i=0; i < n; i++)c[i]=a[i] - b[i];
Algoritmi ce lucreaza cu tablourile
Determinarea valorii minime si a valorii maxime din vector:
O variabila preia continutul primei componente a vectorului (max=v[0] sau min=v[0]), apoi o compara, pe rand, cu celelalte componente ale vectorului, iar in functie de conditia care se pune in program variabila va retine componenta cu valoare maxima sau componenta cu valoare minima.
max=v[0]; if(v[i] > max) max=v[i];
min=v[0]; if(v[i] < min) min=v[i];
Elemente distincteSe considera un vector cu n componente si se decide daca elementele citite sunt distincte (nu exista doua egale) sau nu.Pentru a rezolva problema se procedeaza astfel:- o variabila i retine indicele primei componente;- o variabila j retine indicele urmatoarei componente- se initializeaza o variabila gasit cu valoarea logica 0- daca sunt gasite doua valori egale variabilei gasit i se atribuie valoarea logica 1.
#include <stdio.h>#include <conio.h>
int main(){int v[10], i, j, n, gasit;printf("Introduceti numarul de elemente: ");scanf("%d", &n);for(i=1; i <= n; i++){printf("v[%d] = ", i);scanf("%d", &v[i]);}gasit=0;for(i=1; i <= n; i++)for(j=i+1; j <= n; j++)if(v[i]==v[j])gasit=1;if(gasit==1)printf("\n\nNumerele nu sunt distincte!");elseprintf("\n\nNumerele sunt distincte!");getch();
return 0;}
Metode de sortare
Operatia prin care se aranjeaza elementele unui tablou in ordine crescatoare sau descrescatoare se numeste sortare.In continuare prezentam doua metode de sortare:
a) Sortarea prin selectarea minimului (maximului):- se determina minimul dintre toate valorile retinute incepand cu prima pozitie si acesta este trecut pe prima pozitie prin interschimbarea continuturilor dintre cele doua componente;- se determina minimul dintre toate valorile retinute incepand cu a doua pozitie si acesta este trecut pe prima pozitie prin interschimbarea continuturilor dintre cele doua componente;......................................................- se determina minimul dintre valorile retinute incepand cu penultima pozitie si acesta este trecut pe penultima pozitie.
Sortarea prin interschimbareSe parcurge tabloul intr-un ciclu do while inversand continuturile componentelor care nu sunt in ordine crescatoare (descrescatoare).
Algoritmul este urmatorul:- se efectueaza prima parcurgere si se schimba A[1] cu A[2] (deoarece 3 > 1) si A[3] cu A[4] (deoarece 4 > 2), vectorul va arata astfel:
- se efectueaza a doua parcurgere si se schimba A[2] cu A[3] (deoarece 3 > 2), iar vectorul va arata astfel:
- se efectueaza a treia parcurgere dar deoarece numerele sunt in ordine crescatoare algoritmul se incheie.
do{gasit=0;for(i=1; i <= n-1; i++)if(a[i] > a[i+1]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;gasit=1;}}while(gasit==1);
Tablouri bidimensionale
Operatii cu tablouri bidimensionale
Initializarea elementelor unei matrici in momentul declararii acesteia:
int mat[4][3]={{10, -50, 3},
{32, 20, 1},{-1, 1, -2},{7, -8, 19} };
Citirea de la tastatura a elementelor unei matrici de maxim 10 linii si 10 coloane si afisarea elementelor tabloului:
#include <stdio.h>#include <conio.h>
int main(void){int A[10][10];int nr_lin, nr_col;int i, j;printf("Nr. linii = ");scanf("%d", &nr_lin);printf("Nr. coloane = ");scanf("%d", &nr_col);
// citirea elementelor unei matricifor(i=0; i < nr_lin; i++)for(j=0; j < nr_col; j++){printf("\nA[%d][%d] = ");scanf("%d", &A[i][j]);}
// afisarea elementelor matriciifor(i=0; i < nr_linii; i++){for(j=0; j < nr_col; j++)printf("%d ", A[i][j]);printf("\n");// dupa afisarea elementelor une linii se trece la linia urmatoare
}}
Interschimbarea a doua linii de indici x si yfor(j=1; j <= n; j++){temp=a[x][j];a[x][j]=a[y][j];a[y][j]=temp;}
Interschimbarea a doua coloane de indici x si yfor(i=1; i <= n; i++){temp=a[i][x];a[i][x]=a[i][y];
a[i][y]=temp;}
Siruri de caractere
Sirurile de caractere sunt tablouri de caractere, care au ca ultim element un terminator de sir, caracterul NULL (zero ASCII), '\0'.
Exemplu:char tc[5]={'a', 'b', 'c', 'd', 'e'};// tablou de caractere
char a[11]={'c', 'a', '1', 'c', 'u', 'l', 'a', 't', 'o', 'r' '\0'};// sirul de caractere cu elementele calculator
Vectorii de caractere pot fi initializati la declarare, caracterul NULL fiind memorat automat.
Exemplu:char a[11]='calculator';char a[]='calculator';// in acest caz compilatorul face calculul numarului de octeti necesari
char a[100]='calculator';// se rezerva mai multi octeti decat este necesar
Citirea si scrierea sirurilor de caracteregets(sir)
Functia citeste un sir de caractere pana la intalnirea caracterului '\n' (tasta ENTER).Prin utilizarea acestei functii sunt citite si caracterele albe, este inserat la sfarsitul sirului automat caracterul NULL.
Exemple:1.
char a[10];flushall(); // functia flushall() se utilizeaza de fiecare data inaintea functiei gets() pentru a sterge caracterele ramase in bufferul tastaturii.
printf("Sirul citit este:\n %s", a);
2.#
include <stdio.h># include <string.h># include <conio.h>
int main(void){char sir1[1000], sir2[25];printf("sir1 = ");flushall();gets(sir1);printf("sir2 = ");flushall();gets(sir2);getch();return 0;}
Daca nu am fi folosit functia flushall() inaintea fiecarei citiri de sir, citirea e probabil sa nu se fi realizat.
Functii pentru operatii cu siruri de caractere
Functiile pentru operatii cu siruri de caractere se gasesc in headerul string.h.
strlen (nume_sirReturneaza un numar intreg ce reprezinta lungimea unui sir de caractere, fara a numara terminatorul de sir.
strcmp(sir_1, sir_2)Functia compara cele doua siruri date ca argument si returneaza o valoare intreaga egala cu diferenta dintre codurile ASCII ale primelor caractere care nu coincid.
strcpy(sir_destinatie, sir_sursa)Functia copie sirul sursa in sirul destinatie. Pentru a fi posibila copierea, lungimea
sirului destinatie trebuie sa fie mai mare sau egala cu cea a sirului sursa, altfel pot aparea erori grave.
strcat(sir_destinatie, sir_sursa)Functia concateneaza cele doua siruri: sirul sursa este adaugat la sfarsitul sirului destinatie. Tabloul care contine sirul destinatie trebuie sa aiba suficiente elemente.
Tipul inregistrare
Pentru a utliza date cu componente de tipuri diferite se folosesc structuri (struct). In C exista tipul de date struct cu urmatoarea forma generala:
struct [nume_structura]{[ <tip> <nume_variabila [, nume variabila, ...] > ];[ <tip> <nume_variabila [, nume variabila, ...] > ];...} [lista de variabile];
Sa presupunem ca trebuie sa prelucram simultan informatii despre un produs:Denumire - char denumire[20];Pret - int pret;Cantitate - int cantitate;
Se poate utiliza un vector? (nu, deoarece acesta poate retine doar date de acelasi tip). Informatiile pe care trebuie sa le implementam sunt eterogene ( de tipuri diferite ).
Pentru accesarea campurilor unei structuri se foloseste operatorul de selectie directa:
p.denumire - campul denumire al variabilei p;p.pret - campul pret al variabilei p;p.cantitate - campul cantitate al variabilei p;
Citirea si tiparirea unei variabile de tipul struct (produs):
// citireprintf("denumire produs = ");scanf("%s", p.denumire);printf("pret produs = ");scanf("%d", &p.pret);printf("cantitate produs = ");scanf("%d" &p.cantitate);
// afisareprintf("\ndenumire produs = %s", p.denumire); printf("\npret produs = %d", p.pret); printf("\ncantitate produs = %d", p.cantitate);
Daca se declara doua variabile de tipul produs p1 si p2 se poate utiliza operatia de atribuire p1 = p2, prin care se cope camp cu camp informatia din p2 in p1. O astfel de atribuire se numeste copiere bit cu bit.
Exemplul de mai sus poate fi utilizat in cazul unui singur produs. In realitate trebuie conceputa o structura de date care sa permita memorarea informatiilor pentru un numar oarecare de produse.In acest caz se utilizeaza un tablou unidimensional cu elemente de tip produs.
produs p[100];printf("pret produs = ");scanf("%d", &p.pret[0]);printf("pret produs = %d", p.pret[0]);
Inregistrari imbricate
Limbajul C permite definirea de structuri ale caror membri sunt tot structuri:
struct data{int zi;char luna[11];int an;};
struct persoana{char nume[20], prenume[20];int nr_copii;double salariu;char loc_nastere[20];struct data data_nasterii;} p[100];
Programul cere utilizatorului sa introduca un numar mai mare decat 0 si afiseaza toate numerele mai mici decat acest numar ce indeplinesc conditia ca patratul si cubul lor au cel putin o cifra comuna.
{long nr, i;int ok=0;do{printf("Dati un numar mai mare decat 0: ");scanf("%ld", &nr);}while(nr<=0);printf("\n\nNumerele mai mici decat %ld care indeplinesc conditia ca patratul si cubul lor au cel putin o cifra comuna sunt:\n\n", nr);for(i=1; i< nr; i++)if(CifraComuna(nr)){printf("%ld\n", i);ok=1;}if(!ok)printf("Nu exista numere mai mici decat %ld care sa indeplineasca conditia!\n\n");printf("Apasa o tasta pentru a inchide...");getch();return 0;}
In urma compilarii cu MinGW Developer Studio si pentru numarul 10 am obtinut:
Fisiere text
Limbajul C considera ca orice fisier este o colectie de octeti care vor fi interpretati de program.
mod_deschidere poate fi:- pentru citire: 'r' - deschide un fisier existent. Pointerul de pozitie se afla la inceputul fisierului;- pentru scriere: 'w' - deschide un fisier nou, ori suprascrie in fisierul cu acelasi nume. Pointerul de pozitie se afla la inceputul fisierului.- pentru adaugare: 'a' - daca fisierul nu exista, sistemul de operare il creeaza. Pointerul de pozitie se afla la sfarsitul fisierului.
Functia fopen returneaza un pointer de fisier. Daca fisierul indicat nu a putut fi deschis, pointerul va avea valoarea NULL.
Exemplu:FILE *f;f = fopen("matrice.in", "r");
Citirea si scrierea in fisierPrelucrarea datelor din fisiere se poate face: caracter cu caracter sau linie cu linie.
Prelucrarea caracter cu caracterVor fi utilizate functiile: fgetc() si fputc().Sintaxa:
int fgetc(FILE * pointer_fisier); // pentru citireint fputc(int c, FILE * pointer_fisier); // pentru afisare
< Este necesara includerea fisierului antet stdio.h.fgetc returneaza caracterul citit, dupa conversia acestuia intr-un intreg fara semn. In caz de eroare sau sfarsit de fisier, functia va returna EOF.fputc returneaza caracterul c. In caz de eroare, aceasta returneaza EOF.
Prelucrarea linie cu linieVor fi utilizate functiile: fgets() si fputs(). Sintaxa:
char * fgets (char * sir, int n, FILE * pointer_fisier);
// pentru citire
int fputs (const char * sir, FILE * pointer_fisier);// pentru scriere
Dupa citirea/scriere unei linii de text, pointerul de pozitie avanseaza la inceputul liniei urmatoare.Functia fgets() citeste datele din fisier si le pune in bufferul de caractere sir. Citirea se va efectua pana la n=-1 sau pana la primul caracter '\n' (linie noua). Daca citirea se efectueaza cu succes, functia va returna un pointer la sirul de caractere, altfel (daca apare o eroare sau s-a ajuns la sfarsitul de fisier) functia va returna NULL.Functia fputs() scrie caracterele in sir pana la NULL. Daca operatia se incheie cu succes, functia va returna o valoare pozitiva, in caz contrar va returna EOF.
Afisare cu formatPentru a afisa informatiile conform unui format de afisare, se utilizeaza specificatorii de format de care dispune functia fprintf. Valorile acestora sunt cele cunoscute pentru printf.
Dupa rularea acestui program se va creea un fisier cu numele "date.out" in care va aparea textul:Valoarea lui n: 20
Inchiderea fisierelor textPentru inchiderea unui fisier se utilizeaza functia fclose(). Sintaxa este urmatoarea:
int fclose (FILE * pointer_fisier);
Functii utileCu fisiere text se pot efectua si alte operatii cum ar fi: redenumirea si stergerea acestora.Pentru schimbarea numelui unui fisier se foloseste functia rename(). Sintaxa:
int rename (const char *fisier_vechi, const char *fisier_nou);
Redenumirea poate fi utilizata si pentru a muta un fisier dintr-un director in altul. Daca operatia s-a incheiat cu succes, functia va returna valoarea 0, altfel va returna -1.Pentru stergerea fisierelor se poate utiliza functia remove(). Sintaxa este urmatoarea:
int remove (const char *nume_fisier);
Inainte de stergere, asigurati-va ca ati inchis fisierul!Daca operatia s-a incheiat cu succes, functia va returna valoarea 0, altfel va returna valoarea -1.
long eliminare_zero(long nr){int uc;long x=0, inv=0;while(nr!=0){uc=nr%10;if(uc!=0)x=x*10+uc;nr/=10;}while(x!=0){inv=inv*10+(x%10);x/=10;}return inv;}
int main()
{int n, i;long nr, numere[NMAX];printf("Cate numere vor fi citite? ");scanf("%d", &n);printf("Introduceti cele %d numere:\n", n);for(i=0; i < n; i++){printf("nr%d = ", i+1);scanf("%ld", &nr);numere[i]=eliminare_zero(nr);}printf("\n\nDupa eliminarea zerourilor, numerele sunt:\n\n");for(i=0; i < n; i++)printf("%ld \n", numere[i]);printf("Apasa o tasta pentru a inchide...");getch();return 0;}
Recursivitate
Recursivitatea este un mecanism general de elaborare a programelor.Mecanismul recursivitatii consta in posibilitatea ca un subprogram sa se autoapeleze.Recursivitatea s-a utilizat initial pentru transcrierea formulelor matematice descrise recursiv, ulterior extinzandu-se pentru elaborarea multor algoritmi.
Exemple:1. La un televizor se cupleaza o camera video care filmeaza ecranul televizorului. Pe ecran se va vedea un televizor care va prezenta un televizor... Vom vedea o serie de televizoare din ce in ce mai mici.2. Un descendent al unei persoane este un copil al sau un descendent al unui copil al sau.In exemplul 2 pentru a defini notiunea de "descendent" am folosit notiunea insasi.Spunem ca o notiune este definita recursiv daca in cadrul definitiei intervine insasi notiunea care se defineste.Intalnim procese care se exprima in termeni recursivi, sau in matematica apar frecvent relatii recursive, denumite si relatii de recurenta.1. Cea mai simpla si mai familiara functie exprimata in termeni recursivi este factorialul:
n! = 1 daca n=0 sau n! = n * (n - 1)! daca n > 0.
unsigned long fact (int n){if (n==0)return 1;return n * fact (n-1);}
2.Sirul Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in care primii doi termeni sunt 0 si 1, iar in rest, fiecare termen se obtine insumand cei doi termeni care il preced.Prin urmare, o definitie recursiva pentru sirul lui Fibonacci este:
fib: N -> Nfib(n) = n daca n<=1 si fib(n) = fib(n-1) + fib(n-2) daca n > 1.
unsigned long fibo ( int x){if (x <= 1)return x;return fibo (x-2) + fibo(x-1);}
Observatie:Este absolut necesar sa se asigure iesirea din recursivitate. Pentru aceasta va exista o conditie de iesire.
Recursivitatea in cascadaDaca analizam mecanismul apelurilor pentru a calcula termenul fib(5) observam ca trebuie calculate fib(4) o data, fib(3) de doua ori, .... fib(1) de 5 ori...Aceasta se numeste recursivitate in cascada si apare in cazul in care functia se autoapeleaza de cel putin doua ori pentru a calcula un termen. In acest calculul este ineficient, timpul de calcul este exponential si se recomanda utilizarea unei metode iterative sau stocarea rezultatelor obtinute intr-un vector.
Recursivitate indirectaRecursivitatea se poate realiza si in mod indirect, atunci cand in cadrul blocului unei functii apare apelul unei alte functii care la randul sau apeleaza direct sau indirect functia respectiva.De exemplu, sa presupunem ca in functia A() intervine un apel al functiei B(). In functia B() intervine un apel al functiei A(). Observati ca functia A() se autoapeleaza, prin intermediul functiei B(). Prin urmare functia A() este indirect recursiva.
Observatii:1. Recursivitatea constituie o tehnica de a descrie intr-o maniera eleganta si concisa prelucrari de maniera repetitiva.2. In comparatie cu abordarea iterativa, abordarea recursiva prezinta avantajul scrierii concentrate.3. O aplicatie implementata recursiv se depaneaza mai greu decat una implementata iterativ.
Exemple:
1. #include<stdio.h> #include <conio.h>
void f( long int n){if(n!=0){if(n%2==0)printf("%d", n%10);f(n/10);}}
int main( void ){printf("Apel functie f(12345):\n");printf("rezultat = ");f(12345);getch();return 0;}
2.#include <stdio.h>#include <conio.h>
int f ( long int n, int k){if(n!=0)if(n%10==k)return 1+f(n/10, k);else return 0;}
Prezentare generalaAceasta metoda generala de programare se aplca problemelor in care solutia se poate reprezenta sub forma unui vector X = (x1, ..., xn). Pentru fiecare problema concreta sunt date anumite relatii intre componentele x1, ..., xn ale vectorului X, numite conditii interne.Multimea finita S = S1 x S2 x ... x Sn se numeste spatiul solutiilor posibile ( este un produs cartezian ). Solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Ceea ce ne propunem este de a determina toate solutiile rezultat, cu scopul de a le afisa sau de a alege dintre ele una care maximizeaza sau minimizeaza o eventuala functie obiectiv data.O metoda simpla de determinare a solutiilor rezultat consta in generarea intr-un mod oarecare toate solutiile posibile si de a verifica daca ele satisfac conditiile interne. Dezavantajul consta in faptul ca timpul cerut de aceasta investigare exhaustiva este foarte mare. Astfel, chiar pentru |Si| = 2, oricare ar fi i, timpul necesar este de ordinul 2 la puterea n, deci exponential.Metoda backtracking urmareste sa evite generarea tuturor solutiilor posibile. In acest scop, elementele vectorului X primesc pe rand valori in sensul ca lui xk i se atribuie o valoare numai daca au fost atribuite deja valori lui x1, ..., xk-1. Mai mult, o data o
valoare pentru xn stabilita, nu se trece direct la atribuirea da valori lui xk+1, neindeplinirea lor exprimand faptul ca oricum am alege xk+1, ..., xn nu vom putea ajunge la o solutie rezultat, adica o conditite pentru care conditiile interne sa fie satisfacute. Evident ca in cazul neindeplinirii conditiilor de continuare va trebui sa facem o alta alegere pentru xk, sau daca Sk a fost epuizat sa micsoram pe k cu o unitate incercand sa facem o noua alegere pentru xk, etc. Aceasta micsorare a lui k da numele metodei, ilustrand faptul ca atunci cand nu mai putem avansa, urmarim inapoi secventa curenta din solutie. Este evident ca intre conditiile de continuare si conditiile interne exista o stransa legatura. O buna alegere pentru conditiile de continuare are ca efect o importanta reducere a numarului de calcule.Metoda backtracking poate fi reprezentata usor, pe un arbore construit astfel:- nivelul 1 contine radacina;- din orice varf de pe nivelul k pleaca sk muchii spre nivelul k+1 etichetati cu cele sk muchii ale lui Sk.Nivelul n+1 va contine s1 * s2 * ... *sn varfuri. Pentru fiecare varf de pe nivelul n+1, etichetele muchiilor continute pe drumul ce leaga radacina de acest varf reprezinta o solutie posibila.
Exemplu - Sa consideram problema submultimilor de suma data care consta in urmatoarele: Fie A = (a1, a2, ..., an) cu ai > 0, oricare ar fi i. Fie M inclus in R. Se cauta toate submultimile B ale lui A pentru care suma elementelor este M.Pentru a putea realiza problema prin metoda backtracking vom reprezenta solutia sub forma x = (x1, ..., xn) unde xi = 1 daca ai inclus in B si xi = 0 in caz contrar. Sa ne situam in ipoteza ca n = 4.Castigul obtinut prin introducerea conditiilor de continuare consta in faptul ca, daca intr-un varf ele nu mai sunt verificate, se va renunta la parcurgerea subarborelui care are ca radacina acest varf.Acest exemplu permite prezentarea unei variante a metodei backtracking. Intr-adevar, sa consideram drept solutie posibila o valoare k <= n impreuna cu cuplul (x1, ...,xk) unde pentru i inclus in {1, ..., k}, xi reprezinta indicele elementului pe care il introducem in B. Evident xi este diferit de xj pentru i diferit de j. Pentru a nu se repeta solutii, vom presupune x1 < x2 < ... < xn.Diferite variante ale metodei backtracking nu schimba esenta ei care consta in faptul ca este reprezentabila pe un arbore care este parcurs "coborand" in arbore numai daca exista sanse de a ajunge la o solutie rezultat.In continuare, problemele care vor fi prezentate vor urma o schema generala si anume:- se va testa daca am obtinut o solutie, situatie in care aceasta se va retine;- daca nu am obtinut o solutie se incearca plasarea unui nou element in vectorul solutie cu respectarea conditiilor de continuare.- daca nu se reuseste plasarea unui nou element si spatiul valorilor posibile de plasat s-a epuizat, se revine la pozitia anterioara si se incearca sa se plaseze pe ea un alt
element.Faptul ca dupa plasarea unui element in vectorul solutie algoritmul presupune plasarea unui element pe pozitia imediat urmatoare, adica de fapt reluarea algoritmului, conduce posibilitatea abordarii recursive a algoritmilor de tip backtracking. Acest lucru permite o scriere mult mai scurta si mai simpla a algoritmilor si apoi a programelor care ii implementeaza. Astfel, general, un algoritm backtracking poate fi prezentat astfel:
pentru ficare valoare i din multimea Sk executaxk <-i daca X respecta conditiile interne atuncidaca X este solutie atunciafiseaza Xaltfelapeleaza back(k+1)sfdacasfdacasfpentru
In functie de problema concreta, in algoritmul descris mai sus se vor modifica doar instructiunea pentru, conditiile interne si cele de solutie, structura algoritmului pastrandu-se.
Probleme de generare. Oportunitatea utilizarii metodei backtracking
Problemele care se rezolva prin metoda backtracking pot fi impartite in mai multe grupuri de probleme cu rezolvari asemanatoare, in functie de modificarile pe care le vom face in algoritm. Principalele grupuri de probleme sunt:a) Probleme in care vectorul solutie are lungime fixa si fiecare element apare o singura data in solutie;b) Probleme in care vectorul solutie are lungime variabila si fiecare element poate sa apara de mai multe ori in solutie;c) Probleme in plan, atunci cand spatiul in care ne deplasam este un tablou bidimensional.
Vom prezenta in cele ce urmeaza cateva probleme care fac parte din primul grup. Cele mai cunoscute sunt:- generarea permutarilor unei multimi;- generarea aranjamentelor unei multimi;- generarea submultimilor unei multimi;
- generarea submultimilor cu m elemente ale unei multimi (combinari);- generarea produsului cartezian a n multimi;- generarea tuturor secventelor de n (par) paranteze care se inchid corect;- colorarea tarilor de pe o harta astfel incat oricare din doua tari vecine sa aiba culori diferite;- aranjarea a n regine pe o tabla de sah de dimensiune n fara ca ele sa se atace.
Toate problemele din acest grup au particularitatea ca solutia se obtine atunci cand vectorul solutie ajunge sa contina un anumit numar de elemente.Vom explica modul de lucru al metodei backtracking pentru problema damelor.
Aranjarea reginelorDandu-se o tabla de sah de dimensiune n x n (n > 3) sa se aranjeze pe ea n regine fara ca ele sa se atace. Reamintim ca o regina ataca linia, coloana si cele 2 diagonale pe care se afla. In figura de mai jos celulele colorate mai inchis sunt atacate de regina pozitionata unde indica litera 'R'.
In algoritmul de mai sus avem de particularizat urmatoarele:Instructiunea pentru ficare valoare i din multimea Sk executa va fi inlocuita cu o instructiune pentru care parcurge toate valorile de la 1 la n.Conditia de a putea plasa o regina pe pozitia k este un pic mai complicata si presupune verificarea ca sa nu se atace cu nici una dintre celelalte k-1 regine deja plasate pe tabla. Daca pe pozitia k din vectorul X punem o valoare ea va reprezenta coloana pe care se plaseaza pe tabla regina k. Conditiile devin astfel:x[i] diferit de x[k] si |k-i| diferit de |x[k]-x[i]| cu i de la 1 la k-1 si |x| reprezinta modulul lui x.Conditia de solutie este simpla si presupune plasarea corecta a tuturor celor n regine.
void scriesol(){int i, j;nrsol++;printf("\nSolutia %d este", nrsol);for(i=1; i <= n; i++){printf("\n");for(j=1; j <= n; j++)if(x[j]==i)printf("X ");elseprintf("0 ");}}
int potcont(int k){int i;for(i=1; i <=k-1; i++)if(x[i]==x[k] || k-i==abs(x[k]-x[i]))return 0;return 1;}
void back(int k){int i;for(i=1; i <= n; i++){x[k]=i;if(potcont(k))if(k==n)scriesol();elseback(k+1);}}
int main( void ){int n;do{printf("n (n>=3) = ");scanf("%d", &n);}while(n<3);nrsol=0;back(1);printf("\n\n%d solutii\n\n");printf("Apasa o tasta pentru a inchide...");getch();return 0;}
Din al doilea grup fac parte probleme a caror conditie de solutie nu se mai pune asupra numarului de elemente din vectorul X, ci asupra elementelor din solutie. Exemple:- partitiile unui numar natural n- partitiile unei multimi- plata unei sume cu monede de valori date
Partitiile unui numar natural. Fie n > 0, natural. Sa se scrie un program care sa afiseze toate partitiile unui numar natural n.Numim partitie a unui numar natural nenul n o multime de numere naturale nenule {p1, p2, ..., pk} care indeplinesc conditia p1 + p2 + ... + pk = n.Ex: pt. n = 4 programul va afisa:4 = 1 + 1 + 1 +1 4 = 1 + 1 + 24 = 2 + 24 = 4
Observatii:- lungimea vectorului solutie este cel mult n;- exista posibilitatea ca solutiile sa se repete;- conditia de final este indeplinita atunci cand suma elementelor vectorului solutie este n.
Am mentionat mai sus ca vom folosi doi parametri, unul pentru pozitia in vectorul solutie si un al doilea in care avem sumele partiale la fiecare moment. Avem determinata o solutie atunci cand valoarea celui de-al doilea parametru este egala cu n.In aceasta situatie la fiecare plasare a unei valori in vectorul sol valoarea celui de al doilea parametru se mareste cu elementul ce se plaseaza in vectorul solutie. Apelul procedurii back din programul principal va fi back(1, 0).Exista si posibilitatea de a apela procedura back din programul principal back(1, n) si valoarea celui de al doilea parametru se decrementeaza cu elementul ce se plaseaza in vectorul sol, iar o solutie avem cand acest parametru este zero. Indiferent care modalitate este aleasa acest al doilea parametru ne permite sa optimizam putin programul in sensul ca putem considera niste conditii de continuare mai stranse.
#include <stdio.h>#include <conio.h>
int n, ns, sol[20];
void afis(int l){int i;ns++;
printf("\nSolutia nr. %d:\n", ns);for(i=1; i <= l; i++)printf("%d ", sol[i]);printf("\n");}
void back(int i, int sp){int j;if(sp==n)afis(i-1);elsefor(j=1; j <= n-sp; j++)if(j >= sol[i-1]){sol[i]=j;back(i+1, sp+j);}}
int main( void ){printf("n = ");scanf("%d", &n);back(1, 0);printf("\n\n%d solutii!\n\n", ns);printf("Apasa o tasta pentru a inchide...");getch();return 0;}
Problemele in plan necesita parcurgerea unui tablou unidimensional, iar cele mai cunoscute sunt:- parcurgerea tablei de sah cu un cal, fara a trece de doua ori prin aceeasi pozitie;- gasirea iesirii din labirint;Problemele care se rezolva prin metoda backtracking in plan au ca cerinta deplasarea in tablou, pe linii, coloane sau diagonale sau prin saritura ( de obicei saritura calului ) dintr-un punct in alt punct al tabloului sau pe frontiera (prima linie sau coloana, ultima linie sau coloana ) eventual respectand anumite conditii de deplasare. Daca ne gasim intr-un anumit punct iar cerinta este de a ne deplasa in unul din cei opt vecini ai lui vom utiliza pentru acest lucru doua cicluri for de la -1 la 1 cu care valori vom modifica coordonata punctului curent. Daca deplasarea este permisa numai pe linii conditia de respectat este ca suma in valoare absoluta pentru cei doi indici sa fie 1, iar pentru deplasarea pe diagonala 2. De asemenea se mai impune conditia de a nu parasi tabloul, lucru care il vom respecta testand ca coordonatele noului punct sa apartina multimii [1...nrlinii] si [1...nrcol].
Saritura calului.Fiind data o tabla de sah de dimensiune n x n si un cal in coltul stanga sus al acesteia, se cere sa se afiseze toate posibilitatile de mutare a acestei piese de sah astfel incat sa treaca o singura data prin fiecare patrat al tablei. O solutie va fi afisata ca o matrice n x n in care sunt numerotate sariturile calului.
De exemplu, pentru n = 5, o solutie este:1 14 9 20 2310 19 22 15 85 2 13 24 213 6 17 12 25
Pentru rezolvarea acestei probleme vom codifica directiile de deplasare pentru ca ar fi ineficient sa scriem doua cicluri for de la -2 la 2 cu cele 25 de variante de deplasare din care valide sunt doar 8. De asemene, aici spre deosebire de celelalte probleme tratate la aplicarea metodei backtracking in plan nu vom folosi un vector solutie, ci vom scrie sariturile in tablou urmarind ca la revenire sa refacem pozitiile ocupate pentru a nu se lua blocaje. In figura de mai jos sunt prezentate cele 8 mutari posibile pentru un cal.
#include <stdio.h> #include <conio.h>
const int dx[8]={-1, 1, 2, 2, -1, -2, -2};const int dy[8]={-2, -2, -1, 1, 2, 2, 1, -1};int a[10][10], n;
FILE *f=fopen("cal.txt", "w");
void afis( void ){int i, j;for(i=1; i <= n; i++){for(j=1; j <= n; j++)fprintf(f, "%d ", a[i][j]);fprintf(f, "\n");}fprintf(f, "\n");}
int inside(int i, int j){return i>=1 && i<=n && j>=1 && j<=n;}
void back(int i, int j, int pas){int k, inou, jnou;a[i][j]=pas;if(pas==n*n)afis();elsefor(k=0; k<8; k++){jnou=i+dx[k];jnou=j+dy[k];if(inside(inou, jnou) && a[inou][jnou]==0)back(inou, jnou, pas+1);}a[i][j]=0;}
int main( void )
{printf("n = ");scanf("%d", &n);back(1, 1, 1);printf("\n\nApasa o tasta pentru a inchide...");getch();fclose(f);return 0;}
La aceste categorii de probleme se adauga si cele de optim, care presupun alegerea solutiei optime dintre cele generate.
Program ce realizeaza permutarile unei multimi de elemente (1, 2, 3, ...., n) folosind backtracking iterativ.
#include <stdio.h> #include <conio.h>
#define NMAX 100
typedef int stiva[NMAX]; stiva st;int k, as, ev, n;
int main(){printf("\n\n\nProgramul realizeaza permutarile multimii de elemente {1, 2, 3, ... n}.\n"); do{printf("\nDati n: ");scanf("%d", &n);}while(n<0);printf("\n\nPermutarile multimii formate din primele %d numere sunt:\n\n", n);bt();printf("\n\n\nApasa o tasta pentru a inchide...");getch();
}
Varianta ce foloseste backtracking recursiv a programului ce realizeaza permutarile multimii (1, 2, 3, ..., n).
#include <stdio.h>#include <conio.h>
#define NMAX 100
typedef int stiva[NMAX];stiva st;int n, as, ev, k;
int main(){printf("\n\n\nProgramul realizeaza permutarile primelor n elemente: {1, 2, 3, ... n}.\n\n");do{printf("n = ");scanf("%d", &n);}while(n<0);printf("\n\nPermutarile primelor %d elemente sunt:\n\n", n);bk(1);printf("\n\nApasa o tasta pentru a inchide...");
getch();}
Variabile dinamice (pointeri)
Definitie:Se numeste pointer (variabila dinamica) o variabila care retine adrese de memorie ale altor variabile.
Declarare:*nume_variabila;
Exemplu:int *x; // x retine adresa unei variabile de tip int/integer
Operatori specifici:&x - indica adresa unei variabile, x*x - indica valoarea pe care o adreseaza pointerul x
Functii specifice:
1. Functia de alocare a spatiului de memorie pentru un pointer x:void *malloc(size_t size)
2. Functia de eliberare a spatiului de memorie pentru un pointer x:void free(void *block)
Se defineste constanta NULL ca fiind pointerul nul sau pointerul care nu contine nici o adresa.
a = 7 deci *x are valoarea 7, care se va afisa.b = a * 5 = 7 * 5 = 35 deci si *y are tot valoarea 35.b = b - (7+35) = 35 - 42 = -7, valoarea care se va afisa*x = *y; deci valoarea indicata de x va fi cea indicata si de y, adica -7 ( y este adresa lui b), se va afisa -7Conditia din structura alternativa testeaza daca variabilele x si y indica aceeasi adresa, ceea ce este fals (x este adresa lui a, iar y este adresa lui b), deci se va afisa 0. In concluzie, valorile afisate sunt: 7, -7, -7, -0.
Structuri dinamice de date
Structurile dinamice de date sunt date structurate ale caror componente (noduri) se aloca pe masura ce se creaza, adica in mod dinamic.Avantajele alocarii dinamice fata de alocarea acelorasi structuri de date in mod static (in segmentul de date) sau volatil (in segmentul de stiva) este posibilitatea de a utiliza aceasta memorie dupa dorinta programatorului si, evident, economia de memorie.Pentru a crea o structura dinamica de date se impune folosirea unui camp care sa retina adresa de memorie la care se afla urmatorul element din structura, deci un camp care este un pointer. Astfel se realizeaza o inlantuire dupa adrese. In HEAP, structura respectiva va avea zone alocate componentelor sale in locurile gasite disponibile, care nu se succed intotdeauna in ordinea in care este realizata inlantuirea logica.In functie de tipul inlantuirii realizate intre componente, exista urmatoarele tipuri de organizari:- structuri liniare: liste simplu inlantuite si liste dublu inlantuite, cu cazuri particulare: lista circulara, stiva, coada.- structuri arborescente ierarhice- structuri retea
In aceasta lucrare vom trata structurile dinamice liniare de date.Asupra unei liste liniare putem efectua urmatoarele operatii:- creare lista;- parcurgere lista, pentru prelucrarea informatiei utile (afisare, calcule, sortare, cautare, etc - operatii care se pot efectua in general si asupra vectorior)
- inserarea unui nod in lista- stergerea unui nod din lista
Liste liniare simplu inlantuite
O lista liniara simplu inlantuita are nodul format din doua componente principale: o parte statica, ce contine informatia utila si o parte dinamica, ce contine adresa nodului urmator din lista. Ultimul nod al listei are in partea dinamica valoarea NULL deoarece dupa acesta nu mai este inlantuit niciun alt nod.
Ca modalitate de implementare, putem definii un tip de date inregistrare in care partea dinamica va fi pointer catre acelasi tip, pentru a retine adresa nodului urmator si va fi numita in continuare "adr" iar partea statica va fi numita "info".
struct nod{[tip] info;nod *adr;};
Vom conveni sa notam cu p - primul nod al listei, u - ultimul nod al listei si q - nodul curent, de lucru, in cadrul unei liste.Accesul la campurile unei astfel de inregistrari se face prin:
Astfel, campurle primului nod vor fi accesate astfel:
p->info si p->adr
In continuare vom prezenta operatiile uzuale care se efectueaza asupra unei liste liniare simplu inlantuite.
a. Crearea unei liste liniare simplu inlantuite
Pentru a crea o lista simplu inlantuita se parcurg urmatoarele etape:- Se creeaza primul nod, p;- Se creeaza celelalte noduri din lista prin legarea acestora pe rand de ultimul nod creat.Crearea nodului p presupune: alocarea spatiului de memorie pentru acesta (1), citirea informatiei utile (2), legarea nodului nou creat de lsta preexistenta (3). In cazul primului nod, legatura se face cu nodul NULL.Celelalte noduri se creaza in acelasi mod, avand grija la modul in care se fac legaturile dintre acestea cu lista (se leaga de ultimul nod creat (4) si apoi noul nod devine ultimul din lista (5)).
int main(){struct nod{int info;nod *adr;};typedef nod *NOD;NOD p, u, q;int n, i;printf("Dati numarul de noduri: ");scanf("%d", &n);p=(NOD)malloc(sizeof(nod));printf("nod 1 = ");scanf("%d", &p->info);p->adr=0;for(i=2; i<=n; i++){q=(NOD)malloc(sizeof(nod));printf("nod %d = ", i);scanf("%d", &q->info);q->adr=0;u->adr=q;u=q;}getch();return 0;}
Parcurgerea unei liste liniare simplu inlantuiteSe porneste de la primul nod, p, (1) se prelucreaza informatia utila (2) si se trece la urmatorul nod (3). Procedeul se repeta pana se trece de ultimul nod din lista (4) (se ajunge la nodul NULL).
Observatie:O lista simplu inlantuita poate fi parcursa folosind si alte structuri repetitive. Lasam ca exercitiu parcurgerea listei in acest mod.
Inserarea unui nod intr-o lista simplu inlantuitaIntr-o lista liniara simplu inlantuita se poate insera un nod la inceput, inainte de primul nod, la sfarsit, dupa ultimul nod, sau in interiorul listei, inainte sau dupa un anumit nod dat. Vom prezenta in continuare cele trei modalitati de inserare.
c1. Inserarea unui nod inainte de primul nod din listaSe creaza nodul q (1) si se realizeaza legatura dintre el si lista (2). Apoi acesta va fi noul prim nod. (3)
c2. Inserarea unui nod dupa ultimul nod din listaSe creeaza nodul q (1) si se realizeaza legatura dintre el si ultimul nod din lista (2). Apoi acesta va fi noul ultim nod. (3)
c3. Inserarea unui nod in interiorul listeiDaca vrem sa inseram un nod nou inainte de un nod dat, t, se parcurge lista pana la nodul anterior lui q (1), se creaza un nod nou, r, (2) apoi se realizeaza legatura intre el si nodul t (3), respectiv intre el si nodul anterior lui t (4). Daca nodul t nu se afla in lista, inserarea se va face dupa ultimul nod.
Observatie:Pentru a insera un nod dupa un nod dat, t, se rationeaza analog, doar ca parcurgerea listei se face pana la t, nu pana la nodul anterior lui. Lasam spre exercitiu implementarea acestui mod de inserare.
d. Stergerea unui nod din listaPutem sterge un nod de la inceputul listei, de la sfarsitul ei, sau din interior. Pentru a sterge un nod, se retine acesta intr-o variabila auxiliara (1), se sterg legaturile dintre el si lista (2) apoi se elibereaza spatiul de memorie ocupat de variabila auxiliara (adica de nodul care trebuie sters). (3)
Stergerea unui nod cu informatia data, x:Se parcurge lista pana la nodul anterior celui cu informatia x (4) si acesta se leaga in lista de cel urmator celui cu informatia x (5):
a. StivaStiva este o structura de date care functioneaza dupa principiul "Last in - first out". Putem imagina o stiva ca un teanc de farfurii, de carti, etc. Conform acestui principiu, putem deduce ca asupra unei stive sunt permise urmatoarele operatii:- Adaugarea unui nod inainte de primul introdus- Stergerea primului nod
Observatie:Primul nod dn stiva se numeste varf si dupa cum observam este singurul nod asupra caruia sunt permise operatii. Ultimul nod din stiva se numeste baza.In urma crearii unei stive in mod dinamic, nodurile vor fi prelucrate in ordine
inversa introducerii lor.
a1. Crearea unei stive:Se parcurg aceleasi etape ca la listele liniare simplu inlantuite, doar ca adaugarea unui nod se face inainte de v (varf).
struct nod{<tip> info;nod *adr;};typedef nod *NOD;int n, i;NOD *v, *b, *p;printf("Dati numarul de noduri: ");scanf("%d", &n);v=(NOD)malloc(sizeof(nod));printf("nr = ");scanf("%d", &v->info);v->adr=0;b=v;for(i=2; i <= n; i++){q=(NOD)malloc(sizeof(nod));printf("nr = ");scanf("%d", &q->info);q->adr=v;v=q;}
Lasam ca exercitiu implementarea celorlalte operatii care pot fi efectuate asupra unei stive, pe modelul celor de la listele liniare simplu inlantuite.
b. CoadaCoada este o structura de date care functioneaza dupa principiul "First in - first out". Conform acestui principiu de functionare, se permit asupra unei cozi urmatoarele operatii:- Adaugarea unui nod dupa ultimul introdus;- Stergerea primului nod;
Observatii:- Primul nod din coada se numeste cap iar ultimul nod se numeste coada.- Crearea unei cozi este identica cu crearea unei liste simplu inlantuite. Cum nici celelalte operatii permise nu difera de cele prezentate la aceasta structura de date, lasam ca exercitiu implementarea operatiilor asupra unei cozi.
c. Lista circulara
O lista circulara este o structura dinamica de date in care ultimul nod contine in partea dinamica adresa primului nod. Practic, o lista circulara nu are prim si ultim nod, ci doar nod de plecare in parcurgerea ei.
c1. Crearea listei circularePentru crearea unei liste circulare, vom folosi aceeasi metoda ca la lista liniara simplu inlantuita, avand grija ca la sfarsitul crearii ultimului nod sa adaugam adresa primului element:
c3. Adaugarea unui nod intr-o lista circularaPutem adauga un nod inainte de nodul de plecare sau inainte de un nod oarecare.
Inserarea unui nod inainte de primul nod din listaSe creeaza nodul q si se realizeaza legatura dintre el si lista. Apoi acesta va fi noul prim nod. Se are in vedere pastrarea calitatii de lista circulara.
Observatie:Inserarea unui nod in interiorul listei circulare se face analog cu inserarea intr-o lista simplu inlantuita.
c4. Stergerea unui nod dintr-o lista circularaPutem sterge nodul de pornire sau un nod din interiorul listei. Pentru a sterge un nod, se parcurg aceleasi etape prezentate anterior, avand grija ca lista sa ramana circulara.
Stergerea nodului de plecare
NOD aux;aux=p;p=p->adr;u->adr=p;free(aux);
Stergerea unui nod cu informatia data, x:Se parcurge lista pana la nodul anterior celui cu informatia x (4) si acesta se leaga in lista de cel urmator celui cu informatia x (5):
O lista liniara dublu inlantuita are nodul format din trei componente principale: o parte statica, ce contine informatia utila si doua parti dinamice, ce contin adresa nodului urmator din lista si adresa nodului anterior. Ultimul nod al listei are in partea dinamica din dreapta valoarea NULL iar primul nod din lista are in partea dinamica din stanga valoarea NULL.
Ca modalitate de implementare, putem defini un tip de date inregistrare in care partile dinamice vor fi pointeri catre acelasi tip, pentru a retine adresa nodului din stanga, respectiv adresa nodului din dreapta si vor fi numite in continuare "st", respectiv "dr" iar partea statica va fi numita "info":
int n, i;NOD p, u, q;printf("Dati numarul de noduri: ");scanf("%d", &n);p=(NOD)malloc(sizeof(nod));printf("nr = ");scanf("%d", &p->info);p->st=p->dr=0;for(i=2; i <= n; i++){q=(NOD)malloc(sizeof(nod));printf("nr = ");scanf("%d", q->info);q->dr=0;q->st=u;u->dr=q;u=q;}
Observatie:O lista dublu inlantuita poate fi parcursa in ambele sensuri, pornind de la primul, sau de la ultimul nod. Lasam ca exercitiu parcurgerea listei in acest mod.
c. Inserarea unui nod intr-o lista dublu inlantuitaIntr-o lista liniara dublu inlantuita se poate insera un nod la inceput, inainte de primul nod, la sfarsit, dupa ultimul nod, sau in interiorul listei, inainte sau dupa un anumit
nod dat. Vom prezenta in continuare cele trei modalitati de inserare.
c1. Inserarea unui nod inainte de primul nod din listaSe creaza nodul q si se realizeaza legatura dintre el si lista. Apoi acesta va fi noul prim nod.
c2. Inserarea unui nod dupa ultimul nod din listaSe creeaza nodul q si se realizeaza legatura dintre el si ultimul nod din lista. Apoi acesta va fi noul ultim nod.
Observatie:Pentru a insera un nod inainte sau dupa un nod dat, t, se rationeaza analog ca la listele simplu inlantuite doar ca trebuie avuta in vedere legatura dubla care trebuie facuta atat
in stanga, cat si in dreapta noului nod. Lasam spre exercitiu implementarea acestui mod de inserare.
Stergerea unui nod din lista
d1. Stergerea primului nod din lista
NOD aux;aux=p;p=p->dr;p->st=0;free(aux);
d2. Stergerea ultimului nod al listeiNu mai e nevoie de parcurgerea listei pana la penultimul nod deoarece avem acces la el pornind de la ultimul:
NOD aux;aux=u;u=u->st;u->dr=0;free(aux);
d3. Stergerea unui nod cu informatia data, x:Se parcurge lista pana la nodul anterior celui cu informatia x si acesta se leaga in lista de cel urmator celui cu informatia x:
