Alg-si-SD

Structuri de date liniare şi arborescente în C -------------------------------------------------------------------------------------------------------------

5

1 NoŃiuni introductive

1.1 NoŃiunea de dat ă În informatică, prin dată se desemnează un model de reprezentare a informaŃiei accesibil unui anumit procesor (om, unitate centrală program, etc.), model cu care se poate opera pentru a obŃine noi informaŃii despre fenomenele, procesele şi obiectele lumii reale. O dată care apare ca o entitate indivizibilă, atât în raport cu informaŃia pe care o reprezintă, cât şi în raport cu procesorul care o prelucrează, este denumită dată elementară sau scalară. Data elementară poate fi privită ca model de reprezentare a informaŃiei, la nivelul unui procesor uman (nivel logic) sau la nivelul calculatorului, ca procesor (nivel fizic) . Din punct de vedere logic, o dată elementară poate fi definită ca un triplet de forma: (identificator, atribute, valori), iar din punct de vedere al reprezentării interne (fizic), modelul corespunzător este o zonă de memorie de o anumită mărime, situată la o anumită adresă absolută, în care sunt memorate, în timp şi într-o formă specifică, valorile acesteia. Identificatorul este un simbol (nume), care se asociază datei, pentru a o distinge de alte date şi de a o putea referi în procesele de prelucrare (referire prin nume). Valorile datei se pot preciza prin enumerare sau printr-o proprietate comună. Ele pot fi numere întregi, reale, complexe, valori de adevăr, şiruri de caractere, şiruri de biŃi, etc. Dacă pe tot parcursul procesului de prelucrare data păstrează aceeaşi valoare,


6

atunci ea este numită dată constantă sau simplu constantă, în caz contrar data se numeşte variabilă. Pentru date constante, în general drept identificator se utilizează chiar valoarea, adică o astfel de dată se identifică prin forma textuală a valorii. Atributele precizează proprietăŃi ale datei şi ele determină modul în care aceasta va fi tratată în procesul de prelucrare. Dintre atributele care se pot asocia unei date, cel mai important este atributul de tip. El defineşte apartenenŃa datei la o anumită clasă de date, clasă definită după natura şi domeniul valorilor, pentru care sunt specificate anumite operaŃii şi căreia îi este specific un anumit model de reprezentare internă. În acest sens se disting date de tip întreg, real, logic, complex, şir de caractere, etc. Tipul asociat unei date este precizat în programele pentru calculatoare printr-o declaraŃie de constantă, variabilă sau funcŃie explicită, declaraŃie care textual precede utilizarea respectivei constante, variabile sau funcŃii. În afara atributului de tip, unei date i se pot asocia şi alte atribute, pentru ca, astfel, să se precizeze mai detaliat condiŃiile în care aceasta va fi utilizată în prelucrare cum sunt: precizia reprezentării interne, încadrarea valorii în zona afectată, modul de alocare a memoriei pe parcursul prelucrării (static, dinamic), valoarea iniŃială .

1.2 Structuri de date De cele mai multe ori, în aplicaŃii, datele se prezintă sub forma unor mulŃimi sau colecŃii, iar prelucrarea lor nu poate fi concepută fără o organizare corespunzătoare. Între elementele unei colecŃii de date pot fi identificate sau, eventual, pot fi introduse relaŃii care să determine pe mulŃimea respectivă o anumită structură, adică un anumit mod de ordonare, astfel încât să faciliteze prelucrarea. O colecŃie de date pe care s-a definit o structură, căreia îi este specific un anumit mecanism de selecŃie şi identificare a componentelor, constituie o structură de date. Componentele structurii pot fi individualizate şi selectate prin


7

nume (identificatori) sau prin poziŃia pe care o ocupă în structură, în conformitate cu ordinea specificată. Dacă o componentă poate fi selectată fară a Ńine seama de celelalte componente, atunci se spune că structura are acces direct (de exemplu accesul prin nume). Dacă, dimpotrivă, localizarea unui element se face printr-un proces de parcurgere a mai multor componente, conform cu ordinea acestora (traversare), atunci structura se spune că are acces secvenŃial. Structura de date poate fi creată pentru memoria internă sau pentru un suport extern de memorie (bandă magnetică, disc magnetic, etc). În mod corespunzător se vorbeşte de structuri interne respectiv externe (fişiere) de date. În general, structurile externe au un caracter de date permanente, de lungă durată, pe când cele interne sunt temporare. Dacă în reprezentarea structurii de date pe suportul de memorie, împreună cu componentele acesteia, se înregistrează date care materializează relaŃiile de ordonare, atunci se spune că structura este explicită, iar datele suplimentare, de obicei adrese, se numesc referinŃe sau pointeri . Asupra unei structuri de date se pot efectua o multitudine de operaŃii, care se referă la valorile elementelor şi/sau la structură. Dintre acestea mai frecvent utilizate sunt operaŃiile de: a) creare : memorarea structurii de date în forma iniŃială pe suportul de memorie; b) consultare : acces la elementele structurii pentru prelucrarea valorilor acestora; c) actualizare : schimbarea stării structurii prin adăugarea (inserarea) unor noi elemente, ştergerea elementelor care nu mai sunt necesare şi modificarea valorilor unor elemente; d) sortare : aranjarea elementelor structurii după anumite criterii, date de valorile acestora; e) ventilare : desfacerea unei structuri în două sau mai multe structuri; f) fuzionare : combinarea a două sau mai multe structuri la fel ordonate, într-o singură structură;


8

g) copiere : realizarea unei copii a unei structuri în general pe un alt suport. OperaŃiile la care poate fi supusă o structură de date şi eficienŃa cu care acestea pot fi utilizate depind, în mare măsură, de natura relaŃiilor de ordonare şi de modul în care acestea sunt materializate pe suporturile de memorie. Din acest punct de vedere, operaŃiile constituie un element distinctiv (proprietate) pentru diversele structuri de date. Toate structurile de date care au aceeaşi organizare şi sunt supuse aceloraşi operaŃii formează un anumit tip de structur ă de date . În acest sens se vorbeşte de structură de date de tip listă, arbore, etc. Analizând modul de realizare a operaŃiilor pentru diferite tipuri de structuri se poate pune în evidenŃă faptul că acestea pot fi reduse la utilizarea, eventual repetată, a unui grup specific de operatori (funcŃii). Astfel se poate spune că un tip de structură de date este o mulŃime ordonată de date, pe care s-a definit un grup de operatori de bază, cu o anumită semantică. Componentele unei structuri de date pot să fie date elementare sau să fie ele însele structuri de date. Dacă componentele sunt de acelaşi tip, atunci structura este omogenă iar tipul componentelor se numeşte tip de bază. Numărul valorilor distincte aparŃinând unui tip T se numeşte cardinalitatea lui T. De regulă aceasta reprezintă o măsură a cantităŃii de memorie necesare reprezentării variabilei x a tipului T. Deoarece tipurile constitutive pot fi la rândul lor structurate, poate fi construită o întreagă ierarhie de astfel de structuri, dar în mod evident, ultimele componente, cele de la bază, trebuie să fie atomi ( tipuri primitive). În afara tipurilor definite de programator, trebuie să existe un set de tipuri standard aşa-zise predefinite. Tipurile primitive standard sunt acele tipuri care sunt disponibile în marea majoritate a sistemelor de calcul ca şi caracteristici hardware. Acestea includ de regulă numere şi valori logice. Dacă între valorile individuale ale


9

tipului există o relaŃie de ordonare, atunci tipul se spune că este ordonat sau scalar. Metodele de structurare de bază sunt tablourile, articolele, mulŃimea şi secvenŃa (fişierul). Primele trei tipuri se numesc statice deoarece sunt fixe ca formă şi dimensiune, tipul secvenŃă fiind fix numai ca formă. Structurile mai complicate nu sunt definite în mod uzual ca tipuri “statice”, deoarece ele sunt generate în mod “dinamic” în timpul execuŃiei programului, astfel încât ele pot varia în formă şi în dimensiune. Acestea sunt listele, listele circulare, arborii şi grafurile generalizate finite. Variabilele şi tipurile de date sunt introduse în program cu scopul de a fi utilizate în calcule. În acest scop trebuie să stea la dispoziŃie un set de operatori. De aceea, pe lângă tipuri, limbajele oferă un anumit număr de operatori atomici (standard), şi un număr de metode de structurare, prin care operaŃiile compuse pot fi definite în termenii operatorilor primitivi. Cei mai importanŃi operatori de bază sunt comparaŃia şi atribuirea respectiv testul pentru egalitate (şi ordine în cazul tipurilor ordonate) şi forŃarea egalităŃii. Aceşti operatori fundamentali sunt definiŃi pentru toate tipurile de date. ExecuŃia lor însă poate să presupună un volum cu atât mai sporit de calcul, cu cât gradul de structurare este mai înalt. Dacă un tip de structură de date se compune din (sau se poate descompune în) structuri de date aparŃinând aceluiaşi tip, atunci se spune că structura de date este recursivă. OperaŃiile (operatorii) aplicate asupra unei structuri de date pot să îi afecteze valorile şi/sau structura. Dacă o structură de date îşi modifică structura, atunci este considerată dinamică. Opusul structurilor dinamice sunt structurile statice, care pe tot parcursul existenŃei lor au acelaşi număr de componente şi în aceeaşi ordine. Structurile dinamice pot avea un număr, teoretic nelimitat de componente şi de aceea se mai numesc şi structuri de cardinalitate infinită.


10

1.2.1 Tipuri primitive standard Tipurile primitive standard sunt acele tipuri care sunt disponibile în marea majoritate a sistemelor de calcul ca şi caracteristici hardware. Ele includ numere întregi, şi un set de caractere reprezentabile grafic. De asemenea pe sisteme mai complexe sunt incluse în această categorie şi numerele fracŃionare, împreună cu un set adecvat de operatori primitivi. - Tipul întreg cuprinde o submulŃime a numerelor întregi, a cărei dimensiune variază de la un sistem de calcul la altul. Se presupune că toate operaŃiile asupra acestui tip de date sunt exacte şi corespund regulilor obişnuite ale aritmeticii. Procedeul de calcul trebuie întrerupt în cazul obŃinerii unui rezultat în afara setului reprezentabil. Numerele întregi pot fi reprezentate în sistemele de calcul ca:

• Întregi fără semn; • Întregi cu semn; • Întregi, în complement faŃă de 2;

Reprezentarea nr. întregi pe 8 biŃi conform standardului IEEE 754

Număr

Fără semn Cu semn În complement faŃă de 2

-128 NR* NR 10000000 -127 NR 11111111 10000001 -2 NR 10000010 11111110 -1 NR 10000001 11111111 0 00000000 00000000

10000000 00000000

1 00000001 00000001 00000001 127 01111111 01111111 01111111 128 10000000 NR NR 255 11111111 NR NR


11

*NR Nereprezentabil în format pe 8 biŃi. Reprezentarea în complement faŃă de doi, se numeşte astfel, pentru că reprezentarea internă a numerelor negative (pe n biŃi) se obŃine prin scăderea din 2n a valorii absolute a numarului. Cu alte cuvinte, reprezentarea unui număr negativ reprezintă “complementul”, adică valoarea ce trebuie adăugată valorii absolute pentru a obŃine puterea a n-a a lui 2. De exemplu, dacă n=4, reprezentarea lui –5, în complement faŃă de 2 va fi: 10000- 24

0101 |-5| (adica 5) ------ 1011 -5 (în reprezentarea în complement faŃă de 2) În Limbajul C datele întregi pot fi de tipul: short, int, long. Reprezentarea datelor de tip întreg- Tab.1 Specificarea tipului Dimensiunea în biŃi Modul de reprezentare Int 16 Întreg, reprezentat prin

complement faŃă de 2 Short 16 idem Long 32 idem Unsigned 16 Întreg făra semn unsigned long 32 idem Intervalele de valori pentru datele de tip intreg - Tab.2 Specificarea tipului Intervalul de valori Int [-32768,32767] Short [-32768,32767] Long [-2147483648,2147483647] Unsigned [0,65535] unsigned long [0,4294967295] Tipul predefinit short este identic cu tipul predefinit int la calculatoarele compatibile IBM PC. La alte calculatoare ele pot fi


12

diferite, de exemplu tipul short rămâne reprezentat pe 16 biŃi, iar tipul int poate să fie la fel ca tipul long. Tipul unsigned long poate fi scris inversând cuvintele cheie long unsigned. Operatorii standard pentru datele de tip întreg sunt cei patru operatori aritmetici : + , - , *, / . În cazul în care ambii operanzi sunt de tip întreg operatorul "/" realizează o împărŃire întreagă, adică rezultatul împărŃirii este partea întreagă a câtului. Cu ajutorul împărŃirii întregi se defineşte şi operatorul %-modulo. Dacă m şi n sunt numere întregi , atunci m % n generează restul împărŃirii întregi a lui m la n . Tipul real , în cadrul sistemelor de calcul, precizează o submulŃime reprezentabilă a numerelor reale. Reprezentarea numerelor reale se face în virgulă flotantă (virgulă mobilă) - v.f, simplă precizie (32 biŃi) sau dublă precizie (64 biŃi), sau v.f. format extins (80 biŃi), conform standardului IEEE 754. Pentru a reprezenta un număr real în v.f se aduce numărul la forma binară: N = (-1)s (1. m) 2e

unde s reprezintă semnul; e exponentul; m mantisa (normalizată). Aceasta înseamnă că cel mai semnificativ bit al părŃii fracŃionare este forŃat a fi 1, prin ajustarea exponentului. Întrucât acest bit trebuie să fie 1, el nu este memorat ca parte a numărului. Acesta este numit bitul implicit (sau bit ascuns). În memoria calculatorului, în v.f. numerele se reprezintă sub forma:

S Caracteristica Mantisa(normalizată)


13

s =

pozitivestenumaruldaca

negativestenumaruldaca

0

1 bitul semn

Caracteristica= exponentul + baza În reprezentarea standard IEEE pe 32-biŃi, numită şi reprezentarea în virgulă flotantă simplă precizie (v.f.s.p.) mantisa se reprezintă pe 23 biŃi, iar caracteristica pe 8-biti şi s pe un singur bit. Baza este 127. Numărul zero se va reprezenta în v.f.s.p. prin 32 biŃi egali cu 0. În reprezentarea standard IEEE pe 64-biŃi, numită şi reprezentarea în virgulă flotantă dublă precizie (v.f.d.p.) mantisa se reprezintă pe 52 biŃi, iar caracteristica pe 11-biti şi s pe un singur bit. Baza este 1023. Numărul zero se va reprezenta în v.f.d.p. prin 64 biŃi egali cu 0. În reprezentarea standard IEEE pe 80-biŃi, numită şi reprezentarea în virgulă flotantă extinsă (v.f.ex.) mantisa se reprezintă pe 64 biŃi, iar caracteristica pe 15-biti şi s pe un singur bit. Baza este 16383. Numărul zero se va reprezenta în v.f.ex. prin 80 biŃi egali cu 0. În Limbajul "C", datele reale pot fi de tip: float, double, long double Reprezentarea datelor de tip real- Tab.3 Specificarea tipului Dimensiunea în biŃi Modul de reprezentare float 32 v.f.s.p. double 64 v.f.d.p. long double 80 v.f.ex. Intervalele de valori pentru datele de tip real - T ab.4 Specificarea tipului Intervalul de valori float Valoarea absolută a unei date diferite de zero

aparŃine intervalului [3.4*10-38, 3.4*1038]

double Valoarea absolută a unei date diferite de zero


14

aparŃine intervalului [1.7*10-308, 1.7*10308]

long double Valoarea absolută a unei date diferite de zero aparŃine intervalului

[3.4*10-4932, 3.4*104932] În timp ce aritmetica numerelor întregi conduce la rezultate exacte, aritmetica valorilor de tip real poate fi aproximativă în limitele erorilor de rotunjire, cauzate de efectuarea calculelor cu un număr finit de cifre zecimale. Acesta este principalul motiv al tratării separate a tipurilor întreg şi real în marea majoritate a limbajelor de programare. Operatorii standard pentru datele de tip real sunt cei patru operatori aritmetici : + , - , *, / . Datele de tip caracter-char în "C" se reprezintă pe un octet, prin codul ASCII al caracterului respectiv. Reprezentarea datelor de tip char- Tab.5 Specificarea tipului Dimensiunea în biŃi Modul de

reprezentare char 8 Codul ASCII al

caracterului respectiv Datele de tip caracter pot fi specificate prin: unsigned char sau signed char. În primul caz, se presupune că data este un întreg în intervalul [0,255] (întreg fără semn), iar în cel de-al doilea caz, se presupune că data aparŃine intervalului [-128,127] (întreg cu semn). Datele specificate numai prin char au o interpretare implicită. Această interpretare poate fi definită prin intermediul mediului integrat de dezvoltare Turbo C sau Turbo C++. În mod normal se consideră că datele de tip char sunt numere fără semn. Intervalele de valori pentru datele de tip char - T ab.5 Specificarea tipului Intervalul de valori


15

unsigned char [0,255] signed char [-128,127]

1.2 .2 Tipuri structurate

•••• Tipul tablou Tabloul, în anumite limbaje, este singura structură de date admisă. Un tablou constă din componente care sunt toate de acelaşi tip, numit tip de bază, deci este o structură omogenă. Tabloul se mai numeşte şi structură cu acces direct (random access), deoarece oricare dintre elementele sale sunt direct şi în mod egal accesibile. Pentru a preciza o componentă individuală, numelui întregii structuri i se adaugă un aşa-zis indice care selectează acea componentă. În cazul în care elementele care se grupează într-un tablu sunt ele însele tablouri, vom avea nevoie de mai mulŃi indici, pentru a ne putea referi la ele. În cazul în care se utilizeză un singur indice pentru a ne referi la elementele tabloului, spunem că tabloul este unidimensional. Dacă se folosesc n indici, se spune că tabloul este n-dimensional. Exemple simple de tablouri unidimensionale sunt vectorii care au componente de acelaşi tip. Aşa de exemplu, un vector cu componente întregi este un tablou unidimensional de tip întreg. O matrice de elemente întregi este un exemplu de tablou bidimensional de tip întreg. Referirea la elementele unui tablou se face printr-o variabilă cu indici. O variabilă cu indici se compune din numele tabloului urmat de valorile indicilor, fiecare indice fiind reprezentat printr-o expresie inclusă între paranteze pătrate. Un tablou, ca orice variabilă trebuie să fie declarat înainte de a fi utilizat. DeclaraŃia de tablou, în forma cea mai simplă, conŃine tipul


16

comun elementelor sale, numele tabloului şi limitele superioare pentru fiecare indice, incluse între paranteze pătrate: tip nume[lim1][lim2]…[limn]; unde: tip - este tipul comun elementelor; limi - este limita superioară a indicelui al i-lea; aceasta înseamnă că indicele al i-lea poate avea valorile: 0,1,2,…,limi-1. Limitele limi (i=1,2,…,n) sunt expresii constante. Prin expresie constantă înŃelegem o expresie care poate fi evaluată la compilare în momentul întâlnirii ei de către compilator. În limbajul C, limita inferioară pentru fiecare indice este zero.

Reprezentarea structurilor tablou Memoria unui sistem de calcul poate fi concepută într-o primă aproximaŃie ca un tablou format din celule individuale de memorie numite locaŃii. Indicii acestor locaŃii se numesc adrese. O caracteristică esenŃială a memoriei este dimensiunea acesteia. LocaŃiile de memorie sau multiplii acestora formează aşa-zisele unităŃi de informaŃie (cuvinte, cuvinte duble, etc. ), unităŃi care diferă de la un sistem la altul. Problema reprezentării datelor într-un sistem de calcul constă de fapt în reprezentarea structurilor abstracte în termenii structurilor de date primare standard, implementate de sistemul respectiv, într-un sens mai larg, în exprimarea lor în termenii memoriei fizice a sistemului. La nivelul reprezentării se realizează de fapt corespondenŃa dintre structura de date abstractă (structurile de date care o compun) şi memoria fizică. În forma standard, pe anumite sisteme de calcul, tablourile se memorează în locaŃii succesive de memorie, începând cu o anumită adresă, desemnată prin numele tabloului, linie după linie (la alte


17

sisteme coloană după coloană), în cazul matricilor. Spre exemplu matricea A cu 4 linii şi 5 coloane se reprezintă în limbajul C astfel: A45 → A00 . . . A04 A10 . . . A14 . . . A30 . . . A34

A La întâlnirea unei declaraŃii de tablou, compilatorul alocă pentru tabloul întreg, o zonă contiguă de memorie necesară pentru a păstra valorile tuturor elementelor sale. Pentru fiecare element al tabloului se repartizează o zonă de memorie necesară în conformitate cu tipul tabloului respectiv (pentru tipul int -2 octeŃi, pentu long- 4 octeŃi, etc.). Numele unui tablou este un simbol care are ca valoare chiar adresa primului element al tabloului respectiv. Altă posibilitate de implementare a tablourilor bidimensionale este următoarea: un tablou A declarat cu limita superioară m respectiv n, constă din (m+1) tablouri unidimensionale (liniile), primul dintre aceştia fiind un tablou format din m pointeri. Elementul i al acestui tablou este un pointer la linia i. m n Exemplu: în limbajul C, printr-o declaraŃie int A[ 3 ][ 5 ] cu limita inferioară a indicilor de linie şi coloană 0, reprezentarea elementelor matricei se poate face sub forma (depinde de interpretor dacă se face aşa sau nu) : rând 0 A00 A01 A02 A03 A04 rând 1 A10 A11 A12 A13 A14 rând 2 A20 A21 A22 A23 A24


18

Pentru a referi elementul A[i][j], tabloul A este mai întâi accesat pentru a obŃine pointerul la linia i [deci se parcurge primul tablou unidimensional (rând) şi elementul de pe poziŃia i a acestui tablou ne va furniza adresa liniei i]. Este parcurs apoi tabloul de la adresa determinată şi elementul de pe poziŃia j va fi A[i][j]. Tablourile unidimensionale de tip caracter se utilizează pentru a păstra şiruri de caractere. În felul acesta se suplineşte lipsa tipului şir de caractere , existent în alte limbaje de programare.

Sortarea tablourilor Prin sortare se înŃelege în general reordonarea unei mulŃimi de elemente într-o ordine specificată de utilizator, cu scopul de a facilita căutarea ulterioară a unui element dat. Sortarea este o activitate fundamentală cu caracter universal. Spre exemplu în cartea de telefon, în dicŃionare, în depozitele de mărfuri şi în general în orice situaŃie în care trebuie căutate şi regăsite obiecte, sortarea este prezentă. În cele ce urmează vom presupune că sortarea se referă la anumite elemente care au structura de articol definită după cum urmează:

struct element { int cheie; [alte câmpuri]

};

Câmpul cheie precizat, pote fi neesenŃial din punct de vedere al informaŃiei înregistrate în articol, partea esenŃială a informaŃiei fiind conŃinută de regulă în celelalte câmpuri. Din punct de vedere al sortării însă, cheie este cel mai important câmp întrucât se va adopta următoarea definiŃie a sortării: Defini Ńie: Fiind date elementele de tipul definit mai sus a[0], a[1], ... , a[n-1], prin sortare se înŃelege permutarea elementelor într-o


19

anumită ordine: a[k1], a[k2], ... , a[kn] astfel încât şirul cheilor să devină monoton crescător (sau descrescător), adică: a[k1].cheie≤ a[k2].cheie≤ ...≤ a[kn].cheie Tipul cheii l-am presupus a fi întreg pentru o înŃelegere mai uşoară, în realitate el poate fi de orice tip scalar. O metodă de sortare se spune că este stabilă dacă după sortare, ordinea elementelor cu chei egale coincide cu cea iniŃială. Metodele de sortare sunt clasificate în două mari categorii după cum elementele de sortat sunt înregistrate în memoria centrală sau într-o memorie externă. În primul caz elementele se pot considera a fi organizate într-o structură de tablou şi în consecinŃă ele sunt accesibile într-o ordine oarecare, respectiv în orice moment pot fi comparate între ele oricare dintre chei. În al doilea caz elementele formează o structură secvenŃială de fişier, structură care permite accesul la chei numai în ordine secvenŃială. Din acest motiv, algoritmii de sortare se clasifică în două mari categorii: sortarea tablourilor numită şi sortare intern ă şi sortarea fişierelor numită şi sortare extern ă.

CerinŃa fundamentală care se formulează faŃă de metodele de sortare a tablourilor se referă la utilizarea cât mai economică a zonei de memorie disponibilă. Din acest motiv, prezintă interes numai algoritmii care, dat fiind tabloul A, realizează sortarea chiar în zona de memorie alocată tabloului (sortare „in si tu”). Algoritmii de sortare vor fi clasificaŃi în funcŃie de eficienŃa lor, respectiv în funcŃie de timpul de execuŃie pe care îl necesită. Aprecierea cantitativă a eficienŃei unui algoritm se realizează prin intermediul unor indicatori specifici. Un astfel de indicator este numărul comparărilor de chei, notat cu C, pe care le execută algoritmul. Un alt indicator este numărul asignărilor de elemente, respectiv numărul de mişcări de elemente executate de algoritm,


20

notat cu M. Ambii indicatori depind de numărul total N al elementelor care trebuiesc sortate.

Tehnica de sortare prin inserŃie

Elementele sunt divizate într-o secvenŃă destinaŃie a[0], a[1],...., a[i-1] şi într-o secvenŃă sursă a[i], a[i+1], ..., a[n-1]. La fiecare pas începând cu i=1 şi incrementând pe i cu 1 , cel de-al i-lea element al secvenŃei sursǎ este luat şi transferat în secvenŃa destinaŃie prin inserarea sa la locul potrivit. Astfel la început se sortează primele douǎ elemente, apoi primele trei ş.a.m.d. . Fie tabloul A= ( 34, 65, 12 , 22, 83, 18, 4, 67 ) ; i = 1. Se comparǎ A[1] cu elementul din faŃa sa cu A[0]. 65 > 34, A[1] rǎmâne pe locul lui, A= ( 34, 65, 12 , 22, 83, 18, 4, 67 ) ; i = 2. Se compară A[2] cu elementele din faŃa sa. Selectarea locului în care trebuie inserat A[i] se face parcurgând şirul A[0], ... , A[i-1] de la dreapta la stânga, oprirea realizându-se pe primul element A[j] care are cheia ≤ cu A[i]. Se reŃine în k acest indice j. Dacǎ nu existǎ un astfel de element, k = -1. Se salveazǎ A[i] într-o variabilǎ auxiliarǎ Aux. Toate elementele A[k+1], ... , A[i-1] se mută spre dreapta cu o poziŃie şi apoi se copiază Aux pe poziŃia lui A[k+1].În cazul nostru 65 > 12 , 34 > 12 => k=-1, Aux = 12, A =( 34, 34, 65 , 22, 83, 18, 4, 67 ). Se copiază apoi Aux pe poziŃia A[k+1] =>A=( 12, 34, 65 , 22, 83, 18, 4, 67 ); i = 3. => j=0 => k=0 => Aux = 22. A =(12, 34, 34, 65, 83, 18, 4, 67)=> A[k+1]=Aux =>A=(12, 22, 34, 65, 83, 18, 4, 67); i = 4. => j =3 => k=3 deci nu se face nici o mutare. A=(12, 22, 34, 65, 83, 18, 4, 67);


21

i = 5. => j =0 => k=0 => Aux = 18 => A=(12, 22, 22, 34, 65, 83, 4, 67), apoi A[k+1] = Aux => A=(12, 18, 22, 34, 65, 83, 4, 67); i = 6. => nu există j astfel încât A[j] < A[i] => k=-1 => Aux = 4 => A=(12, 12, 18, 22, 34, 65, 83, 67) => A[k+1] =4 => A= ( 4, 12, 18, 22, 34, 65, 83, 67) ; i = 7. => j =5 => k=5 => Aux = 67=> A=(4,12, 18, 22, 34, 65, 83, 83) => A[k+1]= 67 => A=(4, 12, 18, 22, 34, 65, 67, 83).

DA

NU

START

P

Cit n, a[i], i=0,n-1

i=1

i<n

Scrie a[i], i=0,n-1

STOP

DA j ≥ 0 si a[j].cheie>a[i].cheie

NU

P

j=i-1

j=j-1

k=j

NU

a[j+1]=a[j] j=j-1

aux=a[i]

j > k

j=i-1

DA


22

Sortarea prin inser Ńie

Analiza sort ării prin inser Ńie În cadrul celui de-al i-lea ciclu, numărul ci al comparărilor de chei depinde de ordinea iniŃială a acestora, fiind cel puŃin 1, cel mult i-1 ( presupunând că toate permutările celor n chei sunt egal posibile). Întru-cât avem n-1 paşi, pentru n 2,i = se obŃin următoarele valori :

∑−

=

−==1

1min 11

n

i

nc 22

)1()1(

21

1max

nnnnic

n

i

−=−=−=∑−

=

4

2

2

2maxmin −+=+= nncc

cmed

Numărul de asignări de elemente în cadrul unui ciclu este ((a[j+1]:=a[j]) de ci ori, la care se mai adaugă aux=a[i], a[k+1]=aux) ci+2. Mmin= sunt cel puŃin două asignări în acest caz şi cum sunt ( 1,1 −= ni ) n-1 cicluri ⇒ Mmin=2(n-1).

∑ ∑∑−

=

−

=

−

=

−+=+=+−=+=1

1

1

1

21

1max 2

43)1()21()2(

n

i

n

i

n

ii

nniicM

4

87

2

2maxmin −+=+= nnMM

Mmed

Se observă că atât C cât şi M sunt de ordinul n2 [deci funcŃii de n2]. Valorile minime ale indicatorilor rezultă când A este ordonat,

i=i+1

a[k+1]=aux

Exit


23

iar valorile maxime, când A este ordonat invers. Sortarea prin inserŃie este o sortare stabilă. Algoritmul de sortare prin inserŃie poate fi imbunătăŃit pornind de la observaŃia că secvenŃa destinaŃie este deja ordonată. În acest caz căutarea locului de inserare se poate face mult mai rapid utilizând tehnica căutării binare, prin împărŃiri succesive în două părŃi egale a intervalului vizat. Algoritmul modificat se numeşte inser Ńie binar ă.

DA

NU

START

P


i=1

i<n

Scrie a[i], i=0,n-1

STOP

NU

DA

DA

P

s=0 d=i

s < d P1

NU

a[d]=aux

j=i-1

j ≥ d a[j+1]=a[j]

j=j-1

aux=a[i]

NU DA

d=m

P1

m=[s+d]/2

a[m]≤a[i]

s=m+1

Exit


24

Sortarea prin inserŃie binara Analiza inser Ńiei binare. PoziŃia de inserat este găsită dacă A[j].cheie ≤ A[i].cheie (elementul căutat) ≤ A[j+1].cheie. În final intervalul de căutare trebuie să fie egal cu 1, ceea ce presupune înjumătăŃirea intervalului pentru i chei în [log2 i] paşi. Astfel

112

1

21

2 )(log][log][log ccnndxxiCnn

i

+−=≅= ∫∑=

,

unde C1 = log2 e = 1/ ln2=1.44269… Numărul comparaŃiilor este în principiu independent de ordinea iniŃială a cheilor. Cu toate acestea din cauza trunchierii în operaŃia de împărŃire întreagă, numărul de comparaŃii necesare pentru i elemente poate fi cu 1 mai mare decât cel calculat. Numărul minim de comparaŃii se obŃine pentru un şir ordonat invers, iar numărul maxim pentru un şir ordonat. Acesta este un caz de comportament anormal al unui algoritm de sortare. Din nefericire beneficiile căutării binare se răsfrâng numai asupra numărului de comparaŃii şi nu asupra numărului de mişcări. De regulă mutarea cheilor şi a informaŃiilor asociate necesită mai mult timp decât compararea a două chei. Cu toate că M rămâne de ordinul n2, performanŃele acestei metode de sortare nu cresc în măsura în care ar fi de aşteptat. Resortarea unui tablou gata sortat prin metoda inserŃiei binare, necesită mai mult timp decât inserŃia cu căutare secvenŃială.


25

În ultimă instanŃă sortarea prin inserŃie nu este o metodă potrivită de sortare pe calculator, deoarece inserŃia unui element presupune deplasarea cu o poziŃie în tablou a unui şir de elemente, deplasare care nu este economică. Acest dezavantaj conduce la ideea construirii unor algoritmi în care mişcările se realizează asupra unui singur element şi pe distanŃe mari.

Tehnica sortării tablourilor prin selecŃie Acest algoritm foloseşte procedeul de a căuta elementul cu cheia minimă şi de a schimba între ele poziŃiile acestui element şi a primului element. Se repetă acest procedeu cu cele n-1 elemente rămase, apoi cu cele n-2, etc. , terminând cu ultimele două elemente. Exemplu: Presupunem vectorul (iniŃial) de sortat: A=(34,65,12,22,83,18,04,67) Căutăm minimul şi efectuăm schimbarea ⇒ i=0 A=(34,65,12,22,83,18,04,67) ⇒ A[0] ↔ A[6] i=1 A=(04,65,12,22,83,18,34,67) ⇒ A[1] ↔ A[2] i=2 A=(04,12,65,22,83,18,34,67) ⇒ A[2] ↔A[5] i=3 A=(04,12,18,22,83,65,34,67) ⇒ A[3] ↔ A[3] i=4 A=(04,12,18,22,83,65,34,67) ⇒ A[4] ↔ A[6] i=5 A=(04,12,18,22,34,65,83,67) ⇒ A[5] ↔A[5] i=6 A=(04,12,18,22,34,65,83,67) ⇒ A[6] ↔ A[7]


26

şi obŃinem vectorul ordonat: A=(04,12,18,22,34,65,67,83) Analiza eficien Ńei sort ării prin selec Ńie. Numărul comparărilor de chei C este independent de ordinea iniŃială a cheilor. În acest sens, această metodă se comportă mai puŃin natural decât inserŃia:

22

)1( 22

0

nnnniC

n

i

−=−==∑−

=

DA

NU

START

P


i=0

i<n-1

Scrie a[i], i=0,n-1

STOP

DA

NU

A[k]=A[i] A[i]=min

i=i+1

Exit

j<n Min

P

k=i min=A[i]

j=i+1

DA

NU

Exit

Min

min>a[j]

min=a[j] k=j

j=j+1


27

(Când i=0 se compară min cu A1 , … , An-1 deci n-1 comparaŃii ………………………………………………………………………… i=n-2 se compară min cu xn-1 , deci o comparaŃie) Numărul asignărilor de chei este de cel puŃin 3 pentru fiecare valoare a lui i, [ min=A[i], (l=i), A[l]=A[i], A[i]=min ] de unde rezultă:

Mmin = 3(n-1) Acest minim poate să apară efectiv, dacă iniŃial cheile sunt deja sortate. Pe de altă parte dacă cheile sunt iniŃial în ordine inversă, spre exemplu : A=(80, 70, 60, 50, 40, 30, 20, 10), aplicând algoritmul avem: i=0. Se atribuie lui min 7 valori (j=1..7) [ căci la compararea lui min cu A[j], j=1..n-1 de fiecare dată min>A[j] şi se va face schimbarea min=A[j] ]. Se schimbă apoi poziŃia 0 cu poziŃia 7; i=1. Se atribuie lui min 5 valori (j=2..6) [ A[7]=80, este cea mai mare

valoare, deci nu se mai efectuează schimbarea min=A[7] ]. Apoi se schimba poziŃia 1 cu poziŃia 6.

i=2. Se atribuie lui min 3 valori (j=3..5) apoi se schimbă poziŃia 2 cu poziŃia 5

i=3. Se atribuie lui min o valoare (min=A[4]), apoi se schimbă poziŃia 3 cu poziŃia 4;

În continuare pentru I=4..6 nu se mai fac schimbări ale minimului (deoarece şirul este deja ordonat.). Se vor mai face cele trei schimbări pe aceaşi poziŃie (min=A[4], l=i, A[l]=A[i], A[i]=min). Deci în total vom avea: [7+5+3+1]+3(8-1) = 16+21 schimbări sau

4

82

+3(8-1)=16+21 schimbări.

În general

Mmax= [(n-1)+(n-3)+…+1]+3(n-1) = = (n-1)+(n-2)+(n-3) +…+ 3+2+1 -


28

- [(n-2)+(n-4) +…+4+2]+3(n-1)=

1)3(n4

2n

1)3(n2n

22n

21)n(n

1)3(n2

1)2

2n(

22n

22

1)n(n

−+=

=−+⋅−−−=

=−++−−

−+=

Valoarea medie a lui M nu este media aritmetică a lui Mmin şi Mmax ci se obŃine printr-un raŃionament probabilistic ca fiind

Mmed=n(ln(n)+y)+1, unde y=0.5772 este constanta lui Euler. În concluzie algoritmul bazat pe selecŃie este de preferat celui bazat pe inserŃie, cu toate că în cazurile în care cheile sunt ordonate, sau aproape ordonate, sortarea prin inserŃie este mai rapidă.

Tehnica sortării prin interschimbare Principiul de bază al acestei metode este următorul: se compară şi se interschimbă perechile de elemente alăturate până când toate elementele sunt sortate. Ca şi la celelalte metode, se vor realiza treceri repetate prin tablou de fiecare dată deplasând cel mai mic element al mulŃimii rămase spre capătul din stânga al tabloului. Dacă vom considera tabloul în poziŃie verticală şi vom asimila elementele sale cu nişte bule de aer în interiorul unui lichid, fiecare bulă având o greutate proporŃională cu valoarea cheii, atunci fiecare trecere prin tablou se soldează cu ascensiunea unei bule la nivelul specific de greutate. Din acest motiv această metodă de sortare este cunoscută sub denumirea de bubblesort (sortarea prin metoda bulelor) în


29

literatură. Schema logică şi programul aferent acestei metode sunt prezentate in continuare: Se poate Ńine o evidenŃă dacă a avut sau nu loc cel puŃin o schimbare în urma unei treceri prin tablou. Un ultim pas fără

DA

NU

START

P


i=1

i≤n-1

Scrie a[i], i=0,n-1

STOP

NU

DA

i=i+1

Exit

j>=i P1

P

j=n-1

a[j-1]>a[j]

Exit

P1

aux=a[j-1] a[j-1]=a[j] a[j]=aux

j=j-1

NU

DA


30

schimbări este necesar pentru a determina dacă algoritmul s-a terminat.

NU

DA

START

Citeste n, a[i],i=0,n-1

i=1

i<=n-1 || sw==1

P

Tip a[i],i=0,n-1

STOP

NU

DA

Exit

j>=i P1

P

sw=0

i=i+1

j=n-1

NU

Exit

P1

aux=a[j-1] a[j-1]=a[j] a[j]=aux

sw=1

j=j-1

a[j-1]>a[j]

DA


31

Bubblesort mai poate fi îmbunătăŃit, Ńinând minte ultima poziŃie a elementului k, care are proprietatea că toate elementele care preced poziŃia k sunt deja ordonate, analizele ulterioare putând fi terminate în acest loc. Algoritmul prezintă o asimetrie particulară. Un singur element uşor plasat la capătul greu al tabloului este readus la locul sau într-o singură trecere, în schimb un element greu plasat la capătul uşor al tabloului va fi readus spre locul sau doar câte o poziŃie la fiecare trecere. Spre exemplu tabloul: A=(12 18 22 34 65 67 83 04) va fi sortat cu ajutorul metodei bubblesort printr-o singură trecere, în schimb tabloul: A=(83 04 12 18 22 34 63 67) va necesita 7 treceri în vederea sortării. Această neobişnuită asimetrie sugerează o a treia îmbunătăŃire: alternarea sensurilor de parcurgere ale trecerilor consecutive. Algoritmul corespunzător se va numi shakesort (sortare prin amestecare).

NU

DA

START

Citeste n, a[i],i=0,n-1

s=0

s<=d

P

Tipareste a[i], i=0,n-1

STOP

d=n-2 k=n-1

DA

NU

NU

DA

Exit

i<=d P2

P

i=d

i=s

i>=s P1

s=k+1

d=k-1


32

Analiza sort ării bubblesort şi shakesort. Numărul comparaŃiilor la algoritmul bubblesort este :

2

)1(1

1

−==∑−

=

nniC

n

i

Iar valorile minimă, maximă şi medie a numărului de mişcări (de chei) sunt :

Mmin = 0, Mmax = 3C ,2

)1(3 −=

nn Mmed ,4

)(3 2 nn −=

În ceea ce priveşte sortarea prin amestecare, numărul mediu de comparaŃii este uşor redus faŃă de algoritmul bubblesort.

•••• Tipul stuctur ă (struct) Metoda cea mai generală de obŃinere a tipurilor structurate este aceea de a reuni elemente ale mai multor tipuri, unele dintre ele la rândul lor structurate într-un tip complex. Setul de valori posibile


33

ale tipului compus constă din toate combinaŃiile posibile ale valorilor tipurilor componente, selectând câte o singură valoare din fiecare. O astfel de combinaŃie se numeşte n-tuplu; numărul acestor combinaŃii este egal cu produsul numerelor de elemente ale fiecărui tip constitutiv. Datele care se grupează formează o structur ă - în C, respectiv un articol sau o înregistrare (record) - în PASCAL. Unei structuri i se ataşează un nume. De asemenea, se ataşează câte un nume fiecărei componente ale unei structuri, nume care se utilizează la referirea componentelor respective.

Componentele structurii se numesc câmpuri iar numele lor se numesc identificatori de câmp. Accesul la câmpurile unei variabile structurate de tip structură se face precizând numele câmpului şi numele structurii căreia îi aparŃine câmpul. Un exemplu simplu de structură este data calendaristică, care se compune din zi, lună şi an, unde: zi şi an sunt de tip întreg iar luna este un tablou de tip caracter. Structura, ca şi tabloul, este o mulŃime ordonată de elemente. În exemplul de mai sus se consideră că zi este primul ei element, luna al doilea, iar an ultimul ei element. O structură se declară în felul următor: struct nume { istă de declaraŃii } nume1,nume2, … , numen; unde: nume, nume1,nume2, … , numen - sunt nume care pot şi lipsi, dar nu toate deodată.


34

Dacă nume este absent, atunci măcar nume1 trebuie să fie prezent. Dacă lisata: nume1,nume2, … , numen este vidă, atunci nume trebuie să fie prezent. Nume se poate utiliza în continuare pentru a declara date şi el se consideră un tip nou de dată, introdus prin declaraŃia de structură. Nume1,nume2, … , numen sunt date care au tipul nume, adică structuri de tipul nume. Lista de declaraŃii - se compune din una sau mai multe declaraŃii. Exemplu: Data calendaristică indicată mai sus, se poate declara în felul următor: struct data_calend { int zi; char luna[11]; int an; } data_nasterii, data_angajarii; Prin aceasta s-a introdus tipul structurat data_calend. Data_nasterii, data_angajarii sunt structuri de tipul data_calend. Dacă în program nu dorim să declarăm şi alte date de tipul data_calend, atunci în declaraŃia de mai sus nu era nevoie să se introducă tipul data_calend şi deci putem folosi declaraŃia: struct { int zi; char luna[11]; int an;


35

} data_nasterii, data_angajarii; Modul cel mai frecvent întâlnit este acela în care prin declaraŃia de structură introducem numai tipul ei: struct data_calend { int zi; char luna[11]; int an; }; Apoi definim datele de tipul data_calend în felul următor: struct data_calend data_nasterii, data_angajarii; Am văzut în paragraful 1.2.1 că tipurile de bază ale limbajului C (tipurile primitive standard) numite şi tipuri predefinite, se identifică prin cuvinte cheie (int, long, float, char, etc.), iar tipurile definite de utilizator se introduc printr-o declaraŃie de forma: struct nume {…}; Programatorul poate să atribuie un nume unui tip, indiferent de faptul că acesta este un tip predefinit sau definit de utilizator. Aceasta se realizează prin intermediul construcŃiei typedef. Ea are următorul format: typedef tip nume_tip; unde: tip - Este fie numele unui tip predefinit, fie o declaraŃie de tip definită de utilizator;


36

nume_tip - Este numele atribuit tipului respectiv. Odată atribuit un nume unui tip, numele respectiv poate fi utilizat pentru a declara date de acel tip, exact la fel cum se utilizează în declaraŃii cuvintele cheie int, float etc. ConstituenŃii unei structuri pot fi la rândul lor structuraŃi. Această situaŃie duce la concatenarea selectorilor. În mod evident, tipuri structurate diferite pot fi utilizate într-o manieră încuibată. Astfel, cea de-a i-a componentă a unui tablou A care la rândul său este o componentă a unei variabile structurate R se precizează prin R.A[i ], după cum componenta având numele (de selector) S aparŃinând componentei i de tip structură a unui tablou A este precizată prin A[i].S . Structurile tablou şi structură au proprietatea comună că sunt ambele cu “acces direct”. Structura are un caracter mai aprofundat de generalitate, deoarece nu presupune identitatea tipurilor constituenŃilor. În schimb, structura de tablou este mai flexibilă, permiŃând ca selectorii componentelor să ia valori calculabile reprezentate prin expresii, în timp ce selectorii unei structuri sunt identificatori ficşi, declaraŃi la definirea structurii.

� Reprezentarea structurii

Structurile sunt reprezentate în memoria unui sistem de calcul prin simpla alăturare a componentelor lor. Adresa unei componente (câmp) ci relativă la adresa de origine a structurii S se numeşte deplasamentul (offset) ki al componentei. El se calculează astfel : ki = s1 + s2 + . . . + si-1 unde sj j=1,i-1 este mărimea în unităŃi de informaŃie a celei de-a j-a componente. Caracterul de generalitate al unei structuri de tipul struct nu permite calculul simplu al deplasamentelor câmpurilor ca şi în cazul


37

tablourilor, motiv pentru care a fost adoptată selecŃia componentelor prin identificatori ficşi. Această restricŃie are marele avantaj că deplasamentele respective sunt cunoscute în momentul compilării. EficienŃa utilizării acestei metode este binecunoscută.

•••• Structura secven Ńă Caracteristica comună a structurilor prezentate până acum (tablouri, articole) este aceea că au cardinalitatea finită, respectiv cardinalitatea tipurilor lor componente este finită. Din acest motiv implementarea lor nu ridică probleme deosebite. Cele mai multe din aşa-numitele structuri avansate : secvenŃele, listele, arborii, grafurile, etc., sunt caracterizate prin cardinalitate infinită. Această diferenŃă faŃă de structurile fundamentale este de profundă importanŃă având consecinŃe practice semnificative. Spre exemplu structura secvenŃă se defineşte după cum urmează : DefiniŃie. O secvenŃă cu tipul de bază T0, este fie o secvenŃă vidă, fie o concatenare a unei secvenŃe cu tipul de bază T0 cu o valoare a tipului T0. Definirea recursivă a unui tip secvenŃă conduce la o cardinalitate infinită (fiecare valoare a tipului secvenŃă conŃine un număr finit de componente de tip T0 dar numărul valorilor este nemărginit, deoarece pornind de la orice secvenŃă se poate construi o secvenŃă mai lungă). O primă consecinŃă a acestui fapt este aceea că volumul de memorie necesar reprezentării unei structuri avansate nu poate fi cunoscut în momentul compilării, fiind necesară aplicarea unor scheme de alocare dinamică a memoriei, în care memoria este alocată structurilor care “cresc” şi este eliberată de către structurile care “descresc”. La o secvenŃă accesul este numai secvenŃial adică o secvenŃă este inspectată trecând strict de la un element la succesorul lui şi este generată adăugând respectiv un element la sfârşitul secvenŃei.


38

Noua structură derivată din secvenŃă se numeşte fişier secvenŃial sau fişier cu organizare secvenŃială.

•••• Structura de date de tip fi şier Fişierul reprezintă termenul generic care desemnează structurile de date externe. El este o mulŃime (o colecŃie) ordonată de date omogene din punctul de vedere al semnificaŃiei şi al cerinŃelor de prelucrare. Pe suportul extern, fişierul are, pe lângă partea de date, şi alte informaŃii de identificare (etichete ). Privit din punctul de vedere al prelucrării, un fişier este o colecŃie ordonată de date, numite articole (sau înregistrări ). Componentele articolului sunt denumite câmpuri de date . Depinzând de natura, ordinul de mărime, şi forma de reprezentare externă a valorilor asociate, fiecare câmp de date are o lungime, exprimată uzual în octeŃi. Lungimea unui articol este dată de suma lungimilor câmpurilor componente. După cum toate articolele dintr-un fişier au sau nu aceeaşi lungime, se face distincŃie între fişiere cu articole de lungime fixă sau variabilă. Modul de implementare fizică a celor două tipuri de fişiere diferă de la un sistem la altul şi chiar de la un limbaj de programare la altul. (Limbajul PASCAL acceptă atât fişiere cu articole de lungime fixă- stabilită la momentul fiecărei prelucrări , cât şi de lungime variabilă - implementată prin separarea fizică a două înregistrări alăturate de exemplu prin CR/LF.) Pe purtătorul fizic extern, partea de date a fişierului se prezintă ca o succesiune de octeŃi cu un conŃinut binar fără semnificaŃie informaŃională. În momentul prelucrării, prin descrieri şi operaŃii adecvate, din succesiunea memorată extern se “decupează” entităŃi (articole, blocuri, linii sau câmpuri) cu structuri corespunzătoare prelucrării.Tipul entităŃii care se decupează depinde de tipul fişierului. Datele care se scriu la imprimantă formează un fişier, înregistrarea identificându-se cu datele scrise pe un rând.


39

În aceeaşi idee, se consideră că datele introduse de la un terminal formează un fişier de intrare. Înregistrarea se consideră că este formată din datele unui rând tastate la terminal, deci caracterul de rând nou (newline) se consideră ca fiind terminator de înregistrare. În mod analog datele care se afişează pe terminal formează un fişier de ieşire. Şi în acest caz înregistrarea este formată din caracterele unui rând. În cazul fişierelor de intrare a căror date se introduc de la terminal, sfârşitul de fişier se generează în funcŃie de sistemul de operare considerat. Aşa de exemplu, sub sistemele de operere: MS-DOS - se tastează CTRL/Z; UNIX - se tastează CTRL/D.

� Metode de organizare şi tipul de acces Principiile şi regulile după care se memorează articolele unui fişier pe purtătorul extern cu asigurarea protecŃiei şi regăsirii acestora constituie metoda de organizare. Modurile de organizare a datelor în fişiere, întâlnite în mod uzual, sunt : 1. Organizarea secvenŃială; 2. Organizarea aleatoare; 3. Organizarea relativă; 4. Organizarea indexată. Modurile de organizare determină modurile de acces, adică modalităŃile prin care înregistrările unui anumit fişier pot fi scrise sau citite. Accesul la înregistrări poate fi secvenŃial sau direct. PoziŃia din/în care se face citirea/scrierea în cadrul fişierului este indicată de un pointer. Accesul la datele înregistrate pe un purtător tehnic poate fi secvenŃial sau direct, în funcŃie de modul în care se stabileşte pointerul.


40

Accesul secvenŃial este posibil la toŃi purtătorii tehnici de date şi presupune înscrierea înregistrărilor în ordinea furnizării lor, sau regăsirea în ordinea în care au fost înscrise pe suport. Pointerul de fişier avansează, în scriere şi citire, de la o entitate (articol, bloc, linie sau câmp) la alta. Dacă pointerul se exprimă prin deplasare faŃă de începutul fişierului, atunci, matematic, acest lucru se poate exprima astfel: P(A1)=0; P(Ak)=f(P(Ak-1))=P(Ak-1)+lartk-1; pentru k=2,n; unde Ak este articolul k şi lartk este lungimea articolului k. P(Ak)=f(P(Ak-1)) Traversare A1 A2 . . . Ak-1 Ak . . . An EOF Fig.1.1. Principiul de realizare a accesului secvenŃial la articole O problemă importantă care se pune la consultarea (citirea) în acces secvenŃial este controlul ajungerii la sfârşitul fişierului. După citirea ultimei entităŃi (articol, bloc, linie sau câmp), pointerul indică marcatorul de sfârşit de fişier - EOF (fig.1.2). Pointerul după citirea ultimului articol

A1 A2 . . . Ak-1 Ak . . . An EOF Fig.1.2. Pointerul după citirea ultimului articol din fişier În limbajele de programare se regăsesc două modalităŃi de sesizare a sfârşitului de fişier: a) Sesizarea sfârşitului de fişier în cadrul operaŃiei de citire (limbajele FORTRAN, COBOL). Sfârşitul este sesizat la citirea marcatorului de sfârşit de fişier. SituaŃia din figura 1.2 nu este considerată sfârşit de fişier. Abia la următoarea citire se întâmplă


41

acest lucru (pointerul de fişier avansează după marcatorul de sfârşit de fişier). b) Sesizarea sfârşitului de fişier independent de operaŃia de citire (limbajele BASIC, PASCAL, C). În acest caz, dacă pointerul este pe marcatorul de sfârşit de fişier (după ultimul articol, bloc, linie, câmp ca în figura 1.2) se consideră sfârşit de fişier. Următoarea citire produce eroare de intrare/ieşire (I/E). Proiectarea algoritmilor de prelucrare a fişierelor este determinată de modalitatea în care se sesizează sfârşitul de fişier.

Accesul direct este posibil numai la fişierele care au o anumită organizare, au ca entitate de transfer articolul sau blocul. Accesul direct se bazează pe existenŃa unui algoritm (algoritmul de randomizare) care asigură regăsirea (localizarea) articolelor în funcŃie de o informaŃie de regăsire (cheia articolului). Valoarea pointerului este determinată direct, fără să depindă de valoarea sa anterioară: P(Ak)=f(irk), unde Ak este articolul k, iar irk este o informaŃie de regăsire a articolului k. În funcŃie de algoritmul şi informaŃia de regăsire, există două tipuri de acces direct: după cheie şi după numărul relativ al articolului. În cazul accesului direct după cheie, articolul este regăsit prin aplicarea unui algoritm asupra unei informaŃii de identificare de tip cheie: P(Ak)=f(cheiek). Accesul direct după cheie nu este implementat în limbajul C (la microcalculatoare IBM-PC se regăseşte numai în limbajul COBOL). În cazul accesului direct după numărul relativ - care se mai numeşte, simplu, acces relativ - (figura 1.3), articolul este localizat în fişier prin numărul său, stabilit în cadrul fişierului de la valoarea zero: P*(Ak)=(k-1); P(Ak)=P*(Ak)×lart. P(Ak) reprezintă poziŃia exprimată prin deplasare, în octeŃi, faŃă de începutul fişierului (la unele sisteme numărul relativ este stabilit de la unu şi atunci P*(Ak)=k). La scriere, articolul Ak (numărul relativ k-1) se memorează pe poziŃia sa, celelalte k-1 articole anterioare putând să nu existe (pe suport există însă rezervat loc pentru ele). La citire, articolul Ak (cu


42

numărul relativ k-1, k≤n) este localizat direct şi conŃinutul lui se transferă în memoria internă. Acces direct prin numărul relativ k-1 P*(Ak)=k-1 A 1 A 2 . . . A k-1 A k . . . A n EOF 0 1 k-2 k-1 n-1 Număr relativ Fig. 1.3 Principiul de realizare a accesului direct prin număr relativ

Organizarea secvenŃială Într-un fişier de organizare secvenŃială articolele sunt depuse în mod continuu pe suport (în locaŃii succesive). Un astfel de fişier poate fi organizat pe orice tip de suport (reutilizabil sau nereutilizabil). Fişierele organizate secvenŃial, cu articole de lungime variabilă, admit numai accesul secvenŃial. Fişierele organizate secvenŃial, cu articole sau blocuri de lungime fixă, admit atât accesul secvenŃial cât şi pe cel relativ. Acest lucru derivă din faptul că accesul relativ este realizat de sistem printr-o deplasare secvenŃială faŃă de începutul acestuia, deplasare care este egală cu valoarea expresiei: număr_relativ ×××× lungime_articol.

Organizarea aleatoare Acest tip de organizare presupune memorarea înregistrărilor în fişier în funcŃie de valoarea unui anumit câmp din înregistrare, numit cheia înregistrării. Orice operaŃie de I/E referitoare la o înregistrare


43

este precedată de efectuarea calculului de adresă, pornind de la valoarea cheii articolului ce trebuie găsit. Pentru a evita calcularea repetată a adreselor, acestea sunt păstrate într-un dicŃionar alături de valorile cheilor corespunzătoare. Regăsirea unui articol de o anumită cheie, în acest caz, este precedată de folosirea dicŃionarului care furnizează adresa. Determinarea efectivă a adresei se face prin tehnici de randomizare (hashing). În funcŃie de metoda aleasă este posibil să rezulte o aceeaşi adresă pentru înregistrări cu chei diferite. În acest caz aceste înregistrări se numesc sinonime. Dintre cei mai cunoscuŃi algoritmi de hashing menŃionăm : a) ÎmpărŃirea cu un număr prim, mai mic, cel mult egal cu numărul de adrese disponibile în fişier. (O adresă precizează cilindrul, pista, sectorul de pe disc). Restul rezultat se consideră ca adresă; b) Metoda ridicării la pătrat. Cheia se ridică la pătrat, iar numărul format din cifrele de la mijlocul rezultatului este multiplicat cu un coeficient astfel încât rezultatul să fie o adresă.

Ex: Dacă fişierul are 3000 adrese(zone) şi se dă o cheie ki =530971, ki ∗ ki =281930202841. Numărul format cu cifrele mijlocii (poziŃiile 5,6,7,8) se înmulŃeşte cu coeficientul 0,3 şi se află adresa ai =3020∗0,3=906; c) Cheia este folosită ca intrare într-un generator de numere aleatoare a cărui ieşire este chiar adresa; d) Metoda schimbării bazei; e) Metoda împărŃirii polinoamelor.

Organizarea relativă Într-un fişier de organizare relativă informaŃiile sunt organizate în celule numerotate de la 1 la n, 1 - prima celulă, n - ultima celulă, fiecare celulă având aceeaşi lungime. Numărul celulei reprezintă


44

poziŃia relativă a celulei respective în cadrul fişierului. Fiecare celulă conŃine un singur element. Numărul unui element, deci al celulei, va fi folosit pentru identificarea articolului respectiv în cadrul programului. De exemplu al zecelea articol din fişier va fi identificat prin numărul 10, indiferent dacă în primele 9 celule sunt sau nu memorate alte elemente. Dimensiunea unei celule va fi precizată în momentul creerii fişierului. De asemenea numărul maxim de celule din fişier va fi precizat tot la crearea fişierului. Un astfel de fişier poate exista numai pe disc. Accesul este direct prin numărul articolului (Ex. FORTRAN -77 ).

Organizarea indexată Elementele fişierului, informaŃia este identificată după valoarea unui anumit câmp din articol, numit câmp cheie sau zonă cheie. Acest câmp are aceeaşi lungime şi aceeaşi poziŃie relativă în toate articolele. Pentru un fişier de organizare indexată pot fi definite mai multe câmpuri cheie, dar dintre acestea unul este obligatoriu şi se numeşte cheie primară, iar celelalte se numesc chei secundare. Fiecare fişier indexat conŃine pe lângă informaŃia propriu-zisă şi o tabelă de index. O tabelă de index conŃine valorile câmpului cheie împreună cu adresele la care sunt memorate elementele cu cheia respectivă. Tabelele de indecşi sunt numerotate (0..256 dBase). Tabela de index cu numărul 0 se numeşte tabelă de index primară şi este asociată cheii primare. În fişierul care conŃine informaŃiile despre muncitorii unei societăŃi comerciale, cu articole de forma: marca nume şi prenume salariu putem alege drept câmp cheie câmpul marca.


45

Pentru a avea acces la un element al unui fişier de organizare indexată, se va explora secvenŃial tabela de indexi determinând indexul ce conŃine articolul cu cheia căutată. Acel index conŃine pe lângă valoarea cheii şi adresa la care se găseşte memorat elementul cu cheia căutată, după care accesul va fi direct, în fişierul indexat la articolul căutat, prin adresa determinată. Fişier muncitori Tabela de index asociata câmpului marca marca N.P. salariu 001 Ionescu P. . . . a1 001 t1

010 Popescu G. . . . a2 010 t2

020 . . . . . . a3 020 t3

030 . . . . . . , , , Pentru a avea acces la articolul cu cheia 20 va fi explorată secvenŃial tabela de index şi se găseşte că t3 conŃine cheia 20, cu precizarea că acest articol este memorat la adresa a3. Accesul la o înregistrare dintr-un fişier indexat presupune deci următoarele operaŃii: 1. accesul la index; 2. căutarea în index a adresei înregistrării; 3. accesul la înregistrarea căutată. Indexul poate conŃine toate cheile înregistrărilor din fişier sau doar o parte din ele. În a doua situaŃie atât înregistrările fişierului cât şi indexul sunt sortate după aceleaşi criterii. Fişierul este împărŃit în grupe de dimensiune fixă, fiecare grupă având o intrare în index care conŃine cheia cea mai mică, respectiv cea mai mare a înregistrărilor din grupă. Exemplu: FIŞIER


46

T10 S1

00001

00020 00021

.

.

.

00024 T23 S1 02110 T10 S2

00029 01131

00105 01136 00111 01151 00113 T23 S2 02200 02201

02204

. . . 02207

T10 S9

00191

00203 00204

. . .

00205 T23 S9 03001 T11 S1

00206 03002

00210 03003 00211 00230

T11 S2

00250

00251 00252 00253

. . .

T11 S9

00299

00300 00303 00305


47

Tabela de index este de fapt un fişier de chei şi se poate crea un index al său obŃinând astfel un index ierarhizat. Index sector Index pistă 00001 00024 S1 00001 00205 T10

00029 00113 S2 00206 00305 T11

T10

.

.

. 00191 00205 S9 00206 00230 S1 00250 00253 S2

T11 02110 03003 T23

.

.

. 00299 00305 S9

.

.

. 02110 02151 S1 02200 02207 S2 T23

03001 03003 S9

Exemplu de index (pistă) ierarhizat. Dacă se solicită accesul la înregistrarea cu cheia 303 se caută în indexul de pistă şi se găseşte pista 11 (T11). Se merge apoi la indexul de sector şi se găseşte sectorul 9 (T11, S9) şi apoi se merge la fişier şi se găseşte înregistrarea. Parcurgerea indecşilor se face secvenŃial. Fişierele indexate cuprind o zonă primară în care sunt depuse înregistrările iniŃiale (cele de la crearea fişierului), o zonă de depăşire (secundară) în care sunt depuse înregistrările adăugate ulterior şi o a treia zonă, indexul sau indecşii.


48

Organizarea indexat secvenŃială permite atât accesul secvenŃial cât şi direct şi nu apar probleme de sinonimie ca la organizarea aleatoare, dar pentru a obŃine o înregistrare sunt necesare două sau mai multe operaŃii de citire în funcŃie de numărul indecşilor.

� Opera Ńii asupra fi şierelor

1. Creare - transferul informaŃiilor din memoria centrală pe suport. 2. Consultare - informaŃia e citită de pe suport şi transferată în

memoria centrală. memoria centrală citire scriere zonă tampon suport 3. Actualizare: - adăugare de noi articole în fişier - modificare: pentru aceasta articolul se transferă în memoria centrală, se face modificarea dorită şi se copiază din nou pe suport în formă modificată, în locul de unde a fost citit . - ştergere. În primul rând, orice fişier trebuie să fie deschis (să-l identificăm pe suport şi să avem acces la zona de date, să realizăm legătura logică între numele fişierului de pe suport şi numele sub care fişierul va fi identificat în cadrul programului) pentru a putea fi prelucrat. De asemenea, la terminarea prelucrării unui fişier, acesta trebuie închis. Se impune închiderea fişierului după terminatrea


49

prelucrării, pentru că numărul fişierelor ce pot fi deschise simultan este limitat. Această limită este dependentă de sistemul de operare. OperaŃiile de deschidere şi închidere de fişiere, precum şi operaŃiile indicate mai sus pot fi realizate printr-un set de funcŃii aflate în biblioteca standard I/O a limbajului utilizat.

•••• Tipuri recursive de date Prin structură recursivă se înŃelege o structură care are în componenŃa sa cel puŃin o componentă de acelaşi tip cu structura însăşi. Un exemplu de structură recursivă este arborele genealogic al unei persoane, adică structura care precizeaza toate rudele directe ascendente ale unei persoane. Tipul acestei structuri poate fi definit ca o structură cu trei componente, prima reprezentând numele persoanei, celelalte două fiind arborii genealogici ai părinŃilor. Aceasta s-ar exprima în următoarea formă : struct genealogie { char nume[20]; genealogie tata, mama; }; DefiniŃia de mai sus nu este corectă în C deoarece se utilizează indicatorul genealogie înainte de a fi complet definit. Structurile recursive pot fi implementate în limbajul C numai în forma unor structuri dinamice. Astfel, prin definiŃie, orice componentă care are tipul identic cu structura completă se înlocuieşte cu un pointer care indică acea componentă. Structura genealogie se va implementa astfel : struct genealogie { char nume[20]; struct genealogie *tata, *mama; };


50

Se constată uşor că structurile recursive introduc structuri infinite. În realitate arborii genealogici nu sunt infiniŃi. AbsenŃa unei componente recursive se va indica asignând pointerul referitor la această componentă cu NULL. Ex: PETRU ŞTEFAN NULL MARIA NULL ADAM NULL NULL SIMONA NULL NULL Un alt exemplu de structură recursivă este cel al expresiilor aritmetice: struct expresie { char operator; struct expresie *operand1,*operand2; }; Dacă în câmpul operator va fi unul din caracterele +, -, *, /, atunci celelalte două câmpuri conŃin câte un pointer la o expresie, iar dacă în câmpul operator se găseşte o literă, atunci celelalte două câmpuri vor conŃine NULL.


51

Exemplu: (x∗(y-z))/u ⁄ ∗ u NULL NULL x NULL NULL - Y NULL NULL z NULL NULL


52

2 Structura de date de tip list ă Din punct de vedere matematic, o listă este o secvenŃă de zero sau mai multe elemente numite noduri, de un anumit tip numit tip de bază. Dacă n≥1, lista se prezintă de regulă astfel : a1, a2, ... , an, şi fiecare ai aparŃine tipului de bază. Numărul n al nodurilor se numeşte lungimea listei. Presupunând n≥1 se spune că a1 este primul nod al listei iar an este ultimul nod. Dacă n=0 avem de-a face cu o listă vidă. O proprietate importantă a unei liste este aceea că nodurile sale pot fi ordonate liniar în funcŃie de poziŃia lor în cadrul listei. Se spune că ai precede pe ai+1 pentru i=1,2, ... ,n-1 şi că ai succede pe ai -1 pentru i = 2,3, ... ,n. De regulă se spune că nodul ai se află pe poziŃia i. Aşadar o listă liniară este o colecŃie de n ≥ 0 noduri ale căror proprietăŃi structurale se reduc în principal la poziŃiile relative liniare (unidimensionale) ale acestor noduri. OperaŃiile pe care dorim să le efectuăm asupra listelor liniare pot include, de exemplu, următoarele : 1) Accesul la nodul al i-lea din listă pentru a examina şi/sau modifica conŃinutul câmpurilor sale. 2) Inserarea unui nod nou înaintea nodului al i-lea. 3) Ştergerea nodului al i-lea. 4) Combinarea a două sau mai multe liste într-o singură listă. 5) DespărŃirea unei liste liniare în două sau mai multe liste. 6) Copierea unei liste liniare. 7) Determinarea numărului de noduri dintr-o listă liniară. 8) Sortarea nodurilor unei liste liniare într-o ordine crescătoare a conŃinutului anumitor câmpuri ale nodurilor. 9) Căutarea în listă a nodului cu o valoare particulară a unui anumit câmp.


53

O aplicaŃie pe calculator rareori apelează la toate cele nouă operaŃii de mai sus în întreaga lor generalitate, astfel încât vom constata că există mai multe căi de a reprezenta liste liniare, în funcŃie de clasele de operaŃii care se vor efectua cel mai frecvent. Pare a fi imposibilă elaborarea unei metode unice de reprezentare pentru listele liniare în care toate aceste operaŃii să fie eficiente; de exemplu, asigurarea posibilităŃii de a realiza acces la nodul i al unei liste lungi pentru un i oarecare este relativ greu de realizat dacă în acelaşi timp trebuie inserate şi şterse informaŃii în mijlocul listei. De aceea vom face distincŃie între tipurile de liste liniare în funcŃie de principalele operaŃii de efectuat. Listele liniare în care inserările, ştergerile şi accesul la valori au loc aproape totdeauna la primul sau la ultimul nod sunt foarte frecvent întâlnite, purtând denumiri speciale şi anume : O stivă (stack) este o listă liniară pentru care toate inserările şi ştergerile (şi de obicei orice acces) sunt făcute la unul din capetele listei (fig. 2.1) care se numeşte vârful sau începutul listei. O coadă (queue) este o listă liniară pentru care toate inserările sunt făcute la unul din capetele listei; toate ştergerile (şi de obicei orice acces) sunt făcute la celălalt capăt. O coadă completă (dequeue) sau coadă cu duble capete, este o listă liniară pentru care inserările şi ştergerile (şi de obicei orice acces) sunt făcute la ambele capete ale listei. Rezultă că o coadă completă este mult mai generală ca o stivă sau o coadă. Mai distingem cozi complete cu restricŃii la ieşire sau la intrare.


54

Fig. 2.1 : O stivă reprezentată ca o ramificaŃie de cale ferată Această linie este blocată în cazul cozii complete cu restricŃie la intrare ieşirea din coadă intrarea în coadă intrarea în coadă ieşirea din coadă Această linie este blocată în cazul cozii complete cu restricŃie la ieşire Fig. 2.2 : O coadă completă reprezentată ca o reŃea de cale ferată În cazul unei stive manipulăm întotdeauna “cea mai tânără” informaŃie din listă, de exemplu cea care a fost inserată cel mai recent. În cazul unei cozi este chiar invers: întotdeauna “cea mai veche “ informaŃie este cea manipulată; nodurile părăsesc lista în aceeaşi ordine în care au intrat. Multe persoane şi-au dat seama independent de importanŃa stivelor şi cozilor, au dat alte denumiri acestor structuri. Stivele au fost denumite “liste de deplasare în jos” (push-down list), “memorii reverse” (reversion storages), “vraf” (pile), liste tip “ultimul-sosit-primul-ieşit” (LIFO - Last-In-First-Out). Cozile sunt denumite uneori memorii circulare sau liste “primul-sosit-primul-ieşit” (FIFO - First-In-First-Out). Pentru cozile complete cu restricŃie pentru ieşire a fost folosit şi termenul de “etajeră” (shel) iar cozile complete cu restricŃie pentru intrări erau denumite “sul” (scrolls) sau “rulou” (rolls). Această


55

multiplicitate de denumiri este interesantă în sine căci dovedeşte importanŃa respectivelor concepte. Termenii de coadă, coadă completă, stivă au început să devină termeni consacraŃi. În algoritmii care se referă la aceste structuri se utilizează în general o terminologie specială. Se pune sau se extrage un element în/din vârful (începutul) stivei (vezi fig. 2.3 a). Sfârşitul (sau baza) unei stive este ultimul accesibil şi nu va putea fi extras decât după ce toate celelalte elemente au fost extrase. În cazul cozilor vom vorbi despre faŃa şi spatele cozii; elementele se adaugă la spate şi părăsesc coada prin faŃă (fig.2.3 b). ştergere inserare

vârf (început) FaŃă Al 2-lea Al 3-lea Spate

b)Coadă Cel mai Al 2-lea cel mai din din stânga din dreapta dreapta

sfârşit inserare Al 2-lea inserare

(bază) ştergere din stânga ştergere

a)stivă c)coadă completă Fig. 2.3 Liste liniare speciale Când ne referim la cozi complete, vom vorbi de capătul din stânga şi din dreapta (fig. 2.3 c). Termenii de început, sfârşit, faŃă şi spate sunt uneori folosiŃi şi în cazul cozilor complete utilizate ca stive sau cozi, fără o convenŃie specială dacă începutul, faŃa şi spatele sunt în capătul din stânga sau din dreapta.


56

2.1 Tehnici de implementare a listelor De regulă pentru structurile de date fundamentale există construcŃii de limbaj ce le reprezintă, construcŃii care îşi găsesc un anumit corespondent în particularităŃile hardware ale sistemelor care le implementează. Pentru structurile de date avansate însă, care se caracterizează printr-un nivel mai înalt de abstracŃie, acest lucru nu mai este valabil. De regulă reprezentarea acestor structuri se realizează cu ajutorul structurilor de date fundamentale, observaŃie valabilă şi pentru structurile de tip listă.

2.1.1 Implementarea listelor cu ajutorul tipului tablou

În cazul implementării listelor cu ajutorul tipului tablou, o listă se asimilează cu un tablou, nodurile listei fiind memorate într-o zonă contiguă de memorie, în locaŃii succesive. În implementarea cu ajutorul tipului tablou, tipul lista se defineşte ca o structură cu două câmpuri. Primul câmp este un tablou cu elemente de tip nod, a cărui lungime este astfel aleasă de către programator încât să fie suficientă pentru a putea păstra cea mai mare dimensiune de listă ce poate să apară în respectiva aplicaŃie. Cel de-al doilea câmp va fi un întreg ultim care indică în tablou poziŃia ultimului nod al listei . Dacă considerăm elementele listei de tip întreg, structura de tip lista va fi definită astfel:

#define lungime_max 10 typedef int nod; typedef struct { nod elemente[lungime_max];


57

int ultim; } lista; Primul nod Al doilea nod ultim lista Ultimul nod Gol Fig. 2.4 Reprezentarea listei cu ajutorul tipului tablou În această reprezentare,o listă poate fi uşor traversată, iar noile noduri pot fi adăugate în mod simplu la sfârşitul listei. InserŃia unui nod în mijlocul listei presupune însă deplasarea tuturor nodurilor următoare cu o poziŃie spre sfârşitul listei pentru a face loc noului nod. În mod similar, suprimarea oricărui nod cu excepŃia ultimului presupune de asemenea deplasarea celorlalte în vederea eliminării spaŃiului creat. ObservaŃie: Dacă se încearcă inserŃia unui nod într-o listă care deja a utilizat în întregime tabloul asociat se semnalează eroare (depăşire), iar dacă în cadrul procesului de căutare nu se găseşte elementul căutat se va semnala acest lucru.


58

2.1.2 Implementarea listelor folosind alocarea înl ănŃuită În loc să păstrăm o listă liniară în locaŃii succesive de memorie se poate folosi o schemă mult mai flexibilă, în care fiecare nod este legat de următorul nod al listei prin câmpul urm(ător) al listei, unde info urm p el1 el2 eln NULL Fig. 2.5 Listă liniară simplu înlănŃuită p este o variabilă pointer care indică primul nod.

Există posibilitatea de a folosi o variabilă de tip nod, în care câmpul urm(ător) indică primul nod efectiv al listei, iar celelalte câmpuri, care ar conŃine informaŃia propriu-zisă, ar rămâne neasignate. Pointerul p va indica in această situaŃie, acest nod fictiv cap de listă. Utilizarea acestui nod de început simplifică în anumite situaŃii prelucrarea listelor înlănŃuite. Noi vom utiliza, în cele ce urmează, pointerul de început p.

Considerând cheia de tip întreg şi informaŃia - şir de cel mult 10 caractere, vom putea defini lista ca o structură (recursivă) de tipul: struct nod { int cheie;


59

char info[10]; struct nod *urm; }; typedef struct nod Tnod ; Definim şi tipul ref ca fiind tipul pointer la nodurile listei: typedef Tnod *ref; ref p; /* retine adresa primului nod al listei */

•••• Tehnici de inser Ńie a nodurilor şi de creare a listelor înl ănŃuite

Vom nota cu p variabila pointer care indică primul nod al listei, iar q o variabilă pointer auxiliară (tot de tipul ref) . Pentru a avea o listă înlănŃuită se creează mai întâi primul nod al listei prin funcŃia : p 4 1 2 2 3 q info cheie urm

void ins_p(void) /* insereaza primul nod al listei */ { q=(ref)malloc(sizeof(Tnod)); /* 1 */ printf("Introduceti cheia: "); scanf("%d",&q->cheie); /* 2 */ printf("Introduceti informatia: "); fflush(stdin); scanf("%s",q->info); /* 2 */ q->urm=NULL; /* 3 */ p=q; /* 4 */


60

} /* ins_p */

Inserarea unui nod în listă (altul decât primul, care asigură existenŃa listei) se poate face în faŃa listei (la începutul listei) sau la sfârşitul listei liniare (în spatele listei).

Inserarea în faŃa listei se poate realiza prin : p p 4 3 1 2 q Fig. 2.6 Inserare în faŃa listei

void ins_cf(void) /* insereaza un nod in fata listei */ { q=(ref)malloc(sizeof(Tnod)); /* 1 */ printf("Introduceti cheia: "); scanf("%d",&q->cheie); /* 2 */ printf("Introduceti informatia: "); fflush(stdin); scanf("%s",q->info); /* 2 */ q->urm=p; /* 3 */ p=q; /* 4 */ } /* ins_cf */ Datorită faptului că inserŃia noului nod are loc de fiecare dată la începutul listei, prin funcŃia ins_cf se creează lista în ordinea inversă a introducerii cheilor. Dacă se doreşte crearea listei în ordinea naturală, atunci este nevoie de o funcŃie care inserează un nod la sfârşitul listei.

Inserarea la sfârşitul listei. Acestă funcŃie se redactează mai simplu dacă se cunoaşte locaŃia ultimului nod al listei. Teoretic lucrul acesta nu prezintă nici o dificultate deoarece se poate


61

parcurge lista de la începutul ei indicat prin p , până la detectarea nodului care are câmpul urm = NULL . În practică această soluŃie nu este convenabilă deoarece parcurgerea întregii liste este ineficientă. Se preferă să se lucreze cu o variabilă pointer ajutătoare q care indică mereu ultimul nod al listei, după cum p indică primul nod al listei : p q 5 r 1 4 NULL 2 3 Fig. 2.7 Inserarea la sfârşitul listei

void ins_cs(void) /* insereaza un nod in spatele listei */ { r=(ref)malloc(sizeof(Tnod)); /* 1 */ printf("Introduceti cheia: "); scanf("%d",&r->cheie); /* 2 */ printf("Introduceti informatia: "); fflush(stdin); scanf("%s",r->info); /* 2 */ r->urm=NULL; /* 3 */ q->urm=r; /* 4 */ q=r; /* 5 */ } /* ins_cs */

•••• Traversarea unei liste înl ănŃuite Prin traversarea unei liste se înŃelege executarea unei anumite operaŃii asupra tuturor nodurilor listei. Fie p pointerul care indică primul nod al listei şi fie r o variabilă pointer auxiliară (de tipul ref). Atunci funcŃia care realizează listarea elementelor listei va fi următoarea:


62

void listare(void) { r=p; while (r!=NULL) { printf("Cheia: %-10d | Informatia: %10s\n",r->cheie,r->info); r=r->urm; } } /* listare */

O operaŃie care apare frecvent în practică este căutarea, adică depistarea unui nod care are cheia egală cu o valoare dată k : void cautare(void) { r=p; while ((r->cheie!=k)&&(r!=NULL)) r=r->urm; } /* cautare */

Dacă căutarea se termină fără a găsi elementul de cheie k, deci se termină căci s-a ajuns la sfârşitul listei, r = NULL. Atunci *r nu există (şi deci r->cheie nu are sens). În consecinŃă, în funcŃie de implementare, se semnalează sau nu eroare. Următoarea variantă a operaŃiei de căutare este corectă în toate cazurile, în ea utilizându-se o variabilă booleană ajutătoare notată cu b : void cautare(void) { int b=0; r=p; while((!b)&&(r!=NULL)) { if(r->cheie==k) b=1;


63

else r=r->urm; } } /* cautare */ După execuŃia funcŃiei, dacă nodul a fost găsit variabila pointer r va conŃine adresa nodului căutat, în caz contrar r = NULL.

•••• Inser Ńia unui nod într-un loc oarecare al listei

După un nod anume Fie r un pointer care indică un nod oarecare al listei şi s o variabilă pointer auxiliară (tot de tipul ref). În aceste condiŃii inserŃia unui nod după nodul de adresă memorată în r se realizează astfel : p 4 3 r 1 s 2 Fig. 2.8 InserŃia unui nod după nodul *r void ins_d(void) { s=(ref)malloc(sizeof(Tnod)); /* 1 */ printf("Introduceti cheia:"); scanf("%d",&s->cheie); /* 2 */ printf("Introduceti informatia:"); fflush(stdin); scanf("%s",s->info); /* 2 */ s->urm=r->urm; /* 3 */


64

r->urm=s; /* 4 */ } /* ins_d */

Înaintea unui anumit nod

Dacă se doreşte însă inserŃia noului nod în lista liniară înaintea unui nod indicat *r, apare o complicaŃie generată de imposibilitatea practică de a afla simplu adresa predecesorului nodului *r. (După cum s-a precizat deja, în practică nu se admite parcurgerea de la început a listei pentru aflarea adresei nodului respectiv). Această problemă se poate rezolva simplu cu ajutorul următoarei tehnici : se inserează un nod după *r, se asignează acest nod cu nodul *r, după care se creează câmpurile cheie şi info pentru nod şi se asignează cu ele câmpurile corespunzătoare ale vechiului nod *r, Fig.2.9. p r NULL 4 3 info 2 2 s 1 Fig.2.9 InserŃia unui nod înaintea nodului *r FuncŃia C care descrie această tehnică de inserare, va fi: void ins_i(void) { s=(ref)malloc(sizeof(Tnod)); /* 1 */ *s=*r; /* 2 */ r->urm=s; /* 3 */


65

printf("Introduceti cheia:"); scanf("%d",&r->cheie); /* 4 */ printf("Introduceti informatia:"); fflush(stdin); scanf("%s",r->info); /* 4 */ }

•••• Tehnici de suprimare a nodurilor Se consideră următoarea problemă: se dă un pointer r care indică un nod al listei liniare înlănŃuite şi se cere să se suprime succesorul nodului *r. Aceasta se poate realiza modificând câmpul urm al nodului *r: s=r->urm; r->urm=s->urm; p NULL r Fig. 2.10 Suprimarea unui nod *r cu s o variabilă pointer auxiliară (de tipul ref). Dacă în prelucrările ulterioare nu mai avem nevoie de succesor (nodul *s), locatia acestuia poate fi pusă la dispoziŃia sistemului, în C, prin free(s). (Pentru a nu distruge iremediabil structurile de date create este necesar ca programatorul să studieze cu atenŃie modul în care funcŃia free(s) este implementată de compilatorul pe care îl are la dispoziŃie).

Când se pune problema suprimării unui nod situat după un nod specificat, trebuie tratată separat situaŃia când nodul specificat este ultimul nod al listei, căci în acest caz nu avem ce suprima.

FuncŃia C care realizează suprimarea unui nod situat după un nod specificat, de adresă r, oricare ar fi acesta, va fi:

void suprima_d(void) /*suprima nodul urmator celui specificat prin r/


66

{ if (r->urm==NULL) printf("Eroare: nodul de suprimat nu exista.\n"); else { s=r->urm; r->urm=s->urm; free(s); printf("Suprimarea s-a realizat cu succes.\n"); } } /* suprima_d */ Dacă se doreşte suprimarea chiar a nodului *r, cum este dificil să cunoaştem adresa predecesorului său (pentru a realiza legătura cu succesorul ), vom utiliza următoarea tehnică: se aduce succesorul în locul lui *r, apoi se suprimă vechiul succesor. Aceasta se poate realiza prin secvenŃa : s=r->urm; *r=*s; free(s);

Această secvenŃă este corectă doar dacă nodul de suprimat nu este ultimul nod al listei. În cazul în care nodul care trebuie suprimat este ultimul nod al listei, nu are sens *s şi cazul acesta trebuie tratat separat. Pentru optimizare se analizează separat situaŃia în care nodul de suprimat este şi ultimul şi primul. FuncŃia C care descrie suprimarea unui nod oarecare al listei liniare simplu înnlănŃuită, desemnat de variabila pointer r, va fi:

void suprima_n(void) /*suprima nodul specificat prin r */ { if (r->urm==NULL) /* se testeaza daca *r este ultimul nod al listei */


67

if (r==p) /*este ultimul nod si primul */ { p=NULL; free(r); } else /*este ultimul nod dar nu si primul */ { s=p; /* presupunem s variabila globala */ while (s->urm!=r) s=s->urm; s->urm=NULL; free(r); } else /* este un nod diferit de ultimul */ { s=r->urm; *r=*s; free(s); } } /* suprima_n */

•••• Aplica Ńii ale listelor înl ănŃuite. Problema concordan Ńei.

Fiind dat un text format dintr-o succesiune de cuvinte, se balează textul şi se depistează cuvintele. Pentru fiecare cuvânt se verifică dacă este sau nu la prima apariŃie. În caz afirmativ se înregistrează, în caz negativ se incrementează un contor asociat cuvântului care înregistrează numărul de apariŃii. În final se dispune de toate cuvintele distincte din text şi de numărul de apariŃii. Această problemă este importantă deoarece reflectă într-o formă simplificată una din activităŃile realizate de un compilator.


68

Se va construi o listă înlănŃuită conŃinând cuvintele distincte ale textului. Procesul de căutare în listă, împreună cu inserŃia la începutul listei sau incrementarea contorului, este realizat în funcŃia cauta. Pentru simplificare, ”textul” se presupune a fi de fapt o succesiune de numere întregi pozitive, reprezentând “cuvintele”. Acestea se citesc de la tastatură până la introducerea unui “cuvânt” fictiv, în cazul de faŃă zero, care precizează sfârşitul textului.

•••• Crearea unei liste ordonate În acest paragraf se abordează problema creării listei astfel încât ea să fie mereu ordonată după chei crescătoare. Cu alte cuvinte, odată cu crearea listei, aceasta se şi sortează. Acest lucru se realizează destul de simplu, deoarece înainte de inserŃia unui nod acesta trebuie oricum căutat în listă. Dacă lista este sortată, atunci căutarea se va termina cu prima cheie mai mare decât cea căutată, apoi în continuare se inserează nodul în poziŃia ce precede această cheie. Obs: 1. În cazul unei liste nesortate căutarea înseamnă parcurgerea întregii liste, după care nodul se inserează la început sau la sfârşit. Procedeul descris mai sus, pe lângă faptul că permite obŃinerea unei liste sortate, face să devină mai eficient procesul de căutare. 2. La crearea unor structuri de tablou sau de fişier nu există posibilitatea simplă de a le obŃine gata sortate. În schimb la listele liniare sortate nu există echivalentul unor metode de căutare avansate (căutare binară).

Tehnica celor doi pointeri În continuare vom descrie o altă tehnică de inserŃie într-o listă sortată, bazată pe utilizarea a doi pointeri de memorie q1 şi q2 care indică tot timpul două noduri consecutive ale listei, combinată cu


69

metoda fanionului pentru determinarea poziŃiei de inserat. ”Metoda fanionului” constă în prelungirea listei cu un nod suplimentar numit “fanion”, a cărui cheie se asignează cu valoarea căutată x (care în cel mai rău caz va fi găsită în procesul de căutare pe ultima poziŃie în listă). Cei doi pointeri avansează simultan de-a lungul listei, q2 după q1, până când q1->cheie>=x, lucru ce se va întâmpla cu certitudine cel mai târziu în momentul în care q1 devine egal cu adresa fanionului (fanion). Dacă în acest moment cheia lui *q1 este mai mare decât x, sau q1=fanion, atunci trebuie inserat un nou nod în listă între *q1 şi *q2 (În caz contrar, pentru problema concordanŃei, trebuie incrementat q1->contor cu 1). În realizarea acestui proces se va Ńine cont de faptul că funcŃionarea sa corectă presupune existenŃa în listă a cel puŃin a două noduri, deci cel puŃin un nod în afară de nodul fanion. Din acest motiv lista se va iniŃializa cu două noduri fictive, dintre care unul este fanionul. Problema concordanŃei, folosind această tehnică, va conduce la următoarele modificări: 1. În secŃiunea de declarare a variabilelor, se adaugă declaraŃia ref fanion, în poziŃia /* 1. */ 2. InstrucŃiunea p=NULL indicată prin /* 2. */se va înlocui cu următoarea secvenŃă: p=(ref)malloc(sizeof(Tnod)); fanion=(ref)malloc(sizeof(Tnod)); p->urm=fanion; fanion->urm=NULL;

FuncŃia cauta va fi următoarea:

void cauta(int x,ref *p) { ref q1,q2; q2=*p; q1=q2->urm;


70

fanion->cheie=x; while(q1->cheie<x) { q2=q1; q1=q2->urm; } if((q1->cheie==x)&&(q1!=fanion)) q1->contor++; else { r=(ref)malloc(sizeof(Tnod)); r->cheie=x; r->contor=1; r->urm=q1; q2->urm=r; } } /* caută */

Aceste modificări conduc la crearea listei sortate. Beneficiul obŃinut de pe urma sortării se manifestă doar în cazul unui nod care nu se găseşte în listă. Această operaŃie necesită în medie parcurgerea unei jumătăŃi de listă în cazul listelor sortate, în comparaŃie cu parcurgerea întregii liste dacă aceasta nu este sortată.

Având în vedere că primul nod este un nod fictiv şi ultimul nod este fanionul, funcŃia de listare se va modifica astfel: void listare(void) { if(p->urm==fanion) printf("Lista vida !\n"); else { clrscr();


71

printf("\n\n Cuv. distincte din text si nr. lor de aparitii:\n\n\n"); r=p->urm; while (r!=fanion) { printf("Cuvant = %3d numar aparitii %2d\n", r->cheie,r->contor); r=r->urm; } } printf("\n\nTastati enter\n"); getche(); } /* listare */

•••• Structuri de date derivate din structura de tip list ă.

Liste dublu înlănŃuite Unele aplicaŃii necesită traversarea listelor şi înainte şi înapoi. Cu alte cuvinte, fiind dat un element oarecare al listei trebuie determinat cu rapiditate atât succesorul, cât şi predecesorul său. Maniera cea mai rapidă de a realiza acest lucru este de a memora în fiecare nod al listei referinŃele “înainte” şi “înapoi”, lucru care conduce la structura de listă dublu înlănŃuită. p NULL NULL


72

Fig. 2.11 Listă dublu înlănŃuită În Limbajul C, o astfel de structură de date se descrie (presupunând cheia de tip întreg, iar informaŃia şir de cel mult 10 caractere), astfel: typedef struct nod { char info[10]; int cheie; struct nod *urm,*ant; }Tnod; typedef Tnod *ref; ref p; /* primul element al listei */ Pentru exemplificare se prezintă funcŃia de suprimare a elementului situat în poziŃia r a unei liste dublu înlănŃuite. Pentru început se localizează nodul precedent al nodului *r şi se face câmpul următor al acestuia să indice nodul care urmează celui indicat de r (1). În continuare se modifică câmpul anterior al nodului care urmează celui indicat de r, astfel încât să indice nodul precedent celui indicat de r ( 2 ). 1 r 2 Fig. 2.12 Suprimarea unui nod dintr-o listă dublu înlănŃuită Presupunem că nodul de suprimat nu este nici primul nici ultimul nod în listă. Atunci funcŃia de suprimare, în C, se va descrie astfel :


73

void sterg_nod(void) { ref pred,suc; pred=r->ant; suc=r->urm; if (r->urm!=NULL) suc->ant=pred; if (r->ant!=NULL) pred->urm=suc; } Nodul suprimat este indicat în continuare de r. SpaŃiul de memorie care a fost alocat nodului *r, ar putea fi reutilizat în regim de alocare dinamică a memoriei. Dacă în prelucrările ulterioare nu mai avem nevoie de nodul *r, spaŃiul care a fost alocat nodului *r poate fi pus la dispoziŃia sistemului, în limbajul C, prin free(r). Când nodul de suprimat este primul nod al listei (r=p), trebuie modificat şi pointerul p care conŃine adresa acestuia, astfel încât să indice succesorul lui ( cel care va deveni primul nod al listei, după suprimare) şi de aceea funcŃia trebuie să fie completată cu rezolvarea şi a acestui caz: void sterg_nod(void) { ref pred,suc; pred=r->ant; suc=r->urm; if (r->urm!=NULL) suc->ant=pred; if (r->ant!=NULL) pred->urm=suc; if (r==p) /* daca nodul de suprimat este primul nod */ p=p->urm; free(r); } O listă dublu înlănŃuită permite inserarea uşoară a unui nod fie la dreapta fie la stânga unui nod dat r. Inserarea dup ă nodul *r


74

p NULL NULL 4 5 3 6 r 1 s 2 Fig. 2.14 Inserarea după nodul *r void insd_d(void) { ref s,suc; s=(ref)malloc(sizeof(Tnod)); /* 1 */ printf("Introduceti informatia:");fflush(stdin);scanf("%s",s->info);/*2 */ printf("Introduceti cheia: "); scanf("%d",&s->cheie); /* 2 */ suc=r->urm; s->urm=suc; /* 3 */ s->ant=r; /* 4 */ r->urm=s; /* 5 */ if (suc!=NULL) suc->ant=s; /* 6 */ } Inserarea înaintea nodului *r p NULL NULL 6 5


75

4 3 r s 1 2 Fig. 2.15 Inserare înaintea lui *r void insd_i(void) { ref s,pred; pred=r->ant; s=(ref)malloc(sizeof(Tnod)); /* 1 */ printf("Introduceti informatia:");fflush(stdin);scanf("%s",s->info); /*2*/ printf("Introduceti cheia: "); scanf("%d",&s->cheie); /* 2 */ s->urm=r; /* 3 */ s->ant=pred; /* 4 */ r->ant=s; /* 5 */ if (pred!=NULL) pred->urm=s; /* 6 */ else p=s; } Celelalte operaŃii de bază se efectuează ca şi în cazul în care am considera lista ca o listă simplu înlănŃuită după câmpul urm. Dăm mai jos programul care descrie toate operaŃiile de bază asupra unei liste liniare dublu înlănŃuită, verificând pentru fiecare operaŃie dacă s-a efectuat sau nu corect: În practica programării este frecventă tehnica care face din nodul de început al unei liste dublu înlănŃuite un nod fictiv care practic “închide cercul”. Astfel, câmpul “anterior” al acestui nod indică ultimul nod al listei, iar câmpul “urmator” al ultimului nod al listei indică acest nod fictiv. În acest caz nu mai este necesar să


76

testăm dacă nodul de suprimat are succesor şi predecesor, după cum se va vedea în programul "Implementarea listelor liniare dublu inlantuite circulare, cu element cap de lista", care va fi prezentat în continuare. O astfel de listă în care ultimul nod al listei se înlănŃuie cu primul (şi primul nod cu ultimul în cazul alocării dublu înlănŃuite) se numeşte listă circulară. p Fig. 2.13 Listă circulară dublu înlănŃuită

2.2 STIVE O stivă este un tip special de listă în care toate inserările, suprimările şi orice alt acces se execută la un singur capăt, care se numeşte vârful stivei. Stivele se mai numesc liste de tipul LIFO (Last In First Out) , adică “ultimul element introdus primul suprimat” sau liste de tipul “push-down”. Deoarece stiva este o listă liniară cu caracter special toate implementările discutate până acum sunt valabile şi pentru stive.

2.2.1 Implementarea stivelor bazat ă pe tipul tablou Implementarea stivelor bazată pe tipul tablou nu este cea mai indicată deoarece operaŃia de inserare şi stergere necesită mutarea


77

întregii liste în jos, respectiv în sus, această activitate consumând un timp proporŃional cu numărul de elemente ale stivei. O utilizare mai eficientă a tipului tablou Ńine cont de faptul că inserŃiile şi suprimările se fac numai în vârf. Astfel se poate considera drept bază a stivei sfârşitul tabloului (indexul său cel mai mare), stiva crescând în sensul descreşterii indexului în tablou. Un cursor numit vîrf indică poziŃia curentă a primului element al stivei. 0 gol vîrf primul element al doilea element lungime_max -1 ultimul element Fig. 2.16 Implementarea stivelor prin tipul tablou Structura de date abstractă care se defineşte pentru această implementare va fi următoarea : #define lungime_max 10 typedef int tipelem; typedef struct { int varf; tipelem elemente[lungime_max]; } Stiva; Stiva este vidă când virf = lungime_max. Opera Ńiile tipice asupra stivelor:


78

1. Initializare(&s) care face stiva s vidă: void initializare(Stiva *s) { (*s).varf=lungime_max; } /* intitializare */ 2. Func Ńia stivid(s) returnează valoarea adevărat dacă stiva s este vidă şi fals în caz contrar. int stivid(Stiva s) { if (s.varf>=lungime_max) return 1; else return 0; } /* stivid */ 3. Func Ńia virfst(s) furnizează elementul din vârful stivei s, dacă stiva nu este vidă. int virfst(Stiva s) { if (stivid(s)) { er=1; printf("Stiva este vida.\n"); return 0; /* aici fc. trebuie sa intoarca o valoare diferita de cea a elementelor stivei*/ } else return s.elemente[s.varf]; } /* virfst */


79

4. Pop(&s,&x) suprim ă elementul din vârful stivei s, dacă stiva nu este vidă, după ce în prealabil l-am salvat în variabila x: void pop(Stiva *s,tipelem *x) { if (stivid(*s)) { er=1; printf("Stiva este vida.\n"); } else { (*x)=(*s).elemente[(*s).varf]; (*s).varf=(*s).varf+1; } } /* pop */ 5. Push (x,&s) insereaz ă elementul x în vârful stivei s, dacă stiva nu este plină. void push(tipelem x,Stiva *s) { if ((*s).varf==0) { er=1; printf("Stiva este plina.\n"); } else { (*s).varf=(*s).varf-1; (*s).elemente[(*s).varf]=x; } } /* push */


80

2.3 COZI Cozile sunt o altă categorie specială de liste în care elementele sunt inserate la un capăt (spate) şi sunt suprimate la celălalt capăt (faŃă). Cozile se mai numesc liste de tipul “FIFO” (First-In-First-Out) adică liste de tipul “primul-venit-primul-servit”. OperaŃiile care se execută aupra cozii sunt analoage cu cele asupra stivei, cu diferenŃa că inserŃiile se fac la spatele cozii şi nu la începutul ei şi că ele diferă ca terminologie.

2.3.1 Implementarea cozilor cu ajutorul tipului pointer Ca şi în cazul stivelor, orice implementare a listelor este valabilă şi pentru cozi. Pornind de la observaŃia că inserŃiile se fac numai în spatele cozii, funcŃia de adăugare poate fi concepută mai eficient astfel: în loc de a parcurge de fiecare dată lista de la început la sfârşit atunci când se doreşte inserarea unui element, se va păstra un pointer la ultimul element. De asemenea, ca şi la toate tipurile de liste, se va păstra şi pointerul la primul element al listei utilizat în toate funcŃiile de suprimare şi în cea care furnizează primul element al cozii. În implementare se poate utiliza şi un nod fictiv ca prim element al cozii, caz în care pointerul de început va indica acest nod. Această convenŃie, care permite o manipulare mai convenabilă a cozilor vide, va fi utilizată în continuare în implementarea bazată pe pointeri a structurii de tip coadă. Tipurile de date care se utilizează în acest scop sunt următoarele (presupunem elementele cozii de tip întreg): typedef int tipelement; typedef struct nod { tipelement element;


81

struct nod *urm; } Tnod;

În aceste condiŃii se poate defini o sructură de tip coadă care constă din doi pointeri indicând faŃa respectiv spatele unei liste înlănŃuite. Primul nod al cozii este unul fictiv în care câmpul element este ignorat. Această convenŃie, după cum s-a menŃionat înainte, permite o reprezentare şi o manipulare mai simplă a cozii vide. Astfel se defineşte tipul coadă după cum urmează: typedef struct { Tnod *fata,*spate; } Coada;

SecvenŃele de program care implementează cele cinci operaŃii tipice asupra unei cozi sunt următoarele: 1. Initializare(&c) face coada c vidă. c.fată NULL c.spate Fig. 2.17 IniŃializarea unei cozi

void initializare(Coada* c) { c->fata=(ref)malloc(sizeof(Tnod)); /* creeaza nodul fictiv; */ c->fata->urm=0; c->spate=c->fata; /* nodul fictiv este primul si ultimul nod; */ } /* initializare */ 2. Func Ńia cvid(c) returnează valoarea adevărat dacă coada c este vidă şi fals în caz contrar.


82

int cvid(Coada c) { if (c.fata==c.spate) return 1; else return 0; } /* cvid */

3. Func Ńia primul(c) returnează primul element al cozii c.

tipelement primul(Coada c) { if (cvid(c)) { er=1; printf("Eroare: coada este vida.\n"); return 0; } else return c.fata->urm->element; } /* primul */ 4. Func Ńia adauga(x,&c) inserează elementul x în spatele cozii.

Presupunem că înainte de adăugare coada este : c.fata NULL

c.spate Inserarea în spatele cozii se va realiza astfel: 1 3 c.fata x NULL c.spate 2 Fig. 2.18 Adăugarea unui nod la o coadă void adauga(tipelement x, Coada *c) { c->spate->urm=(ref)malloc(sizeof(Tnod)); /* 1 */ c->spate=c->spate->urm; /* 2 */


83

c->spate->element=x; /* 3 */ c->spate->urm=NULL; /* 3 */ } /* adauga */ 5. Func Ńia sterge(&c) suprimă primul element al cozii c, dacă

coada nu este vidă: Coada înainte de suprimare c.fata NULL c.spate Coada după suprimare c.fata NULL c.spate Fig. 2.19 Suprimarea unui nod din coadă. Elementul care trebuie şters propriu-zis devine el element fictiv: void sterge(Coada *c) { ref r; if (cvid(*c)) { er=1; printf("Eroare: coada este vida.\n"); } else { r=c->fata; c->fata=c->fata->urm; free(r); } } /* sterge */


84

2.3.2 Implementarea cozilor cu ajutorul tablourilor circulare

Reprezentarea listelor cu ajutorul tablourilor poate fi utilizată şi pentru cozi, dar nu este foarte eficientă. Pointerul la ultimul element al listei, permite implementarea simplă, într-un număr finit de paşi a operaŃiei adauga. ExecuŃia operaŃiei sterge presupune însă mutarea întregii cozi cu o poziŃie în tablou. Pentru a depăşi acest dezavantaj putem folosi o structură de tablou circular (listă circulară) în care se pot aranja n=lung_max noduri, x[0] ... x[n-1] implicit într-un cerc, în care x[0] urmează după x[n-1]. . . . 2 n-4 n-3 1 n-2 0 n-1 Fig. 2.20 Coada circulară Vom defini astfel structura de date Coada: #define Lung_max 10 typedef int tipel; typedef struct { tipel elemente[Lung_max]; int fata,spate; } Coada;


85

Elementele cozii se găsesc în poziŃii consecutive, spatele cozii fiind undeva înaintea feŃei la parcurgerea cercului în sensul acelor de ceasornic. Inserarea unui element în coadă presupune mişcarea cursorului c.spate cu o poziŃie în sensul acelor de ceasornic şi introducerea elementului în această poziŃie, iar ştergerea presupune simpla mutare a cursorului c.fata cu o poziŃie în sensul rotirii acelor de ceasornic. Exemplu: Se consideră o coadă cu 4 elemente . . . c.fata = 0 c.spate = 3 e3 3 2 n-1 e2 1 0 e1 e0 Dacă se adaugă un element e4 , obŃinem: c.fata = 0 . . c.spate = 4 e4 . 4 e3 3 2 n-1 e2 1 0 Fig. 2.21 Adăugarea unui element într-o coadă circulară e1 e0

Dacă acum se extrage primul element din coadă atunci : c.fata =1 . c.spate =4


86

. 4 e4 3 e3 e2 2 e1 e0 n-1 1 0 Fig. 2.22 Ştergerea unui element dintr-o coadă circulară Acest mod de implementare ridică însă o problemă referitoare la sesizarea cozii vide şi a celei pline. Presupunând că avem o coadă plină, adică o coadă care conŃine un număr de elemente egal cu Lung_max, cursorul c.spate va indica poziŃia adiacentă lui c.fata în sensul acelor de ceasornic. . . . coada plină e1

en-2

e0 en-1 c.fata 0 n-1 c.spate


87

3 e c.fata 2 2 1 n-1 c.spate 1 n-1 0 0 c.fata c.spate coada înainte de a deveni vidă Coada vidă: după ştergerea ultimului element Fig. 2.23 Diferitele stări ale unei cozi şi sesizarea acestora Pentru a preciza reprezentarea cozii vide se presupune o coadă formată dintr-un singur element. În această situaŃie c.spate şi c.fata indică aceeaşi poziŃie. Dacă se extrage un element, c.fata avansează cu o poziŃie (în sensul acelor de ceasornic) indicând coada vidă, fig. 2.23. Se observă însă că această situaŃie este identică celei anterioare care indică coada plină (c.spate cu o poziŃie în urmă, în sens trigonometric faŃă de c.fata). Astfel, în vederea testării cozii pline, în tablou se vor introduce doar Lung_max-1 elemente deşi în tablou există Lung_max poziŃii. Astfel testul de coadă plină conduce la o valoare adevărată dacă c.spate devine egal cu c.fata după două înaintări succesive, iar testul de coadă vidă conduce la o valoare adevărată, dacă c.spate devine egal cu c.fata după înaintarea cu o poziŃie în tablou. Opera Ńiile tipice asupra cozilor implementate prin tipul tablou:


88

Pentru implementarea operaŃiilor asupra cozii se are în vedere şi funcŃia avanseaza(i) care furnizează poziŃia următoare în coadă, în sens trigonometric, celei indicată de i : 1. int avanseaza (int i) { if (i== Lung_max -1) return 0; else return i+1; } /* avanseaza */

Pentru a putea face o primă inserare, deci pe poziŃia 0, cursorul pentru spate va trebui să arate în momentul inserării poziŃia 0. Evident, înaintea primei inserări în coadă, coada este vidă şi deci ca după o avansare cursorul de spate să ajungă cursorul de faŃă şi să fie pe poziŃia 0, trebuie ca c.fata=0 şi c.spate=Lung_max-1. avanseaza(c.spate)=0 c.fata 0 n-1 c.spate 2. Func Ńia ini Ńializare(&c) face coada c vidă: void initializare(Coada *c) { (*c).fata=0; (*c).spate=Lung_max-1; } /* initializare */


89

3. Func Ńia cvid(c) returnează 1 dacă coada c este vidă şi 0 în caz contrar: int cvid(Coada c) { if (avanseaza(c.spate)==c.fata) return 1; else return 0; } /* cvid */ 4. Func Ńia primul(c) returnează elementul din faŃa cozii c dacă coada nu este vidă: tipel primul(Coada c) { if (cvid(c)) { printf("Eroare: Coada este vida.\n"); er=1; return 0; } else return c.elemente[c.fata]; } /* primul */ 6. Func Ńia adauga(x,&c) adaugă elementul x în spatele cozii c,

dacă coada nu a ocupat în întregime tabloul: void adauga(tipel x,Coada *c) { if (avanseaza(avanseaza((*c).spate))==(*c).fata) { printf("Eroare: Coada este plina!\n"); er=1; }


90

else { (*c).spate=avanseaza((*c).spate); (*c).elemente[(*c).spate]=x; } }/* adauga */ 7. Func Ńia sterge(&c) şterge elementul din faŃa cozii c, dacă coada nu este vidă: void sterge(Coada *c) { if (cvid(*c)) { printf("Eroare: Coada este vida.\n"); er=1; } else { (*c).elemente[(*c).fata]=0; (*c).fata=avanseaza((*c).fata); } } /* sterge */


91

3 Structuri Arborescente Cele mai importante structuri neliniare ce intervin în algoritmii de prelucrare cu calculatorul sunt structurile arborescente. Vorbind în general, structurile arborescente presupun relaŃii de “ramificare” între noduri, asemănător configuraŃiei arborilor din natură. Defini Ńie. Prin arbore se înŃelege o mulŃime finită de n ≥ 0 elemente denumite noduri sau vârfuri, de acelaşi fel, care dacă nu este vidă atunci are: a) un nod cu destinaŃie specială, numit rădăcina arborelui ; b) celelalte noduri sunt repartizate în m ≥ 0 seturi disjuncte A1, A2,..., Am, fiecare set Ai constituind la rândul său un arbore. Există şi alte definiŃii nerecursive pentru arbori (de exemplu cea pe baza relaŃiei de preordine), dar definiŃia recursivă pare cea mai potrivită deoarece recursivitatea reprezintă o caracteristică naturală a structurilor arborescente. Elementele arborelui sunt nodurile şi legăturile dintre ele. Nodul rădăcină r îl considerăm ca fiind de nivelul zero. Întrucât A1, A2,..., Am sunt la rândul lor arbori, fie r1, r2,..., rm rădăcinile lor. Atunci r1, r2,..., rm formează nivelul unu al arborelui (fig.3.1). Nodul r va avea câte o legătură cu fiecare dintre nodurile r1, r2,..., rm. Continuând acest procedeu vom avea nivelurile 2, 3, ... ale arborelui. Deci fiii tuturor nodurilor nivelului i formează nivelul i+1. Dacă numărul nivelurilor este finit atunci şi arborele este finit. În caz contrar se numeşte arbore infinit.


92

O astfel de viziune asupra arborilor este o viziune ierarhică, nodurile fiind subordonate unele altora, fiecare nod fiind subordonat direct unui singur nod, excepŃie făcând rădăcina care nu este subordonată nici unui nod. Dacă un nod nu are nici un nod subordonat, atunci se numeşte frunză sau nod terminal. Numărul fiilor unui nod reprezintă gradul acelui nod. Un nod terminal are gradul zero. Un nod neterminal se numeşte deseori nod de ramificare sau interior. r nivelul 0 r1 r2 . . . rm nivelul 1

r r r n11

12

1... r r r p21

22

2... r r rm m mq1 2 ...

Fig. 3.1 Arbore Dacă nodul A are ca subordonaŃi directi nodurile B şi C, atunci A se numeşte tatăl, părintele lui B şi C, iar B şi C sunt fiii lui A, şi B este fratele lui C. Gradul maxim al nodurilor unui arbore se numeşte gradul arborelui. Dacă ordinea relativă a subarborilor A1, A2,..., Am în punctul b) al definiŃiei are importanŃă, arborele se numeşte arbore ordonat. Exemplu: arborii din fig. 3.2 sunt distincŃi (ca arbori ordonaŃi).


93

A A B C C B Fig. 3.2 Nivelul maxim al nodurilor unui arbore se numeşte înălŃimea arborelui. Fie arborele: nivel 0 A nivel 1 B C D nivel2 E F G H I J nivel 3 K L M N O nivel 4 P


94

Fig. 3.3 Arborele din figura 3.3 are înălŃimea 4, nodul D este de grad 2, H este terminal, F este un nod intern, iar gradul arborelui este 3. Prin subarborii unui arbore se înŃeleg arborii în care se descompune acesta prin îndepărtarea rădăcinii. A1, A2,..., Am din definiŃia b) sunt subarborii arborelui de rădăcină r. Orice nod al unui arbore este rădăcina unui arbore parŃial. Un arbore parŃial nu este însă întotdeauna subarbore pentru arborele complet, dar orice subarbore este arbore parŃial. Dacă n1, n2,..., nk este o secvenŃă de noduri aparŃinând unui arbore, astfel încât ni este părintele lui ni+1 pentru 1≤ i < k, atunci această secvenŃă se numeşte “drum” sau “cale” de la nodul n1 la nodul nk. Lungimea unui drum la un nod este un întreg având valoarea egală cu numărul de ramuri (săgeŃi) care trebuie traversate (parcurse) pentru a ajunge de la rădăcină la nodul respectiv. Rădăcina are lungimea drumului egală cu zero, fiii ei au lungimea drumului egală cu 1 şi în general un nod situat la nivelul i are lungimea drumului i. Spre exemplu, în figura 3.3, lungimea drumului la nodul D este 1, iar la nodul P este 4. Dacă există un drum de la nodul x la nodul y, atunci nodul x se numeşte strămoş al lui y, iar nodul y se numeşte descendent al lui x. Exemplu: în aceeaşi figură strămoşii lui F sunt F, B, A, iar descendenŃii săi F, K, L, M şi P. Conform celor deja precizate, tatăl unui nod este strămoşul său direct sau predecesorul acestuia, iar fiul unui nod este descendentul său direct sau succesorul acestuia. Un strămoş sau un descendent al unui nod, altul decât nodul însuşi, se numeşte strămoş propriu sau descendent propriu. Într-un arbore, rădăcina este singurul nod fără nici un strămoş propriu. Nodurile terminale nu au descendenŃi proprii.


95

ÎnălŃimea unui nod într-un arbore este lungimea celui mai lung drum de la nodul respectiv la un nod terminal. Pornind de la această definiŃie, înălŃimea unui arbore se poate defini şi ca fiind egală cu înălŃimea nodului rădăcină. Adâncimea unui nod este egală cu lungimea drumului unic de la rădăcină la acel nod. În practică se mai defineşte şi lungimea drumului unui arbore, numită şi lungimea drumului intern, ca fiind egală cu suma lungimilor drumurilor corespunzătoare tuturor nodurilor arborelui. În mod evident, lungimea medie a drumului notată cu Pi este:

Pn

n ii ii

h

= ⋅=∑

1

1

unde n = numărul de noduri ale arborelui, n i = numărul de noduri de la nivelul i şi h = nivelul maxim al arborelui. În scopul definirii lungimii drumului extern, ori de câte ori se întâlneşte în arborele iniŃial un subarbore vid, acesta se înlocuieşte cu un nod special. În structura care se obŃine după această activitate, toate nodurile originale vor fi de acelaşi grad şi anume gradul arborelui. Se precizează că nodurile speciale care au înlocuit ramurile absente nu au descendenŃi prin definiŃie. Lungimea drumului extern se defineşte ca fiind suma lungimilor drumurilor la toate nodurile speciale. Dacă numărul nodurilor speciale la nivelul i este si, atunci lungimea medie a drumului extern PE este:

P

ms iE i

i

h

= ⋅=

+

∑1

1

1

unde m=numărul de noduri speciale, h=înălŃimea arborelui. Spre exemplu, arborele din figura 3.4, extins cu noduri speciale reprezentate prin pătrate, ia forma din figura 3.5.


96

A B C D E F G H I J K L M N O P Fig. 3.4 A B C D E F G H


97

I J K L M N O P Fig. 3.5 Numărul de noduri speciale care se adaugă într-un arbore de grad α depinde în mod direct de numărul n de noduri originale, astfel: a) Fiecare nod are exact o săgeată care intră în el; deci există m+n-1 săgeŃi; b) Pe de altă parte din fiecare nod original ies α săgeŃi. Dar numărul de săgeŃi în cazurile a) şi b) este acelaşi ⇒ m+n-1=αn ⇒ m=n(α-1)+1. Nici o săgeată nu iese dintr-un nod special. Numărul maxim de noduri într-un arbore de o înălŃime dată h şi grad αααα, este atins dacă toate nodurile au α subarbori cu excepŃia celor de la nivelul h care nu au niciunul. Pentru arborele de grad α, nivelul 0 va conŃine rădăcina, nivelul 1 va conŃine cei α descendenŃi direcŃi ai săi, nivelul 2 va conŃine cei α 2 descendenŃi direcŃi ai acestora, etc., ceea ce ne conduce la formula:

∑=

=h

i

ihN0

)( αα

N h h2

12 1( ) = −+ De o importanŃă particulară sunt arborii ordonaŃi de gradul 2. Ei se numesc arbori binari. Exemple familiare de arbori sunt: 1) Arborii genealogici, cu cele 2 tipuri obişnuite: a) Genealogia cu tatăl şi mama unei persoane ca descendenŃi; b) DescendenŃa care îi indică pe urmaşi. (Dacă apar şi căsătorii intrafamiliale arborele familial nu mai este de fapt un arbore, deoarece ramuri diferite ale arborelui nu pot fi legate între


98

ele(conform definiŃiei), dar pentru a reprezenta arborescenŃa, acestea se dublează.) 2) O expresie aritmetică cu operatori binari, fiecare operator denotând un nod de ramificare, cu cei doi operanzi ca subarbori. * + - a / d * b c e f Fig. 3.6 Arborele binar corespunzător expresiei aritmetice (a+b/c)*(d-e*f) Terminologia standard pentru structurile arborescente este preluată din arborele de descendenŃă: fiecare rădăcină este tatăl rădăcinilor din subarborii săi, iar aceştia din urmă se numesc fraŃi şi sunt fiii tatălui lor. Rădăcina întregului arbore nu are tată.

3.1 Reprezentarea grafic ă a structurilor arborescente Structurile arborescente pot fi reprezentate grafic în mai multe moduri, fără a avea vreo asemănare cu arborii reali: A


99

B C H I D E F G Fig. 3.7 1) Prin seturi incluse în seturi, adică o colecŃie de seturi în care orice pereche de seturi este fie disjunctă, fie unul conŃine pe celălalt. Arborele din fig 3.7, după metoda (1) se va reprezenta astfel: C H I D F B E G A sau 2) Prin paranteze incluse , care indică şi ordonarea parŃială: ( A ( B ( H ) ( I ) ) ( C ( D ) ( E ( G ) ) ( F ) ) ) pentru arborele din fig. 3.7.

3) Folosind “indentaŃia”. Arborele din fig. 3.7 se va reprezenta prin indentare după cum urmează: A B


100

H I C D E G F 4) NotaŃia zecimală DEWEY, prin analogie cu schema de clasificare zecimală cu acelaşi nume utilizată în biblioteci. NotaŃia zecimală Dewey pentru arborele din figura 3.7 este (dacă α este numărul unui nod oarecare de grad m, atunci fiii săi sunt numerotaŃi: α.1; α.2; ...; α.m): 1A; 1.1B; 1.1.1H; 1.1.2I; 1.2C; 1.2.1D; 1.2.2E; 1.2.2.1G; 1.2.3F; Există o legătură strânsă între notaŃia zecimală Dewey şi notaŃia folosită pentru variabilele indexate. Dacă A este un arbore, putem nota cu A[1] primul subarbore, A[1][2]≡A[1,2], al doilea subarbore al primului subarbore, A[1,2,1] primul subarbore al acestuia din urmă, etc.

3.2 Traversarea arborilor Una din activităŃile fundamentale care se execută asupra unei structuri de arbore este traversarea acestuia. Ca şi în cazul listelor liniare, prin traversarea unui arbore se înŃelege execuŃia unei anumite operaŃii asupra tuturor nodurilor arborelui. În timpul traversării nodurile sunt vizitate într-o anumită ordine, astfel încât ele pot fi considerate ca şi cum ar fi integrate într-o listă liniară. De fapt descrierea celor mai mulŃi algoritmi este mult uşurată dacă în cursul prelucrării se poate preciza elementul următor al structurii de arbore, respectiv se poate liniariza structura de arbore.


101

Există trei moduri de ordonare (liniarizare) mai importante care se referă la o structură de arbore, numite “preordine”, “inordine” şi “postordine”. Toate trei se definesc recursiv, asemenea structurii de arbore. Ordonarea unui arbore se defineşte presupunând că subarborii săi s-au ordonat deja. Cum subarborii au noduri strict mai puŃine decât arborele complet, rezultă că, aplicând recursiv de un număr suficient de ori definiŃia, se ajunge la ordonarea unui arbore vid, care este evidentă. Cele trei moduri de traversare se definesc recursiv după cum urmează: • Dacă arborele A este vid, atunci ordonarea lui A în preordine, inordine, postordine se reduce la lista vidă; • Dacă A se reduce la un singur nod, atunci nodul însuşi reprezintă traversarea lui A, în oricare din cele trei moduri; • Pentru restul cazurilor fie arborele A cu rădăcina R şi cu subarborii A1 , A2 ,..., Ak. R A1 A2 . . . Ak

Fig.3.8 1° Traversarea în preordine a arborelui A presupune traversarea rădăcinii R urmată de traversarea în preordine a lui A1 , apoi de traversarea în preordine a lui A2 şi aşa mai departe, până la Ak inclusiv. 2° Traversarea în inordine presupune parcurgerea în inordine a subarborelui A1 , urmată de nodul R şi în continuare de parcurgerile în inordine ale subarborilor A2,...,Ak. 3° Traversarea în postordine a arborelui A constă în traversarea în postordine a lui A1 , A2 ,..., Ak şi în final a nodului R. Spre exemplu, pentru arborele din fig.3.9 traversările definite anterior conduc la următoarele secvenŃe de noduri:


102

1 2 3 4 5 6 7 8 9 10 Fig.3.9 - preordine: 1 , 2 , 3 , 5 , 8 , 9 , 6 , 10 , 4 , 7 - postordine: 2 , 8 , 9 , 5 , 10 , 6 , 3 , 7 , 4 , 1 - inordine: 2 , 1 , 8 , 5 , 9 , 3 , 10 , 6 , 7 , 4 O metodă simplă, practică de parcurgere a unui arbore este următoarea: având o structură de arbore se imaginează parcurgerea acestuia în sens trigonometric pozitiv, rămânând cât mai aproape posibil de arbore (fig. 3.10). Pentru preordine nodurile se listează prima dată când sunt întâlnite :1 , 2 , 3 , 5 , 8 , 9 , 6 , 10 , 4 , 7 ; pentru postordine ultima dată când sunt întâlnite, respectiv când sensul de parcurgere este spre părinŃii lor: 2 , 8 , 9 , 5 , 10 , 6 , 3 , 7 , 4 , 1 ; pentru inordine se listează un nod terminal la prima trecere prin el, un nod interior la a doua trecere: 2 , 1 , 8 , 5 , 9 , 3 , 10 , 6 , 7 , 4. Traversând arborele din fig. 3.11 şi înregistrând caracterul corespunzător ori de câte ori vizităm o rădăcină se obŃin următoarele ordonări: 1


103

2 3 4 5 6 7 8 9 10 Fig.3.10 1° Preordine : * + a / b c - d * e f 2° Inordine : a + b / c * d - e * f 3° Postordine : a b c / + d e f * - * Ordonarea în postordine este cunoscută sub denumirea de “notaŃie poloneză” (postfix). * + - a / d * b c e f Fig. 3.11 - Structura de arbore binar a unei expresii aritmetice Prin scrierea unei expresii aritmetice în notaŃie poloneză se înŃelege scrierea operatorului după cei doi operanzi, în loc de a-l scrie între ei, ca în notaŃia algebrică obişnuită (infix). Astfel spre exemplu:


104

a + b devine a b + a * b + c devine a b * c + a * (b + c) devine a b c + * a - b / c devine a b c / - (a - b) / c devine a b - c / Este uşor de observat că forma poloneză a unei expresii reprezentată printr-un arbore binar se obŃine parcurgând arborele în postordine. În mod similar, în matematică se defineşte “notaŃia poloneză inversă” (prefix) în care operatorul se scrie în faŃa celor doi operanzi. De exemplu expresia a + b se scrie + a b. Se observă că notaŃia prefix corespunde traversării în preordine a arborelui expresiei. O proprietate interesantă a notaŃiei poloneze este aceea că în ambele forme ea păstrează semnificaŃia expresiei aritmetice fără a utiliza paranteze. Cu privire la ordonarea în inordine, se observă că ea corespunde notaŃiei obişnuite a expresiei aritmetice dar cu omiterea parantezelor, motiv pentru care semnificaŃia matematică a expresiei se pierde, cu toate că arborele binar corespunzător păstrează această semnificaŃie (vezi fig.3.11).

3.3 Reprezentarea structurilor arborescente Pentru reprezentarea pe suport a structurilor arborescente se foloseşte alocarea înlănŃuită. Reprezentarea cu referinŃe descendente = reprezentarea prin pointeri multipli: a) Fiecare nod conŃine, pe lângă informaŃia propriu-zisă, n+1 câmpuri l0 , l1 ,..., ln unde n = gradul nodului; l0 - conŃine gradul nodului (n);


105

li , 1≤ i ≤n - conŃin adresele succesorilor imediaŃi ai nodului. Fie arborele: 1 2 3 4 5 6 7 8 Fig 3.12 Acest arbore se reprezintă în memorie (cu metoda descrisă mai sus) astfel: l0 l1 l2 l3

1 3 2 2 3 1 4 1 5 0 6 0 7 0 8 0 Fig. 3.13 b) În anumite situaŃii însă, fiecărui nod i se asociază n+1 câmpuri, l0, l1,..., ln unde n este de această dată gradul arborelui, li cu 0≤ i ≤n au aceeaşi semnificaŃie ca la punctul a). Dacă unul din subarborii unui nod lipseşte, deci dacă subarborele respectiv este vid, pointerul corespunzător va conŃine


106

referinŃa nulă (NULL, în figură ∧). În acest caz, reprezentarea arborelui din figura 3.12 va fi următoarea: 1 3 2 3 ∧ 3 3 ∧ ∧ 4 3 ∧ ∧ 5 3 ∧ ∧ ∧ 6 3 ∧ ∧ ∧ 7 3 ∧ ∧ ∧ 8 3 ∧ ∧ ∧ Fig.3.14 Datorită faptului că în fiecare nod trebuie să rezervăm loc pentru numărul maxim de referinŃe către fii (care poate să nu fie cunoscut dinainte) risipa de memorie este uneori prea mare. Există evident şi posibilităŃi de înlăturare a acestor neajunsuri, de exemplu păstrând lista referinŃelor către fiii unui nod nu într-un vector (ce corespunde alocării semistatice la nivel de nod), ci într-o listă înlănŃuită (alocare dinamică). Definim nodurile ca variabile cu o structură fixă. În Limbajul C structura se descrie în modul următor (presupunem că informaŃia ataşată nodurilor este de tip întreg şi coincide cu cheia de identificare a nodului): typedef struct nod { int cheie; int nrfii; struct nod *reffii[max]; } Tnod; typedef Tnod *ref; ref radacina;

l0 l1 l2 l3


107

unde max este o constantă care reprezintă gradul arborelui. În cazul arborilor binari, întrucât gradul arborelui se subînŃelege a fi 2 se vor reprezenta pentru fiecare nod, pe lângă informaŃia propriu-zisă, numai referinŃele la cei doi subarbori: st=referinŃa la subarborele stâng, respectiv dr=referinŃa la subarborele drept.

În Limbajul C, structura unui arbore binar, cu cheile nodurilor numere întregi (când cheile coincid cu informaŃiile nodurilor), se va descrie astfel: typedef struct nod { int cheie; struct nod *st,*dr; } Tnod; typedef Tnod *ref; ref radacina; În continuare, cele trei metode de traversare ale arborilor binari vor fi concretizate în trei funcŃii recursive, în care r este o variabilă de tip pointer (ref) care indică rădăcina arborelui, iar P reprezintă operaŃia care trebuie executată asupra fiecărui nod (de exemplu, operaŃia de tipărire). Considerăm structura de arbore definită mai sus.

void Preordine(ref r) { if (r!=NULL) { P(r); Preordine(r->st); Preordine(r->dr); }/* Preordine */ }


108

void Inordine(ref r) { if (r!=NULL) { Inordine(r->dr); P(r); Inordine(r->st); }/* inordine */ } void Postordine(ref r) { if (r!=NULL) { Postordine(r->st); Postordine(r->dr); P(r); }/* Postordine */ }

3.4 Construc Ńia şi reprezentarea grafic ă a unui arbore binar de în ălŃime minim ă Se presupune că arborele care trebuie construit conŃine noduri de tipul definit mai sus, în care cheile nodurilor sunt n numere care se citesc din fişierul de intrare. RestricŃia care se impune este aceea ca arborele construit să aibă înălŃime minimă. Pentru aceasta este necesar ca fiecărui nivel al structurii să-i fie alocate numărul maxim de noduri cu excepŃia nivelului de bază. Acest lucru poate fi realizat prin distribuirea în mod egal a nodurilor care se introduc pe stânga şi pe dreapta fiecărui nod deja introdus. Grafic această tehnică se prezintă pentru numărul de noduri n=1,..,6 după cum urmează:


109

n=1 n=2 n=3 n=4 n=5 n=6 Fig.3.15 Regula după care se asigură distribuŃia egală pentru un anumit număr cunoscut de N noduri, poate fi formulată simplu în termeni recursivi: 1° Se ia un nod drept rădăcină; 2° Se generează subarborele stâng cu NS=N/2 noduri; 3° Se generează subarborele drept cu ND=N -NS -1 noduri. Aceşti arbori se numesc arbori perfect (total) echilibraŃi. Un arbore este perfect echilibrat dacă are toate vârfurile terminale pe ultimele două niveluri, astfel încât pentru orice nod, numărul nodurilor din subarborele stâng să difere de numărul nodurilor din subarborele drept cu cel mult unu. Considerând variabilele: ref radacina; int N ; construim pentru introducerea (generarea) arborelui funcŃia Arbore(N) care generează un arbore perfect echilibrat cu N noduri: ref Arbore(int N) { ref nodnou; int ND,NS;


110

if (N==0) return NULL; else { NS=N/2; /* nr. de noduri din subarborele stang */ ND=N-NS-1; /* nr. de noduri din subarborele drept */ nodnou=malloc(sizeof(Tnod)); printf("noul nod:"); scanf("%d",&nodnou->info); nodnou->st=Arbore(NS); nodnou->dr=Arbore(ND); } return nodnou; } /* arbore */

3.5 Vizualizarea arborelui binar Se pot găsi diverse modalităŃi de tipărire a arborelui, modalităŃi ce vor fi alese în funcŃie de aplicaŃie şi eventual de modul de reprezentare în memorie. Dacă dorim o reprezentare cât mai fidelă, ca formă, a structurii arborescente, deci o reprezentare grafică a arborelui, vizualizarea devine relativ complicată (Vezi aplicaŃiile din paragraful 5.3). De regulă se preferă tipărirea cu indentare. Fie de exemplu arborele din fig.3.16: 1 2 3 4 5 6 7


111

8 9 10 11 12 13 14 15 Fig.3.16 Tipărindu-l cu indentare îl vom obŃine, în funcŃie de modul de traversare, sub una din următoarele trei forme(fig.3.17 a,b,c): 1 8 8 2 4 9 4 9 4 8 2 10 9 10 11 5 5 5 10 11 2 11 1 12 3 12 13 6 6 6 12 13 14 13 3 15 7 14 7 14 7 3 15 15 1 a) Preordine b) Inordine c) Postordine Fig.3.17 Rotind cu 90° în sensul acelor ceasornicului imaginea din figura 3.17b, se obŃine reprezentarea grafică a simetricului arborelui binar (total echilibrat). Indentarea se face în funcŃie de nivelul nodului. În acest sens (pentru tipărirea unui nod de un anumit nivel) vom folosi un ciclu: for(i=1;i<=nivel;i++) printf(" ");


112

pentru tipărirea a 2*nivel spaŃii, urmate apoi de tipărirea nodului prin: printf("%d\n",anod->info); unde anod precizează adresa nodului respectiv. FuncŃia de tipărire a unui nod de un anumit nivel va fi: void Tip(ref anod,int nivel) { int i; for(i=1;i<=nivel;i++) printf(" "); printf("%d\n",anod->info); } Întrucât fiii unui nod de un anumit nivel sunt de nivelul nivel+1 procedurile de traversare se vor descrie astfel: void Preordine(ref rad,int nivel) { if (rad!=NULL) { Tip(rad,nivel); Preordine(rad->st,nivel+1); Preordine(rad->dr,nivel+1); } } /* Preordine */ void Inordine(ref rad,int nivel) { if (rad!=NULL) { Inordine(rad->st,nivel+1); Tip(rad,nivel); Inordine(rad->dr,nivel+1);


113

} } /* Inordine */ void Postordine(ref rad,int nivel) { if (rad!=NULL) { Postordine(rad->st,nivel+1); Postordine(rad->dr,nivel+1); Tip(rad,nivel); } }/* Postordine */

3.6 Arbori binari ordona Ńi Structura de arbore poate fi utilizată pentru a reprezenta în mod convenabil o mulŃime de elemente în care elementele se regăsesc după o cheie unică. Se presupune că avem o mulŃime de n elemente definite ca structuri, având câte o cheie care este un număr întreg. Dacă cele n elemente se organizează într-o structură de listă liniară, căutarea unei chei necesită în medie n/2 comparaŃii. După cum se va vedea în continuare, organizarea celor n elemente într-o structură convenabilă de arbore binar reduce numărul de

comparaŃii la maximum log2 n . Acest lucru devine posibil utilizând structura de arbore binar ordonat. Prin arbore binar ordonat (sau arbore de căutare) se înŃelege un arbore binar care are proprietatea că, parcurgând nodurile în inordine, secvenŃa cheilor este monoton crescătoare. Un arbore binar ordonat se bucură de următoarea proprietate: dacă N este un nod oarecare al arborelui, având cheia C, atunci toate nodurile din


114

subarborele stâng al lui N au cheile mai mici decât C şi toate nodurile din subarborele drept al lui N au cheile mai mari sau egale cu C. De aici rezultă un procedeu foarte simplu de căutare: începând cu rădăcina, se trece la fiul stâng sau la fiul drept, după cum cheia căutată este mai mică sau mai mare decât cea a nodului curent. Numărul comparărilor de chei efectuate în acest procedeu este cel mult egal cu înălŃimea arborelui. În general înălŃimea unui arbore nu este determinată de numărul nodurilor sale. Spre exemplu cu 9 noduri se poate construi atât arborele ordonat a) de înălŃime 3 cât şi arborele ordonat b) de înălŃime 5 din fig.3.18. 5 7 3 8 2 8 2 4 7 9 1 6 9 1 6 3 5 4 a) înălŃime 3 b) înălŃime 5 Fig.3.18 Arbori binari ordonaŃi Este simplu de observat că un arbore are înălŃime minimă dacă fiecare nivel conŃine numărul maxim de noduri, cu excepŃia


115

posibilă a ultimului nivel. Deoarece numărul maxim de noduri al nivelului i este 2i , rezultă că înălŃimea minimă a unui arbore binar cu n noduri este hmin= [log 2n]. Prin aceasta s-a justificat afirmaŃia că o

căutare într-un arbore binar ordonat necesită aproximativ log2 n comparaŃii de chei. ObservaŃie: Această afirmaŃie este valabilă în ipoteza că nodurile s-au organizat într-un arbore ordonat de înălŃime minimă. Dacă această condiŃie nu este satisfăcută eficienŃa procesului de căutare poate fi mult redusă, în cazul cel mai defavorabil arborele degenerând într-o structură de listă liniară. Aceasta se întâmplă când subarborele drept (stâng) al tuturor nodurilor este vid, caz în care înălŃimea arborelui devine n-1, iar căutarea nu este mai eficientă decât într-o listă liniară.

3.6.1 Tehnici de c ăutare într-un arbore binar ordonat Fie t un pointer care indică rădăcina unui arbore binar ordonat ale cărui noduri au structura:

typedef struct nod { int cheie; struct nod *st,*dr; } Tnod; typedef Tnod *ref;

Fie x un număr întreg dat. Atunci functia Loc(x,t) execută căutarea în arbore, a nodului care are cheia egală cu x, conform principiului descris în paragraful anterior. Această funcŃie ia valoarea NULL dacă nu gaseşte nici un nod cu cheia x, altfel valoarea ei este egală cu adresa nodului cu cheia x.


116

ref Loc(int x,ref t) { int gasit=0; while ((gasit==0)&&(t!=NULL)) if (x== t->cheie) gasit=1; else if (x<t->cheie) t=t->st; else t=t->dr; return t; } Tehnica de căutare se poate simplifica dacă se aplică metoda fanionului. În cazul arborilor, această metodă presupune completarea structurii cu un nod fictiv, fanionul, indicat de un pointer notat cu fanion , astfel că toate ramurile arborelui se termină cu acest nod, deci toate referinŃele egale cu NULL le vom înlocui cu fanion . Arborele din fig. 3.18 a) se va reprezenta ca în fig.3.19. Înainte de demararea procesului de căutare propriu-zisă se asignează cheia fanionului cu x. În procesul căutării, nodul cu cheia x se găseşte acum cu certitudine; dacă acest nod va fi fanionul, atunci în arborele iniŃial nu există un nod cu cheia x, în caz contrar nodul găsit este cel căutat. În prezenŃa unei astfel de structuri funcŃia Loc se modifică devenind Loc1, în care se simplifică condiŃia din instrucŃiunea while: Presupunând ca arborele are structura definită mai sus şi că este creat, folosind tehnica fanionului, cu variabila fanion variabilă globală, funcŃia Loc1(x,t) va fi ref Loc1(int x,ref t) { fanion->cheie=x; while (t->cheie!=x)


117

if (x<t->cheie) t=t->st; else t=t->dr; return t; }

Deci dacă Loc1(x,t) ia valoarea fanion, atunci nu există nici un nod cu cheia x, în caz contrar, valoarea funcŃiei este chiar adresa nodului căutat. t 5 3 8 2 4 7 9 1 6


118

fanion Fig.3. 19 Căutare în arbore cu metoda fanionului

3.6.2 Căutare binar ă Dacă structura în care se efectuează o operaŃie de căutare este statică (nu trebuie să se adauge sau să se elimine noi elemente) atunci arborele de căutare se poate reprezenta eficient cu ajutorul unui tablou A cu n elemente (n este numărul nodurilor din arbore). Rădăcina este elementul cu indicele rad=[(n+1)/2], subarborele stâng este format din elementele tabloului cu indice mai mic ca rad, iar cel drept cu indicele mai mare ca rad. Rădăcina subarborelui drept, respectiv a celui stâng se determină în acelaşi mod. Se observă că tabloul va trebui să conŃină de fapt elementele arborelui de căutare în inordine, adică elementele tabloului vor trebui să fie ordonate strict crescător. De asemenea se observă că arborele obŃinut este total echilibrat. Algoritmul de căutare se poate descrie în felul următor: 1) se iniŃializează st←0 şi dr←n-1; 2) dacă st > dr avem căutare fără succes (algoritmul se termină); 3) altfel st ≤ dr (arborele nu e vid) şi se calculează rad = [(st+dr)/2] (se determină rădăcina arborelui) şi se compară cheia x cu A[rad]; dacă A[rad]=x avem căutare cu succes (algoritmul se termină); 4) dacă x > A[rad] se calculează st←rad+1 (se trece la subarborele drept) şi algoritmul se reia de la pasul 2; 5) altfel x < A[rad] şi se calculează dr←rad-1 (se trece la subarborele stâng şi algoritmul se reia de la pasul 2).


119

3.6.3 Tehnici de creare a arborilor binari ordona Ńi În cadrul acestui paragraf se va trata problema construcŃiei unui arbore binar ordonat, pornind de la o mulŃime dată de noduri. Procesul de creare constă în inserŃia câte unui nod într-un arbore binar ordonat care iniŃial este vid. Problema care se pune este aceea de a executa inserŃia de o asemenea manieră încât arborele să rămână ordonat şi după adăugarea noului nod. Aceasta se realizează traversând arborele începând cu rădăcina şi selectând fiul stâng sau drept după cum cheia de inserat este mai mică sau mai mare decât cea a nodului parcurs. Aceasta se repetă pâna când se ajunge la un pointer NULL. În continuare inserŃia se realizează modificând acest pointer astfel încât să indice noul nod. Se precizează că inserŃia noului nod poate fi realizată chiar dacă arborele conŃine deja un nod cu cheia egală cu cea nouă. În acest caz dacă se ajunge la un nod cu cheia egală cu cea de inserat, se procedează ca şi cum aceasta din urmă ar fi mai mare, deci se trece la fiul drept al nodului. În felul acesta se obŃine o metodă de sortare stabilă. Considerăm arborele din fig.3. 20 a). În figura 3.20 b) se prezintă inserŃia unui nou nod cu cheia 8 în structura existentă de arbore ordonat. 5 3 8 2 4 7 9


120

1 6 Fig.3.20 a) 5 3 8 2 4 7 9 1 6 8

Fig. 3.20 b) Inserarea unui nou nod cu cheia 8.

La parcurgerea în inordine a acestui arbore se observă că cele două noduri de chei egale sunt parcurse în ordinea în care au fost inserate. Dacă x este un număr întreg care reprezintă cheia nodului de inserat şi t un pointer care indică rădăcina arborelui, atunci funŃia inarbore(t,&t) realizează cele precizate. Considerăm structura de arbore binar: typedef struct nod { int cheie; struct nod *st,*dr; } Tnod; typedef Tnod *ref; FuncŃia care realizează inserarea unui nod nou într-un arbore binar ordonat, cu această implementare, va fi:


121

void inarbore(int x,ref *t) { if (*t==NULL) { *t=(ref)malloc(sizeof(Tnod)); (*t)->cheie=x; (*t)->st=NULL; (*t)->dr=NULL; } else if (x<(*t)->cheie) inarbore(x,&((*t)->st)); else inarbore(x,&((*t)->dr)); }/* inarbore */ Pentru tipărirea arborelui vom considera funcŃia de tipărire în inordine (simetrică) cu indentare:

void Tip(ref anod,int nivel) { int i; for(i=1;i<=nivel;i++) printf(" "); printf("%d\n",anod->cheie); } void Inordine_s(ref rad,int nivel) { if (rad!=NULL) { Inordine_s(rad->dr,nivel+1); Tip(rad,nivel); Inordine_s(rad->st,nivel+1);


122

} }/* inordine */

•••• Rezolvarea problemei concordan Ńei folosind structura de arbore binar

În cadrul acestui paragraf se va trata aşa-numita problemă a concordanŃei, care se formulează astfel: fiind dat un text format dintr-o succesiune de cuvinte, se baleează textul şi se depistează cuvintele. Pentru fiecare cuvânt se verifică dacă este sau nu la prima apariŃie. În caz afirmativ cuvântul se înregistrează, în caz negativ se incrementează un contor asociat cuvântului care înregistrează numărul de apariŃii. Această problemă este importantă deoarece ea reflectă într-o formă simplificată una din activităŃile pe care le realizează un compilator. În acest scop, nodurile reprezentând cuvintele sunt organizate într-o structură de arbore binar ordonat, pornind de la un arbore vid. Se citeşte un nou cuvânt şi se caută în arbore: dacă nu se găseşte atunci se inserează, altfel se incrementează contorul de apariŃii al cuvântului respectiv. Vom presupune că fiecare cuvânt din text are maximum 10 caractere. Textul se va citi de la tastatură, cuvânt cu cuvânt, până ce se va tasta cuvântul "*". Vom folosi următoarea structură de date: typedef struct nod { char cheie[10]; int contor; struct nod *st,*dr; } Tnod; typedef Tnod *ref;


123

Fie radacina o variabilă pointer care indică rădăcina arborelui. Atunci, în prima aproximaŃie, programul care rezolvă problema concordanŃei se redă astfel: radacina=NULL; printf("\nIntroduceti primul cuvant: "); fflush(stdin);scanf("%s",&cuv); while (strcmp(cuv,"*")!=0) { cauta(cuv,&radacina); printf("\nIntroduceti urmatorul cuvant: "); fflush(stdin);scanf("%s",&cuv); } FuncŃia cauta are rolul de a căuta cheia “cuv” în arborele iniŃializat cu pointerul radacina şi de a insera cheia în arbore dacă nu o găseşte, respectiv de a incrementa contorul corespunzător în caz contrar. După cum se observă, această funcŃie este o combinaŃie a căutării şi creerii arborilor binari ordonaŃi. Metoda de parcurgere a arborelui este cea prezentată în paragraful Tehnici de căutare într-un arbore binar ordonat. Dacă nu se găseşte nici un nod cu cheia “cuv” atunci are loc inserŃia similară celei din procedura Inarbore.

3.6.4 Tehnica suprim ării unui nod dintr-un arbore binar ordonat Se consideră o structură de arbore binar ordonat şi x o cheie precizată. Se cere să se suprime din structura de arbore nodul care are cheia egală cu cea precizată de x. Pentru aceasta, în prealabil se verifică dacă există un nod cu o astfel de cheie. Dacă nu, suprimarea s-a încheiat şi se emite eventual un mesaj de eroare. În


124

caz contrar se execută suprimarea propriu-zisă, de o asemenea manieră încât arborele să rămână ordonat şi după terminarea ei. Dacă elementul ce se şterge este un nod terminal sau un nod cu un singur descendent atunci ştergerea este directă. Dificultatea apare atunci când nodul care se şterge are doi fii, căci nu putem pointa în două direcŃii cu un singur pointer. În această situaŃie elementul care trebuie şters este înlocuit fie cu cel mai din dreapta nod al subarborelui său stâng, fie cu cel mai din stânga nod al subarborelui său drept, ambele având cel mult un fiu, după care cel din urmă se va şterge. 1) Dacă nodul care trebuie suprimat are cel mult un fiu se procedează astfel: dacă p este câmpul referinŃă din tatăl nodului x, adică referinŃa care indică nodul x, valoarea lui p se modifică astfel încât acesta să indice unicul fiu al lui x, dacă acesta există ( fig. 3.21 a), b)) sau, în caz contrar, p devine NIL (fig. 3.21 c)). p p p a) x b) x c) x P=NULL Fig.3.21 Fragmentul de program care apare în continuare realizează acest lucru: q=p; if(q->dr==NULL) p=q->st; /* nodul nu are fiu drept*/ else if(q->st==NULL) p=q->dr; /* nodul nu are fiu sting*/ else /* nodul are doi fii */

2) Cel de-al doilea caz, în care nodul cu cheia x are doi fii se rezolvă astfel:


125

p p q x y q y q y r Fig.3. 22 a) Se caută y=predecesorul b) Se suprimă y lui x în inordine - Se caută predecesorul (respectiv succesorul) nodului în ordonarea arborelui în inordine. Fie acesta nodul cu cheia y. Nodul y există şi este unic deoarece la traversarea în inordine se traversează, în cazul unui nod cu doi fii, mai întâi subarborele său stâng în inordine, deci va fi vizitat cel puŃin încă un nod; dar predecesorul în inordine este unic, deci y există şi este unic.


126

- Se modifică nodul x asignând toate câmpurile sale, cu excepŃia câmpurilor st şi dr cu câmpurile corespunzătoare ale lui y. În acest moment în structura de arbore, nodul y se găseşte în dublu exemplar: în locul său iniŃial şi în locul fostului nod x. Se suprimă nodul y iniŃial conform cazului 1) deoarece nodul nu are fiu drept. Cu privire la nodul y se poate demonstra că el se detectează după următoarea metodă: se construieşte o secvenŃă de noduri care începe cu fiul stâng al lui x, după care se alege drept succesor al fiecărui nod fiul său drept. Primul nod al secvenŃei care nu are fiu drept este y, fig.3.22 a). FuncŃia suprimare realizează suprimarea unui nod din o structură de arbore binar ordonat. FuncŃia suprimafd caută predecesorul în inordine al nodului x, realizând suprimarea acestuia conform metodei descrise. Această funcŃie se utilizează numai în situaŃia în care nodul X are doi fii: void suprimafd(ref *r) { if((*r)->dr!=NULL) suprimafd(&((*r)->dr)); else { q)->cheie=(*r)->cheie; (q)=(*r); (*r)=(q)->st; } } /* suprimafd */ void suprimare (int x, ref *p) { if((*p)==NULL) printf("Nu am ce sterge, nodul nu este in arbore!\n"); else


127

if(x<(*p)->cheie) suprimare(x,&((*p)->st)); else if(x>(*p)->cheie) suprimare(x,&((*p)->dr)); else /* suprim nodul *p */ { q=*p; if(q->dr==NULL) (*p)=q->st; else if(q->st==NULL) (*p)=q->dr; else /* nodul are doi fii */ suprimafd(&((*p)->st)); free(q); } }/* suprimare */

BIBLIOGRAFIE 1. Data Structures and Algorithms Aho, J. Hopcroft, J. Ullman Addison-Wesley, Readings Mass. 1983


128

2. *** BORLAND INTERNATIONAL TURBO C++: Programer's Guide 1990 3. Frederic Lung Le Langage C++ CNIT Paris - La Defense 1990 4. Clara Ionescu, Ioan Zsako Structuri arborescente cu aplicaŃiile lor Editura Tehnică Bucureşti 1990 5. Aaron M. Tenenbaum, Yedidyah Langsam, Moshe J. Augenstein Data Structures Usind C Prentice-Hall 1995 6. Adamson I. T. Data Structures and Algorithms: A First Course Springer-Verlag London Limited 1996

CUPRINS


129

1 NOłIUNI INTRODUCTIVE ................................................................5

1.1 NOłIUNEA DE DATĂ............................................................................5 1.2 STRUCTURI DE DATE...........................................................................6

1.2.1 Tipuri primitive standard ..........................................................10 1.2 .2 Tipuri structurate .....................................................................15

• Tipul tablou ..............................................................................15 • Tipul stuctură (struct) ...............................................................32 • Structura secvenŃă .....................................................................37 • Structura de date de tip fişier ....................................................38 • Tipuri recursive de date ............................................................49

2 STRUCTURA DE DATE DE TIP LISTA ..........................................52

2.1 TEHNICI DE IMPLEMENTARE A LISTELOR...........................................56 2.1.1 Implementarea listelor cu ajutorul tipului tablou ....................56 2.1.2 Implementarea listelor folosind alocarea înlănŃuită ...............58

• Tehnici de inserŃie a nodurilor şi de creare a listelor înlănŃuite..59 • Traversarea unei liste înlănŃuite .................................................61 • InserŃia unui nod într-un loc oarecare al listei ............................63 • Tehnici de suprimare a nodurilor ..............................................65 • AplicaŃii ale listelor înlănŃuite. Problema concordanŃei. .............67 • Crearea unei liste ordonate........................................................68 • Structuri de date derivate din structura de tip listă.....................71

2.2 STIVE .............................................................................................76 2.2.1 Implementarea stivelor bazată pe tipul tablou ..........................76

2.3 COZI ...............................................................................................80 2.3.1 Implementarea cozilor cu ajutoru tipului pointer.....................80 2.3.2 Implementarea cozilor cu ajutorul tablourilor circulare...........84

3 STRUCTURI ARBORESCENTE.......................................................91

3.1 REPREZENTAREA GRAFICĂ A STRUCTURILOR ARBORESCENTE...........98 3.2 TRAVERSAREA ARBORILOR.............................................................100 3.3 REPREZENTAREA STRUCTURILOR ARBORESCENTE..........................104 3.4 CONSTRUCłIA ŞI REPREZENTAREA GRAFICĂ A UNUI ARBORE BINAR DE ÎNĂLłIME MINIMĂ.............................................108


130

3.5 VIZUALIZAREA ARBORELUI BINAR ...................................................110 3.6 ARBORI BINARI ORDONAłI .............................................................113

3.6.1 Tehnici de căutare într-un arbore binar ordonat...................115 3.6.2 Căutare binară .......................................................................118 3.6.3 Tehnici de creare a arborilor binari ordonaŃi.........................119 3.6.4 Tehnica suprimării unui nod dintr-un arbore binar ordonat ..123

3.7 ARBORI ECHILIBRAłI AVL...........ERROR! BOOKMARK NOT DEFINED . 3.7.1 Inserarea într-un arbore AVL .....Error! Bookmark not defined. 3.7.2 Suprimarea nodurilor în arbori AVL .........Error! Bookmark not defined.

BIBLIOGRAFIE……………………………………………………… ..267

Alg-si-SD

Documents

Transcript of Alg-si-SD