Laborator SDA

Laborator
9.4/10 (5 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 114 în total
Cuvinte : 19261
Mărime: 293.09KB (arhivat)
Cost: Gratis

Cuprins

PREFATA

LISTE SIMPLU ÎNLANTUITE

LISTE CIRCULARE SIMPLU ÎNLANTUITE

LISTE DUBLU ÎNLANTUITE

ARBORI

ARBORI BINARI DE CAUTARE

REPREZENTAREA SI TRAVERSAREA

GRAFURILOR

ALGORITMI PENTRU PRELUCRAREA GRAFURILOR

TABELE DE DISPERSIE

METODE GENERALE DE ELABORARE A ALGORITMILOR (I)

METODE GENERALE DE ELABORARE A ALGORITMILOR (II)

METODE GENERALE DE ELABORARE A ALGORITMILOR (III)

ALGORITMI FUNDAMENTALI DE SORTARE

BIBLIOGRAFIE

Extras din document

LISTE SIMPLU ÎNLANTUITE

1. Continutul lucrarii

În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si particularitatile stivelor si cozilor.

2. Consideratii teoretice

Lista este o multime finita si ordonata de elemente de acelasi tip. Elementele listei se numesc noduri.

Listele pot fi organizate sub forma statica, de tablou, caz în care ordinea este implicit data de tipul tablou unidimensional, sau cel mai des, sub forma de liste dinamice, în care ordinea nodurilor este stabilita prin pointeri. Nodurile listelor dinamice sunt alocate în memoria heap. Listele dinamice se numesc liste înlantuite, putând fi simplu sau dublu înlantuite.

În continuare se vor prezenta principalele operatii asupra listelor simplu înlantuite.

Structura unui nod este urmatoarea:

typedef struct tip_nod {

int cheie; /* câmp neobligatoriu */

alte câmpuri de date utile;

struct tip_nod urm; /* legatura spre urmatorul nod */

} TIP_NOD;

Modelul listei simplu înlantuite este prezentat în fig. 2.1.

Fig. 2.1. Model de lista simplu înlantuita

Pointerii prim si ultim vor fi declarati astfel:

TIP_NOD *prim, *ultim;

2.1 Crearea unei liste simplu înlantuite

Crearea unei liste simplu înlantuite se va face astfel:

a) Initial lista este vida:

prim = 0; ultim = 0;

b) Se genereaza nodul de introdus:

n=sizeof(TIP_NOD);

p=(TIP_NOD *)malloc(n); /* rezervare spatiu de memorie în heap*/

citire date în nodul de adresa p;

c) Se fac legaturile corespunzatoare:

p->urm = 0; /*nodul este ultimul în lista */

if(ultim != 0) ultim->urm = p; /* lista nu este vida */

else prim = p;

/* nodul p este primul introdus în lista */

ultim=p;

2.2 Accesul la un nod al unei liste simplu înlantuite

În functie de cerinte, nodurile listei pot fi accesate secvential, extragând informatia utila din ele. O problema mai deosebita este gasirea unui nod de o cheie data si apoi extragerea informatiei din nodul respectiv. Cautarea nodului dupa cheie se face liniar, el putând fi prezent sau nu în lista.

O functie de cautare a unui nod de cheie “key” va contine secventa de program de mai jos; ea returneaza adresa nodului respectiv în caz de gasire sau pointerul NULL în caz contrar:

TIP_NOD *p;

p=prim;

while( p != 0 ) if (p->cheie == key)

{

/* s-a gasit nodul de cheie data */

/* el are adresa p */

return p;

}

else p=p->urm;

return 0; /* nu exista nod de cheie = key */

2.3 Inserarea unui nod într-o lista simplu înlantuita

Nodul de inserat va fi generat ca la paragraful 2.1; se presupune ca are pointerul p.

Daca lista este vida, acest nod va fi singur în lista:

if (prim == 0) {

prim=p; ultim=p; p->urm=0;

}

Daca lista nu este vida, inserarea se poate face astfel:

a) înaintea primului nod

if(prim != 0) {

p->urm = prim; prim = p;

}

b) dupa ultimul nod:

if (ultim != 0) {

p -> urm = 0; ultim -> urm = p; ultim = p;

}

c) înaintea unui nod precizat printr-o cheie “key”:

- se cauta nodul de cheie “key”:

TIP_NOD *q, *q1;

q1=0; q=prim;

while(q!=0)

{

if(q->cheie==key) break;

q1=q; q=q->urm;

}

- se insereaza nodul de pointer p, facând legaturile corespunzatoare:

if(q!=0) { /*nodul de cheie “key” are adresa q */

if (q==prim) {

p->urm=prim; prim=p;

}

else {

q1->urm=p; p->urm=q;

}

}

d) dupa un nod precizat printr-o cheie “key”:

- se cauta nodul având cheia “key”:

TIP_NOD *q;

q=prim;

while(q!=0) {

if(q->cheie==key) break;

q=q->urm;

}

- se insereaza nodul de adresa p, facând legaturile corespunzatoare:

if (q !=)0) { /* nodul de cheie “key” are adresa q */

p -> urm = q -> urm;

q -> urm=p;

if (q == ultim) ultim = p;

}

2.4 Stergerea unui nod dintr-o lista simplu înlantuita

La stergerea unui nod se vor avea în vedere urmatoarele probleme: lista poate fi vida, lista poate contine un singur nod sau lista poate contine mai multe noduri.

De asemenea se poate cere stergerea primului nod, a ultimului nod sau a unui nod dat printr-o cheie “key”.

a) Stergerea primului nod

TIP_NOD *p;

if(prim!=0) { /* lista nu este vida */

p=prim; prim=prim->urm;

elib_nod(p);

/*eliberarea spatiului de memorie */

if(prim==0) ultim=0;

/* lista a devenit vida */

}

Preview document

Laborator SDA - Pagina 1
Laborator SDA - Pagina 2
Laborator SDA - Pagina 3
Laborator SDA - Pagina 4
Laborator SDA - Pagina 5
Laborator SDA - Pagina 6
Laborator SDA - Pagina 7
Laborator SDA - Pagina 8
Laborator SDA - Pagina 9
Laborator SDA - Pagina 10
Laborator SDA - Pagina 11
Laborator SDA - Pagina 12
Laborator SDA - Pagina 13
Laborator SDA - Pagina 14
Laborator SDA - Pagina 15
Laborator SDA - Pagina 16
Laborator SDA - Pagina 17
Laborator SDA - Pagina 18
Laborator SDA - Pagina 19
Laborator SDA - Pagina 20
Laborator SDA - Pagina 21
Laborator SDA - Pagina 22
Laborator SDA - Pagina 23
Laborator SDA - Pagina 24
Laborator SDA - Pagina 25
Laborator SDA - Pagina 26
Laborator SDA - Pagina 27
Laborator SDA - Pagina 28
Laborator SDA - Pagina 29
Laborator SDA - Pagina 30
Laborator SDA - Pagina 31
Laborator SDA - Pagina 32
Laborator SDA - Pagina 33
Laborator SDA - Pagina 34
Laborator SDA - Pagina 35
Laborator SDA - Pagina 36
Laborator SDA - Pagina 37
Laborator SDA - Pagina 38
Laborator SDA - Pagina 39
Laborator SDA - Pagina 40
Laborator SDA - Pagina 41
Laborator SDA - Pagina 42
Laborator SDA - Pagina 43
Laborator SDA - Pagina 44
Laborator SDA - Pagina 45
Laborator SDA - Pagina 46
Laborator SDA - Pagina 47
Laborator SDA - Pagina 48
Laborator SDA - Pagina 49
Laborator SDA - Pagina 50
Laborator SDA - Pagina 51
Laborator SDA - Pagina 52
Laborator SDA - Pagina 53
Laborator SDA - Pagina 54
Laborator SDA - Pagina 55
Laborator SDA - Pagina 56
Laborator SDA - Pagina 57
Laborator SDA - Pagina 58
Laborator SDA - Pagina 59
Laborator SDA - Pagina 60
Laborator SDA - Pagina 61
Laborator SDA - Pagina 62
Laborator SDA - Pagina 63
Laborator SDA - Pagina 64
Laborator SDA - Pagina 65
Laborator SDA - Pagina 66
Laborator SDA - Pagina 67
Laborator SDA - Pagina 68
Laborator SDA - Pagina 69
Laborator SDA - Pagina 70
Laborator SDA - Pagina 71
Laborator SDA - Pagina 72
Laborator SDA - Pagina 73
Laborator SDA - Pagina 74
Laborator SDA - Pagina 75
Laborator SDA - Pagina 76
Laborator SDA - Pagina 77
Laborator SDA - Pagina 78
Laborator SDA - Pagina 79
Laborator SDA - Pagina 80
Laborator SDA - Pagina 81
Laborator SDA - Pagina 82
Laborator SDA - Pagina 83
Laborator SDA - Pagina 84
Laborator SDA - Pagina 85
Laborator SDA - Pagina 86
Laborator SDA - Pagina 87
Laborator SDA - Pagina 88
Laborator SDA - Pagina 89
Laborator SDA - Pagina 90
Laborator SDA - Pagina 91
Laborator SDA - Pagina 92
Laborator SDA - Pagina 93
Laborator SDA - Pagina 94
Laborator SDA - Pagina 95
Laborator SDA - Pagina 96
Laborator SDA - Pagina 97
Laborator SDA - Pagina 98
Laborator SDA - Pagina 99
Laborator SDA - Pagina 100
Laborator SDA - Pagina 101
Laborator SDA - Pagina 102
Laborator SDA - Pagina 103
Laborator SDA - Pagina 104
Laborator SDA - Pagina 105
Laborator SDA - Pagina 106
Laborator SDA - Pagina 107
Laborator SDA - Pagina 108
Laborator SDA - Pagina 109
Laborator SDA - Pagina 110
Laborator SDA - Pagina 111
Laborator SDA - Pagina 112
Laborator SDA - Pagina 113
Laborator SDA - Pagina 114

Conținut arhivă zip

  • Laborator SDA.doc

Alții au mai descărcat și

Proiect Structuri de Date - Orar

1. INTRODUCERE 1.1 Obiectivul problemei : Aceasta aplicatie informatica are ca obiectiv gestionarea cat mai buna a orarului unei facultati pentru...

Structuri de Date

1)Liste.Concept:Structura de date dinamica(isi schimba nr de elemente si relatiile dintre ele. Clasificare:simpu inlantuite,dublu...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Proiectarea și Analiza Algoritmilor

//Varianta A: Arbori B :structura , cel mai lung cuvant,cel mai mare cuvant din arbore. #define N 2 #define M 4 //Strunctura necesara pentru...

Algoritmi și Structuri de Date

Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...

Programarea Calculatorului

1. Lucrare de laborator Nr. 1 2. Tema: Structura programului in limbajul C. Programarea algoritmilor cu structura lineara. 3. Scopul lucrarii:...

Structuri de Date și Algoritmi

Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...

Structuri de Date - Liste

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...

Ai nevoie de altceva?