CURSUL 1 vermanfmi.unibuc.ro [602458]

CURSUL 1 – [anonimizat]

PROGRAMA

 Introducere în limbajul Java
◦ Elemente de bază
◦ Colecții. Tipuri generice
◦ Aplicații – arbori, grafuri
◦ Extinderi , interfețe , awt
 Introducere în algoritmi
 Tehnici de programare:
◦ Greedy
◦ Divide et Impera
◦ Programare dinamica
◦ Backtracking
◦ Branch and Bound
 Algoritmi probabiliști. Algoritmi genetici
 Algoritmi nedeterminiști. NP -comp letitudine
 Principiul lui Dirichlet

BIBLIOGRAFIE

1. Horia Georgescu. Tehnici de programare . Editura Universității din București 2005
2. Jon Kleinberg, Éva Tardos, Algorithm Design , Addison -Wesley 2005
http://www.cs.princeton.edu/~wayne/kleinberg -tardos /
3. T.H. Cormen, C.E. Leiserson, R.R. Rivest – Introducere în algoritmi , MIT Press, trad.
Computer Libris Agora
4. Leon Livovschi, Horia Georgescu. Sinteza și analiza algoritmilor . 1986
5. http://infoarena.ro/
6. http://community.topcoder.com/tc
7. http://www.oracle.com/technetw ork/java/javase/documentation/index.html
8. Horia Georgescu. Introducere în universul Java . Editura Tehnică București 2002
9. Ivor Horton – Beginning Java 2, Java 7 Edition , Wiley Pub., 2011
10. Ștefan Tanasă, Cristian Olaru, Ștefan Andrei, Java de la 0 la expert , ediția a II -a, Polirom
2007
11. M. Naftalin, P. Wadler – Java Generics and Collections , O’Reilly, 2007

Principalele surse pentru materialele prezentate la curs sunt [1] , [2], [8 ], [9].

CURSUL 1 [anonimizat]

2 Limbajul JAVA

Cuprins curs

Caracteristici
Un prim exemplu
ELEMENTE DE BAZĂ ALE LIMBAJULUI JAVA
 Comentarii
 Constante (literali) , variabile și tipuri primitive
 Operatori
 Instrucțiuni
CLASE
TABLOURI UNIDIMENSIONALE
TABLOURI MULTIDIMENSIONALE
CITIREA DE LA TASTATURĂ
CLASE ÎNFĂȘURĂTAORE
TRANSMITEREA PARAMET RILOR
ARBORI BINARI

CURSUL 1 [anonimizat]

3 Limbajul JAVA

Caracteristici :

 Orientat pe obiecte

 Simplitate

 Compilare prealabilă urmată de executare pe mașina gazdă

 Colectorul de reziduuri . Java permite crearea explicită de obiecte (de tipul unei clase).
Distrugerea acestor obiecte este preluată de colectorul de reziduuri (garbage collector ), care
marchează obiectele ce nu mai sunt folosite și eliberează spațiul ocupat de ele; eliberarea nu se
face neapărat imediat, ci periodic sau atunci când spațiul disponibil curent nu mai poate
satisface o nouă cerere de alocare de memorie.

 Securitate ridicată .
 lipsa pointerilor face ca accesarea unor zone de memorie pentru care accesul nu este
autorizat să nu fie posibilă.
 limbajul obligă programatorul să prevadă acțiunile ce trebuie întreprinse la diferitele
erori (numite excepții ) posibile.
 se verifică permanent, la executare, val orea indicelui unui tablou înainte de accesarea
componentei respective.

 Este proiectat pentru lucru în rețea .

 Posibilitatea lansării mai multor fire de executare .

 Extensibilitate . Limbajul Java permite includerea de metode native , adică de funcții scrise în alt
limbaj (de obicei C++). Metodele native sunt legate dinamic la programul Java la momentul
executării, rolul lor fiind în principal de a mări viteza de executare pentru anumite secvențe din
program.

 Applet -uri. Programele Ja va se împart în do uă categorii:
 programe obișnuite, de sine stătătoare ( stand alone ), numite aplicații .
 applet -urile. Este folosit același limbaj, dar diferă modalitatea de lansare în executare.
Când utilizatorul vizualizează o pagină Web ce include un applet, mașina la c are este
conectat transmite applet -ul mașinii gazdă, care este cea pe care se execută applet -ul (se
presupune că mașina pe care lucrează utilizatorul are un interpretor Java).

CURSUL 1 verman@fmi.unibuc.ro

4 Un prim exemplu :
Exempl u Afișarea unui mesaj
class Unu{
public static void main(String arg[]) {
System.out.println("Prima clasa");
}
}
Salvăm codul într -un fișier cu numele Unu.java (codul se poate scrie în orice editor și se
salvează cu extensia java)
Compilarea : javac Unu.java
În urma compilării i a naștere fișierul Unu.class ; mai general, pentru orice unitate de
compilare (formată din mai multe clase), va lua naștere pentru fiecare clasă un fișier având numele
clasei și extensia class ). Pentru acest fișier putem comanda executarea sa apelând interpretorul
java.exe astfel (pentru clasa care conține metoda main)
Rularea : java Unu

ELEMENTE DE BAZĂ ALE LIMBAJULUI JAVA

 Comentarii

Există trei tipuri de comentarii:
– de sfârșit de linie: încep cu // și se termină la sfârșitul liniei;
– generale : încep cu /* și se termină la prima succesiune */.
– de documentare : încep cu /** și se termină la prima succesiune */. Acest tip de
comentariu poate fi plasat doar imediat înaintea unei cla se, unui membru al unei clase sau a
unui constructor. Utilitarul javadoc este capabil să colecteze comentariile de documentare
din codul sursă al claselor și să le introducă în documente HTML.

 Constante (literali) , variabile și tipuri primitive
În Java, ca și în C sau C++, o variabilă se poate declara prin tipul ei urmat de nume.
[modificatori] tip lista_identificatori;

Tipul unei variabile poate fi un tip primitiv sau un tip referință (vectori, clase, interfețe).
Menționăm pentru moment doar u rmătorii modificatori:
– modificatori de acces (public, private, protected ); dacă nu este specificat
nici unul dintre acești modificatori, se consideră că este atașat un modificator implicit;
– static ;
– final .
În funcție de locul în care sunt declarate, variabile se împart în următoarele categorii:
1. Variabile membre (câmpuri) , declarate în interiorul unei clase, vizibile pentru toate metodele
clasei respective si pentru alte clase, în funcție de nivelul lor de acces.

CURSUL 1 verman@fmi.unibuc.ro

5 2. Variabile locale , declarate într-o metodă sau într -un bloc de cod, vizibile doar în metoda/blocul
respectiv
3. Parametrii metodelor , vizibili doar în metoda respectivă
4. Parametrii de la tratarea excepțiilor
Enumerăm în continuare tipurile primitive (de bază )
 Tipuri întregi – byte, short, int, long
 Tipuri în virgulă mobilă – float, double
 Tipul boolean
 Tipul char
 Tipuri întregi
 byte (octet) – 1 octet
 short (întreg scurt) – 2 octeți, valoare maximă 32767
 int (întreg) – 4 octeți, valoare maximă 2109
 long (întreg lung) – 8 octeți, valoare maximă 91018

Tip Nr
octeți Valoare minimă Valoare maximă
byte 1 -128 127
short 2 -32768 32767
int 4 -2.147.483.648 2.147.483.647
long 8 -9.223.372.036.854.775.808 9.223.372.036.854.775.807

Literali întregi
 normali (de tip int) – reprezentați pe 32 de biți
 lungi (de tip long) – reprezentați pe 64 de biți, identificați prin faptul că au sufixul 'l' sau
'L'.
int x = 456789;

long z1 = 49999999999999L;
long z2 = 49_999_999_999_999L; // -java 7

byte y1 = 456789; //possible loss of precision
byte y2 = 1;
Baze :
 10
 16 – prefixul 0x sau 0X
 8 – prefixul 0
 2 (din versiunea 7) – prefixul 0b sau 0B
int x1 = 0xA1B;
System.out.println(x1);
int x2 = 0B101; // -java 7
System.out.println(x2);
În calcule tipurile byte și short sunt convertite la int.

CURSUL 1 verman@fmi.unibuc.ro

6  Tipuri în virgulă mobilă
 float – 4 octeți
 double – 8 octeți.

Literali reali (în virgulă mobilă)
 dubli – reprezentați pe 64 de biți, pentru care scrierea este cea uzuală.
– numere zecimale ce conțin opțional punctul zecimal și pot fi urmate de un
exponent prefixat cu e sau E: 21.0 21. 2.1e1 .21E2
 normali – reprezentați pe 32 de biți, au în plus sufixul 'f' sau 'F'.
double d = 12345.2;
float f = 12345.2; //possible loss of precision
float f = 12345.2f;
 Tipul boolean
Variabilele de acest tip pot lua doar valorile true și false .
 Tipul char
 Variabilele de acest tip sunt reprezentate pe 16 biți (2 octeți) și pot primi ca valoare orice
simbol din codul Unicode.
 O variabilă de tip caracter poate fi folosită oriunde poate apărea o valoare întreagă: este
considerat numărul său de ordine în setul de caractere Unicode.
 Un caracter poate fi reprezentat oriunde în textul sursă și printr -o așa numită "secvență
Escape", a vând forma \uhhhh sau \Uhhhh , unde am notat prin h o cifră hexazecimală
 Secvențele escape pot fi folosite pentru a înlocui caractere speciale sau acțiuni.
Exemple :
Secvența Utilizare
\b backspace
\t tab orizontal
\n line feed (linie nouă)
\" ghilimele
\' apostrof
\\ backslash
\uhhhh caracter Unicode numărul hhhh (în baza 16)

char c='a';
char c1=' \u0061';
System.out.println(c1);

 Operatori

 Operatori aritmetici + – * / %

Reguli
– orice valoare ce depășește limita admisă este redusă modulo această limită
– împărțirea întreagă se face prin trunchiere

CURSUL 1 verman@fmi.unibuc.ro

7 – operatorul % este definit prin: (x/y)*y+x%y==x

double x = 5*2/4+8/6;
System.out.println(x);

– Dacă într -o expresie apar doar variabile de tip short sau byte , acestea sunt convertite la
int și apoi se evaluează expresia, rezultatul fiind de tip int

byte a = 10, b = 13;
a = (byte)(a*b);
System.out.println(a);

– Dacă într -o expresie apare o variabliă de tip long , toate variabilele sunt convertite la long

 Operatorii de incrementare și decrementare ++ și –, care pot fi aplicați operanzilor
numerici (întregi sau în virgulă mobilă) atât în formă prefixată cât și în formă postfixată.
Diferența între x++ și ++x constă în faptul că incrementarea este realizată după, respectiv
înainte de utilizarea lui x în contextul în care apare
double y = 3.5;
System.out.println(y++);
System.out.println(++y);

char c = 'a';
System.out.println(++c);
System.out.println(c+1);

 Operatorii de atribuire = += -= /= *= %= <<= >>= >>>= &= |= ^=

 Operatorii relaționali > >= == < <= !=

 Operatori logici
¦¦ (disjuncția logică, sau) && (conjuncția logică, și) ! (negație)
cu mențiunea că la evaluare se face scurtcircuitare

 Operatori pe biți

– operatorii binari ¦ (sau) & (și) ^ (xor – sau excusiv)

1.
int f = 0b10001;
System.out.println(f);
System.out.println(f&16);

//testare bit
int mask = 0b100;
if( (f& mask) == 0)//!!!obligatoriu ()
System.out.println("bitul 3 este 0");
else
System.out.println("bitul 3 este 1");

CURSUL 1 verman@fmi.unibuc.ro

8 //setare bit
f |= mask;
if( (f& mask) ==0)// !!!obligatoriu ()
System.out.println("bitul 3 este 0");
else
System.out.println("bitul 3 este 1");

2.
a ^= b;
b ^= a;
a ^= b;

– operatorii de translație (shift): <<, >> (cu propagarea bitului de semn), >>>
int b1 = -3;
System.out.println(Integer.toBinaryString(b1));
System.out.println(b1>>1);
System.out.println(b1<<1);
System.out.println( Integer.toBinaryString(b1>>>24));
System.out.println(b1>>>24);

Observație : În clasele înfășurătoare Integer și Long există metode statice pentru operații pe biți
(exemplu: bitCount , highestOneBit ); vom reveni asupra acestor clase
 Operatorul condițional ?:
Acest operator se utilizează în expresii sub forma:
( cond ? e1 : e2 )
a cărei valoare este e1 dacă cond este true , respectiv e2 dacă cond este false ; cond
trebuie să fie o expresie de tip boolean.

 Operatori postfix
– cuprinderea între paranteze a indicilor (cu []);
– operatorul de calificare ( .) folosit pentru accesarea membrilor claselor;
– parantezele rotunde folosite pentru specificarea listei de parametri din invocări;
– operatorii postfix de incrementare/decreme ntare ++ și – de mai sus.

 Operatorul de conversie a tipurilor

(tip) expresie

byte < short < int < long < float < double

Conversii implicite : de la un tip la altul care îi urmează

 Operatorul + pentru lucrul cu șiruri

– este folosit pentru concatenarea șirurilor
– dacă un membru al unei sume este un șir de caractere, atunci are loc o conversie
implicită a celorlalți membri ai sumei (devenită acum concatenare) la șiruri de
caractere;

CURSUL 1 verman@fmi.unibuc.ro

9 – printre membrii sumei pot apărea și variabile referință ! (fiind apelată metoda
toString , de care vom discuta ulterior)

int u=2,v=4;
System.out.println(u+v+" suma");
System.out.println("suma "+u+v);

 Operatorii pentru referințe
– accesul la câmpuri (prin calificare);
– invocarea metodelor (prin calificare);
– operatorul de conversie;
– operatorii == și != ;
– operatorul condițional;
– operatorul instanceof , folosit în contextul:
ob instanceof Clasa
care produce o valoare booleană ce este true dacă și numai dacă obiectul ob este
diferit de null și este o instanță a clasei Clasa sau poate fi convertit la tipul Clasa
String sir="abc";
System.out.println(sir instanceof String);
System.out.println(sir instanceof Object);
 Precedența operatorilor

Ordinea în care are loc efectuarea prelucrărilor determinate de operatori este dată în
următorul tabel de priorități ale operatorilor (de la prioritate maximă la prioritate minimă):
– operatorii postfix
– operatorii unari de incrementare/decrementare, operatorii + și – unari, operatorul de negație !
– operatorul new de creare de obiecte și cel de conversie: (tip) expresie
– operatorii multiplicativi: * / %
– operatorii aditivi: + –
– operatorii de translație (shift)
– operatorii relaționali și instanceof
– operatorii de egalitate: == !=
– operatorul &
– operatorul ¦
– conjuncția logică &&
– disjuncția logică ¦¦
– operatorul condițional ( ? : )
– operatorii de atribuire.

Observații :
– la prioritate egală, operatorii "vecini" acționează conform reguli lor de asociativitate
prezentate în continuare;
– utilizarea parantezelor este mai puternică decât prioritatea operatorilor. Astfel, spre
deosebire de x+y*z , în (x+y)*z prima operație care va fi executată este adunarea.

CURSUL 1 verman@fmi.unibuc.ro

10  Asociativitate
Regula generală o constituie asociativitatea la stânga. Fac excepție următorii
operatori, pentru care este folosită asociativitatea la dreapta:
– operatorii unari;
– operatorii de atribuire.
– operatorul ( ? : ) .

Exemple.
1) În expresia x-y+z întâi se va efectua scăde rea și apoi adunarea;
2) Instrucțiunea:
x = y = z = 0;
este echivalentă cu:
x = ( y = (z = 0));
și are ca efect atribuirea valorii 0 variabilelor x,y,z .

 Instrucțiuni

– Instrucțiunea compusă grupează mai multe instrucțiuni prin includerea lor între acolade; ia
naștere astfel un bloc.
– Instrucțiunea de declarare asociază unei variabile un anumit tip și eventual îi atribuie o valoare
inițială; variabila devine locală celui mai interior bloc care o conține în sensul că există atâta timp
cât se execută instrucțiuni ale blocului. O instrucțiune de declarare poate să apară oriunde în
interiorul unui bloc.
Înainte de utilizarea lor, variabilele locale trebuie să fi primit valori fie prin inițializare la
declarare, fie printr -o instrucțiune de atribuire (în caz contrar va fi semnalată o eroare la
compilare).
– Instrucțiunea de atribuire conține semnul =, eventual prefixat cu un operator.
– Instrucțiunea vidă este formată nu mai din ; și nu prevede vreo prelucrare.
– Instrucțiunea prin care este creat un obiect folosește în acest scop operatorul new.
– Instrucțiunile ce controlează ordinea de executare , ca de exemplu: if-else, for, while ,
do – while

Din versiunea 5 există o formă a instrucțiunii for, pentru obiecte iterabile ( for-each ):
for (tip identificator : obiect_iterabil ) instr;
De exemplu, pentru a afișa elementele unui tablou unidimensional de numere întregi putem
folosi una din variantele

for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
sau
for(int x:a)
System.out.print(x+" ");

– Instrucțiunea break .

CURSUL 1 verman@fmi.unibuc.ro

11 – Instrucțiunea continue
– Instrucțiunea switch evaluează o expresie întreagă, a cărei valoare este folosită pentru a detecta
o secvență de instrucțiuni ce urmează a fi executată.
O primă formă a ei este:
switch (expresie ) {
case val 1 : secvență_instrucțiuni 1
. . .
case val k : secvență_ instrucțiuni k
default : secvență_instrucțiuni
}
unde:
– tipul expresiei poate fi char , byte , short sau int;
– din versiunea 7 tipul expresiei poate fi și String (și enumerare)
– val 1, …, val k sunt constante (literali sau câmpuri statice finale inițializate cu expresii
constante) de același tip cu al expresiei;
– alternativa default este opțională.
1.
int i = 2;
switch (i) {
case 1 : System.out.print("unu ");
case 2 : System.out.print("doi ");
case 3 : System.out.println("trei");
}
2.
String s = "stergere";
switch (s){
case "stergere":System.out.println("sters");break;
case "adaugare":System.out.println("adaugat");break;
default:System.out.println ("nimic");
}

– Instrucțiunea return are una dintre formele:
return;
return expresie;

CLASE

Exemplu – la curs

Clasa este unitatea de programare fundamentală în Java. Orice clasă este formată din
câmpuri, metode și constructori . Câmpurile și metodele unei clase formează împreună membrii
acelei clase.
O clasă se definește astfel:
[modificator] class NumeClasaDefinita [extends NumeClasa] [implements
NumeInterfete]{
corp;
}

Câmpurile unei clase sunt variabile atașate clasei respective și se declară astfel:

[modificatori] tip lista_identificatori;

Metodele sunt funcțiile declarate în interiorul clasei :

[modificatori] tip_returnat numeMetoda(lista_parametrii);

Lista tipurilor param etrilor, în ordinea lor de apariție, formează signatura metodei. În
aceeași clasă pot apărea mai multe metode cu același nume, dar cu signaturi diferite
Clasele sunt considerate tipuri. Entitățile al căror tip este o clasă se numesc obiecte ale clasei
respective. Se mai spune că obiectele sunt instanțieri (instanțe ) ale claselor.
Constructorii unei clase seamănă cu metodele, dar numele lor este obligatoriu numele clasei
și nu întorc valori.
 Unul dintre constructori este automat invocat la crearea unui obiect de tipul clasei
respective.
 Acțiunea constructorilor poate fi oricât de complexă, dar în principal sunt folosiți
pentru inițializarea unor câmpuri ale obiectului.
 Ca și pentru metode, p ot exista mai mulți constructori, dar cu signaturi diferite.
Această posibilitate de a exista mai mulți constructori, respectiv mai multe metode cu același nume,
dar cu signaturi diferite, poartă numele de supraîncărcare (overloading ).

Crearea obiectelor se face cu ajutorul operatorului new.

Declararea și crearea unui obiect de tipul C

C ob1; //variabila referinta – poate memora o referinta la un obiect de tip C
ob1 = new C();
sau
C ob2 = new C(1,true);

La folosirea operatorului new se întâmplă mai multe lucruri:
 se creează o nouă instanță a clasei date
 se alocă memorie pentru aceasta
 este invocat constructorul corespunzător (cu aceeași signatură cu cea din lista de
argumente).
Dacă în clasa C nu există vreun constructor (declarat explicit), se presupune că “există” totuș i un
constructor fără parametri , care nu prevede nici o acțiune . De aceea, în acest caz, la creare
trebuie folosită forma new C().

13
Invocarea metodelor:

int i = ob.met(2);
ob.met();

Observați i.
 O variabilă de tip referință poate avea valoarea null, care indică o referință către " nimic "; drept
urmare variabila nu conține o referință validă, deci nu poate fi folosită pentru a accesa
câmpuri sau invoca metode .
 Gestionarea memoriei se face automat, Java având colector de reziduuri (garbage collector). De
aceea nu este nevoie să fie dezalocată memoria ocupată de obiect.
 La invocarea metodelor se folosește apelul prin valoare
 Dacă metoda este declarată cu modificatorul static , ea poate fi invocată și prin numele clasei.
Astfel, dacă metoda met cu signatura vidă era declarată prin:
static int met() { . . . }
atunci ea putea fi invocată și prin:
C.met();
 Dacă un câmp w este decl arat cu modificatorul static , el este comun tuturor obiectelor de tipul
C, deci este memorat o singură dat ă (joacă rolul de memorie comună pentru toate obiectele ce
instanțiază clasa). În plus el poate fi referit și prin C.w
Exemplu – câmpuri și metode statice
class ExpStatic{
static int nr=1;
int x=1;
static void cresteNr(){ nr++; }
void cresteX(){ x++; } //NU static
void afis(){ System.out.println(nr+" "+x ); }

public static void main(String s[]){
ExpStatic.cresteNr();
System.out.println (ExpStatic.nr);
ExpStatic ob1,ob2;
ob1=new ExpStatic();
ob2=new ExpStatic();
ob1.cresteNr();
ob1.cresteX();
ob1.afis();
ob2.afis();
}
}

14 TABLOURI UNIDIMENSIONALE

 Definiție, declarare
Un tablou a poate fi declarat folosind una dintre următoarele modalități:
tip[] a;
tip a[];
unde tip este tipul componentelor tabloului (poate fi un tip primitiv sau un tip referință) .
Declararea unui tablou nu are drept consecință crearea sa .
Crearea tabloului a declarat mai sus trebuie făcută explicit , prin:
a = new tip[n];
unde n este o constantă sau o variabilă întreagă ce a primit o valoare strict pozitivă.

Exemplu
int a[];
a = new tip[5];
a[0] = 1;

Un tablou este un tip referință . Prin creare se obține un obiect de tip tablou (obiect numit prin
abuz de limbaj tot tablou).
Componentele tabloului pot fi referite prin a[i] , cu i luând valori în intervalul 0..n-1; dacă i
nu este în acest interval, va fi semnalată o eroare la executare. Lungimea tabloului poate fi referită
prin a.length .

Declararea și crearea pot fi făcute și simultan:
int[] a = new int[10 ];
sau printr -o inițializare efectivă, ca de exemplu:
int[] a = {0,3,2,5,1}
prin care, evident, a.length devine 5.

Câmpul length al unui (obiect de tip) tablou este un câmp constant (cu modificato rii
public și final ) de tip int; deci, odată creat, un obiect tablou nu își poate schimba
dimensiunea (numărul de componente). Pe de altă parte, variabilei referință la tablou i se poate
asocia o referință la un tablou de același tip.

Exemple
1.
int[] a = {1,2,3,4} ;
a = new int[20];
//?? a[0]

Noul tablou nu a re nici o legătură cu cel vechi.
2.
int[] a = {1,2,3,4}, b = {11,12,13}, c;
c = a; a = b; b = c;

15 Observați e O atribuire de genul b = a are altă semnificație decât copierea elementelor lui a în b
și nu poate fi folosită în acest scop. Este o atribuire de referințe , în urma acestei atribuiri
variabilele b și a vor referi același obiect (tablou). Dacă modificăm un element al lui a se modifică
și b și invers.
3. Încercați pe rând fiecare dintre cele 3 variante propuse pentru “copierea” elementelor unui
vector a în alt vector b. Justificați rezultatele afișate.

int a[] = {1, 2, 3, 4};
int b[] = new int[4]; //atentie, b trebuie alocat

// Varianta 1 – Nu are efectul dorit
b = a;

// Varianta 2
for(int i=0; i<a.length; i++)
b[i] = a[i];

// Varianta 3
System.arraycopy(a, 0, b, 0, a.length);

System.out.println(a[0]+" "+b[0]);
b[0] = 5;
System.out.println(a[0]+" "+b[0]);
a[0] = 6;
System.out.println(a[0]+" "+b[0]);

În clasa Arrays din pachetul java.util există metode utile pentru lucrul cu tablouri :
fill(int[] a, int fromIndex, int toIndex, int val)
sort(int[] a)

16 TABLOURI MULTIDIMENSIONALE

Tablourile multidimensionale trebuie g ândite ca tablouri unidimensionale ale c ăror
elemente sunt tablouri unidimensionale etc . De aceea referirea la un element al unui tablou
multidimensional a se face prin:
a[indice1]…[indicen].
1.
int[][] a = new int[5][3];
2.
int[][] a = new int[3][];
a[0] = new int[3];
a[1] = new int[4];
a[2] = new int[2];

Ia na ștere astfel un tablou de forma:

Evident, a[1].length=4.
La aceea și structur ă se poate ajunge și printr -o inițializare efectiv ă:
int[][] a = { {0,1,2}, {1,2,3,4}, {2,3} };
care în plus atribuie valori elementelor tabloului.

Dacă în referirea la un element al unui tablou unul dintre indici nu este în intervalul
corespunz ător, va ap ărea excepția IndexOutOfBoundsException .

Exemplu Afișarea elementelor unui tablou bidimensional cu for -each

int x[][]={{1,2,3,7},{4,5},{8}};
for(int[] linie:x){
for(int elem:linie)
System.out.printf("%3 d",elem);
System.out.println();
}

17 CLASE ÎNFĂȘURĂTOARE

Pentru fiecare tip primitiv există o clasă corespunzătoare, numită clasă înfășurătoare
(wrapper class ) care pune la dispoziție diverse constante și metode, de exemplu de conversie
 int – clasa Integer
 double – clasa Double
 long – clasa Long
 short – clasa Short
 byte – clasa Byte
 boolean – clasa Boolean
 char – clasa Character

În clasele înfășurătoare există câmpuri constante ( static final ) pentru - și + și "nu
este un număr":
Double.NaN
Double.NEGATIVE_INFINITY
Double.POSITIVE_INFINITY
Pentru conversia din șiruri de caractere în numere se pot folosi metode statice de tipul
parse TipNumeric aflate în clasa „înfășurătoare” corespunzătoare tipului în care vrem să facem
conversia:
String sir = "123";
int i = Integer.parseInt(sir);
double j = Double.parseDouble(sir);
System.out.println(i);
System.out.println(j);

 Legătura tip primitiv  clasă înfășurătoare

Până la versiunea 5 :
int i = 1;
Integer wi = new Integer(i);
int j = wi.intValue();
System.out.println(j);
Din versiunea – implicit ( autoboxing / unboxing )
int i = 1;
Integer wi = i;
int j = wi;
System.out.println(j);

Obserervație Nu este indicată folosirea claselor înfășurătoare în operații aritmetice, ci doar
în lucrul cu colecții

18 CITIREA DE LA TASTATURĂ

O clasă care se poate folosi pentru citirea datelor de tipuri primitive sau String este clasa
Scanner din pachetul java.util .
Această clasă se poate folosi pentru citirea din diferite surse: de la tastatură, din fișier, din
obiecte de tip String , în funcție de tipul obiectul trimis ca parametru constructorului clasei:
InputStream , File , String .
În mod predefinit un ob iect de tip Scanner citește entități delimitate prin caractere albe și
apoi încearcă să le interpreteze în modul cerut.
Pentru tipurile primitive de date există metodele nextByte() , nextShort() ,
nextInt() , nextLong() , nextFloat() , nextDouble() , nextBoolea n().
Pentru a testa dacă sunt disponibile valori de anumit tip există metode ca hasNextInt() ,
hasNextDouble() etc.
Există și metodele hasNext() și next() pentru a testa existența unei următoare entități
(fără un tip specificat), respectiv pentru citirea următoarei entități (tipul rezultatului întors de
metoda next() este String ).
Mai menționăm metodele nextLine() și hasNextLine() (utile de exemplu dacă dorim
să citim un șir de caractere care conține și spații)

Exemplu – la curs

TRANSMITEREA PARAMETRILOR

După cum aminteam, î n Java parametrii se transmit prin valoare . Pentru a înțelege ce înseamnă
acest lucru și în cazul variabilelor referință considerăm exemplele următoare.

1.
class C{
int a;
C(){ }
C(int a1){ a=a1; }
void afis(){ System.out.println(a); }
}

class TestParam{
static void modif(C ob){ //modific camp
ob.a++;
}
static void modifOb(C ob){ //modific adresa
ob=new C(5);
}
static void creste(int x){ //modific variabila de tip primitiv
x++;
}

19 public static void main(String arg[]){
int x=1;
creste(x);
System.out.println(x);
C ob=new C(1); ob.afis();
modifOb(ob); ob.afis();
modif(ob); ob.afis();
}
}

2.
import java.util.*;
class Tablou {
static void met(int[] a) {
a[0] = 7;
a = new int[5];
Arrays.fill(a,0,4,1);
}
public static void main(String[] s) {
int[] a = {1,2,3,4};
for (int i=0 ; i<a.length; i++)
System.out.print(a[i]+" ");
System.out.println();
met(a);
for (int el:a)
System.out.print(el+" ");
}
}

Exemplificăm în cele ce urmează principalele elemente de limbaj discutate implementând
parcurgerea arborilor binari folosind reprezentarea arborelui cu tablouri sau cu legături (înlănțuită).

20 ARBORI BINARI

Numim arbore un graf neorientat conex și fără cicluri (pentru alte definiții echivalente
consultați cursul de Algoritmica Grafurilor).
În foarte multe probleme referitoare la arbori este pus în evidență un vârf al său, numit
rădăcină . După alegere unui vârf drept rădăcină arborele se poate așeza pe niveluri.
Exemplu Consideră m următorul arbore și modul în care el este așezat pe niveluri prin alegerea
vârfului 5 drept rădăcină.

Reprezentarea pe niveluri a arborilor face ca noțiunile de fii / descendenți , tată / ascendenți
ai unui vârf să aibă semnificații evidente. Un vârf fără descendenți se numește frunză .

 Arbori binari

Un arbore binar este un arbore în care orice vârf are cel mult doi descendenți, cu precizarea
că se face distincție între descendentul stâng și cel drept (nu este propriu -zis un caz particular de
arbore ).
Primele probleme care se pun pentru arborii binari sunt:
– modul de reprezentare;
– parcurgerea lor.
Forma standard de reprezentare a unui arbore binar constă în:
– a preciza rădăcina rad a arborelui;
– a preciza pentru fiecare vârf i tripletul st(i) , dr(i) și info(i) , unde acestea sunt r espectiv
descendentul stâng, descendentul drept și informația atașată vârfului.
Trebuie stabilită o convenție pentru lipsa unuia sau a ambilor descendenți, ca de exemplu
specificarea lor prin simbolul .

Exemplu Considerăm de exemplu următorul arbore binar:

9
10 8 1 7 3 9 2 6 4 5
3 2 1 0
7 3 6
5 4 2
10 8 1
7 6 4 5 3 9 8 2 1

21
Presupunând că informația atașată fiecărui vârf este chiar numărul său de ordine, avem:
– rad = 1 ;
– st = (2,3,4, ,6,,,,);
– dr = (8,5, ,,7,,,9,);
– info= (1,2,3,4,5,6,7,8,9) .
Dintre diferitele alte reprezentări posibile, mai menționăm doar pe cea care se reduce la
vectorul său tata și la vectorul info . Pentru exemplul de mai sus:
tata=(,1,2,3,2,5,5,1,8) .
Problema parcurgerii unui arbore binar constă în identificarea unei modalități prin care,
plecând din rădăcină și mergând pe muchii, să ajungem în toate vârfurile; în plus, atingerea fiecărui
vârf este pusă în evidență o singură dată : spunem că vizităm vârful respectiv. Acțiunea întreprinsă
la vizitarea unui vârf depinde de problema concretă și poate fi de exemplu tipărirea informației
atașate vârfului.
Distingem trei modalități standard de parcurgere a unui arbore binar:

 Parcurgerea în preordine

Se parcurg recursiv în ordine: rădăcina, suba rborele stâng, subarborele drept.
Concret, se execută apelul preord(rad) pentru procedura:

procedure preord(x)
if x!=
vizit(x); preord(st(x)); preord(dr(x))
end

Ilustrăm acest mod de parcurgere pentru exemplul de mai sus, figurând îngroșat rădăcinile
subarborilor ce trebuie dezvoltați:
1
1, 2, 8
1, 2, 3, 5, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9

 Parcurgerea în inordine

Se parcurg recursiv în ordine: subarborele stâng, rădăcina, subarborele drept.
Ilustrăm acest mod de parcurgere pentru exemplul de mai sus
1
2, 1, 8
3, 2, 5, 1, 8, 9
4, 3, 2, 6, 5, 7, 1, 8, 9
Concret, se execută apelul inord(rad) pentru procedura:

procedure inord(x)
if x!=
inord(st(x)); vizit(x); inord(dr(x))
end

22  Parcurgerea în postordine

Se parcurg recursiv în ordine; subarborele stâng, subarborele drept, rădăcina.
Ilustrăm parcurgerea în postordine pentru exemplul de mai sus :
1
2, 8, 1
3, 5, 2, 9, 8, 1
4, 3, 6, 7, 5, 2, 9, 8, 1
Concret, se execută apelul postord(rad) pentru procedura:
procedure postord(x)
if x!=
postord(st(x)); postord(dr(x)); vizit(x)
end

Exemplu Parcurgerea arborilor binari reprezentați folosind tablouri.

import java.util.*;

class ArbBinT {
int rad, nv;
int[] st,dr; //int st[],dr[];
void creare() {
Scanner sc = new Scanner( System.in);
System.out.print("Nr. varfuri : ");
nv = sc.nextInt();
st = new int[nv];
dr = new int[nv];

System.out.print("Radacina ( numerotar e de la 0): ");
rad = sc.nextInt();

for (int i=0; i<nv; i++) {
System.out.print("fii st si dr ai varfului " + i + " ( -1 daca nu
exista): ");
st[i] = sc.nextInt();
dr[i] = sc.nextInt();
}
}

void pre(){
pre(rad);
}

void pre(int x) {
if( x>=0 ){
System.out.print(x + " ");
pre(st[x]);
pre(dr[x]);
}
}

23 void in(){
in(rad);
}

void in(int x) {
if( x>=0 ){
in(st[x]);
System.out.print(x + " ");
in(dr[x]);
}
}

void post(){
post(rad);
}

void post( int x) {
if( x>=0 ){
post(st[x]);
post(dr[x]);
System.out.print(x + " ");
}
}
}
class Exp1ArbBin {
public static void main(String[] args) {
ArbBinT ob = new ArbBinT();
ob.creare();
System.out.print("Preordi ne :\t");
ob.pre();
System.out.print(" \nInordine : \t");
ob.in();
System.out.print(" \nPostordine : \t");
ob.post();
}
}

Exemplu Parcurgerea arborilor binari reprezentați folosind legături.

import java.util.*;

class Varf{
int info;
Varf st,dr;
Varf () {
}
Varf (int i) {
info = i;
}
}

24 class ArbBinL {
Varf rad;
static Scanner sc = new Scanner(System.in);
void creare() {
System.out.print("rad : ");
rad = new Varf(sc.nextInt());
subarb(rad);
}

void subarb(Varf x) { //x – deja alocat
// ataseaza subarb. st. si subarb. dr.
int v;
// v<0 <==> nu exista descendent
System.out.print("Desc. stang al lui " + x.info + ": ");
v = sc.nextInt();
if( v>=0 ) {
x.st = new Varf(v);
subarb(x.st);
}
System.out.print("Desc. drept al lui " + x.info + ": ");
v = sc.nextInt();
if( v>=0 ) {
x.dr = new Varf(v);
subarb(x.dr);
}
}

void pre(){
pre(rad);
}

void pre(Varf x) {
if( x != null ) {
System.out.print(x.info + " ");
pre(x.st);
pre(x.dr);
}
}

void in(){
in(rad);
}

void in(Varf x) {
if( x != null ) {
in(x.st);
System.out.print(x.info + " ");
in(x.dr);
}
}

25
void post(){
post(rad);
}

void post(Varf x) {
if( x != null ){
post(x.st);
post(x.dr);
System.out.print(x.info + " ");
}
}
}

class Exp2ArbBin {
public static void main(String[] args) {
ArbBinL ob = new ArbBinL();
ob.creare();
System.out.print("Preordine : \t");
ob.pre();
System.out.print(" \nInordine : \t");
ob.in();
System.out.print(" \nPostordine : \t");
ob.post();
}
}

Temă : Modificați programul anterior astfel încât lipsa unui fiu să fie marcată la citire printr –
o literă, nu printr -o valoare întreagă negativă