Proiect SDAA. Bibliotecă - TDA listă

Specificatia de definire a problemei

1.1. Enunt tema

BIBLIOTECA: TDA lista. Implementare cu tablouri, pointeri, cursori. Liste ordonate, neordonate sau exploatate prin reordonare; simplu si dublu inlantuite; cu si fara noduri fictive. Definire interfata utilizator. Implementare C. DEMO: Exemple de utilizare. Profil performanta.

1.2. Descrierea cerintelor

Realizarea proiectului necesita alcatuirea unei biblioteci care sa permita utilizatorului sa acceseze diversele tipuri de implementari cerute, într-un singur program. Acest lucru va fi indeplinit de interfata cu utilizatorul.

Mediul de dezvoltare folosit pentru realizarea aplicaţiei a fost Microsoft Visual C++ 5.0 Professional Edition, iar ca limbaj de programare am folosit C.

1.3. Specificarea functionala

Pentru a pune in evidenta profilul de performanta pentru functiile definite am generat un fisier text de 20000 de linii. Fiecare linie contine 2 numere reprezentand cheia, respectiv informatia unui nod.

Profilul de performanta a fost evidentiat la procedurile de creare, cautare si ordonare specifice fiecarui tip de lista.

Pentru lista simplu-inlantuita am prevazut posibilitatea crearii acesteia ordonate sau neordonate (insertie la inceputul listei, inaintea unui nod dat, dupa un nod dat sau la sfarsitul listei ).

De asemenea exista si optiunea de stergere a unui anumit nod dat prin cheie, aceasta realizandu-se pentru fiecare tip de lista.

- Lista simplu-inlantuita

//TDA Lista Simplu inlantuita implementata cu ajutorul tipului pointer

typedef struct n1_nod

{

int key;

int info;

struct n1_nod *next;

}TDASimplePointerList;

/* Operatori pentru Liste simplu inlantuite implementate cu ajutorul tipului pointer */

// Initializarea listei

void initSimplePointerList(TDASimplePointerList **list);

// Adaugare la inceputul listei

int addBeginSimplePointerList(TDASimplePointerList **list, int newkey, int newinfo);

// Adaugare inainte de nodul cu cheia "key"

int addBeforeSimplePointerList(TDASimplePointerList **list, int key, int newkey, int newinfo);

// Adaugare dupa nodul cu cheia "key"

int addAfterSimplePointerList(TDASimplePointerList **list, int key, int newkey, int newinfo);

// Adaugare la sfarsitul listei

int addEndSimplePointerList(TDASimplePointerList **list, int newkey, int newinfo);

// Cautare nod in lista, cu cheia "key"

int searchSimplePointerList(TDASimplePointerList *list, int key);

// Suprimarea nodului cu cheia "key" din lista

int removeSimplePointerList(TDASimplePointerList **list, int key);

// Afisarea listei

void printSimplePointerList(TDASimplePointerList *list);

// Crearea ordonata a listei (exploatata prin reordonare)

void createOrderedSimplePointerList(TDASimplePointerList **root,int key,int info);

// Crearea unui nod fictiv la inceputul listei

void creare_fictiv(TDASimplePointerList **root);

// Ordonarea listei cu metoda nodului fictiv

void ordonareSimplePointerList_fictiv(TDASimplePointerList *root);

// Ordonarea listei fara metoda nodului fictiv

void ordonareSimplePointerList(TDASimplePointerList **root);

- Lista dublu-inlantuita

/TDA Lista multiplu-inlantuita implementata cu ajutorul tipului pointer

typedef struct n2_nod

{

int key;

int info;

struct n2_nod *next;

struct n2_nod *prev;

}TDAMultiPointerList.