pclp3_-_indrumar_de_laborator

Universitatea Transilvania din Braov

Facultatea de Inginerie Electric i tiina Calculatoarelor

Departamentul Automatic i Tehnologia Informaiei

Programarea Calculatoarelor

i Limbaje de Programare III ndrumar de laborator

prof. dr. ing. Sorin-Aurel MORARU

ef lucr. dr. ing. Dominic Mircea KRISTLY

BRAOV, 2012

Programarea calculatoarelor i limbaje de programare III

1

Cuprins

INTRODUCERE N PROGRAMAREA CALCULATOARELOR, ALGORITMI I TEHNICI DE PROGRAMARE 3

1. LUCRUL CU FLUXURI DE TIP FIIER 5

1.1. UTILIZAREA FLUXURILOR DE TIP FIIER N LIMBAJUL C/C++ 5

1.1.1. TESTAREA EXISTENEI UNUI FIIER 5

1.1.2. COPIEREA UNUI FIIER 6

1.2. UTILIZAREA FLUXURILOR N LIMBAJUL JAVA 6

1.2.1. OBINEREA VERSIUNII N TONALITI DE GRI (GRAYSCALE) A UNEI IMAGINI BMP 8

2. LISTE 11

2.1. TIPURI DE DATE 11

2.1.1. TIPURI DE DATE DEFINITE DE UTILIZATOR 11

2.1.1.1. Enumerri 11

2.1.1.2. Structuri 12

2.2. POINTERI 14

2.2.1. POINTERII I TABLOURILE 16

2.2.2. POINTERII I STRUCTURILE 16

2.2.3. GESTIUNEA DINAMIC A MEMORIEI CU OPERATORII NEW I DELETE 17

2.2.3.1. Operatorul new 17

2.2.3.2. Operatorul delete 18

2.3. LISTE 18

2.3.1. REPREZENTAREA SECVENIAL 18

2.3.2. LISTE NLNUITE 19

3. ARBORI BINARI 23

3.1. PARCURGEREA ARBORILOR 23

4. BACKTRACKING 27

4.1. PROBLEMA SRITURII CALULUI PE TABLA DE AH 28

ndrumar de laborator

2

5. ALGORITMI DE CUTARE 33

5.1. CUTAREA BINAR 33

6. ALGORITMI DE SORTARE 35

6.1. METODA BULELOR (BUBBLESORT) 35

6.2. METODA RAPID (QUICKSORT) 36

7. GRAFURI 39

7.1. MODURI DE REPREZENTARE 39

7.2. ALGORITMI PENTRU MINIMIZARE CI 40

7.2.1. DIJKSTRA 40

7.2.2. FLOYD 41

7.2.3. ARBORELE DE ACOPERIRE MINIM ALGORITMUL KRUSKAL 42

7.2.4. ALGORITMUL PRIM PENTRU AFLAREA ARBORELUI PARIAL DE COST MINIM 45


3

Introducere n programarea calculatoarelor, algoritmi i tehnici de

programare

Majoritatea problemelor practice pe care le ntlnim n fiecare zi se pot rezolva efectund un

numr finit de operaii ntr-o anumit ordine, tot timpul aceleai pentru aceiai problem. Unele

probleme (nrudite) accept aceleai tipuri de soluii, adic pot fi rezolvate urmnd aceiai pai.

Prin pas se nelege o operaie sau un raionament.

Suita de pai ce au ca scop rezolvarea unor probleme poart numele de algoritm.

Noiunea de algoritm este des ntrebuinat atunci cnd vine vorba de scrierea programelor

pentru calculator. Sistemele de calcul actuale sunt capabile doar s efectueze, foarte rapid, calcule

matematice simple, fr a nelege scopul sau sensul lor (sunt lipsite de inteligen); prin urmare

nu sunt capabile s rezolve probleme prin raionamente proprii.

Pentru a putea rezolva o problem, un program trebuie s implementeze, ntr-o form neleas

de calculator, unul sau mai muli algoritmi.

Scrierea de programe pentru calculator se realizeaz cu ajutorul limbajelor de programare.

Acestea ofer programatorului o interfa de comunicaie cu sistemul de calcul. Printre limbajele

de programare utilizate pe scar larg la ora actual pot fi menionate: C/C++, Java, C#, Visual

Basic.

Scopul unui program de calculator este de a genera anumite rezultate pe baza unor date de intrare.

Schematic, un program este asemenea unei cutii negre creia i se dau nite date de intrare i

genereaz la ieire nite rezultate.

PROGRAMDate de intrare Date de ieire

Fig. 1 Schema de principiu a unui program

Pentru a uura lucrul cu datele necesare unui program, toate limbajele de programare ofer

mecanismul de variabil. O variabil este, ntr-o definiie foarte simpl, o etichet asociat unei

adrese de memorie, deci, indirect, unei locaii de memorie.

Cea mai important caracteristic a unei variabile l constituie tipul de date asociat.

Tipul de date specific natura valorilor, modul de reprezentare a acestora i plaja de valori ce se

poate memora n zona de memorie asociat variabilei. Majoritatea limbajelor de programare ofer


4

un set redus de tipuri de date, numite de baz. Pe lng acest set, limbajele de programare

moderne ofer i mecanisme pentru crearea de noi tipuri de date (tipuri de date utilizator),

utiliznd tipurile deja existente. Printre aceste mecanisme se remarc enumerrile, structurile i

clasele.

Exist i limbaje de programare (cum ar fi Microsoft Visual Basic) care nu au dect un

singur tip de date, numit generic tipul variant. Practic, tipul variabilelor sunt extrapolate

din contextul n care apar sau sunt convertite explicit n momentul utilizrii. Astfel, o

variabil poate fi tratat att ca numr, ct i ca ir de caractere.

Majoritatea algoritmilor necesit structuri de date specifice pentru a-i putea ndeplini scopul.

Aceste structuri se obin fcnd apel la mecanismele de creare a tipurilor de date utilizator. Acest

ndrumar va trata structurile de date n mod progresiv, pe msur ce algoritmii prezentai o vor

necesita.

Unii algoritmi fac apel la metode speciale de calcul/prelucrare, denumite tehnici de programare,

majoritatea fiind mprumutate din matematic. Printre tehnicile ce vor fi utilizate n acest

ndrumar se numr: greedy, recursivitate, backtracking i divide et impera.

Etimologia cuvntului algoritm provine de la denumirea

crii Algoritmi de numero Indorum (sec. XII), care este o

traducere n latin dup Muhammad ibn Musa Khwarizmi

( Muhammad bin Ms Ab

afar al-awrazm), matematician, astronom i geograf

persan din secolul VII. Cuvntul algoritmi este traducerea

latin a numelui Al-Khwrizm (cel din Khwrizm).

Al-Khwrizm este recunoscut de muli matematicieni ca

fiind printele algebrei. El a prezentat, pentru prima dat,

un mod sistematic de rezolvare a ecuaiilor liniare i

ptratice. n Arithmetica a explicat utilizarea cifrelor arabe i

a fost printre primii matematicieni care au folosit cifra zero.

Muhammad ibn

Musa Khwarizmi


5

1. Lucrul cu fluxuri de tip fiier

Datorit faptului c informaiile prelucrate de majoritatea programelor se stocheaz pe suporturi

externe, este necesar existena unor metode de lucru cu aceste suporturi.

Un fiier reprezint un grup de octei nrudii. Un sistem de fiiere este un produs software folosit

pentru organizarea i pstrarea fiierelor pe un dispozitiv secundar de stocare.

Fiecare fiier are proprieti care l descriu. Sistemul de fiiere determin tipul proprietilor care

descriu fiierul. n mod obinuit, acesta nseamn numele fiierului, permisiunile de acces, data i

ora ultimei modificri a fiierului. n general, cele trei permisiuni de acces folosite sunt: citire /

scriere (read / write), numai citire (read-only) i execuie.

Fiierele sunt organizate n directoare i subdirectoare. Directorul aflat pe poziia cea mai nalt a

ierarhiei se numete director rdcina. De aici ncepe ntreaga ierarhie de directoare i

subdirectoare. Colectiv, directoarele i subdirectoarele formeaz structura de directoare.

1.1. Utilizarea fluxurilor de tip fiier n limbajul C/C++

Fiierele pot fi clasificate dup coninutul lor n:

fiiere text conin o secven de caractere ASCII, structurate pe linii;

fiiere binare conin o secven de octei, fr o structur predefinit.

1.1.1. Testarea existenei unui fiier

1 #include

2 void main()

3 {

4 FILE *fp;

5 if (!(fp=fopen("d:\\fisier.txt","r+b")))

6 {

7 puts("Nu pot deschide fisierul");

8 exit(1); //terminare fortata a executiei cu returnarea codului 1

9 }

10 }

Fiierul "d:\fisier.txt" este deschis pentru citire i scriere ("r+"), n mod binar ("b"). Pentru modul

"r", dac fiierul nu exist pe disc sau operaia de deschidere nu reuete (de exemplu, dac

unitatea de disc nu este pregtit), fopen() ntoarce valoarea NULL. n caz contrar deschide

fiierul, creeaz o structur FILE i ntoarce adresa sa.


6

1.1.2. Copierea unui fiier

1 #include

2 void main()

3 {

4 FILE *fps, *fpd;

5 char c;

6 if (!(fps=fopen("d:\\fin.dat","rb"))==NULL)

7 {

8 puts("Nu pot deschide fisierul sursa");

9 return;

10 }

11

12 if((fpd=fopen("d:\\fout.dat","wb"))==NULL)

13 {

14 puts("Nu pot crea fisierul destinatie");

15 return;

16 }

17

18 while (!feof(fps))

19 {

20 c=getc(fps);

21 if (!feof(fps))

22 {

23 putc(c, fpd);

24 }

25 }

26

27 fclose(fps);

28 fcolse(fpd);

29 }

Deoarece fiierele conin date oarecare, ciclul de copiere folosete funcia feof( ) pentru a

detecta sfritul de fiier. Aceast precauie nu era necesar n cazul unui fiier text (alctuit din

coduri ASCII), unde ar fi suficient testarea valorii ntoarse de getc( ) pentru a detecta caracterul

EOF. Trebuie remarcat c funcia feof() semnaleaz sfritul fiierului abia dup ce acesta a fost

ntlnit la operaia de intrare precedent. Din acest motiv, dac instruciunea if ar lipsi, n fiierul

d:\fout.dat s-ar copia n plus valoarea EOF.

1.2. Utilizarea fluxurilor n limbajul Java

Un flux, n contextul limbajului Java, este un canal de comunicaie unidirecional ntre doi actori;

unul este productor i reprezint sursa de date, iar cel de-al doilea reprezint consumatorul. Prin

prisma acestui aspect, fluxurile se clasific n:

fluxuri de intrare (prin care se primesc date n program);

fluxuri de ieire (prin care se transmit date din program).


7

De asemenea, datorit faptului c limbajul Java utilizeaz sistemul Unicode pentru tipul caracter,

ceea ce nseamn c un caracter ocup 16 bii, API-ul Java introduce dou tipuri de fluxuri:

fluxuri de caracter (pentru date de tip text);

fluxuri de octei (pentru date binare).

Fluxurile sunt implementate n clase aflate n pachetul java.io.

Clasele pentru lucrul cu fluxuri de caracter de intrare motenesc clasa abstract Reader, iar clasele

pentru fluxuri de octei de intrare motenesc clasa abstract InputStream.

Clasele pentru lucrul cu fluxuri de caracter de ieire motenesc clasa abstract Writer, iar clasele

pentru fluxuri de octei de ieire motenesc clasa abstract OutputStream.

Clasele de lucru cu fluxurile de intrare ofer metoda read() pentru a prelua date din flux, care

returneaz o valoare int. n cazul fluxurilor de caracter, aceast valoare reprezint codul Unicode

al caracterului citit, prin urmare doar cei mai puin semnificativi 2 octei sunt utilizai n mod real.

Ceilali 2 octei au tot biii 0. Pentru fluxurile de octei, doar un octet este utilizat (cel mai puin

semnificativ). Dac fluxul de intrare nu mai are date, atunci metoda read() returneaz valoarea -1.

Clasele de lucru cu fluxurile de ieire ofer metoda write().

De exemplu, lucrul cu fiiere poate fi realizat cu ajutorul claselor:

FileReader flux de caractere de intrare;

FileWriter flux de caractere de ieire;

FileInputStream flux de octei de intrare;

FileOutputStrem flux de octei de ieire.

Aceste fluxuri sunt fluxuri primitive, deoarece sunt conectate direct de sursa sau destinaia datelor.

Exist i fluxuri de procesare care se construiesc pe baza fluxurilor primitive i ofer faciliti

suplimentare. Un tip de flux de procesare este fluxul cu zona de memorie tampon ("buffered");

astfel se pot utiliza urmtoarele clase:

BufferedReader flux de caractere de intrare;

BufferedWriter flux de caractere de ieire;

BufferedInputStream flux de octei de intrare;

BufferedOutputStream flux de octei de ieire.

Un tip util de fluxuri e procesare sunt cele de conversie a fluxurilor:

InputStreamReader flux de caractere de intrare care convertete un flux de octei n flux

de caractere;


8

OutputStreamWriter flux de octei de ieire care convertete un flux de caractere n flux

de octei.

Paii de urmat n lucrul cu fluxuri sunt:

1. Deschidere flux (prin instanierea unei clase de lucru cu fluxuri)

2. Procesare date (folosind metodele specifice clasei alese pentru lucrul cu fluxuri)

3. nchidere flux (prin apelarea metodei close() a instanei clasei de lucru cu fluxuri)

Orice eroare n lucrul cu fiierele va rezulta n aruncarea unei excepii, care provine din clasa

IOException. Din acest motiv este obligatoriu ca programele care utilizeaz fluxuri s trateze

toate excepiile de acest tip.

CitireaDinFisier.java

1 importjava.util.*;

2 import java.io.*;

3

4 public class CitireaDinFisier

5 {

6 public static void main(String[] args)

7 {

8 String linie;

9 try {

10 BufferedReader in = new BufferedReader(new FileReader(

11 "\\fis.txt"));

12 while ((linie = in.readLine()) != null)

13 {

14 System.out.println(linie);

15 }

16 }

17 catch (IOException e)

18 {

19 System.out.println(e);

20 }

21 }

22 }

1.2.1. Obinerea versiunii n tonaliti de gri (grayscale) a unei imagini BMP

Formatul BMP (bitmap) este utilizat pentru stocarea informaiilor de tip grafic. Formatul definete

o parte de header, care conine informaii despre documentul de tip imagine i ocup, n mod tipic,

54 de octei, i o parte de date, care conine efectiv imaginea.

n mod tipic, pentru fiecare punct din imagine (pixel) sunt necesari 24 de bii (care definete i

adncimea de culoare), care stocheaz nivelele de intensitate pentru cele 3 componente ale culorii

(R rou, G verde i B albastru), formatul BMP utiliznd spaiul de culoare RGB. Fiecare


9

component este memorat pe un octet, astfel c intensitatea luminoas poate varia ntre 0 (lipsa

componentei de culoare) i 255 (intensitate maxim a culorii).

Pentru a obine versiunea n tonaliti de gri a unei imagini este suficient a se calcula o medie ntre

intensitile culorilor componente ale fiecrui pixel. Deoarece ochiul uman este mai sensibil la

culoarea verde, se prefer utilizarea unei medii ponderate, n care culoarea verde este

predominant. Aceast medie este folosit n calcularea luminanei (componenta Y a spaiului de

culoare YUV). Formula de calcul poate fi regsit pe linia 27 a programului.

BmpClass.java

1 package bmp;

2

3 import java.io.BufferedInputStream;

4 import java.io.BufferedOutputStream;

5 import java.io.FileInputStream;

6 import java.io.FileOutputStream;

7

8 public class BmpClass

9 {

10 public static void main(String[] args)

11 {

12 try

13 {

14 FileInputStream fis=new FileInputStream("C:\\qwerty.bmp");

15 BufferedInputStream dis=new BufferedInputStream(fis);

16 FileOutputStream sif=new FileOutputStream("C:\\qwerty1.bmp");

17 BufferedOutputStream bos = new BufferedOutputStream(sif);

18 byte[] sti=new byte[54];

19 dis.read(sti,0,54);

20 bos.write(sti);

21 while(dis.available()>0)

22 {

23 int b,g,r;

24 b=dis.read();

25 g=dis.read();

26 r=dis.read();

27 int gri=(int)(0.114*b+0.587*g+0.299*r);

28 bos.write(gri);

29 bos.write(gri);

30 bos.write(gri);

31 }

32 dis.close();

33 bos.close();

34 }

35 catch (Exception e)

36 {

37 }

38 }

39 }


10

Headerul fiierului de intrare se copiaz fr modificri, deoarece doar culorile imaginii se schimb,

nu proprietile acesteia.

Fiierul este parcurs apoi octet cu octet i grupuri de cte trei octei sunt utilizate pentru a calcula

luminana. n fiierul de ieire este nscris de trei ori luminana, ceea ce nseamn c se

nlocuiete un pixel colorat cu unul de culoare gri la intensitatea dat de luminan.

S se scrie un program care s genereze, pe baza unui fiier bitmap de intrare, trei fiiere

bitmap, care prezint separat cele trei componente de culoare.


11

2. Liste

2.1. Tipuri de date

2.1.1. Tipuri de date definite de utilizator

Acestea se obin din tipurile de baz sau din combinaii ale acestora sau chiar ale altor tipuri

utilizator.

Limbajele C/C++ pun la dispoziie o serie de mecanisme i structuri ce permit definirea unor tipuri

de date noi. Printre acestea putem meniona structurile, uniunile, enumerrile i clasele.

Noilor tipuri de date li se pot asocia nume (identificatori) fie direct, fie prin utilizarea declaraiei

typedef.

Declararea unor variabile de tip utilizator se face la fel cu cea a tipurilor predefinite. Sintaxa

general este:

Sintaxa utilizat: id_tip id_var1[, id_var2 [, ...]];

Spre deosebire de declararea variabilelor de tip predefinit, declararea variabilelor de tip utilizator

se poate face i n locul definirii tipului respectiv (n cazul n care nu se utilizeaz declaraia

typedef).

2.1.1.1. Enumerri

Se folosesc la definirea unor mulimi de constante. Cuvtul cheie care semnaleaz declaraia unei

enumerri este enum. Sintaxa este:

Format general:

enum [id_tip_nou] {nume_const_1 [=], ...} [lista_variabile];

unde:

id_tip_nou identificatorul tipului (poate lipsi);

nume_const_x identificatorul constantei x din enumerare;

valoare este valoarea atribuit constantei respective; poate lipsi, caz n care valoarea ei

va fi egal cu valoarea constantei definite anterior incrementat cu 1;

lista_variabile lista variabilelor ce se doresc a fi utilizate; aceast list poate lipsi,

fiind posibil o declarare ulterioar (n cazul n care a fost denumit noul tip).

Se pot utiliza i declaraiile de tip astfel:

typedef enum {} id_tip_nou;


12

Exemplu:

enum mVid {LASTMODE=-1, BW40=0, C40, BW80, C80, MONO=7};

Aceeai declaraie se poate scrie i astfel:

typedef enum {LASTMODE=-1, BW40=0, C40, BW80, C80, MONO=7} mVid;

Exemplu de declaraie de variabile:

mVid v1, v2;

2.1.1.2. Structuri

Structurile reprezint unul dintre cele mai puternice mijloace de definire a noi tipuri de date,

permind nglobarea mai multor variabile ntr-un ansamblu unitar. Definirea unei structuri se

realizeaz cu ajutorul cuvntului cheie struct.

Format general:

struct [id_structura]

{

[id_tip id_var[, id_var, ...]] ;

...

} [lista_variabile];

unde:

id_structura identificatorul (numele) structurii; el poate lipsi, caz n care structura va fi

anonim, nemaiputndu-se declara alte variabile de acest tip n afara celor declarate

imediat dup definirea ei;

lista_variabile list declaraii de variabile (poate lipsi).

Operatorul ; nu trebuie s lipseasc dup definirea unei structuri.

Trebuie menionat faptul c dac lipsesc att numele ct i lista de variabile, structura va fi

inutilizabil n program (nu va putea fi referit).

Declararea variabilelor de tip structur se poate realiza n dou moduri:

n locul definirii tipului structur (dac nu a fost definit cu ajutorul declaraiei typedef);

oriunde n program, utiliznd numele dat structurii ca tip al variabilei.


13

n cazul utilizrii declaraiei typedef, definirea unei structuri trebuie s respecte sintaxa:

Format general:

typedef struct

{

[id_tip id_var[, id_var, ...]] ;

...

} [id_structura];

Dup cum a fost menionat anterior, o structur grupeaz mai multe variabile de diferite tipuri

ntr-o aa-numit nregistrare (record); aceste variabile poart denumirea de membri ai structurii

i ei pot fi accesai att direct, ct i referii prin adresele lor. Practic, o variabil de tip structur va

ncorpora mai multe variabile de diferite tipuri sub un singur identificator.

STRUCTURA

Membru 1

Membru 2

Membru 3

Fig. 2 Structura grupeaz mai multe variabile sub un singur nume (identificator)

Accesul la oricare dintre membri unei variabile de tip structur se face cu ajutorul operatorului de

selecie direct ..

Sintaxa utilizat pentru accesarea unui membru al unei structuri este:

Sintaxa utilizat: nume_variabil_structur.identificator_membru

Operaia de iniializare a unei structuri respect sintaxa:

Sintaxa utilizat: id_structura id_var={, ...};

Atribuirea valorilor membrilor structurii se face exact n ordinea n care au fost aezai n definirea

tipului structura (prima valoare va fi atribuit primului membru din definiia structurii, a doua

celui de-al doilea membru, .a.m.d.).

Pentru a ilustra modul de lucru cu structurile, vom defini o structur ce va conine numele unui

student i media notelor acestuia; o vom iniializa, apoi, cu valorile Popescu Andrei pentru nume

i 9,78 pentru medie; vom afia numele i media pe ecran.


14

Student.cpp

#include

// definim structura

struct Student

{

char strNume[30];

float fMedia;

};

// programul principal

void main()

{

// declaram o variabila v1 de tip Student si o initializam

Student v1={Popescu Andrei, 9.79};

// afisam continutul structurii v1

printf(Studentul %s are media %g.\n,v1.strNume,v2.fMedia);

}

S se scrie un program care s determine vectorul sum obinut prin adunarea mai multor

vectori bidimensionali a cror componente se vor citi de la tastatur, i s se reprezinte

grafic obinerea acesteia (fiecare vector va fi reprezentat prin alt culoare).

Indicaii:

Un vector bidimensional este definit de dou componente (lund un sistem de referin

ortogonal) aa cum este prezentat n figura de mai jos:

Problema se rezolv uor dac se utilizeaz metoda triunghiului de nsumare a vectorilor.

2.2. Pointeri

Pointerul este un tip de date ce permite declararea unor variabile capabile s memoreze adresa

unei alte variabile sau a unei funcii.


15

Variabilele de tip pointer nu includ nici o informaie despre tipul datelor stocate la acea adres, de

aceea, n momentul declarrii unei variabile de tip pointer, trebuie s se specifice ctre ce tip de

date va face referire.

Pointerul indic adresa primului byte din variabila la care face referire. Prin urmare, un pointer va

ocupa acelai spaiu de memorie, indiferent de tipul de date ctre care face referire. Spaiul de

memorie ocupat de o variabil pointer poate varia ntre 16 bii i 64 de bii.

n limbajele C/C++, declararea unui pointer ctre o variabil de tip int se face astfel:

int *pVal;

Caracterul * ne indic faptul c variabila pVal este un pointer i nu o variabil de tip int.

Preluarea adresei de memorie a unei variabile se face cu ajutorul operatorului & (adres).

Accesul la coninutul variabilei referite de un pointer (coninutul zonei de memorie referite) se

realizeaz cu ajutorul operatorului * plasat naintea numelui variabilei de tip pointer. Tipul

variabilei pointer indic numrul de octei ce vor fi citii din memorie i modul cum vor fi

interpretai.

Pentru a exemplifica modul de lucru cu pointerii, vom comenta urmtorul exemplu:

1

2

3

4

5

#include

void main()

{

int val=2,*pVal;

pVal=&val;

*pVal+=5;

printf(Noua valoare a variabilei val este: %d.\n,val);

printf(Variabila val este memorata la adresa %p, ocupa %d octeti si

are valoarea %d.\n,pVal,sizeof(val),*pVal);

}

n linia 1 a funciei main() se declar dou variabile: un int (val) i un pointer ctre int (pVal).

Variabila val este iniializat cu valoarea 2.

Linia 2 determin iniializarea variabilei de tip pointer pVal cu adresa varabilei val.

O variabil de tip pointer trebuie ntotdeauna iniializat nainte de a o ntrebuina.

Pentru a specifica o non-valoare (adic variabila pointer nu conine nici o adres) se

utilizeaz constanta NULL.


16

Utiliznd pointerul pVal se modific valoarea variabilei val (coninutul de tip int aflat la adresa

specificat de pointerul pVal) n linia 3.

n linia 4 se afieaz valoarea variabilei val, care acum va fi 7.

Linia 5 afieaz adresa variabilei val (n format hexazecimal), dimensiunea n octei i valoarea de

tip int aflat la adresa dat de valoarea pointerului.

Se pot declara i pointeri generici (la care nu se specific un tip bine definit), dar n momentul

operrii asupra lor trebuie convertii n mod explicit, n concordan cu tipul datelor referite. De

exemplu , se poate scrie un program astfel:

1

2

3

4

#include

void main()

{

float PI=3.14;

void *pOrice;

pOrice=&PI;

printf(Variabila PI se afla la adresa %p si are

valoarea %g.\n,pOrice,*(float*)pOrice);

}

n momentul afirii a trebuit convertit pointerul generic pOrice ntr-un pointer ctre tipul float

(tipul variabilei referite) i apoi afiat coninutul acestei locaii de memorie.

* (float*) pOrice

pointer generic

conversia explicit n pointer ctre float

coninutul aflat la adresa de memorie indicat de pointerul obinut prin conversia pointerului generic

2.2.1. Pointerii i tablourile

Pointerii i tablourile sunt corelate strns n limbajele C/C++, o variabil tablou nefiind altceva

dect un pointer ctre primul element al tabloului.

Avnd o declaraie int Tab[10], egalitatea Tab=&Tab[0] va fi adevrat.

2.2.2. Pointerii i structurile

Ca i pentru orice alt tip de date, i pentru structuri se pot declara pointeri. Accesul la membrii

structurii se va face, n acest caz, cu ajutorul operatorului de selecie indirect -> (aa cum arat

exemplul PStruct.cpp).


17

PStruct.cpp

#include

struct Coord

{

int x,y;

};

void main()

{

Coord varf, *pVarf;

varf.x = 0;

varf.y = 1;

pVarf=&varf;

printf(Varful are coordonatele x=%d, y=%d, pVarf->x, pVarf->y);

}

2.2.3. Gestiunea dinamic a memoriei cu operatorii new i delete

Rolul esenial al pointerilor este reprezentat de gestiunea dinamic a memoriei. Cu ajutorul lor se

poate eficientiza un program din punctul de vedere al utilizrii memoriei.

n cazul n care nu se poate ti dinainte de ct memorie va avea nevoie un program, sau

cantitatea necesar depete capacitatea alocrii statice de memorie, se utilizeaz alocarea

dinamic de memorie. Aceast metod, aplicat corect, asigur utilizarea eficient a memoriei.

Metoda presupune alocarea unor zone de memorie doar n momentul n care programul are

nevoie de acestea i le elibereaz imediat ce devin inutile.

Specific acestui mod de lucru este faptul c alocarea i eliberarea memoriei cade n grija

programatorului. n acest sens, limbajul C++ pune la dispoziie doi operatori dedicai gestiunii

memoriei: new i delete.

2.2.3.1. Operatorul new

Cu ajutorul operatorului new programatorul poate aloca memorie n mod dinamic (n timpul rulrii

programului).

Sintaxa utilizat: var_pointer = new tip_alocat;

n urma unei atribuiri de acest fel se aloc o zon de memorie (n memoria heap memoria de

acumulare, adic nu aparine stivei programului) corespunztoare tipului declarat, care va putea fi

referit prin intermediul variabilei pointer var_pointer. n cazul imposibilitii alocrii de

memorie, operatorul new va returna valoarea NULL.

Operatorul new permite alocarea de memorie pentru orice tip de date.


18

Tipul variabilei pointer trebuie s coincid cu tipul furnizat operatorului new.

2.2.3.2. Operatorul delete

Orice zon de memorie alocat n mod dinamic trebuie eliberat, sarcina revenind

programatorului.

Limbajul C++ definete pentru aceast operaie operatorul delete (complementar operatorului

new).

Dei limbajele C/C++ pun la dispoziie mai multe funcii destinate lucrului dinamic cu memoria,

este indicat utilizarea n pereche a acestora; astfel, dac alocarea s-a fcut utiliznd operatorul

new, eliberarea memoriei se va face cu operatorul delete.Aceeai regul este valabil i pentru

funciile malloc() i free().

Sintaxa utilizat: delete var_pointer;

Acest apel va produce eliberarea zonei de memorie, alocat n prealabil cu operatorul new i

referit de pointerul var_pointer.

ntotdeauna trebuie pstrat o referin ctre o zon de memorie alocat dinamic. n caz

contrar, ea nu va mai putea fi eliberat, lucru ce poate conduce la consumarea memoriei

din sistem i, implicit, funcionri defectuoase ale programului ce pot bloca sistemul pe

care ruleaz.

2.3. Liste

Definiie: Listele ordonate liniar sunt structuri de date alctuite dintr-o mulime A=,A1, A2, , An}de

elemente (de obicei identice), ntre care exist o relaie determinat de poziia lor relativ. Astfel,

fiecare element Ak are un predecesor A k-1 i un succesor A k+1 (mai puin elementele prim i ultim).

Reprezentarea n memorie se poate realiza:

secvenial;

prin nlnuirea elementelor.

2.3.1. Reprezentarea secvenial

n acest tip de reprezentare, elementele sunt dispuse succesiv, ntr-o zon contigu de memorie.

Reprezentarea este similar cu cea a unui tablou (nu trebuie fcut identificarea listei cu obiectul


19

tablou n care sunt memorate elementele ei). (Un tablou este un caz particular de list, acela n

care elementul i al listei se afl memorat n tab *i+).

2.3.2. Liste nlnuite

Definiie: O list nlnuit este alctuit din noduri cu structura date i legturi n care:

cmpul DATE reprezint informaia propriu zis (un element al listei);

cmpul LEGTUR reprezint informaia de secven, legtura spre elementele adiacente

din list.

Observaie: Informaia de secven se adaug explicit pentru fiecare element, sub forma adreselor

elementelor adiacente, astfel nct ordinea listei devine independent de ordinea plasrii

elementelor n memorie.

Clasificare:

list simpl nlnuit;

list dublu nlnuit.

List simplu nlnuit - conine noduri n care este specificat legtura (adresa) spre elementul

urmtor.

Exemplu de structur nod pentru lista simplu nlnuit:

struct nlsi

{

double data; /* informaia din nodul listei */

struct nlsi *urm; /* adresa nodului urmtor */

};

Definiie: O list nlnuit n care legtura ultimului element are valoarea NULL, care marcheaz

sfritul listei, se numete lan.

Definiie: Dac legtura elementului final specific primul element se obine o list circular.

Observaie: n anumite aplicaii algoritmii sunt simplificai de utilizarea unui nod distinct, numit

nod capt, la care este ataat lista propriu-zis.

Pentru o list simplu nlnuit, ataarea unui element nou i extragerea unui element din list

sunt operaii banale i rapide, cu condiia s fie cunoscut adresa elementului precedent.

Exemplu de utilizare a listelor simplu nlnuite:

1 /* 2 cap = [inf|urm] -> [inf|urm] -> ... -> [inf|NULL] 3 */ 4 #include 5 #include 6 #include


20

7 // structura de date 8 struct Nod 9 {

10 int inf; // informatia utila, pe care dorim sa o memoram 11 Nod* urm; // adresa urmatorului Nod (un pointer catre o variabila Nod) 12 }; 13 14 // Functia returneaza numarul de elemente din lista 15 int nrElemente(Nod* lista) 16 { 17 int nr=0; 18 Nod *aux = lista; 19 while (aux!=NULL) 20 { 21 nr++; 22 aux = aux->urm; 23 } 24 25 return nr; 26 } 27 28 /* 29 Adaugare in pozitia N a unui element: 30 - daca N este 1, atunci adaugarea se face la inceputul listei; 31 - daca N este mai mare decat numarul de elemente, atunci se face adaugare 32 la sfarsit de lista. 33 Lista vida va fi simbolizata de valoarea NULL pentru capul acesteia. 34 */ 35 36 void adauga(Nod *&lista, int val, int N) 37 { 38 if (N==1 || lista == NULL) // adaugare la inceputul listei => capul

listei

39 // isi va schimba valoarea 40 { 41 Nod *aux = new Nod; // se aloca memoria necesara memorarii 42 // unei variabile de tip Nod 43 aux->inf = val; // se completeaza partea de informatie utila 44 aux->urm = lista; // urmatorul element va fi chiar vechiul cap al

listei

45 lista = aux; // noul cap al listei este noul element creat 46 } 47 else 48 { 49 int nr = nrElemente(lista); // preiau numarul de elemente din lista 50 if (N>nr+1) // daca pozitia primita ca parametru este mai mare decat 51 // numarul de elemente + 1, atunci ii modific valoarea in 52 // numar de elemente in lista + 1 53 N=nr+1; 54 55 Nod *tmp = new Nod; // creare noului nod - alocare memorie 56 tmp->inf = val; // completarea informatiei utile 57 58 // se parcurge lista pana la al N-1 -lea element 59 Nod *aux = lista; 60 for (int i=1;iurm; 62 63 // realizarea inlantuirii 64 tmp->urm = aux->urm; 65 aux->urm = tmp; 66 } 67 }


21

68 // functie de afisare a elementelor din lista 69 void afisare(Nod *lista) 70 { 71 Nod *aux = lista; // afisarea incepe de la capul listei 72 73 cout


22

131 } 132 133 void main() 134 { 135 clrscr(); // stergere ecran 136 Nod *L = NULL; // initial lista L este vida 137 int opt=0; 138 139 do 140 { 141 // se afiseaza "meniul" programului 142 cout


23

3. Arbori binari

Organizarea liniar de tip list nu este ntotdeauna cea mai adecvat pentru unele aplicaii. Astfel,

dac trebuie s descriem structura unui produs, de cele mai multe ori nu prezentm o list a

tuturor componentelor, ci utilizm o descriere ierarhic. De exemplu, din punct de vedere

constructiv, un calculator este compus din unitate central, terminal, claviatur, alte periferice.

Unitatea central are o carcas n care se afl conectori i plci, pe fiecare plac fiind montate

diverse componente - circuite integrate, condensatori, etc.

De altfel, n vederea studierii unor proprieti, aproape orice obiect poate fi descompus n alte

obiecte, mai simple. Procesul de descompunere poate fi continuat pe mai multe niveluri,

terminndu-se ns dup un numr finit de etape, dependent de natura aplicaiei. Fiecare obiect n

parte este definit printr-un set de atribute i prin mulimea obiectelor componente, care la rndul

lor, sunt descrise n acelai mod . Se observ c aceast definiie este recursiv (un obiect este

compus din mai multe obiecte) i pune n eviden o ierarhie a obiectelor.

Organizarea ierarhic este ntlnit n cele mai diverse domenii, de la organizarea administrativ a

unei ri, la planificarea meciurilor n cadrul unui turneu sportiv, de la structurarea unei cri, pn

la stabilirea ordinii de execuie a operaiilor efectuate pentru determinarea valorii unei expresii

aritmetice.

Tot o structur ierarhic este i cea a cataloagelor n care sunt grupate fiierele de pe discurile fixe

sau flexibile. Aceast organizare este impus, in principal, de raiuni de gestionare ct mai comod

a fiierelor de diverse tipuri, aparinnd diverilor utilizatori ai aceluiai sistem de calcul.

Dac toate nodurile dintr-un arbore au cel mult doi descendeni direci (fii), atunci arborele este

denumit arbore binar, iar cei doi poteniali subarbori ai unui arbore nevid sunt denumii subarbore

stng i subarbore drept.

3.1. Parcurgerea arborilor

Prelucrarea informaiilor memorate ntr-o structur de arbore implic parcurgerea arborelui, adic

inspectarea (vizitarea) fiecrui nod i prelucrarea informaiei specifice. Problema care se pune este

cea a ordinii n care se prelucreaz nodurile arborelui (rdcina i, respectiv, nodurile din

subarbori). De cele mai multe ori, aceasta este impus de specificul aplicaiei.

De exemplu, dac memorm ntr-o structur de arbore multici informaiile despre organizarea

unei societi comerciale, acest arbore poate fi parcurs n mai multe moduri, n funcie de


24

prelucrarea dorit. n cazul n care este solicitat lista personalului cu funcii de conducere, aceasta

poate fi tiprit in dou variante:

1. grupnd persoanele pe nivelurile ierarhice;

2. astfel nct s reflecte relaiile de subordonare.

n prima variant, parcurgerea arborelui se efectueaz n lime, iar n cea de-a doua n adncime.

Tot o parcurgere implic i calculul numrului de persoane angajate n fiecare compartiment

(reprezentat printr-un subarbore). Cele dou parcurgeri n adncime menionate se deosebesc

prin ordinea relativ de prelucrare a nodului rdcin i, respectiv, a subarborilor. n primul caz,

informaia specific nodului rdcin este prelucrat (tiprit) naintea informaiilor din celelalte

noduri ale (sub)arborelui. Acest tip de parcurgere este denumit parcurgere n preordine. Deoarece

numrul de persoane angajate ntr-un compartiment poate fi calculat (i eventual tiprit) numai

atunci cnd se cunoate numrul de angajai din toate compartimentele subordonate, rezult c

prelucrarea de la nivelul nodului rdcina se face dup prelucrarea restului arborelui respectiv,

deci parcurgerea se realizeaz n postordine.

Implementarea de mai jos utilizeaz recursivitatea ca tehnic de programare.

Parcurgerea arborilor binari:

1 #include 2 #include 3 4 struct ArboreBinar 5 { 6 int inf; 7 ArboreBinar *st; 8 ArboreBinar *dr; 9 };

10 11 ArboreBinar* createTree() 12 { 13 int are; 14 ArboreBinar *nod = new ArboreBinar; 15 coutnod->inf; 17 cout


25

32 33 void inordine(ArboreBinar *root) 34 { 35 if (root->st!=NULL) 36 inordine(root->st); 37 coutdr); 49 } 50 51 void postordine(ArboreBinar *root) 52 { 53 coutdr!=NULL) 67 freeTree(root->dr); 68 delete root; 69 } 70 71 void main() 72 { 73 // Pointer catre radacina arborelui 74 ArboreBinar *root=NULL; 75 76 // Crearea recursiva a arborelui 77 root = createTree(); 78 79 cout


26

95 // Eliberarea memoriei 96 freeTree(root); 97 root = NULL; 98 getch(); 99 }

S se scrie un program care parcurge un arbore binar n lime.


27

4. Backtracking

Tehnica Backtracking (a cutrii cu revenire) se poate aplica doar pentru probleme ce admit

conceptul de candidat parial de soluie i ofer un test relativ rapid asupra posibilitii ca un

astfel de candidat s fie completat ctre o soluie valid. Cnd se poate aplica, ns, backtrackingul

este adesea mult mai rapid dect cutarea prin metoda forei brute prin toi candidaii, ntruct

este capabil s elimine dintr-un singur test un mare numr de candidai.

Metoda Backtracking, n general ineficient, avnd complexitate exponenial, poate fi utilizat la

optimizarea procesului de cutare, evitnd cile care nu duc la o soluie.

n multe aplicaii, gsirea soluiilor este rezultatului unui proces de cutare sistematic, cu

ncercri repetate i reveniri n caz de nereuit. De exemplu, un ntreprinztor care dispune de un

capital C, pe care dorete s-l investeasc n vederea obinerii unui profit, va proceda n felul

urmtor: va alege dintre n oferte la care trebuie avansate fondurile f(i) i care aduc beneficiile b(i),

pe acelea pe care le poate onora cu capitalul de care dispune i care-i aduc beneficiul maxim.

Dintre problemele ale cror soluii se gsesc prin cutare menionm cteva exemple:

gsirea unei ci de ieire dintr-un labirint; plasarea pe o tabl de ah a opt dame care nu se atac ntre ele; gsirea unui traseu care acoper tabla de ah, generat adoptnd sritura calului fr a

trece de dou ori prin aceeai poziie.

n general, aceste probleme pot avea mai multe soluii.

O metod direct de gsire a soluiilor este numit metoda forei brute, care va cuta s genereze

toate submulimile de oferte. Pentru fiecare din cele 2 la puterea n submulimi distincte se

calculeaz suma investit i profitul adus. Se rein cele care nu depaesc oferta i aduc profitul

maxim.

O soluie a problemei ar fi o selecie de oferte (s_1, s_2, ..., s_n), n care s_i=1 sau s_i=0 dup cum

oferta este sau nu onorat. Soluiile acestei probleme au aceeai lungime n. Condiia s_i s

aparin lui 0 sau 1 este o restricie explicit. Condiia ca suma investit s nu depeasc capitalul

este o funcie de limitare, o restricie implicit, care restrnge numrul soluiilor.

n metoda cutrii cu revenire, soluia este constituit n mod progresiv, prin adugarea unei

componente sp+1 la o soluie parial (s1, s2, , sp) care reprezint o selecie din primele p oferte

din totalul celor n, astfel nct (s1, s2, , sp+1) s reprezinte de asemenea o soluie parial. Soluia

parial mai poate fi ntlnit i sub numele de soluie p-realizabil.


28

O soluie final este obinut n momentul n care a fost fcut o selecie dintre cele n oferte.

Aceasta este comparat cu soluia optim determinat pn acum, fiind reinut sau ignorat.

4.1. Problema sriturii calului pe tabla de ah

Se presupune existena unei table de ah de dimensiune 8x8. Trebuie s se gseasc toate

modalitile de a deplasa un cal pe aceast tabl, astfel nct calul s treac prin toate csuele de

pe tabl, fr a trece de mai multe ori prin acelai loc.

Pentru a parcurge fiecare csu de pe tabla de ah exact o dat, calul trebuie trebui s fac exact

88=64 de pai. La fiecare pas el poate alege oricare din cele 64 de csue de pe tabl. Se codific

fiecare dintre csuele de pe tabla de ah n modul urmtor: csua de la linia i i coloana j se

noteaz prin perechea (i,j). Se noteaz mulimea tuturor csuelor de pe tabl cu C: C = {(0,0),

(0,1), ..., (0,7), (1,0), ..., (7,7)}.

O soluie a problemei se poate nota printr-un vector x = (x0, x1, ..., x63), unde x S = CCC ... C

(produs cartezian n care mulimea C apare de 64 de ori), iar xi C, i {0, 1, ..., 63}.

Problema sriturii calului pe tabla de ah

1 #include

2 #include

3

4 /* Dimensiunea tablei de sah este definita ca si constanta. */

5 #define N 8

6 #define INVALID -1

7

8 int main(void)

9 {

10 /* Pentru o tabla de dimensiune N solutiile sunt memorate intr-un

11 vector de dimensiune N*N. Fiecare element din vector va fi,

12 la randul lui, un vector cu doua elemente; primul element va

13 memora linia de pe tabla, iar al doilea element va memora

14 coloana de pe tabla. */

15 int c[N*N][2];

16

17 int k, i;

18 int pe_tabla, continuare;

19 int delta_l, delta_c;

20

21 /* Sunt numarate solutiile gasite. */

22 int count = 0;

23

24 /* Pentru inceput se marcheaza toate elementele vectorului "c" cu

25 INVALID, semn ca nu a fost ales nici un element din multimile

26 produsului cartezian. */

27


29

28 for (i=0; i= 0)

36 {

37 /* Se incearca plasarea mutarii "k" a calului in fiecare

38 casuta, pe rand. Se evalueaza posibilitatea continuarii.

39 Procesul se opreste cand au fost incercate toate casutele

40 sau cand este identificata o casuta libera */

41 do

42 {

43 /* Se alege urmatorul element din multimea "C[k]".

44 Daca elementul "c[k]" este setat pe INVALID,

45 inseamna ca inca nu a fost ales nici un element din

46 multimea curenta, prin urmare se alege primul element

47 calul este plasat pe casuta (0,0) */

48 if (c[k][0] == INVALID)

49 {

50 c[k][0] = 0;

51 c[k][1] = 0;

52 pe_tabla = 1;

53 }

54 /* Daca elementul "c[k]" nu este setat pe INVALID, inseamna

55 ca deja s-a ales o casuta din multimea "C[k]". Se alege

56 urmatoarea casuta de pe tabla. Daca este posibil

57 se ramane pe aceeasi linie, deplasarea realizandu-se

58 pe coloana spre drepata. */

59 else

60 if (c[k][1] < N-1)

61 {

62 c[k][1]++;

63 pe_tabla = 1;

64 }

65 /* Daca este ultima casuta din linie, atunci se trece la

66 linia urmatoare, cu verificarea sa nu fie ultima linie

67 caz in care au fost epuizate toate casutele. */

68 else

69 if (c[k][0] < N-1)

70 {

71 c[k][1] = 0;

72 c[k][0]++;

73 pe_tabla = 1;

74 }

75


30

76 /* Daca este ultima linie a tablei, atunci se marcheaza

77 epuizarea casutelor, prin intermediul valorii zero

78 atribuita variabilei "pe_tabla". */

79 else

80 {

81 pe_tabla = 0;

82 }

83

84 /* Daca casuta "c[k]" aleasa este valida (se afla pe tabla

85 de joc),atunci se evalueaz posibilitatea continuarii */

86 if (pe_tabla)

87 {

88 /* Daca este prima mutare, atunci este valida */

89 if (k == 0)

90 continuare = 1;

91 /* Daca nu e prima mutare, se fac o serie de

92 verificari. */

93 else

94 {

95 /* Se verificam daca de la pozitia precedenta a

96 calului pe tabla ("c[k-1]") se poate ajunge

97 in pozitia aleasa. */

98 delta_l = abs(c[k-1][0]-c[k][0]);

99 delta_c = abs(c[k-1][1]-c[k][1]);

100 continuare = (((delta_l == 1) &&

101 (delta_c == 2)) ||

102 ((delta_l == 2) &&

103 (delta_c == 1)));

104

105 /* Se verifica daca a mai fost aleasa casuta */

106 for (i=0; continuare && (i


31

124 continuare, atunci se considera piesa asezata la pozitia

125 "c[k]" si continuam cautarea. */

126 if (continuare)

127 {

128 /* Daca s-a parcurs toata tabla de sah, atunci solutia

129 este afisata. */

130 if (k == N*N - 1)

131 {

132 for (i=0; i


32


33

5. Algoritmi de cutare

O mare gam a cercetrilor n acest domeniu urmresc obinerea minimului n strategii minimax.

n problemele privind parcurgerea combinaional a arborilor de cutare, au fost dezvoltai un

numr mare de algoritmi pentru o cutare ct mai eficient.

Algoritmii se pot grupa dup dou aspecte:

construcia unui arbore de cutare;

izolarea i cutarea doar ntr-o parte a arborelui de cutare.

Cei mai muli algoritmi de acest tip au caracter euristic. O regul euristic ofer o metod de

rezolvare a problemelor, sau o metod de cutare. Ea nu d rezultate corecte la orice moment de

timp i nu este garantat c gsete cea mai bun soluie, dar n acelai timp poate reduce timpul

de cutare. Metodele de acest tip pot fi folosite pentru reducerea mrimii arborilor de cutare n

cazurile arborilor foarte mari.

Metodele relaionale sunt metodele prin care cunoaterea este reprezentat pornind de la relaiile

ntre obiecte sub form de grafuri i reele.

Pornind de la o structur de concepte care poate fi reprezentat arborescent, naintarea spre

frunz reprezint o specializare, pe cnd apropierea de rdcin este o generalizare a conceptului.

5.1. Cutarea binar

Cutarea binar se folosete la regsirea unui element ntr-un tablou ordonat. Folosind tehnica

divide et impera, ce presupune mprirea unei probleme n subprobleme care accept acelai tip

de rezolvare, cutarea binar mparte tabloul original n dou. n funcie de valoarea elementului

de cutat se selecteaz unul dintre cele dou jumti ale tabloului (care conine valoarea cutat).

Se repet procedeul pn se gsete elementul cutat sau dimensiunea subirului este 1 (ceea ce

nseamn ca elementul nu a fost gsit).

n continuare este prezentat o implementare recursiv a cutrii binare.

Cutare binar implementare n limbajul Java (MainPrg.java)

1 package mainprg; 2 3 import java.util.Arrays; 4 import java.util.Scanner; 5 6 public class MainPrg 7 { 8


34

9 public static int cautareBinara(int[] v, int x, 10 int startPoz, int stopPoz) 11 { 12 if (startPoz


35

6. Algoritmi de sortare

n practica de zi cu zi este des necesar ca un volum de date s fie aranjat ntr-o anumit ordine (s

fie sortat).

n acest scop au fost creai algoritmi de sortare precum:

BubbleSort (metoda bulelor);

SelectionSort (sortare prin selecie);

QuickSort (sortare rapid), .a.

n continuare sunt prezentai doi algoritmi: bubblesort (algoritm de tip greedy) i quicksort (ce

utilizeaz tehnica divide et impera).

6.1. Metoda bulelor (Bubblesort)

Ideea general a acestui algoritm este de a se parcurge lista ce necesit a fi sortat i de a compara

elementele dou cte dou, interschimbndu-le dac nu sunt n ordinea corect.

Algoritmul funcioneaz n modul urmtor:

se pleac de la ipoteza c irul de sortat este sortat;

se parcurge irul i se verific dac fiecare dou elemente vecine sunt n ordinea

corespunztoare; dac se gsete o neconcordan cele dou elemente n cauz sunt

interschimbate i se memoreaz faptul c irul nu era sortat;

odat ajuni la sfritul irului, dac irul s-a dovedit a nu fi sortat, se reia procedeul; dac

nu a fost semnalat nicio neconcordan, atunci orice element ak este n relaie corect cu

vecinul su ak+1,prin urmare irul este sortat.

Acest algoritm, dei simplu, este foarte lent, necesitnd multe iteraii pentru obinerea soluiei.

Implementarea algoritmului de sortare Bubblesort ntr-un program C/C++

1 #include 2 #include 3 4 void main() 5 { 6 int TAB[100], // elementele ce vor fi sortate 7 n, // numarul de elemente: este citit de la tastatura 8 i=0, // variabila folosita pentru ciclari, pe post de contor 9 sortat; // varibila logica ce va semnaliza daca tabloul este sortat

10 11 // se citeste numarul de elemente 12 coutn;


36

14 15 // se citesc elementele 16 for (;i


37

4 int getFixedPos(int *T, int startpos, int stoppos) 5 { 6 int i=startpos, j=stoppos, mod=0; // mod=0 - de la dreapta la stanga 7 // mod=1 - de la stanga la dreapta 8 while (iT[j]) 11 { 12 // inversam elementul T[i] cu T[j] 13 int aux = T[i]; 14 T[i] = T[j]; 15 T[j] = aux; 16 // schimbam modul de lucru 17 mod = !mod; 18 } 19 20 if (mod) 21 i++; 22 else 23 j--; 24 } 25 return i; 26 } 27 28 void quicksort(int *T, int startpos, int stoppos) 29 { 30 if (startpos


38

1. Modificai programele de mai sus pentru a afia numrul de interschimbri

efectuate.

2. Realizai o comparaie ntre numrul de interschimbri realizate de fiecare

algoritm prezentat pentru un ir de numere sortat cresctor.

3. Realizai o comparaie ntre numrul de interschimbri realizate de fiecare

algoritm prezentat pentru un ir de numere sortat descresctor.


39

7. Grafuri

n faa unui mare numr de situaii, o veche obinuin ne ndeamn s trasm pe hrtie puncte

reprezentnd indivizi, localiti, corpuri chimice i altele, legate ntre ele prin linii sau prin sgei

care simbolizeaz o anumit relaie. Aceste scheme se ntlnesc peste tot i fr ndoial D. Knig

a fost primul care a propus ca astfel de scheme s se numeasc grafuri i care le-a studiat

sistematic proprietile.

Printr-un graf se nelege o mulime de noduri (numite i vrfuri) i o aplicaie definit pe aceast

mulime cu valori n aceeai mulime, care face legtura ntre aceste noduri, legturi numite arce,

care pot fi sau nu orientate.

O cale este o succesiune de noduri aleas astfel nct s existe arce care s reuneasc nodurile

respective. O cale este simpl dac toate nodurile, cu excepia primului i ultimului, sunt distincte

ntre ele.

n multe din problemele la a cror rezolvare se folosete calculatorul este necesar reprezentarea

unor relaii generale ntre obiecte. Un model potrivit n astfel de cazuri este graful orientat (dac

relaia este nesimetric) sau neorientat (dac relaia este simetric)

Un graf orientat sau digraf (prescurtare de la directed graf) G=(V,E) const deci ntr-o mulime V

de vrfuri (sau noduri) i o mulime E de arce. Un arc poate fi privit ca o pereche ordonat de

vrfuri (v,w) unde v este baza arcului iar w este vrful arcului. Se spune c w este adiacent lui v.

Un graf neorientat sau graf G=(N,R) este alctuit dintr-o mulime de noduri N i o mulime R de

muchii. O muchie este atunci o pereche ordonat de noduri (v,w)=(w,v).

Un graf este echivalent cu un digraf n care pentru fiecare arc (v,w) exist i perechea lui (w,v).

Se spune c o cale (succesiune de vrfuri) v*1+,v*2+,....,v*k+ conecteaz v*1+ i v*k+.

7.1. Moduri de reprezentare

Pentru grafuri exist dou moduri de reprezentare mai des utilizate:

matricea de adiacene i

listele de adiacene.

Alegerea uneia dintre ele trebuie fi fcut n funcie de frecvena operaiilor de acces la nodurile i

muchiile grafurilor.


40

Dat fiind G=(V,E) s considerm mulimea vrfurilor V=,1,2,3,...n- avnd elementele n ordinea

natural a numerelor prin care sunt reprezentate. Matricea de adiacene A de dimensiune n n se

poate defini prin:

A[i,j] = 1 dac [i,j] aparine lui E

0 dac [i,j] nu aparine lui E

Reprezentarea prin matrice de adiacene permite un acces rapid la arcele (muchiile) grafului fiind

util n algoritmii n care se testeaz prezena sau absena unui arc oarecare. Ea este

dezavantajoas dac numrul de arce este mai mic dect n n, caz n care memoria necesar

pentru a pstra matricea este folosit ineficient.

Reprezentarea prin liste de adiacene folosete mai bine memoria, dar determin o cutare mai

anevoioas a arcelor. n aceast reprezentare, pentru fiecare nod se pstreaz lista arcelor ctre

nodurile adiacente. ntregul arbore poate fi reprezentat ca un tablou Cap, indexat dup noduri,

fiecare element Cap[I] fiind un pointer spre lista nodurilor adiacente lui i. Memoria necesar

reprezentrii este proporional cu suma dintre numrul de noduri i numrul de arce ale grafului.

Scriei un program C/C++ sau Java care citete de la tastatur un graf i l memoreaz

folosind reprezentarea prin matricea de adiacen.

7.2. Algoritmi pentru minimizare ci

Dndu-se un digraf G=(V,E), n care fiecare arc are ca etichet un numr ne-negativ (costul su), un

vrf este considerat surs, iar altul destinatar. Problema const n determinarea cii de cost minim

de la surs la destinatar.

7.2.1. Dijkstra

Rezolvarea acestei probleme se bazeaz pe o tehnic greedy datorat lui E.W. Dijkstra. Ea const

n pstrarea unei mulimi Selectate de vrfuri ale cror distane minime fa de surs sunt

cunoscute. Iniial, Selectate conine doar vrful surs; la fiecare pas, se adaug la Selectate un vrf

a crui distan fa de un vrf din Selectate este minim. n rezolvare se utilizeaz:

un tablou Distan al distanelor minime de la surs la fiecare vrf; matrice Cost de costuri, n care Cost i, j este costul asociat arcului (i,j); dac nu exist un

arc (i,j), atunci se consider pentru Cost i, j o valoare infinit (practic, foarte mare).


41

Algoritmul Dijkstra

Algoritm GseteCiMinime(surs)

Selectate sursa

pentru toate vrfurile i de la 1 la n

execut

Distane i Cost sursa, i

pentru toate vrfurile i de la 1 la n-1

execut

gsete vrful K neselectat cu Distane K minim

adaug K la Selectate

pentru fiecare vrf j neselectat

execut

Distane j min ( Distane j ,

Distane K + Cost K, j )

Realizai implementarea algoritmului Dijkstra ntr-un program C/C++ sau Java.

7.2.2. Floyd

Algoritmul de aflare a cilor minime dintr-un punct poate fi repetat lund ca surs fiecare din

nodurile unui graf. Aceasta permite calculul unui tablou al drumurilor minime ntre toate perechile

de noduri ale grafului. O astfel de tehnic este cea datorat lui R. W. Floyd.

Implementarea algoritmului Floyd n C/C++:

1 int floyd(int *A) 2 { 3 int k, i, j; 4 5 for (k = 1; k


42

Calculul distanelor minime se face n n iteraii. La iteraia k, A[i,j+ va avea ca valoare cea mai mic

distan ntre i i j, pe ci care nu conin vrfuri numerotate peste k (exceptnd capetele i i j ).

7.2.3. Arborele de acoperire minim algoritmul Kruskal

O metod utilizat n calcule este aceea a arborelui minim de acoperire (Kruskal). Algoritmul

construiete treptat mulimea T a muchilor arborelui minimal adugnd la fiecare pas muchia care

nu formeaz cicluri cu muchiile aflate deja n T.

Algoritmul Kruskal

T { }

ct timp T nu este arbore de acoperire

execut

{

selecteaz muchia (w,u) de cost minim din R

terge (w,u) din R

dac (w,u) nu creeaz un ciclu n T

atunci adaug (w,u) la T

}

O posibil implementare a algoritmului n limbajul de programare C/C++ este redat mai jos.

Implementarea algoritmului Kruskal n limbajul C/C++

1 #include

2 #include

3

4 void printArray(int a[][100],int n)

5 {

6 int i,j;

7 for(i = 0; i < n;i++)

8 {

9 for(j = 0; j < n;j++)

10 {

11 printf("%d\t",a[i][j]);

12 }

13 printf("\n");

14 }

15 }

16

17 void GenereazaMatriceaDeAdiacenta(int a[][100], int n)

18 {

19 int i,j;

20

21 for(i = 0;i < n; i++)

22 {

23 for(j = 0;j < i; j++)

24 {

25 a[i][j] = a[j][i]= rand()%50;

26


43

27 if(a[i][j]>40)

28 {

29 a[i][j]=a[j][i]=999;

30 }

31 }

32 a[i][i] = 999;

33 }

34 printArray(a,n);

35 }

36

37 int root(int v,int p[])

38 {

39 while(p[v] != v)

40 {

41 v = p[v];

42 }

43 return v;

44 }

45

46 void union_ij(int i,int j,int p[])

47 {

48 if(j > i)

49 p[j] = i;

50 else

51 p[i] = j;

52 }

53

54 void kruskal(int a[][100],int n)

55 {

56 int count, i, p[100], min, j, u, v, k, t[100][100], sum;

57 count = k = sum = 0;

58 for(i = 0; i < n; i++)

59 {

60 p[i] = i;

61 }

62 while(count < n)

63 {

64 min = 999;

65 for(i = 0; i < n; i++)

66 {

67 for(j = 0; j < n; j++)

68 {

69 if(a[i][j] < min)

70 {

71 min = a[i][j];

72 u = i;

73 v = j;

74 }

75 }

76 }


44

77 if(min != 999)

78 {

79 i = root(u, p);

80 j = root(v, p);

81 if (i != j)

82 {

83 t[k][0] = u;

84 t[k][1] = v;

85

86 k++;

87

88 sum += min;

89 union_ij(i,j,p);

90 }

91 a[u][v] = a[v][u] = 999;

92 }

93 count++;

94 }

95

96 if(count != n)

97 {

98 printf("Arborele de acoperire minim nu exista!\n");

99 }

100 else

101 {

102 printf("Arborele de acoperire minim este:\n");

103 for(k = 0; k < n-1 ; k++)

104 {

105 printf(" %d -> %d ",t[k][0],t[k][1]);

106 }

107 printf("\nCost = %d \n",sum);

108 }

109 }

110

111 void main()

112 {

113 int a[100][100],n;

114 printf("Introduceti numarul de noduri: ");

115 scanf("%d",&n);

116 GenereazaMatriceaDeAdiacenta(a,n);

117 kruskal(a,n);

118 }

Introducei mesaje de afiare n programul de mai sus pentru a evidenia paii parcuri n

obinerea arborelui de acoperire de cost minim.


45

7.2.4. Algoritmul Prim pentru aflarea arborelui parial de cost minim

Un alt algoritm greedy pentru determinarea arborelui parial de cost minim ale unui graf se

datoreaz lui Prim (1957). Deosebirea const n faptul c, la fiecare pas, mulimea A de muchii

alese mpreun cu mulimea U a vrfurilor pe care le conecteaz formeaz un subarbore de cost

minim pentru subgraful (U,A) al lui G (i nu o pdure ca n algoritmul lui Kruskal). Iniial, mulimea

U a vrfurilor acestui arbore conine un singur vrf oarecare din V, care va fi rdcina, iar mulimea

A a muchiilor este vid. La fiecare pas se alege o muchie de cost minim, care se adaug la arborele

precedent dnd natere la un nou subarbore de cost minim (deci exact una din extremitile ale

acestei muchii este un vrf n arborele precedent). Arborele de cost minim crete natural, cu

cte o ramur, pn cnd va atinge toate vrfurile din V, adic pn cnd U = V.

n algoritmul lui Prim, la fiecare pas, (U,A) formeaz un arbore parial de cost minim pentru

subgraful (U,A) a lui G. n final se obine arborele parial de cost minim al grafului G.

Descrierea formal a algoritmului este redat mai jos.

Algoritmul Prim

Prim (G =(V,M))

{iniializare}

A 0 {va conine muchiile arborelui parial de cost minim}

U {un vrf oarecare din V}

{Bucl greedy}

ct timp U V

execut

gsete {u,v} de cost minim astfel ca U V \ U i v U

A A {{ u , v }}

U U { u }

returneaz A

Realizai implementarea algoritmului Prim ntr-un program C/C++ sau Java.

Coperta_PCLPPCLP3_Acreditare

pclp3_-_indrumar_de_laborator

Documents