Programarea calculatoarelor
AxeL
Rezolvarea problemelor cu ajutorul calculatorului reprezintă astăzi
nu numai o necesitate obiectivă ci un mod de supravieţuire, în
condiţiile în care, volumul de informaţii şi viteza cu care ele se
derulează sunt din ce în ce mai mari.
Este de înţeles faptul că nu oricine poate să programeze un
calculator astfel încât acesta să “facă ce vreau eu”. Pentru
acest lucru sunt necesare, pe lângă bune cunoştinţe de matematică,
logică şi informatică, abilităţi şi aptitudini de a aborda
problemele în mod specific. Programarea calculatoarelor este de fapt o
artă, care, ca orice lucru de cultură se cultivă, se dezvoltă şi
se perfecţionează continuu.
Acest curs are rolul de a fundamenta şi de a dezvolta cunoştinţele
dobândite şi cultivate în cadrul cursului de elaborare a
algoritmilor. Se urmăreşte modelarea unor principii ale programării
calculatoarelor, dezvoltarea şi însuşirea unor metode şi tehnici
specifice prelucrării anumitor tipuri de date respectiv anumitor
tipuri de structuri de date şi clase de probleme, împreună cu
formarea uni stil în programare apropiat de cerinţele practice ale
construcţiei de soft.
Principalele aspecte sunt legate de metodele clasice şi evoluate de
sortare, căutare, interclasare şi parcurgere pe clase şi structuri
de date specifice. Unele dintre acestea au fost prezentate pe scurt şi
în cursul de algoritmică şi care trebuie revizuite cu atenţie şi
aplicate corect în noile situaţii. Metodele de programare evoluate
tratate în acest curs deschid calea spre rezolvarea optimă a unor
clase de probleme.
Prelucrarea dinamică a datelor prin reprezentarea lor ca liste este
tratată prin exemple şi modele de lucru. Prin varietatea de probleme,
însoţite de soluţii, prezentate în cadrul metodelor de rezolvare a
problemelor şi completarea lor cu alte metode, programarea dinamică,
tehnica branch and bound şi algoritmi specifici grafelor şi
arborilor, cursul încearcă să contureze principalele metode şi
tehnici cunoscute, pe care un programator trebuie să le stăpânească
pentru a putea implementa produse soft de bună calitate.
Recomand în studiul acestui curs utilizarea frecventă a
documentaţiilor menţionate în bibliografie şi bineînţeles a
calculatorului ca unealtă de lucru.
Alba Iulia, 2003
Autorul
II. Principiile programării calculatoarelor
Modalităţile de rezolvare a unei probleme sunt diverse şi depind
atât de tipul problemei cât şi de programator. În general
programarea respectă principiile de programare, respectiv programarea
structurată, programarea modulară, programarea orientată obiect,
etc. funcţie de specificul problemei.
Dezvoltarea de software este un lucru mult mai complex şi mai
complicat. Acesta presupune o serie întreagă de activităţi
distincte în care programarea ocupă un loc bine definit şi se
integrează în lista activităţilor. Aceste activităţi cuprind:
- Definirea problemei
- Analiza cerinţelor
- Construirea planului de implementare
- Definirea detaliilor şi a structurii problemei
- Construcţia, respectiv implementarea
- Integrarea modulelor
- Testarea modulelor
- Testarea sistemului în ansamblu
- Întreţinerea corectivă
- Dezvoltarea funcţională
Intuitiv toate aceste activităţi sunt privite în general ca
„PROGRAMARE”, delimitând aici partea de construcţie (design şi
structură), de transcriere sub formă de cod a activităţilor
(implementare, codificare) şi respectiv ansamblul etapelor de testare
şi întreţinere.
Pornind de la idea că rezolvarea unei probleme presupune cunoaşterea
în totalitate a cerinţelor şi datelor de ieşire, descrierea
corectă a paşilor algoritmilor, forma şi metodele de lucru utilizate
de către programator aparţin exclusiv acestuia. Programarea
industrială presupune însă elaborarea unor coduri după
specificaţii exacte ale altor programatori care au realizat etapa de
construcţie şi arhitectură a programului.
Descrierea programelor, indiferent de limbajul de programare utilizat
presupune respectarea unor principii atât în ceea ce priveşte
descrierea datelor cât şi a paşilor de rezolvare. Aceste principii
se impun din cel puţin următoarele motive:
- Lizibilitatea programului; aspect care presupune aranjarea liniilor
de program astfel încât la citirea, parcurgerea şi verificarea
acestuia să se delimiteze clar secvenţele, structurile şi
instrucţiunile cu modul lor de imbricare şi succesiune. În acest
sens fiecare instrucţiune este scrisă pe câte un rând,
instrucţiunile imbricate se scriu aliniate mai la dreapta faţă de
instrucţiunea “părinte”. Nu se pune problema corectitudinii
algoritmului, el fiind considerat a fi corect.
- Depanarea programului; scrierea programelor pe module mici, în
secvenţe scurte şi clare duce la depistarea uşoară a eventualelor
erori şi totodată la posibilitatea de a verifica uşor corectitudinea
secvenţelor, deci principiul următor:
- Testarea pe module mici presupune testarea programelor îndată ce au
fost elaborate. Fiecare linie nouă de cod adăugată va trebuie
testată pentru a vedea corectitudinea şi situaţiile noi generate de
aceasta;
- Portabilitatea; reprezintă posibilitatea de a implementa programul
pe diverse sisteme şi în diverse configuraţii, eventualele
modificări să permită flexibilitatea modulelor.
- Lucrul în echipă; se cunosc două principii de programare în
echipă:
A) “principiul cutiei negre” care reprezintă totala independenţă
a programatorului în interiorul programului său, legătura cu
exteriorul făcându-se strict pe baza formatului datelor de intrare
şi a celor de ieşire. Sub forma
DATE DE INTRARE DATE DE IEŞIRE
B) “principul cutie transparente”, un principiu modern prin care
se impune respectarea unor reguli interne deci a unui standard vizibil
şi din exteriorul programului.
DATE DE INTRARE program DATE DE IEŞIRE
Respectarea unor principii, reguli, în programarea calculatoarelor
presupune învăţarea corectă, în etape, prin paşi mărunţi a
metodelor de rezolvare a problemelor şi respectarea unor principii
date de experienţa în programare a numeroşi programatori.
Selectăm, din cărţile de specialitate, unele dintre cele mai
frecvent întâlnite sfaturi şi principii ale programării care vă
îndrumă spre ceea ce trebuie şi ceea ce nu trebuie făcut atunci
când doriţi să elaboraţi un program:
1) Defineşte complet problema – definirea completă a unei probleme
presupune cunoaşterea exactă şi în cele mai mici detalii a datelor
de intrare, a cerinţelor problemei precum şi cunoaşterea şi
definirea corectă tuturor noţiunilor care intervin în problemă.
2) Proiectează structurat algoritmii – se elaborează algoritmii
având în vedere secvenţialitatea operaţiilor, posibilitatea de
repetiţie sau de decizie în fiecare etapă.
3) Foloseşte algoritmii existenţi şi tehnica programării modulare
– împărţirea unei probleme în subprobleme şi rezolvarea acestora
folosind algoritmi clasici, cu performanţe deja demonstrate,
uşurează munca de programare şi reduce posibilitatea de eroare în
algoritmi. Utilizarea unor algoritmi neconvenţionali şi aglomerarea
problemelor într-una singură duce la confuzii şi în general la
respingerea programelor astfel elaborate.
4) Foloseşte proiectarea orientată pe obiecte – acest mod de
proiectare permite flexibilitatea atât la nivelul datelor cât şi al
procedurilor.
5) Gândeşte mai întâi, programează pe urmă – în general timpul
alocat elaborării strategiei de rezolvare a unei probleme este cel
puţin dublu faţă de timpul necesar implementării.
6) Detaliile nesemnificative sunt semnificative;
7) Foloseşte comentariile în textul sursă şi utilizează
identificatori sugestivi care să permită şi altor programatori să
interpreteze programul sursă.
8) Asigură portabilitatea programului – prin evitarea folosirii
specificului calculatorului, cum ar fi elemente de afişaj specific
(rezoluţii, plăci grafice, tipuri de interfeţe), transmisie de date
(reţele locale, unităţi de disc specifice), dispozitive periferice
(tipuri de imprimante) şi respectiv medii de programare sau sisteme de
operare.
9) Verifică corectitudinea algoritmului şi a programului în fiecare
etapă a elaborării.
10) Elaborează documentaţia programului odată cu elaborarea sa.
Pe lângă aceste principii se recomandă câteva aspecte care ţin de
prelucrarea datelor în cadrul unui algoritm şi care sunt utile mai
ales celor care fac primii paşi în elaborarea programelor:
- Foloseşte toate variabilele pe care le-ai definit
- Cunoaşte şi respectă tipul şi semnificaţia fiecărei variabile
- Iniţializează variabilele, fie prin citirea lor fie prin atribuirea
unei valori iniţiale.
- Verifică valorile variabilelor imediat după calculul lor.
- Indiferent de metodele de programare utilizate evită să foloseşti
variabile globale. Fiecare modul este bine definit de variabilele sale
locale iar transmiterea valorilor se realizează prin lista de
parametrii.
- Evită artificiile
- Testează programul chiar dacă ai demonstrat corectitudinea sa
pentru mai multe seturi de date de intrare.
- Foloseşte facilităţile de depanare puse la dispoziţie de mediul
de programare (vizualizarea valorilor variabilelor, a stivei de lucru,
a paşilor în execuţia unui program)
III. Structuri de date
1. Noţiuni şi concepte preliminarii
Limbajele de programare dispun de modalităţi de agregare a datelor
care permit apoi tratarea globala a acestora. Este vorba în general de
date care corespund nivelului de abstractizare al limbajului, deci care
nu au corespondent direct în tipurile maşină. Pentru ca aceste date
definite de utilizator conform nevoilor sale concrete sa poată fi
integrate în mecanismul de tipuri al limbajului, acesta din urma pune
la dispoziţia programatorului constructorii de tipuri. în acest
capitol se vor discuta tipurile de date structurate.
Tabelul de mai jos prezintă o clasificare a tipurilor de date
împreună cu modalităţile de organizare a acestora.
Structura Tip de date Număr Componente Tip componente Mod de
organizare
A) simple Numeric Una Numeric Static
Alfanumeric Una Caracter Static
Logic Una Logic Static
B)structurate Tablou Mai multe Acelaşi tip Static
Articol Mai multe Tipuri diferite Static/Dinamic
Fişier Mai multe Acelaşi tip Static
Liste Mai multe Acelaşi tip Static/Dinamic
Pointer Mai multe Tipuri diferite Dinamic
Spre deosebire de datele simple, care sunt atomice, indivizibile,
datele structurate (compuse, agregate) se descompun în componente sau
elemente, fiecare de un tip precizat (simplu sau structurat). O data
structurata poate fi accesată fie ca întreg (global), fie pe
componente. Structura unei date stabileşte relaţiile care există
între componentele acesteia.
Exista patru tipuri de legături structurale fundamentale:
- mulţime (nici o legătură între componente), fişier
- liniară (legătura 1:1), tablou unidimensional (vector), liste
liniare, articol
- arbore (legătura 1:n), liste dublu înlănţuite
- graf (legătura m : n), tablouri bidimensionale (mxn).
Din punctul de vedere al uniformităţii structurale, datele
structurate se împart în:
- omogene (toate componentele au acelaşi tip); tipurile de date
aferente sunt numite tablou (engl. array), mulţime (engl. set) şi
fişier (engl. file);
- heterogene (elementele unei date au de obicei componente diferite ca
tip); ele aparţin tipului de date înregistrare (engl. record).
Tablourile, fişierele şi înregistrările au structura liniara:
exista o prima şi o ultima componenta, iar toate celelalte au fiecare
atât predecesor, cât şi succesor. Prin urmare, un element (al
tabloului), o înregistrare (din fişier) sau un câmp (al
înregistrării) se pot localiza. Un tablou este un agregat de elemente
de acelaşi tip, un element fiind localizat prin poziţia pe care o
ocupa în cadrul acestuia (indicele elementului de tablou). Un fişier
este constituit şi el din elemente (înregistrări) de acelaşi tip,
localizate tot după poziţia ocupata în fişier. Deosebirea dintre un
tablou şi un fişier consta în aceea ca tabloul este memorat în
memoria interna a calculatorului, iar fişierul este memorat în
memoria externa (pe un suport magnetic sau magneto-optic). O
înregistrare este un agregat care grupează de obicei elemente de
tipuri diferite numite câmpuri şi localizate prin numele lor.
Mulţimea are o structura amorfa: ea conţine elemente de acelaşi
tip, care însă nu pot fi localizate explicit, neexistând o ordine
în care sa fie considerate elementele din ea.
2. Tipuri de date structurate. Definiţii şi clasificări.
2.1. Tablouri
Tablourile se folosesc pentru a grupa variabile de tipuri identice şi
a le manipula prin operaţii. dacă fiecare variabila ar fi declarata
individual, atunci fiecare operaţie ar trebui specificata separat,
fapt care ar duce la programe lungi.
Un tablou ne permite sa grupam variabilele de acelaşi tip sub un
singur nume şi sa putem referi fiecare variabila (numita element al
tabloului) asociind numelui un indice (care o va identifica unic). Prin
aceasta se reduce considerabil dimensiunea unui program care
efectuează operaţii similare asupra mai multor elemente din tablou,
folosind indicii şi instrucţiunile de ciclare.
In Pascal, declaraţia de tip tablou are sintaxa:
Type tip_tablou = Array[tip_index] Of tip_element;
unde:
- Array şi Of sunt cuvinte rezervate
- tip_element, numit tipul componentei, poate fi orice tip recunoscut
de sistemul de tipuri
- tip_index este o listă de tipuri de indici; numărul elementelor
din aceasta lista denota numărul de dimensiuni al tabloului, care nu
este limitat.
Tipurile indicilor trebuie sa fie ordinale (cu excepţia lui Longint
şi a subdomeniilor de Longint). Dacă tipul componentei este tot un
tip tablou, rezultatul acestei declaraţii de tip poate fi tratat fie
ca un tablou de tablouri, fie ca un tablou mono dimensional. De
exemplu, a două declaraţie:
type D = 20..30;
type T = array[boolean] of array[1..10] of array[D] of real;
este identica (structural) cu declaratia:
type T1 = array[boolean, 1..10, D] of real;
iar referiri corecte de elemente sunt:
var
A: T;
A1: T1;
A[ false] ş i A1[ false] sunt de tip array[ 1..10] of array[ D] of
real;
A[ false,5] ş i A1[ false,5] sunt de tip array[ D] of real;
A[ false][ 5] şi A1[ false][ 5] sunt de tip array[ D] of real;
A[ false,5,30] şi A1[ false,5,30] sunt de tip real;
A[ false][ 5][ 30] şi A1[ false][ 5]30] sunt de tip real;
Declararea de variabile de tip tablou nu trebuie neapărat să
conţină numele unui tip de date tablou. Constructorul de tip se poate
include în declaraţia de variabilă. Astfel,
Var
V: Array[ 1..10] Of Integer;
este o declaraţie valida de variabila. în această declaraţie de
variabilă, numele tipului tablou este referit chiar prin constructorul
de tip, adică
Array[ 1..10] Of Integer;
Numărul de elemente al unui tablou este dat de produsul numărului de
elemente în fiecare dimensiune.
Accesarea (referirea) unui element de tablou se face prin precizarea
numelui tabloului urmat de o expresie de indice. Expresia de indice
conţine, în paranteze drepte valorile efective ale indicilor
tabloului (ce trebuie, de obicei, să concorde ca număr şi tip cu
declararea acestuia). Există în general două modalităţi de
referire:
- punctuală
- de subtablouri.
Ambele modalităţi se bazează pe calculul de adresa.
Pentru fiecare tablou declarat, se memorează în descriptorul de
tablou următoarele informaţii:
- nume = numele tabloului;
- tip = tipul elementului de tablou;
- lung = lungimea reprezentării unui element de tablou (în unităţi
de alocare);
- adrs = adresa de unde începe memorarea tabloului;
- nrd = numărul de dimensiuni al tabloului;
- pentru fiecare dimensiune i, limitele linfi şi lsupi (i=1,nrd)
Tablourile bidimensionale (numite şi matrice în limbajul curent) au
linii şi coloane. Am văzut în paragraful precedent cum se memorează
aceste tablouri. Dăm aici un exemplu care foloseşte două
modalităţi diferite (structural echivalente) de declarare a
tablourilor bidimensionale.
Exemplu:
Type
DomeniuLinii = 1..25;
DomeniuColoane = 1..80;
Element = Record
Car: Char;
Atr: Byte
End;
TabEcran1 = Array[ DomeniuLinii, DomeniuColoane] Of Element;
TabEcran2 = Array[ DomeniuLinii] Of Array[ DomeniuColoane] Of
Element;
Var
EcranColor1: TabEcran1 Absolute $B800:0000;
EcranMono1: TabEcran1 Absolute $B000:0000;
EcranColor2: TabEcran2 Absolute $B800:0000;
EcranMono2: TabEcran2 Absolute $B000:0000;
Begin
EcranColor1[ 12, 33].Car := 'A';
Write(EcranColor2[ 12][ 33].Car);
EcranMono2[ 11][ 25].Car := 'B';
Write(EcranMono1[ 11,25].Car);
End.
Prima modalitate de declarare permite accesarea
- punctuală: EcranColor1[ 12, 33]
- globală: EcranColor1
A două modalitate de declarare a tabloului permite accesarea
- punctuală: EcranColor2[ 12, 33] sau EcranColor2[12][33]
- a unei linii: EcranColor2[ 12] (care va fi de tipul
Array[DomeniuColoane] Of Element)
- globală: EcranColor2
Tablourile multidimensionale au mai mult de două dimensiuni.
Limbajul Pascal nu impune o regulă privind numărul maxim de
dimensiuni al unui tablou. Trebuie avută în vedere doar restricţia
ca spaţiul alocat unei variabile să nu depăşească dimensiunea
segmentului de date sau de stivă.
Operaţii globale pe tablouri
Operaţiile definite pe tipul tablou sunt atribuirea şi testul de
egalitate. De asemenea, variabilele de tip tablou se pot transmite ca
parametrii în subprograme.
2.2. Mulţime
Limbajul Pascal este unul din primele limbaje care a introdus tipul
mulţime. Fiind dat un tip ordinal B, numit tip de baza, tipul mulţime
T se declară folosind sintaxa:
Type tip_mulţime = Set Of tip_de_baza;
Domeniul tipului tip_mulţime T este mulţimea părţilor
(submulţimilor) domeniului tipului tip_de_baza. Astfel, dacă tipul B
are domeniul {a, b, c}, atunci domeniul lui T va fi
{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Tipul T se consideră structurat deoarece fiecare element al său
conţine elemente (posibil nici unul) din domeniul tipului de baza B.
Implementarea tipului mulţime se face pe şiruri de biţi. Dacă
domeniul tipului de baza B are n elemente, atunci domeniul tipului
mulţime T va avea 2^n (2 la puterea n) elemente, deci o variabila de
tip T se poate reprezenta pe un şir de n biţi. Bitul de pe poziţia i
din şirul respectiv (1<=i<=n) va fi setat pe 1 dacă al i-lea element
din domeniul lui B (ordinal) aparţine mulţimii şi 0 în caz contrar.
Operaţiile tipului mulţime se implementează eficient prin operaţii
pe şiruri de biţi. în cazul limbajului Pascal, n = 256.
Mulţimile reprezintă un instrument matematic elegant. Prezenta lor
în limbajele de programare îmbogăţeşte expresivitatea acestuia.
Din păcate, limitările impuse asupra domeniului tipului de baza
(număr de elemente şi tip) restrâng utilizarea mulţimilor. în
astfel de situaţii, utilizatorul poate să-si definească propriile
sale tipuri mulţime.
Înainte de a opera cu variabile de tip mulţime, ele trebuie
construite. Regulile de construire a variabilelor de tip mulţime în
Pascal sunt următoarele:
- o mulţime Pascal este formata dintr-o lista de elemente separate
prin virgula şi incluse în paranteze drepte;
- mulţimea vidă se marchează prin [ ];
- toate elementele din lista trebuie sa fie de acelaşi tip, tipul de
bază al mulţimii
- toate elementele sunt diferite
- în loc să se enumere toate elementele dintr-un subdomeniu, se
poate preciza subdomeniul pe post de element în lista (primul şi
ultimul element cu .. între ele)
Ordinea în care se executa operaţiile:
- declararea tipului mulţime T
- declararea variabilei V de tipul T
- construirea (iniţializarea) variabilei V
Exemple:
Type
Luni = (Ian, Feb, Mar, Apr, Mai, Iun, Iul, Aug, Sep, Oct, Nov, Dec);
Anotimp = Set Of Luni;
Caractere = Set Of Char;
Var
Iarna, Primavara, Vara, Toamna: Anotimp;
Litere, Cifre: Caractere;
Begin
Iarna := [ Dec, Ian, Feb, Mar];
Vara := [ ];
Toamna := [ Aug, Sep, Oct, Nov];
Primavara := [ Apr, Mai, Iun, Iul];
If Vara = [ ] Then WriteLn('Anul asta n-a fost vara!');
Litere := [ 'A'..'Z', 'a'..'z'];
Cifre := [ '0'..'9']
End.
Compararea mulţimilor şi testul de apartenenţă
---------------------------------------------------------------------------------------
Operator Descriere Exemplu de folosire
Rezultat
---------------------------------------------------------------------------------------
= egalitate de mulţimi [ Ian, Feb] = [ ]
False
<> diferit [ Ian, Mar] <> [ Apr]
True
<= incluziunea A <= B [ Ian, Mar] <= [ Ian, Aug, Mar]
True
înseamnă ca orice element [ Ian, Mar] <= [ Feb]
False
din A aparţine şi lui B
>= include: A >= B înseamnă [ Ian, Aug, Mar] >= [ Ian, Apr]
False
ca orice element din B [ Ian, Mar] >= [ Mar]
True
aparţine şi lui A
in x în A înseamnă x Ian în [ Aug, Feb]
False
aparţine lui A Mar în [ Ian, Aug, Mar]
True
x trebuie sa fie din 'P' în [ 'A'..'Z']
True
tipul de baza
--------------------------------------------------------------------------------------
Operaţiile proprii tipului mulţime sunt cele cunoscute:
a) operaţii binare cu rezultat mulţimi
- reuniunea “+”,
- intersecţia “*”,
- diferenţa “-“
b) operaţii binare cu rezultat boolean
- incluziunea , testul de egalitate “=”
- apartenenţa IN,
c) atribuirea “:=”.
2.3. Articol (înregistrare)
Elementele definitorii ale unei înregistrări sunt:
- numele tipului înregistrare (opţional),
- numărul de câmpuri,
- numele şi tipul fiecărui câmp.
Înregistrarea este o modalitate de agregare (punere împreuna a unor
date de tipuri (în general) diferite. Numele tipului de data
înregistrare este un identificator. Numărul de câmpuri este dedus
din lista de declarare a câmpurilor. Câmpurile unei înregistrări se
memorează în zone adiacente de memorie. Informaţia de tip a
fiecărui câmp serveşte la stabilirea lungimii de reprezentare a
acestuia, iar numele câmpului se foloseşte pentru a accesa valoarea
lui (prin operaţia de accesare). De obicei, sunt accesibile atât data
compusa (înregistrarea), cât şi componentele (câmpurile) acesteia.
Exista două clase de înregistrări: cu structura fixa şi cu
variante. Înregistrările cu structura fixa au o singura definiţie,
iar înregistrările cu variante au o parte fixa, un discriminant şi
mai multe definiţii de variante.
Lungimea unei înregistrări este suma lungimilor câmpurilor
componente. Se poate folosi functia SizeOf cu parametru tipul de data
înregistrare sau variabila de tip înregistrare.
Elementele de discuţie privitoare la tipul de date înregistrare sunt
următoarele:
- maniera de declarare a tipurilor înregistrare;
- maniera de accesare a câmpurilor unei înregistrări;
- definirea înregistrărilor cu structura variabila;
- iniţializarea unei variabile înregistrare;
- operaţiile permise pe variabile de tip înregistrare.
Declararea tipului înregistrare
In Pascal, de exemplu, tipurile de date DataC (data calendaristica),
Timp şi ElementEcran se declara astfel:
Type
DataC = Record
zi : 1..31;
lu : 1..12;
an : 1800..2000;
End;
Timp = Record
ora: 0..23;
min: 0..59;
sec: 0..59
End;
Element = Record { definiţia unui element pe ecranul text }
Car: Char;
Atr: Byte
End;
Se observă că aceste tipuri de date au componente (câmpuri)
diferite ca tip de date. Odată declarate aceste tipuri, se pot declara
variabile de tipurile respective:
Var
DataNasterii, DataCasatoriei: DataC;
OraDeIncepere: Timp;
Ecran: Array[ 1..25] Of Array[ 1..80] Of ElementEcran;
Doar în momentul declaraţiei de variabila se poate stabili
dimensiunea de alocare pentru variabilele de tipurile respective.
Referirea componentelor sau selectarea (accesarea) câmpurilor unei
înregistrări se face în Pascal în două moduri:
- folosind calificarea cu punct
- folosind instrucţiunea With
Calificarea cu punct permite accesarea sau modificarea valorii unui
câmp dintr-o variabila înregistrare. Ea se face în forma:
nume_variabila.nume_câmp
Variabilele de tip înregistrare se pot accesa şi global, prin numele
lor.
Este permisa de asemenea operaţia de atribuire, când variabilele
implicate sunt de acelaşi tip:
Var
Data1, Data2: DataC;
--------------------------------------------------------
Atribuire globala Echivalenta cu
--------------------------------------------------------
Data1 := Data2 Data1.zi := Data2.zi
Data1.lu := Data2.lu
Data1.an := Data2.an
--------------------------------------------------------
Câmpurile unei înregistrări pot fi de orice tip recunoscut de
sistemul de tipuri, în particular şi tip înregistrare.
Type
DataC = Record
zi : 1..31;
lu : 1..12;
an : 1800..2000;
End;
A40 = Array[ 1..40] Of Char;
TipSex = (masc,fem);
StareCiv = (necas,casat,vaduv,divortat);
Persoana = Record
Nume : String[ 30];
NrId : Longint;
Adr : A40;
Sex : TipSex;
StareC : StareCiv;
DataN : Datac;
inalt : Real
End;
Tipurile câmpurilor sunt predefinite (String, LongInt, Real în Turbo
Pascal), simple utilizator (TipSex şi StareCiv), respectiv structurate
(A40 şi DataC).
Prin urmare, cu astfel de notaţii de tip se pot declara tipuri
oricât de complexe. dacă se declară o variabilă de tip Persoana:
Var p : Persoana;
ea va putea fi tratată fie global (atribuire, test de egalitate), fie
selectiv (p.Inalt va semnifica câmpul inalt din înregistrarea p).
Tabelul următor prezintă exemple de accesare (cu punct şi cu With).
With P Do
Begin
P.Nume := 'IONESCU'; Nume := 'IONESCU';
P.Sex := masc; Sex := masc;
P.StareC := casat; StareC := casat;
P.Inalt := 1.80; Inalt := 1.80;
P.DataN.zi := 23; DataN.zi := 23
End
Alte exemple de structuri complexe
- înregistrări cu câmpuri tablou
- tablouri de înregistrări
Const
Max_Persoane = 100;
Max_Discipline = 20;
Type
Personal: Array[ 1..Max_Persoane] Of Persoana;
Medie = Record {facem economie: Medie: Real ocupa 6 bytes }
Parte_Int: Byte; {SizeOf(Medie) = 2}
Parte_Zec: Byte
End; { Medie }
Medii = Array[ 1..Max_Discipline] Of Medie;
Trimestru = 1..3;
Elev = Record
Nume: String[ 40];
DataN: DataC; {declarat în exemplul de mai sus}
SitScolara: Array[ Trimestru] Of Medii;
End; { Elev }
2.4. Fişier
Noţiunea de fişier stă la baza multor concepte în informatică,
cum ar fi sisteme de operare DOS sau WINDOWS etc.
Noţiunile de dată şi nume de dată sunt considerate ca noţiuni
primare şi le vom numi câmpuri.
In prelucrarea datelor a apărut necesitatea considerării unor
grupări de date.
Exemplu: nume, prenume, adresa
Datele asociate celor trei nume de dată, împreună, constituie un
articol (înregistrare).
Exemplu:
Gestiunea mărfurilor dintr-un magazin se realizează pe baza unor
date care conţin: denumirea produsului, cantitatea, preţul unitar,
codul de bară. Aceste date care nume şi tipuri diferite le numim
câmpurile articolului. Articolul corespunzător unui produs îl vom
numi PRODUS, iar câmpurile fiecăruia sunt DEN, CANT, PRET, COD. La un
moment dat ne referim la denumirea unui produs prin PRODUS.DEN. Pentru
un şir de produse referinţa este PRODUS(i).DEN, adică denumirea
produsului de pe poziţia i.
Definiţie.
Numim fişier o mulţime de realizări (înregistrări) ale unuia sau
mai multor articole.
EVIDENTA = {r1,r2,…rn} sau o colecţie de înregistrări de acelaşi
tip.
Accesul la datele dintr-un fişier
Accesul la datele dintr-un fişier poate fi:
- secvenţial; pentru a ajunge la o anumită dată dintr-un fişier
este necesar sa parcurgem realizări de articol una după alta, până
la acea data pe care o caut.
Toate suporturile de date pe care se găsesc fişiere admit acest mod
de acces.
- direct, înseamnă posibilitatea de acces direct la o realizare a
articolului din fişier, fără a mai fi nevoie de consultarea
celorlalte articole. Există posibilitatea de identificare a
înregistrărilor prin intermediul unor chei. Acest mod de acces este
posibil numai pe anumite suporturi pe care există mecanisme fizice
care dau posibilitatea unui astfel de acces. Există posibilitatea de
acces direct în memoria calculatoarelor şi pe discuri magnetice.
Organizare
Modurile de organizare a fişierelor sunt :
a) Organizarea secvenţială presupune aranjarea înregistrărilor
una după alta. Este posibilă pe toate suporturile de date, accesul
este numai cel secvenţial.
b) Organizarea secvenţial-indexată presupune asocierea la fişierul
de această organizare a unui tabel de index care conţine 2 coloane
(câmpuri); un câmp conţine cheile de articol care identifică
înregistrările fişierului; al doilea câmp conţine adresele fizice
ale înregistrărilor fişierului de această organizare. Consultarea
unui astfel de fişier se face folosindu-ne de tabela de index, întâi
se consultă tabela de index, apoi din tabelă găsim înregistrarea
care ne interesează, apoi având adresa acestei înregistrări ne
ducem direct la înregistrarea pe care o căutăm. Avem posibilitatea
de acces direct la aceste înregistrări. Este posibilă o astfel de
organizare pe suporturi care admit un acces direct.
c) Organizarea selectiva, foloseşte nişte câmpuri cheie ale
fişierului pe care dorim să-l organizam în acest fel. Facem o
distribuire a realizărilor de articol în aşa numitele casete care au
câte un număr de ordine, folosind un algoritm special în acest scop;
într-o casetă se găsesc un anumit număr de înregistrări.
Consultarea unui fişier selectiv presupune identificarea casetei în
care se găseşte acea înregistrare, parcurgerea secvenţială a
înregistrărilor din caseta respectiva admit accesul direct.
Distribuirea în casete a înregistrărilor se face pe baza unor
algoritmi numiţi algoritmi de randomizare.
Un astfel de algoritm poate fi: aleg un câmp al fişierului numeric
şi numărul casetei în care se include o realizare de articol poate
fi restul împărţirii la n a valorii numerice din câmpul cheie ales.
Vor fi n casete numerotate: 0,1,…,n
Operaţii cu fişiere
Operaţiile cu fişiere presupun:
- creare de fişier (a scrie într-un fişier, înregistrări);
- exploatate sau consultate (a citi) realizări de articol.
- actualizarea poate fi :
• modificare, adică citesc o înregistrare, din ea modific o
anumită dată.
• adăugare, adaug o nouă înregistrare
• ştergere, ştergerea unei înregistrări.
Actualizarea presupune o citire a înregistrării, apoi modificarea,
scrierea unei înregistrări sau ştergerea unei înregistrări.
La nivelul programului sursa Pascal, un fişier este referit printr-o
variabila fişier, ceea ce am numit anterior identificator logic de
fişier. Deoarece Pascal este un limbaj puternic tipizat,
identificatorul logic de fişier trebuie sa fie de una dintre
următoarele tipuri:
- text (pentru fişiere text)
- file of tip_componenta (fişierul este un fişier record în care
fiecare înregistrare este de tipul tip_componenta)
- file (fişierul este nedefinit, fiind considerat ca o succesiune de
octeţi - stream)
Declararea variabilelor fişier se face uzual, folosind cuvântul
rezervat var. Variabilele fişier nu se pot folosi decât în
operaţiile specifice lucrului cu fişiere. Mai exact, o variabila
fişier se iniţializează prin operaţia de deschidere a fişierului
şi îşi pierde valoarea la închiderea acestuia.
var
fis_text: Text; { fişier text }
fis_intregi = File of Integer; { fişier de intregi }
fis_nedefinit: File; { fişier nedefinit }
Deschiderea unui fişier
Operaţia de deschidere a unui fişier este prima operaţie care se
efectuează asupra acestuia, înaintea prelucrărilor propriu-zise la
care acesta este supus. Menirea acestei operaţii este de a stabili
- modul în care este folosit fişierul (citire sau scriere)
- alocarea buffer-ului şi iniţializarea contorului de poziţie.
Deschiderea fişierelor
In Turbo şi Borland Pascal, operaţia de deschidere a unui fişier se
realizează în doi paşi:
- iniţializarea variabilei fişier;
- deschiderea propriu-zisa a fişierului.
Iniţializarea variabilei fişier se face cu procedura standard
Assign, care are declaraţia:
procedure Assign(var var_fis; nume_fis:String);
unde:
- var_fis este o variabila fişier de oricare tip (identificatorul
logic de fişier),
- nume_fis este un şir de caractere ce desemnează numele extern al
fişierului (specificatorul de fişier)
După execuţia procedurii, var_fis va fi iniţializată, fiind
asociată fişierului extern nume_fis; cu alte cuvinte, orice operaţie
pe var_fis va însemna de fapt lucrul cu fişierul nume_fis. Asocierea
rămâne valabilă până când se închide fişierul referit de
var_fis sau până când var_fis apare într-o alta procedură Assign.
Daca nume_fis este şirul de caractere vid, var_fis va fi asociată
unuia dintre fişierele sistem. Dacă nume_fis este numele unui fişier
deja deschis, se produce o eroare de execuţie.
Deschiderea propriu-zisa a unui fişier se face în mod obişnuit prin
apelul uneia dintre procedurile standard Reset sau Rewrite.
Procedura standard Reset realizează deschiderea unui fişier (de
obicei) în citire. Declaraţia sa este:
procedure Reset(var var_fis);
unde var_fis este o variabila fişier de oricare tip (identificatorul
logic de fişier), asociat în prealabil unui fişier extern prin
apelul procedurii Assign.
Reset deschide fişierul extern asociat variabilei var_fis. dacă
fişierul respectiv este deja deschis, el se închide în prealabil şi
apoi are loc deschiderea. Contorul de poziţie al fişierului se
setează pe începutul fişierului. Reset produce o eroare de
intrare-ieşire dacă fişierul extern nu exista. în cazul fişierelor
text, Reset produce deschiderea acestora numai în citire.
Pentru fişierele non-text, Unit-ul System contine variabila FileMode,
care conţine informaţia privitoare la modul de deschidere a acestora
prin Reset:
- 0 - Read only (numai citire)
- 1 - Write only (numai scriere)
- 2 - Read/Write (valoare implicita).
Aceasta variabila se poate seta de către programator prin operaţia
de atribuire.
Procedura standard Rewrite realizează deschiderea unui fişier în
scriere.
Declaraţia sa este:
procedure Rewrite(var var_fis);
unde var_fis este o variabila fişier de oricare tip (identificatorul
logic de fişier), asociat în prealabil unui fişier extern prin
apelul procedurii Assign.
Rewrite creează fişierul extern asociat variabilei var_fis. Dacă
fişierul respectiv exista, atunci el se şterge şi se creează un
fişier vid. Dacă el este deja deschis, atunci se închide în
prealabil şi apoi este re-creat.
Contorul de poziţie al fişierului se setează pe începutul
fişierului. în cazul fişierelor text, Rewrite produce deschiderea
acestora numai în scriere.
Închiderea unui fişier
Operaţia de închidere a unui fişier semnifica terminarea lucrului
cu acesta. Prin închidere se realizează următoarele:
- transferarea informaţiei din buffer pe suport (în cazul
fişierelor deschise în scriere)
- distrugerea asocierii între variabila fişier şi numele extern al
fişierului.
După închidere, fişierul se poate folosi din nou, respectând
etapele descrise anterior. Variabila fişier devine disponibila, ea
putând fi folosita într-un alt apel al procedurii Assign.
Pentru un fişier deschis în citire, prelucrarea sa se termina de
regulă atunci când s-a ajuns la sfârşitul său. Detectarea
sfârşitului de fişier se face cu funcţia standard EOF. Declaraţia
acesteia este:
function Eof(var var_fis): Boolean; { fişiere non-text
}
function Eof [ (var var_fis: Text) ]: Boolean; { fişiere text }
In cazul fişierelor text, dacă var_fis lipseşte se considera ca EOF
se refera la fişierul standard de intrare. Altfel, var_fis va referi
un fişier deschis în prealabil prin Assign şi Reset/Rewrite. EOF
întoarce:
- True dacă contorul de poziţie este după ultimul octet din fişier
sau dacă fişierul este vid
- False în toate celelalte cazuri.
Exemplu: citirea unui fişier text şi afişarea acestuia pe ecran;
Program CitireT;
var f: text;
linie: string;
numeFis: String;
este: Boolean;
function Exista(NumeFişier: String): Boolean;
{ intoarce
True dacă fişierul extern reprezentat de NumeFişier exista
False altfel
}
var
f: File;
begin
{$I-} { comuta pe off indicatorul $I }
Assign(f, NumeFişier);
FileMode := 0; { deschide în citire }
Reset(f);
Close(f);
{$I+}
Exista := (IOResult = 0) and (NumeFişier <> '')
end; { Exista }
begin
WriteLn('CitireT - afisarea unui fişier text pe ecran');
Repeat
Write('Dati numele fişierului: ');
ReadLn(numeFis);
este := Exista(numeFis);
if not este then WriteLn('Fişier inexistent!');
Until este;
Assign(f, numeFis); { asociaza f la numeFis }
Reset(f); { deschide f în citire }
While not Eof(f) do begin { cat timp nu s-a ajuns la sfarsit }
Readln(f, linie); { citeste o linie din fişier }
Writeln(linie) { scrie linia la iesirea standard }
end;
Close(f); { inchide fişierul }
end. { CitireT }
Poziţionarea
Operaţia de poziţionare se refera la fişierele non-text şi are ca
efect modificarea contorului de poziţie. Modificarea se face în două
moduri:
- implicit, prin operaţiile de citire şi de scriere; orice operaţie
de transfer modifica contorul de poziţie, acesta avansând spre
capătul fişierului
- explicit, prin procedura standard Seek.
Mediile Borland pun la dispoziţia programatorului o funcţie şi o
procedura care îi permit acestuia sa acceseze şi sa modifice contorul
de poziţie:
FilePos şi Seek. De asemenea, functia FileSize determină dimensiunea
unui fişier.
Functia FileSize întoarce numărul de componente dintr-un fişier.
Declaraţia sa este următoarea:
function FileSize(var var_fis): Longint;
în care var_fis este o variabila fişier, asociata unui fişier
deschis în prealabil. FileSize întoarce numărul de componente al
fişierului. dacă fişierul este vid, FileSize întoarce 0. Semantica
exactă a lui FileSize pentru fiecare clasă de fişiere poate fi
studiată folosind exemplele mediului.
Funcţia FilePos întoarce valoarea contorului de poziţie al unui
fişier non-text. Declaraţia sa este:
function FilePos(var var_fis): Longint;
în care var_fis este o variabila fişier, asociata unui fişier
deschis în prealabil. dacă contorul de poziţie este pe începutul
fişierului, FilePos va întoarce 0, iar dacă contorul de poziţie
este la sfârşitul fişierului, atunci FilePos(var_fis) va fi egal cu
FileSize(var_fis).
Contorul de poziţie al unui fişier non-text se exprima în unitari
de măsura proprii tipului de fişier. El semnifica înregistrarea
curenta din fişier, luând valori de la 0 (începutul fişierului,
prima înregistrare din el) la FileSize(var_fis) - 1 (ultima
înregistrare din fişier). Procedura standard Seek realizează
modificarea contorului de poziţie la o noua valoare, specificată ca
parametru al acesteia. Declaraţia sa este:
procedure Seek(var var_fis; pozitie: Longint);
în care:
- var_fis este o variabila fişier, asociata unui fişier deschis în
prealabil
- poziţie este un întreg, cu următoarele valori valide:
• între 0 şi FileSize(var_fis) - 1: contorul de pozitie al
fişierului var_fis se va seta la valoarea poziţie
• FileSize(var_fis): în fişierul var_fis se va adaugă (la
sfârşit) o noua înregistrare
Există, de asemenea, procedura Truncate, care permite trunchierea
unui fişier non-text. Declaraţia sa este:
procedure Truncate(var var_fis);
în care var_fis este o variabila fişier, asociata unui fişier
deschis în prealabil. Truncate păstrează în fişier numai
înregistrările de la 0 şi până la FilePos(var_fis) - 1, eliminând
celelalte înregistrări din el (daca exista) şi setând EOF(var_fis)
pe True.
Citirea
Operaţia de citire înseamnă transferarea de informaţie din
fişierul extern în memoria interna a calculatorului. Mai exact,
citirea realizează iniţializarea unor variabile din programul Pascal
cu valori preluate din fişierul extern.
Citirea se face diferit pentru fiecare clasa de fişiere Borland
(Turbo) Pascal. Ea poate sau nu să fie însoţită de conversii.
Scrierea
Operaţia de scriere înseamnă transferarea de informaţie din
memoria interna a calculatorului în fişierul extern. Mai exact,
scrierea realizează memorarea valorilor unor variabile din programul
Pascal în fişierul extern. Scrierea se face diferit pentru fiecare
clasa de fişiere Borland (Turbo) Pascal. Ea poate sau nu să fie
însoţită de conversii.
2.4.1. Fişiere text
Fişierele text sunt fişiere speciale, care se pot citi sau edita de
orice editor de texte standard. Un fişier text este o succesiune de
caractere ASCII organizate în linii. Numărul de linii este variabil,
iar fiecare linie conţine un număr variabil de caractere. O linie se
termina cu o combinaţie speciala de caractere (de regula CR+LF, adică
ASCII 10 + ASCII 13), iar sfârşitul de fişier poate fi determinat cu
ajutorul funcţiei EOF. Aceasta poate folosi:
- funcţia FileSize (care determina numărul de caractere din fişier)
- un caracter special de sfârşit de fişier (cu codul ASCII 26,
recunoscut prin combinaţia CTRL+Z de la tastatura).
Mediile Borland şi Turbo Pascal permit specificarea unui fişier text
prin cuvântul cheie text, care are declaraţia:
type text = file of char;
In Borland şi Turbo Pascal sunt disponibile următoarele funcţii şi
proceduri specifice lucrului cu fişierele text:
- Append (procedura)
- EOLN (functie)
- Flush (procedura)
- Read (procedura)
- ReadLn (procedura)
- SeekEOF (functie)
- SeekEOLN (functie)
- SetTExtBuf (procedura)
- Write (procedura)
- WriteLn (procedura)
In cele ce urmează, cu excepţia locurilor unde se face o referire
explicita, prin var_fis vom desemna o variabila fişier de tip text,
deschis în prealabil.
Procedura Append este specifică fişierelor text. Ea permite
deschiderea unui fişier în adăugare, adică:
- deschide fişierul în scriere
- setează contorul de poziţie la sfârşitul fişierului.
Declaraţia sa este:
procedure Append(var var_fis: Text);
unde var_fis este o variabila fişier de tip text, asociata în
prealabil printr-o procedura Assign unui fişier extern existent. dacă
fişierul extern nu exista, se produce o eroare de intrare-ieşire.
dacă var_fis desemnează un fişier deja deschis, acesta se închide
în prealabil şi apoi se executa operaţiile specifice lui Append.
Daca terminatorul de sfârşit de fişier CTRL+Z este prezent,
contorul de poziţie se setează pe poziţia acestuia. Prin urmare,
după fiecare scriere în fişier acesta va conţine la sfârşitul sau
terminatorul de fişier.
Funcţia EOLN întoarce statutul de sfârşit de linie, adică EOLN
- întoarce True dacă :
- caracterul curent din fişier (specificat prin contorul de poziţie)
este un terminator de linie sau de fişier
- între caracterul curent şi sfârşitul de linie nu exista decât
spaţii
- întoarce False altfel.
Declaraţia aceste funcţii este:
function EOLN [(var var_fis: Text)]: Boolean;
Dacă var_fis lipseşte, se consideră că EOLN se referă la
fişierul standard de intrare.
Procedura Flush realizează transferul fizic de informaţie din
bufferul unui fişier deschis în scriere (cu Rewrite sau Append) pe
suport. Declaraţia sa este:
procedure Flush(var var_fis: Text);
Scrierea pe un fişier text se realizează prin intermediul unui
buffer. în mod normal, scrierea fizica se efectuează numai atunci
când bufferul este plin.
Apelând Flush, ne asigurăm ca se efectuează scrierea şi când
bufferul nu este plin.
Procedura standard Read citeşte valori dintr-un fişier text
într-una sau mai multe variabile. Citirea se efectuează începând de
la contorul de poziţie, avansându-se spre sfârşitul fişierului. Se
pot efectua conversii, în funcţie de tipul variabilelor prezente ca
parametri ai lui Read. Declaraţia procedurii este:
procedure Read( [ var var_fis: Text; ] V1 [, V2,...,Vn ] );
unde V1, V2, ..., Vn sunt variabile pentru care Read este în domeniul
lor de vizibilitate. Citirea se opreşte la sfârşitul de linie sau de
fişier, fără a se citi şi aceste caractere speciale.
Procedura standard ReadLn este similara procedurii Read, cu excepţia
faptului ca după terminarea citirii trece la linia următoare: la
întâlnirea caracterelor de sfârşit de linie le sare, setând
contorul de poziţie după ele.
Declaraţia procedurii este:
procedure ReadLn( [ var var_fis: Text; ] V1 [, V2,...,Vn ] );
Dupa executarea lui ReadLn, contorul de poziţie va fi setat pe
începutul unei noi linii.
Functia SeekEOF întoarce True dacă s-a ajuns la sfârşitul de
fişier şi False altfel. Declaraţia sa este:
function SeekEOF [ (var var_fis: Text) ]: Boolean;
Functia SeekEOLN întoarce True dacă s-a ajuns la sfârşit de linie
şi False altfel. Declaraţia sa este:
function SeekEOLN [ (var var_fis: Text) ]: Boolean;
Procedura SetTextBuf atribuie unui fişier text un buffer de
intrare-ieşire.
Uzual, bufferul de I/E pentru fişierele text este de 128 de octeţi.
Cu cât bufferul este mai mare, cu atât operaţiile de citire şi de
scriere se executa mai rapid şi printr-un număr mai mic de accese la
suportul fizic. Declaraţia este următoarea:
procedure SetTextBuf(var var_fis: Text; var Buf [ ; Lung: Word ] );
unde:
- Buf este numele unei variabile (de obicei de tipul unui tablou de
caractere) care va fi folosită pe post de buffer
- Lung este dimensiunea bufferului (în octeţi)
SetTextBuf trebuie apelată imediat după deschiderea fişierului
(următoarea instrucţiune după Reset, Rewrite sau Append).
Procedura Write scrie valoarea uneia sau mai multor variabile într-un
fişier text. Scrierea se efectuează începând de la contorul de
poziţie, avansându-se spre sfârşitul fişierului. Se pot efectua
conversii, în funcţie de tipul variabilelor prezente ca parametri ai
lui Write. Declaraţia procedurii este:
procedure Write( [ var var_fis: Text; ] P1 [, P2,...,Pn ] );
unde P1, P2, ..., Pn sunt expresii de formatate, formate din nume de
variabile sau expresii (de una din tipurile Char, Integer, Real, String
şi Boolean) ce conţin variabile împreuna cu specificatori de lungime
şi de număr de zecimale. Pentru tipurile numerice, se face conversia
la string înainte de scrierea în fişier. Fişierul trebuie sa fie
deschis cu Rewrite sau Append. Contorul de poziţie se va mari cu
lungimea stringurilor scrise.
O expresie de formatare P are formatul: V:l[:z], unde
- v este o variabila de tip numeric
- l este lungimea stringului generat (daca partea întreaga a lui v
are lungimea mai mare ca l, atunci l se va seta la lungimea părţii
întregi a lui v - luând în considerare şi semnul)
- z este numărul de cifre la partea zecimala (numai pentru variabile
reale).
Procedura WriteLn este similara cu Write, scriind la sfârşit un
terminator de linie. Declaraţia procedurii este:
procedure WriteLn( [ var var_fis: Text; ] P1 [, P2,...,Pn ] );
iar semantica ei este:
Write( var var_fis, P1 [, P2,...,Pn ] );
Write( var var_fis, Chr(13), Chr(10) ); { terminator de linie }
Procedurile ReadLn şi WriteLn sunt specifice fişierelor text, pe
când
procedurile Read şi Write se folosesc şi în cazul fişierelor cu
tip.
Exemplu:
Program CitireT;
{ exemplu de citire a unui fişier text cu afişarea lui pe ecran }
uses
UFile{, Crt};
var
f: text;
linie: string;
numeFis: string;
nrLinie: integer; { contor de linie }
nrPagina: integer;
este: boolean;
begin
Repeat
{ClrScr;}
WriteLn('CitireT - afişarea unui fişier text pe ecran');
Repeat
Write('Dati numele fişierului (ENTER la terminare): ');
ReadLn(numeFis);
If numeFis = '' then Exit;
este := Exista(numeFis);
if not este then WriteLn('Fişier inexistent!');
Until este;
nrLinie := 0;
nrPagina := 1;
WriteLn('Continutul fişierului ', numeFis, ' este:
', 'Pag. ', nrPagina:3);
Assign(f, numeFis); { asociaza f la numeFis }
Reset(f); { deschide f în citire }
While not EOF(f) do begin { cat timp nu s-a ajuns la
sfarsit }
ReadLn(f, linie); { citeste o linie din fişier }
Inc(nrLinie); { incrementeaza contorul }
WriteLn(nrLinie:5, ' ', linie);
If nrLinie mod 20 = 0 then begin
Asteapta;
{ClrScr;}
nrPagina := nrPagina + 1;
WriteLn('Continutul fişierului ', numeFis, ' este:
', 'Pag. ', nrPagina:3);
end
end;
if nrLinie mod 20 <> 0 then Asteapta;
Close(f);
{Fictiva;}
Until False
end. { CitireT }
2.4.2. Fişiere cu tip
Fişierele cu tip (pe care le numim şi fişiere record) sunt accesate
prin intermediul unei variabile fişier declarată astfel:
var
var_fis: file of tip_componenta;
sau, mai elegant:
type
tip_componenta = ... { definitia tipului componentei }
tip_fişier = file of tip_componenta;
var
var_fis: tip_fişier;
Fişierele cu tip respectă definiţia generală a fişierului,
precizată la începutul acestei secţiuni: ele conţin componente de
acelaşi tip, notat mai sus prin tip_componenta. Tipul componentei
poate fi orice tip recunoscut de sistemul de tipuri al limbajului, cu
excepţia tipului file.
Spre exemplu, următoarele tipuri de fişiere sunt tipuri valide:
type
fişier_integer = file of Integer;
fişier_boolean = file of Boolean;
fişier_persoane = file of Persoana; { tipul Persoana descris mai
sus }
Bufferul este o zona de memorie speciala, fără nume, care o vom nota
în cele ce urmează cu var_fis^(noţiunea de pointer este tratată în
capitoul următor). Iniţializarea variabilei fişier var_fis se face
prin apelul procedurii standard Assign; deschiderea fişierului se face
folosind procedurile standard Reset (în citire sau în scriere şi
citire) şi Rewrite (în scriere). Odată cu deschiderea, devine
accesibil şi bufferul fişierului, adică variabila var_fis^.
Bufferul trebuie considerat ca zona de memorie în care se citesc
informaţiile din fişierul extern, înainte ca acestea sa fie
atribuite variabilelor din program; similar, în buffer sunt depozitate
informaţiile care se doreşte a fi scrise în fişierul extern,
înainte ca scrierea sa aibă loc. Raţiunea de a fi a bufferului este
aceea de a optimiza (în general de a micşora) numărul de accese la
suportul extern, pe care se găseşte fişierul supus prelucrarii.
De obicei, operaţiile fizice de citire şi scriere pe suport extern
realizează transferul unei cantităţi fixe de informaţie, numită
bloc. Dimensiunea blocului depinde de caracteristicile fizice ale
suportului şi perifericului pe care se memorează fişierul. Din punct
de vedere logic, adică al fişierului prelucrat în programul Pascal,
o citire sau scriere logica realizează transferarea unei cantităţi
de informaţie egală cu dimensiunea unei componente a fişierului,
adică SizeOf(tip_componenta). De regulă, dimensiunea bufferului este
un multiplu al dimensiunii bloc
Pentru a simplifica lucrurile, considerăm că dimensiunile blocului,
bufferului şi componentei sunt egale. Folosind declaraţia:
type
tip_componenta = Integer;
tip_fişier = file of tip_componenta;
var
var_fis: tip_fişier;
componenta: tip_componenta;
vom deschide acum în citire fişierul TEST.DAT şi vom putea accesa
deja prima componentă a lui:
Begin
Assign(var_fis, 'TEST.DAT');
Reset(var_fis);
componenta := var_fis^
End.
Deschiderea provoacă şi setarea contorului de poziţie pe prima
înregistrare. Pentru a trece la următoarea componenta (adică pentru
a aduce în buffer următoarea componentă) se foloseşte o procedura
speciala, numita get.
Semantica acesteia este:
- aducerea în buffer a următoarei componente din fişier
- mărirea cu 1 a contorului de poziţie.
Prin urmare, dacă dorim o prelucrare completa a fişierului (de
exemplu afişarea fiecărei componente pe ecran), atunci programul de
mai sus s-ar scrie astfel:
Begin
Assign(var_fis, 'TEST.DAT');
Reset(var_fis);
While not Eof(var_fis) do begin
componenta := var_fis^;
get(var_fis);
WriteLn(componenta)
end;
Close(var_fis)
end.
Am văzut însă ca în Pascal exista procedura standard Read pentru
citirea din fişier. De fapt, semantica exacta a procedurii Read este
data în tabelul următor:
------------------------------------------------------------------
Procedura standard Este echivalenta cu
------------------------------------------------------------------
Read(var_fis, componenta) componenta := var_fis^;
get(var_fis);
-------------------------------------------------------
Procedura get detectează sfârşitul de fişier: când nu mai exista
o următoare înregistrare de citit, ea nu va întoarce nimic, iar
functia Eof(var_fis) va întoarce True, deci citirea fişierului se
termina.
Folosind procedura standard Read, programul de mai sus se scrie
astfel:
Begin
Assign(var_fis, 'TEST.DAT');
Reset(var_fis);
While not Eof(var_fis) do begin
Read(var_fis, componenta);
WriteLn(componenta)
end;
Close(var_fis)
end.
Scrierea în fişier
Folosind aceleaşi declaraţii:
type
tip_componenta = Integer;
tip_fişier = file of tip_componenta;
var
var_fis: tip_fişier;
componenta: tip_componenta;
i: Integer;
vom deschide acum în scriere fişierul TEST.DAT şi vom pune prima
componenta a lui în buffer:
Begin
Assign(var_fis, 'TEST.DAT');
Rewrite(var_fis);
var_fis^ := componenta
End.
Deschiderea în scriere provoacă ştergerea fişierului (daca acesta
există) şi setarea contorului de poziţie pe 0. Pentru a scrie o
componenta în fişier este nevoie ca aceasta sa fie trecută prima
dată în buffer (lucru realizat de ultima instrucţiune din program),
după care se foloseşte o procedură specială, numită put. Semantica
acesteia este:
Procedure put(var_fis)
- scrierea conţinutului bufferului în fişier
- mărirea cu 1 a contorului de poziţie.
Prin urmare, dacă dorim o prelucrare completa a fişierului (de
exemplu scrierea fiecărei componente în el), atunci programul de mai
sus s-ar scrie astfel:
Begin
Assign(var_fis, 'TEST.DAT');
Rewrite(var_fis);
For i := 1 to 10 do begin
componenta := i;
var_fis^ := componenta;
put(var_fis)
end;
Close(var_fis)
end.
Am văzut însă că în Pascal există procedura standard Write
pentru scrierea în fişier. De fapt, semantica exactă a procedurii
Write este data în tabelul urmator:
-------------------------------------------------------
Procedura standard Este echivalenta cu
-------------------------------------------------------
Write(var_fis, componenta) var_fis^ := componenta;
put(var_fis);
-------------------------------------------------------
In scriere, sfârşitul de fişier trebuie marcat. Acest lucru este
efectuat de procedura standard Close.
Folosind procedura standard Write, programul de mai sus se scrie
astfel:
Begin
Assign(var_fis, 'TEST.DAT');
Rewrite(var_fis);
For i := 1 to 10 do begin
componenta := i;
Write(var_fis, componenta)
end;
Close(var_fis)
end.
2.4.3. Fişiere fără tip (stream)
Fişierele fără tip pot fi considerate ca fiind fişiere cu tip în
care o înregistrare are un octet, şi tipul ei este Byte
type
file = file of byte;
Deoarece este greoaie manipularea înregistrărilor de 1 byte, la
fişierele fără tip se foloseşte un parametru nou, dimensiunea
înregistrării (bufferului), numit în engleza RecSize. Acest
parametru se precizeaza la deschiderea fişierului. dacă nu este
precizat, se consideră implicit valoarea 128. Procedurile standard
Reset şi Rewrite au forma generala:
procedure Reset(var var_fis ş: File; Recsize: Word ] );
procedure Rewrite(var F: File ş; Recsize: Word ] );
Pentru citirea şi scrierea din fişierele fără tip se folosesc
proceduri specifice, BlockRead şi BlockWrite.
Procedura BlockRead are sintaxa:
procedure BlockRead(var F: File; var Buf; Count: Word [; var Result:
Word]);
unde:
F Variabila fişier fără tip
Buf variabila de orice tip (de obicei un tablou de byte), de
lungime cel puţin egala cu RecSize
Count expresie de tip Word
Result variabila de tip Word
Semantica acestei proceduri este următoarea: se citesc cel mult Count
înregistrări (de lungime RecSize fiecare) din fişierul F în
variabila Buf (care joaca rolul bufferului). Numărul efectiv de
înregistrări citite este întors în parametrul opţional de ieşire
Result. dacă acesta lipseşte, se declanşează o eroare de
intrare-ieşire (detectabila prin folosirea lui IOResult) dacă
numărul de înregistrări citite este mai mic decât Count.
Pentru ca operaţia sa aibă sens, dimensiunea bufferului Buf trebuie
sa fie cel puţin egala cu Count * RecSize octeţi, dar nu mai mare
decât 64K:
65535 > SizeOf(Buf) > Count * RecSize
Daca Count * RecSize > 65535 se declanşează o eroare de
intrare-ieşire.
Parametrul de ieşire Result va avea valoarea (dacă este prezent în
apel) - egala cu Count dacă din fişier s-a putut transfera numărul
de octeţi precizat
- mai mic decât Count dacă în timpul transferului s-a detectat
sfârşitul de fişier; Result va conţine numărul de înregistrări
complete citit.
După terminarea transferului, contorul de poziţie al acestuia se
măreşte cu Result înregistrări.
Procedura BlockWrite are sintaxa:
procedure BlockWrite(var F: File; var Buf; Count: Word [; var Result:
Word]);
unde:
F Variabila fişier fără tip
Buf variabila de orice tip (de obicei un tablou de byte), de
lungime cel puţin egala cu RecSize
Count expresie de tip Word
Result variabila de tip Word
Semantica acestei proceduri este următoarea: se scriu cel mult Count
înregistrări (de lungime RecSize fiecare) din variabila Buf în
fişierul F.
Numărul efectiv de înregistrări scrise este întors în parametrul
opţional de ieşire Result. Dacă acesta lipseşte, se declanşează o
eroare de intrare-ieşire (detectabila prin folosirea lui IOResult)
dacă numărul de înregistrări scrise este mai mic decât Count.
Pentru ca operaţia să aibă sens, dimensiunea bufferului Buf trebuie
să fie cel puţin egala cu Count * RecSize octeti, dar nu mai mare
decât 64K:
65535 > SizeOf(Buf) > Count * RecSize
Daca Count * RecSize > 65535 se declanşează o eroare de
intrare-ieşire.
Parametrul de ieşire Result va avea valoarea (daca este prezent în
apel)
- egala cu Count dacă s-a putut transfera în fişier numărul de
octeţi precizat
- mai mic decât Count dacă suportul pe care se face transferul se
umple; Result va conţine numărul de înregistrări complete scris
Dupa terminarea transferului, contorul de poziţie al acestuia se
măreşte cu Result înregistrări.
3. Structuri statice şi structuri dinamice. Liste
3.1. Liste. Structuri statice. Structuri dinamice.
Lista este o structura liniară şi dinamică de date.
Spunem ca o structura este liniara dacă ea este formata din elemente
care au o poziţie bine determinată în cadrul structurii:
- exista un unic element numit primul;
- exista un unic element numit ultimul;
- orice element (cu excepţia primului) are un predecesor
- orice element (cu excepţia ultimului) are un succesor.
Spunem că o structura este dinamică dacă numărul de elemente al ei
se modifică în timp. Cu alte cuvinte, spaţiul de memorie alocat
pentru respectiva structură are dimensiunea variabilă în timp: în
fiecare moment este alocată doar atâta memorie câtă este necesară
pentru a păstra elementele curente ale structurii.
Spunem că o structura este statică dacă numărul de elemente al ei
este fix în timp. Cu alte cuvinte, spaţiul de memorie alocat pentru
respectiva structură are dimensiunea fixă în timp.
Putem face o comparaţie între structurile de date tablou şi lista.
Ambele structuri sunt structuri liniare. Tabloul este o structura
statica, pe când lista este o structură dinamică.
Tabloul (aşa cum este el definit în Pascal) are un număr de
elemente cunoscut dinainte. Spunem ca tabloul este o structură
statică. Examinând definiţia structurii liniare, constatăm că
tabloul verifică această definiţie:
- fiecare element este memorat în tablou într-o singura
locaţie, definită de valoarea unui 'indice'
- pentru un tablou cu n elemente, indicii variază de regulă de
la 1 la n
- exista un unic element numit primul, acela cu indicele cel mai
mic
- exista un unic element numit ultimul, acela cu indicele cel mai
mare
- primul element al tabloului are indicele 1 şi nu are predecesor
- ultimul element al tabloului are indicele n şi nu are succesor
- orice alt element de indice i (1 < i < n) are
un predecesor: elementul de indice i-1
un succesor: elementul de indice i+1
Tabloul este o structura statică pentru că înainte de alocarea lui
în memorie trebuie cunoscut n - numărul de elemente al său. Prin
urmare, indiferent câte elemente din tablou vor fi folosite efectiv,
se va aloca spaţiu pentru toate.
Lista este o structura dinamica: iniţial ea este vidă, deci nu
conţine nici un element, iar spaţiul de memorie alocat are
dimensiunea 0. Pe măsura ce apar (se produc) elemente care trebuie
incluse în listă, se alocă spaţiu pentru ele şi se face
includerea, stabilindu-se prin aceasta poziţia pe care elementul
inclus o ocupă în cadrul listei. Nu exista teoretic nici o
restricţie privitoare la locul unde se include un nou element în
lista; includerea se poate face fie la începutul ei (înaintea
primului element din ea), fie undeva la mijlocul ei (intre primul şi
ultimul element), fie la sfârşitul listei, după ultimul element.
În mod analog, din lista se pot scoate elemente. Scoaterea unui
element din listă înseamnă refacerea legăturilor între elementul
dinaintea şi cel de după elementul care se scoate.
Elementele listei se numesc noduri.
Lista este astfel organizată încât fiecare nod al ei conţine:
- informaţia utilă din nod
- adresa nodului precedent (predecesorul nodului curent)
- adresa nodului următor (succesorul nodului curent).
În terminologia listelor, operaţiile de mai sus se numesc:
- inserare: adăugarea unui nod nou la lista
- ştergere: ştergerea unui nod din lista
- parcurgere (traversare): inspectarea nodurilor din listă,
începând cu
primul şi terminând cu ultimul.
Adresele nodului precedent şi următor formează ceea ce numim
„informaţie de înlănţuire”, iar structura de date lista cu
nodurile definite ca mai sus se numeşte în practica lista dublu
înlănţuită. Aceasta înseamnă că, dacă ne aflăm într-un nod,
putem să parcurgem lista fie spre începutul acesteia (folosind adresa
nodului precedent) fie spre sfârşitul acesteia (urmând adresa
nodului următor).
3.2. Lista simplu înlănţuită
Lista simplu înlănţuită este un caz particular de listă, în
nodurile căreia se păstrează fie adresa nodului precedent, fie
adresa nodului următor.
O listă simplu înlănţuită (listă liniară simplu înlănţuită)
este un şir de elemente dintr-o anumită mulţime. Fiecare element al
unei liste ocupă o zonă de memorie (locaţie) formată din două
componente: INFORMAŢIA şi LEGĂTURA.
Memorarea listelor se face prin alocarea unor zone de memorie pentru
elementele acesteia în două moduri:
a) Alocarea secvenţială constă în memorarea elementelor listei în
locaţii aflate la adrese succesive în memorie, pornind de la o
adresă de bază, adresa primului element din listă. Fiecare element
din listă poate fi identificat conform ordinii în listă.
Un exemplu, pe care l-am studiat, de astfel de liste, sunt tablourile.
Fiecare element se identifică prin indicele său în tablou, iar
informaţia se află în locaţia T(i1, i2,…,in).
b) Alocarea înlănţuită presupune ca fiecărui element din listă
să i se aloce o zonă corespunzătoare în care se păstrează
INFormaţia şi adresa de LEGătură la care se află următorul
element, sub forma:
Cap
Prim INF LEG
16 INF LEG
80 INF LEG
44 INF LEG
Nil Coada
Ultim
3 3 16 80 44 44
Sub fiecare locaţie am precizat adresa la care se află şi valorile
corespunzătoare pentru primul şi ultimul element. Se observă că
locaţiile de memorie nu au adrese succesive. Avantajul alocării
înlănţuite este că se foloseşte doar atâta zonă de memorie cât
este necesară şi se poate folosi orice zonă liberă la un moment
dat.
Operaţii elementare asupra listelor:
Inserarea unui element, într-un anumit loc, în listă (la cap, la
coadă, în interiorul listei);
Ştergerea unui element din listă (eliminarea din listă);
Parcurgerea elementelor unei liste, deci accesul la elementele sale,
fie prin poziţia în listă fie prin valoarea informaţiei.
Concatenarea listelor.
Tipuri de liste simplu înlănţuite
În funcţie de operaţiile pe care le putem aplica listelor liniare,
precum şi a locului în care acestea se efectuează, distingem
următoarele tipuri de liste:
a) lista liniară simplu înlănţuită – inserarea şi ştergerea
elementelor se face oriunde în listă.
b) Stiva (lista LIFO, Last în First Out, ultimul intrat va fi primul
ieşit, inserarea şi ştergerea se realizează la acelaşi capăt, Cap
sau Prim)
c) Coada (lista FIFO, First în First Out, primul intrat va fi primul
ieşit, inserarea şi ştergerea se realizează la capete diferite,
Coada sau Ultim respectiv Cap sau Prim)
d) Lista circulară (lista nu are capete, legătura ultimului element
se face spre primul element)
3.2.1. Specificarea structurii de date listă simplu înlănţuită
Structura de date listă simplu înlănţuită pe care o prezentăm
în continuare are operaţii proprii în funcţie de tipul structurii:
- structurilor liniare: poziţionare (primul, ultimul, precedentul,
următorul), element curent, căutare, traversare
- structurilor dinamice: creare, inserare, ştergere, eliberare
Specificarea unei structuri de date cuprinde următoarele secţiuni:
- Elemente: precizează informaţii despre elementele conţinute în
structură
- Structura: precizează informaţii despre legăturile dintre
elemente
- Domeniu: precizează câmpurile structurii
- Operaţii: precizează operaţiile efectuate asupra structurii
Specificarea unei operaţii se face prin:
Nume: numele operaţiei
Parametri: parametrii operaţiei, numele lor
Precondiţie: predicat referitor la datele de intrare condiţiile
în care se poate executa operaţia
Postcondiţie: predicat referitor la datele de ieşire condiţiile
pe care le satisfac acestea, legătura dintre datele de intrare şi
datele de ieşire
Specificarea structurii de date listă simplu înlănţuită
Elemente: Toate elementele sunt de acelaşi tip, desemnat prin TNod
şi se numesc noduri. Un nod conţine informaţie utilă, de tipul
TInfo
Structura: Lista simplu înlănţuită are o structura liniara.
Există un nod numit primul şi un nod numit ultimul. Fiecare nod (cu
excepţia ultimului) conţine în el adresa nodului următor.
Domeniu: Lista are două câmpuri, Cap şi Cursor. Cap refera
primul element al sau, iar Cursor refera elementul curent.
Operaţii:
Creeaza(L) - creează o listă L vidă
Pre: True
Post: L este vidă (L.Cap şi L.Cursor nu referă nimic)
L.Cap = L.Cursor = Nil
Vidă(L) - testează dacă L este vidă
Pre: True
Post: vidă = True dacă L este vidă şi vidă = False în caz
contrar
Insereaza(L, I) - inserează în L un nod nou (care conţine
informaţia utila I), pe poziţia cursorului
Pre: True
Post: L.Cap[Info] = I şi L.Cursor = L.Cap (daca L.Cursor = Nil)
sau dacă L.Cursor <> Nil, atunci L.Cursor[Urm] = nodul nou inserat şi
apoi L.Cursor := nodul nou inserat
Sterge(L) - sterge din L nodul referit de L.Cursor
Pre: L nu este vidă şi L.Cursor refera un nod existent în L
Post: nodul referit de L.Cursor este şters şi nodul din capul
listei devine nod curent (este referit de L.Cursor)
Modifica(L, I) - modifica informaţia utilă din nodul referit de
cursor
Pre: L este nevidă
Post: informaţia utila din nodul referit de cursor are valoarea I
Extrage(L, I) - extrage informaţia utila din nodul referit de
cursor
Pre: L este nevidă
Post: I primeşte valoarea informaţiei utile din nodul curent
Elibereaza(L) - şterge din L toate nodurile
Pre: True
Post: L este vidă
Cauta(L, I) - caută în L nodul cu informaţia utila I
Pre: True
Post: Informaţia utila din nodul curent este I şi Caută = True
( dacă exista în L un nod cu informaţia utila I )
sau
L.Cursor rămâne nemodificat şi Cauta = False
( dacă nu exista în L un nod cu informaţia utila I )
Primul(L) - poziţionează L.Cursor pe primul element din lista
Pre: L este nevidă
Post: L.Cursor := L.Cap
Ultimul(L) - poziţionează L.Cursor pe ultimul element din lista
Pre: L este nevidă
Post: L.Cursor refera ultimul element din lista
Precedentul(L, Esec)
Pre: L este nevidă
Post: L.Cursor refera nodul precedent lui L.Cursor şi Esec =
False
(daca L.Cursor nu refera primul nod din lista)
sau
L.Cursor rămâne nemodificat şi Esec = True
(dacă nu există un nod precedent celui curent )
Urmatorul(L, Esec)
Pre: L este nevidă
Post: L.Cursor refera nodul următor lui L.Cursor şi Esec = False
(daca L.Cursor nu referă ultimul nod din listă)
sau
L.Cursor rămâne nemodificat şi Esec = True
(dacă nu există un nod următor celui curent )
Traverseaza(L)
Pre: True;
Post: Parcurge toate nodurile listei, începând de la primul
(L.Cap) şi până la ultimul. L.Cursor nu se modifică.
3.3. Tipuri de liste simplu înlănţuite
3.3.1. Stiva
Un exemplu clasic de stivă este “stivuirea unor cutii care au un
anumit conţinut”. Este evident că doar asupra cutiei din vârful
stivei putem să acţionăm.
Stivele permit trei operaţii elementare: inserarea la vârf,
ştergerea de la vârf şi parcurgerea.
În descrierile algoritmilor, pentru operaţiile pe stivă, vom
folosi în reprezentarea generală a unui element dintr-o listă tipul
de date articol care are structura:
Element = articol
leg: adresa_element;
inf: informaţia_de_un_anumit_tip;
unde
Adresa_element = adresa_unei_zone_ de_memorie
Vom folosi variabilele
p, q, vârf : adresa_element;
Prin leg [p] şi inf [p] vom înţelege legătura şi informaţia
aflată la adresa p.
leg [p] este de tip adresa_element, iar inf [p] este de tip
informaţia_de_un_ anumit_tip.
Pentru stiva vidă avem vârf = nil.
Alocarea unei zone noi de memorie se realizează cu aloc (
adresa_element)
Disponibilizarea unei zone de memorie se realizează cu disp
(adresa_element).
Inserarea unui element în vârful stivei (deci vârf are o anumită
valoare)
Aloc (p); {alocarea memorie pentru noul element}
inf [p] = <expresie>; {atribuirea valorii zonei de informaţie}
leg [p] = vârf; {adresa_de_legătură a noului element este vârf}
vârf = p; {noul vârf se află acum la noua adresă p }
Ştergerea unui element din vârful stivei (deci vârf are o anumită
valoare)
P = vârf; {se salvează adresa vârfului pentru a nu se pierde}
Vârf = leg[p]; {noua adresă a vârfului este legătura celui vechi}
Disp ( p ); {se disponibilizează (şterge) zona de adresă p}
Parcurgerea elementelor unei stivei pornind din vârf.
P = vârf; {se salvează adresa vârfului pentru a nu se pierde}
Cât timp p <> nil execută{condiţia poate fi schimbată după
cerinţele de parcurgere}
{Operaţie asupra elementului de la adresa p}
p = leg[p]; {noua adresă a elementului p}
sf cât timp;
Exerciţii:
Pentru exemplificare studiaţi problemele de la secţiunea de
verificare şi soluţiile din anexă.
3.3.2. Coada
Coada (coada de aşteptare) este o listă liniară simplu
înlănţuită cu proprietăţile:
Inserarea unui element se face numai la coada stivei, numit ultim
element al stivei.
Ştergerea unui element se face numai la capul stivei, numit prim
element al stivei.
Legătura elementului din coada stivei, numit ultim, este nil (nimic).
Cap
Prim INF LEG
16 INF LEG
80 INF LEG
44 INF LEG
Nil Coadă
Ultim
70 70 16 80 44 44
Un exemplu clasic de coadă este “Trecerea vagoanelor, pe o linie de
cale ferată, printr-un tunel, într-un singur sens”. Este evident
că vagoanele intră şi ies în aceeaşi ordine. Deci locomotiva,
vagonul 1, 2, etc.
Cozile permit trei operaţii elementare: inserarea la coadă (ultim),
ştergerea de la cap (prim) şi parcurgerea.
În descrierile algoritmilor, pentru operaţiile asupra cozilor, vom
folosi în reprezentarea generală aceleaşi notaţii ca în cazul
stivelor:
Vom folosi variabilele
p, q, prim, ultim : adresa_element;
Pentru iniţializarea cozii avem:
aloc (prim);
leg [prim] = nil;
ultim = prim;.
Alocarea unei zone noi de memorie se realizează cu aloc (
adresa_element)
Disponibilizarea unei zone de memorie se realizează cu disp
(adresa_element).
Inserarea unui element în coadă, deci ultim are o anumită valoare.
Aloc (p); {alocarea memorie pentru noul element}
inf [p] = <expresie>; {atribuirea valorii zonei de informaţie}
leg [p] = nil; {p fiind ultimul element, adresa de legătură este
nil}
leg [ultim] = p; {adresa_de_legătură a ultimului element este noul
p}
ultim = p; {noul ultim se află acum la noua adresă p }
Ştergerea unui element din coadă, deci prim are o anumită valoare)
P = prim; {se salvează adresa lui prim pentru a nu se pierde}
prim = leg[prim]; {noua adresă a lui prim este legătura sa}
Disp ( p ); {se disponibilizează (şterge) zona de adresă p}
Parcurgerea elementelor unei cozi pornind de la prim.
P = prim; {se salvează adresa prim pentru a nu se pierde}
Cât timp p <> nil execută {condiţia poate fi schimbată după
cerinţele de parcurgere}
{Operaţie asupra elementului de la adresa p}
p = leg[p]; {noua adresă a elementului p}
sf cât timp;
Exerciţii:
Pentru exemplificare studiaţi problemele de la secţiunea de
verificare şi soluţiile din anexă.
3.3.3. Lista circulară
Lista circulară este o listă liniară simplu înlănţuită,
definită în mod similar cu coada. În plus are proprietatea că:
leg [ ultim ] = prim;
Pe lângă operaţia de parcurgere care este similară cu cea de la
coadă, operaţiile de inserare şi ştergere se pot efectua la orice
adresă q convenabilă.
Inserarea după elementul de la adresa q.
Aloc (p); {alocarea memorie pentru noul element}
inf [p] = <expresie>; {atribuirea valorii zonei de informaţie}
leg [p] = leg [q] ; {adresa de legătură a lui p este cea a lui q}
leg [q] = p; {adresa_de_legătură a lui q este noul p}
Ştergerea elementului de după elementul de la adresa q ( leg [q]).
P = leg[q]; {se salvează adresa lui leg [q] pentru a nu se pierde}
leg[q] = leg[p]; {noua legătură a lui q este legătura lui p}
Disp ( p ); {se disponibilizează (şterge) zona de adresă p}
3.4. Lista dublu înlănţuită
Aşa cum am definit lista dublu înlănţuită în paragraful 3.1.,
este o listă în care un element este format din INFormaţie şi două
adrese de legătură, înspre elementul PREdecesor şi respectiv
SUCcesor. Lista dublu înlănţuită are două capete pe care le vom
nota la fel ca în cazul cozii cu prim şi respectiv ultim.
Cap
Prim Nil INF SUC
16 PRE
70 INF SUC
44 PRE
16 INF SUC
Nil Coadă
Ultim
70 70 16 44 44
Definiţia unui element al listei dublu înlănţuite:
Element = articol
pre: adresa_element;
suc: adresa_element;
inf: informaţia_de_un_anumit_tip;
Pe lângă operaţia de parcurgere care este similară cu cea de la
coadă sau stivă, cu diferenţa că deplasarea se face spre PRE sau
spre SUC, operaţiile de inserare şi ştergere se pot efectua la orice
adresă q convenabilă.
Inserarea înaintea elementului de la adresa q.
Aloc (p); {alocarea memorie pentru noul element}
inf [p] = <expresie>; {atribuirea valorii zonei de informaţie}
pre [p] = pre [q] ; {legătura pre a lui p este legătura pre a lui q}
suc [p] = q ; {suc lui p este q}
suc [ pre [p]] = p; {predecesorul lui p are ca succesor pe p}
pre [q] = p; {adresa_de_legătură a lui q este noul p}
Exerciţiu:
Verificaţi pentru lista din figura de mai sus presupunând noua
adresă a lui p=60 şi q=16.
Ştergerea elementului aflat la adresa succesorului lui q (deci de la
suc [q]).
P = suc[q]; {se salvează adresa lui suc [q] pentru a nu se pierde}
suc[q] = suc[p]; {noul succesor a lui q este lui p}
pre [suc[p]] = q; { succesorul lui p are ca predecesor pe p}
Disp ( p ); {se disponibilizează (şterge) zona de adresă p}
Exerciţiu:
Verificaţi pentru lista din figura de mai sus presupunând q=70.
Listele dublu înlănţuite se folosesc la reprezentarea arborilor
binari, despre care vom vorbi în continuare.
4. Structuri de date dinamice
4.1. Tipuri de variabile (după durata de viaţă)
1) globale
- declarate în programul principal
- alocate în segmentul de date
- durata lor de viata este durata de execuţie a programului
- se iniţializează la declarare cu valori identice lui 0 (0
pentru numere, stringul vid pentru string-uri, mulţimea vida pentru
mulţimi, etc) - în Borland (Turbo) Pascal 7.0
2) locale unui subprogram
- sunt formate din
- variabilele declarate în subprogramul respectiv
- parametrii transmişi prin valoare
- sunt alocate în stiva de execuţie
- alocarea se face automat, când subprogramul de care ele ţin este
lansat în execuţie = înregistrarea de activare a acestuia este pusa
în stiva de execuţie (vezi CTRL+F3)
- dealocarea se face automat, când subprogramul îşi termină
execuţia
- în stiva de execuţie pot fi mai multe subprograme
- cel din vârful stivei este cel activ (care se execută curent)
- celelalte au apelat fiecare subprogramul de deasupra lor din stiva
- nu sunt iniţializate automat
3) dinamice
- nu au un nume propriu (se numesc 'anonime')
- sunt referite prin intermediul pointerilor
- sunt alocate şi dealocate de către programator
- sunt alocate în memorie în "heap"
heap = grămada, ansamblu, zona de memorie dinamică
= împreuna cu stiva de execuţie ocupă porţiunea de
memorie rămasă ne ocupată de programul executabil (cod + segmentul
de date), fiecare pornind de la un capăt spre mijloc
Deosebirea dintre stiva şi heap constă în:
- stiva este o zonă de memorie de dimensiune fixa, numit
segment de memorie, (in Pascal minim 16384, maxim 65536 bytes) care
permite stocarea programelor şi a variabilelor la executarea acestora.
Apelarea subprogramelor permite alocarea sau dealocarea de memorie
pentru variabilele locale. Alocarea pe stivă se face static la
executarea programelor.
- heap-ul este o zonă de memorie formată din totalitatea
segmentelor de memorie disponibile pe un sistem de calcul. În Pascal
pentru Windows dimensiunea maximă ce poate fi alocată pe heap este de
655360 bytes, iar în UNIX (FreePascal) dimensiunea depinde doar de
memoria RAM a sistemului, disponibilă la momentul alocării. Alocarea
se face dinamic.
- dimensiunea creste sau descreşte după cum apar
instrucţiuni de alocare sau dealocare de variabile dinamice
- este format din blocuri de memorie (segmente)
- are o lista de blocuri libere
- pe măsura ce se fac alocări şi dealocări, heap-ul
este tot mai fragmentat
- funcţii Turbo (Borland) Pascal pentru heap:
- MaxAvail - dimensiunea celui mai mare bloc liber
- MemAvail - suma dimensiunilor blocurilor libere
4.2. Tipul pointer
Este un tip de date definit de utilizator şi are la bază
următoarele elemente:
a) domeniu
- valorile sale sunt adrese de memorie ale altor obiecte din
program (variabile, subprograme)
- mai exact: mulţimea valorilor adreselor din memoria RAM
disponibila programului, plus o valoare particulară notată (în
Pascal) cu Nil
b) operaţii
- de atribuire: (:=)
- de comparare: (= şi <>)
- de alocare a variabilei dinamice referite de pointer:
New (Pascal standard) şi GetMem (in Turbo şi Borland
Pascal)
- de dealocare a variabilei dinamice referite de pointer:
Dispose (Pascal standard) şi FreeMem (in Turbo şi Borland
Pascal)
4.2.1. Declararea tipului pointer
Variabilele de tip pointer referă alte obiecte. Deoarece Pascal este
un limbaj puternic tipizat, tipul unui pointer (TP) va indica tipul
obiectelor referite de variabilele de tipul pointer TP:
type
tip_pointer = ^tip_de_baza
va indica faptul că orice variabilă de tipul "tip_pointer" va avea
ca valoare o adresă a unei variabile (obiect) de tipul "tip_de_baza".
Această declaraţie introduce un nou tip de date, cu numele
"tip_pointer" în sistemul de tipuri al programului în care ea apare,
după toate regulile cunoscute.
Tipul de date "tip_de_baza" poate fi
- predefinit
- definit deja (declaraţia lui apare înaintea declaraţiei lui
"tip_pointer"
- definit după declaraţia de mai sus (numai în cazul declaraţiei
tipului pointer se permite ca un nume (in cazul nostru "tip_de_baza"
să fie referit înainte de a fi declarat
Exemple: (vom prefixa cu P numele tipurilor pointer şi cu T numele
celorlalte tipuri de date definite)
type
PInteger = ^Integer; { variabilele de tip PInteger vor fi pointeri la
întregi, adică vor conţine adresa unor variabile de tip Integer }
TVector = Array[1..10] of Real;
PVector = ^TVector; { TVector a fost definit înainte de PVector
}
PMatrice = ^TMatrice; { TMatrice este definit după }
TMatrice = Array[1..5, 1..10] of Integer;
Limbajele Borland şi Turbo Pascal au un tip pointer predefinit cu
numele Pointer. Acest tip se refera la pointeri fără tip şi se poate
folosi în conversii sau în explicarea polimorfismului.
Exemplu:
var
p: PMatrice;
q: Pointer;
begin
New(p); { aloca p^ }
q := p; { atribuire corectă }
p := q; { eroare de compilare, atribuire de tip
incorectă }
p := PMatrice(q); { conversie explicita de pointeri }
end.
4.2.2. Declararea de variabile de tip pointer
Odată declarat tipul pointer, se pot declara variabile de tipul sau,
respectiv declaraţia normala a variabilelor.
Exemple:
var
pi: PInteger;
pi2: ^Integer; { tipul ^Integer este un tip anonim }
v: PVector;
m: PMatrice;
4.3. Semantica variabilelor de tip pointer. Operaţii
4.3.1. Variabile pointer şi variabile dinamice asociate
Ori de câte ori lucrăm cu variabile de tip pointer, trebuie să
ştim că o astfel de variabilă are o dublă semnificaţie (sau că
avem de-a face cu două variabile, total diferite una de alta). Cele
două variabile au sensul:
1) variabilei pointer obişnuită, notat prin numele variabilei, care
are
- un domeniu de vizibilitate (dat de locul în care apare
declaraţia sa)
- o durată de viaţă (variabila poate fi globala, locala sau
dinamică)
- o valoare (adresa unui alt obiect din memorie)
2) obiectului pe care îl referă variabila pointer (a cărui adresa o
conţine ca valoare), notat prin numele variabilei pointer urmat de ^
Exemplu:
var
pi: PInteger;
- pi este o variabila pointer de tipul PInteger, deci ea poate
conţine adresa unei variabile de tip Integer din program
- pi^ este variabila de tip Integer a cărei adresă este
conţinută de pi.
Terminologie
pi este variabila pointer
pi^ este variabila dinamica referita de pi
4.3.2. Operaţia de atribuire. Semantica.
Având de-a face cu două variabile distincte, semantica operaţiei de
atribuire trebuie discutată pentru fiecare caz în parte:
a) Atribuirea de pointeri
Pentru declaraţia
var
pi1, pi2: PInteger;
atribuirea
pi1 := pi2;
are semnificaţia
- se atribuie lui pi1 valoarea lui pi2, adică
- pi1 va conţine aceeaşi valoare ca şi pi2
- ele vor referi aceeaşi variabilă dinamică, adică după
atribuire
pi1^ şi pi2^ vor referi acelaşi obiect
b) Atribuirea de valori (ale variabilelor dinamice)
Pentru declaraţia
var
pi1, pi2: PInteger;
atribuirea
pi1^ := pi2^;
are semnificaţia
- se atribuie lui pi1^ valoarea lui pi2^, adică
- pi1^ va conţine aceeaşi valoare ca şi pi2^
- pi1 şi pi2 vor referi variabile dinamice diferite;
- valoarea variabilei dinamice pi2^ este atribuita variabilei
dinamice pi1^
- pi1^ şi pi2^ rămân în continuare obiecte diferite, însă ele
vor avea aceeaşi valoare
c) Lucrul cu obiecte existente în program prin intermediul
pointerilor
Pentru declaraţiile
var
pi: PInteger;
i: Integer;
instrucţiunea de atribuire
pi := Addr(i)
are efectul unei atribuiri de pointeri
- funcţia Addr(o) întoarce adresa unui obiect o din memoria
programului
- în cazul nostru, Addr(i) întoarce adresa variabilei i
Exemplu: Programul PtrDemo1.PAS
4.3.3. Alocarea variabilelor dinamice şi iniţializarea pointerilor
In lucrul cu pointeri, distingem în mod normal următoarele momente:
- declararea tipurilor pointer pe care vrem sa le folosim
- declararea variabilelor de tip pointer, acolo unde vrem sa le
folosim
- alocarea variabilelor dinamice referite de pointeri
- lucrul propriu-zis cu pointeri
- dealocarea variabilelor dinamice referite de pointeri
Atribuirea de valori unei variabile pointer se face în Borland Pascal
prin:
- folosirea procedurilor standard New şi GetMem
- folosirea operatorului @ ('at')
- folosirea functiei Addr
- folosirea functiei Ptr.
Dintre acestea, New şi GetMem realizează şi alocarea în heap a
variabilei dinamice referită de pointer.
Există o valoare constantă, notată cu Nil, care semnifica faptul
că pointerul care are aceasta valoare nu refera nimic (nu exista
încă variabila dinamică referită de el).
Procedura standard New are declaraţia:
Procedure New(var P: Pointer);
şi care realizează următoarele:
- alocă variabila dinamică P^
- atribuie ca valoare lui P adresa variabilei dinamice P^.
Tipul Pointer din declaraţie este unul general. Procedura primeşte
ca parametru o variabila P de orice tip pointer recunoscut de sistemul
de tipuri. Alocarea variabilei dinamice P^ se va face în funcţie de
tipul lui P.
Faţă de limbajul Pascal standard, există în Borland şi Turbo
Pascal extensii ale procedurilor de alocare şi dealocare New şi
Dispose, care vor fi discutate la programarea orientată pe obiecte
(GetMem, FreeMem şi @).
Lucrul cu variabile pointer înseamnă operaţii de atribuire şi
comparare.
Trebuie avute în vedere următoarele:
- prima operaţie asupra unei variabile pointer este iniţializarea
acesteia, care se poate face:
- prin New, GetMem, @, Addr sau Ptr
- prin atribuire de pointeri
- prin atribuire de pointeri se pierde vechea valoare a variabilei
dinamice care apare în partea stângă a operatorului de atribuire
Exemplu: la atribuirea
pi1 := pi2;
vechea valoare a lui pi1 (deci adresa variabilei dinamice pi1^) se va
pierde; în locul ei se va trece (scrie peste) adresa variabilei
dinamice pi2^).
- durata de viaţă a variabilei p^ poate să depăşească domeniul
de vizibilitate al variabilei p.
Exemplu: Programul DuV_Ptr;
4.3.4. Dealocarea variabilelor dinamice
După ce am terminat lucrul cu o variabilă dinamică, ea trebuie
dealocată explicit. Dealocarea se face în funcţie de modul în care
s-a făcut alocarea după cum urmează
Alocarea s-a făcut cu Dealocarea se face cu
---------------------------------------------------
New Dispose
GetMem FreeMem
---------------------------------------------------
Procedura standard Dispose are declaraţia
Procedure Dispose(var P: Pointer);
ea realizează
- dealocarea din heap a variabilei dinamice referite de P, adică a
lui P^
- zona ocupată de P^ este pusă în lista de blocuri libere a
heap-ului
- deiniţializarea valorii lui P: referirea lui P după Dispose(P)
provoacă o eroare de execuţie.
Exemplu complex de lucru cu Pointeri: COMPLEXP.PAS, unit-ul
UCOMPL_P.PAS
Aplicaţie (p434.pas):
Să se verifice dacă trei puncte date prin coordonatele lor
carteziene sunt vârfurile unui triunghi echilateral.
Program triunghi_echilateral;
uses crt;
TYPE punct=record
a,o:real;
end;
Var A,B,C :^punct;
Lab,Lac,Lbc :real;
Begin
clrscr;
New(A);
Write('A.a=');readln(A^.a);
Write('A.o=');readln(A^.o);
New(B);
Write('B.a=');readln(B^.a );
Write ('B.o=');readln(B^.o);
New(C);
Write('C.a=');readln(C^.a );
Write('C.o=');readln(C^.o);
LAB:=sqrt(sqr(A^.a-B^.a)+sqr(A^.o-B^.o));
LBC:=sqrt(sqr(B^.a-C^.a)+sqr(B^.o-C^.o));
LAC:=sqrt(sqr(A^.a-C^.a)+sqr(A^.o-C^.o));
Dispose(A);Dispose(b);Dispose(C);
If (LAB=LBC)and(LBC=LAC) then
Writeln('ABC- echilateral')
Else
Writeln('ABC- nu este echilateral');
Readln
End.
4.3.5. Probleme propuse
1. Se dau coordonatele carteziene a patru puncte. Sa se verifice dacă
ele sunt vârfurile unui dreptunghi. Se va folosi tipul punct definit
în aplicaţia anterioară.
2. Să se afişeze ora exactă şi data exactă folosind variabile
alocate dinamic.
3. Să se afişeze cel mai mare divizor comun şi cel mai mic multiplu
comun a două numere naturale memorate dinamic.
4. Se dau 4 puncte prin coordonatele lor carteziene şi un cerc prin
centrul său şi rază. Să se afişeze numărul de puncte interioare
şi exterioare cercului.
5. Se dau 2 numere complexe. Să se scrie un program care permite
efectuarea următoarelor operaţii: suma, diferenţa, modul, conjugat,
produs, cât şi putere.
Se va folosi tipul complex definit astfel:
TYPE complex=^element;
Element=Record
Re, Im:real;
End;
4.4. Structuri de date dinamice. Aplicaţii.
Structurile date dinamice sunt structuri de date cu număr variabil de
componente. Aceste structuri folosesc alocarea dinamică fiind mult mai
avantajoase din punct de vedere al utilizării judicioase a memoriei
în comparaţie cu cele statice. În general o componentă a unei
structuri dinamice are forma:
Informaţie adrese de legătura cu
componenta următoare
Clasificarea structurilor de date dinamice:
a) În funcţie de tipul de legătură
liste liniare - componentele structurii se află pe un singur nivel,
legătură 1:1.
. . .
arbori – componentele structurii sunt grupate pe niveluri.
reţele – între componentele structurii pot exista legături între
oricare elemente
în general asupra (nodurilor) componentelor unei structuri se fac
următoarele operaţii:
introducere de componente
ştergeri de componente
parcurgere a componentelor şi prelucrarea informaţiilor asociate
În continuare vom prezenta câteva cazuri speciale de liste liniare
(stiva, coada, liste simplu înlănţuite, liste dublu înlănţiute
şi liste circulare) alocate dinamic.
În TurboPascal un nod din listă va fi utilizat prin variabile de tip
reper definit astfel:
TYPE reper=^Element;
Element=record
Informatie:tip;
Leg:reper;
End;
Observaţie:
În TurboPascal orice tip folosit trebuie declarat anterior. Pentru
tipul reper este permisă folosirea unui tip şi declararea lui
ulterioară. Aici este singurul loc unde TurboPascal face această
concesiune.
4.4.1. Aplicaţia stiva (p441.pas):
a) Să se construiască o stivă cu numere naturale, citirea numerelor
terminându-se cu 0 (care nu face parte din stivă);
b) Să se afişeze numerele din stivă;
c) Să se şteargă componenta din vârful stivei;
d) Să se afişeze numerele din stivă după ştergerea componentei de
la pct. c).
program stiva;
uses crt;
type reper=^element;
element=record
inf:word;
leg:reper;
end;
var
vf:reper;
procedure creare(var vf:reper);
var n:word;
p:reper;
begin
vf:=nil;
write('numar=');readln(n);
while n<>0 do
begin
new(p);
p^.inf:=n;
p^.leg:=vf;
vf:=p;
write('numar=');readln(n);
end;
end;
procedure afisare(vf:reper);
begin
if vf=nil then
writeln('stiva vidă')
else
repeat
write(vf^.inf,' ');
vf:=vf^.leg;
until vf=nil;
end;
procedure stergere(var vf:reper);
var p:reper;
begin
p:=vf;
vf:=vf^.leg;
dispose(p);
end;
begin{p.p.}
writeln('a) creare stiva');
creare(vf);
writeln('b) afisare');
afisare(vf); writeln;
writeln('c) stergere...');
stergere(vf);
writeln('d) afisare după stergere');
afisare(vf);
end.
4.4.2. Aplicaţia coada (p442.pas):
a) Să se construiască o coadă cu numere naturale, citirea numerelor
se termină o dată cu introducerea numărului 0 (care nu face parte
din coadă).
b) Să se afişeze numerele din coadă.
c) Să se şteargă o componentă din coadă.
d) Să se afişeze componentele din coadă după operaţia de la
punctul c)
program coada;
uses crt;
type reper=^element;
element=record
inf:integer;
leg:reper;
end;
var p,u:reper;
procedure creare(var p,u:reper);
var q:reper; n:integer;
begin
write('nr=');readln(n);
p:=nil; {coada vina}
while n<>0 do
begin
new(q);
q^.inf:=n;
q^.leg:=nil;
if p=nil then
begin
p:=q;
u:=q;
end
else
begin
u^.leg:=q;
u:=q;
end;
write('nr=');readln(n);
end;
end; {creare}
procedure afisare(p,u:reper);
var q:reper;
begin
q:=p;
if q=nil then
writeln('coada vidă')
else begin
writeln('coada contine:');
repeat
write(q^.inf,' ');
q:=q^.leg
until q=nil
end;
writeln;
end;{afisare}
procedure stergere(var p,u:reper);
var q:reper;
begin
if p=nil then
writeln('Coada vidă!')
else
begin
q:=p;
if p=u then
p:=nil
else
p:=p^.leg;
dispose(q);
end;
end;{stergere}
begin {progr. principal}
clrscr;
writeln('a) creare coada');
creare(p,u);
writeln('b) afisare');
afisare(p,u);
writeln('c) stergere');
stergere(p,u);
writeln('d) afisare după stergere');
afisare(p,u);
readln;
end.
4.4.3. Aplicaţia lista simplu înlănţuită (p443.pas):
a) Să se construiască o listă simplu înlănţiută cu numere
naturale, citirea numerelor se termină o dată cu introducerea
numărului 0 (care nu face parte din coadă).
b) Să se insereze o componentă în listă după o componentă dată
prin informaţia ei.
c) Să se insereze o componentă în listă inaintea unei componente
dată prin informaţia ei.
d) Să se şteargă o componentă dată prin informaţia ei.
După fiecare subpunct se va afişa lista.
program l_s_i;
uses crt;
type reper=^element;
element=record
inf:integer;
leg:reper;
end;
var s1,s2:reper; info:integer;
procedure creare(var s1,s2:reper);
var q:reper; n:integer;
begin
new(s1);new(s2);
s1^.leg:=s2;
s2^.leg:=nil;
write('nr=');readln(n);
while n<>0 do
begin
new(q);
s2^.inf:=n;
q^.leg:=nil;
s2^.leg:=q;
s2:=q;
write('nr=');readln(n);
end;
end;{creare}
function adresa(s1,s2:reper;info:integer):reper;
{Aceasta functie returneaza adresa nodului cu
informatia egala cu cea a parametrului info}
var q:reper; sw:boolean;
begin
q:=s1^.leg;
sw:=false;
while (q<>s2) and (not sw) do
if q^.inf=info then
sw:=true
else
q:=q^.leg;
adresa:=q;
end;{adresa}
procedure inserare_i(info:integer);
var w,q,r:reper; n:integer;
begin
r:=adresa(s1,s2,info);
if r=s2 then
write('nu exista nodul inaintea caruia sa inseram')
else
begin
q:=s1;
while q^.leg<>r do
q:=q^.leg;
write('info din nodul inserat=');readln(n);
new(w);
w^.inf:=n;
w^.leg:=r;
q^.leg:=w;
end;
end;{inserare_i}
procedure inserare_d(info:integer);
var r,w:reper; n:integer;
begin
r:=adresa(s1,s2,info);
if r=s2 then
write('nu ex. nod după care sa inserez')
else
begin
new(w);
write('info=');readln(n);
w^.inf:=n;
w^.leg:=r^.leg;
r^.leg:=w;
end;
end;{inserare_d}
procedure stergere(info:integer);
var q,r,w:reper;
begin
r:=adresa(s1,s2,info);
if r=s2 then
write('nu ex. nodul')
else
begin
q:=s1;
while q^.leg<>r do
q:=q^.leg;
q^.leg:=r^.leg;
dispose(r);
end;
end;{stergere}
procedure afisare(s1,s2:reper);
var q:reper;
begin
q:=s1^.leg;
if q=s2 then
write('lista vidă')
else
repeat
write(q^.inf,' ');
q:=q^.leg;
until q=s2;
writeln;
end;{afisare}
begin{p.p.}
clrscr;
writeln('a) creare lista simplu înlănţuită');
creare(s1,s2);
writeln('Afisare:');
afisare(s1,s2);
writeln('b) inserare inainte');
write('informatia no inaintea caruia se insereaza=');
readln(info);
inserare_i(info);
writeln('Afisare:');
afisare(s1,s2);
writeln('c) inserare dupa');
write('informatia nodului după care se insereaza=');
readln(info);
inserare_d(info);
writeln('Afisare:');
afisare(s1,s2);
writeln('d) stergere');
write('informatia din nod ce va fi sters=');
readln(info);
stergere(info);
writeln('Afisare:');
afisare(s1,s2);
readln;
end.
4.4.4. Aplicaţia Lista dublu înlănţuită (p444.pas):
a) Să se construiască o listă dublu înlănţiută cu numere
naturale, citirea numerelor se termină o dată cu introducerea
numărului 0 (care nu face parte din coadă).
b) Să se insereze o componentă în listă după o componentă dată
prin informaţia ei.
c) Să se insereze o componentă în listă inaintea unei componente
dată prin informaţia ei.
d) Să se şteargă o componentă dată prin informaţia ei.
e) Folosind interschimbări de adrese ale componentelor să se formeze
o listă cu numere ordonate crescător.
f) Să se afişeze lista parcurgând-o de la stânga la dreapta şi de
la dreapta la stânga.
După fiecare subpunct se va afişa lista.
program l_d_i;
uses crt;
type nod=^elem;
elem=record
st,dr:nod;
inf:integer;
end;
var s1,s2:nod; n,m:integer;
procedure creare(var s1,s2:nod);
var n:integer; p:nod;
begin
new(s1);
new(s2);
s1^.dr:=s2;
s2^.st:=s1;
write('numar=');readln(n);
while n<>0 do
begin
s2^.inf:=n;
new(p);
p^.st:=s2;
s2^.dr:=p;
s2:=p;
write('numar=');readln(n);
end;
end;{creare}
function caut(s1,s2:nod;n:integer):nod;
{functia returneaza adresa nodului cu
informatia egala cu parametrul n}
var p:nod;
begin
p:=s1^.dr;
while(p<>s2) and(p^.inf<>n) do
p:=p^.dr;
if p=s2 then
caut:=nil
else
caut:=p;
end;{caut}
procedure stergere(s1,s2:nod;n:integer);
var q,r,p:nod;
begin
p:=caut(s1,s2,n);
if p<>nil then
begin
q:=p^.dr;
r:=p^.st;
r^.dr:=q;
q^.st:=r;
dispose(p);
end
else
writeln('nu exista nod cu inf=',n);
end;{stergere}
procedure afisaresd(s1,s2:nod);
{afisarea informatiilor în sensul
s1--->s2}
var p:nod;
begin
p:=s1^.dr;
while p<>s2 do
begin
write(p^.inf,' ');
p:=p^.dr;
end;
writeln;
end;{afisaresd}
procedure afisareds(s1,s2:nod);
{afisarea informatiilor în sensul
s2--->s1}
var p:nod;
begin
p:=s2^.st;
while p<>s1 do
begin
write(p^.inf,' ');
p:=p^.st;
end;
writeln;
end;{afisareds}
procedure inserare_dupa(s1,s2:nod;n,m:integer);
var p,q:nod;
begin
p:=caut(s1,s2,n);
if p= nil then
writeln ('nu exista nod cu inf=',n)
else
begin
new(q);
q^.inf:=m;
q^.dr:=p^.dr;
p^.dr:=q;
q^.st:=p;
end;
end;{inserare_dupa}
procedure inserare_inainte(s1,s2:nod;n,m:integer);
var p,q:nod;
begin
p:=caut(s1,s2,n);
if p=nil then
writeln('nu exista nod cu inf=',n)
else
begin
new(q);
q^.inf:=m;
q^.st:=p^.st;
q^.dr:=p;
(p^.st)^.dr:=q;
p^.st:=q;
end;
end;{inserare_inainte}
procedure interschimbare(s,p,q,r:nod);
begin
s^.dr:=q;
q^.st:=s;
q^.dr:=p;
p^.st:=q;
p^.dr:=r;
r^.st:=p;
end;{interschimbare}
procedure ord_cresc(s1,s2:nod);
var p:nod; sw:boolean;
begin
sw:=true;
while sw do
begin
sw:=false;
p:=s1^.dr;
while(p^.dr<>s2) do
if p^.inf>(p^.dr)^.inf then
begin
interschimbare(p^.st,p,p^.dr,(p^.dr)^.dr);
sw:=true;
end
else
p:=p^.dr;
end;
end;{ord_cresc}
begin {p.p.}
clrscr;
writeln('a) creare lista dublu înlănţuită');
creare(s1,s2);
writeln('afisare st-dr');
afisaresd(s1,s2);
writeln('afisare dr-st');
afisareds(s1,s2);
writeln('b) inserare dupa');
write('inserare după nodul cu info=');
readln(n);
write('informatie nod inserat=');
readln(m);
inserare_dupa(s1,s2,n,m);
writeln('lista după inserare=');
afisaresd(s1,s2);
writeln('c) inserare inainte');
write('inserare inaintea nodului cu info=');
readln(n);
write('informatie nod inserat=');
readln(m);
inserare_inainte(s1,s2,n,m);
writeln('lista după inserare');
afisaresd(s1,s2);
writeln('d) stergere nod');
write('informatie nod ce va fi sters=');
readln(n);
stergere(s1,s2,n);
writeln('dupa stergere');
afisaresd(s1,s2);
afisareds(s1,s2);
writeln('e) ordonare');
ord_cresc(s1,s2);
writeln('lista după ordonare crescatoare:');
afisaresd(s1,s2);
readln;
end.
4.4.5. Aplicaţia listă circulară (p445.pas):
O listă circulară este o listă simplu înlănţuită în care
ultima componenta conţine adresa primei componente.
Exemplu:
Lista circulară cu numerele 5, 20, 13 poate fi reprezentată astfel:
Pentru a lucra cu liste circulare este nevoie de o singură variabilă
dinamică în care să reţinem adresa unui nod (spre exemplu adresa
primului nod introdus).
Operaţiile asupra listei circulare sunt aceleaşi ca cele de la lista
simplu înlănţuită. Aceste operaţii le vom prezenta în aplicaţia
următoarea.
a) Să se construiască o listă circulară care să conţină n
numere naturale distincte citite de la tastatură.
b) Să se afişeze numerele din lista creată la punctul a).
c) Să se insereze un număr citit de la tastatură înaintea şi
după cel mai mare număr din lista circulară. Apoi să se afişeze
numerele din lista.
d) Să se şteargă din lista circulară toate numerele prime. Apoi
să se afişeze numerele din lista.
program lista_circulare;
uses crt;
type nod=^element;
element=record
inf:byte;
urm:nod;
end;
var pr:nod;
x:integer;
procedure creare(var pr:nod);
var i,x,n:integer;p,q:nod;
begin
write('n='); readln(n);
pr:=nil;
for i:=1 to n do
begin
new(p);
write('numar='); readln(x);
p^.inf:=x;
if pr=nil then
begin
p^.urm:=p;
pr:=p;
q:=p;
end
else
begin
q^.urm:=p;
q:=p;
end;
end;
q^.urm:=pr;
end;{creare}
procedure afisare(pr:nod);
var p:nod;
begin
p:=pr;
repeat
write(' ', p^.inf);
p:=p^.urm;
until p=pr;
writeln;
end;{afisare}
function maxim(pr:nod):integer;
var p:nod; max:integer;
begin
p:=pr^.urm;
max:=p^.inf;
while p<>pr do
begin
if p^. inf>max then max:=p^.inf;
p:=p^.urm;
end;
maxim:=max;
end;{maxim}
function adresa_inainte(pr,q:nod):nod;
var p:nod;
begin
p:=pr;
while p^.urm<>q do
p:=p^.urm;
adresa_inainte:=p;
end;{adresa_inainte}
procedure inserare_i_d(pr:nod; x:integer);
var p,q,r:nod;max:integer;
begin
p:=pr;
max:=maxim(pr);
while p^.urm<>pr do
if p^.inf=max then
begin
{inserarea inainte de nodul p}
new(q);
r:=adresa_inainte(pr,p);
q^.inf:=x;
q^.urm:=p;
r^.urm:=q;
{inserare după nodul p}
new(q);
q^.inf:=x;
q^.urm:=p^.urm;
p^.urm:=q;
p:=q;
end
else
p:=p^.urm;
{ultimul nod il prelucram separat}
if p^.inf=max then
begin
new(q);
q^.inf:=x;
q^.urm:=p^.urm;
p^.urm:=q;
p:=q;
end
end;{inserared}
procedure stergere(pr:nod);
{stergem din lista circurara
toate numerele prime}
var q,p:nod;
function prim(a:integer):boolean;
var i:integer; sw:boolean;
begin
if (a=0)or(a=1) then
sw:=false
else
begin
sw:=true;
for i:=2 to trunc(sqrt(a)) do
if a mod i=0 then
sw:=false;
end;
prim:=sw;
end;{prim}
begin
p:=pr;
if p<>nil then
repeat
if prim(p^.inf) then
begin
q:=adresa_inainte(pr,p);
q^.urm:=p^.urm;
dispose(p);
p:=q^.urm;
end
else
p:=p^.urm;
until p=pr;
end;{stergere}
begin{p.p.}
clrscr;
writeln('a) creare lista circulara');
creare(pr);
writeln('b) elementele din lista circulara: ');
afisare(pr);
writeln('c) inserare nr. inainte şi după max.');
write('nr. natural ce va fi inserat=');
readln(x);
inserare_i_d(pr,x);
writeln('afisare după inserare:');
afisare(pr);
writeln('d) stergere numere prime');
stergere(pr);
writeln('afisare după stergere:');
afisare(pr);
readln;
end.
4.4.6. Probleme propuse
1. Să se creeze o stivă cu primele n (n citit de la tastatură)
numere prime. Apoi să se afişeze numerele din stivă.
2. Să se ceeze o coadă care să conţină primele n numere pătrate
perfecte. Apoi să se afişeze numerele din coadă.
3. a) Să se creeze o listă simplu înlănţuită cu numele şi
înălţimea a n elevi dintr-o clasă.
b) Să se afişeze lista.
c) Să se insereze înainte şi după o componentă ce conţine elevi
cu înălţimea maximă doi elevi cu datele (nume şi înălţime)
citite de la tastatură.
d) Să se afişeze lista.
e) Să se şteargă din listă componentele care au înălţimea
minimă.
f) Să se afişeze lista.
4. a) Să se creeze o listă dublu înlănţuită care să conţină
numere naturale x<1000000000. Citirea numerelor se încheie tastând 0
(care nu face parte din listă).
b) Să se afişeze lista.
c) Să se insereze înainte şi după fiecare componentă din lista
dublu înlănţuită ce conţine un număr format numai din cifre pare,
numărul 0.
d) Să se afişeze lista.
e) Să se şteargă componentele din listă care conţin numere ce au
în scrierea lor numai cifre impare.
f) Să se afişeze lista.
5. a) Să se creeze o listă liniară care să conţină un şir de
cuvinte. Citirea datelor se încheie prin tastarea caracterului
‘*’.
b) Pentru un cuvânt x, dat să se construiască două liste liniare
pornind de la lista creată la punctul a), care să conţină cuvintele
mai mici în ordine lexicografică, respectiv mai mari decât x.
6. Folosind liste liniare să se calculeze suma şi produsul a două
numere mari.
7. Folosind liste liniare să se calculeze suma şi produsul a două
polinoame. Se va folosi pentru un nod al listei structura:
Exemplu:
Pentru polinomul P(X)=5X100+20X5-7 se va folosi lista:
8. Folosind liste liniare (pentru reţinerea cifrelor) să se
calculeze puterea am, unde a este cifră, iar m este un număr natural
mai mic s-au egal cu 1000000000.
9. Folosind liste circulare să se reţină coordonatele vârfurilor
unui poligon convex. Apoi să se calculeze perimetrul şi aria
poligonului.
IV. Metode şi tehnici de programare
Rezolvarea problemelor algoritmice presupune uneori o abordare
riguroasă a metodei alese. Acest lucru se impune pentru a reduce
complexitatea algoritmului şi pentru organizarea eficientă a datelor.
Există astfel clase de probleme rezolvabile şi abordabile prin metode
specifice.
1. Metoda Greedy
Metoda Geedy (din engleză “lacom”) este o metodă care se aplică
problemelor în care se dă o mulţime A de n elemente şi se cere să
se determine o submulţime B a acesteia care să îndeplinească
anumite condiţii, numite condiţii interne. În general aceste
probleme cer ca mulţimea B să satisfacă o funcţie de optim, şi se
numesc probleme de optim.
În majoritatea cazurilor există mai multe soluţii posibile ale unei
astfel de probleme. Dintre acestea doar unele sunt şi soluţii optime.
Tehnica Greedy permite găsirea uneia dintre soluţiile optime.
Algoritmul Greedy constă în lăcomia sa. La fiecare pas se alege
câte un element al mulţimii A, care satisface condiţiile cerute. La
alegerea elementului, există certitudinea că elementul îndeplineşte
condiţiile problemei şi deci face parte din soluţia optimă.
Pentru a descrie algoritmic metoda considerăm algoritmii:
Alege (A, i, x ) care alege din mulţimea A un element corespunzător
x, aflat pe poziţia i, dintre elementele rămase în A.
Posibil (B, x, cod) care verifică dacă elementul x este acceptat ca
soluţie, şi îndeplineşte condiţiile de optim. El poate fi adăugat
mulţimii B. Validarea elementului se face prin variabila cod a cărei
valoarea de adevăr corespunde validităţii (true- elementul este
acceptat. False- în caz contrar);
Adaug (B, x) care adaugă elementul x mulţimii B şi îl elimină din
A.
Folosind aceşti algoritmi definiţi în funcţie de specificul
problemei, algoritmul general al Metodei Greedy este:
Algoritm Greedy (A, n, B);
Cod : boolean;
B = {Mulţimea vidă};
Pentru i=1, n,1 execută
Alege (A, i, x )
Posibil (B, x, cod)
Dacă cod atunci
Adaug (B, x);
Sf dacă;
Sf pentru;
Complexitatea algoritmilor Greedy este în general liniară (O(n)),
unde n este numărul elementelor mulţimii A.
Exemplul 1:
Un exemplu foarte general este problema de determinare a unui număr
maxim de elemente dintr-o mulţime A astfel încât suma lor să nu
depăşească o valoare dată V.
Tehnica Greedy constă în a alege în ordine crescătoare elemente
până când un nou element adăugat să depăşească valoarea
cerută. Pentru a scrie mai uşor algoritmul de rezolvare vom apela la
algoritmii construiţi anterior (ordonarea unui şir).
{tipul Sir este un şir de n valori numerice}
Algoritm Posibil (x, S, V: numeric, cod : boolean);
Dacă S+x<=V atunci
Cod = adevărat;
Sf dacă;
Algoritm Greedy (A: sir, n, V: numeric, B: sir);
Cod : boolean;
s, k: numeric;
BubbleSort (A, n);
k = 0;
S = 0;
Pentru i=1, n,1 execută
Posibil ( A(i), S, V, cod );
Dacă cod atunci
k = k + 1;
S = S + A (i);
B (k) = A (i);
Sf dacă;
Sf pentru;
Exemplul 2
Problema rucsacului
Se dă o mulţime A de obiecte, caracterizate prin utilitate şi
greutate şi un rucsac care poate să suporte o greutate maximă
notată prin G. Se cere să se stabilească obiectele din A ce se pot
pune în rucsac, astfel ca suma greutaţilor lor să nu depaşească G,
iar utilitatea lor să fie maximă.
Considerăm că mulţimea A are n obiecte,
A = {a1, a2, ..., an}
fiecare obiect ai este caracterizat de
u_i = gradul de utilitate al obiectului
g_i = greutatea acestuia.
O implementare Greedy constă în alegerea elementelor din A în
ordinea dată de raportul utilitate(a)
------------ cu condiţia ca raportul să fie maximal.
greutate(a)
Programul Rucsac.PAS foloseste acestă implementare şi respectiv cea
în care se ordonează elementele lui A. Toate subprogramele necesare
sunt incluse in unit-ul URucsac.PAS. Problema este rezolvată în
secţiunea Probleme de pe CD la capitolul Metode, Greedy, printr-un
algoritm clasic.
Probleme propuse
1. Se dau n bancnote fiecare exprimând o valoare vi, i=1,n. Să se
determine o modalitate de plată a unei valori cât mai apropiată de o
sumă S, folosind un număr minim de bancnote.
2. Se dau n ţevi de lungimi Li , i=1,n. Să se acopere un tronson de
lungime M folosind un număr cât mai mare de ţevi.
3. Pe n scaune aşezate în cerc se află n-1 copii, cel mult unul pe
un scaun. La un moment dat scaunul liber poate fi ocupat de un alt
copil a cărui scaun devine liber. Dâdu-se o configuraţie iniţială
de aşezare a copiilor şi una finală, să se determine modul în care
copii se pot reaşeza ajungând de la configuraţia iniţială la cea
finală.
2. Metoda Divide et Impera
Divide et Impera (“împarte şi stăpâneşte”) este o metodă
care constă în:
- Descompunerea problemei ce trebuie rezolvată într-un anumit număr
de subprobleme mai mici, în general de aceeaşi natură;
- Rezolvarea succesivă şi independentă a fiecărei subprobleme;
- Combinarea tuturor soluţiilor fiecărei subprobleme pentru a
obţine soluţia întregii probleme.
Modelul general al algoritmului Divide et Impera se poate descrie în
două moduri:
A)Recursiv, metodă care în situaţiile în care numărul de
subprobleme este mare devine ineficient;
B) Iterativ, când pentru fiecare subproblemă în parte se alocă,
dacă este necesar un spaţiu de memorie.
Algoritmul Divide et Impera_recursiv, atunci când problema se
descompune doar în două subprobleme, este:
Algoritm divimp (p, q, a);
Dacă q – p <= eror atunci
prelucrare (p, q, a);
altfel
împarte (p, q, m);
divimp (p, m, b);
divimp (m+1, q, c);
combină (b, c, a);
sf dacă
Unde p şi q reprezintă capetele mulţimii unei subprobleme, a, b, c
fiind soluţiile subproblemelor.
Cazul general presupune împărţirea problemei P, a cărei soluţie S
o căutăm, în Np probleme ca vor avea fiecare soluţiile Sp şi o
dimensiune Dp. Vom utiliza următorii algoritmi:
Rezolva (P, S) care rezolvă problema P, atunci când dimensiunea sa
este suficient de mică, deci rezolvabilă, obţinând soluţia S.
Descompune ( P, Np, Dp) care descompune problema P în problemele Np
de dimensiuni Dp.
Combină (Sp, Dp, S) combină soluţiile subproblemelor Sp de
dimensiuni Dp şi obţine soluţia S.
Algoritmul general „Divide et Impera” poate fi descris astfel:
Algoritm DivideEtImpera (P, Dp, S)
Dacă „P este rezolvabilă” atunci
Rezolva (P, S)
Altfel
Descompune ( P, Np, Dp)
Pentru „Fiecare problema Np” execută
DivideEtImpera(Np, Dp, Sp)
SfPentru
Combină (Sp, Dp, S)
SfDacă
În cele ce urmează vom prezenta câţiva dintre cei mai
reprezentativi algoritmi care folosesc tehnica Divide Et Impera şi
care fac parte dintr-o categorie importantă, căutarea şi sortarea
pentru structuri de date mari.
2.1. Căutare şi sortare pentru structuri de date
Căutarea şi sortarea sunt două dintre cele mai des întâlnite
subprobleme în programare. Ele constituie o parte esenţială din
numeroasele procese de prelucrare a datelor. Operaţiile de căutare
şi sortare sunt executate frecvent de către oameni în viaţa de zi
cu zi, ca de exemplu căutarea unui cuvânt în dicţionar sau
căutarea unui număr în cartea de telefon.
Căutarea este mult simplificată dacă datele în care efectuăm
această operaţie sunt sortate (ordonate, aranjate) într-o anumită
ordine (cuvintele în ordine alfabetică, numerele în ordine
crescătoare sau descrescătoare).
Sortarea datelor constă în rearanjarea colecţiei de date astfel
încât un câmp al elementelor colecţiei să respecte o anumită
ordine. De exemplu în cartea de telefon fiecare element (abonat) are
un câmp de nume, unul de adresă şi unul pentru numărul de telefon.
Colecţia aceasta respectă ordinea alfabetică după câmpul de nume.
Dacă datele pe care dorim să le ordonăm, adică să le sortăm,
sunt în memoria internă, atunci procesul de rearanjare a colecţiei
îl vom numi sortare internă, iar dacă datele se află într-un
fişier (colecţie de date de acelaşi fel aflate pe suport extern),
atunci procesul îl vom numi sortare externă.
Fiecare element al colecţiei de date se numeşte articol iar acesta
la rândul său este compus din unul sau mai multe componente. O cheie
C este asociată fiecărui articol şi este de obicei unul dintre
componente. Spunem că o colecţie de n articole este ordonat
crescător după cheia C dacă C(I)<=C(j) pentru 1<=i<j<=n, iar dacă
C(i)>=C(j) atunci şirul este ordonat descrescător.
Algoritmi de căutare
Deci problema căutării are următoarea specificare:
Date a,n,(k,i=1,n);
Precondiţia: n din=N, n<=1 şi k1<k2<…<kn;
Rezultate p;
Precondiţia: (p=1 şi a<=k1)sau(p=n+1 şi a>kn)
sau (1<p<=n) şi (kp-1<a<kp).
Pentru rezolvarea acestei probleme vom descrie mai mulţi
subalgoritmi.
O primă metodă este căutarea secvenţială, în care sunt examinate
succesiv toate cheile.
Sublagoritmul CautSecv(a,n,k,p) este:
{n din N, n>=1 şi k1<k2 <…<kn. Se caută p astfel ca: (p=1) şi
a<=k1) sau (p=n+1 şi a>kn) sau (1<p<=n) şi (kp-1<a<=kp).Cazul
“încă negăsit”}
Fie p:=0;
Dacă a<=k1 atunci p:=1 altfel
Dacă a>kn atunci p:=n+1 altfel
Pentru i:=2, n execută
Dacă (p=0) şi (a<=kI) atunci
p:=i
sfdacă
Sfpentru
Sfdacă
Sfdacă
Sf-CautSecv
Se observă că prin această metodă se vor executa în cel mai
nefavorabil caz n-1 comparări, întrucât contorul i va lua toate
valorile de la 2 la n. Cele n chei împart axa reală în n+1
intervale. Tot atâtea comparări se vor efectua în n-1 din cele n+1
intervale în care se poate afla cheia căutată, deci complexitatea
medie are acelaşi ordin de mărime ca şi complexitatea în cel mai
rău caz.
2.2. Căutare binară
Se dau un vector A=(a1,…,an) şi o valoare x. Se cere să se
determine dacă x se află printre elementele vectorului A.
Dacă A este un vector oarecare, atunci trebuie parcurse secvenţial
elementele vectorului. Această modalitate necesită cel mult n
comparaţii în cazul unei căutări cu succes şi exact n comparaţii
în cazul căutării fără succes. Numărul mediu de comparaţii în
cazul unei căutări cu succes este (1+2+…+n)/2=(n+1)/2.
Dacă A are elementele în ordine crescătoare – situaţie des
întâlnită în practică – atunci există posibilitatea de a
efectua o căutare mai performantă. Deci în continuare vom lucra în
ipoteza a1<=a2<=…<=an.
Vom folosi metoda “Divide et impera”, începând prin a compara x
cu elementul “din mijloc”, adică cu ai unde i=(n+1)/2. Dacă aI=x,
atunci căutarea se încheie cu succes. În caz contrar, vom căuta x
în secvenţa a1,…,ai-1 dacă x<ai sau în secvenţa ai+1,…,an
dacă x> ai. Vom presupune că dorim ca soluţia să fie exprimată sub
forma:
(s,i)=(1,i) dacă x=aI, i =1,n
(0, i) dacă ai < x < ai , i =1,n+1unde a0 = - maxint an+1 =
+maxint
Căutarea binară se poate realiza practic prin apelul funcţiei
BinarySearch(a,n,k,1,n), deschisă mai jos, folosită în subalgoritmul
dat în continuare.
Subalgoritmul CautBin(a,n,k,p) este:
{n din N, n>=1 şi k1<k2 <…<kn. Se caută p astfel ca: (p=1) şi
a<=k1) sau (p=n+1 şi a>kn) sau (1<p<=n) şi (kp-1<a<=kp).}
Dacă a<=k 1 atunci p:=1 altfel
Dacă a>k n atunci p:=n+1 altfel
p:=BinarySearch(a,n,k,1,n)
sfdacă
sfdacă
sfCautBin
Funcţia BinarySearch(a,n,k,St,Dr) este:
Dacă st>dr-1 atunci BinarySearch:=Dr
Altfel m:=(st+dr) div 2;
Dacă a<=k[m]
Atunci BinarySearch:=BinarySearch(a,n,k,st,m)
Altfel BinarySearch:=BinarySearch(a,n,k,m,dr)
Sfdacă
Sfdacă
SfBinarySearch
În funcţia BinarySearch deschisă mai sus, variabilele St şi Dr
reprezintă capetele intervalului de căutare, iar m reprezintă
mijlocul acestui interval. Prin această metodă, într-o colecţie
având n elemente, rezultatul căutării se poate furniza după cel
mult log2n comparări. Deci complexitatea în cel mai rău caz este
direct proporţională cu log2n. Fără a insista asupra
demonstraţiei, menţionăm că ordinul de mărime al complexităţii
medii este acelaşi.
Exemplu:
Următorul program pascal realizează căutarea binară într-un şir
de numere întregi, folosind tehnica recursivă:
program cautare_binara; {Solutia
Probleme/81Metode/Divide/binara.pas}
type sir=array[1..10] of integer;
var a:sir;
i,n:byte;
x:integer;
procedure cautare(st,dr:byte);
var mijloc:byte;
begin
if st>dr then begin
write('el nu apartine sirului');exit;
end;
mijloc:=(st+dr) div 2;
if a[mijloc]=x then
write('valoarea ',x,' se afla pe pozitia ',mijloc)
else
if a[mijloc]>x then
cautare(st,mijloc-1)
else
cautare(mijloc+1,dr);
end;
begin
write('dati nr de valori ');read(n);
write('dati sirul ordonat');
for i:=1 to n do
begin
write('a[',i,']= ');
read(a[i]);
end;
write('dati valoarea ');read(x);
cautare(1,n);
readln;
readln;
end.
2.3. Sortarea rapidă
O metodă mai performantă de ordonare, care va fi prezentată în
continuare, se numeşte “Quick Sort” şi se bazează pe tehnica
“divide et impera” după cum se poate observa în continuare.
Metoda este prezentată sub forma unei proceduri care realizează
ordonarea unui subşir precizat prin limita inferioară şi limita
superioară a indicilor acestuia. Apelul procedurii pentru ordonarea
întregului şir este: Quick Sort(n,k,1,n), unde n reprezintă numărul
de articole ale colecţiei date. Deci
Subalgoritmul SortareRapidă (n,k) este:
Cheamă Quick Sort (n,k,1,n)
SfSortareRapidă
Procedura Quick Sort (n,k,St,Dr) va realiza ordonarea subşirului kSt
, kSt+1,…, kDr. Acest subşir va fi rearanjat astfel încât kSt
să ocupe poziţia lui finală (când şirul este ordonat). Dacă i
este această poziţie, şirul va fi rearanjat astfel încât
următoarea condiţie să fie îndeplinită:
kj <= kj <= kl, pentru st <= j < i < l <= dr
Odată realizat acest lucru, în continuare va trebui doar să
ordonăm subşirul
kSt , kSt+1 , … , ki-1 prin apelul recursiv al procedurii Quick Sort
(n,k,st,i-1) şi apoi subşirul ki+1 , … , kDr prin apelul Quick Sort
(i+1, Dr). Desigur ordonarea acestor două subşiruri (prin apelul
recursiv al procedurii) mai este necesară doar dacă acestea conţin
cel puţin două elemente.
Procedura Quick Sort este prezentată în continuare:
Subalgoritmul Quick Sort (n,k,St,Dr) este:
Fie i:=St; j:=Dr; a:=k;
Repetă
Câttimp kj >=a şi (i<j) execută j:=j-1 sfcât
Ki:= kj;
Câttimp ki >=a şi (i<j) execută i:=I+1 sfcât
Kj:= ki;
Pânăcând i=j sfrep
Fie kj:=a;
Dacă St<i-1 atunci Cheamă Quick Sort (n,k,St,i-1)
Sfdacă
Dacă i+1<Dr atunci Cheamă Quick Sort (n,k,i+1,Dr)
Sfdacă
Sf Quick Sort
Complexitatea algoritmului prezentat este O(n2) în cel mai
nefavorabil caz, dar complexitatea medie este de ordinul O(nlog2n).
Algoritmul QuickSort este disponibil în limbajul Pascal şi poate fi
utilizat pentru căutări rapide:
program QSort;
{$R-,S-}
uses Crt;
{ Acest program aplica metoda Quicksort pentru un sir de 1000 de}
{ numere alese aleator, cu valori intre 0 si 29999. Rezultatul }
{este afisat direct la ecran pentru a observa viteza de executie}
const
Max = 1000;
type
List = array[1..Max] of Integer;
var
Data: List;
I: Integer;
procedure QuickSort(var A: List; Lo, Hi: Integer);
{Procedura QuickSort contine o procedura recursiva }
{care ordoneaza efectiv elemnetele. }
procedure Sort(l, r: Integer);
var
i, j, x, y: integer;
begin
i := l; j := r; x := a[(l+r) DIV 2];
repeat
while a[i] < x do i := i + 1;
while x < a[j] do j := j - 1;
if i <= j then
begin
y := a[i]; a[i] := a[j]; a[j] := y;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
begin {QuickSort};
Sort(Lo,Hi);
end;
begin {QSort}
Write('Generare 1000 numere ...');
Randomize;
for i := 1 to Max do Data[i] := Random(30000);
Writeln;
Write('Sortarea numerelor ...');
QuickSort(Data, 1, Max);
Writeln;
for i := 1 to 1000 do Write(Data[i]:8);
end.
2.4. Sortare cu număr minim de comparaţii
Fie de sortat vectorul A=(a1,…,an) având componentele distincte.
Oricărei strategii de sortare bazată pe comparări ale elementelor
lui A i se poate asocia un arbore binar strict în care:
fiecare vârf intern (neterminal) este etichetat cu i:j
semnificând faptul că se compară elementele ai şi aj ;
muchia spre descendentul stâng reprezintă ramificarea
corespunzătoare ai < aj,
muchia spre descendentul drept corespunde situaţiei ai > aj.
pentru orice vârf terminal, comparaţiile reprezentate de vârfuri
împreună cu rezultatele lor, corespunzătoare faptului că fiecare
vârf diferit de rădăcină este descendentul stâng sau drept al
tatălui său, conduc în mod necesar la inegalităţile:
ap(1)<ap(2)<…<ap(n)
unde p din Sn este permutarea ataşată vârfului extern respectiv.
Un astfel de arbore se numeşte arbore de comparare. Această
problemă va fi discutată în capitolul special destinat grafurilor.
Probleme rezolvate şi probleme propuse
1. Să se determine, folosind tehnica Divide Et Impera, maximul
(minimul dintre elementele unui şir.
(Probleme/81Metode/Divide/maxdivi.pas(mindivi.pas)).
2. Calculaţi produsul elementelor unui şir folosind Divide Et
Impera. (Probleme/81Metode/Divide/prodivi.pas).
3. Calculaţi cel mai mare divizor comun a n numere naturale nenule.
4. Problema turnurilor din Hanoi. Pe o tijă sunt aşezate n discuri
in ordinea descrescatoare a diametrelor lor. Se cere să se mute toate
discurile pe o altă tijă, folosind o a treia tijă auxiliară, exact
în aceeaşi ordine. Singura mutare permisa este aceea de a aşeza un
disc de pe o tija pe alta, respectându-se întotdeauna ordinea
descrescatoare a diametrelor discurilor aflate pe fiecare tijă.
(Probleme/81Metode/ Divide/hanoi.pas).
3. Metoda Backtracking
Vom începe prezentarea metodei Backtracking printr-un exemplu.
Se consideră tabla de şah şi opt turnuri. Se cere să se aşeze
în toate modurile posibile cele opt turnuri pe tabla de şah astfel
încât să nu existe două care se atacă (nu se află pe acceşi
linie respectiv coloană).
Dacă luăm în faţa noastră o tablă de şah şi încercăm să
aşezăm turnuri din colţul din stânga sus al tablei vom observa că
o primă aşezare, corectă, situează turnurile pe diagonala tablei.
Fie această soluţie 1,2,3,4,5,6,7,8, considerând linia pe care am
aşezat fiecare turn, coloana fiind poziţia lor în şir. Dorim însă
să obţinem toate posibilităţile fără a pierde nici una. Să
procedăm în felul următor:
Luaţi de pe tablă ultima piesă, turnul 8.
Încercaţi să aşezaţi turnul 7 cu o linie mai jos, pe linia 8 pe
tablă şi apoi încercaţi să reaşezaţi turnul 8. Veţi obţine
soluţia 1,2,3,4,5,6,8,7.
Reluaţi acelaşi algoritm de unde am rămas. Luaţi turnul 8.
Turnul 7 nu poate fi mutat mai jos, deci luaţi turnul 7.
Încercaţi să aşezaţi turnul 6 cu o linie mai jos, pe linia 7 pe
tablă şi apoi încercaţi să reaşezaţi turnul 7 pe prim poziţie
corectă, 6, apoi la fel pentru turnul 8. Veţi obţine soluţia
1,2,3,4,5,7,6,8.
Reluaţi acelaşi algoritm de unde am rămas. Luaţi turnul 8. Turnul
7 poate fi mutat mai jos iar aşezarea lui 8 va da soluţia
1,2,3,4,5,7,8,6.
Continuaţi în acelaşi mod şi veţi ajunge în final la ultima
soluţie, aşezarea pe diagonala secundară, respectiv 8,7,6,5,4,3,2,1.
Dacă aţi mânuit corect piesele pe tabla de şah înseamnă că aţi
înţeles metoda Backtracking, caută cu revenire.
Descrierea metodei.
Metoda Backtracking se aplică problemelor ale căror soluţii sunt
elemente ale unui produs cartezian A1xA2 x…xAn, care satisfac anumite
condiţii, numite condiţii interne.
Mulţimea tuturor elementelor produsului cartezian se numeşte spaţiul
soluţiilor. Din această mulţime se determină toate soluţiile de
forma (x1,x2,…,xn) din A1xA2 x…xAn care satisfac condiţiile
interne.
Metoda backtracking se foloseşte în rezolvarea problemelor care
îndeplinesc simultan următoarele condiţii:
-soluţia lor poate fi pusă sub forma unui vector x= (x1,x2,…,xn)
dintr-un spaţiu A= A1xA2 x…xAn , astfel încât x1A1, x2 A2
,…,xn An .
-mulţimile Ai, i=1…n, sunt mulţimi finite, card (Ai) = ai , iar
elementele lor se consideră că se află într-o relaţie de ordine
bine stabilită;
-există anumite relaţii între componentele x1,x2,…,xn ale
vectorului X, numite condiţii interne;
-nu se dispune de o altă metodă de rezolvare mai rapidă.
Mulţimea A= A1xA2 x…xAn se numeşte spaţiul soluţiilor posibile.
Soluţiile posibile care satisfac condiţiile interne se numesc
soluţiile problemei.
Observaţii
-Nu pentru toate problemele n este cunoscut;
-x1,x2,…,xn pot fi la rândul lor vectori;
-în multe probleme mulţimile A1xA2 x…xAn coincid.
Scopul acestei metode este de a determina toate soluţiile problemei
(cu scopul de a le lista sau de a alege dintre ele una care
maximizează sau minimizează o eventuală funcţie obiectiv dată). O
metodă de determinare a soluţiilor constă în a genera într-un mod
oarecare toate soluţiile posibile şi de a verifica dacă ele satisfac
condiţiile interne.
Dezavantajul constă în faptul că timpul cerut de această
investigare exhaustivă este foarte mare (chiar pentru card(Ai)=2,
timpul necesar este de ordinul 2n, adică exponenţial).
Metoda backtracking urmăreşte să evite generarea tuturor soluţiilor
posibile. În acest scop, elementele vectorului x primesc pe rând
valori, în sensul că lui xk i se atribuie o valoare numai dacă au
fost atribuite deja valori lui x1,x2,…,xk-1. O dată o valoare pentru
xk stabilită, nu se trece direct la atribuirea de valori lui xk+1, ci
se verifică condiţiile de continuare referitoare la x1,x2,…,xk ,
care stabilesc situaţiile în care are sens să trecem la calculul lui
xk+1.
Concret:
-se alege primul element x1, ce aparţine lui A1
-presupunând generate elementele x1,x2,…,xk aparţinând mulţimilor
A1xA2 x…xAk se alege (dacă există) xk+1, primul element disponibil
din mulţimea Ak+1; apar două posibilităţi:
i. nu s-a găsit un astfel de element, caz în care se reia căutarea
considerând generate elementele x1,x2,…,xk-1, iar aceasta se reia de
la următorul element al mulţimii Ak, rămas netestat.
ii. a fost găsit, caz în care se testează dacă acesta
îndeplineşte anumite condiţii de continuare, apărând astfel 2
posibilităţi:
a) le îndeplineşte, caz în care se testează dacă s-a ajuns la
soluţie şi apar, din nou, 2 posibilităţi:
- s-a ajuns la soluţie, se tipăreşte soluţia şi se reia
algoritmul considerând generate elementele x1,x2,…,xk (se caută,
în continuare, un element al mulţimii Ak+1 rămas netestat).
- nu s-a ajuns la soluţie, caz în care se reia algoritmul
considerând generate elementele x1,x2,…,xk+1 şi se caută un prim
element xk+2Ak+2.
b) nu le îndeplineşte, caz în care se reia algoritmul considerând
generate elementele x1,x2,…,xk, iar elementul xk+1 se caută între
elementele mulţimii Ak+1rămase netestate.
Algoritmul se termină atunci când nu mai există nici un element
x1 A1, netestat.
Observaţie. Tehnica backtracking are ca rezultat generarea tuturor
soluţiilor problemei. În cazul în care se cere o singură soluţie,
se poate forţa oprirea, atunci când a fost găsită.
Am arătat că orice soluţie se generează sub formă de vector. Vom
considera că generarea soluţiilor se face într-o stivă. În acest
fel, stiva (notată st) va arăta ca mai jos:
xk
…
…
x2
x1
Fig. 2.1.
Nivelul k+1 al stivei trebuie iniţializat (pentru a alege în ordine
elementele mulţimii k+1). Iniţializarea trebuie făcută cu o valoare
aflată (în relaţia de ordine considerată pentru mulţimea Ak+1)
înaintea tuturor valorilor posibile din mulţime.
De exemplu, pentru generarea permutărilor mulţimii 1, 2, …,
n, orice nivel al stivei va lua valori de la 1 la n. Iniţializarea
unui nivel (oarecare) se face cu valoarea 0. Procedura de iniţializare
o vom numi init şi va avea doi parametri: k, nivelul care trebuie
iniţializat şi st (stiva).
Găsirea următorului element al mulţimii Ak, element netestat, se
face cu ajutorul procedurii succesor (as, st, k). Parametrul as am
succesor este o variabilă booleană. În situaţia în care am
găsit elementul, acesta este pus în stivă şi as ia valoarea true,
contrar (nu a rămas un element netestat) as ia valoarea false.
Odată ales un element, trebuie văzut dacă acesta îndeplineşte
condiţiile de continuare (altfel spus, dacă elementul este valid).
Acest test se face cu ajutorul procedurii valid (ev, st, k). Variabila
ev este booleană.
Testul dacă s-a ajuns sau nu la soliţia finală se face cu ajutorul
funcţiei soluţie (k). Soluţia se tipăreşte cu ajutorul procedurii
tipar.
Prezentăm rutina backtracking:
k:=1; init(1,st);
while k0 do
begin
repeat
succesor (as, st, k);
if as then valid (ev, st, k)
until (not as) or (as and ev);
if as then
if soluţie (k)
then tipar
else
begin
k:=k+1;
init (k, st)
end
else k:=k-1
end;
Observaţii
Problemele rezolvate prin această metodă necesită timp îndelungat.
Din acest motiv, este bine să utilizăm metoda numai atunci când nu
avem la dispoziţie un alt algoritm mai eficient.
Menţionăm că există probleme pentru care nu se cunosc algoritmi
efecienţi de rezolvare, deci backtracking este indicată.
Rutina prezentată corespunde variantei iterative.
Algoritmul de descriere a metodei Backtracking care foloseşte tehnica
recursivă este prezentat în algoritmul BACK, unde A este mulţimea
A1xA2 x…xAn dată ca un şir de şiruri, n este numărul de mulţimi,
x şirul soluţiei x= (x1,x2,…,xn). Folosim urmatorii sublalgoritmi:
Algoritmul Posibil (x, Ak(i), cod) verifică dacă elemetul Ak(i),
elementul i din mulţimea Ak , poate fi adăugat în soluţie, deci
dacă verifică condiţiile interne.
Algoritmul Solutie ( x, n) care furnizează o soluţie corectă a
problemei;
Vom utiliza aceeaşi variabilă k pentru a memora stiva de lucru
curentă, respectiv poziţia din şirul x pentru care căutăm
soluţie.
Algoritm Back (k: numeric);
Pentru i:=1 , card (Ak) execută
x (k) = Ak(i);
Posibil ( x, Ak(i), cod );
Dacă cod atunci
Dacă k < n atunci
Back (k + 1)
altfel
Scrie_şir ( x, n);
Sf dacă;
Sf dacă;
Sf pentru;
Stop;
Exemple
1. Să se genereze toate permutările mulţimii M = {1, 2, 3, …, n},
pentru un n dat. (probcurs\capIV\permutr.pas, permner.pas).
permutr.pas – varianta recursivă
type sir=array[1..10] of byte;
var x:sir;
n,m:byte;
procedure solutie(x:sir;n:byte);
var i:byte;
begin
for i:=1 to n do
write(x[i],',');
writeln;
end;
Function valid(i:byte):boolean;
var cod:boolean;
j:byte;
begin
cod:=true;
for j:=1 to i-1 do
if x[i]=x[j] then cod:=false;
valid:=cod;
end;
procedure permut(j:byte);
var i:byte;
begin
for i:=1 to n do
begin
x[j]:=i;
if valid(j) then
if j<n then permut(j+1)
else solutie(x,n);
end;
end;
begin
Write('n');readln(n);
permut(1);
end.
permner.pas – varianta nerecursivă
program bktr_nerecursiv;
uses crt;
type vector=array[1..25] of integer;
var st, v:vector;
n:integer;
procedure initializari;
var i:integer;
begin
write('n='); readln(n);
for i:=1 to 25 do st[i]:=0;
writeln;
end;
procedure tipar(p:integer);
var i:integer;
begin
for i:=1 to p do write(st[i]:4,' ');
writeln;
end;
function valid(p:integer):boolean;
var i:integer; ok:boolean;
begin
ok:=true;
for i:=1 to p-1 do
if st[p]=st[i] then ok:=false;
valid:=ok;
end;
procedure back;
{implementeaza algoritmul nerecursiv de backtracking}
var p:integer; {varful stivei}
begin
p:=1; st[p]:=0; {initializam primul nivel}
while p>0 do {cat timp stiva nu devine din nou vida}
begin
if st[p]<n then
begin
st[p]:=st[p]+1; {punem pe nivelul p urmatoarea valoare}
if valid(p) then
{daca solutia(st[1],st[2],...,st[p]) este valida}
if p=n then {daca solutia este si finala}
tipar(p)
else
begin
p:=p+1; st[p]:=0;
{trecem la nivelul urmator, pe care il reinitializam}
end;
end
else
p:=p-1; {pasul inapoi la nivelul anterior}
end;
end;
begin
clrscr;
initializari;
back;
readln;
end.
2. Backtracking în plan.
Pe o suprafaţă dreptunghiulară de dimensiune m x n, împărţită
în pătrăţele de dimensiune unu, se află depozitate rezervoare de
combustibil. Un autoturism porneşte din unul din pătrăţele şi se
deplasează doar pe orizontală şi verticală, consumând o unitate de
combustibil la trecerea de la un pătrăţel la altul, până când
adună toate rezervoarele de benzină. Să se determine un punct de
plecare şi de sosire astfel încât cantitatea acumulată să fie
maximă.
Autoturismul nu se poate deplasa fără combustibil şi adună toată
cantitatea la trecerea printr-un pătrăţel.
(probcurs\capIV\auto.pas)
program auto;
uses crt;
type pereche=record
x,y:byte;
end;
mat=array[0..20,0..20]of integer;
sir=array[1..40] of pereche;
var f:text;
a,b:mat;
c,cmax:sir;
Sn,Snmax,n,i,j,m,kmax:integer;
Procedure drum(m,n:integer;c:sir);
var l:integer;
begin
for l:=1 to kmax do
writeln(c[l].x,',',c[l].y);
end;
Function oprire:boolean;
var i,j:integer;
begin
oprire:=true;
for i:=1 to m do
for j:=1 to n do
if b[i,j]>0 then oprire:=false;
end;
Procedure mers(k,i,j:integer);
var l:integer;
begin
if b[i,j]<> -1 then
begin
sn:=sn+a[i,j]-1;
b[i,j]:=-1;
c[k].x:=i;
c[k].y:=j;
if oprire then
begin
if SN>Snmax then
begin
Snmax:=Sn;
cmax:=c;
kmax:=k;
end;
end
else
begin
if (SN>0) and (i>1) then mers(k+1,i-1,J);
if (SN>0) and (j<n) then mers(k+1,i,J+1);
if (SN>0) and (i<m) then mers(k+1,i+1,J);
if (SN>0) and (j>1) then mers(k+1,i,J-1);
end;
sn:=sn-a[i,j]+1;
b[i,j]:=a[i,j];
end;
end;
begin
assign(f,'mat.in');
reset(f);
read(f,m,n);
for i:=1 to m do
for j:=1 to n do
read(f,a[i,j]);
SNmax:=0;
b:=a;
for i:=1 to m do
for j:=1 to n do
if a[i,j]>0 then
mers(1,i,j);
writeln('Cantitate maxima adunata:', SNmax);
drum(m,n,cmax);
close(f);
end.
Probleme
P.1. Să se genereze toate aranjamentele de n luate câte m ale
mulţimii M = {1, 2, 3, …, n}, pentru n şi m date.
(probcurs\capIV\p1.pas)
P.2. Să se genereze toate combinările de n luate câte m ale
mulţimii M = {1, 2, 3, …, n}, pentru n şi m date.
(probcurs\capIV\p2.pas)
P.3. Într-o bibliotecă sunt n titluri de cărţi. Un raft al
bibliotecii poate conţine doar m cărţi, m<n. Descrieţi toate
modurile de aşezare a celor n cărţi pe raftul de câte m astfel
încât titlurile să fie în ordine alfabetică.
(probcurs\capIV\p3.pas)
P.4. Un grup de n persoane conţine f femei. Să se formeze toate
delegaţiile posibile formate din m persoane care conţin exact p
femei. (m<=n, p <=f) (probcurs\capIV\p4.pas)
4. Programare dinamică
Metodele studiate pâna acum căutau soluţii într-un spaţiu de
soluţii posibile şi alegeau, în diverse moduri, mulţimi ale
acestora pe baza unor condiţii date. Dacă metoda Backtracking are o
complexitate exponenţială iar Greedy şi Divide et Impera erau
polinomiale, rezolvarea unor probleme se poate realiza polinomial dacă
se cere valoarea optimă a soluţiei.
Programarea dinamică face parte din categoria metodelor matematice,
bazate pe reguli de calcul şi deducţii, numite în literatura de
specialitate metode de scufundare. Metoda se apică problemelor de
optim şi constă în determinarea soluţiei pe baza unui şir de
decizii. Strategia generală de rezolvare a problemelor folosind metode
programării dinamice se bazează pe principiul optimalităţii
(Bellman R.) şi se bazează pe descompunerea problemei în
subprobleme. Spre deosebire de metoda Divide et Impera în care
subproblemele sunt independente, subproblemele rezolvate prin
programarea dinamică depind unele de altele unele subprobleme folosind
solutiile subproblemelor anterioare. Matoda propgramării dinamice
acţionează de jos în sus trecînd rezolvarea problemei prin stări
succesive. Metoda se caracterizează prin:
- evitarea calculării de mai multe ori a aceleiaşi subprobleme şi
păstrarea rezultatelor intermediare.
- se porneşte de la cele mai mici subprobleme şi pe baza unor
formule recursive se construiesc alte subprobleme.
-respectă principiul optimalităţii: Oricare ar fi o stare
iniţială şi decizia iniţială, deciziile rămase trebuie să
contituie o strategie optimă în raport cu starea care rezultă din
decizia anterioară.
Soluţia optimă nu este în general unică, la fel ca în cazul
medodei greedy.
Modelul general al metodei programării dinamice
Fie D1 , D2 , ... , Dn un şir de decizii care transformă problema
din starea Si-1 în starea Si , i=0,n. Trecerea de la o stare la alta
se face de regulă prin aplicarea unei recurenţe în deciziile care se
iau şi apoi calculul pe baza unor formule recursive.
De obicei, relaţiile de recurenţă sunt de două feluri:
- înainte
decizia Di depinde de deciziile Di+1, ... , Dn deci, deciziile se
iau începând de la n la 1.
- înapoi
decizia Di depinde de deciziile D1, ... , Di-1 deci, deciziile se
iau începând de la 1 la n.
Paşii pe care trebuie să-i parcurgem pentru a rezolva o problemă
folosind programarea dinamică se pot descrie prin următoarea
secvenţă:
• Defineşte structura unei soluţii optime
• Caută o formulă recursivă care permite calculul valorii
soluţiei optime într-o anumită stare.
• Calculează valoarea soluţiei optime „de jos în sus”
• Dacă pe lângă valoarea optimă se doreşte şi o soluţie
explicită parcurge de sus în jos şirul deciziilor şi contruieşte
soluţia.
Problemă
Un robot care funcţionează pe o platformă de formă
dreptunghiulară (mxn) se află în colţul din stânga sus şi prin
deplasare numai spre dreapta şi jos adună piese aflate pe platformă
şi ajunge în colţul din stânga jos. Dacă se dau piesele aflate la
intersecţia liniilor orizontale şi verticale ale platformei şi
robotul se poate deplasa doar pe aceste linii se cere numărul maxim de
piese pa care robotul le poate aduna la o trecere.
Exemplu:
M=6 şi N=7, valorile reprezintă numărul de piese, deplasarea se
face spre dreapta şi jos din fiecare punct.
1 0 3 0 0 2 0
2 0 2 0 3 0 1
0 2 3 0 4 5 6
0 0 0 0 0 0 0
0 9 0 8 0 7 0
4 0 5 0 6 7 8
Numărul maxim de piese adunate este 42.
Problema se poate rezolva folosind metode Backtracking dar eficienţa
este foarte mică la matrice de dimensiuni mari.
Vom încerca o gândire inductivă pentru a definii structura
problemei. Să presupunem că matricea are dimensiunea 2. Atunci
maximul pieselor se obţine în trei etape. În poziţia (1,2) voi
aduna 1 piesă, în (2,1) 3 piese, deci în (2,2) maximul posibil va fi
3. Această valoarea este maximul dintre numărul de piese adunate în
poziţiile imediat anterioare poziţiei în care se află, şi din care
poate ajunge în poziţia curentă. Vom extinde la m=2 şi n=3 problema
şi vom obţine succesiv
1 1 1
1 1 3 deci maxim 3. Unde fiecare element este maximul dintre
elementele aflate pe poziţiile (i-1,j), (i,j-1) la care adăugăm
valoarea curentă.
În final se obţine:
1 1 1 1 1 1 1
1 1 3 3 6 6 7
1 3 6 6 10 15 21
1 3 6 6 10 15 21
1 12 12 20 20 27 27
1 12 17 20 26 34 42 unde 42 reprezintă maximul căutat.
Să definim formula de recurenţă:
Fie A(i,j), i=1,m, j=1,n, matricea pieselor, iar B(i,j) matricea
stărilor. Atunci următoarea formulă de recurenţă defineşte
problema noastră.
B(i,j)= max(B(i-1,j),B(i,j-1))+ A(i,j),
unde i=1,m, j=1,n,
şi vom considera B(i,0)=B(0,j)=0.
Calculâd succesiv, pe linii, valorile maxime folosind relaţia de
recurenţă, elementul de pe poziţia (m,n) ne dă valoarea maximă
căutată.
Încercând să găsim şi un drum pe care să-l parcurgă robotul vom
pleca din (m,n) şi vom alege, în sens invers poziţia (i-1,j) sau
(i,j-1) dacă şi numai dacă diferenţa între
(B(i,j)-B(i-1,j))=A(i,j) respectiv B(i,j),B(i,j-1))=A(i,j). Deci un
drum invers este 42, 34, 27, 20, 12, 12, 3, 3, 1, 1.
Soluţia problemei este dată în Probleme\41Metode\Dinamica\
robot.pas.
V. Grafuri. Arbori. Reprezentare şi algoritmi elementari.
5.1. Grafuri
Definiţie
Un graf orientat (sau digraf) G este o pereche (V, E), unde V este o
mulţime finită, iar E este o relaţie binară pe V, definită prin
perechi ordonate (x, y).
Mulţimea V se numeşte mulţimea vârfurilor lui G, iar elementele ei
se numesc vârfuri. Mulţimea E se numeşte mulţimea arcelor lui G,
şi elementele ei se numesc arce.
(a) (b) (c)
Figura 5.1. Grafuri orientate şi neorientate
(a) Un graf orientat G = (V, E), unde V = {1, 2, 3, 4, 5, 6}şi E =
{(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}. Arcul
(2, 2) este o autobuclă.
(b) Un graf neorientat G = (V, E), unde V = {1,2,3,4,5,6} şi E = {(1,
2),(1, 5),(2, 5),(3, 6)}. Vârful 4 este izolat.
(c) Subgraful grafului de la (a) indus de mulţimea de vârfuri {1, 2,
3, 6}.
Figura 1 (a) este o reprezentare grafică a unui graf orientat cu
mulţimea de vârfuri {1, 2, 3, 4, 5, 6}. În figură, vârfurile sunt
reprezentate prin cercuri, iar arcele prin săgeţi. Observaţi că
sunt posibile autobuclele - arce de la un vârf la el însuşi.
Definiţie
Într-un graf neorientat G =(V, E), mulţimea muchiilor E este
construită din perechi de vârfuri neordonate, şi nu din perechi
ordonate. Cu alte cuvinte, o muchie este o mulţime {u, v}, unde u, v
aparţin lui V şi u diferit de v. Prin convenţie, pentru o muchie vom
folosi notaţia (u, v) în locul notaţiei pentru mulţimi {u, v}, iar
(u, v) şi (v, u) sunt considerate a fi aceeaşi muchie. Într-un graf
neorientat, autobuclele sunt interzise şi astfel fiecare muchie este
formată din exact două vârfuri distincte.
Figura 1 (b) este o reprezentare grafică a unui graf neorientat
având mulţimea de vârfuri V={1, 2, 3, 4, 5, 6}
Multe definiţii pentru grafuri orientate şi neorientate sunt
aceleaşi, deşi anumiţi termeni pot avea semnificaţii diferite în
cele două contexte.
Definiţie
Dacă (u, v) este un arc într-un graf orientat G = (V, E), spunem că
(u, v) este incident din sau pleacă din vârful u şi este incident
în sau intră în vârful v.
De exemplu, arcele care pleacă din vârful 2, în figura 1, sunt (2,
2), (2, 4) şi (2, 5). Arcele care intră în vârful 2 sunt (1, 2) şi
(2, 2).
Definiţie
Dacă (u, v) este o muchie într-un graf neorientat G = (V, E), spunem
că (u, v) este incidentă vârfurilor u şi v.
În figura 1 (b), muchiile incidente ale vârfului 2 sunt (1, 2) şi
(2, 5).
Definiţie
Dacă (u, v) este o muchie (arc) într-un graf G = (V, E), spunem că
vârful v este adiacent vârfului u. Atunci când graful este
neorientat, relaţia de adiacenţă este simetrică. Când graful este
orientat, relaţia de adiacenţă nu este neapărat simetrică. Dacă v
este adiacent vârfului u într-un graf orientat, uneori scriem
u v.
În părţile (a) şi (b) ale figurii 1, vârful 2 este adiacent
vârfului 1, deoarece muchia (arcul) (1, 2) aparţine ambelor grafuri.
Vârful 1 nu este adiacent vârfului 2 în figura 1 (a), deoarece
muchia (2, 1) nu aparţine grafului.
Definiţie
Gradul unui vârf al unui graf neorientat este numărul muchiilor
incidente acestuia.
De exemplu, vârful 2, din figura 1 (b), are gradul 2. Un vârf al
cărui grad este 0, cum este, de exemplu, vârful 4, din figura 1 (b),
se numeşte vârf izolat.
Într-un graf orientat, gradul exterior al unui vârf este numărul
arcelor ce pleacă din el, iar gradul interior al unui vârf este
numărul arcelor ce intră în el. Gradul unui vârf al unui graf
orientat este gradul său interior, plus gradul său exterior.
Vârful 2 din figura 1 (a) are gradul interior 2, gradul exterior 3
şi gradul 5.
Definiţie
Un drum de lungime k de la un vârf u la un vârf z într-un graf G =
(V, E) este un şir de vârfuri (v0, v1, v2,..., vk) astfel încât u =
v0, z = vk şi (v(i-1), vi) aparţin lui E pentru i=1, 2,..., k.
Lungimea unui drum este numărul de muchii (arce) din acel drum. Drumul
conţine vârfurile v0, v1, v2,..., vk şi muchiile (v0, v1), (v1,
v2),..., (vk-1, vk). Dacă există un drum p de la u la z, spunem că z
este accesibil din u prin p.
Definiţie
Un drum este elementar dacă toate vârfurile din el sunt distincte.
În figura 1 (a), drumul (1, 2, 5, 4) este un drum elementar de
lungime 3. Drumul (2, 5, 4, 5) nu este elementar.
Un subdrum al unui drum p = (v0, v1,..., vk) este un subşir continuu
al vârfurilor sale. Cu alte cuvinte, pentru orice 0 i j
k, subşirul de vârfuri (v0, v1, v2,..., vk) este un subdrum al lui p.
Definiţie
Într-un graf orientat, un drum (v0, v1,..., vk) formează un ciclu
dacă v0 = vk şi drumul conţine cel puţin o muchie. Ciclul este
elementar dacă, pe lângă cele mai de sus, v1, v2,..., vk sunt
distincte. O autobuclă este un ciclu de lungime 1. Două drumuri (v0,
v1,..., v(k-1), v0) şi (w0, w1,... w(k-1), w0) formează acelaşi
ciclu dacă există un număr întreg j astfel încât wi = w(i+j) mod
k pentru i = 0, 1,..., k-1.
În figura 1 (a), drumul (1, 2, 4, 1) formează acelaşi ciclu ca
drumurile (2, 4, 1, 2) şi (4, 1, 2, 4). Acest ciclu este elementar,
dar ciclul (1, 2, 4, 5, 4, 1) nu este elementar. Ciclul (2, 2) format
de muchia (2, 2) este o autobuclă.
Definiţie
Un graf orientat fără autobucle este elementar.
Într-un graf neorientat, un drum (v0, v1,..., vk) formează formează
un ciclu elementar dacă k3, v0 = vk şi vârfurile v1, v2,..., vk
sunt distincte.
De exemplu, în figura 1 (b), drumul (1, 2, 5, 1) este un ciclu.
Definiţie
Un graf fără cicluri este aciclic.
Propoziţie
Un graf neorientat este conex dacă fiecare pereche de vârfuri este
conectată printr-un drum. Componentele conexe ale unui graf sunt
clasele de echivalenţă ale vârfurilor sub relaţia "este accesibil
din".
Graful din figura 1 (b) are trei componente conexe: {1, 2, 5}, {3, 6}
şi {4}. Fiecare vârf din {1, 2, 5} este accesibil din fiecare vârf
din {1, 2, 5}.
Propoziţie
Figura 5.2. (a) (b) (c)
Un graf neorientat este conex dacă are exact o componentă conexă,
sau, altfel spus, după fiecare vârf este accesibil din fiecare vârf
diferit de el.
Un graf orientat este tare conex dacă fiecare două vârfuri sunt
accesibile din celălalt. Componentele tare conexe ale unui graf sunt
clasele de echivalenţă ale vârfurilor sub relaţia "sunt reciproc
accesibile". Un graf orientat este tare conex dacă are doar o singură
componentă tare conexă.
Graful din figura 5.2. (a) are trei componente tare conexe: {1, 2, 4,
5}, {3} şi {6}. Toate perechile de vârfuri din {1, 2, 4, 5} sunt
reciproc accesibile. Vârfurile {3, 6} nu formează o componentă tare
conexă, deoarece vârful 6 nu este accesibil din vârful 3.
5.2. Arbori
Definiţie
Un arbore este un graf neorientat, aciclic şi conex. Dacă un graf
neorientat este aciclic, dar s-ar putea să nu fie conex, el formează
o pădure. Mulţi algoritmi pentru arbori funcţionează, de asemenea,
şi pentru păduri.
Figura 2 (a) prezintă un arbore liber, iar figura 2 (b) prezintă o
pădure. Pădurea din figura 2 (b) nu este arbore şi pentru că nu
este conexă. Graful din figura 2 (c) nu este nici arbore şi nici
pădure, deoarece conţine un ciclu. Următoarea teoremă prezintă
într-o formă concentrată multe proprietăţi importante ale
arborilor.
Teoremă (Proprietăţile arborilor)
Fie G = (V, E) un graf neorientat. Următoarele afirmaţii sunt
adevărate:
1. G este un arbore.
2. Oricare două vârfuri din G sunt conectate printr-un drum
elementar unic.
3. G este conex, dar, dacă eliminăm o muchie oarecare din E, graful
obţinut nu mai este conex.
4. G este conex, şi |E| = |V| - 1.
5. G este aciclic, şi |E| = |V| - 1.
6. G este aciclic, dar dacă adăugăm o muchie oarecare în E, graful
obţinut conţine un ciclu.
Demonstraţia acestei teoreme se găseşte în [4] la pag. 79.
Definiţie
Un arbore cu rădăcină este un arbore în care unul din vârfuri se
deosebeşte de celelalte. Acest vârf se numeşte rădăcină. Pentru
un vârf al arborelui vom folosi uneori denumirea de nod.
5 Nivel 0
4 2 Nivel 1
3 1 7 Nivel 2
6 8 Nivel 3
Fig. 5.3. Arbore binar, reprezentat pe nivele.
În exemplul de mai sus nodul 5 este rădăcina.
Orice nod aflat pe un drum de la rădăcină spre orice alt nod se
numeşte strămoş al rădăcinii, sau al unui alt nod. Dacă se
consideră un nod x şi toţi strămoşii săi spunem că avem un
subarbore de rădăcină x. De exemplu subarborele lui 4 conţine {4,
3, 1, 6, 8}.
Un arbore este definit pe nivele, începând cu nivelul 0. O muchie
(x, y) în care x este pe un nivel inferior lui y este în relaţia
părinte copil astfel:
x este părintele lui y, iar y este copilul lui x.
De exemplu 2 este părintele lui 7, iar 7 este copilul lui 2.
Definiţie
Un nod care nu are copii se numeşte frunză.
Numărul de copii ai unui nod se numeşte gradul nodului.
Lungimea drumului de la rădăcină la un nod x se numeşte adâncimea
nodului x. Cel mai mare grad n, dintre gradele tuturor nodurilor, este
gradul arborelui şi arborele se numeşte arbore n-ar (pentru n=2,
arbore binar). De exemplu, arborele din figură este binar.
Definiţie
Un arbore binar se defineşte în mod recursiv ca fiind o structură
definită pe o mulţime finită de noduri prin:
• Nu conţine nici un nod, sau
• Conţine trei mulţimi:
1. un nod rădăcina,
2. un arbore binar numit subarborele stâng şi
3. un arbore binar numit subarborele drept.
5.3. Reprezentarea grafurilor şi a arborilor binari
Reprezentarea grafurilor sau a arbori în algoritmi se realizează
folosind structuri de date statice sau dinamice, respectiv tablouri sau
liste.
Un graf G=(X,U) cu n vârfuri se poate reprezenta prin:
a) Matricea de adiacenţă
Matrice pătratică de ordin n, definită prin
A(i,j)= 1 , pentru (i,j) din U
A(i,j)=0 , în caz contraj, pentru orice pereche (i,j) din U.
Matricea de adiacenţă asociată grafului din Fig. 5.1. (b)este:
b) Matricea de incidenţă
Se utilizează la reprezentarea grafurilor orientate fără bucle, în
care mulţimea arcelor este ordonată şi numerotată U={1,2,3,...,m}
unde m este numărul arcelor. Astfel matricea are n linii
corespuzătoare vârfurilor i=1,n şi m coloane corespunzătoare
arcelor, definită prin:
B(i,u)= 1 , dacă există j din X astfel încât u=(i,j)
B(i,u)= -1 , dacă există j din X astfel încât u=(j,i)
B(i,u)= 0 , altfel
Aplicaţie: Construiţi matricea de incidenţă asociată
grafului din Fig. 5.1. (a), fără bucla nodului 2, cu muchiile
numerotate astfel: 1- (1,2), 2- (2,4), 3 - (2,5), 4 - (4,5), 5- (5,4),
6- (4,1).
c) Lista arcelor
Pentru reprezentare se utilizează două tablouri unidimensionale cu m
valori care reprezintă extremităţile arcelor din U. Şirurile a(i),
b(i), i=1,m, reprezintă extremitatea iniţială şi respectiv finală
a unui arc, u=(a(i), b(i)).
Grafului din Fig. 5.1. (a), fără bucla nodului 2, cu muchiile
(1,2), (2,4), (2,5), (4,1), (4,5), (5,4), îi corespund şirurile:
a: 1, 2, 2, 4, 4, 5
b: 2, 4, 5, 1, 5, 4
Obs. Se recomandă ordonarea şirurilor după vârfurile iniţiale şi
finale.
d) Lista succesorilor (predecesorilor)
Se utilizează două şiruri A şi B. Şirul A, de lungime n+1 reţine
pe poziţia i poziţia din şirul B de la care încep succesorii
vârfului i. Şirul B conţine între poziţiile A(i) şi A(i+1)-1
inclusiv, toţi succesorii vârfului i. Dacă poziţiile A(i) şi
A(i+1) au aceeaşi valoare atunci i nu are succesori.
Grafului din Fig. 5.1. (a), fără bucla nodului 2, cu muchiile
(1,2), (2,4), (2,5), (4,1), (4,5), (5,4), îi corespund şirurile:
A: 1, 2, 4, 4, 6
B: 2, 4, 5, 1, 5, 4
(am aşezat sugestiv unul sub altul, cele două şiruri. De exemplu
i=3 nu are succesori, incepând de pe poziţia 4 din B, iar i=4 are 2
succesori incepând cu poziţia 4 din şirul B).
Observaţie.
Lista predecesorilor se obţine în mod similar precizând pentru
fiecare vârf predecesorul său.
e) Liste de adiacenţă
Pentru fiecare vârf al grafului neorientat se păstrează câte o
listă care conţine toate vârfurile adiacente cu acesta. Numărul
listelor va fi egal cu numărul vârfurilor, eventualele vîrfuri
izolate vor avea liste vide.
Graful din Fig. 5.1. (b), va conţine 6 liste după cum urmează:
1. 2, 5
2. 1, 5
3. 6
4. listă vidă
5. 1, 2
6. 3
Reprezentarea grafurilor orientate folosind liste de adiacenţă se
realizează prin precizarea orientării, deci lista va conţine doar
vârfurile adiacente lui i.
f) Reprezentarea arborilor binari
Cea mai frecventă modalitate de reprezentare a arborilor binari se
bazează pe utilizarea listelor dublu înlănţuite.
Definim o structură a listei sub forma:
type arbore=^nod;
nod=record
FiuStanga, FiuDreapta:nod;
inf:TipInformatie;
end;
Adresa primului elemnet din listă se consideră adresa rădăcinii.
Arborele din Fig. 5.3. se reprezintă sub forma:
inf FiuSt FiuDr inf FiuSt FiuDr
5 4 2 2 nil 7
4 3 1 1 6 8
3 nil Nil 7 nil Nil
6 nil Nil 8 Nil Nil
Dacă în reprezentarea arborilor se doreşte deplasarea în structura
arborescentă şi înspre părinte, se adaugă adresa părinteluui
fiecărui nod, pentru radacină nil şi definţia structurii devine:
type arbore=^nod;
nod=record
FiuStanga, FiuDreapta, Parinte:nod;
inf:TipInformatie;
end;
cu următoarea reprezentare pentru arborele de mai sus:
inf FiuSt FiuDr Parinte inf FiuSt FiuDr
Parinte
5 4 2 nil 2 nil 7 5
4 3 1 5 1 6 8 4
3 nil Nil 4 7 nil Nil 2
6 nil Nil 1 8 Nil nil 1
Exemple de probleme care folosesc reprezentarea arborilor binari se
află în directorul Probleme\5Grafuri\Arbori.
5.4. Algoritmi elementari
5.4.1. Parcurgerea grafurilor
Să considerăm problema parcurgerii nodurilor unui graf neorientat.
Pornind de la un nod oarecare se poate parcurge graful prin alegearea
unei muchii incidente în vârful initial, care ne va duce la un nou
nod nevizitat. Algoritmul continua prin alegearea din noul vârf a unei
muchii incidente cu acesta care să ne ducă într-un vârf nevizitat,
şi aşa mai departe. La epuizarea tuturoe drumurilor dintr-un vârf se
revine la vârful anterior şi se continuă algoritmul până la
epuizarea vârfurilor. O astfel de parcurgere se numeşte parcurgere
în adâncime sau „DEPTH-FIRST” (DF).
5
4 2
3 1 7
6 8
Parcurgerea grafului (arborelui) de mai sus folosind algoritmul DF
începând cu vârful 1, iar alegearea nodurilor vecine se face în
ordine crescătoare, este:
1, 4, 3, 5, 2, 7, 6, 8
Algoritmul care realizează parcurgerea „DEPTH-FIRST”, foloseşte
tehnica Backtracking.
Procedura DF ( i )
Vizit (i) = -1
{şirul nodurilor nevizitate se iniţializează cu 0, fiecare nod
vizitat e marcat cu -1}
Pentru „orice nod j vecin cu i” execută
Dacă Vizit (i)=0 atunci
DF (j)
Sf dacă
Sf Pentru
Parcurgerea întregului graf este asigurată prin apelul procedurii DF
pentru toate nodurile nevizitate.
Pentru i=1,n,1 execută
Dacă Vizit (i)=0 atunci
DF (i)
Sf dacă
Sf Pentru
(Programul Probcurs\capV\df1.pas recursiv, respectiv df.pas varianta
nerecursivă)
type matrice=array[1..100,1..100] of 0..1;
var a:matrice;
viz:array[1..100] of 0..1;
j,n:integer;
timp:longint absolute $000:$046C;
timpinit:longint;
Procedure citiregraf(var a:matrice;var n:integer);
var f:text;
x,y:byte;
begin
assign(f,'bf1.in');
reset(f);
readln(f,n);
while not (eof(F)) DO
begin
readln(f,x,y);
a[x,y]:=1;
a[y,x]:=1;
end;
close(f);
end;
Procedure back(i:integer);
var j:byte;
begin
write(i,',');
viz[i]:=1;
for j:=1 to n do
begin
if (a[i,j]=1) and (viz[j]=0) then
back(j);
end;
end;
begin
timpinit:=timp;
writeln('timpinit: ',timpinit);
citiregraf(a,n);
readln(j);
back(j);
writeln('timp: ',timp);
writeln;
end.
Dacă la fiecare vârf vizitat se continuă cu toate vârfurile
adiacente acestuia, vizitate pe rând, acestea în ordine crescătoare,
parcurgerea se realizează în „lăţime” sau „BREATH-FIRST”
(BF). Parcurgerea grafului de mai sus BF, pornind de la 1 este:
1, 4, 6, 8, 3, 5, 2, 7
Algoritmul care realizează parcurgerea „BREATH-FIRST” foloseşte
acelaşi şir Vizit (i) care marchează nodurile vizitate dar şi o
listă de tip coadă în care sunt introduse nodurile care au fost
vizitate dar ai căror vecini nu au fost incă prelucraţi.
Procedura BF extrage pe rând câte un element din coadă, introduce
apoi descendenţii săi care nu au fost vizitaţi şi îi vizitează.
Procedura BF ( i )
{se iniţializează coada}
PUSH (i)
Vizit (i) = 1
{prelucrare nod i}
Cât timp „coada nu este vidă” execută
j = POP
Pentru „toţi vecinii k a lui j” execută
Dacă Vizit (k)=0 atunci
PUSH (k)
Vizit (k) = 1
{prelucrare nod k}
Sf dacă
Sf Pentru
Sf cât timp
(Programul Probcurs\capV\bf1.pas)
type matrice=array[1..100,1..100] of 0..1;
sir=array[1..100] of byte;
var a:matrice;
x,y:sir;
i,j,h,ii,p,n,m,t:byte;
f:text;
ok:boolean;
Procedure citire(var a:matrice);
begin
assign(f,'bf1.in');
reset(f);
readln(f,n,m);
for h:=1 to m do
begin
readln(f,i,j);
a[i,j]:=1;
a[j,i]:=1;
end;
readln(f,j);
close(f);
assign(f,'bf1.out');
rewrite(f);
end;
begin
citire(a);
y[j]:=1;
t:=1;
x[t]:=j;
p:=1;
repeat
for i:=1 to n do
begin
if (a[x[p],i]=1) AND (y[i]=0) then
begin
t:=t+1;
x[t]:=i;
y[i]:=1;
end;
end;
inc(p);
until (t=n) ;
for i:=1 to n do
write(f,x[i],' ');
close(f);
end.
5.4.2. Conexitatea unui graf
Un graf conex se poate verifica prin apelul procedurilor DF sau BF
pornind de la oricare nod şi verificând apoi dacă toate vârfurile
au fost vizitate. În caz afirmativ graful este conex.
Un algoritm similar care verifică dacă un graf este conex, pornind
de la nodul k, este următorul:
Procedura Conex ( k )
Pentru i=1,n,1 execută
Vizit (i)=0
Sf Pentru
BF (k)
Cod = true
I = 1
Cât timp i<=n and cod execută
Dacă Vizit (i)=0 atunci
Cod=false
Sf dacă
i=i+1
Sf cât timp
Daca cod atunci
* Graf conex
altfel
* Graf neconex
sf daca
(Programul Probcurs\capV\conexit.pas)
type matrice=array[1..100,0..100] of byte;
sir=array[1..100] of byte;
var x:matrice;
viz,a:sir;
n,m,t,k,i,j,h:byte;
f:text;
Procedure citire;
begin
assign(f,'conexit.in');
reset(f);
readln(f,n);
for i:=1 to n do
begin
viz[i]:=0;
x[i,0]:=0;
end;
while not eof(f) do
begin
readln(f,i,t);
x[i,0]:=x[i,0]+1;
x[i,x[i,0]]:=t;
x[t,0]:=x[t,0]+1;
x[t,x[t,0]]:=i;
end;
close(f);
end;
begin
citire;
write('introduceti varful a carui vecini ii doriti: ');readln(m);
viz[m]:=1;
a[1]:=m;
k:=1;
for i:=2 to x[m,0]+1 do
if viz[x[m,i-1]]=0 then
begin
k:=k+1;
viz[x[m,i-1]]:=1;
a[k]:=x[m,i-1];
end;
i:=1;
repeat
i:=i+1;
for j:=1 to x[a[i],0] do
begin
if viz[x[a[i],j]]=0 then
begin
viz[x[a[i],j]]:=1;
k:=k+1;
a[k]:=x[a[i],j];
end;
end;
until i=k;
writeln('vecini acestui varf sunt: ');
for i:=1 to k do
write(a[i],' ');
writeln;
readln;
end.
5.4.3 Arbori parţiali
Dacă unui graf G = (X,U) ataşăm fiecărei muchii un cost, c(i,j),
se pune problema determinării unui arbore parţial, al grafului dat,
cu proprietatea ca suma costurilor muchiilor arborelui este minimă.
Această problemă este cunoscută ca problema determinării arborelui
parţial de cost minim într-un graf dat.
Un algoritm care determină acest arbore prin alegerea muchiilor în
ordine crescătoare a valorilor costurilor cu condiţia ca muchia
aleasă să nu determine un ciclu împreună cu cele deja alese,
Algoritmul lui Kruskal.
Procedura Kruskal (G)
{Ordonează lista muchiilor crescător după cost c(i,j), fie aceasta
uk, k=1,m}
i=1
a(i)=u(1)
Pentru k=2,m,1 execută
Dacă „u(k) nu formează cicluri” atunci
i=i+1
a(i)=u(k)
sf daca
Sf pentru
(Programul Probcurs\capV\apm.pas)
type sir=array[1..100] of byte;
as=record
i,j,k:byte;
end;
asd=array[1..100] of as;
var a:asd;
x,y:sir;
ok:boolean;
d,n,m,i,j,k,t,s,p:byte;
Procedure citire;
var f:text;
begin
assign(f,'apm.in');
reset(f);
readln(f,n);
t:=0;
m:=1;
while not eof(f) do
begin
readln(f,i,j,k);
t:=t+1;
if i>m then m:=i;
if j>m then m:=j;
a[t].i:=i;
a[t].j:=j;
a[t].k:=k;
end;
p:=m;
m:=t;
close(f);
for i:=1 to p do
x[i]:=i;
end;
Procedure ordonare;
begin
for i:=1 to m-1 do
for j:=i+1 to m do
if a[j].k<a[i].k then
begin
t:=a[i].i;
a[i].i:=a[j].i;
a[j].i:=t;
t:=a[i].j;
a[i].j:=a[j].j;
a[j].j:=t;
t:=a[i].k;
a[i].k:=a[j].k;
a[j].k:=t;
end;
end;
begin
citire;
ordonare;
s:=0;
t:=0;
i:=0;
repeat
i:=i+1;
if not (x[a[i].i]=x[a[i].j]) then
begin
s:=s+a[i].k;
t:=t+1;
y[t]:=i;
if x[a[i].i]<x[a[i].j] then
begin
d:=x[a[i].j];
for j:=1 to n do
if x[j]=d then
x[j]:=x[a[i].i];
end
else if x[a[i].i]>x[a[i].j] then
begin
d:=x[a[i].i];
for j:=1 to n do
if x[j]=d then
x[j]:=x[a[i].j];
end;
end;
ok:=false;
for j:=1 to p-1 do
if not (x[j]=x[j+1]) then ok:=true;
until ((t=p-1) and (ok=false)) or (i=m);
writeln('s= ',s);
for i:=1 to p-1 do
write('(',a[y[i]].i,',',a[y[i]].j,') ');
writeln;
writeln;
readln;
end.
VI. Teste
Test 1
1. “Principiul cutiei negre” se bazează pe următoarele principii:
a) programatorul nu cunoaşte nimic despre structura internă a
programului şi despre datele de intrare.
b) reprezintă totala independenţă a programatorului în interiorul
programului său, legătura cu exteriorul făcâdu-se strict pe baza
formatului datelor de intrare şi a celor de ieşire
c) se impune respectarea unor reguli interne deci a unui standard
vizibil şi din exteriorul programatorului.
2. Evitarea folosirii specificului calculatorului, cum ar fi elemente
de afişaj specific (rezoluţii, plăci grafice, tipuri de interfeţe),
transmisie de date (reţele locale, unităţi de disc specifice),
dispozitive periferice (tipuri de imprimante) şi respectiv medii de
programare sau sisteme de operare, reprezintă principiul enunţat de:
a) Verifică corectitudinea algoritmului şi a programului în fiecare
etapă a elaborării.
b) Asigurară portabilitatea programului
c) Proiectează structurat algoritmii
3. Programul de mai jos realizează următoarele operaţii:
Var var_fis:text;
C: char;
Begin
Assign(var_fis, 'TEST.DAT');
Reset(var_fis);
While not Eof(var_fis) do
begin
Readln(var_fis,c)
WriteLn(c)
end;
Close(var_fis)
end.
a) Deschide fisierul TEST.DAT, de tip text, citeşte primul caracter de
pe fiecare linie din fişier şi afişează caracterul pe ecran pe
câte o linie fiecare.
b) Deschide fisierul TEST.DAT, de tip text, citeşte caracter cu
caracter din fişier până la sfârşitul fişierului şi afişează
caracterele pe ecran pe o singură linie.
c) Deschide fisierul TEST.DAT, de tip text, citeşte primul caracter
din fişier până la sfârşitul fişierului şi afişează
caracterele pe o linie pe ecran.
4. Fie următoarele definiţii de tipuri şi variabile:
type sir=array[0..10] of real;
mat= array[1..5] of sir;
var a,b:sir;
x:mat;
k:integer;
Care din următoarele operaţii sunt corecte:
a) k:=4; a[1,k]=3.5 b) k:=0; b[k]:=a[7] c) x[3]:=a d) x[1,0]:=b[5]
5. Următoarea declaraţie de tip corespunde unei structuri dinamice de
tip:
type nod=^elem;
elem=record
st,dr:nod;
inf:integer;
end;
a) coada b)stiva c) incorectă c) listă dublu înlănţuită
6. Pentru polinomul P(X)=7X50+15X5-4X3+6 reprezentaţi coeficienţii
şi gradul lor folosind o lista simplu înlănţuită.
7. Descrieţi o functie de adăugare a unui element într-o stivă.
Antetul funcţiei, folosind definiţiile de date de la exerciţiul 6,
este:
Function AdaugaStiva(S:nod; e:elem):nod;
8. Scrieţi procedura de citire a unui graf, dat ca perechi de muchii
într-un fişier text, pentru care se crează matricea de adiacenţă.
Procedura va avea urmatorul antet:
Procedure graf(var f:text;var n:byte;var a:matrice);
1. b); 2. b); 3. a); 4. b),d); 5) c.
Test 2
1. Functia Valid împreună cu procedura backtracking descrise mai jos
rezolvă problema:
Function valid(i:byte):boolean;
Var cod:boolean;
j:byte;
begin
cod:=true;
for j:=1 to i-1 do
if x[i]=x[j] then cod:=false;
valid:=cod;
end;
procedure Back(j:byte);
var i:byte;
begin
for i:=1 to n do
begin
x[j]:=i;
if valid(j) then
if j<k then Back(j+1)
else solutie(x,k);
end;
a) Permutărilor b) Combinărilor c) Aranjamentelor
2. Parcurgerea în adâncime (DF), pornind de la vârful 3, a grafului
din figura de mai jos este:
a) 3,1,2,5,4,6 b) 3, 1, 2, 4, 5, 6 c) 3,2,4,1,5,6
3. Alegeţi corespunzător liniile care lipsesc din următorul algoritm
pentru a descrie corect tehnica Greedy:
Algoritm Greedy (A, n, B);
Cod : boolean;
B ← {Mulţimea vidă};
Pentru i=1, n,1 execută
_____________________
_____________________
Dacă cod atunci
Adaug (B, x);
Sf dacă;
Sf pentru;
a) Alege (A,n,x) b)Alege(A,i,x) c)Alege(A,i,x )
Posibil(A,x,cod) Posibil(B,n,cod) Posibil(B,x,cod)
4. Descrieţi algoritmul de sortare prin selecţie
5. Descrieţi algoritmul de căutare binară
6. Arborele parţial de cost minim corespunzător grafului (2) are
costul:
a) 39 b) 42 c) 38
d) 40
1. c) 2. b) 3. c) 6. b)
VII. Bibliografie
1. Andone R., Gârbacea I., Algoritmi fundamentali o perspectivă C++,
Editura Libris, Cluj Napoca, 1995.
2. Böhm C., Jacopini T.C., Flow diagrams, Turing Machines and
Languages with only two Formation Rules, CACM 9, 5, 1966.
3. Calude C., Complexitatea calcului, aspecte calitative, Editura
Ştiinţifică şi Enciclopedică, Bucureşti, 1982.
4. Cormen T.H., Leiserson E.C., Rivest R.R., Introducere în algoritmi,
Editura Libris Agora, 2000 (traducere în limba română).
5. Dahl O.J., Dijkstra E.W., Hoare C.A.R., Structured Programing,
Academic Press, 1972.
6. Lazăr, M. Frenţiu, S. Motogna, V. Prejmerean, Elaborarea
algoritmilor, Ed. Presa Universitară Clujeană, Cluj Napoca, 1998
7. Lazăr, M. Frenţiu, S. Motogna, V. Prejmerean, Programare Pascal,
Ed. Presa Universitară Clujeană, Cluj Napoca, 1998
8. Lica D., Onea E., Informatică, Manual pentru clasa a IX-a, Editura
L&S, Bucureşti, 1999.
9. Livovschi L., Georgescu H., Sinteza şi analiza algoritmilor,
Editura Ştiinţifică şi Enciclopedică, Bucureşti, 1986.
10. McConnell S.C., Code Complete: a practical handbook of software
construction, Microsoft Press, Washington, 1993
11. Mitrana V., Provocarea algoritmilor, Editura Agni, Bucureşti,
1994.
12. Motogna S.,Metode şi tehnici de proiectare a algoritmilor,
Universitatea “Babeş Bolyai”, Cluj Napoca, 1998
13. Pólya G., How to solve it? A new aspect of mathematical method,
Princeton Univerity Press, 1957.
14. Rancea D., Limbajul Pascal. Algoritmi fundamentali., Editura
Computer Libris Agora, Cluj Napoca, 1999.
15. Tudor S., Cerchez E., Şerban M., Informatică. Manual pentru clasa
a IX-a, Editura L&S, Bucureşti, 1999.
16. Logofătu Hrinciuc E., Probleme rezolvate şi algoritmi, Editura
Polirom, 2001.
17. Pătrăşcoiu O., Marian G., Mitroi N., Elemente de grafuri şi
combinatorică. Metode, algoritmi şi programe, Editura All,
Bucureşti, 1994.
Cuprins
I. Introducere 4
II. Principiile programării calculatoarelor 6
III. Structuri de date 10
1. Noţiuni şi concepte preliminarii 10
2. Tipuri de date structurate. Definiţii şi clasificări. 11
2.1. Tablouri 11
2.2. Mulţime 14
2.3. Articol (înregistrare) 17
2.4. Fişier 21
2.4.1. Fişiere text 29
2.4.2. Fişiere cu tip 34
2.4.3. Fişiere fără tip (stream) 38
3. Structuri statice şi structuri dinamice. Liste 41
3.1. Liste. Structuri statice. Structuri dinamice. 41
3.2. Lista simplu înlănţuită 43
3.2.1. Specificarea structurii de date listă simplu înlănţuită 44
3.3. Tipuri de liste simplu înlănţuite 47
3.3.1. Stiva 47
3.3.2. Coada 48
3.3.3. Lista circulară 50
3.4. Lista dublu înlănţuită 51
4. Structuri de date dinamice 52
4.1. Tipuri de variabile (după durata de viaţă) 52
4.2. Tipul pointer 53
4.2.2. Declararea de variabile de tip pointer 55
4.3. Semantica variabilelor de tip pointer. Operaţii 55
4.3.1. Variabile pointer şi variabile dinamice asociate 55
4.3.2. Operaţia de atribuire. Semantica. 56
4.3.3. Alocarea variabilelor dinamice şi iniţializarea pointerilor 57
4.3.4. Dealocarea variabilelor dinamice 59
4.3.5. Probleme propuse 60
4.4. Structuri de date dinamice. Aplicaţii. 61
4.4.1. Aplicaţia stiva (p441.pas): 63
4.4.2. Aplicaţia coada (p442.pas): 63
4.4.3. Aplicaţia lista simplu înlănţuită (p443.pas): 65
4.4.4. Aplicaţia Lista dublu înlănţuită (p444.pas): 68
4.4.5. Aplicaţia listă circulară (p445.pas): 73
4.4.6. Probleme propuse 77
IV. Metode şi tehnici de programare 79
1. Metoda Greedy 79
2. Metoda Divide et Impera 82
2.1. Căutare şi sortare pentru structuri de date 83
2.2. Căutare binară 85
2.3. Sortarea rapidă 87
2.4. Sortare cu număr minim de comparaţii 89
3. Metoda Backtracking 90
4. Programare dinamică 100
V. Grafuri. Arbori. Reprezentare şi algoritmi elementari. 104
5.1. Grafuri 104
5.2. Arbori 108
5.3. Reprezentarea grafurilor şi a arborilor binari 109
5.4. Algoritmi elementari 112
5.4.1. Parcurgerea grafurilor 112
5.4.2. Conexitatea unui graf 116
5.4.3 Arbori parţiali 118
VI. Teste 121
VII. Bibliografie 126