Structuri de date și algoritmi

Înainte de a elabora un algoritm, trebuie să ne gândim la modul în care reprezentăm datele. Structurile fundamentale de date cu care se poate opera sunt: fişier, tablou, listă, graf, arbore. În acest capitol ne vom ocupa de liste, arbori şi grafuri, întrucât primele două (tablou, fişier) au fost studiate anterior. O listă este o colecţie de elemente de informaţie (noduri) aranjate într-o anumită ordine. Lungimea unei liste este dată de numărul de noduri din listă. Structura listei trebuie să ne permită să determinăm eficient care este primul/ultimul nod în structură şi care este predecesorul/succesorul unui nod dat. Cea mai simplă listă este lista liniară. Un alt tip de listă este cea circulară, în care, după ultimul nod, urmează primul, deci fiecare nod are succesor şi predecesor.

Operaţiile curente care se fac în liste sunt: inserarea unui nod, ştergerea (extragerea) unui nod, concatenarea unor liste, numărarea elementelor unei liste etc. Implementarea unei liste se poate face in principal în două moduri.

Primul, constă în implementarea secvenţială, adică în locaţii succesive de memorie, conform ordinii nodurilor din listă, care conţin informaţia dorită. Avantajul acestei tehnici este accesul rapid la predecesorul/succesorul unui nod, inclusiv găsirea rapidă a primului/ultimului nod. Dezavantajele sunt inserarea/ştergerea relativ complicată a unui nod şi faptul că, în general, nu se foloseşte întreaga memorie alocată listei.

Cel de-al doilea, implementarea înlănţuită. în care fiecare nod conţine două părţi: informatia propriu-zisă şi adresa nodului următor. Alocarea memoriei fiecărui nod se poate face în mod dinamic, în timpul rulării programului. Accesul la un nod necesită parcurgerea tuturor predecesorilor săi, ceea ce poate lua ceva mai mult timp. Inserarea/ştergerea unui nod este în schimb foarte rapidă. Se poate construi o listă dublu înlănţuită, care conţine două adrese în loc de una, astfel încat un nod să conţină pe lânăa adresa nodului următor şi adresa nodului anterior.

Listele implementate înlănţuit pot fi reprezentate cel mai simplu prin tablouri. În acest caz, adresele sunt de fapt indici de tablou. O alternativă este să folosim tablouri paralele: să memoram informaţiile fiecărui nod într-un tablou INFO[n], iar adresele (indicii) nodurilor succesoare într-un tablou SUCC[n]. Indicele primului nod din listă (fie că este de tip coadă sau stivă) va fi păstrat într-o variabilă. Acest mod de reprezentare este simplu dar apare o problemă, şi anume cea a gestionării locaţiilor libere. O soluţie este să reprezentăm locaţiile libere tot sub forma unei liste înlănţuite. Atunci, ştergerea unui nod din listă implică inserarea sa într-o listă cu locaţii libere, iar inserarea unui nod în listă implică ştergerea sa din lista cu locaţii libere. Este interesant de remarcat că, pentru implementarea listei de locaţii libere, putem folosi aceleaşi tablouri, dar avem nevoie de o alta variabilă, care să conţină indicele primei locaţii libere din VAL şi LINK, în timp ce variabila cealaltă, iniţială, va conţine adresa primei locaţii din lista propriu-zisă.

Vom exemplifica în continuare două tipuri de liste foarte des folosite, şi anume coada şi stiva, considerând implementarea ce utilizează alocarea statică (tablouri).

O stivă (stack) este o listă liniară cu proprietatea că operaţiile de inserare/extragere a nodurilor se fac în/din coada listei, motiv pentru care stivele se mai numesc şi liste LIFO (Last In First Out). Cel mai natural mod de reprezentare pentru o stivă este implementarea secvenţială într-un tablou S[n], unde n este numarul maxim de noduri. Primul nod va fi memorat în S[0], al doilea în S[1], iar ultimul în S[n-1]; sp este o variabila care conţine adresa (indicele) ultimului nod inserat. Iniţial, cand stiva este vidă, avem sp = -1 (sau poate fi 0). Iată funcţiile de inserare, extragere a unui nod, precum şi cele de afişare şi de semnalare a situaţiilor extreme (stivă goală sau stivă plină).

/* stivatab.c - operatii cu o stiva realizata static intr-un tablou;

operatii disponibile: inserare, extragere, afisare cap stiva,

afisare stiva, afisare pointer la varful stivei */

6

#include <stdio.h>

#include <conio.h>

#define MaxS 10

typedef int ElTip; // ElTip - definire tip element din stiva

typedef struct {

ElTip elem [MaxS];// spatiu pentru elem. stivei

int sp;

/* index/ referinta la varful stivei (stack pointer) */

} TStiva, *AStiva;

void eroare (char *meserr){

printf("%sn", meserr);

}

void InitStiva (AStiva rs){

/* initializare stiva, sp nu refera un element (stiva goala) */

rs->sp=-1;

}

int StivaGoala (AStiva rs){

return (rs->sp == -1);

}

int StivaPlina (AStiva rs){

/* stiva este plina, index=MaxS-1, indice maxim,

nu se mai pot introduce elemente in stiva */

return (rs->sp == MaxS-1);

}

void Push (AStiva rs, ElTip el){

/* introduce element in stiva, daca nu este plina */

if (StivaPlina (rs))

eroare ("Stiva Plina !!!");

else {rs->sp=rs->sp+1;

rs->elem[rs->sp]=el;

}

}

ElTip Pop (AStiva rs){

/* extrage element din stiva, daca nu este goala */

ElTip e;

if (StivaGoala (rs))

{eroare ("Stiva Goala !!!");

return 0;

}

else

{e=rs->elem[rs->sp];

rs->sp=rs->sp-1;

return e;

}

}

ElTip CapStiva (AStiva rs){

if (StivaGoala (rs))

{eroare ("Stiva Goala !!!");

return 0;