STRUCTURI DE DATE

ALOCATE STATIC ŞI DINAMIC

PrezentareScopul lucrării

CUPRINSUL LUCRARII

Cap. I: Structuri de date

Cap. II: Structuri de date alocate static

Cap. III: Alocarea dinamică a memoriei

Cap. IV : Consideraţii metodice privind predarea structurilor de date

Cap. V : Probleme propuse

back

I.1. Conceptul de structură de date. Clasificarea structurilor de date. I.2. Structuri statice.

I.2.1. Articolul I.2.2. Tabloul I.2.3 Mulţimea

I.3. Structuri semistatice I.3.1 Stiva. I.3.2 Coada. I.3.3 Tabela de dispersie.

I.4. Structuri dinamice. I.4.1 Lista liniară. I.4.2 Arborele. I.4.3. Reţeaua.

I.5. Structuri dinamice externe

CAPITOLUL I: STRUCTURI DE DATE

Cuprins

II.1.Structura memoriei la execuţia unui program. II.2.Variabile statice. Alocarea statică a memoriei. II.3.Reprezentarea secvenţială a listelor liniare.

II.3.1 Stiva. II.3.2 Coada. II.3.3 Liste oarecare.

II.4.Reprezentarea înlănţuită a listelor liniare. II.4.1 StivaII.4.2 CoadaII.4.3 Lista simplu înlănţuităII.4.4 Lista circularăII.4.5 Lista dublu înlănţuită

II.5.Comparaţie între alocarea secvenţială şi alocarea înlănţuită

CAPITOLUL II: STRUCTURI DE DATE ALOCATE STATIC

CuprinsPrezentare

III.1.Variabile dinamice. Tipul reper.III.2.Structuri dinamice de date.

III.2.1 Stiva.III.2.2 Coada.III.2.3 Lista simplu înlănţuită.III.2.4 Lista circulară.III.2.5 Lista dublu înlănţuită.

III.3. Comparaţie între alocarea statică şi alocarea dinamică.

CAPITOLUL III: ALOCAREA DINAMICĂ A MEMORIEI

Cuprins

IV.1. Consideraţii generaleIV.1.1. Principiile didacticeIV.1.2 Obiectivele majore ale studiului informaticii. Precizarea obiectivelor.IV.1.3. Metode generale de învăţareIV.1.4. Instrumente(mijloace de predare)IV.1.5. Metode de evaluare pentru atingerea obiectivelor

IV.2. Organizarea lecţiei de informaticăIV.2.1. Calitatea cunoştinţelor asimilateIV.2.2. Formarea limbajului de specialitateIV.2.3. Exprimarea fluentă în limbajul de specialitate. Exerciţiul oral.IV.2.4. Repetarea materiei parcurseIV.2.5. Evaluarea rezultatelor şcolare. Modele de teste şi fişe de evaluare.IV.2.6. Aprecierea cunoştinţelor elevului

IV.3. Planificarea şi pregătirea profesorului pentru lecţie.IV.3.1. Planificarea activităţii didacticeIV.3.2. Etapele esenţiale ale proiectării demersului didacticIV.3.3. Modele de proiecte de tehnologie didactică

CAPITOLUL IV: CONSIDERAŢII METODICE PRIVIND PREDAREA STRUCTURILOR DE DATE

DE TIP LISTĂ, STIVĂ, COADĂ

CuprinsPrezentare

Începând cu a doua jumătate a secolului al XX-lea, apariţia şi dezvoltarea calculatoarelor electronice au declanşat o nouă revoluţie în toate domeniile vieţii economice şi sociale. La baza acestei revoluţii stau cercetările fundamentale din domeniul matematicii şi realizările din domeniul microelectronicii.

Diversificarea spectaculoasă a mijloacelor tehnice din domeniul microelectronicii a dus la o dezvoltare continuă a software-ului, necesitând totodată adecvarea structurilor de date la aplicaţii din ce în ce mai complexe. Astfel au apărut structurile de date dinamice, pe lângă cele statice şi semistatice, care permit o alocare dinamică atât în cadrul structurii cât şi la nivelul întregii structuri. Lista liniară ca structură de date dinamică s-a dovedit a fi utilă într-o gamă foarte variată de aplicaţii, unde se pot obţine economie de timp şi memorie, o minimizare a numărului de operaţii, ajungându-se la algoritmi eficienţi şi, implicit, la programe fiabile, performante.

Foarte multe produse software care utilizează un volum mare de date folosesc structuri de date dinamice.

O primă problemă ce apare în prelucrarea structurilor de date este legată de reprezentarea în memoria internă şi pe suporturile externe. Lucrarea are drept scop prezentarea câtorva modalităţi de reprezentare, evidenţiindu-se avantajele fiecăreia în parte.

back

Tipurile de date de care avem nevoie în rezolvarea diferitelor probleme fie există ca atare în limbajul de programare ales, fie se pot declara cu ajutorul tipurilor de date elementare. În organizarea datelor, conform logicii algoritmului de rezolvare, datele de diferite tipuri se grupează în structuri, denumite structuri de date.

O structură de date poate ocupa în memorie o zonă de dimensiune constantă, în care elementele componente ocupă tot timpul execuţiei programului acelaşi loc. O astfel de structură se numeşte statică. Alocarea de memorie făcută pentru o structură statică este o alocare statică atât la nivelul întregii structuri, cât şi pentru fiecare componentă în parte.

Dacă o structură de date ocupă o zonă de dimensiune constantă, dar elementele componente ocupă un loc variabil în timpul execuţiei programului atunci o astfel de structură se numeşte semistatică. Pentru o structură semistatică alocarea este statică la nivelul structurii şi dinamică la nivelul componentelor,

Dacă o structură de date ocupă în memoria internă o zonă care se alocă în timpul execuţiei programului pe măsura nevoii de prelucrare, fără a avea o dimensiune constantă, atunci structura este dinamică. Pentru o structură dinamică alocarea este dinamică atât la nivelul componentelor cât şi la nivelul întregii structuri.

back

Toate variabilele declarate într-o secţiune var sunt alocate static şi se

numesc variabile statice. O variabilă statică este declarată într-o secţiune var a

unui bloc sub un anumit nume, prin intermediul căruia va fi referită în cadrul

acestuia, alocându-i-se memorie la activarea blocului. Variabila va exista(va

ocupa memoria alocată ei) atâta timp cât blocul în care a fost declarată este activ.

În urma declarării, compilatorul Pascal rezervă automat pentru fiecare

variabilă statică o zonă fixă în memoria internă RAM, alcătuită din locaţii

succesive de memorie. Mărimea acestei zone depinde de tipul variabilei: 2 octeţi

pentru integer , 6 pentru real, 1 octet pentru char etc.

Spaţiul de memorie aferent unor astfel de date se defineşte şi se rezervă

la dimensiune maximă, prestabilită, ca spaţiu propriu care nu poate fi

disponibilizat şi nici împărţit cu alte date, chiar dacă, în momentul diverselor

execuţii ale programului, nu este în întregime utilizat (rezervare statică sau la

momentul compilării).

Există două moduri de alocare a acestor structuri de date:

alocare secvenţială şi alocare înlănţuită back

Elementele listei vor fi stocate într-un tablou de înregistrări. Câmpurile unei înregistrări vor conţine în mod specific informaţiile pe care dorim să le reprezentăm în listă. Memorarea listei liniare în memoria calculatorului se va realiza prin memorarea elementelor listei în locaţii succesive de memorie, nod după nod. Se va folosi un tablou în care vor fi reţinute elementele listei, tabloul având dimensiunea max.const nmax=20;type element=record

câmp1:tip_info_1; câmp2:tip2_info_2; ………….. end;

lista=array[1..nmax] of element;var l:lista; PRIM,ULTIM:integer;Variabilele cu ajutorul cărora vom manipula elementele listei sunt :PRIM şi ULTIM care identifică primul, respective ultimul element al listei. back

În cazul reprezentării înlănţuite, elementele listei nu sunt aşezate

succesiv, fiind nevoie să precizăm în mod suplimentar ordinea lor reală.

Fiecare element al listei trebuie să indice unde se află elementul

următor(anterior). În acest caz va trebui să ştim unde se află primul

element al listei, pentru a avea acces apoi, pe baza înlănţuirilor, şi la

elementele următoare ale listei. De asemenea, este necesar să ştim când

nu mai există succesor(este vorba de ultimul element).

Implementarea alocării înlănţuite se realizează cu ajutorul vectorilor.

Lista va fi un vector care va conţine informaţia ataşată nodului(de

exemplu, un număr întreg) şi adresa nodului următor. Ultimul element

nu are nici un succesor; ca urmare, vom declara o constantă, numită

NUL, care va indica o intrare fictivă a tabloului. Pentru a nu face

confuzie între informaţia de adresă, care este tot de tip integer, şi restul

informaţiei memorate, vom „reboteza” tipul integer. next

Const nmax=100;

nul=0;

Type adresa=integer;

nod=record

inf:integer;

urm:adresa;

end;

Pentru memorarea listei folosim un vector care are componente de tip nod,

descris mai jos:

lista=array[1..nmax] of nod;

ocupat= array[1..nmax] of 0..1; - reţine 1 dacă componenta corespunzătoare

din L memorează un nod, sau 0 în caz contrar.

var L:lista;

Exemplu:

Vectorul L: ((7,3),( , ),(5,4),(1,5),(4,0),( , ))

Vectorul o:(1,0,1,1,1,0)

Lista este: 7, 5, 1, 4. back

back

•Alocarea înlănţuită necesită spaţiu suplimentar de memorie pentru gestionarea locaţiilor libere/ocupate.

•Extragerea unui nod dintr-o listă liniară alocată înlănţuit se realizează mult mai uşor decât extragerea unui nod dintr-o listă liniară alocată secvenţial. Pentru alocarea secvenţială o asemenea ştergere implică în general deplasarea unei părţi din listă în locaţii diferite. O concluzie similară se obţine în cazul inserării unui nod în cadrul unei liste liniare.

•Accesul la diferite părţi din listă este mult mai rapid în cazul alocării secvenţiale. Aşa cum am văzut, locaţia nodului k din listă în cazul alocării secvenţiale este o funcţie liniară de k, deci pentru a obţine accesul la acest nod se consumă un timp constant. În cazul alocării înlănţuite acest acces necesită k iteraţii urmărind referinţele a k-1 noduri. Astfel utilizarea memoriei înlănţuite este mai eficientă când parcurgerea listei se face secvenţial şi nu aleatoriu.

•Alocarea înlănţuită permite o mai mare flexibilitate în ceea ce priveşte reunirea a două sau mai multor liste într-o singură listă sau desfacerea unei liste în mai multe părţi.

Spre deosebire de variabilele statice, variabilele dinamice se alocă şi se distrug la cererea utilizatorului; ele nu sunt declarate într-o secţiune var, deci nu se pot identifica prin nume şi nici nu există pe toată durata activării blocului în care s-au creat. Din acest motiv, variabilele dinamice prezintă un mare avantaj comparativ cu cele statice, şi anume posibilitatea utilizării mult mai eficiente a memoriei.

Variabilele dinamice se alocă dinamic într-o zonă specială, numită HEAP care este eliberată la „distrugerea” variabilei dinamice. Neavând nume, variabilele dinamice trebuie referite prin intermediul altor variabile, numite din acest motiv variabile reper(sau variabile referinţă).

Zona HEAP cuprinde, de obicei, memoria liberă rămasă în momentul executării unui program. Dimensiunea zonei STACK şi/sau dimensiunea minimă şi maximă a zonei HEAP pot fi specificate prin comanda MEMORY SIZES din meniul OPTIONS sau prin directiva de compilare $M. Dimensiunea minimă implicită a zonei HEAP este 0, iar cea maximă 640 KB.

Variabilele reper sunt alocate static şi au ca valori adrese ale unor variabile dinamice de un anumit tip.

back

Liste. Noţiuni introductive

Lista simplu înlănţuităDefinireOperaţii specifice

Lista dublu înlănţuită

DefinireOperaţii specifice

O listă este o structură de date dinamică în care atâtadăugarea cât şi extragerea unui element se poate face depe orice poziţie.

Există mai multe tipuri de liste:

Definiţie :

•Liste simplu înlănţuite•Liste dublu înlănţuite•Liste circulare•Stive, cozi(cazuri particulare de liste)

next

Nodurile unei liste simplu înlănţuite prezintă două zone :informaţia

utilăadresă de legătură

Inf urmInf urm

Lista simplu înlănţuită este o structură de forma:

Pentru a gestiona lista se folosesc două variabile reper :

•prim care conţine adresa primului element din listă ;•ultim care conţine adresa ultimului element din listă;

type adresa=^ nod ;

nod= record

inf :tip_informaţie;

urm : adresă;

end;

Var prim ,ultim :adresă

Observaţie : Ultimul element al listei (cel aflat la adresa ultim) conţine ca informaţie de legătură valoarea constantei predefinite nil, cu semnificaţia că după acest element nu mai există în listă nici un alt element .

inf urm ......................

inf urm inf nil inf urm

primprim ultimultim

I.Crearea primului nod

II.Adăugare de noduri :

adăugare la sfârşitul listeiadăugare la începutul listeiadăugare după un nod precizat prin adresăadăugare în faţa unui nod precizat prin adresă

III.Ştergerea unui nod din listăştergerea primului nod din listăştergerea ultimului nod din listăştergerea unui nod precizat prin valoare sau adresă

IV.Parcurgerea listei

V.Căutarea unui nod în listă

Crearea primului nod

Adăugare de noduri : adăugare la sfârşitul listeiadăugare la începutul listei

adăugare după un nod precizat prin adresăadăugare în faţa unui nod precizat prin adresă

Ştergerea unui nod din listăştergerea primului nod din listăştergerea ultimului nod din listăştergerea unui nod precizat prin adresă

Parcurgerea listei

Căutarea unui nod în listă

prim

inf urm

Lista are un singur nod. Se folosesc doi pointeri care-i memorează adresa.

Observaţie :

Procedure creare_prim (var prim,ultim:adresa); begin new (prim) ; write (‘dati informatia :’) ; readln (prim ^.inf) ; prim ^.urm:=nil ; ultim:=prim; end;

inf nil2. se completează informaţia utilă din noul nod

write (‘dati informatia :’) ;

readln (prim^.inf) ;

1.se alocă spaţiu de memorie pentru noul nod

new (prim);

3. se completează zona de legătură cu nilprim^.urm:=nil;

se memorează adresa nodului prim în pointerul ultim

ultim:=prim

4.

ultim

se alocă spaţiu in heap pentru noul nod new(p); completarea informaţiei utile din nodul p write(‘dati valoarea: ‘); readln(p^.inf); se va completa zona de legătură a nodului p cu valoarea constantei nill p^.urm:=nil; se leagă nodul p la lista ultim^.urm:=p; se actualizează valoarea variabilei ultim cu adresa lui p ultim:=p;

inf urm

nilnilinf

inf urminf urm

infinf urm

inf urm

. . . . . . . . . . . . inf urm

prim

inf nil urm

ultim

1.

2.

3.

4.

5.

p

procedure adaugare_sfarsit(var ultim:adresa);var p:adresa;begin new(p); write(‘dati informatia:’); readln(p^.inf); p^. urm:=nil; ultim ^.urm:=p; ultim:=p;end;

se alocă spaţiu în heap pentru un nou nod notat p new(p);se completează informaţia utilă write(‘dati valoarea:’); read(p^.inf);se completează zona de legătură a nodului p cu adresa primului nod din lista p ^.urm :=prim;se reactualizează adresa primului nod din lista cu valoarea nodului p prim:=p ;

infinf

inf urminf urm

infinf urm

ultim

. . . . . . . . . . . .

inf urm

inf urm nil

inf urm

p

urminf

procedure adaugare_inceput(var prim:adresa); var p:adresa;begin new(p); write(‘dati informatia:’); readln(p^. inf); p ^.urm:=prim; prim:=p;end;

prim

1.

2.

3.

4.

inf urm . . . . . . . . . . . . inf urm urm inf

p

q

p^.urminf urm

se alocă spaţiu în heap pentru noul nod new(q);

se leagă noul nod la listă q^.urm:=p^.urm; p^.urm:=q;

se completează zona inf pentru noul nod writeln(‘dati informatia:’); readln(q^.inf);

. . . . .. . . . .

urminf

q^.urm

procedure adauga_dupa(p:adresa);var q:adresa;begin new(q); writeln(‘dati informatia:’); readln(q^.inf); q^.urm:=p^.urm; p^.urm:=q;end;

inf urminf urminf urm

1.

3.

2.

inf urm . . . . . . . . . . . . inf urm urm

inf

p

q

p^.urminf urm

. . . . .. . . . .

urm

q^.urm

se alocă spaţiu pentru noul nod q new(q );se copie informaţia din nodul p în nodul q q^.inf:=p^.inf;se citeşte noua informaţie în p write(‘dati informatia: ’); readln(p^.inf);se leagă nodul q la listă q^.urm:=p^.urm;se leagă nodul p de nodul q p^.urm:=q;

procedure adauga_in_fata(p:adresa); var q:adresa; begin new(q); q^.inf:=p^.inf; write(‘dati informatia:’); readln(p^.inf); q^.urm:=p^.urm; p^.urm:=q;end;

inf urminf urminf urm

1.

2.

3.

4.

5.

infinf

se parcurge lista pentru a afla adresa penultimului nod, adresă pe care o vom memora în pointerul q q:= prim; while q^.urm<>ultim do q:=q^.urm; penultimul nod va deveni ultimul după ştergere, deci legătura sa următoare devine nil q^.urm:=nil; se şterge fizic ultimul nod dispose(ultim); se reactualizează valoarea pointerului ultim ultim:=q;

Procedure sterge_ultim(var ultim:adresa);var q:adresa;begin q:=prim; while q^.urm<>ultim do q:=q^.urm; q^.urm:=nil; dispose(ultim); ultim:=q;end;

inf

inf urm

inf nil

ultim

inf urm

1.

2.

3.

4.

inf urm

prim

inf urm

q

.................

q q

inf urm

inf urm

q q

urmnil

ultim

se memorează adresa celui de-al doilea noddin listă în pointerul p, operatie necesară întrucât după ştergere al doilea nod va deveni primul p:=prim^.urm;se şterge fizic primul nod dispose(prim);se reactualizează valoarea pointerului prim prim:=p;

Procedure sterge_prim(var prim:adresa);var p:adresa;begin p:=prim^.urm; dispose(prim); prim:=p;end;

inf urm

p

inf urm .............

inf urminf urm

inf urm

prim

inf urm

1.

2.

3.

prim

inf urm

inf urm

p

inf urm

prim

inf urm

q

......... .........

se parcurge lista pentru a afla adresa nodului aflat înaintea cheii de adresă p; adresa ovom memora în pointerul q q:= prim; while q^.urm<>p do q:=q^.urm;adresa memorată în zona urm a nodului p va fi reţinută în zona urm a nodului q q^.urm:=p^.urmse şterge fizic nodul p dispose(p);

Procedure sterge_dupa(p:adresa);var q:adresa;begin q:=prim; while q^.urm<>p do q:=q^.urm q^.urm:=p^.urm; dispose(p);end;

inf urminf urm

1.

2.

3.

qp^.urm

inf nil

inf urm

inf urm

prim

inf urm

p

inf nil

ultim

............... inf urm

Parcurgem nodurile liste cu ajutorul unui pointer p care, plecând de la primul nod va referi pe rând fiecare nod al listei : prelucrăm informaţia din nodul p, mutăm p la următorul nod şi prelucrarea continuă.

Cât timp pointerul p nu a ajuns la sfârşitul listei {p<>nil}: - prelucrăm informaţia din nodul p (p^.inf) - mutăm pointerul p la nodul următor {p:=p^.urm}

Procedure parcurgere(prim:adresa);var p:adresa;begin p:=prim; while p<>nil do begin {prelucrarea informatiei din nodul p} p:=p^.urm; end;end;

inf urminf urminf urminf urm

Funcţia returnează : - nil, dacă valoarea x nu a fost găsită în listă; - adresa nodului ce are completată zona inf cu valoarea memorată în variabila x;

Cât timp pointerul p nu a ajuns la sfârşitul listei {p<>nil} şi informaţia memorată în zona inf a nodului curent este diferită de x : - mutăm pointerul p la nodul următor

Function cauta(prim:adresa;x:byte):adresa;var p:adresabegin p:=prim; while (p^.inf<>x) and (p<>nil) do p:=p^.urm; cauta:=p;end;

prim

ultim

se alocă spaţiu pentru nodul prim new(prim);completarea zonei inf pentru noul nod write(‘dati informatia:’); readln(prim^.inf);se va completa zona de legătură urm cu constanta nil prim^.urm:=nil;se va completa zona de legătură ant cu valoarea constantei nil prin^.ant:=nil;pointerul ultim memoreaza adresa nodului prim ultim:=prim

Procedure creare_prim(var prim,ultim:adresa);begin new(prim); write(‘dati informatia:’); readln(prim^.inf); prim^.urm:=nil; prim^.ant:=nil; ultim:=prim; end;

1.

2.

3.

4.

inf nilnil

5.

se alocă spaţiu pentru noul nod p new(p);se completează zona inf cu informaţia utilă write(‘dati informatia’); readln(p^.inf);completarea zonei urm cu constanta nil p^.urm:=nil;completarea zonei de legătură ant a nodului p cu adresa ultimului nod din listă p^.ant:=ultim;se leagă nodul p de nodul ultim ultim^.urm:=p;se actualizează valoarea variabilei ultim cu adresa lui p ultim:=p;

ant inf ..............

ant inf nil

ultim

Procedure adaugare_sfarsit(var ultim:adresa);var p:adresa;begin new(p); write(‘dati informatia:’); readln(p^.inf); p^.urm:=nil; p^.ant:=ultim; ultim^.urm:=p; ultim:=p;end;

p

1.

2.

3.

4.

5.

6.

ultim

urmnil

ant inf urm ant inf urm

inf urm ..............nil inf urm

alocarea spaţiului în heap pentru noul nod notat p new(p); completarea zonei inf cu informaţia utilă write(‘Dati informatia:’); readln(p^.inf); completarea zonei de legătură ant a nodului p cu constanta nil p^.ant:=nil; se leagă nodul p de nodul prim prim^.ant:=p; p^.urm:=prim; se actualizează adresa primului nod din listă cu valoarea nodului p prim:=p;

Procedure adauga_in_fata(var prim:adresa);var p:adresa;begin new(p); write(‘dati informatia:’); readln(p^.inf); p^.ant:=nil; prim^.ant:=p; p^.urm:=prim; prim:=p;end;

p prim

1.

2.

3.

5.

4.

nilant

ant inf urm ant inf urm

ant inf urm

p^.urm

ant inf urmant inf urm ant inf urm

q^.urm

ant urm

q

se alocă spaţiu pentru noul nod q new(q );se copie informaţia din nodul p în nodul q q^.inf:=p^.inf;se citeşte noua informaţie în p write(‘dati informatia: ’); readln(p^.inf);se leagă nodul q la listă q^.urm:=p^.urm; p^.urm^.ant:=q; p^.urm:=q; q^.ant:=p;

Procedure adauga_in_fata(var p:adresa);var q:adresa;begin new(q); q^.inf:=p^.inf; write(‘dati informatia:’); readln(p^.inf); q^.urm:=p^.urm; q^.urm^.ant:=q; p^.urm:=q; p^.ant:=p;end;

1.

2.

3.

4.

inf

p

... ...

ant inf urm

ant inf urm

ant inf urmant inf urm

se alocă spaţiu pentru noul nod q new(q );se citeşte noua informaţie în q write(‘dati informatia: ’); readln(q^.inf);se leagă nodul q la listă q^.urm:=p^.urm; p^.urm^.ant:=q; p^.urm:=q; q^.ant:=p;

... ...

1.

2.

3.

Procedure adauga_după(var p:adresa);var q:adresa;begin new(q); write(‘dati informatia:’); readln(q^.inf); q^.urm:=p^.urm; q^.urm^.ant:=q; p^.urm:=q; p^.ant:=p;end;

q

p^.urmq^.urmp

nil inf urm

prim p

inf urm ..............

memorăm adresa celui de-al doilea nod din listă în pointerul p,operaţie necesară întrucât după ştergere al doilea nod va deveni primul p:=prim^.urm;se completează zona de legătură ant a pointerului p cu valoarea constantei nil p^.ant:=nil;se şterge fizic primul nod dispose(prim);se reactualizează valoarea pointerului prim prim:=p;

Procedure sterge_primul(var prim:adresa);var p:adresa;begin p:=prim^.urm; p^.ant:=nil; dispose(prim); prim:=p;end;

1.

2.

3.

4.

antnil

prim

Procedure sterge_nod(p:adresa);begin p^.ant^.urm:=p^.urm; p^.urm^.ant:=p^.ant; dispose(p);end;

deoarece nodul p se şterge din listă este necesară crearea unor noi legături între: nodul din faţa nodului p şi nodul de după nodul p p^.ant^.urm:=p^.urm; p^.urm^.ant:=p^.ant;se şterge fizic nodul p dispose(p);

..............p

ant inf urmant inf urm

p^.ant p^.urm

ant inf urm....

1.

2.

p^.ant^.urm

Procedure parcurgere(prim:adresa);var p:adresa;begin p:=prim; writeln; write(‘rezultatul este:’); while p<>nil do begin {prelucrarea informatiei din nodul p } p:=p^.urm; end; writeln;end;

Parcurgem nodurile liste cu ajutorul unui pointer p care, plecând de la primul nod va referi pe rând fiecare nod al listei : prelucrăm informaţia din nodul p,mutăm p la următorul nod şi prelucrarea continuă.

Cât timp pointerul p nu a ajuns la sfârşitul listei {p<>nil}: - prelucrăm informaţia din nodul p (p^.inf) - mutăm pointerul p la nodul următor {p:=p^.urm}

Funcţia returnează : - nil, dacă valoarea x nu a fost găsită în listă; - adresa nodului a cărui zonă inf este completată cu valoarea memorată în variabila x;

Cât timp pointerul p nu a ajuns la sfârşitul listei {p<>nil} şi informaţia memorată în zona inf a nodului curent este diferită de x : - mutăm pointerul p la nodul următor

Function cauta(prim:adresa;x:byte):adresa;var p:adresa;begin p:=prim; while( p<>nil) and (p^.inf<>x) do p:=p^.urm; cauta:=p;end;

ant inf nil

ultim

se memorează adresa penultimului nod din listă în nodul p p:=ultim^.ant;se completează zona urm a nodului p cu valoarea constantei nil deoarece nodul p va deveni ultimul nod din listă p^.urm:=nil;se şterge fizic ultimul nod din listă dispose(ultim);se reactualizează valoarea pointerului ultim ultim:=p;

..............

ultim^.ant

ant inf urmurminfant

1.

2.

3.

4.

p

nil

ultim

Procedure sterge_ultim(var ultim:adresa);var p:adresa;begin p:=ultim^.ant; p^.urm:=nil; dispose(ultim); ultim:=p;end

Nodurile unei liste dublu înlănţuite prezintă trei zone :

type adresa=^ nod ;

nod= record

inf :tip_informatie;

urm,ant : adresa;

end;

Var prim ,ultim :adresă

Pentru a gestiona lista se folosesc două variabile reper :

•prim care conţine adresa primului element din listă ;•ultim care conţine adresa ultimului element din listă;

Adresa de legătură cu nodul următor

Informaţiautilă

Adresa de legătură cu nodul anterior

ant inf urm

Observaţie : Ultimul element al listei (cel aflat la adresa ultim) conţine ca informaţie de legăturăcu nodul următor valoarea constantei predefinite nil, cu semnificaţia că după acest element nu mai există în listă nici un alt element .Primul element al listei (cel aflat la adresa prim) conţine ca informaţie de legătură cu nodul anterior valoarea constantei nil, cu semnificaţia că înaintea acestui nod nu mai există nici un alt element.

nil inf urm

prim

inf urm.....…ant ant inf nil

ultim

Lista dublu înlănţuită este o structură de forma

Planificare calendaristica

Unitate de invatare

Proiect de

tehnologie didactica

Şcoala………………………... Profesor……………………………Disciplina……………………. Clasa/nr. ore pe săpt./anul………

Planificare calendaristică

Unităţi deînvăţare

Obiective de referinţă/Competenţe specifice

Conţinuturi Numărorealocate

Săptămâna Obs.

•Unităţile de învăţare se indică prin titlurile temelor stabilite de către profesor.•În rubrica Obiective de referinţă/Competenţe specifice se trec numerele obiectivelor de referinţă/competenţelor specifice din programa şcolară.•Conţinuturile selectate sunt cele extrase din lista de conţinuturi a programei.•Numărul de ore alocate se stabileşte de către profesor în funcţie de experienţa acestuia şi de nivelul clasei.Întregul cuprins al planificării are valoare orientativă, eventualele modificări determinate de aplicarea efectivă la clasă putând fi consemnate în rubrica Observaţii.

În rubrica referitoare la Conţinuturi apar inclusiv detalieri de conţinut necesare în explicitarea anumitor parcursuri, respectiv în cuplarea lor la baza proprie de cunoaştere a elevilor.În rubrica Obiective de referinţă/Competenţe specifice se trec numerele obiectivelor de referinţă/competenţelor specifice din programa şcolară.Activităţile de învăţare pot fi cele din programa şcolară, completate, modificate sau chiar înlocuite de altele, pe care profesorul le consideră adecvate pentru atingerea obiectivelor propuse. Activităţile de învăţare se construiesc prin corelarea obiectivelor de referinţă la conţinuturi şi presupun orientarea către un anumit scop, redat prin tema activităţii. În momentul propunerii lor spre rezolvare elevilor, activităţile de învăţare vor fi transpuse într-o anumită formă de comunicare inteligibilă nivelului de vârstă. Rubrica Resurse cuprinde specificări de timp, de loc, forme de organizare a clasei, material didactic folosit etc.În rubrica Evaluare se menţionează instrumentele sau modalităţile de evaluare aplicate la clasă.

Şcoala………………………... Clasa/nr. ore pe săpt...…………………Disciplina……………………. Săptămâna/anul…………………………

Proiectul unităţii de învăţareUnitatea de învăţare……………………Nr. ore alocate…………………………

Conţinuturi Obiective de referinţă/Competenţe specifice

Activităţi de învăţare

Resurse Evaluare

Data: Obiectul: InformaticăClasa: a XI-a - profil matematică-informatică Tema: Liste simplu înlănţuite.Tipul lecţiei: Lecţie de fixare şi sistematizare.Durata lecţiei: 50 minute Obiectivul funadamental: Recapitularea şi fixarea cunoştinţelor privind modul de declarare şi de

utilzare a listelor simplu înlănţuite alocate static.Competenţe specifice: C1.Elevii vor şti să definească structura de date de tip listăC2. Elevii vor şti cum se implementează o listă simplu înlănţuită;C3. Elevii vor şti care sunt operaţiile elementare ce se pot efectua la

nivelul unei liste simplu înlănţuite;C4. Elevii vor cunoaşte modul de selectare a unui element, precum şi cum

se realizează crearea, respectiv afişarea informaţiilor dintr-o listă simplu înlănţuită;

C5. Elevii vor fi capabili să rezolve probleme ce necesită folosirea listelor simplu înlănţuite;

PROIECT DE TEHNOLOGIE DIDACTICĂ

Metode şi procedee didactice:

Explicaţia, conversaţia, exerciţiul, demonstraţia.

Mijloace de învăţământ:

Calculatorul, manualul;

Mediul de instruire:

Laboratorul de informatică;

Forme de organizare:

Activitate frontală

Resurse:

- pedagogice:cursuri de informatică, metodica predării informaticii

- oficiale: programa şcolară

- temporale: 50 minute

- psihologice: cunoştinţele dobândite de către elevi la disciplina

informatică

SUCCESIUNEA ŞI DESFĂŞURAREA MOMENTELOR LECŢIEI I.Moment organizatoric:•obiective urmărite: crearea unei atmosfere specifice bunei desfăşurări a

activităţii didactice;•activitatea profesorului: verificarea prezenţei, asigurarea că elevii sunt

pregătiţi pentru începerea lecţiei;•activitatea elevului: pregătirea caietului;•metode şi procedee didactice: metoda conversaţiei, explicaţia;

II. Captarea atenţiei şi trezirea interesului pentru lecţie•activitatea profesorului: se va preciza elevilor că urmează a fi recapitulată

structura de tip listă simplu înlănţuită şi vor fi rezolvate probleme ce necesită

folosirea acestei structuri de date . •activitatea elevului: ascultă şi notează cele prezentate sau notate pe tablă de

către profesor şi pune întrebări cu care să poată lămuri contextul în care se va

desfăşura lecţia;•metode şi procedee didactice: metoda conversaţiei, metoda problematizării,

modelarea;

III.Anunţarea lecţieiSe poartă un dialog pe tema: “Lista simplu înlănţuită”.activitatea profesorului: sunt adresate clasei următoarele întrebări:Care este definiţia unei liste simplu înlănţuite?Ce alte structuri de date cunoaşteţi?Cum se implementează structura de date de tip listă simplu înlănţuită?Care sunt principalele operaţii ce se pot efectua la nivelul unei liste simplu înlănţuite? după care se va propune elevilor spre rezolvare următoarea problemă:Fiind dată o matrice rară (spunem că o matrice este rară dacă cel puţin două treimi din elementele mulţimii sunt nule) să se alcătuiască o listă înlănţuită în care elementele au forma (linia, coloana, valoarea) şi valoarea ≠0.să se listeze elementele aflate pe diagonala principală;să se determine elementul minim de pe diagonala principală;să elimine elementul de valoare maximă;determinaţi suma şi produsul a două astfel de matrici;Datele de intrare se citesc din fişierul text date.txt.activitatea elevului: răspunde la întrebările adresate şi este atent la completările aduse de către profesor după care trece la rezolvarea problemei propuse;metode şi procedee didactice: metoda conversaţiei, a demonstraţiei, a problematizării şi a modelării;

IV.Asigurarea conexiunii inverse-activitatea profesorului: profesorul propune precizarea conţinutului listei pentru matricea:-activitatea elevului: elevii rezolvă pe caiete noile cerinţe.

0000900

0010000

0002100

V. Evaluarea cunoştinţelor dobândite-activitatea profesorului: profesorul verifică corectitudinea soluţiilor scrise de elevi. Elevii care nu au înţeles modul de memorare a matricei cu ajutorul listelor, sunt solicitaţi să iasă la tablă, fiind urmăriţi şi ajutaţi de colegii lor din bancă(care au rezolvat corect)-activitatea elevului: elevii reţin şi notează observaţiile făcute-metode şi procedee: metoda conversaţiei, verificarea frontală

VI. Prezentarea temei pentru acasă-activitatea profesorului:li se propun elevilor spre rezolvare următoarele probleme:Considerând polinoamele cu coeficienţi reali(nenuli), ca fiind reprezentate sub forma unor liste înlănţuite în care un element reprezintă un monom caracterizat prin rangul şi valoarea coeficientului să se determine valoarea unui astfel de polinom într-un punct dat X. Polinomul se va citi din fişierul date.txt iar valoarea lui x se va introduce de la tastatură.Exemplu: Pentru fişierul:5 0 6 4 –8 12polinomul corespunzător este:p=5+6*x4-8*x12 Să se determine suma a două astfel de polinoame.Într-o listă simplu înlănţuită se memorează n persoane. Să se verifice dacă, pentru o persoană dată p, există în listă o persoană cu acelaşi nume ca şi p. Dacă nu, să se insereze în poziţia k în listă noua persoană p. Discuţie după valoarea lui k. -activitatea elevului: notează tema în caiet precum şi indicaţiile date de profesor-metode şi procedee folosite: metoda conversaţiei