Un arbore încărcat este un set de caractere și are o structură care îi permite să fie utilizat pentru stocarea, căutarea, inserarea sau ștergerea șirurilor de caractere (cuvinte). Fiecare nod al unui astfel de arbore este un prefix de la cuvintele stabilite, adică o scrisoare a cuvântului. Fiecare cale de la rădăcină la frunză corespunde unui singur cuvânt din set. Pentru a evita coliziunile cuvintelor, este introdus un marcator de sfârșit special - acesta este simbolul $, care indică sfârșitul oricărui cuvânt.
Dăm mai jos un exemplu al unui astfel de copac pentru cuvintele grădină, san, sanie, suc, falcon, sor, magpie (Figura 5.2).
O astfel de structură este necesară pentru a organiza căutarea unui cuvânt dat între un set de cuvinte. Dacă ați căutat anterior un cuvânt între cuvinte consecutive (căutări exhaustive), acum cu această structură este suficient să treceți prin ramura de copac de la rădăcină la frunză pentru a verifica dacă există un astfel de cuvânt în setul dat (ramură și metodă limită).
Un arbore încărcat poate fi implementat în două moduri:
1) printr-o serie de pointeri la noduri de același tip;
2) prin intermediul listelor legate.
Cea mai simplă implementare a unui arbore încărcat este o serie de pointeri către noduri de același tip.
Nodurile unui arbore sunt aceleași matrice de indicatori de același tip. Structura este dinamică și poate avea orice grad de randament al nodului și înălțimea copacului. Indicii din matrice sunt elementele setului (Figura 5.3).
Un copac încărcat poate fi, de asemenea, utilizat pentru a implementa un "dicționar". În acest caz, nodurile arborelui încărcat sunt reprezentate de liste legate (Figura 5.4). Această reprezentare a "dicționarului" este mai eficientă decât structura sa obișnuită, implementată prin intermediul listelor legate.
Un fișier este o secvență de înregistrări și fiecare înregistrare este alcătuită din același set de câmpuri. Câmpurile pot avea o lungime fixă - atunci când numărul de octeți sau o variabilă este predeterminat. Fișierele cu înregistrări cu durată fixă sunt utilizate pe scară largă în sistemele de gestionare a bazelor de date pentru stocarea datelor cu structură complexă. Fișierele cu înregistrări cu lungime variabilă sunt utilizate pentru a stoca informații textuale (în Pascal astfel de fișiere nu sunt furnizate).
"Fișierul" în sine poate fi stocat ca o matrice sau o listă. Iar diferitele moduri de a implementa un "fișier" este o structură pentru accesarea rapidă a elementelor "fișier", adică Add-in pentru căutarea ușoară printre multe elemente "file".
Metode de accesare a elementelor "fișier":
1) printr-un indice descărcat;
2) prin arborele B.
Puteți crea un tip pentru acest mod de accesare a "fișierului":
Articole similare
Trimiteți-le prietenilor: