MINISTERUL EDUCATIEI SI CERCETARII

COLEGIUL TEHNIC "G-RAL D. PRAPORGESCU"

MUNICIPIUL TURNU MAGURELE

JUDETUL TELEORMAN

Structuri de date

de tip liste

REFERAT

ABSOLVENT: .....................

TITLUL LUCRARII: .................

Calitatea exprimarii in termeni de specialitate:

pfoarte buna

pbuna

psatisfacatoare

pnesatisfacatoare

Contributia personala:

pfoarte bine

pbine

psatisfacator

pnesatisfacator

Observatii: ..................... ............................

Concluzii: ...................... ..........................

REFERENT, APRECIERE FINALA,

Data ___/___/___

TEMA LUCRARII

Sa se faca un studiu despre structurile de date de tip lista si sa se prezinte structura tip lista si structurile particulare de liste .

Lucrarea trebuie sa cuprinda :

Notiuni generale despre limbajul Turbo Pascal ;

Introducere in structura de date ;

Clasificarea structurilor de date ;

Structurile statice ;

Structuri de tip lista ;

Structuri particulare de tip lista ;

Implementarea algoritmului in limbajul Turbo Pascal ;

Rezolultatul obtinut dupa rularea programului ;

Bibliografia .

Referat ;

Tema lucrarii ;

Cuprins ;

Limbajul Turbo Pascal ;

Introducere in structura de date ;

Clasificarea structurilor de date ;

Structurile statice ;

Structuri de tip lista ;

Structuri particulare de tip lista ;

Implementarea algoritmului in limbajul Turbo Pascal ;

Rezolultatul obtinut dupa rularea programului ;

Bibliografia .

Notiuni de date

Principalele tipuri de date ale limbajului PASCAL sunt:

integer  ;

boolean  ;

char sau(* *)

Tipuri de date standard

Datele vehiculate in dialogul om-calculator,fie ca sunt constante,fie ca sunt variabile, pot fi de urmatoarele cinci tipuri de baza:tipul intreg(numere intregi),tipul real(numere reale),tipul alfanumeric(sir de caractere),tipul boolean(logic),tipul pointer si tipul enumerare.Aceste categorii de date sunt numite tipuri simple , in opozitie cu tipurilr structurate.

Constante

Asa cum am afirmat,constantele sunt informatii care se autodefinesc,spatiul de memorie necesar pastrarii lor fiind rezervat si gestionat de mediul de programare.

Constante numerice de tip intreg sunt numere intergi in sensul matematic cunoscut.

Exemple

0 +0 -0

3 +3 -3

950 -4567 +43

Limbajul Pascal standard accepta numere intregi din intervalul

Constante numerice de tip real

Numerele reale se scriu apelind la exponenti ai bazei(asa numita scriere stintifica a numerelor reale).De pilda, putem reprezenta constanta reala 19.55 in nenumarate moduri:

0.1955E2 0.01955E3 1955E-2

De aici ideea de scriere in virgula mobila a numerelor reale.Din infinitatea manierelor de scriere;cea evidentiata se numeste forma normala,unica pentru orice constanta.Ea este caracterizata de faptul ca se reprezinta printr-un numar sub unitar(0.1955)cu cifra zecilor (prima dupa marca zecimala) diferita de zero.Reprezentarea in calculator a constantelor reale se face pornind de la formula normala:

mantisa E exponent

iar la tiparire, in lipsa informatiilor pentru formatare este utilizata forma normala.

Constante logice(booleene)

Acestea sunt, de fapt, constante simbolice,fiind desemnate prin cuvintele false - corespunzatoare valorii logice fals(desemnata prin F in capitolul doi)

Si true - corespunzatoare valorii logice adevar (marcata cu A in acelasi capitol).

Reperezentarea in memoria calculatorului se face prin completarea cu valoarea 1 a zonei de memorie rezervate in cazul valorii logice adevar si,

respectiv , cu 0 in cazul valorii logice fals (de aici relatia flse <true).

Constante de tip alfanumeric

Aceasta categorie de constante reprezinta succesiuni de caractere ale limbajului (elemente din setul de caractere)avind sintaxa :

'succesiune de caractere'

Pentru a introduce caracterul apostrof (intr-o constanta alfanumerica Pascal),

se procedeaza ca in exemplul de mai jos:

'Emilia este ' serioasa' '

echivalent cu sirul

Emilia este 'serioasa'

Definirea constantelor

Cind o anume valoare apare in mod repetat este recomandabil a o 'boteza',mai ales in cazul in care ea are o scriere'lunga'.De pilda , in loc sa folosim in mod repetat constanta 312.054973 o definim sub un nume iar la fiecare aparitie a acestei valori vom scrie numele ce i

l-am dat.Definirea constantelor se face conform sintaxei :

const nume_variabila=valoare ;

Variabile

Ca si constantele,variabilele pot fi de tipurile amintite in paragraful anterior.Ele sunt desemnate prin identificatori alesi de programator,fiind recomandabil a fi sugestivi.In programe,orice variabila are un domeniu in care ia valori si pentru o utilizare corecta trebuie sa primeasca valori din domeniul respectiv

Definirea variabilelor

Variabilele se declara utilizind sintaxa :

Var nume_variabila :tip_variabila ;

Variabilele numerice

Definitia acestora se face apelind in simbolurile integer,byte,shortint,word,longint pentru tipul intreg si real,single,double,extended pe tipul real,prin care sunt evidentiate domeniile de valori standard posibile pentru variabile.Tipurile single ,

double,extende necesita coprocesor matematic.

Variabilele alfanumerice

Variabilele alfanumerice pot fi de tip caracter (evidentiate prin terminalul char si reprezentate pe un octet)sau de tip sir de caractere (marcate prin terminalul string in Pascal fiind reprezentate prin numarul de caractere necesare stocari sirului la care se adauga un caracter de control. In pascal acest caracter se adauga in fata si reprezinta numarul de caractere.

Exemplu :

Daca avem segventele

P :string ;

P:='Emi';

Atunci rezulta

P[1]='E' p[2]='m' p[3]='i'

P[0]=3

Variabile logice

Aceasta categorie de variabile este pusa in evidenta prin simbolul boolean.

Exemplu

Var B: boolean.

Constante si variabile

Programul poate contine anumite date a caror valoare nu se modifica,numite constante.Constantele limbajului PASCAL sunt :

-numere intregi ;

-numere reale ;

siruri de caractere ;

-constante desemnate prin identificatori.

Limbajul PASCAL desemneaza constante si care se vor prezenta in capitolele urmatoare :

-identificatori introdusi prin definitii de costante ;

identificatorii constantelor unui tip enumerare ;

-identificatori standard true si false ;

-cuvantul cheie nil.

In cadrul programului pot exista si date a caror valoare trebuie modificata.Aceasta categorei de date este modelata in program cu ajutorul variabilelor,care sunt primite ca entitati caracterizate la un moment dat printr-o anumita valoare.Este posibil insa ca variabila sa nu contina nici o valoare, caz in care se spune ca este nedefinita.

VARIABILA este o entitate careia i s-a asociat unui identificator si care poate lua valori corespunzatoareunui anumit tip.Asocierea identificator-tip se face printr-o declaratie de variabila,iar programatorul se va referi la valoarea curenta a variabilei prin numele ei.

Instructiunea care modifica valoarea unei variabile se numeste instructiune de atribuire.Deosebirea dintre definitii,declaratii si instructiuni se folosesc pentru deosebirea tipurilor si a obiectelor utilizate,specifica actiunilor ce trebuie indeplinite de catre calculator in momentul executiei programului.Daca exista mai multe definiri de constante ,ele trebuie separate cu ajutorul caracterului , iar integul grup va fi introdus prin folosirea cuvantului cheie const.

Valoarea asociata indicatorului nu se poate modifica prin actiunile , iar tipul sau este identic cu al valorii aflate in dreapta semnului'='.

Partea din program care contine declaratii de variabile incepe cu cuvantul cheie 'var' ,urmat de declaratii de variabile separate prin caracterul ' ;'.

Ca o regula generala a limbajului Pascal,putem mentiona faptul ca virgula se foloseste pentru a separa componentele unei liste in interiorul:

-definitiilor;

-declaratiilor;    in timp ce intre acestea apare caracterul punct si virgula

-instructiunilor;

2.Notiunea de tip.Tipul integer

a)Tipul Integer;

In PASCAL , tipul integer, permite reprezentarea, memorarea si prelucrarea numerelor intregi. Teoretic, acestea pot avea valori absolute, oricat de mari, dar reprezentarea datelor in cadrul calculatorului nu permite existenta seturilor de numere infinite.

Limbajul Pascal ,implementeaza aceasta restrictie furnizand in mod automat ,un identificator de constanta,Masant, a carui valoare reprezinta cel mai mare numar ce poate fi continut de o variabila de tip integer.

Operatiile aritmetice efectuate asupra valorilor de tip integer vor fi executate corect de catre calculator numai daca toti operanzii si toate rezultatele intermediare sunt cuprinse in intervalul "-Masant" pana la "+Masant".Numerele de tip integer sunt scrise la o secventa de cifre zecimale,precedate de semnul '-', pentru a indica un numar negativ, de nici un semn sau de semnul '+', pentru a indica un numar pozitiv.

Operatori aritmetici - ce se pot aplica asupra valorilor de tip integer :

-cu semnificatia de ' inmultire' ;

-(div) - cu semnificatia de 'impartire si trunchiere' ;

-(mod) -cu semnificatia de 'modulo' ;

- cu semnificatia de 'adunare' ;

- cu semnificatia de 'scadere' ;

Operatorul 'dire' realizeaza operatia de impartire a unui numar intreg prin alt numar intreg si indeparteaza partea fractionara a rezultatului,astfel incat operatia ne furnizeaza tot un numar intreg.

a)      '=' cu inteles de 'egal cu'

b)      '< >' cu inteles de 'diferit'

c)      '< ' cu inteles de 'mai mic decat'

d)      '<=' cu inteles de 'mai mic sau egal cu'

e)      ' >=' cu inteles de 'mai mare sau egal cu'

f) ' > ' cu inteles de ' mai mare decat'

O expresie este, fie o expresie simpla,fie o comparatie,dupa cum se arata si in diagramele de sinteza.

Aceasta reprezentare genereaza doua consecinte :

1)in Pascal ,operatorii de comparatie,au cel mai scazut nivel de prioritate in raport cu toti ceilalti operatori ;

2)comparatiile doble,cum ar fi x<=y<=z , nu sunt permise ca atare si trebuie implementate in alt mod.

Expresii logice care contin mai multe operatii

Operatorii cu ajutorul carora putem scrie astfel de expresii se numesc operatori logici si sunt cuvinte-cheie :

-ond cu inteles de 'si logic' ;

-or cu inteles de 'sau logic' ;

-not cu inteles de 'negare logica'.

Operatorul 'mod' ,asigura obtinerea ca rezultat a restului impartirii unui numar intreg prin alt numar intreg.Incercarea de a calcula restul in cazu l impartirii unui numar intreg la zero genereaza mesaj de eroare.

Functiile standard care lucreaza cu valori de tip integer si genereaza rezultate de acest tip sunt :

-abs(x) rezultatul reprezinta valoarea absoluta a lui x ;

-sqr(x) rezultatul reprezinta valoarea lui x la puterea a-II-a ;

Alte functii standard care genereaza rezultate de tip integer :

-trunc(x) rezultatul reprezinta partea intreaga a numarului real x,partea fractionara fiind indepartata ;

-round(x) rezultatul reprezinta valoarea numarului real x rotunjita pana la urmatorul intreg.

b)Tipul Boolean;

O are valoarea true (adevarat), daca ea este indeplinita, astfel , conditia are valoarea false(fals).

Tipul Boolean este format din multimea valorilor logice false si true.

Valorile unuei variabile booleane rezulta in urma unei operatii de comparatii.Valorile comparate pot fi de orice tip darn u este permisa compararea valorilor de tipuri diferite.

In Pascal exista o gama larga de operatori de comparative, dar deoarece unele dintre simbolurile matematiceconventionale nu figureaza in setul de caractere al celor mai multe dintre sistemele de calcul,se folosesc conventii de notatii.In Pascal se inched intre paranteze toate comparatiile folosite ca operanzi ai operatiilor logice:and, or, not.

In limbajul Pascal valorile de tip logic nu pot fi citite.In limbajul Pascal,exista relatii de ordonare pentru toate tipurile de variabile inclusive pentru tipul logic.Se considera ca false<true.

Prioritatea operatiilor logice este urmatoarea:

-a) not;

-b) and;

-c) or ;

Functiile standard care furnizeaza rezultate de tip logic sunt:

-add(x) rezultatul este true(adevarat), daca x este un intreg impar;astfel este false;

-eolu(h) rezultatul este true(adevarat),daca s-a ajuns la sfarsitul linii a fisierului;

-eof(f) rezultatul este true(adevarat),daca s-a ajuns la sfarsitul fisierului f.

Ultimele doua functii noi pot fi explicate mai detaliat intr-unul dintre capitolele urmatoare.

c)Tipul Real

Numarul de cifre zecimale ale unui numar real ce poate fi memorate in calculator este limitat.Exista o limita a marimii numerelor reale si o limita a preciziei de reprezentare a acestora.

In Pascal numerele reale pot fi exprimate fie cu ajutorul notatiei conventionale a fractiilor zecimale,fie cu afutorul notatiei stiintifice,care permite scrierea unor numere foarte mari sau foarte mici.

Operatorii ce pot fi folositi sunt urmatorii:

a)"+" -cu inteles de "adunare";

b)"-" - cu inteles de "scadere";

c)"*" - cu inteles de "inmultire";

d - cu inteles de "impartire de tip real".

Functiile standard care accepta un parametru de tip real si furnizeaza rezultatele de tip intreg:

-round(x) calculeaza valoarea lui x rotunjit la cel mai apropiat intreg;

-trunc(x) calculeaza valoarea lui x ,trunchita la partea intreaga.

Reguli ce se aplica in cazul tipului Pascal

a)Deoarece fiecare numar intreg are un numar real,expresiile de tip real contin operanzi de tip intreg;

b)Este permisa atribuirea de valori intregi variabilelor de tip real;

c)Operanzii de tip real, nu pot fi folositi in expresii de tip intreg.

d)Tipul CHAR(character)

Este cel mai obisnuit mod de comunicare.Cele mai uzate seturi de caractere sunt:

-ASCII (ISO) contine 128 caractere;

-EBCDIC contine 256 caractere (dublul setului ASCII).

Un caracter cuprins intre apostrofuri reprezinta o constanta de tip char.Penrtu a reprezenta caracterul apostrof, acesta se scrie de doua ori.

Conventia de a inchide caracterele intre apostrofuri se foloseste numai in cadrul textului unui progrtam Pascal ,fiind necesara pentru a se putea farce distinctia intre valoarea caracter si simbolurile folosite in program.EA nu se foloseste insa in timpul executiei programului la introducerea datelor de tip caracter.Diferitele seturi de caractere au diferite moduri de ordonare.

In cazul setului ASCII cifrelor zecimale apar inaintea literelor,in timp ce in cazul setului EBCDIC,ordinea este inversata. In cadrul acestei ordonari,fiecarui caracter ii corespunde un numar intreg, numit numar de ordine.

Functiile standard care permit vizualizarea se mai numesc si functii de transfer.

-ord ( e ) furnizeaza ca rezultat numarul de ordine al caracterului in cadrul setului de caractere.

- chr (i ) furnizeaza ca rezultat valoarea caracterului cu numar de ordine e;

Alte functii standard ce pot avea argumente de tip char:

-pred (e) functia predecesor ; furnizeaza ca rezultat caracterul ce preceda caracterul 'e' in setul dat;

-succ (e) functia successor; furnizeaza ca rezultat caracterul ce succeed caracterul 'e',in setul dat.

3.Structura generala a unui program PASCAL

Doua sectiuni principale ale unui program scris cu ajutorul limbajului Pascal este egala cu sectiunea declarativa si sectiunea de instructiuni.

Sectiune declarative Sectiunea instructiunilor

Program Ariecerc ; begin

Const    Readln(Raza);

P_c=3,141596;    Aria:=P_i *sar(Raza);

Var    Writeln(Aria);

Raza,aria:real;    end;

1)Sectiunea declarative- poate cuprinde maximum sase alte sectiuni ,grupate astfel:

a)antetul programului -precedat de cuvantul cheie 'program';

b)sectiunea de declarare a antetului - definite cu ajutorul cuvantului cheie 'label' grupeaza declaratiile de etichete folosite pentru controlarea stricta a salturilor neconditionate generate in program de instructiunile 'geto';

c)sectiunea de declarare a constantelor , definite cu ajutorul cuvantului cheie 'const';

d)sectiunea de declarare a tipurilor ,definite cu ajutorul cuvantului cheie 'type', grupeaza declaratiile de noi tipuri de variabile specifice utilizatorului;

e)sectiunea de declarare a variabilelor -definita cu ajutorul cuvantului cheie 'var',care grupeaza declaratiile de variabile;

f)sectiunea de declaratie de variabile si proceduri , care grupeaza toate declaratiile de functii si proceduri, precedate de cuvantul cheie 'function', respectiv 'procedure'.

Sectiunea instructiunilor este delimitate de cuvintele cheie'begin' si 'end', care cuprinde toate instructiunile.

Subprogramele unui program Pascal au ele insele aceeasi structura.

Declararea fiecarui program este precedat de cuvantul cheie corespunzator.

4)Structuri de control

Exista structuri de iesire-intrare

Prin procedura intelegem un program scris intr-o forma astfel incat sa poata fi apelat dintr-un alt program, acesta din urma furnizand proceduri, un set de parametri de intrare.

Instructiuni

1)Instructiunile de intrare sunt:

A) READ - preia datele de la dispozitivul de intrare si le introduce in memoria interna, iar cursorul ramane la sfarsitul ultimului caracter.

Are ca forma generala :

-read ([f],var 1 [var 2 ,., var n]);

in care s-au inclus intre paranteze drepte parametrii operationali ai procedurii.

Procedura READ - tasteaza fisierul de intrare ca pe o succesiune de campuri.Campurile sunt separate prin 'blancuri'.

Exista doua conditii pentru functionarea corecta a procedurii READ :

a)Numarul de campuri din fisierul de intrare trebuie sa depaseasca sau sa fie egal cu numarul variabilelor prezentate in apelul de procedura.;

b)Dincolo de cel de-al doilea camp din fisierul de intrare trebuie sa existe un terminator de linie.

B) READ-LN - dupa citirea datelor muta cursorul la inceputul urmatorului rand.Are forma generala de :

-readln [ (f,var 1,.,nar n)] ;

Procedura READ-LN -are doua diferente:

procedura read-ln priveste fisierul de intrare mai degraba ca o succesiune de linii;

a doua diferenta consta in faptul ca procedura 'read-ln' poate fi apelat 'fara parametrii' sub forma:

II)Instructiuni de iesire

A)WRITE- tipareste datele.Are ca forma :

Write([ f ] par 1[, par 2 ,.. , par n)] ;

B)WRITELN - extrage din memoria interna date de pe un dispozitiv de iesire.Dupa ce tipareste datele muta cursorul pe linia urmatoare.Are ca formula generala :

Writeln[(f,, par 1 ,par 2 ,, par n)] ;

III)Instructiuni de atribuire

Se calculeaza expresia din partea drteapta a instructiunii de atribuire si rezultatul ei este pus in variabile.Instructiunea este corect scrisa daca tipul variabilei coincide cu tipul expresiei.Instructiunile de atribuire fac parte din categoria de instructiuni numite simple.

IV)Intructiuni compuse

STRUCTURI DE CONTROL

Instructiunile limbajului Turbo Pascal transcriu aceste structuri de control,transformand programarea structurata intr-o activitate care decurge natural,firesc.

Instructiunile Turbo Pascal sunt urmatoarele:

• Instructiune de atribuire;
• Instructiune compusa;
• Instructiune IF;
• Instructiune CASE;
• Instructiune WHILE;
• Instructiune REPEAT;
• Instructiune FOR;
• Instructiune GOTO;
• Instructiune WITH;
• Instructiune procedurala(de apel procedura).

Instructiunea procedurala a fost exemplificata prin apelul

procedurilor : READ,READLN,WRITE,WRITELN.

Structura liniara cuprinde operatii care se executa secvential.

Aceasta structura este generata de instructiunile de atribuire,procedurale sau compuse.

Instructiunile de atribuire

Executia acestei instructiuni consta in :

se evalueaza expresia;

variabila primeste valoarea expresiei;daca tipul expresiei nu coincide cu cel al variabilei,valoarea expresiei se converteste inainte de atribuire in tipul identificatorului.

Instructiunea compusa -este formata dintr-o lista de instructiuni separate prin caracterul ' ;' si cuprinde intre ele cuvintele cheie ' begin si end',instructiuni care se executa una dupa alta , in ordinea aparitiei lor in lista.

Executia instructiunii compuse consta in executia instructiunilor cuprinse intre delimitatori BEGIN si END,in ordinea in care acestea apar.

Instructiunea compusa permite utilizarea mai multor instructiuni in instructiunile structurate a caror sintaxa impune prezenta unei singure instructiuni.

Sectiunea de program a blocului are forma instructiunii compuse.Orice program Pascal cuprinde cel putin o instructiune compusa.

Instructiunea compusa poate cuprinde alte instructiuni compuse incluse in ea,delimitate si ele de cuvintele cheie BEGIN si END,a caror grupare respecta regula parantezelor din matematica.

Caracterul ";" separa instructiunile,deci nu le termina si nu face parte din instructiuni.Din diagrama,se observa ca inainte de END un exista " ; " ,dar daca totusi se pune,nu se semnaleaza eroare,intrucat se considera ca s-a introdus o instructiune vida,care nu implica nici o actiune.

V)Instructiuni repetitive

a)WHILE

Instructiunea WHILE nu permite decat o instructiune.

Daca avem mai multe instructiuni le tratam ca pe o instructiune compusa (in BEGIN si END).

Succesiunea instructiunilor in cadrul instructiunii WHILE :

1)Tastarea conditiei precizate prin 'expresia'.

2)Revenire la pasul 1.

3)Executia instructiunii componente , stiind ca este indeplinita conditia.

4)Stiind ca nu este indeplinita conditia , se continua executia celorlalte instructiuni din program.

b)REPEAT

Are sintaxa : Repeat

i1;

i2;

.

.

.

in;

Until - conditie logica.

Daca instructiunea Repeat/ Until , implementata in limbajul Pascal , permite executia unei multimi de instructiuni pana la indeplinirea unei conditii.

Instructiunea Repeat - se mai numeste si 'ciclu cu text final'.Ea se incheie in momentul in care conditia devine adevarata sau trece la urmatoarea instructiune din program.

c)FOR

Are structura:

For x:=1 to n do instructiune.

Variabila de ciclare ;

Initial i , ia valoarea aflata in imediata apropiere a semnului de atribuire.Executa instructiunea dupa care i se incrementeaza i:=i+1 si executa instructiunea.

Procesul continua pana in momentul in care i devine egal cu n,-moment in care se executa instructiunea si iese din ciclu.

For- se aplica numai pentru numere intregi si primeste o singura

instructiune.Daca este necesar sa scriem mai multe instructiuni dupa 'do' , le transformam in instructiuni compuse.

VI)Instructiuni conditionale

O instructiune conditionala , realizeaza selectarea in vederea executiei a unei singure instructiuni dintre mai multe posibile.

Are ca instructiuni :

a)Instructiunea IF - ea selecteaza o instructiune dintre doua alternative posibile.

Succesiunea operatiilor este urmatoarea :

1)Tastarea conditiei ;

2)Daca valoarea conditiei este ' true' ,se executa instructiunea care apare dupa cuvantul cheie ' then' si apoi se continua;

3)Daca valoarea conditiei este ' false' , se executa instructiunea care apare dupa cuvantul cheie ' else', si apoi se continua ;

4)Se continua cu executia urmatoarelor instructiuni ale programului .

Are sintaxa :

If expresie then instructiune

else instructiune ;

end.

b)Instructiunea CASE

Aceasta instructiune realizeaza selectarea in vederea executiei unei singure instructiuni dintre mai multe posibile.

Are ca sintaxa:

CASE expresie of instructiune end,

Etichetare.

Expresia - se mai numeste si indexul instructiunii CASE , iar constantele ce pot sa apara se numesc etichete si reprezinta valorile posibile ale indexului.

Efectul instructiunii -CASE este urmatorul :

-se evalueaza indexul si apoi se executa, o singura conditie a corpului selectiei si anume instructiunea ce are ca eticheta valoarea indexului.

Etichetele instructiunii CASE , nu reprezinta etichete obisnuite ale programului si nu pot fi referite de catre o instructiune 'goto'.

Ele pot fi scrise intr-o ordine arbitrara , dar trebuie sa fie unice in cadrul instructiunii 'CASE'.

Daca valoarea indexului nu coincide cu nici o eticheta , se va selecta instructiunea vida.

5.Tipuri definite in program

Un tip - reprezinta o multime de valori carora li se poate atasa un nume.

Numarul elementelor acestei multimi se numeste 'cardinalitatea tipului'.

In limbajul PASCAL , programatorul are posibilitatea de a folosi tipurile standard sau de a defini el insusi tipul care reprezinta uneori structuri de date complexe.

Tipul - poate fi explicat direct la declararea unei variabile : var x :tip :

In cadrul programelor, toate definitiile de 'tip' se grupeaza sub cuvantul cheie 'type' si trebuie plasate dupa definirea constantelor si inaintea declaratiilor de variabile.

A)    Tipul SCALAR

I)Tipul enumerare

Multimea valorilor unui tip enumerare se defineste prin enumerarea identificatorilor ce reprezinta aceste valori.Prin definirea tipului se precizeaza atat identificatorul tipului , cat si identificatorii reprezentand valorile posibile.

Deoarece multimea valorilor unui tip enumerare este ordonata,intre elementele sale se pot aplica operatorii relationali : '=' ;'<>' ;'<' ;'<=' ;'>=' ;'>'.

Numarul de ordine al unui element este determinat de pozitia identificatorului in lista.Deasemenea, pot fi folosite functiile standard, 'succ' si 'ord' cu parametrii de tip enumerare.

Numarul de ordine corespunzator primului identificator enumerat este'0'

in continuare fiind valabila relatia :

ord(x) = ord(pred(x))+1;

In concluzie, utilizarea tipului enumerare confera programelor scrise in limbajul PASCAL , o mai mare claritate si asigura naturalete exprimarii.

II)Tipul subdomeniu

Constantele trebuie sa fie de acelasi tip si sa se afle in relatie:

-constanta 1< constanta 2 si are sintaxa :

Constanta

Nu se poate definii subdomenii ale tipului real.Operatorii si functiile standard corespunzatoare unui anumit tip scalar sunt valabile pentru orice subdomeniu al sau.

B)Tipuri STRUCTURATE DE DATE

Tipurile descise in paragrafele anterioare sunt tipurile simple.Pe baza acestora se pot construi tipuri structurate :

-tablou (array) ;

-inregistrare (record) ;

-multime (set) ;

-fisier (file).

Deosebirile intre acestea constau in :

-tipul componentelor ;

-metoda de structurare ;

-tehnica de selectare din ansamblu a elementelor componente.

Necesarul de memorie pentru reprezentarea unei structuri rezulta din tipul si numarul componentelor sale si ramane constant , motiv pentru care aceste structuri se numesc 'structuri statice'.

I)Tipul ARRAY(tablou)

Este o structura formata dintr-un numar fix de componente , toate de acelasi tip, numite elemente.

La defirea unui tablou se precizeaza :

-tipul elementar ;

-tipul permis pentru indici ;

Sintaxa tipului array

Tipul indicelui poate fi orice tip scalar cu tipul elementelor poate fi oricare dintre tipurile permise in limbajul Pascal. Elementele unei structuri tablou se mai numesc si variabile indexate deoarece pot fi selectate.

II)Tipul IMPACHETAT

In momentul definirii unei structuri se poate cere in mod explicit alocarea spatiului de memorie necesar reprezentarii tuturor valorilor posibile, caz in care calculul dimensiunii se face fara a tine seama de considerare privind optimizarea accesului la componente.

Un astfel de tip, se numeste impachetat si optiunea se indica prin cuvantul cheie 'pached', care il precede definitia.

In limbajul Pascal, un tablou impachetat se specifica prin folosirea cuvintelor cheie 'pached array'.

Impachetarea unui tablou poate reduce necesarul de memorie de la 1 pana la 32 de ori.

Variabilile de tip 'sir' sunt deseori folosite pentru memorarea si manevrarea cuvintelor si a textelor.

Manipularea excesiva a componentelor unui astfel de structuri duce la scaderea vitezei de executie a programului, motiv pentru care structurile impachetate se vor folosi mai des pentru stocarea informatiei.

Limbajul PASCAL permite :

-definirea de constante sir ;

-definirea de tip sir ;

-declararea de variabile sir ;

Sirul trebuie sa aiba exact aceeasi lungime ca si variabila si careia ii este atribuit.Limbajul PASCAL permite scrierea unui sir complet cu ajutorul procedurii 'WRITE ' , dar nu permite citirea unui sir complet cu instructiunea 'READ' , deoarece nu s-ar putea preciza numarul de caractere ce trebuie citite.De aceea, programatorul trebuie sa gandeasca si sa scrie in cadrul codului aceasta operatie intr-un mod asemanator.

Ordonarea alfabetica a cuvintelor este o operatie des intalnita in practica.

Reguli pentru siruri:

a)Compatibilitatea atribuirii - sirul trebuie sa aiba exact aceeasi lungime ca a variabilei sir careia ii este atribuit.

b)Comparatii - se poate compara numai siruri care au exact aceeasi lungime.

III)Tipul STRING(sir de caractere)

Limitarile si deficientele de manipulare ale acestora sunt estimate in versurile TURBO PASCAL , prin includerea ca tip predefinit a tipului

' string'.

Un tip string- este un tip special de vector, cu elemente de tip char, care memoreaza, in afara caracterelor din sir si lungimea respectivului sir de caractere, adica numar de caractere existente efectiv in sir.

O valoare de tip string, poate fi orice sir de caractere cu lungime cuprinsa intre zero si lungimea specifica in definitia tipului.

Sirul de lungime zero, denumit sir vid se reprezinta prin coanstanta.

Sintaxa tipului string este :

Daca in definirea tipului apare numai cuvantul cheie string, se presupune ca dimensiunea implicata este de 255.

Limitarea la 255 de caractere se datoreaza modului de reprezentare efectiva a valorilor de tip string.

Deoarece codul unui caracter este un intreg apartinand intervalului 0.255, apare ca evidenta necesitatea limitarii dimensiunii sirului la valoarea 255.

EXPRESIE

identificator

Elementele componente ale unei variabile de tip string pot fi accesate la fel ca si elementele unui tablou de caractere, care are sintaxa :

Este o notiune abstracta, caracterizata prin operatiile care se executa asupra ei, in timp ce tipul de date reprezinta aspectul, referiotor la implementare

Orice program prelucreaza date de intrare in scopul obtinerii unor rezultate (date de iesire). Datele prelucrate de program pot fi simple (de exemplu, numere intregi, numere reale, caractere) sau pot fi grupate in structuri.

Importanta unei bune organizari a datelor in structuri este sintetizata de celebra ecuatie a lui Niklaus Wirth :

STRUCTURI DE DATE + ALGORITM = PROGRAM

Pentru majoritatea aplicatiilor, o buna proiectare a structurilor de date influenteaza in mod esential sficienta programului. Aceleasi date pot necesita mai mult sau mai putin spatiu de memorie, in functie de structurile de date utilzate pentru memorarea lor. De asemeea, in functie de structurile de date alese, prelucrarea datelor poate fi mai simpla sau mai complicata, mai eficienta sau mai putin eficienta ( din punctul de vedere al numarului de operatii elementare necesare). Prin urmare, una dintre cele mai importante decizii necesare in implementarea unui algoritm este modul de organizare a datelor in structuri de date, deoarece influenteaza timpul de executie a programului, dimensiunea spatiului de memorie necesar, concizia si claritatea programului.

O structura de date nu este o entitate pasiva. Pentru a scrie o structura de date a bstracta trbuie sa definim operatiil permise de sturctura respectiva.

Structura de date si tipul de date oferit de limbajul de progrramare pentruimplementare stricturii respective nu reprezinta doua notiuni echivalente !

In functie de tipul datelor memeorate in cardul structurii, structurile de date se pot clasifica in:

v                 Strucutri de date omogene - toate datele componente sunt de acelasi tip.De exemplu, tabloul este o structura de date omogena.

v                 Strucuri de date neomogene - pot contine date de tipuri diferite. De exemplu, aritcolul nu este o structura de date omogena.

Alocarea memoriei pentru strucutrile de date se poate face in doua moduri :

I. STATIC : structura de date ocupa o zona de memorie de dimensiune fixa, alocata pe intreaga durata a executiei blocului in care este declarata.

II. DINAMIC : structura de date ocupa o zona de memorie de dimensiune variabila, alocata pe parcursul executiei programului la cererea explicita a programatorului.

Uneori se mai intalneste notiunea de structura de date semistatica, care ocupa o zona de memorie de dimensiune constanta, alocata pe toata durata executiei blocului in care apare declaratia structurii, dar elementele structurii ocupa pozitii variabile in cadrul structurii pe parcursul executiei programului.

De exemplu, stiva este o structura de date care poate fii alocata atat dinamic cat si static. In cazul alocarii statice, elementele stivei sunt memorate intr-un vector, dar elementele ocupa pozitii diferite invector pe parcursul executiei programului, deci stiva alocata static poate fi considerata structura de date semistatica.

In urma declararii, compilatorul Pascal rezerva automat pentru fiecare variabila statica o zona fixa in memoria interna RAM, alcatuita din locatii succesuve de memorie.Marimea acestei zone depinde de tipul variabilei: 2 octeti pentru integer , 6 pentru real , un octet pentru char etc.Acest mod de memorare a variabilelor statice se numeste alocare statica a memoriei.

Adresa de memorie a unei variabile statice este adresa primeia dintre locatiile de memorie rezervate variabilei.

DEFINITIE :

Structurile de date ale caror componente sunt variabile statice se numesc structuri de date alocate static.

Exemplu de structuri de date alocate static

1.Vectorul-atunci cand trebuie sa operam cu un sir, avem posibilitatea sa memoram toate elementelesale intr-o singura variabila indexata, in care elementele sunt asezate intr-o anumita ordine, ocupand pozitii consecutive, bine-determinate. O astfel de variabila se numeste tablou unidimensional sau vector.

Pozitia unui element se mai numeste si indice sau rangul elementului , iar elementele se mai numesc si componente ale vectorului.Pentru a referi un anumit element al sirului memorat in vector, trebuie sa scriem numele variabilei vector urmat de pozitia elementului cuprinsa intre paranteze patrate.

Un vector trebuie declarat, la fel ca orice variabila, in saectiunea de declaratii a programului. Variabila -vector in sine apartine unui tip de date nou, numit tipul array

Sintaxa :

[var]<nume> :array[<ind>] of <tip>;

In declaratia unui vector trebuie sa apara:identificatorul vectorului (<nume>), tipul de date din care fac parte pozitiile elementelor(<ind>) si tipul elementelor(<tip>).

Orice vector se caracterizeaza printr-un numar maxim de elemente, reprezentand cel mai mare numar de elemente care s-ar putea memora in vectorul respective(o valoare constanta).Din tipul de dateal pozitiilor elementelor va reiesi atat numarul maxim de elemente, cat si modul in care se numeroteaza pozitiile.

Exemplu:

Var v :array[[1..25] of integer;

Sedeclara un vector v cu maxim 25 de elemente numere intregi :pozitiile elementelor sunt valorile tipului subdomeniu(interval) 1..25,adica 1,2,,24,25,iar elementele v[1], v[2],.,v[25] sunt toate valori intregi.

Ca orice tip anonim , un tip de date array poate fi denumit, folosind cuvantul cheie type.

Exemplu:

Type vect=array[1..50] of integer;

Var v:vect;

- am denumit tipulde date array [1..50] of integer (adica tipul "vector de maxim 50 elemente numere intregi"),dandu-i numele vect.In continuare, declaram vectorul v ca pe o variabila de tipul vect.

In urma declarari unui vector, compilatorul rezerva pentru elementele sale o zona fixa de memorie, care sa poata memora numarul maxim de elemente (precizat la declarare).

Dar in general ,intr-un program in care am declarat un vector nu vom folosi toate elementele acestuia.In acest scop definim un asa numit numar real (efectiv) de elemente, reprezentand numarul elementelor care vor fi efectiv folosite la o anumita executie a programului.De obicei, numarul real de elemente precum si elementele vectorului se citesc de la tastatura in timpul executiei.

Elementele unui vectorse comporta ca niste variabile simple , desi pot fi citite , afisate si folosite in expresii si atributii.

In cele ce urmeaza , consideram vectorul v=(v[1], v[2], .,v[n]), de unde n este numarul real de elemente.

Prin parcurgerea vectorului se intelege "vizitarea" elementelor pe rand , si prelucrarea acestora. Pentru a parcurge primele n elemente ale vectorului v putem proiecta un ciclu, astfel :

- Contorul ciclului i va lua pe rand valorile 1,2,,n, reprezentand pozitiile elementelor in vector ;

- La fiecare pas, pentrufiecare valoare a lui i, ''vizitam''  si prelucram elementul v[i].

IMPLEMENTAREA ALGORITMULUI IN T.P. :

program lista;

const Nmax=50;

var st:array[1..Nmax]of integer;

i,n,opt:integer;

Procedure Antet;

begin

Writeln (' Proiect pentru atestat ');

Writeln;

Writeln (' Structuri de date de tip lista ');

Writeln;

Writeln (' Nume elev:Paraschiv Gabriel ');

Writeln;

Writeln (' Clasa:XII A ');

Writeln;

Writeln (' Prof.indrumator:Prof.Paraschiv Niculina ');

Writeln;

Writeln (' Sesiunea Mai-2005 ')

End;

Procedure tastare;

Begin

Writeln;

Writeln( 1-adaugarea unui element in varful stivei');

Writeln;

Writeln( 2-eliminarea elementului aflat in varful stivei');

Writeln;

Writeln( 3-afisarea stivei');

Writeln;

Writeln( 0-pentru terminare');

Writeln;

end;

begin

antet

tastare

n

repeat

writeln

writeln('optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]');

readln(opt);

case opt of

1:if n=Nmax then writeln('stiva este plina')

else

begin

n:=n+1; write('noul element :'); readln(st[n]);

end

2:if n=0 then writeln('stiva este vida, nu am ce elimina !')

else n:=n-1;

3:if n=0 then

writeln('stiva este vida!')

else

for i:=1 to n do write(st[i],' ')

else writeln('optiune incorecta!');

end

until opt=0;

end

REZULTATE OBTINUTE IN URMA RULARI PROGRAMULUI :

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

Proiect pentru atestat

Structuri de date de tip lista

Nume elev:Paraschiv Gabriel

Clasa:XII A

Prof.indrumator:Prof.Paraschiv Niculina

Sesiunea Mai-2005

1-adaugarea unui element in varful stivei

2-eliminarea elementului aflat in varful stivei

3-afisarea stivei

0-pentru terminare

optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]

noul element :2

optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]

noul element :3

optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]

noul element :5

optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]

optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]

optiunea dvs [1=adaugare, 2=eliminare, 3=afisare]

Bibliografie

Bazele informaticii clasa a X - a Editura : Didactica si Pedagogica - Bucuresti 1996 Autori : Ioan Tomescu

Manual informatica clasa a XI - a Editura Niculescu , varianta Pascal    Autori : George Daniel Mateescu , Pavel Florin Moraru

Informatica clasa a XI - a    Editura : LiceAll 2000    Autori : Anca Elena Voicu , Robert Aurelian Sova

Programarea in limbajele Pascal si Turbo Pascal

Editura : TEHNICA, BUCURESTI

Autor : BALANESCU TUDOR