2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T...

38
33. STRUCTURI DE TEXT UNIFORM 33.1 Text uniform Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T 1 , T 2 , ..., T n ce se parcurg într-o ordine prestabilită. Astfel, un text uniform conţine, pe lângă mesajul în sine, şi informaţii prin care se precizează modul în care acesta este structurat. Principalul domeniu de aplicabilitate al structurilor de text uniform este reprezentat de către aplicaţiile WEB. Se urmăreşte atât originalitatea construcţiilor din punct de vedere grafic, cât mai ales obţinerea unui nivel ridicat de atractivitate prin conţinut şi prin uşurinţa de satisfacere a cerinţelor tuturor celor are accesează resursele. Multe alte aplicaţii, din diverse domenii, sunt bazate pe text uniform organizat sub forma unor structuri de date. Structurile de bază pot fi agregate conducând la construcţii complexe, axate pe respectarea unor standarde şi prototipuri. Agregarea acestor structuri poate fi realizată atât pe orizontală cât şi în profunzime, pe verticală, în funcţie de exigenţele utilizatorilor. Principalele avantaje ale utilizării unor prototipuri sunt: - reducerea consumului de resurse; - creşterea gradului de reutilizare; - o mai bună distribuire a sarcinilor în cadrul echipei; - scurtarea duratei de realizare; - creşterea gradului de satisfacţie a utilizatorilor; - reducerea costurilor efective; - creşterea calităţii produsului finit atât în raport cu criteriile dezvoltatorului cât şi ale utilizatorilor. Într-o economie digitală reală, dezvoltarea aplicaţiilor prin respectarea unor standarde are menirea de a asigura caracterul deschis, intangibil şi mentenabil al acestora, oferindu-le caracter operaţional în raport cu exigenţele mereu crescânde ale utilizatorilor. 33.2 Structuri liniare de text uniform Utilizarea structurilor liniare asociate unui text uniform permite scurtarea duratei de introducere a fragmentelor de către mai mulţi operatori simultan şi includerea lor într-o construcţie uniformă, continuă. Structura liniară simplă În cadrul unei structuri liniare simple, textul uniform este fragmentat în T 1 , T 2 , ..., T n . Ordinea de parcurgere a fragmentelor este indicată de figura 33.1. Figura 33.1 Structură liniară simplă de text uniform T 1 T n T 222

Transcript of 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T...

Page 1: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

33. STRUCTURI DE TEXT UNIFORM

33.1 Text uniform Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ..., Tn ce se parcurg într-o ordine prestabilită. Astfel, un text uniform conţine, pe lângă mesajul în sine, şi informaţii prin care se precizează modul în care acesta este structurat. Principalul domeniu de aplicabilitate al structurilor de text uniform este reprezentat de către aplicaţiile WEB. Se urmăreşte atât originalitatea construcţiilor din punct de vedere grafic, cât mai ales obţinerea unui nivel ridicat de atractivitate prin conţinut şi prin uşurinţa de satisfacere a cerinţelor tuturor celor are accesează resursele. Multe alte aplicaţii, din diverse domenii, sunt bazate pe text uniform organizat sub forma unor structuri de date. Structurile de bază pot fi agregate conducând la construcţii complexe, axate pe respectarea unor standarde şi prototipuri. Agregarea acestor structuri poate fi realizată atât pe orizontală cât şi în profunzime, pe verticală, în funcţie de exigenţele utilizatorilor. Principalele avantaje ale utilizării unor prototipuri sunt:

- reducerea consumului de resurse; - creşterea gradului de reutilizare; - o mai bună distribuire a sarcinilor în cadrul echipei; - scurtarea duratei de realizare; - creşterea gradului de satisfacţie a utilizatorilor; - reducerea costurilor efective; - creşterea calităţii produsului finit atât în raport cu criteriile

dezvoltatorului cât şi ale utilizatorilor. Într-o economie digitală reală, dezvoltarea aplicaţiilor prin

respectarea unor standarde are menirea de a asigura caracterul deschis, intangibil şi mentenabil al acestora, oferindu-le caracter operaţional în raport cu exigenţele mereu crescânde ale utilizatorilor.

33.2 Structuri liniare de text uniform Utilizarea structurilor liniare asociate unui text uniform permite scurtarea duratei de introducere a fragmentelor de către mai mulţi operatori simultan şi includerea lor într-o construcţie uniformă, continuă.

Structura liniară simplă În cadrul unei structuri liniare simple, textul uniform este fragmentat în T1, T2, ..., Tn. Ordinea de parcurgere a fragmentelor este indicată de figura 33.1.

Figura 33.1 Structură liniară simplă de text uniform

T1 Tn T222

Page 2: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Crearea unei astfel de structuri se realizează prin adăugarea textelor individuale în ordinea dorită. De exemplu, considerăm textul uniform T ce este divizat în T1, T2, T3, ca în figura 33.2.

Starea de spirit este starea dogmatică, transformată în cuvinte inteligibile.

T1

Nici o pasăre nu va şti niciodată mai mult despre lume decât atunci când a spart coaja oului.

Textul T T2 (preluare din Marea

supravieţuire de Nichita Stănescu)

Aidoma ochiului, cuvântul vede lumina, dar, spre diferenţă de ochi, cuvântul o reţine în el.

T3

Figura 33.2 Exemplu de structură liniară simplă de text uniform Regăsirea unui text se realizează prin parcurgerea secvenţială a structurii liniare în ordinea stabilită prin intermediul legăturilor.

Inserarea unui nou fragment presupune intercalarea textului şi actualizarea legăturilor. În figura 33.3 se prezintă modul în care fragmentul T23 a fost adăugat la textul prezentat anterior.

Starea de spirit este starea dogmatică, transformată în cuvinte inteligibile.

T1

Nici o pasăre nu va şti niciodată mai mult despre lume decât atunci când a spart coaja oului.

T2

Textul T Cuvântul este cel mai apropiat de sine fără ca să facă parte din sine.

T23 (preluare din Marea supravieţuire de Nichita Stănescu)

Aidoma ochiului, cuvântul vede lumina, dar, spre diferenţă de ochi, cuvântul o reţine în el.

T3

Figura 33.3 Exemplu de structură liniară simplă de text uniform

Page 3: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Structura liniară actualizată este prezentată în figura 33.4.

Figura 33.4 Inserarea unui element în cadrul unei structuri liniare simple

de text uniform

Ştergerea unui fragment implică eliminarea textului urmată de actualizarea legăturilor. Pentru ştergerea unei componente Ti din structura liniară, se înlocuieşte referirea din componenta Ti-1 astfel încât legătura să se realizeze către componenta Ti+1, ca în figura 33.5.

Figura 33.5 Ştergerea componentei Ti din structura liniară

În continuare este prezentat un exemplu de clasă ce implementează

o structură liniară de text uniform.

// SimpleList.cpp #include "stdafx.h" #include "string.h" #include "conio.h" #include "iostream.h" class SimpleList { #define MAX_LEN 150 private: struct Text { short TextID; // cheie TEXT char TextFragment[MAX_LEN]; // fragment de TEXT Text *NextFragment; // elementul următor }; Text *Top; public: SimpleList(); void AppendElement(short TextID, char* TextFragment); Bool AddElement(short TextID, char* TextFragment, short PrevTextID);

T1 T2 T3

T23

T1 T2 Ti-1 Ti Ti+1

Page 4: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

bool ModifyElement(short TextID, char* TextFragment); bool RemoveElement(short TextID); void RemoveAllElements(); bool DisplayElement(short TextID); void DisplayAllElements(); ~SimpleList(); }; SimpleList::SimpleList() { Top = NULL; } SimpleList::~SimpleList() { RemoveAllElements(); } void SimpleList::AppendElement(short TextID, char* TextFragment) { Text *Fragment = new Text; // initializare fragment Fragment->TextID = TextID; strcpy(Fragment->TextFragment, TextFragment); Fragment->NextFragment = NULL; if (Top == NULL) { // lista este vidă Top = Fragment; } Else { // element Text *Element = new Text; // pozitionare pe ultimul element Element = Top; while (Element->NextFragment != NULL) { Element = Element->NextFragment; } // adaugarea fragmentului la sfarsitul listei Element->NextFragment = Fragment; } } Bool SimpleList::AddElement(short TextID, char* TextFragment, short PrevTextID) { bool ReturnValue = false; Text *Fragment = new Text; // initializare fragment Fragment->TextID = TextID; strcpy(Fragment->TextFragment, TextFragment); Fragment->NextFragment = NULL;

Page 5: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

if (Top == NULL) { // list este vida Top = Fragment; } else { // element Text *Element = new Text; // cautare ID anterior Element = Top; while (Element != NULL) { if (Element->TextID == PrevTextID) { // adaugare fragment la pozitia curenta Fragment->NextFragment = Element->NextFragment; Element->NextFragment = Fragment; ReturnValue = true; break; } Else { Element = Element->NextFragment; } } } return ReturnValue; } bool SimpleList::ModifyElement(short TextID, char* TextFragment) { bool ReturnValue = false; if (Top != NULL) { // lista este deja populata Text *Element = new Text; // cautarea unui anumit element Element = Top; while (Element != NULL) { if (Element->TextID == TextID) { // elementul a fost gasit strcpy(Element->TextFragment, TextFragment); ReturnValue = true; break; } else { Element = Element->NextFragment; } }

Page 6: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

} return ReturnValue; } bool SimpleList::DisplayElement(short TextID) { bool ReturnValue = false; if (Top != NULL) { // lista este deja populata Text *Element = new Text; // cautarea unui anumit element Element = Top; while (Element != NULL) { if (Element->TextID == TextID) { // elementul a fost gasit // afisarea detaliilor ReturnValue = true; break; } else { Element = Element->NextFragment; } } if (ReturnValue) { // elementul a fost gasit si va fi afisat cout << "Element gasit - ID: " << Element->TextID << ", Fragment: " << Element->TextFragment << endl; } else { // elementul nu a fost gasit cout << "Element negasit - ID: " << TextID << endl; } } return ReturnValue; } void SimpleList::DisplayAllElements() { if (Top != NULL) { // lista este deja populata Text *Element = new Text; // parcurgere elemente Element = Top; while (Element != NULL) { // afisare detalii

Page 7: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

cout << "ID " << Element->TextID << " - " << Element->TextFragment << endl; // salt la urmatorul fragment Element = Element->NextFragment; } } } bool SimpleList::RemoveElement(short TextID) { bool ReturnValue = false; if (Top != NULL) { // lista este deja populata Text *Element = new Text; Text *Previous = new Text; // cautarea unui anumit element Element = Top; Previous = NULL; while (Element != NULL) { if (Element->TextID == TextID) { // element gasit if (Previous == NULL) { Top = Element->NextFragment; } else { Previous->NextFragment = Element->NextFragment; } // stergerea lui delete Element; ReturnValue = true; break; } else { Previous = Element; Element = Element->NextFragment; } } } return ReturnValue; } void SimpleList::RemoveAllElements() { while (Top != NULL) { // lista nu este vida Text *Element = new Text;

Page 8: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

// stergere fragment curent Element = Top; Top = Top->NextFragment; delete Element; } } int main(int argc, char* argv[]) { SimpleList SList; bool ReturnCode; cout << "Inceputul programului ..." << endl << endl; // adaugarea unui numar de 3 noduri cout << "Adaugare 3 texte (T1, T2, T3)" << endl; SList.AppendElement(1, "Text 1 - Starea de spirit este starea dogmatica, transformata in cuvinte inteligibile."); SList.AppendElement(2, "Text 2 - Nici o pasare nu va sti niciodata mai mult despre lume decat atunci cand a spart coaja oului."); SList.AppendElement(3, "Text 3 - Aidoma ochiului, cuvantul vede lumina, dar, spre diferenta de ochi, cuvantul o retine in el."); // adaugare T23 intre T2 si T3 cout << "Adaugare T23 intre T2 si T3 - "; ReturnCode = SList.AddElement(23, "Text 23 - Cuvantul este cel mai apropiat de sine fara ca sa faca parte din sine.", 2); cout << "textul anterior " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // modificare T23 cout << "Modificare T23 - "; ReturnCode = SList.ModifyElement(23, "Text 23 ----- Cuvantul este cel mai apropiat de sine fara ca sa faca parte din sine."); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // modificare T34 cout << "Modificare T34 - "; ReturnCode = SList.ModifyElement(34, "Text 34 – revizuit"); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // adaugare T12 intre T1 si T2 cout << "Adaugare T12 intre T1 si T2" << endl; SList.AddElement(12, "Text 12", 1); // afisare T12 cout << "Afisare continut T12 - "; SList.DisplayElement(12); // afisare T34 cout << "Afisare continut T34 - "; SList.DisplayElement(34); // stergere T12 cout << "Stergere element T12 - ";

Page 9: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

ReturnCode = SList.RemoveElement(12); cout << "elementul " << (ReturnCode?"":"nu") << " a fost sters" << endl; // afisare T12 cout << "Afisare continut T12 - "; SList.DisplayElement(12); // afisarea tuturor fragmentelor textului uniform cout << "Afisarea tuturor fragmentelor" << endl; SList.DisplayAllElements(); cout << endl << "Sfarsitul programului ..." << endl; return 0; }

În situaţia în care există o legătură între ultimul element şi primul, se obţine o structură circulară, ca în figura 33.6.

Figura 33.6 Structură liniară circulară

Structura liniară circulară permite o parcurgere în ordinea T1, T2, …,

Tn, T1.

Structura liniară cu legături duble

Considerând textul uniform T ce este divizat în , T2, ..., Tn, structura liniară cu legături duble permite să se realizeze atât traversarea de la Ti spre Ti+1 cât şi de la Ti către Ti-1, ca în figura 33.7.

Figura 33.7 Structură liniară cu legături duble

O astfel de construcţie este caracteristică situaţiilor în care un text

uniform trebuie parcurs integral de la T1 la Tn şi, în acelaşi timp, sunt necesare şi reveniri de la Ti la Ti-1.

Structura liniară cu legături duble ce corespunde textului uniform din figura 33.2 este prezentată în figura 33.8.

T2 T1 Tn

T1 T2 Tn-1 T3 Tn

Page 10: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Figura 33.8 Structura liniară cu legături duble corespunzătoare textului

uniform T

Operaţiile ce pot fi efectuate asupra unei astfel de structuri sunt exemplificate prin intermediul următorului program. // DoubleList.cpp #include "stdafx.h" #include "string.h" #include "conio.h" #include "iostream.h" class DoubleList { #define MAX_LEN 150 #define TOP_END_DIRECTION 1 #define END_TOP_DIRECTION 2 private: struct Text { short TextID; // identificator TEXT char TextFragment[MAX_LEN]; // fragment de TEXT Text *NextFragment; // urmatorul element Text *PrevFragment; // elementul anterior }; Text *Top; Text *End; public: DoubleList(); void AppendElement(short TextID, char* TextFragment); bool AddElement(short TextID, char* TextFragment, short PrevTextID); bool ModifyElement(short TextID, char* TextFragment); bool RemoveElement(short TextID); void RemoveAllElements(); bool DisplayElement(short TextID); void DisplayAllElements(short Direction); ~DoubleList(); }; DoubleList::DoubleList() {

T1 T2 T3

Page 11: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Top = NULL; End = NULL; } DoubleList::~DoubleList() { RemoveAllElements(); } void DoubleList::AppendElement(short TextID, char* TextFragment) { Text *Fragment = new Text; // initializare fragment Fragment->TextID = TextID; strcpy(Fragment->TextFragment, TextFragment); Fragment->NextFragment = NULL; Fragment->PrevFragment = NULL; if (Top == NULL) { // lista este vida Top = Fragment; End = Fragment; } else { // elementul curent Text *Element = new Text; // pozitionare pe ultimul element Element = Top; while (Element->NextFragment != NULL) { Element = Element->NextFragment; } // adaugarea fragmentului la sfarsitul listei Element->NextFragment = Fragment; Fragment->PrevFragment = Element; End = Fragment; } } Bool DoubleList::AddElement(short TextID, char* TextFragment, short PrevTextID) { bool ReturnValue = false; Text *Fragment = new Text; // initializare fragment Fragment->TextID = TextID; strcpy(Fragment->TextFragment, TextFragment); Fragment->NextFragment = NULL; Fragment->PrevFragment = NULL; if (Top == NULL) { // lista este vida

Page 12: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Top = Fragment; End = Fragment; } else { // element Text *Element = new Text; // cautare ID anterior Element = Top; while (Element != NULL) { if (Element->TextID == PrevTextID) { // adaugare fragment la pozitia curenta // actualizare legatura catre elementul anterior if (Element->NextFragment != NULL) { Element->NextFragment->PrevFragment = Fragment; } Fragment->PrevFragment = Element; // actualizare legatura catre elementul urmator Fragment->NextFragment = Element->NextFragment; Element->NextFragment = Fragment; // actualizare capat lista, daca este cazul if (Fragment->NextFragment == NULL) { End = Fragment; } ReturnValue = true; break; } else { Element = Element->NextFragment; } } } return ReturnValue; } bool DoubleList::ModifyElement(short TextID, char* TextFragment) { bool ReturnValue = false; if (Top != NULL) { // lista este deja populata Text *Element = new Text; // cautarea unui anumit element Element = Top; while (Element != NULL) {

Page 13: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

if (Element->TextID == TextID) { // elementul a fost gasit strcpy(Element->TextFragment, TextFragment); ReturnValue = true; break; } else { Element = Element->NextFragment; } } } return ReturnValue; } bool DoubleList::DisplayElement(short TextID) { bool ReturnValue = false; if (Top != NULL) { // lista este deja populata Text *Element = new Text; // cautarea unui anumit element Element = Top; while (Element != NULL) { if (Element->TextID == TextID) { // elementul a fost gasit // afisare detalii ReturnValue = true; break; } else { Element = Element->NextFragment; } } if (ReturnValue) { // elementul a fost gasit, afisare detalii cout << "Element gasit - ID: " << Element->TextID << ", Fragment: " << Element->TextFragment << endl; } else { // elementul nu a fost gasit cout << "Element inexistent - ID: " << TextID << endl; } } return ReturnValue; }

Page 14: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

void DoubleList::DisplayAllElements(short Direction) { if (Top != NULL) { if (Direction == TOP_END_DIRECTION) { // lista este deja populata Text *Element = new Text; // parcurgere elemente Element = Top; While (Element != NULL) { // afisare detalii cout << "ID " << Element->TextID << " - " << Element->TextFragment << endl; // urmatorul fragment Element = Element->NextFragment; } } if (Direction == END_TOP_DIRECTION) { // lista este deja populata Text *Element = new Text; // parcurgere elemente Element = End; while (Element != NULL) { // afisare detalii cout << "ID " << Element->TextID << " - " << Element->TextFragment << endl; // fragmentul anterior Element = Element->PrevFragment; } } } } bool DoubleList::RemoveElement(short TextID) { bool ReturnValue = false; if (Top != NULL) { // lista este deja populata Text *Element = new Text; Text *Previous = new Text; Text *Next = new Text; // cautarea unui anumit element Element = Top; Previous = NULL; Next = NULL; while (Element != NULL) { if (Element->TextID == TextID)

Page 15: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

{ // elementul a fost // actualizare legaturi if (Element->PrevFragment != NULL) { Element->PrevFragment->NextFragment = Element->NextFragment; } else { Top=Element->NextFragment; } if (Element->NextFragment != NULL) { Element->NextFragment->PrevFragment = Element->PrevFragment; } else { End = Element->PrevFragment; } // stergerea lui delete Element; ReturnValue = true; break; } else { Previous = Element; Element = Element->NextFragment; } } } return ReturnValue; } void DoubleList::RemoveAllElements() { while (Top != NULL) { // lista nu este vida Text *Element = new Text; // stergere fragment curent Element = Top; Top = Top->NextFragment; delete Element; } } int main(int argc, char* argv[]) { DoubleList DList; bool ReturnCode;

Page 16: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

cout << "Inceputul programului ..." << endl << endl; // adaugarea unui numar de 3 noduri cout << "Adaugare 3 texte (T1, T2, T3)" << endl; DList.AppendElement(1, "Text 1 - Starea de spirit este starea dogmatica, transformata in cuvinte inteligibile."); DList.AppendElement(2, "Text 2 - Nici o pasare nu va sti niciodata mai mult despre lume decat atunci cand a spart coaja oului."); DList.AppendElement(3, "Text 3 - Aidoma ochiului, cuvantul vede lumina, dar, spre diferenta de ochi, cuvantul o retine in el."); // adaugare T23 intre T2 si T3 cout << "Adaugare T23 intre T2 si T3 - "; ReturnCode = DList.AddElement(23, "Text 23 - Cuvantul este cel mai apropiat de sine fara ca sa faca parte din sine.", 2); cout << "elementul anterior " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // modificare T23 cout << "Modificare T23 - "; ReturnCode = DList.ModifyElement(23, "Text 23 ----- Cuvantul este cel mai apropiat de sine fara ca sa faca parte din sine."); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // modificare T34 cout << "Modificare T34 - "; ReturnCode = DList.ModifyElement(34, "Text 34 – revizuit"); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // adaugare T12 intre T1 si T2 cout << "Adaugare T12 intre T1 si T2" << endl; DList.AddElement(12, "Text 12", 1); // afisare T12 cout << "Afisare continut T12 - "; DList.DisplayElement(12); // afisare T34 cout << "Afisare continut T34 - "; DList.DisplayElement(34); // stergere T12 cout << "Stergere element T12 - "; ReturnCode = DList.RemoveElement(12); cout << "elementul " << (ReturnCode?"":"nu") << " a fost sters" << endl; // afisare T12 cout << "Afisare continut T12 - "; DList.DisplayElement(12); // afisarea tuturor fragmentelor cout << "Afisarea tuturor fragmentelor" << endl; cout << "De la inceput catre sfarsit" << endl;

Page 17: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

DList.DisplayAllElements(TOP_END_DIRECTION); cout << "De la sfarsit catre inceput" << endl; DList.DisplayAllElements(END_TOP_DIRECTION); cout << endl << "Programul s-a terminat ..." << endl; return 0; }

Structurii liniare cu legături duble i se poate adăuga o conexiune

directă între primul şi ultimul element, obţinându-se astfel o structură liniară circulară, ca în figura 33.9.

Figura 33.9 Structura liniară circulară cu legături duble

Structura liniară cu legături multiple

Structura liniară cu legături multiple este o construcţie care conduce la referirea textelor uniforme după o regulă impusă. Structura liniară cu referirea universală a primului element are modelul prezentat în figura 33.10.

Figura 33.10 Structura liniară cu referirea universală a primului element

Acest tip de structură se utilizează atunci când utilizatorul întrerupe în

orice punct traversarea oricărui text şi doreşte reluarea de la început a procesului de traversare.

33.3 Structuri arborescente de text uniform În cadrul unei structuri arborescente, textele uniforme, prin relaţiile care se stabilesc între ele, se dispun pe niveluri astfel încât componentele de pe nivelul i+1 sunt considerate descendenţi în timp ce componentele de pe nivelul i sunt părinţii componentelor de pe nivelul i+1, ca în figura 33.11.

T1 T2 T3

T1 T2 Tn T3

Page 18: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Figura 33.11 Raportul descendent-părinte

Structura arborescentă cu arce orientate spre descendenţi Reprezintă tipul clasic de structură arborescentă în care toate arcele sunt orientate numai de la nodurile părinte către cele copil. Pentru a exemplifica acest tip de structură, vom considera textul uniform T aparţinând domeniului geometrie este compus din următoarele fragmente uniforme:

- T1 – geometria se ocupă cu reprezentările în plan şi în spaţiu a unor figuri şi corpuri;

- T2 – geometria plană se ocupă cu reprezentările în spaţiul bidimensional a figurilor;

- T3 – geometria în spaţiu studiază corpurile în spaţiu tridimensional;

- T4 – triunghiul; - T5 – dreptunghiul; - T6 – trapezul; - T7 – paralelipipedul; - T8 – conul; - T9 – piramida; - T10 – sfera. Acestor texte li se poate asocia structura arborescentă cu arce

orientate către descendenţi prezentată în figura 33.12.

Figura 33.12 Raportul descendent-părinte

Componentele de pe nivelul cel mai de jos nu au descendenţi şi se

numesc frunze.

Ti1

Ti+1 1 Ti+1 2

Ti2

Ti+1 3 Ti+1 4

Ti3

Ti+1 5

nivelul i componente părinte

nivelul i+1 Ti+1 6 componente descendenţi

T1

T2 T3

T4 T5 T6 T7 T8 T9 T10

Page 19: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Pentru exemplificarea unei astfel de structuri vom utiliza un arbore binar de căutare. Fiecare nod al unui astfel de arbore satisface următoarele proprietăţi:

- are cel mult doi descendenţi; - orice nod al subarborelui stâng are o valoare mai mică decât cea

a nodului curent; - orice nod al subarborelui drept are o valoare mai mare decât cea

a nodului curent. Operaţiile ce pot fi efectuate asupra unei astfel de structuri sunt

exemplificate prin intermediul următorului program. // BinaryTree.cpp #include "stdafx.h" #include "string.h" #include "conio.h" #include "iostream.h" class BinaryTree { #define MAX_LEN 150 #define PREORDER 1 #define INORDER 2 #define POSTORDER 3 public: struct Text { short TextID; // identificator TEXT char TextFragment[MAX_LEN]; // fragment de TEXT Text *LeftFragment; // subarbore stang Text *RightFragment; // subarbore drept }; Text *Root; public: BinaryTree(); bool AddElement(Text* &Tree, short TextID, char *TextFragment); bool ModifyElement(Text* &Tree, short TextID, char* TextFragment); bool RemoveElement(Text* &Tree, short TextID, bool ElementFound); bool DisplayElement(Text* Tree, short TextID, char *TextFragment); void DisplayAllElements(Text* Tree, short Order); void RemoveAllElements(Text* &Tree); ~BinaryTree(); }; BinaryTree::BinaryTree() { Root = NULL;

Page 20: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

} BinaryTree::~BinaryTree() { RemoveAllElements(Root); } bool BinaryTree::AddElement(Text* &Tree, short TextID, char *TextFragment) { bool ReturnValue = false; if (Tree == NULL) { // adaugare fragment Text *Fragment = new Text; // initializare fragment Fragment->TextID = TextID; strcpy(Fragment->TextFragment, TextFragment); Fragment->LeftFragment = NULL; Fragment->RightFragment = NULL; Tree = Fragment; ReturnValue = true; } else { // testeaza valoare element if (Tree->TextID > TextID) { // inserare in subarborele stang AddElement(Tree->LeftFragment, TextID, TextFragment); } else if (Tree->TextID < TextID) { // inserare in subarborele drept AddElement(Tree->RightFragment, TextID, TextFragment); } else { // fragmentul deja exista in arbore ReturnValue = false; } } return ReturnValue; } bool BinaryTree::ModifyElement(Text* &Tree, short TextID, char* TextFragment) { bool ElementFound = false; // cautare element // prin parcurgere arbore Text *Fragment = new Text;

Page 21: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Fragment = Tree; while ((Fragment != NULL) && (!ElementFound)) { if (Fragment->TextID == TextID) { // elementul a fost gasit strcpy(Fragment->TextFragment, TextFragment); ElementFound = true; } else if (TextID < Fragment->TextID) { Fragment = Fragment->LeftFragment; } else { Fragment = Fragment->RightFragment; } } return ElementFound; } bool BinaryTree::DisplayElement(Text* Tree, short TextID, char *TextFragment) { bool ElementFound = false; // cautare element // prin parcurgere arbore Text *Fragment = new Text; Fragment = Tree; while ((Fragment != NULL) && (!ElementFound)) { if (Fragment->TextID == TextID) { // elementul a fost gasit strcpy(TextFragment, Fragment->TextFragment); ElementFound = true; } else if (TextID < Fragment->TextID) { Fragment = Fragment->LeftFragment; } else { Fragment = Fragment->RightFragment; } } return ElementFound; }

Page 22: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

void BinaryTree::DisplayAllElements(Text* Tree, short Order) { if (Tree != NULL) { switch (Order) { case PREORDER: cout << "ID - " << Tree->TextID << ", fragment - " << Tree->TextFragment << endl; DisplayAllElements(Tree->LeftFragment, Order); DisplayAllElements(Tree->RightFragment, Order); break; case INORDER: DisplayAllElements(Tree->LeftFragment, Order); cout << "ID - " << Tree->TextID << ", fragment - " << Tree->TextFragment << endl; DisplayAllElements(Tree->RightFragment, Order); break; case POSTORDER: DisplayAllElements(Tree->LeftFragment, Order); DisplayAllElements(Tree->RightFragment, Order); cout << "ID - " << Tree->TextID << ", fragment - " << Tree->TextFragment << endl; break; } } } bool BinaryTree::RemoveElement(Text* &Tree, short TextID, bool ElementFound) { bool ReturnValue = true; if (!ElementFound) { // cautare element if (Tree == NULL) { // fragment inexistent ReturnValue = false; } else if (TextID < Tree->TextID) { // cautare in subarborele stang RemoveElement(Tree->LeftFragment, TextID, ElementFound); } else if (TextID > Tree->TextID) { // cautare in subarborele drept RemoveElement(Tree->RightFragment, TextID,ElementFound); } else { // fragmentul a fost gasit ElementFound = true;

Page 23: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

// suprimare RemoveElement(Tree, TextID, ElementFound); } } else { // verificare subarbori // subarborele stang inexistent if (Tree->LeftFragment == NULL) { // subarborele drept va inlocui nodul curent Text *Fragment = Tree; Tree = Tree->RightFragment; delete Fragment; } // subarborele drept inexistent else if (Tree->RightFragment == NULL) { // subarborele drept va inlocui nodul curent Text *Fragment = Tree; Tree = Tree->LeftFragment; delete Fragment; } // ambii subarbori sunt prezenti else { // cauta in subarborele stang // fragmentul cu ID-ul cel mai mare Text *Fragment = Tree->LeftFragment; while (Fragment->RightFragment != NULL) { Fragment = Fragment->RightFragment; } // actualizare legaturi Tree->TextID = Fragment->TextID; strcpy(Tree->TextFragment, Fragment->TextFragment); RemoveElement(Fragment, TextID, ElementFound); } } return ReturnValue; } void BinaryTree::RemoveAllElements(Text* &Tree) { // distrugerea elementelor // arborelui bonar if (Tree != NULL) { RemoveAllElements(Tree->LeftFragment); RemoveAllElements(Tree->RightFragment); delete Tree; }

Page 24: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Tree = NULL; } int main(int argc, char* argv[]) { BinaryTree SearchTree; bool ReturnCode; cout << "Inceputul programului ..." << endl << endl; // adaugare fragmente cout << "Adaugare fragmente - 5, 2, 7, 1, 9, 8, 3" << endl; SearchTree.AddElement(SearchTree.Root, 5, "Text 5 - Starea de spirit este starea dogmatica ..."); SearchTree.AddElement(SearchTree.Root, 2, "Text 2 - ... transformata in cuvinte inteligibile"); SearchTree.AddElement(SearchTree.Root, 7, "Text 7 - Nici o pasare nu va sti niciodata mai mult despre lume ..."); SearchTree.AddElement(SearchTree.Root, 1, "Text 1 - ... decat atunci cand a spart coaja oului"); SearchTree.AddElement(SearchTree.Root, 9, "Text 9 - Aidoma ochiului, cuvantul vede lumina ..."); SearchTree.AddElement(SearchTree.Root, 8, "Text 8 - ... dar, spre diferenta de ochi ..."); SearchTree.AddElement(SearchTree.Root, 3, "Text 3 - ... cuvantul o retine in el."); cout << "Adaugare fragmente - OK" << endl; // afisare fragmente – inordine cout << "Afisare fragmente" << endl; SearchTree.DisplayAllElements(SearchTree.Root, INORDER); // modificare fragment 3 cout << "Modificare fragment 3 - "; ReturnCode = SearchTree.ModifyElement(SearchTree.Root, 3, "Text 3 nou ----- Cuvantul este cel mai apropiat de sine fara ca sa faca parte din sine."); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // afisare continut fragment 3 char FragmentText[100] = {0,}; cout << "Afisare continut fragment 3 - "; SearchTree.DisplayElement(SearchTree.Root, 3, FragmentText); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit"; cout << " - " << FragmentText << endl; // modificare fragment 0 cout << "Modificare fragment 0 "; //ReturnCode = SearchTree.ModifyElement(SearchTree.Root, 0, "Text 0"); cout << "elementul " << (ReturnCode?"":"nu") << " a fost gasit" << endl; // stergere fragment 8 cout << "Stergere fragment 8 - ";

Page 25: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

ReturnCode = SearchTree.RemoveElement(SearchTree.Root, 8,false); cout << "elementul " << (ReturnCode?"":"nu") << " a fost sters" << endl; // afisarea tuturor fragmentelor cout << "Afisarea tuturor fragmentelor" << endl; cout << "Preordine" << endl; SearchTree.DisplayAllElements(SearchTree.Root, PREORDER); cout << "Inordine" << endl; SearchTree.DisplayAllElements(SearchTree.Root, INORDER); cout << "Postordine" << endl; SearchTree.DisplayAllElements(SearchTree.Root, POSTORDER); cout << endl << "Sfarsitul programului ..." << endl; return 0; }

Structura arborescentă cu referinţe de la frunze spre rădăcină

Se consideră o structură arborescentă având textul T0 numit rădăcină şi textele TF1, TF2, …, TFn numite frunze. La mulţimea arcelor de la părinte spre descendenţi se adaugă şi arcele de la frunze spre rădăcină, obţinându-se o construcţie asemănătoare celei din figura 33.13.

T0

T1 T2

Figura 33.13 Structura arborescentă pentru geometrie cu arce şi de la

frunze spre rădăcină

O astfel de construcţie este necesară situaţiei în care după traversarea unui traseu se impune revenirea la prima secvenţă de text a aplicaţiei.

Structura arborescentă cu arce duble

Structura arborescentă cu arce duble reprezintă o construcţie în cadrul căreia nodurile descendente au legături de la părinte spre ele şi există arce şi dinspre descendenţi către părinte, ca în figura 33.14.

TF1 TF2 TF3 TF4 TF5 TF6 TF7

Page 26: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

T1

T2 T3

T4 T7 T5 T6 T8 T9 T10

Figura 33.14 Structură arborescentă cu legături duble

Legăturile duble în structura arborescentă vizează pe de o parte relaţiile părinte-descendent, iar pe de altă parte descendenţii aparţinând aceluiaşi nivel, ca în figura 33.15.

T1

T2 T3

Figura 33.15 Legături între noduri de pe acelaşi nivel

Construcţia este caracteristică situaţiilor în care informaţiile aceluiaşi

nivel se utilizează pentru a soluţiona o problemă dată. În acelaşi mod se dezvoltă construcţiile arborescente cu legături

totale care includ: - referiri părinte-descendenţi; - referiri descendenţi spre rădăcină; - referiri duble pe orizontală; - referiri descendenţi-părinte. Această structură cu grad ridicat de complexitate este prezentată în

figura 33.16.

T4 T5 T6 T9 T7 T8 T9

Page 27: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

T1 T2 T3

Figura 33.16 Structură arborescentă cu legături multiple

Acest tip de construcţie este specific organizaţiilor în care accesul

trebuie făcut spre toate direcţiile pentru a satisface cerinţele de moment ale utilizatorilor care doresc fie să revină asupra unei secvenţe de text folosind referirea descendent-părinte, fie să treacă de la detalierea unui aspect, folosind referirea părinte-descendent, fie să treacă în revistă elemente cunoscute de pe acelaşi nivel, folosind referirea la stânga fie, respectiv, să continue cu traversarea elementelor cu acelaşi grad, în continuare, folosind referirea spre dreapta.

33.4 Agregarea structurilor Structurile prezentate anterior pot fi agregate în scopul obţinerii unor noi structuri mai complexe şi mai eficiente.

Liste de liste Există numeroase domenii în care descompunerea textelor se realizează după regulile liniarităţii:

- textul iniţial T se descompune într-o mulţime de texte T1, T2, …, Tn care se referă unul în continuarea celuilalt, de la T1 spre T2, de la T2 spre T3, etc.

- textul Ti se descompune la rândul său într-o mulţime de texte Ti1, Ti2, …, Ti ni, fiecare dintre acestea constituindu-se într-o secvenţă liniară.

Textul T şi textele T1, T2, …, Tn se constituie în secvenţa liniară dată în figura 33.17.

Figura 33.17 Structură liniară de nivel 1

T4 T5 T6 T7 T8 T9 T222

T1 T2 Tn

Page 28: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Textul Ti se descompune, de asemenea, în structura liniară dată în figura 33.18.

Figura 33.18 Structură liniară de nivel 2

Se obţine în final o structură liniară de structuri liniare, ca în figura

33.19.

Figura 33.19 Listă liniară de liste liniare de text

Pentru exemplificare, dacă se construieşte o galerie de pictori moderni P1, P2, …, Pn şi pentru fiecare pictor Pi se includ reproducerile Pi1, Pi2, …, Pi mi, rezultă o construcţie sub forma unei liste de liste. La nivelul unui element Pi de pe primul nivel se află:

- informaţii generale despre pictorul Pi şi portretul lui; - referirea spre lista de reproduceri ale tablourilor; - referirea spre elementul Pi+1.

Liste cu legături multiple

În cazul unei astfel de liste, pentru primul nivel există legături duble

iar pentru listele de pe nivelele următoare avem numai legături simple, ca în figura 33.20

Ti1 Ti2 Ti ni

T1 T2 Tn

T11 T21 Tn1

T12 T22 Tn2

T2m

Tn mn

T1 m1

Page 29: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Figura 33.20 Listă cu legături duble care referă liste cu legături simple

Dacă se doreşte revenirea la textul T1 din orice punct terminal al

listelor, se obţine structura a cărei reprezentare este dată în figura 33.21.

Figura 33.21 Listă de liste cu legături spre primul element

T1 T2 Tn

T11 T21 Tn1

T12 T22 Tn2

T1 m1

T2m

Tn mn

T1 T2 Tn

T11 T21 Tn1

T12 T22 Tn2

T2m

Tn mn

T1 m1

Page 30: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Construcţia oferă un grad de flexibilitate în trecerea de la un element la altul în cadru listei de pe primul nivel, precum şi reluarea de la început a aplicaţiei după traversarea listelor de pe nivelul al doilea.

Agregarea structurilor arborescente Agregarea a doi arbori, figura 33.22, are ca rezultat obţinerea unui nou arbore cu mai multe noduri şi cu cel puţin un nivel mai mult, figura 33.23. Nodul T0 reprezintă rădăcina noului arbore.

Figura 33.22 Structuri arborescente iniţiale

Figura 33.23 Structură arborescentă agregată

Este preferabil ca structurile T1 şi T2 să fie omogene, adică tipurile de

legături să fie corespunzătoare aceluiaşi mod de traversare. În cazul în care criteriul omogenităţii nu este satisfăcut, se

procedează la omogenizare prin aducerea structurii arborescente cu nivel mai scăzut către nivelul cel mai ridicat al structurii arborescente.

De exemplu, dacă se consideră structura arborescentă dată în figura 33.24 şi structura arborescentă cu legături multiple din figura 33.25, prin omogenizare se obţine o structură cu nivelul de agregare maxim în raport cu structura arborescentă cu legături multiple.

T11

T111 T112

T1

T12

T121 T122 T123

T21

T211

T2

T22

T212 T221 T222

T0

T1 T2

Page 31: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

T1

T11

T12

Figura 33.24 Structură arborescentă simplă

Figura 33.25 Structură arborescentă cu legături multiple

Mai întâi, structura arborescentă din figura 33.24 se transformă în structură cu legături multiple, ca în figura 33.26.

Figura 33.26 Structură arborescentă transformată având legături multiple

Agregarea celor două structuri omogene are rolul de a conduce la o

nouă structură în care legăturile dinspre elementele T1 şi T2 sunt deplasate spre elementul T0, ca în figura 33.27.

T21

T231 T232

T2

T22 T23

T1

T11 T12

Page 32: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Figura 33.27 Structură arborescentă agregată cu legături multiple

În toate cazurile se impune ca în faza de proiectare să se obţină construcţii omogene în ceea ce priveşte numărul de legături şi modul de traversare.

33.4 Complexitatea structurilor de text uniform

Complexitatea ciclomatică Se consideră un text uniform căruia i se asociază un graf cu arce orientate în care nodurile corespund fragmentelor şi arcele indică modul de referire a acestora.

Graful G(NO,AR) este definit prin - NO – mulţimea nodurilor; - AR – mulţimea arcelor. Mulţimea NO a nodurilor conţine nn elemente iar mulţimea AR a

arcelor conţine na elemente. Complexitatea C în sens McCabe sau numărul ciclomatic al grafului, este dată de relaţia:

C = na – nn + 2 (33.1)

Unei structurii liniare de text uniform i se asociază graful din figura

33.28.

Figura 33.28 Structură liniară

T21

T231 T232

T2

T22 T23

T1

T11 T12

T0

X1 X2 Xnn

Page 33: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Graful are nodurile X1, X2, …,Xnn şi arcele (X1, X2), (X2, X3), …, (Xnn-1, Xnn). Rezultă că structura liniară are nn noduri şi nn-1 arce, iar complexitatea C este egală cu:

C = (nn-1) – nn + 2 = 1 (33.2)

Putem astfel concluziona că orice structură liniară are complexitatea

egală cu unitatea. Dacă structura liniară este şi circulară atunci complexitatea asociată va fi egală cu 2. În cazul unei structuri de tip listă dublă, cum este cea prezentată în figura 33.29, numărul de arce este dublu faţă de lista simplă în timp ce numărul de noduri este acelaşi.

Figura 33.29 Structură liniară cu legături duble

Complexitatea unei astfel de structuri este dată de relaţia:

C = 2(nn - 1) –nn + 2 = nn (33.3)

Dacă structura de text uniform este un arbore binar perfect echilibrat organizat pe k niveluri, ca în figura 33.30, atunci:

nn = 2k+1 - 1 iar na = nn – 1 (33.4)

Complexitatea unei astfel de structuri este dată de relaţia:

C = (2k+1 - 2) – (2k+1 - 1) + 2 = 1 (33.5)

Figura 33.30 Structură arborescentă perfect echilibrată

X1 X2 X3 Xnn

X22 X23 X24

X11 X12

X0 nivelul 0

nivelul 1

nivelul 2 X21

Page 34: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Structurile de text uniform conţin numeroase referiri, cea mai complexă dintre ele corespunzând situaţiei în care fiecare nod le referă pe toate celelalte. Astfel, dacă graful are nn noduri, numărul de arce este egal cu nn

2 – 1. Rezultă că pentru o structură de text uniform cu nn noduri, complexitatea maximă este dată de relaţia

C = (nn

2 - nn) – nn + 2 = nn2 – 2nn + 2 (33.6)

Indicatori de complexitate

În scopul obţinerii unui indicator de complexitate normat pe intervalul [0, 1], se defineşte relaţia:

222max

nn

c nn

C

C

CI (33.7)

Indicatorul oferă o imagine mai bună în legătură cu efortul de dezvoltare a referinţelor. Tabelul următor prezintă valorile indicatorului pentru o parte dintre structurile prezentate în cadrul acestui capitol.

Tabelul nr. 33.1 Valorile indicatorului de complexitate normat pe [0, 1] Denumire structură C Ic

Error! Reference source not found. 1 1/Cmax

Error! Reference source not found. 2 2/Cmax Error! Reference source not found. nn nn/Cmax

Error! Reference source not found. nn+1 (nn+1)/Cmax

Error! Reference source not found. nn nn/Cmax

Error! Reference source not found. 1 1/Cmax

Error! Reference source not found. nn nn/Cmax

Complexitatea pe tipologie de structură revine la a considera o structură completă tip listă, listă dublă sau arbore şi a calcula complexitatea relativă a unei structuri particulare în raport cu structura completă.

Astfel, dacă notăm complexitatea structurii complete cu Cc iar pe cea a structurii particulare cu Cp, atunci complexitatea relativă poate fi exprimată cu ajutorul următorului indicator:

cp

cpr CC

CCI

,max

,min (33.8)

Pentru orice structură liniară, complexitatea structurii complete este

egală cu cea a structurii particulare şi din acest motiv indicatorul de complexitate relativă va avea o valoare egală cu 1.

În figura 33.31 este prezentată o listă dublă din care lipsesc două arce.

Page 35: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Figura 33.31 Listă dublă incompletă

Aşa cum am arătat anterior, complexitatea listei duble complete (Cc)

este egală cu nn. Pentru lista incompletă, complexitatea va fi calculată astfel:

Cp = 2(nn - 1) – 2 – nn + 2 = nn – 2 (33.9)

Valoarea indicatorului de complexitate relativă Ir devine:

n

n

nn

nn

cp

cpr n

n

nn

nn

CC

CCI

2

,2max

,2min

,max

,min

(33.10)

Considerăm un arbore binar incomplet organizat pe trei niveluri, ca în figura 33.32.

Figura 33.32 Arbore binar incomplet

Această structură se doreşte a fi comparată cu arborele binar complet

organizat pe trei niveluri, prezentat în figura 33.30. Complexităţile celor două construcţii sunt:

Cp = (nn – 1) – nn + 2 = 1 (33.11) Cc = (nn – 1) – nn + 2 = 1 (33.12)

iar valoarea indicatorului de complexitate relativă devine:

1

1

1

1,1max

1,1min

,max

,min

cp

cpr CC

CCI (33.13)

X1 X2 X3 X4 X5

X22

X11 X12

X0 nivelul 0

nivelul 1

nivelul 2 X21

Page 36: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Indicatorii de complexitate permit compararea aplicaţiilor ce utilizează

texte uniforme. Omogenitatea structurilor care compun o astfel de aplicaţie generează variaţii stabile şi la nivelul indicatorilor de complexitate.

Aspecte calitative ale structurilor de text uniform Studierea structurilor de date şi a modurilor de agregare conduce la obţinerea unor aplicaţii accesibile, cu multe regularităţi, uşor de utilizat şi de întreţinut. Atunci când se proiectează astfel de aplicaţi, nu trebuie să se piardă din vedere aspectele calitative ale structurilor de text uniform, cum ar fi omogenitatea şi simetria. O structură arborescentă este omogenă dacă frunzele se găsesc situate pe acelaşi nivel.

Simetria presupune existenţa unor structuri identice pentru subarborii corespunzători oricărui nod care nu este terminal. Două structuri sunt identice dacă au aceleaşi legături şi acelaşi număr de drumuri în arbore. Indicatorul numit grad de simetrie (S, 0 S 1) poate fi utilizat pentru a cuantifica măsura în care două structuri sunt asemănătoare. Astfel, dacă structurile sunt identice indicatorul va avea valoarea 1 iar dacă se compară două structuri total diferite atunci indicatorul va fi egal cu 0.

Auto-organizarea structurilor de text uniform

Un alt aspect foarte important ce este bine a fi urmărit atunci când se proiectează aplicaţii bazate pe structuri de text uniform este reprezentat de posibilitatea ca structurile să se auto-organizeze în mod dinamic în funcţie de frecvenţele de referire ale fragmentelor corespunzătoare.

Astfel, considerăm o aplicaţie web destinată comercializării de cravate ce implementează o structură arborescentă de text uniform, ca în figura 33.33. Pentru alegerea unei anumite cravate utilizatorul trebuie să parcurgă un drum complet în cadrul arborelui de la rădăcină şi până la unul dintre nodurile frunză.

Iniţial, la proiectarea aplicaţiei, s-a considerat că primul criteriu de care vor ţine seama utilizatorii atunci când vor alege o cravată este culoarea, apoi modelul şi in cele din urmă materialul.

Page 37: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

Figura 33.33 Organizarea iniţială a structurii arborescente

Dacă aplicaţia cuantifică frecvenţele de referire ale nodurilor, în

situaţia în care, după un anumit timp, se va observa că frecvenţa maximă este asociată materialului mătase, atunci structura arborescentă va fi reorganizată în mod dinamic astfel încât să reflecte preferinţele utilizatorilor, ca în figura 33.34.

Figura 33.34 Structură arborescentă reorganizată dinamic în funcţie de

frecvenţele de referire După ce structura arborescentă s-a auto-organizat în mod dinamic,

orice client care accesează aplicaţia respectivă va începe procesul de căutare a unei cravate cu alegerea materialului, urmată de alegerea culorii şi a modelului.

mătase poliester mătase poliester mătase poliester mătase poliester

dungi buline dungi buline

roşu galben

culoare

dungi buline dungi buline dungi buline dungi picăţele

roşu galben roşu galben

mătase poliester

material

Page 38: 2010-2011/ZZZZ-cartea...33. STRUCTURI DE TEXT UNIFORM . 33.1 Text uniform . Un text uniform T reprezintă o înşiruire de cuvinte care este divizată în fragmentele T1, T2, ...,

La elaborarea acestui tip de aplicaţie trebuie să se urmărească echilibrarea nivelului complexităţii pe tipologie de structură în aşa fel încât structura să fie cât mai omogenă din perspectiva referinţelor.