SDD - structură site web

1. Introducere

a.Obiectivul problemei

Proiectul constă în realizarea unui program care să implementeze structurile de lista, arbore binar de căutare şi lista de liste, pentru gestiunea site-urilor web.

b.Necesitatea

Aceasta aplicaţie, pe lângă gestiunea site-urilor web realizează si implementarea diferitelor operaţii pe structurile alese: adăugarea unui nou nod in lista si in arbore binar de căutare, căutarea unui element în arbore, ştergerea unei înregistrări din listă şi arbore. De asemenea mai realizează şi diferite tipuri de conversii, cum ar fi: din fişier în listă dublu înlănţuită şi din listă în arbore, din arbore în listă de liste, respectiv din arbore în fisier, şi din listă de liste in fişier.

c.Mijloacele de realizare

Aplicaţia a fost realizată in Microsoft Visual Studio 2008 (Microsoft Visual C++ 2008).

Datele de intrare, după ce acestea au fost în prealabil validate, s-au încărcat în fişierele text corespunzătoare structurii:SiteWeb, apoi aceste fişiere au fost convertite in structuri de tip listă dublu înlănţuită, arbore binar de căutare, respectiv listă de liste astfel încât resursele să fie alocate corespunzător si să permită prelucrările cât mai eficiente.

2. Structura programului

Programul realizează citirea din fişier a datelor despre site-urile web, introducerea lor într-o structură dinamică de date, de tip lista dublu înlănţuită,intr-un arbore binar de căutare si gruparea lor după un criteriu prestabilit(lista de liste). Afişarea datelor se face in 2 fisiere text, unul pentru afisarea informatiilor care rezulta din cautarea in arborele binar de cautare, iar celalalt pentru afisare informatiilor din lista de liste.

3. Structuri de date utilizate

Pentru rezolvarea aplicaţiei am folosit urmatoarele tipuri de structuri şi anume :

1) structuri simple de tip articol

2) arbori binari de cautare

3) liste simplu înlănţuite

4) liste dublu inlantuite

1 ) Articolele sunt constituite prin compunerea mai multor tipuri de date date fundamentale, rezultând ansambluri eterogene de elemente de bază, sau elemente agregate.

Articolul utilizat pentru a memora datele pentru fiecare site web, are următoarea structură:

struct Siteweb

{

char *tip;

int *nrVizitatori;

int *nrPagini;

int *id;

float *pret;

char *administrator;

};

Structura nodurilor din lista dublu înlănţuită este următoarea:

struct nod

{

Siteweb sw;

nod* st, *dr;

};

Aceasta structura este folosita si pentru implementarea arborelui binar de cautare.

Structura folosita pentru lista de liste , este o lista simplu inlantuita , cu urmatoare structura a nodurilor:

struct cls

{

nod* inf;

cls* leg;

char* tips;

};

2) Arborii binari de căutare sunt arbori binari în care nodurile sunt memorate ordonat în funcţie de o cheie. Toate nodurile din arbore au în subarborele stâng noduri care au chei mai mici şi în subarborele drept chei mai mari.

Arborii de căutare permit regăsirea rapidă a informaţiilor (O(log2 n)) atât timp cât

arborele este echilibrat. În cazul cel mai defavorabil, timpul de căutare este identic cu cel

al unei liste simplu înlănţuite.

Operaţiile de bază pe un arbore de căutare sunt următoarele:

Căutare - Se compara cheia cu nodul curent. Dacă este mai egală, am găsit nodul, dacă

este mai mică căutăm în subarborele stâng, altfel căutăm în subarborele drept.

Căutarea se opreşte când nodul a fost găsit sau s-a atins baza arborelui.

Adăugare - Se caută folosind algoritmul de căutare poziţia în arbore şi se alocă memoria

şi se face legătura cu nodul părinte.

Ştergere - Se caută nodul de şters şi se şterge nodul. Subarborele drept este avansat în

locul nodului şters, iar subarborele stâng este mutat ca fiu al celui mai mic

element din subarborele drept.