UNIVERSITATEA SPIRU HARET FACULTATEA DE MATEMATIC INFORMATIC

GRIGORE ALBEANU (coordonator)

LUMINIA RPEANU, LUMINIA RADU, ALEXANDRU AVERIAN

TEHNICI DE PROGRAMARE - Lucrri practice de programarea calculatoarelor -

EDITURA FUNDAIEI ROMNIA DE MINE, BUCURETI, 2003

Descrierea CIP a Bibliotecii Naionale a Romniei

Tehnici de programare / Grigore Albeanu, Luminia Rpeanu, Luminia Radu, Alexandru Averian. - Bucureti: Editura Fundaiei Romnia de Mine, 2003

224 p., 20,5 cm Bibliogr. ISBN 973-582-665-8

I. Albeanu, Grigore II. Rpeanu, Luminia III. Radu, Luminia IV. Averian, Alexandru 004.42

Editura Fundaiei Romnia de Mine, 2003 ISBN 973-582-665-8

Coperta: Marilena BLAN

Bun de tipar: 24.01.2003; Coli tipar: 14 Format: 16/61 x 86

Editura i Tipografia Fundaiei Romnia de Mine

Splaiul Independenei, nr. 313, Bucureti, S. 6, O. P. 83 Tel.: 410 43 80; Fax. 410 51 62; www.spiruharet.ro

3

CUPRINS

Prefa ... 5

1. Operaii de intrare/ieire n limbajele Pascal i C 7 1.1. Fiiere n limbajul Pascal ... 7 1.2. Fiiere n limbajul C ...... 17

2. Structuri de date .. 31 2.1. Liste simplu nlnuite ... 32 2.2. Liste dublu nlnuite . 46 2.3. Liste circulare .... 50 2.4. Stive ... 53 2.5. Cozi .... 55 2.6. Grafuri .... 62 2.7. Arbori ..... 87

3. Metode pentru rezolvarea problemelor .... 101 3.1. Metoda Divide et Impera 101 3.2. Metoda programrii dinamice 107 3.3. Metoda Greedy 116 3.4. Metoda backtracking 125 3.5. Metoda Branch and Bound 135

4. Programare modular n Turbo Pascal ... 145

5. Introducere n programarea orientat obiect folosind limbajul C++

173

6.Teste pentru verificarea cunotinelor ... 201 6.1. Teoria i practica programrii .... 201 6.2. Probleme pentru concursuri ... 222

Bibliografie ... 224

4

Capitolele lucrrii au fost elaborate dup cum urmeaz:

Prof. univ. dr. Grigore ALBEANU Prefaa, Cap. IV, Cap. V 2, Cap VI 2, Bibliografia Prof. gr. 2 Luminia RPEANU Cap. II, Cap. III, 2, Cap. VI 1. Prof. Luminia RADU Cap. I Prep. Alexandru AVERIAN Cap III 1, 3, 4, 5, Cap. V 1.

Lectura textului integral al lucrrii, structurarea materialului, verificarea

programelor (Pascal, C, C++) i procesarea final a materialului au fost efectuate de Prof. univ. dr. Grigore Albeanu.

5

Prefa Realizarea unui software complex presupune att organizarea

intrrilor i ieirilor, ct i o foarte bun gestiune a datelor i prilor componente.

Aceast lucrare continu demersul iniiat n cadrul volumului Algoritmic i programare n limbajul Pascal, Editura Fundaiei Romnia de Mine, 2001, oferind cadrul teoretic i practic n nv-area tehnicilor de programare fundamentale. Sunt tratate modaliti de lucru cu fiiere, structuri de date complexe, metode de elaborarea algoritmilor, organizarea subprogramelor n uniti de translatare precum i conceptele de baz ale metodei de proiectare bazat pe lucrul cu obiecte.

Conceptele, tehnicile i strategiile sunt ilustrate prin exemple, att n limbajul Pascal, ct i n limbajul C. Ultima parte ilustreaz metodologia OOP (engl. Object Orieted Programming) cu ajutorul limbajului C++.

Materialul este util att elevilor i studenilor ce urmeaz specia-lizrile informatic i matematic-informatic, absolvenilor n vederea examenelor de titularizare, definitivat, ct i pregtirii complementare n cadrul nvmntului postuniversitar de informatic.

Prin colecia de exemple, probleme propuse (la nivelul fiecrui capitol) i teste de evaluare general (capitolul 5) lucrarea este util pregtirii individuale sau n cadrul cercurilor de elevi sau seminariilor studeneti, pentru participarea la concursurile de programare i la diferite examene: bacalaureat, licen, titularizare etc.

Studenii de la cursurile cu frecven redus i nvmnt la distan vor gsi exemple utile aprofundrii noiunilor transmise n cadrul cursurilor: Algoritmic i programare, Tehnici de programare, Informatic i Bazele informaticii.

Grigore ALBEANU

6

7

1. Operaii de intrare/ieire n limbajele Pascal i C 1.1. Fiiere n limbajul Pascal Definiia 1.1.1. Se numete fiier, o structur de date ale crei compo-nente, numite nregistrri, de dimensiune fix sau variabil, sunt stoca-te (depuse), de obicei, pe un suport magnetic (band sau disc) de pe care pot fi citite/scrise direct din program. Observaia 1.1.1. Dac nregistrrile din fiier au o dimensiune variabil, se impune existena unor marcaje speciale numite separatori de nregistrare. Observaia 1.1.2. Organizarea datelor n fiiere este necesar, dac: volumul datelor prelucrate este foarte mare i depete capa-

citatea memoriei interne disponibile. datele trebuie stocate n vederea unei prelucrri ulterioare, n

cadrul aceluiai program sau al altora. Observaia 1.1.3. n Turbo Pascal se poate lucra cu trei tipuri de fiiere: 1) fiiere cu tip componentele au acelai tip i sunt stocate pe disc. 2) fiiere fr tip componentele sunt blocuri de informaii de

lungime fix i sunt stocate pe disc. 3) fiiere text componentele sunt caractere structurate pe linii de

lungimi variabile putnd fi stocate pe suport magnetic sau, fac obiectul operaiilor de intrare-ieire cu consola (tastatura, ecran).

Observaia 1.1.4. Tipul fiier se aseamn cu tipul tablou prin faptul c toate componentele au acelai tip, dar se deosebete de acesta prin modul de acces la componente i prin accea c numrul componen-telor unui tip fiier nu este limitat. Accesul la componentele unui fiier poate fi: 1) secvenial - pentru a accesa o anumit component trebuie

parcurse toate componentele care o preced. 2) direct orice component se poate accesa imediat dac se

precizeaz numrul ei de ordine in fiier, fr s fie necesar parcurgerea elementelor precedente.

Accesul direct este permis numai pentru fiierele cu sau fr tip stocate pe disc. Discul este singurul suport adresabil, care permite calculul adresei unei componente, dac i se cunoate lungimea i numrul de ordine n fiier.

8

Fiecrui fiier cu sau fr tip stocat pe disc i se asociaz de ctre compilator o variabil numit indicator de fiier care cuprinde, n tot timpul prelucrrii fiierului, numrul de ordine al componentei curente. Observaia 1.1.5. ntr-un program Turbo Pascal un fiier se identific printr-o variabil de tip fiier. Aceast variabil de tip fiier nu are voie s apar n atribuiri sau expresii. Prelucrarea fiecrui fiier trebuie precedat de apelul unei proceduri standard ASSIGN, prin care variabilei de tip fiier i se asociaz numele unui anumit fiier fizic. Toate operaiile n care se va specifica variabila respectiv se vor face asupra fiierului fizic asociat prin procedura assign. Procedure assign Forma general Procedure assign (var fiier;nume:string); Efect I se asociaz variabilei de tip fiier din program,

numele fiierului fizic de pe suportul extern . Apelul assign (fiier, nume); unde fiier reprezint

identificatorul variabilei de tip fiier din program, iar nume reprezint o expresie de tip string, a crei valoare este numele fiierului fizic de pe suport extern.

Observaia 1.1.6. Asocierea rmne valabil pn la un alt apel al procedurii assign, asupra aceluiai fiier extern. Apelul se termin cu eroare dac fiierul fizic este deschis n momentul apelului. Prelucrrile admise asupra unui fiier sunt: Crearea fiierului Scrierea componentelor n fiier. Exploatarea fiierului Citirea i prelucrarea componentelor

fiierului Actualizarea fiierului Adugarea, modificarea sau tergerea

unor componente ale fiierului. Observaia 1.1.7. Oricare ar fi modul de prelucrare a unui fiier, accesul la componentele acestuia este permis numai dac acesta este deschis. Deci orice prelucrare ncepe cu deschiderea fiierului i se ncheie cu nchiderea sa. Deschiderea unui fiier se realizeaz prin comenzile reset (fiier) sau rewrite(fiier). nchiderea fiierului prin comanda close(fiier).

9

Executarea procedurii reset (fiier) realizeaz: Iniializarea indicatorului de fiier cu valoarea 0 (pentru fiiere cu

sau fr tip); Iniializarea variabilei Filemode din unit-ul System astfel nct

s permit, n continuare, executarea de operaii de citire pentru fiiere de tip text sau operaii de citire/scriere pentru fiiere cu tip sau fr tip.

Observaia 1.1.8. Apelul se termin cu eroare, dac fiierul fizic nu exist. Dac fiierul este deschis n momentul apelului, acesta se nchide, apoi se redeschide. Apelul procedurii rewrite are forma: Rewrite(fiier) i executarea procedurii const n: Iniializarea indicatorului de fiier cu valoarea 0 (pentru fiier cu

sau fr tip). Iniializarea variabilei filemode pentru a permite n continuare:

operaii de scriere pentru fiier de tip text, respectiv operaii de scriere/citire pentru fiiere cu sau fr tip.

Observaia 1.1.9. Apelul se termin cu eroare, dac nu este loc suficient pe disc pentru noul fiier. Dac fiierul fizic asociat exist pe suportul extern coninutul su este ters. Dac fiierul s-a deschis prin executarea acestei proceduri, operaiile de citire sunt permise numai dup ce s-au fcut scrieri. Apelul procedurii close are forma: close(fiier) i are ca efect nchide-rea fiierului prin care operaiile de citire/scriere a componentelor lui sunt interzise pn la o nou deschidere. Definiia 1.1.2. Poziia curent dintr-un fiier (zona n care se efectueaz operaiile de intrare/ieire) se numete indicator de fiier. Fiiere text. Creare i exploatare Un fiier text este format din caractere structurate pe linii. Fiecare linie este terminat cu un marcaj sfrit de linie (eng. eol - end of line), format din caracterele CR i LF (tastei ENTER i corespunde secvena de caractere CR (eng. carriage return) i LF (eng. line feed) cu codurile ASCII 13, respectiv 10, secven care reprezint marcajul de sfrit de linie). Observaia 1.1.10. Fiierele text se stocheaz pe disc sau sunt asociate unui dispozitiv logic (i se termin cu caracterul ^Z)

Observaia 1.1.11. Tipul fiier text se declar conform diagramei: Tip fiier text Dimensiunea zonei tampon asociat unui fiier text este, n general 128 bytes. Un fiier text poate fi deschis prin apelul procedurilor: rewrite - sunt permise numai operaii de scriere reset - sunt permise numai operaii de citire append - sunt permise numai operaii de scriere; realizeaz

deschiderea la sfrit a unui fiier creat pe disc i permite adugarea unor noi linii la sfritul fiierului.

Observaia 1.1.12. Accesul poate fi numai secvenial (pas cu pas), nu poate fi accesat direct. Procedurile i funciile pentru prelucrarea fiierelor text Procedura read Apelul: Read (fiier, v1 [, v2, , vn]); Efect: Citete din fiierul fizic asociat variabilei fiier n

variabila (variabilele) v1[, , vn] unde: fiier este numele variabilei asociate fiierului fizic (dac lipsete se consider INPUT), iar v1, v2, , vn sunt n variabile (n>1) care pot fi de tip: char, string, integer i variantele, real i variantele n virgul mobil.

Procedura readln Apelul: Readln (fiier, v1[, v2 ,, vn]); Efect: Citete din fiierul fizic asociat variabilei fiier n

variabila v1[, , vn] i trece la linie nou n fiier. Este echivalent cu secvena: read(fiier, v1[, v2 ,, vn]); readln(fiier);

Procedura write Apelul: Write(fiier, v1[, v2, , vn]); Efect: Scrie n fiierul fizic asociat variabilei fiier, variabilele

v1[, v2, , vn]. Procedura writeln Apelul: Writeln (fiier, v1 [, v2, , vn]); Efect: Scrie n fiierul fizic asociat variabilei fiier, variabilele

v1[, v2, , vn] i un marcaj de sfrit de linie n fiierul fizic asociat variabilei fiier. Este echivalent cu secvena: write(fisier, v1[, v2, ..., vn]); writeln(fisier);

text

10

11

Funcia EOF (End Of File) este de tip boolean, deci ntoarce dou valori: true, dac poziia curent n fiier este dup ultimul caracter al fiierului, sau fiierul este vid, respectiv false, n celelalte cazuri. Apel: eof [(var fiier)] Funcia seekoln este de tip boolean, deci ntoarce dou valori: true, dac avem sfrit de linie, respectiv false, n caz contrar Apel: seekeoln[(fiier)]; Efect: atunci cnd caracterul curent ce urmeaz a fi citit din zona tampon asociat fiierului este un caracter egal cu SPAIU sau TAB, se crete adresa caracterului curent din zona tampon astfel nct s fie un caracter diferit de spaiu sau tab. Returneaz true, cnd caracterul curent care urmeaz s fie citit din zona tampon reprezint un marcaj de sfrit de linie sau de sfrit de fiier; false altfel. Funcia EOLN returneaz un rezultat de tip boolean, true dac indicatorul este la sfrit de linie, iar false, n caz contrar. Apel: eoln[(fiier)]; Observaia 1.1.13. Funcia seekeoln difer de funcia eoln prin faptul c face salt peste caracterul SPAIU (blanc) sau TAB, nainte de a testa sfritul de linie. Funcia SEEKEOF este de tip boolean Apel Seekeof [(fiier)]; Efect a) se modific adresa caracterului curent din zona

tampon astfel nct acesta s fie un caracter diferit de spaiu, tab sau sfrit de linie (face salt peste ele) b) returneaz: true, cnd poziia curent n fiier este dup ultimul caracter al acestuia i false, n caz contrar.

Observaia 1.1.14. Funcia seekeof difer de eof prin faptul c face un salt peste caracterele: tab, blanc, sfrit de linie, nainte de a testa sfritul de fiier. Procedura APPEND(nume fiier) deschide fiierul n vederea adug-rii la sfarit n fiier. Procedura ERASE Apelul: Erase(fiier); Efect: Realizeaz tergerea fiierului fizic asociat variabilei

fiier. n momentul apelului fiierul trebuie s fie nchis. Procedura RENAME schimb n program numele fiierului de pe suport extern. Apelul rename (fiier,nume) realizeaz redenumirea

12

fiierului fizic asociat variabilei fiier cu numele dat prin irul de caractere nume. n momentul apelului fiierul asociat variabilei fiier trebuie s existe, s fie nchis i nu trebuie s existe un alt fiier cu numele nume.

Exemplificare: rename(f,'document.dat') schimb numele fizic asociat lui f cu numele fizic document. Aplicaia 1.1.1. S se afieze numrul cuvintelor citite dintr-un fiier text, introdus de la tastatur (cuvintele sunt separate prin unul sau mai multe spaii). Soluie: program nr_cuv_din_fis_INPUT; var c:char; n:longint; begin n:=0; write('linia:'); while not eof do begin while seekeoln do begin read(c); while (c' ') and not eoln do read(c); n:=n+1 end; readln; write('Introducei linia:') end; writeln('Fiierul cuprinde:',n,'cuvinte') end. {n reine numarul de cuvinte din text} Exemplu de executare: Intrare: Ana are main Ieire: Fiierul are 6 cuvinte. Crina are calculator Aplicaia 1.1.2. S se afieze numrul numerelor din fiecare linie a fiierului standard de intrare INPUT. Soluie: program afis_nr_de_numere_din_liniile_fisierului_input; var n,nr,i:byte; begin i:=1; write('linia', i,':');

while not eof do begin n:=0; while not seekeoln do begin read(nr); inc(n) end; readln; writeln('din linia', i, 's-au citit' ,n, 'numere'); inc(i); write('linia',i,':') end end. Exemplu de executare: Intrare: Ieire: linia 1: 10 20 30 din linia 1 s-au citit 3 numere linia 2: 40 50 din linia 2 s-au citit 2 numere. Fiiere cu tip Definiia 1.1.3. Fiierele cu tip sunt construite din articole cu lungime fix, de acelai tip (pot fi: array, string, set, record sau tipuri simple de date-intregi, char, etc); se mai numesc i fiiere cu prelucrare la nivel de articol.

Declararea unui fiier cu tip se realizeaz astfel:

13

Exemplul 1. S declarm un fiier ale crui articole sunt numere ntregi.

IDENTIFICATOR DE TIPOF FILE

Soluie: type fisint = file of integer; var a:fisint; sau var a: file of integer; Exemplul 2. S se declare un fiier cu articole de tip record. Soluie: type inreg = record

nume:string[30]; varsta:byte; end;

fisier = file of inreg; var f:fisier;{f-reprezint fiierul cu tip ce poate conine articole }

14

Observaia 1.1.15. Accesul la datele fiierului cu tip este secvenial sau direct. Citirea i scrierea din/in fiier 1) read(fiier, v1, v2, , vn); - prelucreaz n componente succesive

din fiier, ncepand cu componenta situat la poziia indicatorului de articol i se memoreaz n variabilele v1, v2, , vn (valoarea indicatorului de articol crete cu 1, dup citirea unei componente).

2) write(fisier, v1, v2, , vn); - se scrie coninutul variabilelor v1,v2,,vn n componentele succesive ale fiierului fiier (indicatorul creste cu 1 dup scrierea fiecrei variabile), evident tot ncepand de la poziia iniial a indicatorului.

Funcii i proceduri utile n prelucrarea fiierelor cu tip 1) EOF(fiier) ntoarce true, dac pointerul este la sfaesit de fiier,

sau false, altfe; 2) Filesize(fiier) ntoarce numrul de componente al fiierului

asociat variabilei fiier; 3) Filepos(fiier) ntoarce poziia pointerului(numrul de ordine al

componentei curente); 4) Seek(fisier,n) - pointerul se poziioneaz la valoarea n. Exemplu:

seek(fisier,7)-pointerul de fiier puncteaz a aptea valoare. 5) Truncate(fiier) terge toate componentele fiierului ncepand cu

componenta indicat de pointerul de fiier pan la ultima component din fiier.

6) Erase(fiier)- terge fiierul; 7) Rename(fiier,noul-nume) schimb din program numele

fiierului de pe suport extern. Aplicaia 1.1.3. Se consider fiierul cu nregistrri DATE , care are urmtoarea structur:

cod_mat:string[5]; den_m:string[20]; cod_mag:integer; cant:real; um :string[4]; pu:real;

S se scrie un program care sorteaz fiierul descris anterior dup valorile campului cod material. Soluie: type inr = record cod_mat:integer; den_mat:string[20]; cod_mag:integer;

cant:real; um:string[4]; pu:real; end; fisier = file of inr;

var inr1, inr2:inr; f:fisier;ok:boolean; i, j, t, mag:integer; m1,m2:integer; c_er:integer;

15

procedure sort1(i,j:integer); var k:integer; begin

repeat ok:=true; for k:=i to j-1 do

begin seek(f,k); read(f,inr1,inr2); if inr1.cod_mat>inr2.cod_mat then

begin seek(f,k); write(f,inr2,inr1); ok:=false end end;

until ok; end; {program principal} begin assign(f,'date');reset(f);

repeat ok:=true; for i:=0 to filesize(f)-2 do

begin seek(f,i); read(f,inr1,inr2); if inr1,cod_mag>inr2.cod_mag then

begin seek(f,i); write(f,inr2,inr1);ok:=false end; end

until ok; close(f); reset(f);read(f,inr1); mag:=inr1.cod_mag; i:=0;

writeln('Magazia:',inr1.cod_mag); while not eof(f) do

begin read(f,inr1); with inr1 do if mag=cod_mag then begin j:=filepos(f)-1; sort1(i,j) end else

begin i:=filepos(f)-1; mag:=inr1.cod_mag; writeln(Magazia:, cod_mag); end;

end; end.

Fiiere fr tip Definiia 1.1.4. Fiierele fr tip sunt constituite din blocuri de lungime fix i aceeai pentru fiecare bloc. Observaia 1.1.15. Un bloc cuprinde o succesiune de octei. Citirea/scrierea dintr-un fiier fr tip presupune transferul unuia sau mai multor blocuri. Declararea fiierelor fr tip se realizeaz astfel: FILE

Deschiderea fiierelor fr tip se realizeaz astfel: Rewrite(fiier,[dimensiune_bloc]) Reset(fiier,[dimensiune_bloc]);

unde dimensiune_bloc este de tip ntreg i reprezint numrul de octei pe care a fost scris blocul(implicit este 65536 octei) Citirea i scrierea:

Blockread(fiier, variabil, nr_blocuri_care_se_vor_citi)-citete din fiier n variabila un numr de blocuri specificate. Blockwrite(fiier, variabil, nr_blocuri_care_se_vor_scrie)-scrie blocurile specificate.

Observaia 1.1.16. Indicatorul de fiier reine numrul blocului curent. Accesul poate fi secvenial sau direct. Observaia 1.1.17. Asemnator cu fiierele cu tip se pot folosi urmtoarele funcii/proceduri: seek, eof, filesize, filepos, erase, rename. Aplicaia 1.1.4. S se creeze un fiier fr tip cu n inregistrri avand cmpurile: nume:string[16]; varsta:integer; type inregistrare=record nume:string[20]; varsta:integer; end; var f:file;inr:inregistrare; n,i:integer; begin assign(f,'date');write('n=');readln(n); rewrite(f); for i:=1 to n do begin write('Nume=');readln(inr.nume); write('Varsta=');readln(inr.varsta); blockwrite(f,inr,1); end; close(f); end.

16

17

1.2. Fiiere n limbajul C Fiierul este un grup de octei stocai pe un suport de memorie extern care este tratat n mod unitar de ctre sistemul de operare.

Lucrul cu fiiere n C presupune cunoscut modul de lucru cu date de tip struct i cu pointeri. Se utilizeaz conceptul de flux (stream).

Un flux se reprezint, n C, printr-un pointer la o entitate de tip FILE care conine informaii despre poziia curent n flux, indicatori de eroare i de sfrit de fiier, zone tampon (eng. buffers) asociate. Limbajul C permite folosirea a dou tipuri de flux: text i binare.

Un flux text presupune transferul de caractere organizate n linii de caractere. Fluxul binar reprezint o succesiune de octei care nu suport nici o modificare n timpul transferului.

Deschiderea i nchiderea unui fiier Orice fiier nainte de a fi prelucrat trebuie deschis. Dup terminarea prelucrrii unui fiier acesta trebuie nchis. Forma general a funciei pentru deschidere:

FILE *fopen(const char *numele_fis, const char *mod); - "deschide un fiier" i-i asociaz numele respectiv; - returneaz un pointer spre tipul FILE (vezi fiierul STDIO.H) sau

Null, n caz de eroare unde: numele_fis = pointer ctre numele fiierului ce urmeaz a fi deschis; mod = pointer spre un ir de caractere care definete modul de prelucrare al fiierului, dup deschidere. Se definete astfel: r = deschiderea unui fiier text pentru citire w = deschiderea unui fiier text pentru scriere a = deschiderea unui fiier text pentru adugare r+ = deschiderea unui fiier text pentru modificare r+b = citire/scriere binar rb = citire binar wb = scriere binar Observaia 1.2.1. Cu funcia fopen, un fiier inexistent se poate "deschide" n modul r, w sau a, iar n acest caz este i creat. Observaia 1.2.2. Dac se deschide un fiier existent n modul w atunci se va crea unul nou cu acelai nume, vechiul coninut se pierde. Apelul: fp = fopen("INPUT.TXT") - la apel se deschide fiierul cu numele INPUT.TXT i se stabilete o legtur logic ntre pointerul fp i fiierul INPUT.TXT.

18

Observaia 1.2.3. Deschiderea unui fiier n modul a pentru adugarea de nregistrri dup ultima nregistrare existent n fiier. Observaia 1.2.4. Fiierele corespunztoare dispozitivelor standard nu se deschid de ctre utilizator, ntruct ele sunt deschise automat la lansarea programului. Observaia 1.2.5. Fiierele disc i dispozitivele periferice sunt gestio-nate de variabila pointer. Prelucrarea pe caractere a unui fisier Fiierele standard pot fi scrise i citite caracter cu caracter, folosind dou funcii simple: putc i getc. Forma general:

int putc(int c, FILE *pf); returneaz valoarea lui c, reprezentand codul ASCII al caracterului scris n fiier sau -1, dac este eroare; pf reprezint pointer spre tipul FILE a crui valoare a fost returnat de funcia fopen la deschiderea fiierului n care se scrie. Observaia 1.2.6. n particular pf poate fi unul din pointerii: stdout - ieire standard; stderr - ieire pe terminal n caz de eroare; stdaux - ieire serial; stdprn - ieire paralel la imprimant. Forma general:

int getc(FILE *pf); returneaz codul ASCII al caracterului citit sau EOF la sfrit de fiier; pf - pointer spre tipul FILE a crui valoare a fost returnat de funcia fopen la deschiderea fiierului. n particular pf poate fi pointerul stdin (citire (intrare) de la tastatur). nchiderea unui fiier (eliberarea spaiului de memorie alocat folosind fopen i ntreruperea legturii logice) se realizeaz cu funcia fclose care are prototipul

int fclose (FILE *pf); i returneaz valoarea: 0, la nchidere normal sau -1, n caz de eroare. Aplicaia 1.2.1. S se elaboreze un program pentru a copia intrarea standard la ieirea standard folosind funciile putc i getc. Soluie: #include void main(void) {

int c; c= getc (stdin); while (c != EOF) {putc(c, stdout); c=getc(stdin);}

}

19

Aplicaia 1.2.2. Cum se copiaz intrarea standard la imprimant? Soluie: # include void main(void){

int c; c= getc (stdin); while (c != EOF){putc(c, stdprn); c=getc(stdin);}

} Operaii de intrare/ieire cu iruri de caractere Biblioteca standard a limbajului C conine funciile: fgets i fputs care permit citire dintr-un, repectiv scrierea ntr-un fiier ale crui nregis-trri sunt iruri de caractere. Prototipul: char *fgets (char *s, int n, FILE *pf); returneaz valoarea pointerului s sau NULL la ntlnirea sfritului de fiier; s - pointerul spre zona n care se pstreaz caracterele citite (numele unui tablou de tip char de dimensiune cel puin n); n - dimensiunea n octei a zonei n care se citesc caracterele din fiier; pf - pointerul spre tipul FILE a crui valoare s-a definit la deschiderea fiierului. Observaia 1.2.7. Citirea se oprete la ntlnirea caracterului '\n' sau dup citirea a cel mult n-1 caractere. n acest caz, n zona receptoare se transfer caracterul '\n' i apoi caracterul '\0' (NULL) Funcia fputs scrie ntr-un fiier un ir de caractere care se termin prin '\0' i are prototipul int fputs(const char *s, FILE *pf);

Returneaz codul ASCII al ultimului caracter scris n fiier sau -1 la eroare; pf - pointer spre tipul FILE care definete fiierul n care se scrie; s-pointerul spre zona care conine irul de caractere, care se scrie. Observaia 1.2.8. Pentru a citi de la intrarea standard stdin, se poate folosi funcia gets, care nu mai are parametrii pf i n. Parametrul pf este implicit stdin. Observaia 1.2.9. La fiierele text, cnd este ntalnit caracaterul '\n', acesta este transformat ntr-o secven "newline". Fiierele binare nu produc transformri. Operaii de intrare-ieire cu format Acest lucru se realizeaz folosind funciile: fscanf- citire cu format dintr-un fiier; fprintf - scriere cu format n fiier. Opereaz la fel ca printf i scanf cu excepia faptului c lucreaz cu fiiere, nu cu consola.

20

Apelul lui fscanf: fscanf(FILE *pf, char *format, par1, par2, ,parn) - citete date, conform formatului, din stream; returneaz valoare EOF, la ntalnirea sfaritului de fiier; pf - pointer spre tipul FILE, a crui valoare a fost definit prin apelul funciei fopen; format - conine texte i/sau specificatori de format (_). Parametrii par1, par2, ,parn definesc zonele receptoare ale datelor citite prin intermediul funciei fscanf. Exemplificare: Apelul fscanf(pf, "%d %c %f", &i, &n, &c); Apelul fprintf(FILE *pf, char *format, par1, parn) - scrie date, n stream, conform formatului. Poziionarea ntr-un fiier Pan acum am citit/scris datele unui fiier n mod secvenial de la nceput pn la sfarit. Utiliznd funcia fseek se poate accesa orice articol al unui fiier (acces aleator). Cu ajutorul ei se poate deplasa capul de citire/scriere al discului n vederea prelucrrii ntregistrrilor fiierului ntr-o ordine oarecare, diferit de cea secvenial. Prototipul Int fseek(FILE *pf, long deplasament, int origine); Returneaz 0, la poziia corect sau o valoare diferit de 0, n caz

de eroare; unde: deplasament reprezint numrul de octei peste care se va deplasa capul de citire/scriere al discului, iar origine ia una din valorile: 0 Deplasamentul se consider de la nceputul fiierului; 1 Deplasamentul se consider din poziia curent a

capului de citire/scriere; 2 Deplasamentul se consider de la sfaritul fiierului.

O alt funcie util n cazul accesului aleator este funcia ftell, care indic poziia capului de citire/scriere din fiier. Prototip Long ftell(FILE *pf); Returneaz O valoare de tip long care definete poziia curent a

capului de citire/scriere, i anume reprezint deplasa-mentul n octei a poziiei capului fa de nceputul fiierului .

Aplicaia 1.2.3. Folosind funcia fseek( ) cutai i citii orice byte dintr-un fiier specificat

21

Soluie: #include #include void main(void) {

FILE *pf; long loc;

if ((pf= fopen("g1.cpp", "r"))==NULL) { printf ("Nu pot deschide fisierul! "); exit (1); }

printf(Introducei locaia , n octeti, din fiier, ce se va vizualiza! ); scanf(%d, &loc); if (fseek(fp, loc, 0)){

printf("Eroare de cautare! "); exit(1); }

printf("Valoarea de la locatia %ld este %c", loc, getc(pf)); fclose(pf); } Alte funcii pentru prelucrarea fiierelor 1 nchiderea unui fiier se realizeaz cu ajutorul funciei fclose

care are prototipul: int fclose (FILE *f); Funcia returneaz valoarea 0 la nchidere normal, respectiv -1 n caz de eroare.

2 Testarea atingerii sfritului de fiier se poate realiza cu ajutorul funciei feof, care are prototipul: int feof (FILE*f); Funcia feof returneaz valoare 0, dac indicatorul de fiier nu este la sfritul fiierului, respectiv o valoare diferit de 0, dac indicatorul de fiier este la sfrit.

3 int rename(const char *nume_vechi, const char *nume_nou);- redenumete un fiier;

4 int remove(const char *filename); - terge un fiier de pe suportul de informaie pe care este memorat;

5 size_t fread(void *ptr, size_t size, size_t n, FILE *stream);- citete date dintr-un fiier; mai precis, citete n elemente, fiecare cu lungimea size din stream, ntr-un bloc specificat de ptr;

6 size_t fwrite(const void *ptr, size_t size, size_t n, FILE * stream) - adaug fiierului stream n elemente, fiecare avand dimensiunea size din blocul specificat de ptr.

1.3. Probleme rezolvate

R1.3.1. Se consider un fiier text IN.txt ce conine numere ntregi dispuse pe mai multe linii i separate prin spaii. Scriei un program care creeaz un fiier OUT.txt ce conine pe fiecare linie media aritmetic a numerelor situate pe aceeai linie n fiierul IN.txt. Media aritmetic va fi scris cu doua zecimale Varianta C

#include #include void main (void){FILE *fin, *fout; char sir[256],sn[256]; long int n,i,j1,j2,suma; float media; if (!(fin=fopen("IN.txt","r"))){

printf("\n Nu pot deschide sursa!"); exit(1);}

if (!(fout=fopen("OUT.TXT","w"))){ printf("\n Nu pot crea fisierul destinatie!");exit(1);} while (!feof(fin)){

fgets(sir,256,fin); n=0;i=0;j1=0;j2=0;suma=0; while(sir[i]){ if (sir[i]=' ') {sn=substr(sir,j1,j2);

suma=suma+atoi(sn); j1=j2=i+1;sn=' ';i++; }

else {i++; j2++;}} media=suma/n; fprintf(fout, "%10.2f\n",media); } fclose(fin);fclose(fout); } char substr(char sir[256]; int j1,j2){ char ss[]="';int i; if ((j1>strlen(sir)||(j2>strlen(sir))

return 1; for(i=j1;i

R1.3.2. Scriei un program care verific dac dou fiiere Input1.txt i Input2.txt au coninut identic. Soluie:

23

Varianta Pascal Var i:integer;

f,g:text; s,s1:string; identic:boolean;

Begin assign(f.Input1.txt); reset(f); assign(g.Input2.txt); reset(g); Identic:=true; While

(not eof(f)) and (not eof(g)) and (identic) do

Begin readln(f,s); readln(g,s1); If ss1 then identic:=false; End; if eof(f) and not eof(g) then Identic:=false; if eof(g) and not eof(f) then Identic:=false; if identic then write(Fiierele sunt identice) else write(Fisierele nu sunt identice);

Varianta C #include #include void main (void){ char sir1[256],sir2[256]; FILE *f1, *f2; int ind; if ((f1=fopen("Input1.txt","r")) ==NULL) { printf("\n Nu pot deschide fis1!"); exit(1); } if((f2=fopen("Input2.txt","r")) ==NULL) { printf("\n Nu pot deschide fis2!"); exit(1); } ind=0; while ((!feof(f1))&&(!feof(f2))){

fgets(sir1,f1); fgets(sir2,f2); if (strcmp(sir1,sir2)!=0)

ind=1 }

clrscr(); if (ind=0) printf("\n Fisierele sunt identice!");else printf("\n Fisierele nu sunt identice!") fclose(f1); fclose(f2); }

close(f); close(g); end.

24

R1.3.3. Creai un program care transform toate literele mici din fiierul INPUT.txt n majuscule. Soluie: program pr; uses crt; var f,f1:text;i:integer; s,s1:string; begin clrscr; assign(f,'in.txt'); reset(f); assign(f1,'in1.txt'); rewrite(f1);

while not eof(f) do begin readln(f,s); s1:=''; for i:=1 to length(s) do s1:=s1+upcase(s[i]); writeln(f1,s1); end; close(f);close(f1); end.

Exerciiu: S se traduc programul de mai sus n limbajul C. R1.3.4. Se consider o matrice a cu n linii i n coloane stocat n fiierul Matrice.txt (pe prima linie este scris valoarea n, iar pe urmtoarele n linii matricea a, linie cu linie). Se cere s se afieze n fiierul SUMA.TXT, suma elementelor de pe diagonala principal. program matrice; uses crt;type mat = array[1..10,1..10] of integer; var a:mat;

i,j,s,n:integer; f,g:text; begin

assign(f,'Matrice.txt'); reset(f); assign(g,'Suma.txt'); rewrite(f); readln(f,m); readln(f,n);

for i:=1 to m do begin for j:=1 to n do read(f,a[i,j]); readln(f) end; s:=0; for i:=1 to n do s:=s+a[i,i]; writeln(g,s); close(f);

close(g); readln; end.

25

Aplicaii propuse AP1. n fiierul SECVENTE.TXT sunt scrise mai multe linii. Fiecare linie conine cate o secven, secven format din primele patru numere prime (fiecare secven conine cel puin odat fiecare numr prim, fr spaii ntre ele), ir format din cel mult 255 de cifre. Se cere s se scrie n fiierul PERECHI.TXT, pe cate o linie, desprite prin spaii, indicii elementelor ce reprezint capetele secvenei determinate din cea curent din fiierul de intrare astfel ncat secvena din ir s aib lungime maxim i s conin un numr egal de cifre din fiecare numr prim din cele date. Exemplu: Pentru fiierul SECVENTA.TXT 55552753275325732357223 253257322 Atunci fiierul PERECHI.TXT va conine 5 20 4 7 AP2. n fiierul NUMERE.TXT sunt scrise dou numere cu maxim dou cifre fiecare. Se cere s se scrie n fiierul RASPUNS.TXT mesajul DA, dac unul dintre cuvintele este anagrama celuilalt (conin exact acelai cifre eventual n alt ordine) sau NU, n caz contrar. AP3. n fiierul MATRICE.TXT se afl o matrice n format ptratic astfel: pe prima linie dimensiunea matricei, iar pe urmtoarele linii despite prin spaii elementele matricei. Pe ultima linie se afl un numr ce reprezint linia k. Se cere s se afieze n fiierul ORDONAT.TXT matricea cu elementele n linia k ordonate descrescator. AP4. Se citesc doi vectori deja ordonai cresctor (dou linii) din fiierul VECTORI.TXT; numerele pe linie sunt desprite prin spaii. Se cere s se scrie n fiierul INTERCLASARE.TXT vectoul obinut prin interclasarea celor doi.

Exemplu: Pentru fiierul VECTORI.TXT 2 5 7 3 4 9 11 Atunci fiierul INTERCLASARE.TXT va conine 2 3 4 5 7 9 11

AP5. Se citesc mai multe numere reale din fiierul INTRARE.TXT Ele sunt dispuse pe mai multe linii, desprite prin spaii n cadrul

26

fiecrei linii. S se scrie n fiierul IESIRE.TXT pe prima linie numrul de numere distincte, iar pe urmtoarele linii, desprite prin spaii, aceste numere ordonate cresctor.

Exemplu: Dac fiierul INTRARE.TXT conine 2 3.7 2 5 8 5 Atunci fiierul IEIRE.TXT conine 4 2 3.7 5 8

AP6. Se cere s se scrie n fiierul OUT.TXT numrul de numere prime de pe fiecare linie din fiierul IN.TXT i pe urmtoarea linii numerele prime din fiierul de intrare. AP7. Se dau dou fiiere MULT1.TXT i MULT2.TXT care conin, desprite prin cate un spaiu mai multe numere reale reprezentand cate o mulime fiecare. Se cere s se scrie n fiierul INT_REUN.TXT pe prima linie, intersecia celor 2 mulimi, iar urmtoarea linie reuniunea lor.

Exemplu: Dac fiierul MULT1.TXT conine 5.5 6 8 7.6

i fiierul MULT2.TXT conine 5.5 8 7

atunci fiierul INT_REUN.TXT 5.5 8 5.5. 6 7 7.6 8

AP8. Fiierul text FIS.DAT conine numere i cuvinte pe mai multe linii, fiecare avand maximum 255 de caractere. S se realizeze un program care inventariaz coninutul fiierului, afisand pentru fiecare linie i pentru ntregul fisier numrul de caractere, numrul de cuvinte i numrul de valori numerice. AP9. S se ordoneze descresctor dup medii, nregistrrile unui fiier care conine datele i rezultatele candidaiilor la un examen de admitere n clasa a IX-a (sau la facultate). Fiecare nregistrare este compus din cinci cmpuri: un nume (variabil de tip string cu 20 de caractere), trei note reale reprezentand notele la cele dou probe, media obinut la examen i un cmp logic ce memoreaz rezultatul final (ADMIS sau RESPINS). Programul va afia rezultatul examenului de admitere n funcie de un numr citit de la tastatur reprezentnd numrul de locuri posibile.

27

AP10. Fiierul PRODUSE.DAT conine informaii despre produsele dintr-un magazin alimentar: numele produsului (maxim 20 de caractere), preul unitar (numr ntreg, maxim 100.000), cantitatea (numar real) i termenul de garanie (sub forma zi-luna-an cnd expir termenul de folosin al produsului). S se afieze n funcie de data (i s se elimine din fiier) produsele expirate i costul lor. AP11. S se determina frecvena apariiei caracterelor (date de codul lor ASCII) dintr-un fiier precizat. AP12. S se afieze pe ecran toate caracterele unui fiier text existent, caracterele netiparibile (cu cod ASCII mai mic dect 32) fiind nlocuite la scriere cu codul lor ASCII, precedat de caracterul '#'. AP13. S se creeze un fiier text avand ca surs dou fiiere text, al doilea fiind adugat n continuarea primului. AP14. [Numere mari] Se consider dou numere naturale n i m care au cel puin 200 de cifre. S se determine produsul celor dou numere. Pe prima linie a fiierului de intrare INPUT.TXT este scris numrul n, avand cifrele desprite prin cate un spaiu; pe a doua linie este scris numarul m, n mod similar. n fiierul OUTPUT.TXT se va scrie pe fiecare linie cate o cifra din rezultat. AP15. [Goldbach] Se consider un numr n>6 par. S se determine toate reprezentrile lui n ca sum de numere prime (sum cu numr minim de termeni). Rezultatele vor fi scrise n fiierul OUTPUT.TXT, fiecare linie coninand toi termenii dintr-o reprezentare.

Exmplu: Pentru n = 8, atunci OUTPUT.TXT conine 3 5 5 3

Nu se consider perechile (1, 7) i (7, 1) din cauza numrului 1. AP16. [Factor prim] Se consider un ir de n numere ntregi. S se determine factorul prim care apare la puterea cea mai mare n des-compunerea produsului celor n numere. Pe prima linie a fiierului INPUT.TXT este scris numrul n, reprezentand numrul de elemente din ir; pe urmtoarea linie sunt scrise cele n numere. Rspunsul se va afia pe ecran sub forma: i^j cu semnificaia: factorul i la puterea j

Exemplu: INPUT.TXT pe ecran se va afia : 4 3^4 24 9 17 21

28

AP17. [Cel mai mare divizor comun] Se consider n numere scrise n baza 16. S se determine cel mai mare divizor comun al celor n numere. Pe prima linie a fiierului INPUT.TXT este scris numrul de numere n; pe urmtoarele n linii se gsesc numerele scrise n hexazecimal. Numrul care reprezint c.m.m.d.c. al celor n numere, se va afia pe ecran.

Exemplu: INPUT.TXT se va afisa : 4\n 1A \n 8 \n 10 \n 2 2

AP18. [Cifre romane] S se scrie un program care transform un numr scris cu cifre romane n scrierea cu cifre arabe. n fiierul INPUT.TXT sunt scrise mai multe numere n scriere romana (corecte), fiecare pe cte o linie. Este posibil ca unele din cifrele romane sa fie scrise cu litere mici. Rspunsurile se vor afia pe ecran, fiecare numr pe cte o noua linie.

Exemplu: INPUT.TXT pe ecran se va afia: CDLIV 454 MMMMDLXXIII 4573 MCLXVI 1166 CMXLLVIII 948

AP19. [Propoziii] Se consider un text scris pe n linii (n fiierul de intrare INPUT.TXT). Fiecare linie constituie o propoziie. Cuvintele sunt formate doar din litere mari i litere mici i sunt desprite prin: spaiu, virgul i punct. Nici o propozitie nu are mai mult de 250 de caractere. Textul nu conine cuvinte n care s apar liniua de desprire (exemplu: "ntr-un").

S se determine propoziia cu cele mai multe cuvinte i s se afieze pe ecran scriind fiecare cuvnt pe linie nou avnd prima liter majuscul; separatorii nu se vor afia. Exemplu: INPUT.TXT se va afisa Ce faci Alo Unde esti Este O sa reusim Ora buna dimineata Sapte Alo, este ora sapte si treizeci de minute, fix. Si

Treizeci De

29

Minute Fix

AP20. [Matrice] Se d matricea A cu m linii i n coloane. S se scrie un program care prin intermediul unui meniu realizeaz urmtoarele operaii: Elimin din matrice linia L i coloana k fr a folosi o nou

matrice; Ordoneaz cresctor elementele de pe o coloan oarecare j prin

interschimbri de linii. Datele de intrare se vor citi dintr-un fiier text. AP21. [Ordonare] Se consider un tablou bidimensional ptratic de dimensiune n*n de numere ntregi. Se cere s se inverseze liniile i coloanele acestuia astfel nct tabloul obinut s conin elemente de pe diagonala principal n ordine cresctoare. Datele de intrare se citesc din fiierul de intrare INPUT.TXT sub forma urmtoare: pe prima linie este scris numrul n, reprezentnd numrul de linii i coloane, iar pe urmtoarele n linii, se gsesc elementele tabloului linie dup linie.

Rezultatul va fi scris n fiierul OUTPUT.TXT. Pe fiecare linie a fiierului se va scrie o linie a tabloului obinut.

Exemplu: INPUT.TXT OUTPUT.TXT 3 -1 8 7 2 4 3 2 3 4 1 5 6 1 6 5 -1 7 8

AP22. [Frecvene] Se consider un fiier INPUT.TXT care conine un text. Se cere determinarea listei cu frecvena de apariie maxim. In cazul cand exist mai multe soluii se vor afia toate. Fiierul de intrare conine pe fiecare linie cel mult 250 de caractere. Nu se va face distincie ntre litera mic i litera mare. Rezultatul se va afia pe ecran. Exemplu: INPUT.TXT pe ecran se va afisa: Mama si cu tata merg la piata A apare de 7 ori Memoriu, memoriu! M apare de 7 ori

30

AP23. [Ordonare n matrice] Se consider o matrice de dimensiune n*m. S se reaeze elementele n matrice astfel nct ele s apar n ordine cresctoare att pe linii ct i pe coloane. Matricea A se gsete n fiierul de intrare INPUT.TXT, fiecare linie a matricei pe cte o linie din fiier.

Nu sunt specificate valoarile pentru n i m. Matricea obinut se va scrie, n mod similar, n fiierul OUTPUT.TXT. n cazul n care exist mai multe soluii se va scrie n fiier numai una.

Exemplu: INPUT.TXT OUTPUT.TXT 3 2 5 44 3 1 1 2 2 2 2 2 6 7 55 4 3 2 3 3 3 3 3 4 4 10 4 2 4 5 4 4 4 4 4 5 34 5 6 8 2 4 5 5 5 6 6 7 5 3 2 4 41 3 8 10 34 41 44 55

AP24. O matrice cu elemente ntregi este memorat n fiierul text in.txt sub urmtorul format: pe prima linie numrul n de linii i numrul m de coloane. Pe urmtoarele n linii, elementele de pe fiecare linie a matricii. Citii matricea i tiprii-o pe coloane n fiierul out.txt. AP25. Citii un text scris pe mai multe linii n fiierul text.txt. Calculai, pentru fiecare liter a alfabetului, procentul de cuvinte care ncep cu acea liter. Separatori ntre cuvinte vor fi considerai: blancul, punctul, virgula i sfritul de linie. AP26. Creai cu editorul Pascal un fiier text pe mai multe linii. Scriei un program care calculeaz:

a) Numrul de cuvinte din fiier. Ca separatori ntre cuvinte se vor considera blancurile i sfritul de linie.

b) Tiprii liniile care conin cel puin o vocal. c) Cte linii conin mai mult de n cuvinte, n citit de la tastatur?

31

2. Structuri de date O structur de date este o mulime de date organizate ntr-un anumit mod mpreun cu relaiile dintre acestea.

n funcie de modul de alocare, structurile de date se clasific n: structuri de date statice : tabloul, nregistrarea, mulimea, fiierul.

Structurile de date statice ocup o zon de memorie constant pe toat durata de executare a blocului n care apare declaraia i elementele ocup poziii fixe. Fiierele sunt structuri de date externe (vezi capitolul 1).

structuri de date semistatice: stiva alocat static, coada alocat static. Structurile de date semistatice ocup o zon de memorie de dimensiune constat, alocat pe toat durata executrii blocului n care apare declaraia de structur, iar elementele ocup poziii variabile pe parcursul executrii programului.

structuri de date dinamice: lista nlnuit, structuri arborescente. Structurile de date dinamice ocup o zon de memorie de dimensiune variabil, alocat dinamic. Alocarea dinamic permite gestionarea memoriei n timpul executrii programului. Ele sunt mult mai flexibile dect cele statice i din aceast cauz sunt extrem de avantajoase.

Liste: O list este o colecie de elemente de informaie (noduri) aranjate ntr-o anumit ordine. Lungimea unei liste este numrul de noduri din list. Structura corespunztoare de date trebuie s ne permit s determinm eficient care este primul/ultimul nod n structur i care este predecesorul/succesorul (dac exist) unui nod dat. Limbajele Pascal sau C(++) ofer posibiliti de implementare a acestor structuri att static ct i dinamic. Operaiile curente care se fac n liste sunt: inserarea unui nod, tergerea (extragerea) unui nod, concatenarea unor liste, numrarea elementelor unei liste etc. Implementarea unei liste se poate face n principal n dou moduri:

Implementarea secvenial, n locaii succesive de memorie, conform ordinii nodurilor n list. Avantajele acestei tehnici sunt accesul rapid la predecesorul/succesorul unui nod i gsirea rapid a primului/ultimului nod. Dezavantajele sunt inserarea/tergerea relativ complicat a unui nod i faptul c nu se folosete ntreaga memorie alocat listei.

Implementarea nlnuit. Fiecare nod conine dou pri: informaia propriu-zis i adresa nodului succesor. Alocarea

memoriei fiecrui nod se poate face n mod dinamic, n timpul rulrii programului. Accesul la un nod necesit parcurgerea tuturor predecesorilor si, ceea ce poate lua ceva mai mult timp. Inserarea/tergerea unui nod este, n schimb, foarte rapid.

Listele se pot clasifica dup numrul de legturi n: liste simple liste duble liste circulare

O list simpl are o singur legtur, legtura ultimului element este adresa NIL/NULL. Pentru a accesa lista avem nevoie de o variabil care s pstreze adresa primului element (cap sau prim). O list dubl are dou legturi: legtura de tip urmtor i legtura de tip precedent sau anterior. O lista circular este o lista n care, dup ultimul nod, urmeaz primul, deci fiecare nod are succesor i predecesor.

Listele se pot clasifica dup locul n care se fac operaiile de adugare/eliminare astfel:

stive cozi

2.1. Liste simplu nlnuite ntre nodurile unei liste simplu nlnuite este definit o singur relaie de ordonare. Fiecare nod conine un pointer a crui valoare reprezint adresa nodului urmtor din list. Limbajul Pascal

type lista = ^nodnod=record

inf:tip ;urm: lista;

end;

Limbajul C(++) typedef struct nod { tip inf; struct nod *urm; }lista;

unde urm este adresa urmtorului nod (pointer ctre urmtorul nod), iar inf este un cmp de informaie util. Operaii asupra listei simplu nlnuite Crearea unei liste simplu nlnuite: 1. Se iniializeaz pointerul prim cu Nil/NULL, deoarece lista la

nceput este goal; 2. Se rezerv zon de memorie n memoria heap pentru nodul curent; 32

3. Se ncarc nodul curent cu date; 4. Se determin adresa ultimului nod i se realizeaz legtura cu

nodul creat; 5. Se reia cu pasul 2 dac se introduce un nod nou. Inserarea unui element x al crui cmp cheie a fost iniializat n

faa unei liste nlnuite LISTA-INSEREAZA(p,x) 1: urm(x) p 2: dac pNIL atunci px

Cutarea ntr-o list nlnuit p a elementului x se realizeaz prin subprogramul LISTA-CAUTA i returneaz pointerul la acest obiect.

LISTA-CAUTA(p,x) 1. qp 2. ct timp qNIL i cheie(q)x execut qurm(q) 3. returneaz q

Probleme rezolvate 1. Fiind dat o list simplu nlnuit cu elemente numere ntregi s se realizeze un program care s execute urmtoarele operaii: crearea, parcurgerea, adugarea unui nod la nceputul listei, adugarea unui nod la sfritul listei, tergerea unui nod de pe o poziie dat. Observaii:

Limbajul C(++) Funcia MALLOC se folosete pentru a rezerva octei din memoria heap. Trebuie inclus fiierul antet: stdlib.h sau alloc.h

Limbajul Pascal: Procedura NEW(pointer)- alocarea dinamic a memoriei pentru variabila dinamic pointer. Procedura DISPOSE(pointer)-eliberarea memoriei ocupate de ctre variabila dinamic pointer.

Rezolvare: Parcurgerea unei liste liniare simplu nlnuite se realizeaz cu un pointer care pleac de la capul listei i va referi pe rnd fiecare nod, prelucrnd informaiile din nod apoi se trece la urmtorul nod, prelu-crm informaiile din nod etc.

33

34

tergerea unui nod de pe o poziie dat p din interiorul listei se realizeaz astfel: se parcurge lista pn la pozitia p-1, se pstreaz nodul de pe poziia p, se realizeaz legtura ntre nodul p-1 i p+1 i, apoi se elibereaz memoria ocupat de nodul p. Implementare n Pascal: type lista=^nod;

nod=record inf:integer; urm:lista end; var p,x:integer;cap:lista;{adresa primului nod al listei} procedure adaug(var cap:lista;x:integer); {adaugarea la sfarsitul listei}

var nou,q:lista; begin new(nou);nou^.inf:=x;nou^.urm:=nil; if cap=nil then cap:=nou else begin

q:=cap; while q^.urm nil do q:=q^.urm;

q^.urm:=nou; end;

end; procedure adaug_inc(var cap:lista;x:integer); {adaugarea la inceput}

var nou:lista; begin new(nou);nou^.inf:=x;nou^.urm:=nil; {crearea nodului nou} if cap=nil then cap:=nou else begin

nou^.urm:=cap;cap:=nou; {realizarea legaturii si primul nod devine nodul creat}

end; end;

procedure listare(cap:lista);{listarea listei} var t:lista; begin t:=cap; while tnil do begin

write(t^.inf,' '); {prelucrarea informatiei} t:=t^.urm; {trecerea la urmatorul nod} end;

end; procedure sterge(var cap:lista; p:integer);

35

{stergerea nodului de pe pozitia p} var q,w,t:lista;i:integer; begin if cap=nil then writeln('Lista vida !!! ')

else if p=1 then begin {stergere la inceputul listei} q:=cap; cap:=cap^.urm; dispose(q); end

else if (cap nil) then begin t:=cap; i:=1; while (t^.urm nil) and (i+1

36

lista* sterg_inc(lista *prim){ lista *p;

p=prim; prim=prim->urm; free(p);

return prim; }

void adauga(lista*prim) { /*adauga un nod la o lista simplu inlantuita si returneaza pointerul spre nodul adaugat sau zero daca nu s-a realizat adaugarea*/

lista *p,*q; for (p=prim;p->urm!=NULL;p=p->urm) q=(lista*) malloc(sizeof(q)); scanf("%d",&q->inf); q->urm=NULL; p->urm=q; }

void main(){ lista *prim; prim=creare(); parcurgere(prim); prim=sterg_inc(prim); printf("\n"); parcurgere(prim); adauga(prim); parcurgere(prim);

} lista *creare(){

int n,i,inf; lista *prim,*p,*q; printf("nr. de elemente");scanf("%d",&n); printf("informatia primului nod"); scanf("%d",&inf); prim=(lista*)malloc(sizeof(prim)); prim->inf=inf;prim->urm=NULL; for(q=prim,i=2;iinf=inf;p->urm=NULL; q->urm=p; q=p; }

return(prim); } void parcurgere(lista *p){

lista *q; for (q=p;q;q=q->urm) printf("%d ",q->inf);

}

2. Inversarea legturilor ntr-o list simplu nlnuit. Rezolvare: Se parcurge lista iniial folosind trei variabile dinamice p1, p2, p3 care vor face referire la elementele consecutive din list. p1 va fi capul listei modificate. Implementare Pascal: program invers; type lista=^nod; nod=record inf:integer; urm:lista end; var i,n,x:integer; p:lista; procedure creare(var p:lista; x:integer);

var q:lista; begin if p=nil then begin new(p); p^.inf:=x; p^.urm:=nil end else begin

q:=p; while q^.urmnil do q:=q^.urm; new(q^.urm); q^.urm^.inf:=x; q^.urm^.urm:=nil; end;

end; procedure listare(p:lista);

var q:lista; begin q:=p; while qnil do begin write(q^.inf,' '); q:=q^.urm end; end;

Subprogramul de inversare n C: lista* invers(lista*p){

lista *p1,*p2,*p3; p1=p; p2=p->urm; p->urm=NULL; while (p2){

p3=p2->urm; p2->urm=p1;

p1=p2; p2=p3;

} return p1;

}

function inversare(p:lista):lista; var p1,p2,p3:lista; begin p1:=p; p2:=p^.urm; p^.urm:=nil; while p2nil do begin p3:=p2^.urm; p2^.urm:=p1; p1:=p2; p2:=p3; end; inversare:=p1; end;

37

38

begin read(n); for i:=1 to n do begin read(x); creare(p,x) end; listare(p);writeln; p:=inversare(p); listare(p)

end. 3. S se efectueze suma a dou polinoame rare (polinom cu foarte muli coeficieni egali cu zero) folosind liste simplu nlnuite. Rezolvare: Lista are ca informaie gradul i coeficientul fiecrui termen de coeficient nenul. Pentru a calcula suma este necesar s parcurgem listele celor dou polinoame i s adugm corespunztor n cea de-a treia list. Implementare Pascal: type lista=^nod;

nod=record grad:1..5000; coef:integer; urm:lista end; var a,b,p,q,r:lista;

i,n,m:integer; procedure creare(var p:lista); begin write('cati coeficienti nenuli are polinomul');readln(n);

new(p);readln(p^.coef,p^.grad); p^.urm:=nil;b:=p; {b este adresa ultimului nod}

for i:=2 to n do begin new(a); write('coef ',i,':');readln(a^.coef); write('grad ',i,':');readln(a^.grad); b^.urm:=a; b:=a; b^.urm:=nil end end; procedure listare(p:lista); var a:lista; begin a:=p; while anil do begin write(a^.coef,'x^', a^.grad,' +'); a:=a^.urm end; writeln(#8,' '); end;

39

procedure aduna(p,q:lista;var r:lista); var a,b,c,d:lista; begin

a:=p;b:=q; {c este adresa ultimului nod pentru lista suma} while (anil) and (bnil) do

if a^.grad=b^.grad then begin if r=nil then begin

new(c);c^.grad:=a^.grad; c^.coef:=a^.coef +b^.coef; r:=c; r^.urm:=nil; end

else begin new(d); d^.grad:=a^.grad; d^.coef:=a^.coef+b^.coef; c^.urm:=d;c:=d;c^.urm:=nil end;

a:=a^.urm;b:=b^.urm; end

else if a^.grad

40

if anil then c^.urm:=a; if bnil then c^.urm:=b;

end; begin

creare(p);creare(q);listare(p);listare(q); r:=nil; aduna(p,q,r); listare(r); readln;

end. Exerciii: 1. S se implementeze n C aplicaia de mai sus. 2. S se scrie un subprogram pentru calcularea produsului a dou

polinoame rare. 3. S se calculeze valoarea unui polinom ntr-un punct dat. Indicaie: Calcularea produsului se va face prin parcurgerea tuturor perechilor de termeni astfel: -fiecare pereche genereaz un nod n polinomul produs -gradul noului nod va fi suma gradelor nodurilor din pereche -coeficientul noului nod va fi produsul coeficienilor termenilor din pereche -se elimin nodurile din lista de termeni prin pstrarea fiecrui grad o singur dat astfel: dac exist dou noduri cu acelai grad unul din ele va fi eliminat, iar coeficientul celuilalt va avea valoarea sumei coeficienilor celor doi termeni.

Valoarea unui polinom se va calcula prin parcurgerea listei i adugnd la valoare produsul dintre coeficient i valoarea dat la puterea gradului din nod. 4.Dndu-se dou liste simplu nlnuite cu elemente numere intregi distincte, s se afiseze diferena celor dou liste i elementele comune celor dou liste. Rezolvare:

Diferena celor dou liste conine elementele primeia care nu sunt n cea de-a doua. Se parcurge prima list i pentru fiecare nod se verific dac este n cea de-a doua list, dac nu se afl atunci se adaug listei trei. Intersecia celor dou liste se determin parcurgnd

41

prima list i pentru fiecare nod se verific dac elementul se afl i n cea de-a doua list, dac da atunci se adaug n cea de-a treia list. Implementare Pascal: type lista=^nod;

nod = record inf:integer; urm:lista end; var q,cap1,cap2,cap3:lista;

gasit:boolean; procedure creare(var cap:lista); var n,i:integer;

nou,q:lista; begin

write('nr elem'); read(n); new(cap); read(cap^.inf); cap^.urm:=nil; for i:=2 to n do begin

new(nou); read(nou^.inf); nou^.urm:=nil; q:=cap; while q^.urmnil do q:=q^.urm; q^.urm:=nou end end; procedure diferenta(cap1,cap2:lista); var x:integer;

q2:lista; begin

q:=cap1; while qnil do begin

x:=q^.inf; gasit:=false; q2:=cap2; while q2nil do begin if q2^.inf=x then gasit:=true; q2:=q2^.urm end; if not gasit then write(x, ' '); q:=q^.urm end end; procedure afisare(cap:lista); var q:lista; begin

q:=cap; while qnil do begin write(q^.inf,' '); q:=q^.urm end;

writeln; end;

42

procedure intersectie(cap1,cap2:lista; var cap3:lista); var q,q2,nou,q3:lista;

x:integer; begin

q:=cap1; while qnil do begin

x:=q^.inf; gasit:=false; q2:=cap2; while q2nil do begin if q2^.inf=x then gasit:=true; q2:=q2^.urm; end; if gasit then if cap3=nil then

begin new(cap3); cap3^.inf:=x; cap3^.urm:=nil end else begin new(nou); nou^.inf:=x ; nou^.urm:=nil; q3:=cap3;

while q3^.urm nil do q3:=q3^.urm; q3^.urm:=nou end; q:=q^.urm end end; begin creare(cap1); creare(cap2); afisare(cap1); afisare(cap2); diferenta(cap1,cap2); writeln; diferenta(cap2, cap1); writeln('intersectie'); intersectie(cap1,cap2,cap3); afisare(cap3); end. Exerciiu: S se implementeze aplicaia de mai sus in C. 5. S se creeze o list simplu nlnuit, cu informaie numeric astfel nct la orice moment al inserrii lista s fie ordonat cresctor dup informaie. Rezolvare: Paii: -crearea unui nod nou -dac informaia care se adaug este mai mic dect informaia din capul listei atunci se insereaz n faa primului nod -altfel se parcurge lista pn la primul nod a crei informaie este mai mare dect informaia noului nod i se insereaz.

43

Implementare C: #include #include #include

typedef struct nod { int inf; struct nod*urm;} lista; lista *prim; lista *creare(void); void parcurgere(lista *p);

void main(){ lista *prim; prim=creare(); parcurgere(prim);

} lista *creare(){ int n,inf; lista *prim,*p,*q,*nou; printf("nr. de elemente");scanf("%d",&n); prim=NULL; for(int i=1;iinf=inf; if (prim==NULL){

prim=nou;prim->urm=NULL; }

else if (prim->inf>inf){ nou->urm=prim;prim=nou; }

else { p=q=prim;

while(p&&p->infurm;} if (p) {q->urm=nou; nou->urm=p;} else{q->urm=nou; nou->urm=NULL;} }

} return prim; } void parcurgere(lista *p){ lista *q; for (q=p;q;q=q->urm) printf("%d ",q->inf); }

44

Exerciiu: S se implementeze aplicaia de mai sus n Pascal. 6. S se scrie un program pentru interclasarea a dou liste ordonate simplu nlnuite. Rezolvare: Se va parcurge simultan cele dou liste urmnd ca introducerea unui nod n lista final s fie fcut din lista care are valoarea informaiei din nod mai mic. Implementare C: #include #include #include typedef struct nod {int inf; struct nod*urm;}lista; lista *inter(lista *prim1, lista*prim2){ lista *prim,*ultim; if (prim1->inf>prim2->inf){

prim=prim2;prim2=prim2->urm; }

else { prim=prim1; prim1=prim1->urm; }

ultim=prim; while(prim1&&prim2)

if (prim1->inf>prim2->inf){ ultim->urm=prim2;

ultim=prim2; prim2=prim2->urm; }

else {ultim->urm=prim1; ultim=prim1;

prim1=prim1->urm; }

if (prim1) ultim->urm=prim1; else ultim->urm=prim2; return prim; } lista *creare(void); void parcurgere(lista *p);

45

void main(){ lista *prim1,*prim2,*prim; prim1=creare(); prim2=creare(); /* parcurgere(prim1) */; prim=inter(prim1,prim2); parcurgere(prim1);

} lista *creare(){

int n,inf; lista *prim,*p,*q,*nou; printf("nr. de elemente");scanf("%d",&n); prim=NULL; for(int i=1;iinf=inf; if (prim==NULL){

prim=nou; prim->urm=NULL; }

else if (prim->inf>inf){ nou->urm=prim;prim=nou; }

else { p=q=prim;

while(p&&p->infurm;} if(p) {q->urm=nou;nou->urm=p;} else {

q->urm=nou;nou->urm=NULL; }

} }

return prim; } void parcurgere(lista *p){ lista *q; for (q=p;q;q=q->urm) printf("%d ",q->inf); } Exerciiu: S se implementeze aplicaia de mai sus n limbajul Pascal.

2.2. Liste dublu nlnuite Pentru liste duble create dinamic modul de definire a unui nod este:

Limbajul Pascal type lista=^nod; nod=record inf:tip; urm, ant:lista; end;

typedef struct nod{ inf tip; struct nod *urm; struct nod *ant; }lista;

Operaiile care se pot defini asupra listelor dublu nlnuite sunt aceleai ca i n cazul listelor simplu nlnuite: - crearea unei liste dublu nlnuite; - accesul la un element al unei liste dublu nlnuite; - inserarea unui nod ntr-o list dublu nlnuit; - tergerea unui nod dintr-o list dublu nlnuit; - tergerea unei liste dublu nlnuite. Probleme rezolvate 1. S se scrie un program care va conine un meniu cu principale operaii asupra listei dublu nlnuite. Implementarea Pascal a soluiei: type lista=^nod; nod=record inf:integer; urm,ant:lista end; var cap:lista;

x:integer; procedure creare(var cap:lista); begin new(cap); write('inf=');readln(cap^.inf); cap^.urm:=nil;cap^.ant:=nil; end; procedure adaugare(var cap:lista); var q,nou:lista; begin new(nou);readln(nou^.inf);nou^.urm:=nil; q:=cap; while q^.urm nil do q:=q^.urm; q^.urm:=nou;nou^.ant:=q; end;

46

47

procedure inserare(var cap:lista); var nou,q:lista;

k,i:integer; begin

writeln('unde inserezi? '); read(k);new(nou); write('ce? ');readln(nou^.inf); if k=1 then begin

cap^.ant:=nou; nou^.urm:=cap; nou^.ant:=nil; cap:=nou; end

else begin q:=cap; i:=1; while (q^.urmnil) and (i

48

if i=k then begin q:=p; p^.ant^.urm:=p^.urm;

p^.urm^.ant:=p^.ant; dispose(q); end

else begin write('nu exista'); readln end end

end; procedure parcurgere(var cap:lista); var q:lista; begin q:=cap; while qnil do begin write(q^.inf, ' '); q:=q^.urm end; readln end; procedure parcurgere_inv(var cap:lista); var q:lista; begin q:=cap; while q^.urmnil do q:=q^.urm; while qnil do begin write(q^.inf, ' '); q:=q^.ant end; readln; end; begin while x 7 do begin

writeln('1.creare'); writeln('2.adaugare'); writeln('3.inserare'); writeln('4.stergere'); writeln('5.parcurgere'); writeln('6.parcurgere_inv'); writeln('7.iesire'); readln(x); case x of

1:creare(cap); 2:adaugare(cap); 3:inserare(cap); 4:stergere(cap); 5:parcurgere(cap); 6:parcurgere_inv(cap); end

end end.

49

2. Crearea i parcurgerea listei dublu nlnuite n limbajul C: #include #include typedef struct nod{int inf; struct nod*urm,*ant; } lista; lista*prim ,*ultim; void creare(int n); void parcurg(lista*prim); void parcurg1(lista*ultim); void main(){

int n; printf("numarul de elemente:");scanf("%d",&n); creare(n); puts("\n Parcurgere directa");parcurg(prim); puts("\n Parcurgere indirecta");parcurg1(ultim); }

void creare(int n){ int i; lista *p; prim=(lista*)malloc(sizeof(lista)); printf("informatia primului nod"); scanf("%d",&prim->inf); prim->urm=prim->ant=NULL; ultim=prim; for(i=2;iinf); p->ant=ultim;ultim->urm=p;

p->urm=NULL; ultim=p;

} } void parcurg(lista*p){ if (p){

printf("%d ",p->inf); parcurg(p->urm); }

} void parcurg1(lista *p){ lista *q; for (q=p;q;q=q->ant) printf("%d ",q->inf); }

50

2.3. Liste circulare Dup numrul de legturi, listele circulare se mpart n: liste simple i liste duble. Listele circulare simple sunt liste simple care au n plus propietatea c valoarea cmpului urmtor a ultimului nod este adresa capului listei. Listele circulare duble sunt liste duble care au propietatea c legtura urmtor a celui de-al doilea cap este primul cap i legtura anterior a primului cap este al doilea cap. Crearea i parcurgerea listei circulare simplu nlnuite n limbajul C: #include #include #include typedef struct nod{ int inf; struct nod *urm;}lista; void main(){

lista *prim,*p,*q; int i,n; /*crearea listei circulare*/ printf("inf primului nod"); prim=(lista*)malloc(sizeof(lista)); scanf("%d",&prim->inf);prim->urm=NULL; p=prim; printf("nr de elemente");scanf("%d",&n); for (i=2;iinf); p->urm=q;p=q; }

p->urm=prim; /*parcurgerea listei*/ printf("%d ",prim->inf); for (q=prim->urm;q!=prim;q=q->urm) printf("%d ",q->inf);

} Problem rezolvat: Se d un grup de n copii aezai n cerc, care sunt numrai din m n m. Copilul care a fost numrat cu valoarea m este eliminat. Dndu-se pasul de eliminare m se cere s se precizeze ordinea ieirii din cerc.

51

Rezolvare: Simularea eliminrii copiilor se realizeaz cu o list circular la care se realizeaz eliminarea nodului care are ca informaie numrul copilului scos din joc. Numrarea se va face parcurgnd m elemente de la poziia de unde s-a efectuat ultima tergere. Implementarea Pascal (Lista circular este simpl.) type lista=^nod; nod=record inf:integer; urm:lista end; var i,n,m,j:integer;

prim,q,p:lista; procedure creare(var prim:lista;x:integer); begin new(prim); prim^.inf:=x; prim^.urm:=prim end; procedure adaugare(var prim:lista;x:integer); var q,p:lista; begin

new(q); q:=prim; while q^.urmprim do q:=q^.urm; new(p); p^.inf:=x; q^.urm:=p;p^.urm:=prim;

end; procedure listare(prim:lista); var q:lista; begin new(q);q:=prim; write(q^.inf,' '); while q^.urmprim do begin q:=q^.urm; write(q^.inf,' ') end; end; begin {program principal} read(n); creare(prim,1); for i:=2 to n do adaugare(prim,i); listare(prim); read(m); p:=prim; for i:=1 to n-1 do begin

if i=1 then for j:=1 to m-2 do p:=p^.urm else for j:=1 to m-1 do p:=p^.urm;

q:=p^.urm; write(q^.inf,' '); p^.urm:=q^.urm; dispose(q); end; writeln('castigator=',p^.inf); end.

52

Implementarea C (Lista circular este dubl). #include #include typedef struct nod{int inf; struct nod *urm,*ant; }lista;

lista *prim,*p,*q; void creare(void); void parcurgere(void); int n,m,i,k;

void main(){ creare(); printf("pasul de numarare");scanf("%d",&m); parcurgere(); while (p!=p->ant){

for( i=1;iurm; printf("%d ",p->inf); p->ant->urm=p->urm; p->urm->ant=p->ant; q=p;p=p->urm;free(q); }

printf("%d",p->inf); } void parcurgere(){ for (p=prim,i=1;iurm) printf("%d",p->inf); /* p=p->urm;*/ } void creare(){ printf("nr. de copii");scanf("%d",&n); prim=(lista*)malloc(sizeof(lista));prim->inf=1; prim->urm=prim->ant=NULL; p=prim; for (i=2; iinf=i; p->urm=q; q->ant=p; p=q; }

q->urm=prim;prim->ant=q; }

2.4. Stive

O stiv (stack) este o list liniar cu proprietatea c operaiile de inserare/extragere a nodurilor se fac n/din vrful listei. Ultimul nod inserat va fi i primul ters, stivele se mai numesc i liste LIFO (eng. Last In First Out) sau liste pushdown.

53

Cel mai natural mod de reprezentare pentru o stiv este implementarea secvenial ntr-un tablou S[1 .. n], unde n este numrul maxim de noduri. Primul nod va fi memorat n S[1], al doilea n S[2], iar ultimul n S[top], unde top este o variabil care conine adresa (indicele) ultimului nod inserat. Algoritmii de inserare i de tergere (extragere) a unui nod:

pop

push

function push(x, S[1 .. n])

{adauga nodul x in stiva} if top = n then return stiva plina top top+1 S[top] x

return succes function pop(S[1 .. n])

{sterge ultimul nod inserat din stiva si il returneaza} if top =0 then return stiva vida x S[top] top top-1

return x Cei doi algoritmi necesit timp constant, deci nu depind de mrimea stivei.

54

Problem rezolvat: Realizai un meniu n limbajul Pascal care s conin operaii asupra stivei. Rezolvare: Implementarea Pascal: type stiva=^nod; nod=record inf:integer; urm:stiva end; var cap:stiva; x:integer; procedure adauga(var cap:stiva); var nou:stiva; begin

new(nou); writeln('Ce sa adaug? '); readln(nou^.inf); nou^.urm:=nil; if cap=nil then cap:=nou

else begin nou^.urm:=cap;

cap:=nou; end;

end; procedure sterge(var cap:stiva); var q:stiva; begin if cap=nil then writeln('Stiva vida')

else begin q:=cap; cap:=cap^.urm; dispose(q) end;

end; procedure parcurgere(cap:stiva); var q:stiva; begin

q:=cap; while q nil do begin

writeln('|',q^.inf,'|'); q:=q^.urm end; writeln('___')

end;

55

begin while x 4 do begin

writeln('1.Adaugare'); writeln('2.Stergere'); writeln('3.Listare'); writeln('4.Iesire'); writeln('Dati optiunea'); readln(x); case x of

1:adauga(cap); 2:sterge(cap); 3:parcurgere(cap)

end end

end. Exerciiu: S se implementeze n limbajul C aplicaia de mai sus. Probleme propuse

1. S se scrie un program care citind numere ntregi din fiierul in.txt creeaz o stiv i o afieaz. S se transforme un numr din baza 10 n baza b folosind o stiv.

2. Pe o linie de cale ferat se gsesc, ntr-o ordine oarecare, n vagoane numerotate de al 1 la n. Linia continu cu alte k linii de manevr. Cunoscnd ordinea iniial a vagoanelor, s se obin la ieire vagoanele n ordine: 1,2 ,n; liniile de manevr sunt destul de lungi nct s ncap pe o singur linie toate cele n vagoane.

Indicaie: Se dorete partiionarea vagoanelor n k submulimi care au vagoanele ordonate cresctor 2.5. Cozi O coad (eng. queue) este o list liniar n care inserrile se fac doar n capul listei, iar extragerile doar din coada listei. Cozile se numesc i liste FIFO (eng. First In First Out). O reprezentare secvenial pentru o coad se obine prin utilizarea unui tablou C[0 .. n-1], pe care l tratm ca i cum ar fi circular: dup locaia C[n-1] urmeaz locaia C[0]. Fie p variabila care conine indicele locaiei predecesoare primei locaii ocupate i fie u variabila care conine indicele locaiei ocupate ultima oar. Variabilele p i u au aceeai valoare atunci i numai

56

atunci cnd coada este vid. Iniial, avem p= u= 0. Inserarea i tergerea (extragerea) unui nod necesit timp constant. Operaii asupra cozii: function insert-queue(x, C[0 .. n-1])

{adauga nodul x in capul cozii} p (p+1) mod n if p=u then return coada plina C[p] x

return succes function delete-queue(C[0 .. n-1])

{sterge nodul din coada listei si il returneaza} if p=u then return coada vida u (u+1) mod n x C[u]

return x Testul de coad vid este acelai cu testul de coad plin. Dac s-ar folosi toate cele n locaii, atunci nu am putea distinge situaia de coad plina i cea de coad vid, deoarece n ambele situaii am avea p = u. Se folosesc efectiv numai n-1 locaii din cele n ale tabloului C, deci se pot implementa astfel cozi cu cel mult n-1 noduri. Problem rezolvat: Relizarea unui meniu pentru implementarea static a cozii. Rezolvare: Cea mai simpl implementare a cozii static este folosirea unui tablou. Pentru gestionarea cozii este nevoie de dou elemente: p poziia primului element i u poziia de dup ultimul element din coad. Se va face o utilizare circular a spaiului alocat astfel: urmtoarea poziie este p mod n +1. Implementarea Pascal: TYPE coada=array[1..50] of integer; var c:coada; p,n,u,o,x:integer; procedure adaugare(var c:coada; var p,u:integer;x:integer); begin

if p(u mod n)+1 then begin c[u]:=x; u:=u mod n +1 end

else writeln('coada plina'); end;

57

procedure stergere(var c:coada; var p,u,x:integer); begin if pu then begin x:=c[p]; p:=p mod n+1 end else writeln('coada goala'); end; procedure listare(c:coada;p,u:integer); var i:integer; begin if p=u then writeln('coada goala') else begin i:=p; while iu do begin write(c[i],' '); i:=i mod n+1 end; end; end; begin

writeln('nr max de elem'); read(n);n:=n+1; p:=1;u:=1; repeat

writeln('1..adaugare'); writeln('2..stergere'); writeln('3..listare'); write('citeste optiunea');readln(o); case o of

1: begin write('introduceti numarul adaugat');readln(x);

adaugare(c,p,u,x); end;

2: begin stergere(c,p,u,x); if pu then writeln(x); end;

3: listare(c,p,u); end;

writeln; until o=4;

end. Exerciiu: S se implementeze aplicaia de mai sus n limbajul C++.

58

Problem rezolvat: S se creeze un program care s conin un meniu cu operaii asupra unei cozi alocate dinamic. Rezolvare: Implementarea n limbajul C++: #include #include #include // intrri-ieiri n C++ typedef struct nod {int inf; struct nod *urm; }lista; void adaug(lista* &prim, int x){

lista *nou, *p; nou=new lista; // crearea unui nod n C++ nou->inf=x;nou->urm=NULL; if (prim==NULL) prim=nou;

else { nou->urm=prim; prim=nou; }

} lista * creare(){

int n,x; lista*prim; prim=NULL; clrscr(); coutn; for (int i=0;i

59

void sterg(lista *&prim){ lista *p; if (prim==NULL) couturm!=NULL){p=p->urm;} delete p->urm; p->urm=NULL;

} } void main(){

lista *prim=NULL; int opt,x; do{

clrscr(); cout

60

Exerciiu: S se realizeze programul n Pascal corespunztor aplicaiei de mai sus. Probleme propuse: 1. Fiind dat o list simplu nlnuit avnd informaii numere ntregi

s se elimine numerele negative. 2. S se realizeze interclasarea a n liste simplu nlnuite ordonate

cresctor. 3. Fiind date dou liste simple cu informaii de tip ntreg, s se

realizeze subprograme pentru urmtoarele operaii: intersecia, reuniunea, diferena i diferena simetric a elementelor celor dou liste.

4. S se scrie un program care citete cuvintele dintr-un fiier text in.txt, cuvintele sunt separate prin spaii i afieaz numrul de apariii al fiecrui cuvnt din fiier. Se vor folosi liste simplu nlnuite.

5. S se elimine dintr-o list simplu nlnuit toate nodurile care au o informaie dat.

6. S se realizeze operaii cu matrici rare folosind alocarea dinamica. 7. Fiind dat o list dubl, s se separe n dou liste elementele de pe

poziii pare de elementele de pe poziii impare. 8. Fiind dat o list dubl cu informaii de tip ir de caractere, s se

fac ordonarea elementelor listei. 9. Fiind dat o list dubl cu informaii de tip ntreg s se

construiasc o list dubl numai cu elemente prime. 10. Pe o tij sunt n bile colorate cu cel mult k culori, fiecare bil

avnd o etichet cu un numr de la 1 la n. S se mute bilele pe alte k tije, pe fiecare punnd numai bile din aceeai culoare. S se afieze bilele de pe fiecare din cele k tije, folosind structuri dinamice.

Indicaie: Tija iniial reprezint o stiv, informaia dintr-un nod va fi compus din numrul bilei i numrul culorii. Se va parcurge stiva i se adaug n stiva corespunztoare culorii, apoi se terge din stiva iniial. Se va lucra cu un vector de stive pentru cele k tije. 11. S se implementeze subprograme pentru operaiile de baz cu liste

circulare duble. 12. Fie un traseu circular ce cuprinde n orae. O main trebuie s

parcurg toate oraele i s se ntoarc de unde a plecat. Parcurgerea se poate face n ambele sensuri. Se cere s se

61

determine un traseu posibil de parcurgere astfel nct s nu rmn n pan tiind c n fiecare ora exist o staie de benzin cu o cantitate de benzin suficient, iar maina consuma c litri la 100 de kilometri.

13. Fiind dat o list circular dubl, s se fac un subprogram de inserare a unui element pe o poziie dat.

14. S se realizeze un subprogram care terge elementele egale cu zero dintr-o list circular.

15. S se creeze o list de liste, s se parcurg i s se tearg. 16. S se scrie un program care citete cuvintele dintr-un text i

afieaz numrul de apariii al fiecrui cuvnt din textul respectiv. 17. S se scrie un program care citete cuvintele dintr-un text i scrie

numrul de apariie al fiecrui cuvnt, n ordinea alfabetic a cuvintelor respective.

18. ntr-o gar se consider un tren de marf ale crui vagoane sunt inventariate ntr-o list. Lista conine, pentru fiecare vagon, urmtoarele date: codul vagonului, codul coninutului vagonului, adresa expeditorului, adresa destinatarului. Deoarece n gar se inverseaz poziia vagoanelor, se cere listarea datelor despre vagoanele respective n noua lor ordine.

Indicaie: se creeaz o stiv n care se pstreaz datele fiecrui vagon. Datele corespunztoare unui vagon constituie un element al stivei, adic un nod al listei simplu nlnuite. Dup ce datele au fost puse n stiv, ele se scot de acolo i se listeaz. 19. La o agenie CEC exist un singur ghieu care se deschide la ora 8

i se nchide la ora 16, dar publicul aflat la coad este deservit n continuare. Deoarece la ora nchiderii coada este destul de mare se ridic problema oportunitii deschiderii a nc unui ghieu la agenia respectiv. Se cunosc operaiile efectuate la agenie i timpul lor de execuie. n acest scop se realizeaz o simulare pe calculator a situaiei existente care s stabileasc o medie a orelor suplimentare efectuate zilnic pe o perioad de un an.

Indicaie: Programul de simulare a problemei indicate construiete o coad de ateptare cu persoanele care sosesc la agenie n intervalul de timp indicat. Se va folosi funcia random pentru a determina operaia solicitat i apoi pentru a determina intervalul de timp ntre dou persoane care vin la agenie.

62

20. S se realizeze un program care implementeaz subprograme pentru crearea i exploatarea unei cozi duble.

21. Se d o matrice rar memorat ntr-o list. Se cere: a) s se afieze toate elementele diferite de zero de pe diagonala principal, secundar; b) s se afieze pe ecran matricea sub forma obinuit, fr reconstituirea ei n memorie.

2.6. Grafuri Noiuni introductive Un graf este o pereche G = , unde V este o mulime de vrfuri, iar M = VxV este o mulime de muchii. O muchie de la vrful a la vrful b este notat cu perechea ordonat (a, b), dac graful este orientat, i cu mulimea {a, b}, dac graful este neorientat. Dou vrfuri unite printr-o muchie se numesc adiacente. Un drum este o succesiune de muchii de forma (a1, a2), (a2, a3), ..., (an-1, an) sau de forma {a1, a2}, {a2, a3}, ..., {an-1, an} dup cum graful este orientat sau neorientat. Lungimea drumului este egal cu numrul muchiilor care l constituie. Un drum simplu este un drum n care nici un vrf nu se repet. Un ciclu este un drum care este simplu, cu excepia primului i ultimului vrf, care coincid. Un graf aciclic este un graf fr cicluri. Un subgraf al lui G este un graf , unde V' V, iar M' este format din muchiile din M care unesc vrfuri din V'. Un graf parial este un graf

uneori valori, iar muchiilor li se pot ataa informaii numite uneori lungimi sau costuri. Metode de reprezentare a grafurilor a) Matricea de adiacen Cea mai cunoscut metod de memorare a grafurilor neorientate este matricea de adiacen, definit n felul urmtor: 1, dac exist muchie (arc) de la vrful i la vrful j i 0, n caz contrar. n cazul grafurilor neorientate, aceast matrice este simetric, folosindu-se efectiv numai jumtate din spaiul matricei. n unele probleme este eficient ca cealalt jumtate a matricei s fie folosit pentru reinerea altor informaii. Matricea de adiacen este folosit n general pentru grafuri cu un numr mic de noduri, deoarece dimensiunea ei este limitat de dimensiunea stivei. Exemplu de graf orientat:

0 0 1 0 0 1 0 00 0 0 0 0 0 1 00 0 0 0 0 0 1 00 0 0 0 1 0 0 00 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 10 0 0 0 0 0 0 0

0 1 2 3 4 5 6 701234

7

56

00000

1

00

8

0 0 0 0 0 0 0 08 0

1

4

5

6

3

2

8

7

0

b) Listele de muchii Aceast metod de memorare presupune reinerea unei matrice cu 2 linii i m coloane, pe fiecare coloan fiind reinute dou extremiti ale unei muchii. Aceasta reprezentare este eficient atunci cnd avem de examinat toate muchiile grafului.

63

64

Listele de muchii sunt folosite n cazul algoritmilor care prelucreaz secvenial muchiile, cum ar fi de exemplu algoritmul Kruskal de aflare a arborelui parial de cost minim n cazul grafurilor rare (cu numr mic de muchii). c) Listele de vecini. Prin liste de vecini (adiacen) se realizeaz ataarea la fiecare vrf i a listei de vrfuri adiacente lui (pentru grafuri orientate, este necesar ca muchia s plece din i). ntr-un graf cu m muchii, suma lungimilor listelor de adiacen este 2m, dac graful este neorientat, respectiv m, dac graful este orientat. Dac numrul muchiilor n graf este mic, aceast reprezentare este preferabil din punct de vedere al memoriei necesare. Este posibil s examinm toi vecinii unui vrf dat, n medie, n mai puin de n operaii. Pe de alt parte, pentru a determina dac dou vrfuri i i j sunt adiacente, trebuie s analizm lista de adiacen a lui i (i, posibil, lista de adiacen a lui j), ceea ce este mai puin eficient dect consultarea unei valori logice n matricea de adiacen. Listele de vecini sunt cele mai recomandate n tratarea algoritmilor din teoria grafurilor din dou motive principale: 1. spatiul folosit este gestionat dinamic, putndu-se memora astfel

grafuri de dimensiuni mari; 2. complexitatea optim pentru majoritatea algoritmilor fundamen-

tali din teoria grafurilor (parcurgeri, conexitate, muchii i puncte critice, algoritmi de drum minim etc.) este obinut numai folosind liste de vecini.

Exist dou modaliti de implementare a listelor de vecini. a) Prima dintre ele folosete o matrice T cu 2 linii i 2m coloane i

un vector C cu n elemente care reine pentru fiecare nod indicele coloanei din T pe care este memorat primul element al listei nodului respectiv (sau 0 dac vrful respectiv nu are vecini). Apoi, pentru o anumit coloan i din T, T(i,1) reine un element din lista curent, iar T(i,2) reine coloana pe care se gsete urmtorul element din lista respectiv sau 0 dac lista s-a terminat.

b) Cea de-a doua implementare folosete pentru fiecare nod o list simplu nlnuit memorat n heap. Pentru fiecare list este suficient s pstrm o singur santinel (cea de nceput a listei), introducerea vrfurilor fcndu-se mereu la nceputul listei (deoarece ordinea vrfurilor n list nu conteaz).

Exemplu:

65

1

4

5

6

3

2

8

7

0

01234

7

56

8

2 5

6

6

4

5

3 7

2 8

Parcurgerea grafurilor

Parcurgerea unui graf presupune examinarea n vederea prelucrrii tuturor vrfurilor acelui graf ntr-o anumit ordine, ordine care s permit prelucrarea optim a informaiilor ataate grafului.

a) Parcurgerea DF (parcurgerea n adncime) Parcurgerea DF (Depth First) presupune ca dintr-un anumit nod v, parcurgerea s fie continuat cu primul vecin al nodului v nevizitat nc. Parcurgerea n adncime a fost formulat cu mult timp n urm ca o tehnic de explorare a unui labirint. O persoan care caut ceva ntr-un labirint i aplic aceast tehnic are avantajul ca urmtorul loc n care caut este mereu foarte aproape.

Parcurgerea vrfurilor n adncime se face n ordinea: 1 3 4 5 2 6 1

4

56

3

2Cel mai cunoscut mod de imple-

mentare a parcurgerii DF se realizeaz cu ajutorul unei funcii recursive, dar exist i cazuri n care este recomandat o implementare nerecursiv.

Implementarea acestei metode se face folosind o stiv. Aceasta este iniia-

66

lizat cu un nod oarecare al grafului. La fiecare pas, se ia primul vecin nevizitat al nodului din vrful stivei i se adaug n stiv dac nu mai exist se coboar n stiv. Algoritmul recursiv: procedure DF(G) for fiecare v V do marca[v] nevizitat for fiecare v V do if marca[v] = nevizitat then ad(v) procedure ad(v) {varful v nu a fost vizitat} marca[v] vizitat for fiecare virf w adiacent lui v do if marca[w] = nevizitat then ad(w) Algoritmul iterativ: procedure iterad(v) S stiva vida marca[v] vizitat push(v, S) while S nu este vida do while exista un varf w adiacent lui ftop(S) astfel incat marca[w] = nevizitat do marca[w] vizitat push(w, S) pop(S) unde funcia ftop returneaz ultimul vrf inserat n stiv.

Parcurgerea n adncime a unui graf nu este unic; ea depinde att de alegerea vrfului iniial, ct i de ordinea de vizitare a vrfurilor adiacente. Problem: Ct timp este necesar pentru a parcurge un graf cu n vrfuri i m muchii? Rezolvare: Deoarece fiecare vrf este vizitat exact o dat, avem n apeluri ale procedurii ad. n procedura ad, cnd vizitm un vrf, testm marcajul fiecrui vecin al su. Dac reprezentm graful prin liste de adiacen, adic prin ataarea la fiecare vrf a listei de vrfuri adiacente lui, atunci numrul total al acestor testri este m, dac graful este orientat,

67

i 2m, dac graful este neorientat. Algoritmul necesit un timp O(n) pentru apelurile procedurii ad i un timp O(m) pentru inspectarea mrcilor. Timpul de executare este O(max(m, n)) = O(m+n).

Dac reprezentm graful printr-o matrice de adiacen, se obine un timp de executare de O(n2). b) Parcurgerea BF (parcurgerea n lime) Parcurgerea BF (Breath First) presupune faptul c dup vizitarea unui anumit nod v, sunt parcuri toi vecinii nevizitai ai acestuia, apoi toi vecinii nevizitai ai acestora din urm, pn la vizitarea tuturor nodu-rilor grafului.

Parcurgerea n lime este folosit de obicei atunci cnd se exploreaz parial anumite grafuri infinite, sau cnd se caut cel mai scurt drum dintre dou vrfuri.

Implementarea acestei metode se face folosind o coad. Aceasta este iniializat cu un nod oarecare al grafului. La fiecare pas, se viziteaz nodul aflat n vrful cozii i se adaug n coad toi vecinii nevizitai ai nodului respectiv.

Parcurgere_BF(nod start) Coada start Vizitat(start) adevrat ct timp coada nu este vid ic nodul de la nceputul cozii adaug toti vecinii nevizitati ai lui ic n coad Vizitat(i) adevrat, unde i este un vecin nevizitat al nodului ic

Pentru a efectua o parcurgere n laime a unui graf (orientat sau neorientat), aplicm urmtorul principiu: atunci cnd ajungem ntr-un vrf oarecare v nevizitat, l marcm i vizitm apoi toate vrfurile nevizitate adiacente lui v, apoi toate vrfurile nevizitate adiacente vrfurilor adiacente lui v etc. Spre deosebire de parcurgerea n adncime, parcurgerea n lime nu este n mod natural recursiv. procedure lat(v) C coada vida marca[v] vizitat insert-queue(v, C)

68

while C nu este vida do u delete-queue(C) for fiecare virf w adiacent lui u do if marca[w] = nevizitat then marca[w] vizitat insert-queue(w, C) Pentru compararea celor dou metode apelm procedurile iterad i lat din procedura parcurgere(G) procedure parcurge(G) for fiecare v V do marca[v] nevizitat for fiecare v V do if marca[v] = nevizitat then {iterad sau lat} (v) Aplicaia 2.6.1: Algoritmul lui Dijkstra Fie G = (X,U) un graf orientat, unde X este mulimea vrfurilor i U este mulimea muchiilor. Fiecare muchie are o lungime nenegativ. Unul din vrfuri este desemnat ca vrf surs. Problema este s determinm lungimea celui mai scurt drum de la surs ctre fiecare vrf din graf. Vom folosi un algoritm greedy, datorat lui E.W. Dijkstra (1959). Notm cu C mulimea vrfurilor disponibile (candidaii) i cu S mulimea vrfurilor deja selectate. n fiecare moment, S conine acele vrfuri a cror distan minim de la surs este deja cunoscut, n timp ce mulimea C conine toate celelalte vrfuri. La nceput, S conine doar vrful surs, iar n final S conine toate vrfurile grafului. La fiecare pas, adugam n S acel vrf din C a crui distan de la surs este cea mai mic.

La fiecare pas al algoritmului, un tablou D conine lungimea celui mai scurt drum special ctre fiecare vrf al grafului. Dup ce adugm un nou vrf v la S, cel mai scurt drum special ctre v va fi, de asemenea, cel mai scurt dintre toate drumurile ctre v. Cnd algoritmul se termin, toate vrfurile din graf sunt n S, deci toate drumurile de la surs ctre celelalte vrfuri sunt speciale i valorile din D reprezint soluia problemei.

Matricea M d lu