333333

INDEX GENERAL
CONCEPTE GENERALE.............................................. 2
SISTEM DE PROCESARE A DATELOR. ............................. 2
REPREZENTAREA FIZICĂ A DATELOR. ............................ 3
DEFINIȚ IA STRUCTURII DE DATE: ............................. 4
CLASIFICAREA STRUCTURILOR DE DATE: ......................... 4
OPERAȚ IUNI ASUPRA DATELOR STRUCTURATE. ..................... 7
RECURSIVITATE..................................................... 8
REGULA DE RECURSIVITATE ÎN REZOLVAREA PROBLEMELOR. ........... 9
TIPURI DE RECURSIUNE. ........................................ 10
ESTRUCTURA: PILA................................................ 13
IMPLEMENTAREA STRUCTURII PILĂ ÎN JAVA. ................. 15
STRUCTURA: COADĂ SIMPLĂ......................................... 20
IMPLEMENTAREA STRUCTURII COADA SIMPLE ÎN JAVA. .......... 21
LECTURA COMPLEMENTARIA:....................................... 27
COLOANE DE PRIORITATED ............................................ 27
STRUCTURA: COADĂCIRCULARĂ....................................... 28
IMPLEMENTAREA STRUCTURII COADĂ CIRCULARĂ ÎN JAVA. ........ 30
STRUCTURA: BI COLA............................................. 38
IMPLEMENTAREA STRUCTURII BI-COADA ÎN JAVA. .............. 39
VARIANTE ALE BI-COLAS ..................................... 48
STRUCTURA: LISTĂ SIMPLĂ........................................ 51
IMPLEMENTAREA STRUCTURII LISTĂ SIMPLE ÎN JAVA. ......... 52
STRUCTURA: LISTĂ CIRCULARĂ...................................... 64
IMPLEMENTAREA LISTEI CIRCULARE ÎN JAVA, ..................... 65
STRUCTURA: LISTA DOBLEMENTE ÎNLAZATĂ........................... 76
IMPLEMENTAREA CLASEI LISTĂ DUBLĂ ÎN JAVA, ............... 77
STRUCTURA: ÁRBORI............................................. 91
ARBORII BINARI DE CĂUTARE (ABB)) ............................ 95
IMPLEMENTAREA UNUI ARBORE BINAR DE CĂUTARE ÎN JAVA. ....... 96
 STRUCTURA DE DATE

CONCEPTE GENERALE

DEFINIȚIA COMPUTERULUI.

Computator, computer sau ordinator

este o ma ș ină electronică, capabilă să
reconcilia date de intrare,
a procesa ș i a produce informa ț ii
evident; totul acesta sub controlul
de un program de instruc ț iuni, care
este stocat anterior.

SISTEM DE PROCESARE A DATELOR.

Scopul oricărei computere este procesarea

date, aceste date pot fi: cifrele vânzărilor unui
supermercado, las calificaciones de un curso, lista de
clienț i, lista de furnizori, registrele angajaț ilor.

2 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

DEFINIȚIA DATULUI

Datele sunt o reprezentare simbolică (numerică,

alfabetică, algoritmică, etc.) a unui atribut sau variabil
cuantitativ. Datele descriu fapte empirice, evenimente ș i
entităț i.

Executarea programelor de instrucț iuni este reflectată în

schimbările de valoare suferite de datele de intrare, oferind
locul pentru datele de ieș ire (informaț ii).

În rezolvarea problemelor cu computerul. Proiectarea de

structura de date este la fel de importantă ca designul
algoritm, sau dezvoltarea ș i implementarea programului.

REPREZENTAREA FIZICĂ A DATELOR.

a.DEFINICIÓN DEBIT:

Este este unitatea de informa ț ie cea mai simplă posibilă în

sistemul binar. Înseamnă digit binar, sau ceea ce este
mismo, număr (cifrem) cu două valori posibile: 0 sau 1.

b.DEFINIȚIA DEBYTE:

Unitate de informaț ie care constă din 8 biț i echivalentă cu

un singur caracter, cum ar fi o literă, un număr sau un semn

special.

3 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

c.DEFINICIÓN DECARACTER:

Este un element luat dintr-un set de simboluri. În

care includ cifre, caracterele alfabetului ș i
câț iva caractere speciale.

{0,1,2,3,4,5,6,7,8,9,A,B,C....Y,z,¡,-,+,*}

d.DEFINTIA CUVÂNTULUI:

Conjunto de bi ț i care, ca unitate elementală, poate

manipula un computer. Lungimea în bi ț i a unei
o cuvânt într-un computer poate fi de 8, 16, 32, etc., ș i
depinde de microprocesorul unită ț ii centrale de
proces

DEFINIȚIA STRUCTURII DE DATE:

Înprogramareo structură de date este o formă de

a organiza unset de datesimple cu scopul de
facilita ț i manipularea sa. Un fapt esen ț ial este minimul
informaț ii care se află într-un sistem.

O structură de date define ș te organizarea ș i

interrela ț iece există între aceste date. În plus de un
set de operaț iuni care permite manipularea acestora.

CLASIFICAREA STRUCTURILOR DE DATE:

Într-un program, fiecare variabilă aparț ine unei structuri
de date definită explicit sau implicit, care
determină ansamblul operaț iunilor valide pentru ea.

4 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

DATE SIMPLICE (PRIMITIVE). Sunt cele care nu sunt

compuse din alte structuri:

a.Enteros, O structură de date primitivă. Membru al

următorul set de numere: {...,-(n+1), -n,...-2,-
1,0,1,2...n,n+1,...}

Opera ț iile fundamentale asupra numerelor întregi sunt: adunare,

scădere, înmulț ire, împărț ire, exponentiere ș i altele.

5 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
b.Reale, Numerele reale au întotdeauna un punct
decimal y pot fi pozitive sau negative. Un număr
real constă dintr-un întreg ș i o parte decimală, prin
exemplu, 0.08, 3789.25, -8.12, 3.0

Opera ț iile fundamentale asupra numerelor întregi sunt: adunare,

resta, multiplicare, împărț ire, exponentiere ș i altele

c.Booleanos, numit ș i logic. Este un element care

poate avea una din cele două valori: adevărat sau fals (1 sau
0).

Cei trei operatori booleani de bază sunt nu, ș i, sau

(negare, conjuncț ie ș i disjuncț ie)

d.Caracter, Un tip de date caracter conț ine doar un

caracter. se recunosc următoarele caractere
alfabetici ș i numerici:

- Caracteres Alfabéticos (A,B,C...X,Y,Z) (a,b,c,.....z)

- Caracteristici Numerice (1,2,3......,9,0)

- Caractere speciale (+,-,*,/,`,<,>,°,$,&....)

DATE STRUCTURATE. Datele simple pot fi combinate de

variante moduri de a forma structuri mai complexe, cum ar fi:

a.STRUCTURI DE DATE STATICE.

Sunt cei care au o cantitate fixă de memorie,

care este asignat în momentul creării sale ș i nu poate
se poate schimba în timpul execuț iei programului.

Exemplu.

Stringuri, Array-uri, Registres ș i Fiș iere

6 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
b.STRUCTURA DE DATE DINAMICE.

Sunt cei care nu au o cantitate fixă de memorie.

Cantitatea de memorie cre ș te sau scade
durante execuț ia programului.

Printre principalele avem

-Lineare: Stive, Cozi (simple, circulare, duble) ș i

Listes (simple, circulare, duble)

-Non-lineare: Copaci (general, binar, binar de

căutare) ș i Grafuri.

OPERATII ASUPRA DATELOR STRUCTURATE.

Operaț iile de bază sunt:

a.Inserț ii, adăugaț i o nouă valoare la

structură.

b.Eliminări, ș tergerea unei valori din structură.

c.Căutăria găsi o anumită valoare în

structura pentru a efectua o opera ț ie cu acesta
valoare, sub formăsecvenț ial(obinarioîntotdeauna ș i

când datele sunt ordonate).

d. Rute, vizitaț i fiecare dintre elementele

structură.

CONCLUZIE.

Fiecare structură oferă avantaje ș i dezavantaje în relaț ie cu

simplicitatea ș i eficien ț a pentru realizarea fiecărei
opera ț iune. În acest fel, alegerea structurii
datele adecvate pentru fiecare problemă; depinde de factori precum
frecven ț a ș i ordinea în care se realizează fiecare opera ț iune
despre date.

7 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

RECURSIVITATE
DEFINIȚIA FUNCȚIILOR.

Funcț iile sunt SUBPROGRAME (set de

instrucț iuni), care îndeplinesc o sarcină concretă ș i
returnează o valoare unică.

CARACTERISTICI ALE FUNCȚIILOR.

a) Au un nume (identificator),

b) Deț ine variabile pentru a primi date (parametrii de

entrada)

c) O funcț ie este invocată de programul principal u

alte funcț ii,

d) Rezultatul se stochează în numele funcț iei,

e) Pentru a returna o valoare se foloseș te cuvântul return.

8 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
RECULSIVITATE.

Recursivitatea nu este o
structura de date, altfel, una
tehnică de programare care
permite ca un bloc de
instruc ț iuni să fie executate un
un anumit număr de ori. Ș i
constituie o alternativă la utilizare
de buclele while, do while
pentru.

DEFINICIÓN DE RECURSIVIDAD.

Recursivitatea este un proces prin care o funcț ie se

se cheamă pe sine în mod repetat, până când este satisfăcută
o condiț ie stabilită.

REGULA DE RECURSIVITATE ÎN REZOLVAREA PROBLEMELOR.

Pentru a putea implementa soluț ia unei probleme în mod

recursiv, este necesar să se îndeplinească următoarele
condiț ii

a) Problema trebuie să fie definit în termeni de sine.

b) Problema trebuie să includă o condiț ie de finalizare

(criteriu de bază).

c) Când condiț ia de finalizare este adevărată,

funcț ia nu trebuie să se apeleze singură.

d) Problema trebuie să poată fi rezolvat într-un set finit

de paș i.

9 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

TIPURI DE RECURSIVITATE.
În func ț ie de numărul de func ț ii care trebuie utilizate, putem
diferentia

1.RECURSIVITATE DIRECTĂ.
a.RECURSIE SIMPLĂ. În recursia simplă, fiecare apel
recursiva generează, cel mult, un alt apel recursiv.

Ejemplo 1.

Implementa ț i o func ț ie recursivă în Java, care să calculeze

factorialul unui număr n .

int factorial(n)
int
{
(n==0) returna 1;
dacă
altfel întoarce n*factorial(n-1);
}

Exemplu 2.

Implementaț i o funcț ie recursivă în java, care să permită

a face împărț irea prin scăderi succesive .

int divizare(a,
int b) int
{
(b>a)
dacă întoarce 0;
altfel
returna diviziune(a-b, b)+1;
}

10 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
b.RECURSIE MULTIPLEXĂ. Unele apeluri recursive pot
genera mai multe apeluri la funcț ie.

Exemplu 3.

Implementaț i o funcț ie recursivă în java, care să calculeze

un număr din seria Fibonacci .

int fibonacci(n){
int

(n==1||n==2)
dacă returnaț i1;

altfel returnează fibonaci(n-1)+fibonaci(n-2);

2.RECURSIVITATE INDIRECTĂ.

c.RECURSIVITATEA MUTUALĂ. Implică mai mult de o funcț ie, care se

se sună reciproc.

Exemplu 4.

Implementaț i o funcț ie recursivă în java, care să determine

ș i un număr este impar .

publicboolean int par(n){

(n==0) returntrue
dacă ;
altfel returnează impar(n-1);
}

publicboolean impar(n){
int
(n==0) returnfalse
dacă ;
altfel întoarce par(n-1);
}

11 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
Exemplul 5.

Implementaț i o funcț ie recursivă în java, care să determine

ș i un număr este pozitiv .

publicboolean pozitiv(n)
int {
(n>0) returntrue
dacă ;
altfel returnează negativ(n);
}

publicboolean negativ(n){
int
(n<0) returnfalse
dacă ;
altfel returnează pozitiv(n);
}

IMPORTANȚA
Pentru a executa fiecare dintre funcț ii, trebuie să
creaț i clasa principală care va conț ine metoda main().

public classPrincipal {

public static void main(String[] args) {

int f = fibonacci(5);// apelează funcț ia.

System.out.println("x: " + f);// imprima f

12 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ESTRUCTURA: PILA

DEFINIȚIE.

Unapila (stivă) este ostructura de datelinial ș i

static, în care modul de a stoca ș i a recupera
datele sunt de tipLIFO(Ultimul intrat, primul ieș it)
primul care iese.

CARACTERISTICI.

- Pentru gestionarea datelor se dispune de două

operaț ii de bază: PUSH() ș i POP.

oPUSH(), care plasează un dată în stivă,

oPOP(), care retrage ultimul date stivuit.

- În fiecare moment se are acces doar la partea superioară

de la pila denumită TOP.
- Atât pentru căutare, cât ș i pentru traseu, se face
uso de o baterie auxiliar.

13 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

REPREZENTARE GRAFICĂ A UNEI PILI.

Structura unei PILA poate fi reprezentată prin:

- Vectores,
- Liste legate.
În acest apartament, se va face prin intermediul vectorilor sau
array„s.

ELEMENTE ALE UNEI PILI.

Implementarea acestei structuri de date se va realiza

cu utilizarea vectorilor, în această în ț elegere, cităm
elemente.

maxPila:Variable que contiene la capacidad de almacenar

date în stivă.

PILA[]:Vector care împinge datele în stivă.

TOP:Puntero care indică ultima dată din stivă.

14 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

IMPLEMENTAREA STRUCTURII PILĂ ÎN JAVA.

Doar în scopuri didactice, implementarea se realizează la
prin două clase: Principal ș i Pila.

I. CLASA PRINCIPALĂ ÎN JAVA.

Permite crearea unei stive X ș i utilizarea opera ț iunilor

definite despre ea.

public classPrincipal {

public static void main(String[] args) {

Pila p1=newPila();// creează obiectul pila.

// Adaugă codul necesar pentru rezolvarea de

// probleme cu stive
// Exemplu: System.out.println("topul: " + p1.top);
}
}

II. CLASĂ PILA ÎN JAVA.

Definiț i atributele ș i metodele specifice ale stivei.

clasa Publică Pila {

// adăugaț i aici atributele ș i metodele care
// conformarea la structura de date PILA
}

VARIABELE DIN CLASA STIVĂ [ATRIBUTELOR].

final intmaxPila= 100; // defineț i dimensiunea stivei

int[] PILA; // define un vector ce
stoca datele
inttop // defineș te pointerul stivei

15 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

DEFINIȚIA OPERAȚIUNILOR ASUPRA PILILOR [METODE].

Operaț iile care se definesc asupra unei stive sunt detaliate în

continuación:

1.OPERAȚIUNI DE STAT.
Metode care permit cunoaș terea stării actuale a stivei
cum ar fi: valoarea elementului TOP, numărul de elemente,
etc.

a.CREARE Ș I INICIALIZARE STIVĂ [CONSTRUCTOR],creaț i stiva e

initializează pointerul TOP la -1.

publicPila() {
PILA=new int[maxPila];
top= -1;
}

b.PILAVACÍA, Devuelve adevărat dacă nu există niciun

element în stivă.

public booleanpilaVacia() {
returntop == -1;
}

c.DIMENSIUNE DEPILA. Întoarceț i numărul de elemente care

deț ine pila.

public int dimensiunePila() {

returntop + 1;
}

16 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
d.PILALLENA. Întoarce adevărat dacă stiva este plină.

public booleanpilaLlena() {
returntop == maxPila - 1;
}

e.MOSTRAR ELEMENTO TOP. Returnează elementul care se

găseș te în ultima poziț ie.

public intTepe() {
returnPILA[top];
}

2.OPERAȚII FUNDAMENTALE.
Sunt metode care permit gestionarea datelor stocate
în pila:

a. INSERARE UN ELEMENT. Inserează un date pe TOP în

pilă.

public void push(int elemento) {

dacă(pilaLlena()) {
System.out.println("Pila Plină! Nu s-a putut")
adăuga.
}else{
top++;
PILA[top] = element;
}
}

17 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
b. ELIMINAREA UNUI ELEMENT. Elimină un dată prin TOP în
pilă.

public intpop() {
intelemento = 0;
dacă(pilaVacia()) {
System.out.println("Pila Vida! Nu s-a putut")
elimina.
}else{
elemento = PILA[top];
top--;
}
returnelemento;
}

3.OPERAȚIUNI SUPLIMENTARE.

Metode care permit completarea opera ț iunilor

routinare precum: inseraț i N date în stivă, imprimaț i
datele stivei, etc.

a.RECORRER PILA.Măreș te toate elementele din pila de

DIN STÂNGA ÎN DREAPTA

public void imprimaPila() {

Pila PAux = new Pila();
inta;
dacă(pilaVacia())
Sistemul.out.println("Pila Vazio! Nu se poate")
nu arăta nimic.
altfel{
while(!pilaVacia()) {

18 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
a = pop();
System.out.println(" " + a);
PAux.push(a);
}
}
// returnează datele în pila sursă
în timp ce(!PAux.pilaVacia()) {
impinge(PAux.pop());
}
}

b.CĂUTAREA DE ELEMENTE. Returnează poziț ia pe care o ocupă

element în stivă. în cazul în care nu se găseș te returnează
valoarea -1.

c. INSERARE N ELEMENTE ÎN PILE. Inserează N date prin

TOP, în pilă.

public void adaugăNelementos() {

Scanner t = new Scanner(System.in);
System.out.print("Nro. de elementos a agregar a la
PILA: ");
intn = t.nextInt();
System.out.println("ingrese los elementos:");
pentru(int i = 0; i < n; i++) {
System.out.print("Pila[" + (i + 1) + "]: ");
intx = t.nextInt();
this.push(x);
}
}

19 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ESTRUCTURA: COLA SIMPLE

Numele provine din

analogiei cu o
ventana de aten ț ie la
persoane, în care el
primul care ajunge este
primul care să fie asistat,
ș i to ț i cei care merg
ajungând, se aș ează
în continuare unul din
altul a ș teptând ca
mi-a venit rândul.

DEFINIȚIE.

O coadă este o structură de date liniară ș i statică, cu

proceduri de acces la date FIFO (Primul venit, primul servit).
Primul care intră este primul care iese, ceea ce înseamnă
că prima informaț ie care ajunge în coadă este prima care este
tratat

REPREZENTARE GRAFICĂ A UNEI COZI.

20 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
ELEMENTE ALE UNEI COZI.

maxCola:Variable que contiene la capacidad máxima de

date pe care le poate avea coada.

COLA[]:Vector que almacena los datos de la cola.

F:Frente, pointer care indică prima dată din coadă.

R:Final, pointer care indică la ultima dată din coadă.

IMPLEMENTAREA STRUCTURII DE COADĂ SIMPLĂ ÎN JAVA.

Doar în scopuri didactice, implementarea se realizează la

prin două clase: Principal ș i Cola.

I. CLASA PRINCIPALĂ ÎN JAVA.

Permite crearea unei cozi simple C1 ș i verificarea
funcț ionarea operaț iunilor definite asupra ei.

public class Principal {

public static void main(String[] args) {

Cola C1=newCola();// creează obiectul cola.

// Adaugă codul necesar pentru soluț ionarea

// probleme cu cozile

II.CLASA COADA ÎN JAVA.

Defini ț i atributele ș i metodele specifice unei cozi

simplu.

21 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

public class Cola {

// Adăugaț i aici atributele ș i metodele pe care
// va conforma structura de date COLA SIMPLĂ
}

ATRIBUTELOR COLOANEI.
Se definesc elementele cozii, cum ar fi variabilele:

public class Cola {

final intmaxCola= 100; // define dimensiunea cozii

int[]COLA; // define un vector care va stoca
datele
intF; // definează pointerii faț ă
intR; // y final de la cola

//Adăugaț i aici metodele (operaț iile) care se dezvoltă

// în clase.

OPERAȚIUNI DEFINITE ASUPRA COZILOR.

Operaț iile care se definesc asupra unui coadă simplă sunt:

1.OPERAȚ IUNI DE STAT.

a.CREARE Ș I INIȚIALIZARE COADĂ [CONSTRUCTOR].

publiccola() {
COLA =new int[maxCola];
F = -1;
R = -1;
}

22 Ing. Pascual Yana Chejo

STRUCTURA DE DATĂ
b.COLA VACÍA, Returnează adevărat dacă nu există niciun
element în coadă.

public boolean ColaVacia() {

return((F == -1) && (R == -1));
}

c.TAMAÑO DE COLA. Returnează numărul de elemente care

are coada.

public int DimensiuneCoada() {

dacă(colaVacia())
returnR - F;
return(R - F) + 1;
}

d.COLA LLENA. Devine adevărat dacă coada este plină.

public booleanColaLlena() {
return(R+1) == maxCola;
}

23 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
2.OPERATII ELEMENTARE

a.INSERARE UN ELEMENT. Inserează un element la FINAL

[R] la coadă.

public void insera(int x) {

dacă(colaPlina()) {
Cola Plină! Nu s-a putut
adicionar.
}else{
dacă((F == -1) && (R == -1)) {
R++;
COLA[R] = x;
F = 0;
}else{
R++;
COLA[R] = x;
}
}
}

b.ELIMINAREA UNUI ELEMENT. Elimină un element pe FRENTE [F]

în coadă.

public inteliminar() {
intx = -1;
dacă(colaVacia()) {
Cola Vacia! Nu s-a putut
elimina.
}else{
dacă(R == F) {
x = COLA[F];
F = -1;
R = -1;
}else{
x = COLA[F];
F = F + 1;
}
}
returnx;
}

24 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
3.OPERAȚII COMPLEMENTARE

a.RECORRER COLA.Măsură elemente ale cozii din STÂNGA

A DREAPTA

public void Recorrer() {

dacă(colaVacia()) {
System.out.println("Cola Vacia! Nu se poate")
afişaţi nimic.
}else{
cola aux =newcola();
System.out.print("COLA: ");
while(!colaVacia()) {
intx = elimina();
System.out.print(x + " ");
aux.insera(x);
}
while(!aux.colaVacia()) {
inserare(aux.elimina());
}
}
}

b.CĂUTAREA ELEMENTELOR.

Returnează poziț ia unui element în interiorul cozii. În

în cazul în care nu se găseș te, returnează valoarea -1.

public void Cautare() {

// rămâne ca sarcină pentru student
}

25 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
c.INSERTA N ELEMENTE ÎN COADA. Inserează N elemente prin
finalul în coadă.

public void InserareNElemente() {

Scanner in = new Scanner(System.in);
System.out.print("Nro.Elemente: ");
intn = in.nextInt();
System.out.println("Introduceț i elemente:");
pentru(int i = 0; i < n; i++) {
intx = in.nextInt();
insera(x);
}
}

TAREA Nr.2.

În clasa coadă simplă:

a. Dezvoltaț i o metodă care să permită afiș area primului

elementul din coadă.
b. Dezvoltaț i o metodă care să permită afiș area ultimei
elementul din coadă.
c.Dezvoltaț i o metodă care să permită căutarea unei valori în
încoadă ș i returnează poziț ia pe care o ocupă acesta în coadă.
d.Dezvoltaț i o metodă care permite eliminarea primelor N
elementele cozii.
e.Desenvelopaț i o metodă care să permită încărcarea cu N elemente
aleatorii la coadă.

26 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

LECTURA COMPLEMENTARIA:
COLA DE PRIORITATE
O coadă de priorităț i este o structură de date în care
elementele se tratează în ordinea indicată de o
prioritate asociată fiecăruia. Dacă mai multe elemente au
aceeaș i prioritate, se vor gestiona în mod convenț ional în funcț ie de
poziț ia pe care o ocupă.

Acest tip special de coada are aceleaș i operaț ii ca ș i

cozile, dar cu condi ț ia ca elementele să
se acordă în ordinea priorităț ii.

Înț elegând prioritatea ca o valoare numerică ș i alocând pentru

alte priorităț i, valori mici.

Forme de implementare:

- Adăuga ț i un câmp fiecărui nod cu prioritatea sa. Rezultă

convenabil să men ț ii coada ordonată după ordine de
prioritate.
- Crea atâtea cozi câte priorităț i există ș i stochează fiecare
element în coada sa.

Tipuri de cozi de prioritate

Cozi de priorită ț i cu ordonare ascendentă: în ele

elementele sunt inserate în mod arbitrar, dar la
ora de a îi extrage, se extrage elementul cel mai mic
prioritate.
-Cozi de priorită ț i cu ordonare descrescătoare: sunt
egale cu cozile de prioritate cu ordonare
ascendent, dar când se extrage elementul, se extrage cel de
prioritate majoră.

27 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ESTRUCTURA: COLA CIRCULAR

Eliminările care se efectuează într-o coadă simplă generează

spaț ii care nu pot fi reutilizate. Soluț ia pe care o
descrie implica reutilizarea acestor spaț ii, prin intermediul
mecanismul numit COADĂ CIRCULARĂ.

DEFINIȚIE.

O coadă circulară este o structură de date liniară ș i

statică, care permite inserarea de date în spa ț iile
generate prin metoda elimina() a clasei coadă, odată ce
că s-a atins capacitatea maximă (maxColac).

CARACTERISTICI ALE UNEI COLA CIRCULARE.

O coadă circulară este o structură de date în care

datele vor fi organizate logic într-o formă circulară.

28 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
- Eliminările, ca o coadă simplă, se efectuează
porFC(frente).
- Inserț iile se efectuează prin RD (final). Dacă se
ar fi ajuns la maxColac, se inserează în spaț ii
generateț i prin metoda elimina() .
- Pentru căutări ș i parcursuri în cozile circulare,
se foloseș te o coadă auxiliară.

REPRESENTACIÓN GRÁFICA DE UNA COLA CIRCULAR.

În această sec ț iune vor fi reprezentate cozile

circulare prin vectori sau array-uri unidimensionale.

a)

b)

29 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
ELEMENTE ALE UNEI COZI CIRCULARE.

maxColac:Variable que contiene la capacidad de la cola.

COLAC[]:Vector que almacena los datos de la cola.

FC: pointer care indică primul date din coadă.

RC: pointer care indică spre ultima dată din coadă.

IMPLEMENTAREA structurii COADĂ CIRCULARĂ ÎN JAVA.

Cu scopuri didactice, implementarea cozii circulare se
realizaț i prin intermediul a două clase: principală ș i colă circulară.

I. CLASA PRINCIPALĂ ÎN JAVA.

Creează o coadă simplă C1 ș i confirmă funcț ionarea acesteia.
operaț iuni definite asupra ei.

clasa publică Principal {

public static void main(String[] args) {

ColaCircular CC1 = newColaCircular();

// creează obiectul coadă.

// Adaugă codul necesar pentru rezolvarea

// probleme cu cozile

II.CLASSA COADA CIRCULAR ÎN JAVA.

Define ț i atributelor ș i metodelor specifice unei cozi

circular.

30 Ing. Pascual Yana Chejo

 ESTRUCTURA DE DATOS
public class ColaCircular {
// Adăugaț i aici atributele ș i metodele care
// va conforma structura de date COADA SIMPLĂ
}

ATRIBUTELOR STRUCTURII COADA CIRCULARĂ.

Se definesc elementele cozii, cum ar fi variabilele:

public class ColaCircular {

final intMaxColac= 100; // define dimensiunea cozii

int[]COLAC; // define un vector care va stoca
datele
intFC; // definează pointerii faț ă
intRC; y final de la cola

//Adăugaț i aici metodele (operaț iile) care se dezvoltă

// în clase.

OPERAȚII DEFINITE ASUPRA COZILOR.

Operaț iile care se definesc asupra unei cozi simple sunt:

1.OPERAȚ IUNI DE STAT.

a.CREARE Ș I INIȚIALIZARE COADĂ CIRCULARĂ [CONSTRUCTOR].

publicColaCircular() {
COLAC =new int[MaxColac];
FC = -1;
RC = -1;
}

31 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
b.COLA CIRCULAR VACÍĂ, Devuelve adevărat dacă nu există
niciun element în coadă.

public boolean ColaVacia() {

return((FC == -1) && (RC == -1));
}

c.DIMENSIUNE COADĂ CIRCULARĂ. Returnează numărul de elemente

ce are în coadă.

public int Dimensiune() {

dacă(ColaVacia())
return(RC - FC + MaxColac) % MaxColac;
return((RC - FC + MaxColac) % MaxColac) + 1;
}

d.COLA CIRCULAR LLENA. Devuelve adevărat dacă coada este

plină.

public boolean ColaLlena() {

returnTamaño() == MaxColac;
}

32 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
2.OPERAȚII FUNDAMENTALE

a.INSERTAR UN ELEMENTO EN LA COLA CIRCULAR. Inserta un

elementul pentru FINAL [RC] în coadă.

public void Insertar(int x) {

dacă(ColaLlena()) {
Cola Plină! Nu s-a putut
adicionar.)
}else{
dacă((FC == -1) && (RC == -1)) {
RC = RC + 1;
COLAC[RC] = x;
FC = 0;
}else{
dacă(RC == (MaxColac - 1)) {
RC = 0;
COLAC[RC] = x;
}else{
RC = RC + 1;
COLAC[RC] = x;
}
}
}
}

33 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

b. ELIMINAREA UNUI ELEMENT DIN COADA CIRCULARĂ. Elimină un

element pentru FATA [FC] în coadă.

public intȘ terge() {

intx = -1;
dacă(ColaVacia()) {
Cola Vazia! Nu s-a putut
eliminaț i.
}else{
dacă(RC == FC) {
x = COLAC[FC];
FC = -1;
RC = -1;
}else{
dacă(FC == (MaxColac - 1)) {
x = COLAC[FC];
FC = 0;
}else{
x = COLAC[FC];
FC = FC + 1;
}
}
}
returnx;
}

34 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

c.RECORRER COADA CIRCULAR.Muș trii toate elementele de

la cola circular (de STÂNGA ÎN DREAPTA)

public void Recorrer() {

dacă(ColaVacia()) {
System.out.println("Cola Vacia! No se puede
nu arăta nimic.
}else{
ColaCircular CCaux =newColaCircular();
System.out.print("COLAC: ");
while(!ColaVacia()) {
intx = Eliminare();
System.out.print(x + " ");
CCaux.Insertar(x);
}
while(!CCaux.ColaVacia()) {
Inserare(CCaux.Ș terge());
}
}
}

d.CĂUTAREA UNUI ELEMENT. Afiș ează locaț ia (indicele)

de un element din coada circulară. Dacă se
găseș te, altfel afiș ează un mesaj de Eroare.

35 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public voidCautare() {
int pos=-1;
int c=0;
Scanner in = new Scanner(System.in);
System.out.println("Introduceț i valoarea de căutare:");
inteb= in.nextInt();
dacă(ColaVacia()) {
Cola Vacia! Nu se poate
efectuază căutarea fără niciun element.
}else{
ColaCircular CCaux =newColaCircular();
while(!ColaVacia()) {
pos = FC;
intx = Eliminar();
dacă (x == eb) {c=c+1;
System.out.println("poziț ia: " + pos);
CCaux.Insertar(x);
altfel{ CCaux.Insertar(x);}
}
while(!CCaux.colaVacia()) {
Inserare(CCaux.Ș terge());
}
}
dacă(c == 0)) { System.out.println("Nu…!, nu există
elementul din Coada Circulară.

}else{ System.out.println(" S-a găsit: " + c +

elemente în coada circulară
}
}

36 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
3.OPERAȚIUNI COMPLEMENTARE

a. INSERARE N ELEMENTE ÎN COADA CIRCULARĂ. Inserează N

elemente pentru FINAL în coadă.

public void InsertaN() {

Scanner in = new Scanner(System.in);
System.out.print("Nr.Elemente: ");
intn = in.nextInt();
System.out.println("Introduceț i elementele:");
pentru(int i = 0; i < n; i++) {
intx = in.nextInt();
Inserare(x);
}
}

EXERCIȚII.

a.Dezvolta o metodă care să permită afiș area primului

elementul din coadă.
b.Dezvoltarea unei metode care să permită afiș area ultimei
elementul din coadă.
c.Dezvoltarea unei metode care să permită eliminarea primelor N
elemente ale cozii.
d.Dezvoltaț i o metodă care să permită încărcarea cu N elemente
aleatori la coadă.

37 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

STRUCTURA: BI COLO

DEFINIȚIE. O BI-COLĂ este o structură de datelinial ș i

estatică, care permite inserarea ș i ș tergerea de date prin ambele păr ț i

extreme.

Este un mecanism care integrează într-o structură unică

funcț ionalităț ile stivei ș i cozii.

CARACTERISTICI ALE UNEI BI-COLĂ.

- Eliminările se efectuează din fa ț ă, este

spune porFI(stânga) sau FD(dreapta).
- Inserț iile se fac la final, fie că acesta este
RI(stânga)oRD(dreapta).
- Pentru căutări ș i trasee în Bi-colas, se face
uso de o coadă auxiliar.

38 Ing. Pascual Yana Chejo

 ESTRUCTURA DE DATOS

REPREZENTARE GRAFICĂ A UNEI COZI CIRCULARE.

Se va reprezenta o bi-colă, prin intermediul vectorilor la care

sunt cunoscuț i ș i sub denumirea de array-uri unidimensionale.

ELEMENTE ALE UNEI BI-COLI.

MaxBiCola: Variabilă care conț ine capacitatea bi-

cola.

BICOLA[]:Vector que almacena los datos de la bi-cola

FI: pointer care indică către prima dată pe partea stângă

de la bi-cola.

RI: pointer care indică ultima informaț ie pe partea stângă

de la bi-cola.

FD: pointer care indică către primul dat pe partea dreaptă

de la bi-cola.

RD: pointer care indică ultima dată pe partea dreaptă

de la bi-cola.

IMPLEMENTAREA STRUCTURII BI-COLOANĂ ÎN JAVA.

Cu scopuri didactice, implementarea se realizează prin

două clase: Principal ș i BiCola.

I. CLASE PRINCIPAL ÎN JAVA.

Cree un obiect BC1 (Bi-Cola) ș i se execută operaț iile care
s-au definit asupra acelei structuri de date.

39 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

public classPrincipal {

public static void main(String[] args) {

BiCola BC1=newBiCola();

// creează obiectul bi-colă.

// Adaugă codul necesar pentru rezolvarea de

// probleme cu cozile

}
}

II.CLASA BI-COLA ÎN JAVA.

Define los atributos y los métodos propios de una Bi-Cola.

public class BiCola {

// Adăugaț i aici atributele ș i metodele care
// va conforma structura de date BI-COLA
}

ATRIBUTELE STRUCTURII COLOANE CIRCULARE.

Se definesc elementele cozii, cum ar fi variabilele
cu cei cu care se va implementa această nouă structură:

public class BiCola {

final intMaxBiCola= 100;// define dimensiunea cozii

int[]BICOLA; // define un vector care va stoca
datele
intFI,FD; // define los punteros frente

intRI,RD; y final de la cola

//Adăugaț i aici metodele (operaț iile) care vor fi dezvoltate
// în clase.

40 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

1.OPERAȚ IUNI ELEMENTARE SAU DE STAT.

a.CREARE Ș I INIȚIALIZARE BI-COLA [CONSTRUCTOR].

publicBiCola() {
BCOLA =new int[MaxBiCola];
FI= -1; FD= -1;
RI= -1; RD= -1;
}

b.COLA VACANTĂ, Returnează adevărat dacă nu există nimic

element în bi-cola.

public boolean colaVacia() {

return((FI == -1) && (RI == -1) && (FD == -1)
&& (RD == -1));
}

c.TAMAÑO DE LA BI-COLA. Devuelve el número de elementos

ce posedă bi-cola

public int DimensiuneCoada() {

returnează(RI - FI) + 1;
}

d.COLA LLENA EXTREMO DERECHO. Devuelve adevărat dacă bi-

cola este plină, când se citeș te de la STÂNGA la DREAPTA

public boolean ColaLlenaRI() {

returnRI == (MaxBiCola–1);
}

41 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
e.COLA LLENA EXTREMO IZQUIERDA. Returnează adevărat dacă
bi-cola este plină, atunci când este citită de DREAPTA la STÂNGA

public boolean ColaLlenaRD() {

return(RD - 1) < 0;
}

OPERATII FUNDAMENTALE

a. INSERARE ELEMENT PE EXTREMUL DIN DREAPTA. Inserează un

elementul pentru FINALUL STÂNG în bi-coada; întotdeauna ș i
cuando se pueda, caso contrario despliega un mensaje de
eroare.

public void InserareRI(int x) {

dacă (ColaLlenaRI()) {
Sistemul.out.println("Coca Plină! Nu s-a putut")
adauga la FINAL STÂNGÄ.
}else{
dacă(colaVacia()) {
RI = RI + 1;
BICOLA[RI] = x;
FI = 0; FD = 0; RD = 0;
}
RI = RI + 1;
BICOLA[RI] = x;
FD = RI;
}
}
}

42 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
b.INSERTARE ELEMENT DE LA EXTREMUL STÂNG. Inserează un
element pentru FINALUL DREPT în bi-coadă. Dacă bi-
coada este goală ș i dacă există element în pozi ț ia 0,
afiș ează un mesaj de eroare.

public void InserareRD(int x) {

dacă(colaLlenaDI()) {
Sistemul.out.println("Cola Plină! Nu s-a putut")
adicionar.
}else{
if(colaVacia()) {
Nu s-a putut adăuga
por elemente FINAL DREPT.
}else{
RD = RD - 1;
BICOLA[RD] = x;
FI = RD; }
}
}

c. ELIMINARE ELEMENT DIN EXTREMUL STÂNG. Elimină un

elementul pentru FATA STÂNGA a bi-cozii. Se pune în
consideraț i următoarele cazuri:

Cazul 1: dacă este vorba de un bi-coadă goală, atunci

afisează un mesaj de a nu efectua procesul.
Caz 2: Element unic, se elimină elementul ș i toate
punctele se asează la -1.
Cazul 3: dacă ar exista elemente ș i nu ar fi singurul
atunci se elimină datele ș i se actualizează
puntero a la siguiente posición.

43 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public inteliminarFI() {
intx = -1;
dacă(colaVacia()) {
Cola Vacia! Nu s-a putut
elimina.
}else{
if(RI == FI) {
x = BICOLA[FI];
FI = -1; RI = -1;
FD = -1; RD = -1;
}else{
x = BICOLA[FI];
FI = FI + 1;
RD = FI;
}
}
returnx;
}

d.ELIMINARE ELEMENT DIN EXTREMUL DREPT. Elimină un

elementul bi-cola pe partea din faț ă dreaptă.
Cazul 1 ș i 2: Se procedează la fel ca în secț iunea anterioară.

Cazul 3: se elimină elementul ș i se actualizează pointerul

a o poziț ie anterioară.

public inteliminarFD() {
intx = -1;
dacă(colaVacia()) {
Cola goală! Nu s-a putut
eliminar.

44 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
}else{
dacă(RD == FD) {
x = BICOLA[FD];
FI = -1; RI = -1;
FD = -1; RD = -1;
}else{
x = BICOLA[FD];
FD = FD - 1;
RI = FD;
}
}
returnx;
}

e.RECORRER BI-COLA DE IZQUIERDA A DERECHA.Muestra todos

elementele bi-colăi DE LA STÂNGA LA DREAPTA,
ori de câte ori ar exista vreun element în cazul
în caz contrar, afiș ează un mesaj de eroare.

public void arataID() {

dacă(colaVacia()) {
Cola Vacantă!!!!!
}else{
bcola aux =newbcola();
System.out.print("COLA: ");
while(!colaVacia()) {
intx = eliminaFI();
System.out.print(x + " ");
aux.insertarRI(x);
}
while(!aux.colaVacia()) {
insereazăRI(aux.eliminăFI());
}
}
}

45 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

f.RECORRER BI-COLA DE DERECHA A IZQUIERDA.Mostra toate

elementele bi-colii de DREAPTA LA STÂNGA, dacă
în cazul contrar, afiș ează un mesaj de eroare.

public void afiseazaDI() {

dacă(colaGoală()) {
Cola goală! Nu se
nu poate afiș a nimic.
}else{
bcola aux =newbcola();
System.out.print("BICOLA: ");
while(!colaVacia()) {
intx = eliminareFD();
System.out.print(x + " ");
aux.insereazăRI(x);
}
while(!aux.colaVacia()) {
inserareRI(aux.eliminareFD());
}
}

g.CĂUTAREA DE ELEMENTE ÎNTR-O BI COADĂ. Afiș ează

locaț ia (indicele) unui element în cadrul bi-cola,
la fel ca totalul apari ț iilor, dacă se.
găseș te; în cazul contrar, afiș ează un mesaj de eroare.

46 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public voidCaută() {
int pos=-1;
int c=0;
Scanner in = nou Scanner(System.in);
System.out.println("Introduceț i valoarea de căutare:");
inteb= in.nextInt();
dacă(ColaVacia()) {
Bi-Cola Vacia! Nu se
nu poate efectua căutare de niciun
elemento.
}else{
BiCola BCaux = new BiCola();
while(!ColaVacia()) {
pos = FC;
intx = EliminarFI();
dacă (x == eb) {c=c+1;
System.out.println("poziț ie: " + pos);
BCaux.InsertarRI(x);}
altfel{ BCaux.InserareRI(x); }
}
while(!BCaux.colaVacia()) {
InserareRI(BCaux.Ș tergeFI());
}
}
dacă(c == 0)) { System.out.println("Nu…!, nu există
elementul din Coada Circulară.
} else { System.out.println(" S-a găsit: " + c +
elemente în coada circulare
}
}

47 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
2.OPERAȚIUNI COMPLEMENTARE

a. INSERARE N ELEMENTE ÎN BI-COLA. Permite inserarea N

elemente pentru FINALUL STÂNGHII în bi-coadă.

public void inserareNElemente() {

Scanner in = new Scanner(System.in);

System.out.print("Nr. Elemente: ");
intn = in.nextInt();
System.out.println("Introduceț i elemente:");
pentru(int i = 0; i < n; i++) {
intx = in.nextInt();
inseraRI(x);
}
}

VARIANTELOR DE BI-COLAS
Este posibil să definiț i restricț ii într-o biciclă în raport cu
tipul de intrare sau tipul de ieș ire a datelor.

Există două variante de cola dublă:

a. DOBLE COLA DE ENTRADA RESTRINGIDA. O bicola cu

intrare restringerată este cea care permite doar
inser ț ii printr-unul dintre extreme [FINAL]. Dar
realiza eliminările de ambele extremităț i.

48 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

b.DOBLE COLA DE SALIDA RESTRINGIDA. O bicola cu

restric ț ia la ie ș ire este aceea care admite
inser ț ii de la ambele capete. Dar elimină doar
date de unul dintre capete [FRONTE].

TAREA NRO.5

a. Implementează clasa BiColaEntradaRestrungida.

b. Implementaț i clasa BiColaSalidaRestribgida

49 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
EXERCIȚII.

a.Dezvoltarea metodelor care permit afiș area primului

elementul de la bi-cola. (considera ț i atât pe cel de la
stânga cu cea din dreapta)
b.Dezvoltaț i metodele care permit afiș area ultimei
elementul de la bi-cola. (considera ț i atât pe cel de la
stânga cu cea de dreapta)
c.Dezvoltaț i o metodă care să permită eliminarea primelor N
elementele bi-cola.
d.Dezvoltarea unei metode care să permită încărcarea cu N
elemente, într-o formă aleatorie bi-cola.
e.Dezvoltarea unei metode care să permită centralizarea
operaț iunea insertarRI() ș i insertarRD().
f.Dezvoltarea unei metode care să permită centralizarea
operaț iunea EliminarFI() ș i EliminarFD().

50 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ESTRUCTURA: LISTĂ SIMPLĂ

Listele permit organizarea

numeroase entită ț i ale
lumea reală, cum ar fi
datele studen ț ilor de
un paralel, datele despre
personalul angajaț ilor unei
instituț ie programe
informatici stoca ț i în
un disc magnetic, etc.

DEFINIȚIA LISTEI

Este o structură de date liniară ș i dinamică, compusă din

o secvenț ă de elemente numite noduri care corespund la
un acelaș i tip. Ș i în care, din fiecare dintre ei se poate
indicaț i care este următorul (în cazul în care există).

Nodurile pot fi inserate la început, la sfârș it sau înainte de

după un nod X al listei. Tipărirea listei se
realiza în ordine ascendentă, de la primul nod până la
ultimul.

REPREZENTAREA LISTELOR SIMPLICE.

51 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
ELEMENTE ALE UNEI LISTE SIMPLE.

a.NODO. Variabilă care este compusă dintr-un câmp de date

(almacena los dato o información) y campo apuntador
(conț ine adresa de memorie a următorului nod de
lista).

b.PRIMERO.Puntero de tip nod, care pointează la adresa

de memoria a primului nod al listei.

c.ULTIMO.Puntero de tipo nodo, que apunta a la dirección

de memoria al ultimului nod din listă.

IMPLEMENTAREA STRUCȚIEI LISTĂ SIMPLĂ ÎN JAVA.

Numai în scopuri didactice, implementarea se realizează la

prin intermediul a două clase: principal, nod ș i listă simplă.

I. CLASE PRINCIPAL ÎN JAVA.

Ce permite crearea unei liste simple X ș i utilizarea acestora
operaț ii definite asupra ei.

public classPrincipal {

public static void main(String[] args) {

ListaSimple LS1=newListaSimple();
// creează obiectul Listă Simplă.
// Adaugă cod pentru rezolvarea problemelor
}
}

52 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

II.IMPLEMENTAREA Clasei NOD în JAVA.Se creează un nod

cu două câmpuri, unul pentru a stoca informa ț ia ș i
altul un indicator.

public class Nodo {

intdato;
Nodosiguiente;
}

III. IMPLEMENTAREA CLASEI LISTĂ SIMPLĂ ÎN JAVA, Creează

lista, se declară pointerii care vor indica spre primul ș i
ultimul nod al listei.

public class ListaSimplă {

// Adăugaț i aici atributele ș i metodele clasei
lista....!
}

ATRIBUTOARELE UNEI LISTE SIMPLE.

public class ListaSimple {

Nodoprimero;
Nodoultimo;
// Adăugaț i aici metodele clasei listă....!
}

OPERATIUNI ASUPRA UNEI LISTE. Opera ț iile care se

se dezvoltă pe liste; se clasifică în operaț iuni de
stare, opera ț iuni fundamentale ș i opera ț iuni
complementare:

53 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
1.OPERAȚ IUNILE DE STAT sunt cele care verifică
starea actuală a listei, cum ar fi: verifica ț i dacă există vreo
element, care este primul din listă, etc.

a.Inicializa lista.Inicializează pointerii listei,

asignează valoare null.

publiclista() {
primero =null; ultimo =null;
}

b.Lista goală. Returnează adevărat dacă lista nu conț ine

niciun nod.

public boolean listaVacia() {

return((primero ==null) && (ultimul ==null));
}

c.Tamaño de lista.Returnează numărul de noduri pe care le are

lista simplă.

public intTamañoLista() {
inttam = 0;
dacă(listaVacia()) {
return0;
}else{
nodo aux = primul;
while(aux !=null) {
tam++;
aux = aux.următor;
}
}
returntam;
}

54 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
2.OPERAȚ II FUNDAMENTALE, acestea sunt metodele care
permit să insera ț i noduri noi ș i să le elimina ț i pe rând
extremităț ile.

a.Insera la începutul listei.Se iau în considerare

următoarele cazuri:

55 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void inserareLaInceput(int xdato) {

nodo nou =newnodo();
nuevo.dato = xdato;
dacă(listaVacia()) {
nuevo.siguiente =null;
ultimul = primul = nou;
}else{
nuevo.siguiente = primul;
primero = nuevo;
}
}

b.Inserț ie în mediu, cazul în care lista ar avea

elemente deja, Se creează un nou nod ș i se inserează în
poziț ia indicată de utilizator.

Implementarea în Java rămâne ca practică pentru un

student

56 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
c.Insera ultimul nod în listă. Inserează un nod în
final de la lista [ultimul nod].

public voidinsertarAlFinal(intxdato) {
nodo nuevo =newnodo();
nou.dato = xdato;
dacă(listaVacia()) {
nuevo.siguiente =null;
ultimul = primul = nou;
}else{
nuevo.siguiente =null;
ultimo.siguiente = nou;
ultimo = nuevo;
}
}

d. Elimina primul nod din listă. Elimină nodul care se

găseș te mai întâi în listă

57 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public inteliminarAlInicio() {

intx = -1;
if(listaVacia())
Lista goală..!, nu sunt elemente.
altfel{
dacă (primul == ultimul) {
x = primero.dato;
primul = ultimul = null;
}else{
x = primero.dato;
primul = primul.următor;
}
}
returna;
}

58 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

e.Ș terge ultimul nod din listă. Ș terge nodul

ce se află ultimul în listă.

59 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public inteliminarAlFinalUltimo() {
intx = -1;
dacă(listaVacia())
System.out.println("Lista gol..!, nu se ")
a putut elimina
altfel{
dacă(primul == ultimul) {
x = primero.dato;
primul = ultimul = null;
}else{
nodo aux = primul;
while(aux.siguiente != ultimul) {
aux = aux.următoare;
}
x = ultimul.dato;
ultimul = aux;
ultimo.siguiente = null;
}
}
returnx;
}

f.Parcurge lista simplă. Afiș ează pe ecran conț inutul

de la lista.

60 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void aratăLista() {

nodo aux = primul;
dacă(aux == null)
Lista goală...! Nu există
nimic de arătat
altfel{
while(aux !=null) {
System.out.print(" " + aux.dato);
aux = aux.urmator;
}
}
}

g.Caută un element într-o listă, afiș ează poziț ia.

Afiș ează pe ecran locaț ia unei valori în interiorul
la lista.

61 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void cauta() {

Scanner in = new Scanner(System.in);
System.out.println("Introduceț i elementul de căutat:");
int x = in.nextInt();
nodo aux = primul;
intcont= 0;
intpos = 0;
dacă (ListaVacia()){System.out.println(“Lista Goală..!
nu există elemente de căutare
în listă." );
altfel {
while(aux !=null) {
pos++;
dacă(x == aux.dato) {
cont=cont+1;
System.out.println("poziț ie:" + pos);
aux = aux. următor;
}else{
aux = aux.siguiente;
}
}
if(cont ==0) {
Acest dată nu există..!
În lista);
}else{
s-a găsit un total de:
+ cont + "elemente în listă";
}
}

62 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
3.OPERATII COMPLEMENTARE, sunt acele metode care sunt
adicionale la operaț iile fundamentale, cum ar fi parcurgerea
lista, afiș aț i datele din listă, etc.

EXERCIȚII.

1.Dezvoltaț i o metodă care să afiseze pe ecran Prima de

lista.
2.Dezvoltarea unei metode care să afiș eze pe ecran Ultimul de
lista.
3.Dezvoltarea unei metode care să afiș eze pe ecran
Localizarea unui dat în cadrul listei.
4.Dezvoltarea unei metode care să permită inserarea unui nod înainte
de un anumit termen.
5.Develop a method that allows inserting a node afterwards
de un anumit datum.
6.Dezvoltarea unei metode care să permită inserarea unui nod într-o
poziț ie dată.
7.Dezvoltarea unei metode care să permită eliminarea unui anumit
data.
8. Dezvoltarea unei metode care să permită Eliminarea unui nod dintr-o
poziț ie determinată.
9.Dezvoltarea unei metode care să permită inserarea a N elemente în
listă.

63 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ESTRUCTURA: LISTA CIRCULAR

Éstas listas poseen nodos simples que generan una secuencia

circular. Unde inser ț ia unui nou nod, precum ș i a sa
eliminarea nu rupe acea structură circulară.

DEFINIȚIA LISTEI CIRCULARE.

Este o structură de date liniară ș i dinamică, în care

campo următor al ultimului nod, indică către primul nod al
lista.
Inserț iile ș i eliminările nodurilor simple se fac
se realizează în general prin extremităț ile listei.

REPREZENTARE GRAFICĂ.

ELEMENTE ALE UNEI LISTE SIMPLES.

a.NODO, Variabilă care este compusă dintr-un câmp de date ș i

campo de legătură care indică către următorul nod din listă.

64 Ing. Pascual Yana Chejo

 ESTRUCTURA DE DATOS

b.PRIMUL. Punctator de tip nod, care punctează către adresa

de memoria a primului nod al listei.

c.ULTIMO. Punter de tip nod, care indică adresa de

memoria ultimului nod din listă.

IMPLEMENTAREA UNEI LISTE CIRCULARE ÎN JAVA

Din motive didactice, implementarea se

realizată prin clasele: nod, listaCircular ș i
principal; Fiecare dintre ele pe o fiș ă separată.

I. IMPLEMENTAREA CLASEI NODULUI,

Se creează un nod cu două câmpuri, unul pentru a stoca
informaț ie ș i cealaltă un pointer.

public class nod {

int dato;
nodul următor;
}

II. IMPLEMENTAREA Clasei Principale

În această clasă se găseș te metoda main(). Ș i ne va permite
a testa metodele pe care le vom dezvolta.

public class principal {

public static void main(String[] args) {

listaCircular LC1 = new listaCircular();

// v1.dimensiuneLista();
// v1.listaVacia(); ș i alte instrucț iuni
}
}

65 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
III. IMPLEMENTAREA CLASEI LISTA CIRCULAR,
Creează lista, se declară pointerii care vor indica către
primul ș i ultimul nod al listei.
ATRIBUTELE CLASEI LISTA CIRCULAR.

public class listaCircular {

nodul primul;
nodo ultim
// Adăugaț i aici toate metodele clasei
listaCircular..!
}

OPERATII ASUPRA UNEI LISTE. Operatiile care se

dezvoltă despre listele circulare sunt acelea ș i care
cu o listă simplă.

1.OPERAȚ IUNI DE STAT, acelea care verifică starea

actual de la lista cum ar fi: verificaț i dacă există un element.
cine este primul de pe listă, etc.

a.Inicializa lista.Inicializează pointerii listei,

asigna valoare null.

publiclistaCircular() {
primero =null;
ultimo =null;
}

b.Listă goală. Returnează adevărat dacă lista nu conț ine

niciun nod.

66 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public boolean listaVacia() {

return((primero == null) && (ultimul == null));
}

c.Dimensiunea listei.Returnează numărul de elemente care

poate lista.

public int tamanioLista() {

inttam = 0;
dacă(listaVacia()) {
return0;
}else{nodo aux = primul;
făcând

tam++;
aux = aux.urmatorul;
}în timp ce(aux != primul);
returntam;
}

2.OPERAȚIUNILE FUNDAMENTALE, acestea constituie metodele care

permit în inserarea de noduri noi ș i eliminarea lor unul câte unul

extremităț ile.

a.Insera primul nod în listă.În cazul în care

lista să nu aibă niciun element, se creează noul nod
ș i va actualiza pointerul.

67 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void inserareLaInceput(int x dato) {

nodo nou = newnodo();
nuevo.dato = xdato;
dacă ((primul ==null) && (ultimul ==null)) {
primul = ultimul = nou;
ultimul.suivant = primul;
}else{
nuevo.siguiente = primero;
primero = nuevo;
ultimo.siguiente = primero;
}
}

b.Inserț ie în mediu, cazul în care lista ar avea

elemente deja, Se creează un nou nod ș i se inserează în
poziț ia indicată de utilizator.
Implementarea în java rămâne ca practică pentru
student

68 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
c.Insera ultimul nod în lista.Insera un nod la
final de la lista [ultimul nod].

public void inseraLaFinal(int x dato) {

nodo nuevo =newnodo();
nuevo.dato = xdato;
dacă(listaVacia()) {
primul = ultimul = nou;
ultimul.următor = primul;
}else{
ultimo.siguiente = nou;
ultimo = nuevo;
ultimul.siguiente = primul;
}
}

d.Scoate nodul iniț ial din listă. Ș terge nodul care

se află mai întâi pe listă.

69 Ing. Pascual Yana Chejo

STRUCTURI DE DATE

public inteliminarElPrimero() {

intx = -1;
dacă(listaVacia())
Lista goală..!, nu există elemente.
altfel{
dacă(primul == ultimul) {
x = primul.dato;
primul = ultimul = null;
}
x = primero.dato;
primul = primul.următor;
ultimo.siguiente = primero;
}
}
returnx;
}

70 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
e. Elimină ultimul nod din listă. Elimină nodul care
se află ultimul în listă.

71 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public inteliminarElUltimo() {
intx = -1;
if(primero ==null)
System.out.println("Lista goală..!, nu sunt elemente.");
altfel{
dacă(primul == ultimul) {
x = primero.dato;
primul = ultimul = null;
}else{
nodo aux = primul;

while(aux.siguiente != ultimul) {
aux = aux.următor;
}
x = ultimo.dato;
ultimul = aux;
ultimo.siguiente = primero;
}
}
returnx;
}

3.OPERAȚIUNI COMPLEMENTARE, sunt acele metode care sunt

aditionale la operaț iunile fundamentale, cum ar fi parcurgerea
lista, arată datele din listă, etc.

a.Căutaț i un element într-o listă, afiș aț i poziț ia.

Afiș ează pe ecran locaț ia unei valori în interiorul
lista.

72 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void cauta(int x) {

nodo aux = primul;
booleansw =false;
intpos = 0;
do{ pos++;
dacă(x == aux.dato) { // Ș i găseș te datele
sw =true;
}else{ // Apunta al siguiente nodo
aux = aux.următor;
}
}în timp ce((aux != primul) && (sw !=true));
dacă (sw == adevărat) {

Sistem.out.println("Acest dată este în listă.")

Se află în poziț ia:
else{
System.out.println("Acest dat nu există...! En")
la lista
}
}

b.Imprimă lista de la stânga la dreapta. Afiș ează în

afiș aț i conț inutul listei.

73 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void afiseazaLista() {

nod auxiliar;

dacă(listaVacia())
System.out.println("Lista goală...! Nu există ")
nimic de arătat
altfel{
aux = primul;
fă{
System.out.print(" " + aux.dato);
aux = aux.următor;
}while(aux != primul);

}
}

74 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

EXERCIȚII.

1.Dezvoltarea unei metode care să afiș eze pe ecran Primul de

lista.
2.Dezvoltaț i o metodă care să afiș eze pe ecran Ultimul de
lista.
3.Dezvoltaț i o metodă care să afiș eze pe ecran
Localizarea unui dată în cadrul listei.
4.Dezvoltarea unei metode care să permită inserarea unui nod înainte
de un anumit date.
5.Dezvoltarea unei metode care să permită inserarea unui nod după
de un anumit dat.
6.Dezvoltarea unei metode care să permită inserarea unui nod într-o
poziț ia dată.
7.Dezvoltarea unei metode care să permită eliminarea unui anumit
dato.
8.Dezvoltarea unei metode care permite eliminarea unui nod dintr-o
poziț ie determinată.
9.Dezvoltarea unei metode care să permită inserarea a N elemente în
lista.

75 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ESTRUCTURA: LISTĂ DOBLEMENTE ÎNLAZATĂ

Este o structură de date liniară ș i dinamică, care se

caracterizează prin faptul că au noduri cu două câmpuri: legătură ș i câmp

dato; la aceleaș i care păstrează referinț e la un nod anterior ș i

următorul.
Elementele pot fi introduse la început sau la sfârș it de
lista. Se poate parcurge lista înainte sau înapoi
înapoi, permitându-se să se aibă imprimarea în ordine normală sau în ordine

inverso.

REPREZENTARE GRAFICĂ.

ELEMENTE ALE UNEI LISTE DOBLE.

a.NODO, Variabilă care este compusă dintr-un câmp de date ș i

două câmpuri care indică nodul anterior ș i următor
respectiv.

76 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
b.PRIMUL. Punctator de tip nod, care indică către adresa
de memoria a primului nod al listei.

c.ULTIMO. Puntero de tip nod, care pointează către adresa

de memoria a ultimului nod al listei.

IMPLEMENTAREA CLASEI LISTĂ DUBLĂ ÎN JAVA

Se va realiza prin intermediul a trei cursuri:

I. IMPLEMENTAREA CLASEI NOD ÎN JAVA.

Se creează un nod cu trei câmpuri, unul pentru a stoca
informaț ii ș i celelalte de pointeri.

public classnodo {
intdato;
nodul următor;
nodo anterior;
}

II. IMPLEMENTAREA CLASEI PRINCIPALE,

Reprezintă implementarea clasei nod ș i a clasei
listaDoble.

clasa publică principală {

public static voidmain(String[] args) {

listaDoble LD1=newlistaDoble();

// LD1.dimensiuneListaDublu();
// LD1.listaDobleVacia(); ș i alte instrucț iuni

}
}

77 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
III. IMPLEMENTAREA CLASEI LISTĂ DUBLĂ,
Creează lista, se declară pointerii care vor indica la
primul ș i ultimul nod al listei.
ATRIBUȚIILE CLASEI LISTĂ DUBLĂ

clasa listaDoble publică {

nodul întâi;
nodo ultim
// Adăugaț i aici metodele clasei...!
}

OPERATIUNI ASUPRA UNEI LISTE. Opera ț iile pe care le

se dezvoltă cu privire la listele duble legate sunt:

1.OPERAȚ IUNI DE STAT, sunt acelea care verifică

starea actuală a listei cum ar fi: a verifica dacă există vreo
element, cine este primul din listă, etc.

a.Inicializa lista.Inicializează pointerii listei,

atribuie valoare null.

publiclistaDoble() {
primero =null;
ultimo =null;
}

b.Lista goală. Returnează adevărat dacă lista nu are

niciun nod.

public boolean listaVacia() {

return((primero ==null) && (ultimo ==null));
}

78 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

c.Tamaño de lista. Returnează numărul de elemente care

poseda lista.

public int dimensiuneLista() {

inttam = 0;
dacă(listaVacia()) {
return0;
}else{
nodo aux = primul;
în timp ce(aux !=null) {

tam++;
aux = aux.următor;
}
}
returntam;
}

2.OPERAȚII FUNDAMENTALE, acestea sunt metodele care

permit să insera ț i noduri noi ș i să le elimina ț i câte unul
extremităț ile.

a.Insera primul nod în listă.În cazul în care

lista să nu aibă niciun element, se creează noul nod
ș i va actualiza pointerul.

79 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void inseraLaÎnceput(int xdato) {

nodo nou =newnodo();
nuevo.dato = xdato;
dacă(listaVacia()) {
nuevo.anterior =null;
nuevo.siguiente =null;
ultimul = primul = nou;
}else{
nuevo.anterior =null;
nou.siguiente = primul;
primero.anterior = nuevo;
primero = nuevo;
}
}

80 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
b. Inserț ie în mediu, cazul în care lista ar avea
elemente deja, Se cree un nou nod ș i se inserează în
poziț ia indicată de utilizator.
Implementarea în Java rămâne ca practică pentru
student

c.Insera ultimul nod în listă. Inserează un nod la

final de la lista [ultimo nodo].

81 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public voidinsertarAlFinal(intxdato) {
nodo nuevo =newnodo();
nou.dato = xdato;
dacă(listaVacia()) {
nuevo.anterior =null;
nuevo.siguiente =null;
ultimul = primul = nou;
}else{
nuevo.siguiente =null;
nuevo.anterior = ultimo;
ultimul.siguiente = nou;
ultimo = nuevo;
}
}

82 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
d. Elimină primul nod din listă. Elimină nodul care
se află mai întâi pe listă.

83 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public inteliminarPrimero() {

intx = -1;
dacă(listaVacia())
System.out.println("Listă goală..!, nu se ")
pudo elimina
altfel{
dacă (primul == ultimul) {
x = primero.dato;
primul = ultimul = null;
}else{
x = primero.dato;
primul = primul.următor;
primero.anterior =null;
}
}
returnx;
}

84 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
e. Eliminarea ultimului nod din listă. Ș terge nodul care
se află ultimul în listă.

85 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public inteliminarUltimo() {

intx = -1;
dacă(listaVacia())
System.out.println("Lista goală..!, nu se ")
pud e elimina
altfel{
if(primero == ultimo) {
x = primero.dato;
primul = ultimul = null;
}else{
x = ultimo.dato;
ultimo = ultimo.anterior;
ultimo.siguiente =null;
}
}
returnx;
}

3.OPERAȚII COMPLEMENTARE, sunt acele metode care sunt

aditionale la operaț iile fundamentale, cum ar fi parcurgerea
lista, afiș aț i datele din listă, etc.

a.Caută un dată într-o listă, arată poziț ia.

Afiș ează pe ecran locaț ia unei valori în interiorul
lista.

86 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void cauta(int x) {

nodo aux = primul;
booleansw =false;
intpos = 0;
while(aux != null && sw != true) {
pos++;
if(x == aux.dato) { // dacă găseș te datele
sw =true;
}else{ // apontaț i la următorul nod
aux = aux.urmator;
}
}
dacă (sw == adevărat) {

Sistem.out.println("Acest dată este în listă. Se

găseș te în poziț ia:
}else{
System.out.println("Acest date nu există...! În ")
lista
}
}

87 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

b.Imprimă lista de la stânga la dreapta. Afiș ează în

afiș ează conț inutul listei.

public voidmostrarListaID() {
nodo aux = primul;
dacă(aux ==null)
System.out.println("Lista goală..! nu există
nimic de arătat
altfel{
while(aux !=null) {
System.out.print(" " + aux.dato);
aux = aux.următorul;
}
}
}

88 Ing. Pascual Yana Chejo

STRUCTURI DE DATE

c.Imprimă lista de la dreapta la stânga. Afiș ează în

afiș ează conț inutul listei.

public void arataListaDI() {

nodo aux = ultimul;
dacă(aux == null)
Lista goală..! nu există
nimic de arătat
altfel{
while(aux != null) {
System.out.print(" " + aux.dato);
aux = aux.anterior;
}
}
}

89 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
EXERCIȚII.

1.Dezvoltaț i o metodă care să afiș eze pe ecran Primul de

lista.
2.Dezvoltaț i o metodă care să afiș eze pe ecran Ultimul de
pe listă.
3.Dezvoltaț i o metodă care să afiș eze pe ecran
Localizarea unui dat în interiorul listei.
4.Dezvoltarea unei metode care să permită inserarea unui nod înainte
de un anumit dată.
5.Developaț i o metodă care să permită inserarea unui nod după
de un anumit dată.
6.Dezvoltaț i o metodă care să permită inserarea unui nod într-o
poziț ia dată.
7.Dezvoltarea unei metode care să permită eliminarea unui anumit
dato.
8.Developaț i o metodă care să permită eliminarea unui nod dintr-o
poziț ie determinată.
9.Dezvoltarea unei metode care să permită introducerea a N elemente în
lista.

90 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

STRUCTURA: COPACI.

DEFINIȚIA UNUI COPAC

Un arbore este o structură de date non-liniară, dinamică ș i

jerarhică; în care fiecare nod poate indica către unul sau mai multe
nodos

Un arbore este definit ca o structură de date formată din

elemente de acelaș i tip, numite noduri, legate în astfel de
mod în care:

- Există un nod special numit rădăcină.

- Nodurile rămase se împart în A1, A2, A3,... AN;
fiecare dintre care, la rândul său, este arbore (subarbore).

Ș i se cunoaș te adresa nodului rădăcină, de la el se

are acces la toț i ceilalț i membri ai structurii.

REPREZENTARE GRAFICĂ A UNUI COPAC: Un copac general se

reprezintă prin grafuri.

91 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

TERMINOLOGÍA DE ARBOLES:

Definiț ii în relaț ie cu alte noduri:

Nod părinte: Este nodul arbore care are cel puț in un

nod copil.

Ejm. Aes este tatăl lui B, CyD.

Bes tată de EyF.
Des el tatăl lui GyH
Ees tată deIyJ
Fes este tatăl lui KyL
Ges tată deM

Nod fiu: Este acel nod care întotdeauna va avea un nod

antecesor sau tată.

Ejm. B, C ș i D sunt copii ai lui A

E ș i Fson de fii de B
G ș i H sunt fii de D
I y Json copii deE
K y Lson copii de F
Mes fiul meu deG

Nodo frate: sunt aceș tia care se află în aceeaș i

nivel, adică dacă au acelaș i părinte.

Ejm. B, C ș i D sunt fra ț i pentru că sunt copii de A

E ș i Fson fraț i pentru că sunt copii de B
G ș i Hson fraț i pentru că sunt fiii lui D
Eu ș i fraț ii mei pentru că sunt copii ai lui Dumnezeu

K y Lson fraț i pentru că sunt fiii lui F

92 Ing. Pascual Yana Chejo

 STRUCTURA DE DATĂ

În ceea ce priveș te poziț ia în cadrul copacului:

Nodul rădăcină: Este nodul principal al unui arbore ș i nu are

antecesori. Acesta este nodul pe care îl vom folosi pentru a ne referi la

al pom.

Ejm.Aes nod rădăcină.

Nodo frunza: Sunt acele noduri care nu au copii sau

de asemenea, nodurile finale ale unui arbore.

Ejm.C,I, J, K, L ș i M sunt noduri frunza

Nodo rama: de ș i această defini ț ie abia o vom folosi,

acestea sunt nodurile care nu apar ț in niciuneia dintre
două categorii anterioare.

Ejm. B, D, E, F ș i G sunt noduri ramă.

Conceptii legate de dimensiunea lor:

Ordin: este numărul potenț ial de copii pe care îi poate

a avea fiecare nod de copac.

Grad: se spune că gradul unui nod este numărul

de fii pe care îi are acest nod.

Nivel sau adâncime: Se spune că nivelul unui nod

este numărul de arce care trebuie parcurse,
pornind de la rădăcină pentru a ajunge la el.

Înălț ime: Se spune că înălț imea unui copac este

maximul nivelurilor luând în considerare toț i nodurile sale.

Rama: este arcu care leagă un nod de altul.

Este important să conservăm întotdeauna nodoraiză, deoarece este

nodul de la care se dezvoltă copacul, dacă pierdem

dacă pierdem acest nod, vom pierde accesul la tot arborele.

93 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

ARBORE BINAL:

Un arbore binar este un set finit de zero sau mai multe noduri
tales que:

-Există un nod denumit rădăcină a arborelui.

Fiecare nod poate avea 0, 1 sau 2 subarbori; către care se
le cunosc ca subarbore stâng ș i subarbore drept.

Unde: se spune că două arbori binari sunt similari dacă

au aceea ș i structură ș i echivalente dacă con ț in
aceeaș i informaț ie.

Un arbore binar este echilibrat dacă înălț imile celor doi

subarborile fiecărui nod al arborelui se deosebesc cu o unitate
cel mult.

Un árbol binario está lleno cuando todas sus hojas están al

acelaș i nivel ș i nodurile sale interioare au fiecare câte doi copii.

Un arbore binar complet este echilibrat în timp ce un arbore

un arbore binar plin este complet echilibrat.

RECORRILE ÎNTR-UN ARBORE BINAR: A recorre înseamnă a vizita

nodurile copacului în formă sistematică; într-un mod în care
toate nodurile să fie vizitate o singură dată:

94 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
El recorrido en PRE-ORDEN, es también llamado orden previo y
constă în:

Vizitează rădăcina.
Parcurge subarborele stâng în preordine.
- Parcurgerea subarborelui drept în preordine.

Ejm.A B D H I E J K C F L G M N

Parcurgerea în IN-ORDINE, de asemenea cunoscută sub numele de ordine simetrică;

- Parcurge subarborele stâng în ordine.

Vizitaț i rădăcina.
Parcurgeț i subarborele drept în ordine.

Ejm.H D I B J E K A L F C M G N

Parcursul în POST-ORDINE, de asemenea, numit ordonare Posterioară;

Recorre subarborele stâng în post-ordonare.

- Parcurge subarborele drept în ordine post-ordine.
Vizitaț i rădăcina.

Ejm.H I D J K E B L F M N G C A

ARBORE BINARY DE CĂUTARE (ABB)

95 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
Este un arbore binar ordonat, care îndepline ș te următoarele
premisas:

- Există un nod numit rădăcină al arborelui ABB.

Datele nodurilor din subarborele stâng sunt
mai mici decât cele ale nodului rădăcină.

- Datele nodurilor din subarborele drept sunt mai mari

decât cea a nodului rădăcină.

Nu există două noduri cu aceeaș i dată.

- La fel, atât subarborele stâng cât ș i cel drept sunt
arborele binar de căutare.

NOTĂ: Un arbore binar ordonat este acela de la care se poate

ob ț ineț i o secven ț ă ordonată a datelor dvs., prin intermediul
parcurgere IN-ORDEN.

IMPLEMENTAREA UNEI ARBORE BINARE DE CĂUTARE ÎN JAVA.

Se implementează prin intermediul a trei clase: clasa nod, care defineș te

atributele unui nod; clasa arbore ABB, care defineș te

96 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
atributele ș i metodele acestei clase; ș i clasa principală,
ce va conț ine metoda main [în responsabilitatea studentului].

I. CLASA NODO ÎN JAVA.

Se creează un nod cu trei

câmpuri: cursor stâng,
care indică către subarbore

stânga; pointer drept,

care indică către subarbore

drept; ș i câmpul datei, care

conț ine informaț ia.

public class nodo {

intdato;
nod stâng;
nodo drept;
// Constructor, care iniț ializează pointerii în null....!
nodo() {
izquierdo =null;
derecho =null;
}
}

II.CLASA PRINCIPALĂ ÎN JAVA,

Se implementează în sala de clasă împreună cu profesorul ș i studentul.

III. CLASE ÁRBOL BINAR DE CĂUTARE ÎN JAVA,

Defini ț i clasa cu numele deabb, de asemenea stabili ț i
nodo rădăcină în null.

97 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE

public classabb {
nodo raiz =null;
// Adăugaț i aici metodele clasei listă....!
}

OPERATIUNI ASUPRA UNUI ARBOL BINAR DE CĂUTARE.

operaț ii care se desfăș oară asupra unui ABB; se clasifică în
operaciones de estado, operaciones fundamentales y
operaț iuni complementare:

1.OPERAȚ IUNI DE STAT, sunt acelea care verifică

starea actuală a listei, cum ar fi: verifica ț i dacă există vreo
element, care este primul din listă, etc.

a.Schimbare goală. Returnează adevărat dacă lista nu are

niciun nod.

public boolean arboreVacios() {

returnraiz == null;
}

b.Părinte de. Returnează adresa de memorie a părintelui

un nod copil.

98 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

publicnodo părinteleDe(nodo nodX) {

nodo raizAux = raiz;
nodo padre =null;
while(raizAux !=null) {
dacă(nodoX.dato == raizAux.dato)
returnpadre;
altfel dacă (nodoX.dato > raizAux.dato) {
tată = rădăcinăAux;
raizAux = raizAux.dreapta;
}else{
tata = raizAux;
raizAux = raizAux.izquierdo;
}
}
return null;
}

2.OPERAȚ II FUNDAMENTALE, acestea sunt metodele care

permit accesul la inserarea de noi noduri si eliminarea acestora; pentru aceasta se

sus ț in în alte metode precum: căutare (existăDato),

padre de, recorrerIzquierda, etc.

a.CĂUTARE ÎNTR-UN ABB: Căutarea va începe de la nodul

rădăcină. Dacă X este egal cu câmpul dat al nodului, căutarea
finaliza cu succes. Dacă X este mai mic decât câmpul dat de
nod, se va trebui să se efectueze căutarea în subarbore
stânga. Dacă, dimpotrivă, X este mai mare, atunci
căutare continuă în subarborele drept.

99 Ing. Pascual Yana Chejo

STRUCTURA DE DATI
Procesul continuă până când se găseș te un nod cu
câmpul dat este egal cu X sau un subarbore gol [NULL] cine
avalat că nu există niciun nod cu valoarea X.

publicnodo existeDato(intdatoX) {
nodo ra Aux = ra ;
while(raizAux !=null) {
dacă(datoX == raizAux.dato)
returnraizAux;
altfel dacă(datoX > raizAux.dato)
raizAux = raizAux.dreapta;
altfel
raizAux = raizAux.stanga;
}
return null;

b. INSERAREA UNUI NOD ÎNTR-UN ABB: primul lucru care trebuie

a face este a efectua căutarea. Dacă datele de inserat se
găse ș te în copac, nu se face nimic. În caz
din contră, datele sunt introduse în locul care
coresponde. Menț inând structura ABB.

100 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

public void inserareNod(int x) {

nodo nou = newnodo();
nuevo.dato = x;
daca(arbolVacio())
// Caz: dacă arborele ar fi gol, noul este rădăcina
raiz = nuevo;
altfel{
// Caz: arborele ar avea alte noduri.
dacă(existeDato(x) ==null) {
nodo padre =null;
nodo raizAux = raiz;
Parcurge până localizezi locul de inserare
while(raizAux !=null) {
tata = rădăcinăAux;
dacă(x < raizAux.dato)
raizAux = raizAux.stânga;
altfel
raizAux = raizAux.drept;
}
// Leagă ca fiu stâng sau drept
dacă(x < padre.dato)
padre.izquierdo = nuevo;
altfel
padre.derecho = nuevo;
else
// Caz: valoare repetată, nu se inserează
System.out.println("YA Există... " + x + "!, în ");
Copac.
}

101 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
NOTA: Nodurile sunt întotdeauna inserate prin frunze, deoarece
căutarea se încheie fără succes atunci când se accesează un subarbore

stânga sau dreapta care este goală.

c.ELIMINAREA UNUI NOD ÎNTR-UN ABB: Este un proces complex

deoarece trebuie men ț inută structura unui arbore
binariu, primul lucru este să căutăm în arbore pozi ț ia
del nod de eliminat ș i apoi eliminaț i în funcț ie de caz:
-Elimină un nod fără copii (frunză), pur ș i simplu se
elimină nodul.

-Elimina ț i un nod cu un singur copil, trebuie doar să

a efectua o reasignare de pointeri. tatăl lui
nodo pe care dorim să-l eliminăm începe să pointeze către fiul lui

nodul care este eliminat.

-Eliminarea unui nod cu doi copii,

1. Se înlocuie ș te câmpul de date al nodului pe care îl dorim
elimină cu datele maxime din subarborele său
izquierdo (sau elementul minim al subarborelui său
drept)
2. Uimitor, se elimină nodul maxim (sau minim,
în funcț ie de caz).

public inteliminarNodo(nodo dne) {

dacă(!arbolVacio()) {
intx = dne.dato;
// Creamăm o variabilă pentru a ș ti dacă are copii stânga ș i dreapta

booleantieneNodoDerecha = dne.derecho !=null?true:

fals
booleantieneNodoIzquierda = dne.izquierdo !=null?true
false
// Caso 1: No tiene hijos (es un nodo hoja)

102 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
dacă(!tieneNodoDerecha && !tieneNodoIzquierda) {
nodo padre = padreDe(dne);
dacă (padre.izquierdo == dne) {
padre.izquierdo =null;
}
if(padre.dreapta.dato == dne.dato) {
padre.derecho =null;
}
}
// Caz 2: Are un singur copil ș i celălalt nu
dacă((tieneNodoDerecha && !tieneNodoIzquierda) ||
(!tieneNodoDerecha && tieneNodoIzquierda)) {
nodo padre = padreDe(dne);
/* Guardemos los hijos del padre temporalmente para
să ș tii pe care dintre ei trebuie să îl elimini

nodo fiuActual = dne.izquierdo !=null ?

dne.izquierdo : dne.derecho;
dacă(padre.izquierdo == dne) {
padre.izquierdo = hijoActual;
}
if(padre.dreapta == dne) {
tata.drept = fiulActual;
}
}
// Cazul 3: Are amândoi copiii
dacă(tieneNodoDerecha && tieneNodoIzquierda) {
/* Luăm fiul drept al Nodului pe care îl dorim
elimina*/
nodo nodoMasALaIzquierda =
recorrerIzquierda(dne.drept);
nodo_părinte = părinteDe(nodoMaiLaStânga);
Înlocuim valoarea nodului pe care dorim să-l eliminăm
prin nodul care se află cel mai la stânga.

103 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
dne.dato = nodoMasALaIzquierda.dato;
// Eliminăm nodul cel mai din stânga
dacă(padre.dato != nodoMasALaIzquierda.dato)
padre.izquierdo =null;
altfel
padre.derecho =null;
}
returnx;
}
Arbore Gol...! Nu există nimic pentru
elimina
return0;
}
Recursiv, caută până găseș te nodul cel mai
la stânga*/

publicnodo parcurgereStanga(nodo dne) {

dacă (dne.izquierdo !=null) {
returnrecorrerStanga(dne.stanga);
}
returndne;
}

3.OPERAȚIUNI COMPLEMENTARE, sunt acele metode care sunt

adicionale la operaț iile fundamentale, cum ar fi a parcurge
copacul, a arăta datele copacului, etc.

a.Imprimarea datelor în ordine se efectuează prin

parcurgere In-Ordine.

104 Ing. Pascual Yana Chejo

STRUCTURA DE DATE
private void imprimareInOrdine(nodo aux) {
dacă(aux !=null) {
imprimaInOrdine(aux.stanga);
System.out.print(aux.dato + " ");
imprimareInOrdine(aux.dreapta);
}
}
public void imprimeInOrdine() {
dacă(!arbolVacio()) {
imprimaInOrdine(raiz);
System.out.println("");
}else
Copac fără frunze...! Nu este nimic ce
afişa.
}

b.Imprimarea datelor în Pre-Ordine se realizează prin

recorrido Pre-Orden.

private void imprimarePreOrden(nod aux) {

dacă(aux != null) {
System.out.print(aux.dato + " ");
imprimirPreOrden(aux.izquierdo);
imprimirPreOrden(aux.dreapta);
}
}
public void imprimaPreOrdine() {
dacă(!arbolVacio()) {
imprimarePreOrdine(raiz);
System.out.println("");
}else
Sistem.out.println("Copac fără frunze...! Nu este nimic")
ce să arate.
}

105 Ing. Pascual Yana Chejo

STRUCTURA DE DATE

c.Imprimarea datelor în Post-Ordine se face prin intermediul

parcurgere Post-Ordine.

private void imprimaPostOrdine(nod aux) {

dacă(aux !=null) {
imprimirPostOrden(aux.stanga);
imprimarePostOrdonat(aux.drept)
System.out.print(aux.dato + " ");
}
}
public void imprimarePostOrdine() {
if(!arbolVacio()) {
imprimirPostOrden(raiz);
System.out.println("");
>else
Sistem.out.println("Copac fără frunze...! Nu este nimic"
ce să arate.
}

106 Ing. Pascual Yana Chejo

 STRUCTURA DE DATE
EXERCIȚII.

1.Dezvoltarea unei metode care să afiș eze pe ecran cantitatea

de nodos hoja.
2.Dezvoltarea unei metode care să afiș eze pe ecran înălț imea
de copac.
3.Dezvoltaț i o metodă care să afiș eze pe ecran
Localizarea unui dat mai mare din arbore.
4.Desenvoltaț i o metodă care să afiș eze pe ecran
Localizarea unui element mai mic din arbore.

www.buenastareas.com
www.rena.edu.ve

107 Ing. Pascual Yana Chejo