Structuri de Date

L A B O R A T O R 10a

Arbori XML

1. Sa se defineasca un tip "Node" pentru un nod de arbore XML in reprezentareacu vector de pointeri la fii, vector extins cu 1 la fiecare adaugare a unui fiuCampuri: - val (char*): adresa tag sau text - nc (short): numar de fii - kids (Node**): adresa vector de pointeri la fii - parent (Node*) : adresa nod parinte Sa se scrie si sa se verifice urmatoarele functii: - Node* make ( char* v); // creare nod frunza cu valoarea v - void addChild (Node* p, Node* f); // adauga nodul f ca fiu al nodului p - void print (Node* r, int n);// afisare arbore cu rad. r, cu indentare n - int size (Node* r);// numar de noduri in arborele cu radacina r

Exemplu de program pentru verificarea functiilor anterioare:

int main() { Node* r, *p, *q; r= make (""); addChild (r, (p=make(""))); addChild (p, make("cafea")); addChild (p, q=make("")); addChild (q, make("Elite")); addChild (p, q=make("")); addChild (q, make("10")); addChild (r, (p=make(""))); addChild (p, make("ceai")); addChild (p, q=make("")); addChild (q, make("Lipton")); addChild (p, q=make("")); addChild (q, make("7")); print (r,0);// afisare arbore printf ("%d noduri\n", size(r)); getchar();}

2. Sa se scrie si sa se verifice o functie parser XML care construieste unarbore XML pe baza unui text ce contine un document XML: Node* parse (char* xml); // rezultat = radacina arbore xml

Algoritm folosit: creare nod radacina r cu primul tag crt=r// pozitie curenta in arbore repeta cat timp nu e sfarsit de text { extrage urmatorul simbol in token daca token este marcaj de inceput atunci { creare nod "nou" cu valoare marcaj adauga la crt pe nou crt=nou // coboara un nivel } daca token este marcaj de sfarsit atunci crt = parent(crt)// urca un nivel, la nod parinte daca token este text atunci { creare nod "nou" cu text adauga la crt pe nou // ramane pe acelasi nivel } } return r; Functia urmatoare extrage urmatorul atom XML dintr-un text XML; are ca rezultat adresa urmatoare din textul XML sau zero (NULL) la sfarsit de text.Atomii se depun la adresa t si pot fi deosebiti dupa primele caractere:orice marcaj incepe cu ''); tl=(p2+1)-p1; strncpy(t,p1,tl); t[tl]=0; return p2+1;}

In functia "main" se va citi un fisier XML, se va crea si afisa arborele XML, numarul de noduri si inaltimea arborelui. Exemplu de fisier:

cafea Elite 10 ceai Lipton 7

3. Sa se scrie o functie care verifica daca un sir s contine numai spatii:

int spaces(char* s); // 1= numai spatii, 0= alte caractere

Se va folosi functia "isspace" declarata in Sa se modifice functia "parse" pentru a nu crea noduri cu spatii albe si sa se afiseze numarul de noduri din arbore.

4. Sa se modifice functia "parse" (pentru construire arbore XML) astfel casa foloseasca varianta urmatoare a functiei "next":

char* next (char * & s) { // rezultat adresa token urmator char t[100], *p1, *p2; int tl;// tl=tag length p1=strchr(s,''); tl=(p2+1)-p1; strncpy(t,p1,tl); t[tl]=0; s= p2+1; } return strdup(t); // adresa diferita pentru fiecare token}

5. Sa se scrie o functie pentru serializarea continutului unui arbore XMLintr-un fisier XML cu cate o linie pentru fiecare marcaj sau text si cuindentare de 3 spatii la schimbare nivel. Sa se verifice prin serializareaarborelui creat la pct.1 (se adauga functiei "main" date apelul functiei deserializare). Serializarea este o varianta de afisare prefixata cu indentare, care adaugaun marcaj de terminare dupa afisarea subarborelui marcajului de inceput.