Descriere:Cazuri particulare de liste liniare
Download:Nu necesita
Autor:Anonim
Sursa (Link-ul oficial): Propria parere:Util.
Tutorialul:
a. Stiva
Stiva este o structura de date care functioneaza dupa principiul "Last in - first out". Putem imagina o stiva ca un teanc de farfurii, de carti, etc. Conform acestui principiu, putem deduce ca asupra unei stive sunt permise urmatoarele operatii:
- Adaugarea unui nod inainte de primul introdus
- Stergerea primului nod
Observatie:
Primul nod dn stiva se numeste varf si dupa cum observam este singurul nod asupra caruia sunt permise operatii. Ultimul nod din stiva se numeste baza.
In urma crearii unei stive in mod dinamic, nodurile vor fi prelucrate in ordine inversa introducerii lor.
a1. Crearea unei stive:
Se parcurg aceleasi etape ca la listele liniare simplu inlantuite, doar ca adaugarea unui nod se face inainte de v (varf).
Cod: Selectaţi tot
struct nod {
<tip> info;
nod *adr;
};
typedef nod *NOD;
int n, i;
NOD *v, *b, *p;
printf("Dati numarul de noduri: ");
scanf("%d", &n);
v=(NOD)malloc(sizeof(nod));
printf("nr = ");
scanf("%d", &v->info);
v->adr=0;
b=v;
for(i=2; i <= n; i++)
q=(NOD)malloc(sizeof(nod));
printf("nr = ");
scanf("%d", &q->info);
q->adr=v;
v=q;
}b. Coada
Coada este o structura de date care functioneaza dupa principiul "First in - first out". Conform acestui principiu de functionare, se permit asupra unei cozi urmatoarele operatii:
- Adaugarea unui nod dupa ultimul introdus;
- Stergerea primului nod;
Observatii:
- Primul nod din coada se numeste cap iar ultimul nod se numeste coada.
- Crearea unei cozi este identica cu crearea unei liste simplu inlantuite. Cum nici celelalte operatii permise nu difera de cele prezentate la aceasta structura de date, lasam ca exercitiu implementarea operatiilor asupra unei cozi.
c. Lista circulara
O lista circulara este o structura dinamica de date in care ultimul nod contine in partea dinamica adresa primului nod. Practic, o lista circulara nu are prim si ultim nod, ci doar nod de plecare in parcurgerea ei.
Pentru crearea unei liste circulare, vom folosi aceeasi metoda ca la lista liniara simplu inlantuita, avand grija ca la sfarsitul crearii ultimului nod sa adaugam adresa primului element:
Cod: Selectaţi tot
struct nod {
<tip> info;
nod *adr;
};
typedef struct nod *NOD;
int n, i;
NOD *p, *u, *q;
printf("Dati numarul de noduri: ");
scanf("%d", &n);
p=(NOD)malloc(sizeof(nod)); // 1
printf("nr = ");
scanf("%d", &p->info); // (2)
p->adr=0;
for(i=2; i <= n; i++) {
q=(NOD)malloc(sizeof(nod));
printf("nr = ");
scanf("%d", &q->info);
q->adr=0;
u->adr=q; // (4)
u=q;
}
u->adr=p;Parcurgerea unei liste circulare se face pornind de la un nod dat, p, pana cand se revine la nodul de pornire:
Cod: Selectaţi tot
q=p;
do {
printf("%d", q->info);
q=q->adr;
} while(q!=p);Putem adauga un nod inainte de nodul de plecare sau inainte de un nod oarecare.
Inserarea unui nod inainte de primul nod din lista
Se creeaza nodul q si se realizeaza legatura dintre el si lista. Apoi acesta va fi noul prim nod. Se are in vedere pastrarea calitatii de lista circulara.
Cod: Selectaţi tot
q=(NOD)malloc(sizeof(nod));
printf("nr = ");
scanf("%d", &q->info);
q->adr=p;
u->adr=q;
p=q;Inserarea unui nod in interiorul listei circulare se face analog cu inserarea intr-o lista simplu inlantuita.
c4. Stergerea unui nod dintr-o lista circulara
Putem sterge nodul de pornire sau un nod din interiorul listei. Pentru a sterge un nod, se parcurg aceleasi etape prezentate anterior, avand grija ca lista sa ramana circulara.
Stergerea nodului de plecare
Cod: Selectaţi tot
NOD aux;
aux=p;
p=p->adr;
u->adr=p;
free(aux);Se parcurge lista pana la nodul anterior celui cu informatia x (4) si acesta se leaga in lista de cel urmator celui cu informatia x (5):
Cod: Selectaţi tot
NOD aux;
q=p;
while(q->adr->adr!=p && q->info!=x)
q=q->adr;
aux=q->adr;
q->adr=q->adr->adr;
free(aux);