Colectare (programare)
Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită pe 28 august 2018; verificările necesită
9 modificări .
O colecție în programare este un obiect program care conține, într-un fel sau altul, un set de valori de unul sau mai multe tipuri și vă permite să accesați aceste valori.
O colecție permite ca valorile să fie scrise și recuperate. Scopul unei colecții este de a servi drept depozit de obiecte și de a oferi acces la acestea. De obicei, colecțiile sunt folosite pentru a stoca grupuri de obiecte de același tip care sunt supuse stereotipurilor. Pentru a accesa un anumit element al unei colecții pot fi folosite diferite metode, în funcție de organizarea logică a acesteia. O implementare POATE permite efectuarea de operațiuni individuale asupra colecțiilor în ansamblu. Prezența operațiunilor pe colecții în multe cazuri poate simplifica foarte mult programarea.
Colecții și containere
O colecție sau un container grupează un număr variabil (posibil zero) de elemente de date care au o anumită valoare comună pentru rezolvarea unei probleme. Sunt operați într-un fel. De obicei, elementele de date sunt de același tip sau (în limbile care acceptă moștenirea ) tipurile vor fi derivate dintr-un tip de strămoș comun. O colecție este un concept aplicat unor tipuri de date abstracte și nu prescrie o implementare specifică printr-o anumită structură de date, deși există adesea o alegere bine stabilită. Containerele în teoria tipurilor sunt abstracții care permit colecțiilor de structuri diferite, cum ar fi liste și arbori , să fie reprezentate într-un mod uniform. Un container ( unar ) este definit de indicii S și de o familie de tipuri la pozițiile P indexate de S: este dată o funcție de la tipurile de index la tipul de element. Containerele pot fi considerate ca clase canonice pentru colecții de diferite tipuri. Listele sunt indexate prin numere naturale (inclusiv zero ). Listele au un index maxim. Pentru arbori, structura arborelui poate fi exprimată în termeni de indici fără informații specifice despre conținutul nodurilor. Indicii elementelor de structură din memorie sunt izomorfi la căile de la rădăcina arborelui la nodurile acestuia .
Clasificare
După caracteristicile generale
- O colecție poate avea o dimensiune constantă sau în schimbare dinamică. În primul caz, în colecție poate fi scris doar un număr strict definit de obiecte, în al doilea, colecția permite plasarea a câte obiecte este necesar (desigur, în limitele specificate de restricții tehnice). În cele mai multe cazuri, când vorbim despre o colecție, ele înseamnă o colecție dinamică, adică o colecție de al doilea fel, deși, de exemplu, o matrice statică obișnuită este și o colecție.
- O colecție poate stoca doar obiecte de același tip sau tipuri diferite. În al doilea caz, se vorbește de o colecție eterogenă .
Conform logicii organizației
În funcție de modul în care este organizat logic accesul la datele de colectare, se disting următoarele tipuri principale:
- Vector - elementele colecției sunt ordonate, fiecare având propriul număr, numit index , prin care poate fi accesat în orice moment. De regulă, numerele întregi succesive sau valorile transmise acestora acționează ca indici. Un element al unui vector este accesat folosind numele vectorului și valoarea indexului. La adăugarea unui nou element, acesta este adăugat fie la sfârșitul vectorului, fie la poziția cu indexul dat. Eliminarea unui element dintr-un vector are ca rezultat un element gol.
- Matrice - Elementele au doi indici ordonați, fiecare dintre care este un număr întreg sau o valoare care poate fi convertită într-un număr întreg. Pentru a accesa un element, trebuie să specificați numele matricei și ambii indici. Un element nou poate fi adăugat doar la o poziție cu o pereche de indici dată. Ștergerea lasă un element gol.
- O matrice multidimensională este o dezvoltare logică a ideii de vector și matrice la un număr mai mare (în general arbitrar) de indici.
- Listă - elementele colecției sunt ordonate, elementele nu au identificatori. Listă este o colecție cu acces secvenţial. În orice moment, primul element al colecției este disponibil (de obicei, ultimul element este disponibil). Din orice element al colecției, puteți accesa următorul în ordine, astfel încât să puteți trece secvenţial de la primul element al listei la orice dorit. Este posibilă o implementare care permite o trecere inversă (la elementul anterior de la unul cunoscut). Noul element poate fi adăugat la începutul sau la sfârșitul listei. Atunci când un element este eliminat de la începutul listei, următorul element devine primul element, atunci când este eliminat de la sfârșit - cel anterior, de la mijloc - elementele precedente și ulterior devin, respectiv, anterior și următorul pentru alte.
- O stivă este o colecție care implementează principiul de stocare LIFO (last in, first out). Un singur element este întotdeauna disponibil pe stivă - cel care a fost adăugat ultimul. Un nou element poate fi adăugat la stivă, acesta va deveni cel actual. Elementul curent poate fi întotdeauna eliminat ("luat") din stivă, după care elementul care a fost adăugat imediat înainte de a deveni disponibil.
- O coadă este o colecție care implementează principiul de stocare FIFO (primul intrat, primul ieșit). Un singur element este întotdeauna disponibil în coadă - cel care a fost adăugat primul dintre cele disponibile. Când este adăugat un nou element, acesta intră în coadă. Elementul curent poate fi șters - apoi elementul adăugat primul dintre cele rămase devine cel curent.
- Un tablou asociativ (dicționar) este o colecție neordonată care stochează perechi cheie-valoare. Elementele sunt accesate prin cheie. Valorile de diferite tipuri pot fi folosite ca cheie, singura restricție este că tipul de cheie trebuie să permită compararea pentru egalitate. Orice pereche poate fi eliminată în orice moment. Numai o pereche (cu o cheie specifică) poate fi adăugată. Poate fi introdusă o interdicție privind duplicarea cheilor dintr-o colecție. Dacă nu există o astfel de restricție, atunci când accesați o cheie duplicată, pot fi returnate fie a n-a valoare găsită (unde n este fie constantă, fie determinată de formularul de interogare), fie toate valorile cu această cheie.
- Un set este o colecție neordonată care stochează un set de valori unice și acceptă operațiunile de adăugare, eliminare și definire a unei apariții pentru acestea. În general, operațiunile similare cu operațiile cu mulțimi matematice sunt acceptate pentru mulțimi: unire, intersecție, diferență de mulțimi simetrice și diferență de mulțimi asimetrice .
- Un multiset este o colecție neordonată, similară unui set, dar care permite colecției să aibă două sau mai multe valori identice în același timp.
Prin implementare
La nivel de implementare, o colecție poate fi una dintre următoarele structuri de date:
Operațiuni asupra colecțiilor
În funcție de tipul boolean al colecției și de implementare, pot fi suportate diferite operații asupra colecțiilor în general. În toate cazurile, operațiile pot fi efectuate numai pe perechi de colecții de același tip (și, dacă colecțiile nu sunt eterogene, cu același tip de elemente). De asemenea, pot fi acceptate următoarele operațiuni:
- Pentru toate tipurile de colecții - unire. Rezultatul unei astfel de operații este o colecție de același tip cu operanzii, care conține toate elementele conținute în operanzi.
- Pentru vectori și matrice care conțin valori numerice - operații matematice tipice pe obiecte cu același nume: adunare, scădere, înmulțire, transpunere.
- Pentru vectori, extrageți o serie de indici. Rezultatul unei astfel de operații va fi un vector de același tip, care conține doar acele elemente ale originalului care se încadrează într-un anumit interval specificat.
- Pentru vectori și liste, sortare.
- Pentru mulțimi, unire, intersecție, diferență și diferență simetrică.
Implementări notabile
- Glib este o bibliotecă care implementează majoritatea colecțiilor sub licența GNU LGPL .
- STL este o implementare sub forma unei biblioteci de șabloane pentru C++.
Vezi și
Note
Link -uri