Colegiul National "Aurel Vlaicu"
Lectie asistata pentru invatarea
listelor simplu-inlantuite
Lucrare pentru atestat in informatica
Elev:Martin Marius Profesori coordonatori :
Clasa: XII B Oprescu Daniela
Damacus Cristina
Sesiunea Mai 2008
Cuprins
Operatii cu liste simplu-inlantuite :
Creare
Parcurgere
Localizare element
Adaugare
Stergere
Domeniu:Programare-date eterogene
structurate
Referintele de continut: Informatica,
Matematica
Utilitate:Invatarea listelor
simplu-inlantuite
Etapele realizarii proiectului:
-documentare
-realizarea algoritmilor in pseudocod
-realizarea programului in C++
-structurarea si preazentarea in POWER POINT
Caracteristicile listei
Inregistrarile pe disc,cartile din biblioteca,elevii de la coada la bufet sau orasele vizitate prin firma de turism alcatuiesc colectii de informatii necesare in prelucrarile descrise.
Colectiile sunt omogene,informatiile definesc elemente de acelasi tip.
Intre elementele colectiei exista o ordine logica de succesiune.
In fiecare colectie,elementele se succed liniar, conform unei liste de informatii.
La crearea listei,ordinea logica coincide cu ordinea fizica de asezare a elementelor.
Fiecare element din lista are un element precedent si unul urmator,mai putin elementele capete.
Asupra listelor se fac operatii de parcugere si actualizare, respectandu-se ordinea logica a elementelor.
Operatiile in carte intra elementele colectiilor pot modifica relatia dintre ordinea fizica si ordinea logica a elementelor.
Creare
Prelucrarea initiala pentru o lista este definirea unei liste vide.Astfel,inainte de a se inregistra primul element in spatiul alocat listei,se vor face operatiile:
atribuirea valorilor de indici inexistenti pentru prim si ultim : prim=-1; ulitm=- 1;
completarea vectorului L cu valoarea 1 in toate cele n_max elemente;
inintializarea cu 0 a variabilelei n, numarul de elemente existente in lista;
struct persoana
elment grup[10];
int prim,ultim,n,L[10],curent,n_max=10;
prim=ultim=-1;n=0;
for(curent=0;curent<n_max;curent++)
L[curent]=1;
Parcurgere
Parcurgerea listei se poate face pentru mai multe scopuri.Cea mai frecventa operatie este afisarea listei.Variabila curent va trece pe rand prin lista incepand cu indicele prim.
curent=prim;
while(curent>=0)
Localizare element
Proprietatea dupa care se face cautarea poate fi legata de:
valoarea informatiei din acel element;
pozitia elemntului in lista.
Cautarea se incheie in momentul gasirii elementului,furnizand locul(indicele) lui in lista,sau in momentul terminarii listei,furnizand valoarea -1 ca adresa(loc) in lista pentru un element inexistent.
Dupa valoarea informatiei din acel element:
curent=prim;
while(curent!=-1 && strcmp(grup[curent],"Bianca")!=0)
curent=grup[curent].urm;
gasit=curent
Dupa pozitia elementului in lista:
curent=prim;
nr=0;
while(curent!=-1 && ++nr!=3)
curent =grup[curent].urm;
gasit=curent;
Adaugare
La inceputul listei:
if(ant==-1)
La sfarsitul listei:
if(gasit==-1)
In interiorul listei:
Stergere
Elementul care trebuie sters este localizat ca fiind primul:
ant==-1;
curent=prim;
L[curent]=1;
prim=grup[prim].urm;
Elementul care trebuie sters este localizat ca fiind utimul:
curent=ultim;
L[curent]=1;
grup[ant].urm=-1;
ultim=ant;
Elementul care trebuie sters este in interiorul listei:
L[curent]=1;
grup[ant].urm=grup[curent].urm;
|
