PROGRAMAREA STRUCTURILOR DE DATE IN C

PROGRAMAREA STRUCTURILOR DE DATE IN C

Implementarea operatiilor cu structuri de date

Operatiile cu anumite structuri de date sunt usor de programat si de aceea pot fi rescrise in aplicatiile care le folosesc, pentru a tine seama de tipul datelor sau de alte particularitati ale aplicatiei. Din aceasta categorie fac parte vectori, matrice, stive, cozi, liste inlantuite simple si chiar arbori binari fara reechilibrare.

Pentru alte structuri operatiile asociate pot fi destul de complexe, astfel ca este preferabil sa gasim o biblioteca sau surse care pot fi adaptate rapid la specificul aplicatiei. Din aceasta categorie fac parte arborii binari cu autoechilibrare, tabele de dispersie, liste cu acces direct ("skip list"), arbori B s.a.

Biblioteci generale de functii pentru operatii cu principalele structuri de date exista numai pentru limbajele orientate pe obiecte (C++, C#, Java). Pot fi gasite insa si biblioteci specializate in C, Pascal sau Fortran, cum este LEDA pentru operatii cu grafuri. Pentru referinte catre diverse implementari se poate folosi [Ski97] si dictionarul Wikipedia de pe Internet ( cu cautare dupa "Data Structures").

Limbajul de programare folosit in descrierea si/sau in implementarea operatiilor cu colectii de date poate influenta mult claritatea descrierii si lungimea programelor. Diferenta cea mai importanta este intre limbajele procedurale (Pascal si C) si limbajele orientate pe obiecte (C++ si Java).

In acest text se foloseste limbajul C cu doua imprumuturi din C++: comentarii care incep cu "//" si se termina la sfarsitul liniei si parametri de tip referinta in functii ( declarati cu 'tip &').

Uilizarea tipului referinta permite simplificarea definirii si utilizarii functiilor care modifica continutul unei structuri de date, definite printr-un tip structura. In C, o functie nu poate modifica valoarea unui argument de tip structura decat daca primeste adresa variabilei ce se modifica, printr-un argument de un tip pointer. Exemplul urmator foloseste o structura care reuneste un vector si dimensiunea sa, iar functiile utilizeaza parametri de tip pointer.

#define M 100 // dimensiune maxima vectori

typedef struct Vector;

// operatii cu vectori

void initV (Vector * pv)

void addV ( Vector * pv, int x)

void printV ( Vector v)

void main()

Pentru o utilizare uniforma a functiilor si pentru eficienta am putea folosi argumente pointer si pentru functiile care nu modifica vectorul (de ex. "printV").

In C++ si in unele variante de C se pot folosi parametri de tip referinta, care simplifica mult definirea si utilizarea de functii cu parametri modificabili. Un parametru formal referinta se declara folosind caracterul '&' intre tipul si numele parametrului. In interiorul functiei parametrul referinta se foloseste la fel ca un parametru de acelasi tip (transmis prin valoare). Parametrul efectiv care va inlocui un parametru formal referinta poate fi orice nume de variabila (de un tip identic sau compatibil). Exemple de functii din programul anterior cu parametri referinta:

void initV (Vector & v)

void addV ( Vector & v, int x)

void main()

In continuare vom folosi parametri de tip referinta pentru functiile care trebuie sa modifice valorile acestor parametri. In felul acesta utilizarea functiilor este uniforma, indiferent daca ele modifica sau nu variabila colectie primita ca argument.

In cazul vectorilor sunt posibile si alte solutii care sa evite functii cu argumente modificabile (de ex. memorarea lungimii la inceputul unui vector de numere), dar vom prefera solutiile general aplicabile oricarei colectii de date.

O alta alegere trebuie facuta pentru functiile care au ca rezultat un element dintr-o colectie: functia poate avea ca rezultat valoarea elementului sau poate fi de tip void iar valoarea sa fie transmisa in afara printr-un argument de tip referinta sau pointer. Pentru o functie care furnizeaza elementul (de un tip T) dintr-o pozitie data a unui vector, avem de ales intre urmatoarele variante:

T get ( Vector & v, int k); // rezultat obiectul din pozitia k

void get (Vector& v, int k, T & x); // extrage din pozitia k a lui v in x

int get (Vector& v, int k, T & x); // rezultat cod de eroare

unde T este un tip specific aplicatiei, definit cu 'typedef'.

Alegerea intre prima si ultima varianta este oarecum subiectiva si influentata de limbajul utilizat (de ex. in Java nu este posibila decat prima varianta).

O alternativa la functiile cu parametri modificabili este utilizarea de variabile externe (globale) pentru colectiile de date si scoaterea acestor colectii din lista de argumente a subprogramelor care opereaza cu colectia. Solutia este posibila deseori deoarece multe aplicatii folosesc o singura colectie de un anumit tip (o singura stiva, un singur graf) si ea se intalneste in textele mai simple despre structuri de date. Astfel de functii nu pot fi reutilizate in aplicatii diferite si nu pot fi introduse in biblioteci de subprograme, dar variabilele externe simplifica programarea si fac mai eficiente functiile recursive (cu mai putini parametri de pus pe stiva la fiecare apel).

Exemplu de utilizare a unui vector ca variabila externa:

Vector a; // variabila externa

void initV()

void addV (int x)

// utilizare operatii cu un vector

void main()

Functiile de mai sus pot fi folosite numai intr-un program care lucreaza cu un singur vector, declarat ca variabila externa cu numele 'a'. Daca programul foloseste mai multi vectori, functiile anterioare nu mai pot fi folosite. In general se recomanda ca toate datele necesare unui subprogram si toate rezultatele sa fie transmise prin argumente sau prin numele functiei.

Majoritatea subprogramelor care realizeaza operatii cu o structura de date se pot termina anormal, fie din cauza unor argumente cu valori incorecte, fie din cauza starii colectiei; de exemplu, incercarea de adaugare a unui nou element la un vector plin. In absenta unui mecanism de tratare a exceptiilor program (cum sunt cele din Java si C++), solutiile de raportare a acestei conditii de catre un subprogram sunt :

- Terminarea intregului program dupa afisarea unui mesaj, cu sau fara utilizarea lui 'assert' (pentru erori grave dar putin probabile) . Exemplu:

// extragere element dintr-un vector

T get ( Vector & v, int k)

- Scrierea tuturor subprogramelor ca functii de tip boolean (intreg in C), cu rezultat 1 (sau alta valoare pozitiva) pentru terminare normala si rezultat 0 sau negativ pentru terminare anormala. Exemplu:

// extragere element dintr-un vector

int get ( Vector & v, int k, T & x)

// utilizare

if ( get(v,k,x) < 0)

Utilizarea de tipuri generice

O colectie poate contine valori numerice de diferite tipuri si lungimi sau siruri de caractere sau alte tipuri agregat (structuri), sau pointeri (adrese). Se doreste ca operatiile cu un anumit tip de colectie sa poata fi scrise ca functii generale, adaptabile pentru fiecare tip de date ce poate face parte din colectie.

Limbajele orientate pe obiecte au rezolvat aceasta problema, fie prin utilizarea de tipuri generice, neprecizate (clase "template"), fie prin utilizarea unui tip obiect foarte general pentru elementele unei colectii, tip din care pot fi derivate orice alte tipuri de date memorate in colectie (tipul 'Object' in Java).

Realizarea unei colectii generice in limbajul C se poate face in doua moduri:

1) Prin utilizarea de tipuri generice (neprecizate) pentru elementele colectiei in subprogramele ce realizeaza operatii cu colectia. Pentru a folosi astfel de functii ele trebuie adaptate la tipul de date cerut de o aplicatie. Adaptarea se face partial de catre compilator (prin macro-substitutie) si partial de catre programator (care trebuie sa dispuna de forma sursa pentru aceste subprograme).

2) Prin utilizarea unor colectii de pointeri la un tip neprecizat ("void *" ) si a unor argumente de acest tip in subprograme, urmand ca inlocuirea cu un alt tip de pointer (la date specifice aplicatiei) sa se faca la executie. Utilizarea unor astfel de functii este mai dificila, dar utilizatorul nu trebuie sa intervina in textul sursa al subprogramelor si are mai multa flexibilitate in adaptarea colectiilor la diverse tipuri de date.

Primul exemplu arata cum se defineste un vector cu componente de un tip T neprecizat in functii, dar precizat in programul care foloseste multimea :

// multimi de elemente de tipul T

#define M 1000 // dimensiune maxima vector

typedef int T ; // tip componente multime

typedef struct Vector;

// operatii cu un vector de obiecte

void initV (Vector & a )

void addV ( Vector & a, T x)

int findV ( Vector a, T x)

Functiile anterioare sunt corecte numai daca tipul T este un tip numeric pentru ca operatiile de comparare la egalitate si de atribuire depind in general de tipul datelor. Operatiile de citire-scriere a datelor depind de asemenea de tipul T , dar ele fac parte in general din programul de aplicatie.

Pentru operatiile de atribuire si comparare avem doua posibilitati:

a) Definirea unor operatori generalizati, modificati prin macro-substitutie :

#define EQ(a,b) ( a==b) // equals

#define LT(a,b) (a < b) // less than

Exemplu de functie care foloseste acesti operatori:

int findV ( Vector a, T x)

Pentru o multime de siruri de caractere trebuie operate urmatoarele modificari in secventele anterioare :

#define EQ(a,b) ( strcmp(a,b)==0) // equals

#define LT(a,b) (strcmp(a,b) < 0) // less than

typedef char * T ;

b) Transmiterea functiilor de comparare, atribuire, s.a ca argumente la functiile care le folosesc (fara a impune anumite nume acestor functii). Exemplu:

typedef char * T;

typedef int (*Fcmp) ( T a, T b) ;

int findV ( Vector a, T x, Fcmp cmp)

In cazul structurilor de date cu elemente legate prin pointeri (liste si arbori) mai exista o solutie de scriere a functiilor care realizeaza operatii cu acele structuri astfel ca ele sa nu depinda de tipul datelor memorate: crearea nodurilor de lista sau de arbore se face in afara functiilor generale (in programul de aplicatie), iar functiile de insertie si de stergere primesc un pointer la nodul de adaugat sau de sters si nu valoarea ce trebuie adaugata sau eliminata. Aceasta solutie nu este adecvata structurilor folosite pentru cautarea dupa valoare (multimi, dictionare).

Uneori tipul datelor folosite de o aplicatie este un tip agregat (o structura C): o data calendaristica ce grupeaza numere pentru zi, luna, an , descrierea unui arc dintr-un graf pentru care se memoreaza numerele nodurilor si costul arcului, s.a. Problema care se pune este daca tipul T este chiar tipul structura sau este un tip pointer la acea structura. Ca si in cazul sirurilor de caractere este preferabil sa se manipuleze in programe pointeri (adrese de structuri) si nu structuri. In plus, atribuirea intre pointeri se face la fel ca si atribuirea intre numere (cu operatorul '=').

In concluzie, tipul neprecizat T al elementelor unei colectii este de obicei fie un tip numeric, fie un tip pointer (inclusiv de tip "void *" ). Avantajul principal al acestei solutii este simplitatea programelor, dar ea nu se poate aplica pentru colectii de colectii (un vector de liste, de exemplu) si nici pentru colectii neomogene.

Utilizarea de pointeri generici

O a doua solutie pentru o colectie generica este o colectie de pointeri la orice tip (void *), care vor fi inlocuiti cu pointeri la datele folosite in fiecare aplicatie. Si in acest caz functia de comparare trebuie transmisa ca argument functiilor de insertie sau de cautare in colectie. Exemplu de vector generic cu pointeri:

#define M 100 // dimens maxima vector

typedef void * Ptr; // pointer la un tip neprecizat

typedef int (* fcmp) (Ptr,Ptr); // tip functie de comparare

typedef void (* fprnt) (Ptr); // tip functie de afisare

typedef struct Vector;

void initV (Vector & a)

//afisare date de la adresele continute in vector

void printV ( Vector a, fprnt print )

// adaugare la sfirsitul unui vector de pointeri

void addV ( Vector & a, Ptr p)

// cautare in vector de pointeri

int findV ( Vector v, Ptr p, fcmp cmp)

Secventa urmatoare arata cum se poate folosi un vector de pointeri pentru a memora arce dintr-un graf cu costuri:

// tipuri de date si functii ale aplicatiei

typedef struct arc;

void prntarc ( Ptr p)

int readarc (Ptr p)

int cmparc (Ptr p1, Ptr p2)

void main ()

printV (v, prntarc); // afisare vector

}

Avantajele asupra colectiei cu date de un tip neprecizat sunt:

- Functiile pentru operatii cu colectii pot fi compilate si puse intr-o biblioteca si nu este necesar codul sursa.

- Se pot crea colectii cu elemente de tipuri diferite, pentru ca in colectie se memoreaza adresele elementelor, iar adresele pot fi reduse la tipul comun 'void*'.

- Se pot crea colectii de colectii: vector de vectori, lista de liste, vector de liste etc.

Dezavantajul principal al colectiilor de pointeri (in C) este complexitatea unor aplicatii, cu erorile asociate unor operatii cu pointeri. Pentru o colectie de numere trebuie alocata memorie dinamic pentru fiecare numar, ca sa obtinem cate o adresa distincta pentru a fi memorata in colectie. Exemplu de creare a unui graf ca vector de vectori de pointeri la intregi (liste de noduri vecine pentru fiecare nod din graf):

void initV (Vector* & pv)

// adaugare la sfirsitul unui vector de pointeri

void addV ( Vector* & pv, Ptr p)

// afisare date reunite in vector de orice pointeri

void printV ( Vector* pv, Fprnt print)

void main () while (j>=0);

addV(graf,vecini); // adauga vector de vecini la graf

}

}

Pentru colectii ordonate (liste ordonate, arbori partial ordonati, arbori de cautare) comparatia este necesara in mai multe functii si atunci este preferabil ca adresa functiei de comparatie sa fie transmisa la initializarea colectiei si sa fie memorata alaturi de alte variabile ce definesc colectia de date. Exemplu:

typedef int (* fcmp) (Ptr,Ptr); // tip functie de comparare

typedef struct Vector;

// operatii cu tipul Vector

void initV (Vector & a, fcmp cmp)

int findV ( Vector a, Ptr p)

Generalitatea programelor C cu structuri de date vine in conflict cu simplitatea si usurinta de intelegere; de aceea exemplele care urmeaza sacrifica generalitatea in favoarea simplitatii, pentru ca scopul lor principal este acela de a ilustra algoritmi. Din acelasi motiv multe manuale folosesc un pseudo-cod pentru descrierea algoritmilor si nu un limbaj de programare.

Limbajul C permite o mare diversitate in exprimarea operatiilor asociate unor structuri de date, vizibila si in programele publicate.