Multe din informatiile prelucrate de calculator sunt organizate ca liste: lista candidatilor la admitere intr-o facultate, lista materialelor necesare dintr-o sectie industriala, lista locatarilor unui imobil etc. De aceea lista ocupa un loc important intre structurile uzuale. In cele ce urmeaza, sunt prezentate cateva elemente de baza referitoare la liste, modalitatile de reprezentare a listelor in calculator si unele aplicatii semnificative.
DEFINITII
O lista liniara este o structura de date omogena, secventiala formata din elemente ale listei.
Un element din lista contine o informatie specifica si, eventual, o informatie de legatura.
De exemplu, in lista candidatilor inscrisi la concursul de admitere, un element poate contine urmatoarele informatii specifice: nume, numar de legitimatie, indicativul sectiei la care candideaza, notele obtinute si media lor.
Fiecare din aceste informatii poate reprezenta o cheie ce poate fi folosita pentru inspectii si comparatii. De exemplu, luand drept cheie media, se poate face clasificarea candidatilor si stabilirea celor admisi si a celor respinsi.
Pozitia elementelor din lista (primul element, al doilea sau al n-lea) defineste ordinea elementelor.
Continutul listei se poate modifica prin:
– Adaudarea de noi elemente la sfarsitul listei (inscrierea de candidati poate fi consemnata cronologic, caz in care fiecare nou inscris este adaugat la sfarsitul listei);
– Inserarea de noi elemente in orice loc din lista (daca lista este pastrata in ordine alfabetica, inscrierea unui nou candidat duce la reorganizarea completa a listei);
– Stergerea de elemente din orice pozitie a listei (pot sa existe candidati care renunta);
– Modificarea unui element dintr-o pozitie data (este posibila corectarea informatiilor introduse gresit).
Se include printre operatiile care modifica structura listei si initializarea unei liste ca o lista vida, adica o lista fara elemente (la inceputul inscrierilor lista candidatilor este o lista vida; tot o lista vida se poate obtine dintr-o lista prin stergeri repetate).
Alte operatii sunt cele de caracterizare. Acestea nu modifica structura listelor, ci furnizeaza informatii despre ele.
Dintre operatiile de caracterizare vom considera in continuare:
– Determinarea lungimii listei (numarul de elemente);
– Localizarea elementului din lista care indeplineste o anumita conditie (de exemplu: gasirea primului candidat din lista care a obtinut media 10).
Pot fi imaginate si operatii mai complexe, ca de exemplu:
– Separarea unei liste in doua sau mai multe subliste (din lista tuturor candidatilor inscrisi se creeaza doua subliste, cu cei inscrisi la doua sectii diferite);
– Combinarea a doua sau a mai multor liste intr-una singura; aceasta poate fi o simpla concatenare (alipire) sau o interclasare (de exemplu: o rearanjare conform criteriului alfabetic);
– Crearea unei liste ordonate dupa valorile (crescatoare sau descrescatoare) ale unei chei (astfel sortarea dupa cheia nume dispune elementele listei in ordine alfabetica; lista poate fi reorganizata si dupa o alta cheie, de exemplu, media obtinuta la concursul de admitere);
– Selectia elementelor dintr-o lista, care satisfac unul sau mai multe criterii, intr-o noua lista.
Elementele listelor sunt in general inregistrari avand structura specifica aplicatiilor considerate.
In memorie, listele pot fi reprezentate prin structuri statice (tablouri) sau prin structuri dinamice (liste inlantuite). Acest aspect poate fi transparent prin utilizator, daca se definesc, sub forma unor subprograme (operatii de acces cunoscute prin nume, parametri si efectul realizat de ele) si daca toate prelucrarile listelor se fac prin intermediul lor. Astfel, modul in care au fost concepute aceste operatii si modul de reprezentare a listelor poate fi “ascuns” utilizatorului.
Setul de operatii primitive, considerat in cele ce urmeaza, utilizeaza pozitia curenta in lista, definita ca pozitia elementului accesibil la un moment dat. Operatiile de prelucrare se refera la elementul din pozitia curenta. In afara acestora, sunt definite operatii care asigura modificarea pozitiei curente.
Au fost considerate urmatoarele primitive:
1) Operatii de modificare a pozitiei curente:
PozitionareInceput – pozitionare pe primul element din lista
PozitionareSfarsit – pozitionare pe ultimul element din lista
Urmator – pozitionare pe succesorul elementului
curent
Precedent – pozitionare pe predecesorul elementului
curent
2) Operatii de modificare a continutului listei:
AdaugaLaSfarsit – adaugarea unui element la sfarsitul listei
InsereazaElement – inserare inaintea elementului curent
ModificaInformatie – modificarea cheii elementului curent
StergeElement – stergerea elementului curent din lista
3) InitializareLista – initializarea unei liste ca o lista vida
4) AdresaInformatie – copierea adresei informatiilor din elementul curent
5) Operatii de caracterizare:
TestListaVida – testarea unei liste daca este vida
TestInceput – testul pozitionarii pe primul element
TestSfarsit – testul pozitionarii dupa ultimul element
LungimeLista – determinarea lungimii listei.
REPREZENTAREA LISTELOR IN MEMORIE
Spatiul de memorie ocupat de lista poate fi alocat static (printr-un tablou) sau dinamic (folosind pointeri).
In primul caz, elementele vecine din lista ocupa pozitii alaturate in memorie.
Accesul la un element din lista, parcurgerea listei sau adaugarea unui element la sfarsitul listei se fac cu usurinta, in timp ce inserarea si stergerea de elemente din mijlocul listei sunt operatii costisitoare, deoarece presupun deplasarea unor elemente.
O lista alocata static este definita printr-un tablou de elemente reprezentand pointeri la informatia utila si prin pozitiile elementului curent si a ultimului element.
In cazul alocarii dinamice a memoriei, elementele listei pot sa nu fie vecine, ci dispersate in intreaga memorie disponibila.
Legarea intre ele a elementelor aceleiasi liste se face prin pointeri, care se adauga informatiei utile din elemente.
Structura LISTA este reprezentata prin lungimea ei si prin trei pointeri: la inceputul listei, la sfarsitul listei si la elementul curent din lista.
Pentru ca operatiile de inserare si stergere sa se faca la fel pentru orice element din lista, s-au folosit doua elemente false (intalnite si sub numele de elemente santinele), plasate la inceputul si la sfarsitul listei (inaintea primului, respectiv dupa ultimul element din lista). In acest fel toate elementele utile din lista au atat predecesor cat si succesor.
Un element din lista poate contine o singura legatura – la elementul urmator (lista simplu inlantuita) sau doua legaturi- la elementul urmator si la cel precedent (lista dublu inlantuita).
Structura element (sau celula) contine pentru o lista simplu inlantuita un pointer la informatia utila si informatia de legatura (pointerul la elementul urmator).
Inserarea si stergerea de elemente se fac in acest caz prin modificarea unor adrese de legatura. Cautarea unui element, pe de alta parte, se face (ca si in cazul listelor reprezentate prin tablouri) prin parcurgerea secventiala a listei.
Pentru o lista simplu inlantuita parcurgerea se face intr-un singur sens – de la inceputul catre sfarsitul listei.
Exista operatii precum: inserarea inaintea elementului curent din lista sau stergerea elementului curent, care presupun referirea la elementul dinaintea elementului curent – operatie care se realizeaza cu dificultate. Pentru a remedia acest neajuns se utilizeaza listele dublu inlantuite.
Pentru listele dublu inlantuite, un element contine doua informatii de legatura: la elementul urmator si la cel precedent.
Prin legarea intre ele a primului si ultimului element (succesorul ultimului element devine primul, iar predecesorul primului – ultimul element) se confera listei o structura circulara. In acest caz nu se mai folosesc elemente false.
IMPLEMENTAREA OPERATIILOR PRIMITIVE
Setul de operatii primitive implementate este cel propus in primul paragraf. Acestea au fost definite ca functii booleene, care intorc rezultatul adevarat daca operatia se desfasoara normal si fals – in caz ca se produce o eroare; celelalte rezultate sunt transmise prin lista de parametri. Se recomanda ca utilizatorul acestor functii sa testeze rezultatul aplicarii lor, luand masurile corespunzatoare in situatiile de esec. Daca exista siguranta desfasurarii normale a unei operatii se poate omite verificarea conditiei de eroare.
Operatiile primitive sunt grupate intr-un modul separat; in cele ce urmeaza sunt prezentate doua module: LISTES corespunzator implementarii cu tablouri si LISTED corespunzator implementarii cu pointeri. Ele au fost codificate in Pascal si C. Oricare din ele poate fi folosit pentru realizarea de aplicatii cu aceeasi forma de apel in cele doua module.
Operatiile definite se refera la liste cu orice fel de elemente. Acest lucru este posibil datorita utilizarii pointerilor generici catre celule.
In aplicatiile cu liste, tipul informatiei din celule trebuie se fie precizat. Aceasta cere programatorului sa transforme referintele la valori de tip nespecificat in referinte la date de tip precizat, folosind conversia de tip.
IMPLEMENTAREA STATICA A LISTELOR
In cazul alocarii statice, tipul LISTA este descris prin pozitia elementului curent si a ultimului element si printr-un tablou de pointeri la informatia continuta de elemente.
IMPLEMENTAREA DINAMICA A LISTELOR
In acest paragraf sunt listate modulele care realizeaza operatiile primitive cu liste implementate dinamic. S-au folosit liste dublu inlantuite cu doua elemente santinela. In figura urmatoare este detaliata operatia de inserare a unui element intr-o lista implementata dinamic.
NOTA IMPORTANTA: ARTICOLELE PUBLICATE IN PAGINA DE REFERATE AU SCOP DIDACTIC SI SUNT ELABORATE IN URMA UNEI DOCUMENTARI SUSTINUTE. ESTE STRICT INTERZISA PRELUAREA ARTICOLELOR DE PE SITE SI PREZENTAREA LOR LA ORELE DE CURS. Referatele din aceasta sectiune sunt trimise de diferiti colaboratori ai proiectului nostru. Referatele va sunt prezentate pentru COMPLETAREA STUDIULUI INDIVIDUAL, si va incurajam si sustinem sa faceti si voi altele noi bazate pe cercetari proprii.
Referat trimis de: Olteanu Ancuta si Dumitru Adina
