Structuri de Date - Liste

Curs
9/10 (2 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 17 în total
Cuvinte : 5281
Mărime: 59.19KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Marian Paunescu
Este o gama variata de structuri de date folositi ca niste algoritmi clasici.

Extras din document

3. Structuri elementare de date

Inainte de a elabora un algoritm, trebuie sa ne gandim la modul in care reprezentam datele. In acest capitol vom trece in revista structurile fundamentale de date cu care vom opera. Presupunem in continuare ca sunteti deja familiarizati cu notiunile de fisier, tablou, lista, graf, arbore si ne vom concentra mai ales pe prezentarea unor concepte mai particulare: heap-uri si structuri de multimi disjuncte.

3.1 Liste

O lista este o colectie de elemente de informatie (noduri) aranjate intr-o anumita ordine. Lungimea unei liste este numarul de noduri din lista. Structura corespunzatoare de date trebuie sa ne permita sa determinam eficient care este primul/ultimul nod in structura si care este predecesorul/succesorul (daca exista) unui nod dat. Iata cum arata cea mai simpla lista, lista liniara:

O lista circulara este o lista in care, dupa ultimul nod, urmeaza primul, deci fiecare nod are succesor si predecesor.

Operatii curente care se fac in liste sunt: inserarea unui nod, stergerea (extragerea) unui nod, concatenarea unor liste, numararea elementelor unei liste etc. Implementarea unei liste se poate face in principal in doua moduri:

- Implementarea secventiala, in locatii succesive de memorie, conform ordinii nodurilor in lista. Avantajele acestei tehnici sunt accesul rapid la predecesorul/succesorul unui nod si gasirea rapida a primului/ultimului nod. Dezavantajele sunt inserarea/stergerea relativ complicata a unui nod si faptul ca, in general, nu se foloseste intreaga memorie alocata listei.

- Implementarea inlantuita. In acest caz, fiecare nod contine doua parti: informatia propriu-zisa si adresa nodului succesor. Alocarea memoriei fiecarui nod se poate face in mod dinamic, in timpul rularii programului. Accesul la un nod necesita parcurgerea tuturor predecesorilor sai, ceea ce poate lua ceva mai mult timp. Inserarea/stergerea unui nod este in schimb foarte rapida. Se pot folosi doua adrese in loc de una, astfel incat un nod sa contina pe langa adresa nodului succesor si adresa nodului predecesor. Obtinem astfel o lista dublu inlantuita, care poate fi traversata in ambele directii.

Listele implementate inlantuit pot fi reprezentate cel mai simplu prin tablouri. In acest caz, adresele sunt de fapt indici de tablou. O alternativa este sa folosim tablouri paralele: sa memoram informatia fiecarui nod (valoarea) intr-o locatie VAL[i] a tabloului VAL[1 .. n], iar adresa (indicele) nodului sau succesor intr-o locatie LINK[i] a tabloului LINK[1 .. n]. Indicele de tablou al locatiei primului nod este memorat in variabila head. Vom conveni ca, pentru cazul listei vide, sa avem head = 0. Convenim de asemenea ca LINK[ultimul nod din lista] = 0. Atunci, VAL[head] va contine informatia primului nod al listei, LINK[head] adresa celui de-al doilea nod, VAL[LINK[head]] informatia din al doilea nod, LINK[LINK[head]] adresa celui de-al treilea nod etc.

Acest mod de reprezentare este simplu dar, la o analiza mai atenta, apare o problema esentiala: cea a gestionarii locatiilor libere. O solutie eleganta este sa reprezentam locatiile libere tot sub forma unei liste inlantuite. Atunci, stergerea unui nod din lista initiala implica inserarea sa in lista cu locatii libere, iar inserarea unui nod in lista initiala implica stergerea sa din lista cu locatii libere. Aspectul cel mai interesant este ca, pentru implementarea listei de locatii libere, putem folosi aceleasi tablouri. Avem nevoie de o alta variabila, freehead, care va contine indicele primei locatii libere din VAL si LINK. Folosim aceleasi conventii: daca freehead = 0 inseamna ca nu mai avem locatii libere, iar LINK[ultima locatie libera] = 0.

Vom descrie in continuare doua tipuri de liste particulare foarte des folosite.

3.1.1 Stive

O stiva (stack) este o lista liniara cu proprietatea ca operatiile de inserare/extragere a nodurilor se fac in/din coada listei. Daca nodurile A, B, C, D sunt inserate intr-o stiva in aceasta ordine, atunci primul nod care poate fi extras este D. In mod echivalent, spunem ca ultimul nod inserat va fi si primul sters. Din acest motiv, stivele se mai numesc si liste LIFO (Last In First Out), sau liste pushdown.

Cel mai natural mod de reprezentare pentru o stiva este implementarea secventiala intr-un tablou S[1 .. n], unde n este numarul maxim de noduri. Primul nod va fi memorat in S[1], al doilea in S[2], iar ultimul in S[top], unde top este o variabila care contine adresa (indicele) ultimului nod inserat. Initial, cand stiva este vida, avem top = 0. Iata algoritmii de inserare si de stergere (extragere) a unui nod:

function push(x, S[1 .. n])

{adauga nodul x in stiva}

if top ³ n then return “stiva plina”

top ¬ top+1

S[top] ¬ x

return “succes”

function pop(S[1 .. n])

{sterge ultimul nod inserat din stiva si il returneaza}

if top £ 0 then return “stiva vida”

x ¬ S[top]

top ¬ top-1

return x

Cei doi algoritmi necesita timp constant, deci nu depind de marimea stivei.

Vom da un exemplu elementar de utilizare a unei stive. Daca avem de calculat expresia aritmetica

Preview document

Structuri de Date - Liste - Pagina 1
Structuri de Date - Liste - Pagina 2
Structuri de Date - Liste - Pagina 3
Structuri de Date - Liste - Pagina 4
Structuri de Date - Liste - Pagina 5
Structuri de Date - Liste - Pagina 6
Structuri de Date - Liste - Pagina 7
Structuri de Date - Liste - Pagina 8
Structuri de Date - Liste - Pagina 9
Structuri de Date - Liste - Pagina 10
Structuri de Date - Liste - Pagina 11
Structuri de Date - Liste - Pagina 12
Structuri de Date - Liste - Pagina 13
Structuri de Date - Liste - Pagina 14
Structuri de Date - Liste - Pagina 15
Structuri de Date - Liste - Pagina 16
Structuri de Date - Liste - Pagina 17

Conținut arhivă zip

  • Structuri de Date - Liste.doc

Alții au mai descărcat și

Implementarea bazei de date a unui policlinici - listă dublu înlănțuită circulară

1. Introducere 1.1. Istoria bazelor de date Când vine vorba despre stocarea informaţiilor, pentru unii acest termen înseamnă o agenda veche în...

Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...

Grafuri Neorientate - Euleriene

’’ Ideile, si daca sunt abstracte si daca nu, ca sa le poti manui, trebuie sa le ai. Calculatorul, ca sa-si faca treaba, trebuie sa inteleaga...

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

Clase în Java

Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...

Clase

1. Programare procedurala –Programare orientata pe obiecte. Limbajul C, ca si Pascal, utilizeaza modelul programarii structurate procedurale, care...

Te-ar putea interesa și

Testarea Adaptivă ca Factor de Optimizare a Procesului de Instruire în Învățământul Universitar

INTRODUCERE Actualitatea temei. în ultimele trei decenii în lumea educaţiei s-au produs schimbări de ordin principial, ca reacţie la...

Program de contabilitate primară într-un laborator de cofetărie

1 INTRODUCERE Gestiunea datelor a stat in atentia majoritatii utilizatorilor calculatoarelor inca de la incerputul folosirii acestora. La inceput...

Structuri de Date în Limbajul Java

Motivaţia lucrării Structurile de date reprezintă modalitatea în care datele sunt dispuse în memoria calculatorului(sau păstrate pe disc)....

Limbajul Tool - Command Language

1. Iniţiere in Tcl\Tk 1.1 Iniţiere Tcl este un limbaj interpretativ in care totul este sub forma de şiruri de...

Proiect PSI pe o firmă de leasing financiar

Diagrama de clase se descriu clasele.Ele descriu aspecte structural ale sistemului. 38 PREZENTAREA SOCIETATII DE Porsche Leasing Romania • 1999 -...

Activitatea de Vânzare și Cumpărare a Acțunilor la o Societate de Valori Mobiliare

1. Prezentarea societăţii SSIF Broker S.A. SIVM BROKER SA (prima denumire a societăţii comerciale SSIF BROKER SA) a fost infiinţată ca societate...

Liste liniare dublu înlănțuite

CAP. STRUCTURI DE DATE Structura de date este o notiune abstracta, caracterizata prin operatiile care se executa asupra ei, in timp ce tipul de...

Registru de casă

2. Prezentarea generala a aplicatiei 2.1. Obiective, performante, limite Aplicatia isi propune realizarea registrului de casa pe care il...

Ai nevoie de altceva?