structuri de date în java (i) -...

1

Structuri de Date în JAVA (I)

● Prezentare curs şi laborator● Fazele dezvoltării de software● Originea limbajului Java● Specificaţii, design, implementare● Pe scurt despre excepţii● Analiza timpului de rulare● Citirea şi scrierea la consolă● J2SE API (Application Programming Interface)● Reguli de scriere a codului● JavaDoc

2

PrezentareCurs:

● Honorius Gâlmeanu, galmeanu@vega.unitbv.ro

Bibliografie: ● Michael Main, “Data Structcures and Other

Objects using JAVA”, Addison Wesley, 2003● Bruce Eckel, “Thinking in Java”,

http://mindview.net/Books/TIJ4

Notare:● 10% prezenţa la curs● 40% laborator (notare la fiecare oră)● 50% colocviu final

3

Fazele dezvoltării software

● structuri de date – colecţii organizate după o regulă generală

● exemple – array – care este regula ?

Fazele de dezvoltare● specificarea problemei● proiectarea soluţiei● implementarea

● analiza soluţiei găsite● testarea şi depanarea● întreţinerea şi evoluţia

Fazele se confundă într-un proces iterativ

4

Originea limbajului JAVA

Sun Microsistems, 1991 (James Gosling)

lists.java (fişier text)class lists{

protected int i;public s tatic void main (String[]

args){

// code follows here// ...

}// ...

}

Java Runtime Environment (JRE)

Hardware de calculator

lists.class (JAVA bytecodes)3A 25 00 45 34 98 ...34 55 76 FE D5 3A ...

5

Specificaţii, design, implementarespecificaţii = descrierea exactă a problemei de rezolvat

(concret) Realizarea unui convertor de temperatură Celsius - FarenheitCELSIUS FARENHEIT-------------------------------- 30.00 Temperatura- 20.00 echivalentă- 10.00 va fi afişată 0.00 aici 10.00 20.00 30.00-------------------------------

Farenheit=95⋅Celsius32

6

● algoritm = procedură sau secvenţă de instrucţiuni cu ajutorul cărora se rezolvă o problemă dată

● exprimarea algoritmului se face de regulă în limbaj pseudocod

● descompunerea problemei (metode)➔ conversia de temperatură➔ tipărirea tabelului valorilor

procedure convertor (t, step)tipăreşte capul de tabelfor i = 1 to 7 do

c = t + (i – 1) * 10f = 9 * c / 5 + 32tipăreşte c, “C”, un spaţiu, f şi “F”

tipăreşte finalul de tabel

observaţi stilul de scriere

şialinierea

algoritmul

7

● descompunerea problemei în subtask-uri➔ reutilizarea codului (metodă genrică de tipărire)➔ uşurinţa modificărilor➔ ascunderea informaţiei (ascunderea implementării)

● semnătura unei metode Java:

// conversia temperaturii din grade Celsius în Farenheitpublic static double celsiusToFarenheit (double c)

tip returnat numele metodei parametri

8

● specificaţiile metodei

// converteşte temperatura din Celsius în Farenheit // @params// double c – temperatura în grade Celsius// @returns// temperatura convertită în grade Farenheit// @throws IllegalArgumentException// dacă temperatura este mai mică decât cea mai mică// temperatură permisă – zero absolut, 273,16public static double celsiusToFarenheit (double c){

// ...}

9

1: public class SampleThrow 2: { 3: public int test (int x) 4: { 5: if( x < 0 ) 6: throw new IllegalArgumentException (); 7: 8: return 1; 9: }10: 11: public static void main (String[] args)12: {13: //try14: //{15: SampleThrow st = new SampleThrow ();16: System.out.println (st.test (0));17: System.out.println (st.test (-1));18: //}19: //catch( IllegalArgumentException e)20: //{21: // System.out.println ("argument invalid");22: //}23: }24: }25:

1Exception in thread "main" java.lang.IllegalArgumentException at SampleThrow.test(int)

(SampleThrow.java:6) at SampleThrow.main

(java.lang.String[])(SampleThrow.java:17)

Rezultatele rulării:

10

Analiza timpului de rulare● analiza de timp = descrierea calitativă a 'vitezei' algoritmului

Bob urcă în turnul Eiffel cu intenţia de a număra câte trepte are acesta. Se foloseşte de un creion şi o hârtie. Punerea unui semn pe hârtie sau acţiunea de a coborî / urca o singură treaptă se numeşte operaţie.

Trei variante:● Metoda 1:

➔ urcă până sus; pentru fiecare treaptă urcată sau coborâtă pune câte un semn;

11

● Metoda 2:➔ lasă hârtia la baza turnului; pentru prima treaptă, o urcă,

îşi lasă şapca pe ea, o coboară; face un semn pe hârtie; apoi, de fiecare dată va urca până îşi găseşte şapca, mai urcă o treaptă, mută şapca aici, coboară; ajuns jos, pune un semn pe hârtie; repetă acţiunile până nu mai găseşte noi trepte;

● Metoda 3:➔ strigă către Pierre, care se află în turn, “Câte trepte are

turnul ?”, notează răspunsul pe hârtie – 2689 trepte, adică face 4 semne.

Pentru fiecare metodă, numără semnele pe care le-a pus pe hârtie.

Ne interesează efortul depus – câte operaţii a realizat.

12

Fie n numărul de trepte ale turnului. Cu n notăm de regulă mărimea cazului.

● Metoda 1:➔ urcă n trepte➔ pune, la fiecare treaptă urcată, câte un semn, în total n

semne➔ coboară n treptetotal: n + n + n = 3n (operaţii)

13

Fie n numărul de trepte ale turnului. Cu n notăm de regulă mărimea cazului.

● Metoda 2:➔ treapta 1: urcă 1 treaptă, coboară 1 treaptă, pune 1 semn➔ treapta 2: urcă 2 trepte, coboară 2 trepte, pune 1 semn➔ . . .➔ treapta n: urcă n trepte, coboară n trepte, pune 1 semntotal:

1 + 2 + ... + n + n +(n-1) + ... + 1 + n ---------------------------(n+1)+(n+1) + ... +(n+1)+ n = n(n+2)

14

Fie n numărul de trepte ale turnului. Cu n notăm de regulă mărimea cazului.

● Metoda 3:➔ scrie 4 cifre (4 operaţii)

15

Exprimăm câte operaţii se fac în funcţie de mărimea cazului – f(n)

● Metoda 1:ordin de timp liniar

● Metoda 2: ordin pătratic

● Metoda 3:ordin logaritmic

Care metodă este mai rapidă ? / Care algoritm este mai eficient ?

Cazuri extreme (comparaţi):● un maratonist aplică metoda 1, un melc metoda 2● maratonistul metoda 1, melcul metoda 3 (răzbunarea

melcului)

f n=3n

f n=n22n

f n=[ log10 n]1

16

17

Exemplu – citire şi scriere la consolăimport java.io.*;public class Additive{ public static void main (String[] args) { System.out.println ("Calculul sumei a doua numere"); InputStreamReader stdin = new InputStreamReader (System.in); BufferedReader console = new BufferedReader (stdin); String s; float a = 0, b = 0;

18

try { System.out.print ("Introduceti a: "); s = console.readLine (); a = Float.parseFloat (s); System.out.print ("Introduceti b: "); s = console.readLine (); b = Float.parseFloat (s); } catch (IOException ioex) { System.out.println ("Input error"); System.exit (1); } catch (NumberFormatException nfex) { System.out.println ("\"" + nfex.getMessage () + "\"" + " is not numeric"); System.exit (1); } System.out.print (a + " + " + b + " = "); String result = String.format ("%1$07.3f", a+b); System.out.println (result); }}

19

Java 2 Standard Edition (J2SE) API

20

Reguli de scriere a codului● după modificare, neapărat testaţi programul● nu modificaţi mult fără a testa● impuneţi verificări a parametrilor primiţi● stabiliţi test cases pentru cât mai multe situaţii● după o modificare rulaţi toate test case-urile anterioare● metode cât mai scurte, descrise clar● comentaţi la fiecare început de operaţie● respectaţi alinierea codului (2 spaţii)● syntax highlighting● unit testing (testare pe bucăţele)● trataţi toate situaţiile particulare care pot apărea

21

/** Exemplu de aruncare a unei exceptii */public class SampleThrow{ /** Verifica daca un intreg este negativ @param x intregul respectiv @throws IllegalArgumentException daca numarul este negativ @return 1 in cazul in care reuseste */ public int test (int x) { if( x < 0 ) throw new IllegalArgumentException ("x < 0"); return 1; }

// comentariile de genul acesta nu se proceseaza in JavaDoc // ...}

Documentarea codului (JavaDoc)

22