Ez a szócikk az adatszerkezetek listáját tartalmazza. Az egyes adatszerkezetekre vonatkozó részletekért lásd az algoritmusokról és az egyes adatszerkezetekről szóló cikkeket.
Adattípusok
| Kategória | Típusok |
| Elemi adattípusok | - Egész szám (integer)
- Felsorolási típus (enumeration, enum)
- Fixpontos szám (fixed)
- Karakter (char)
- Karakterlánc (string)
- Lebegőpontos szám (real, float, double)
- Logikai (boolean)
- Referencia (pointer, reference)
|
| Összetett adattípusok | - Egyesítési típus (union)
- Rekord (record, struct)
- Tömb (array)
|
| Absztrakt adattípusok | - Asszociatív tömb (associative array, map)
- Kétvégű sor (deque)
- Fa (tree)
- Gráf (graph)
- Halmaz (set)
- Hash (hash)
- Prioritásos sor (priority queue)
- Sor (queue)
- Verem (stack)
|
Lineáris adatszerkezetek
| Kategória | Specifikus típusok |
| Tömbök | - Bittáblázat (bitboard)
- Bittérkép (bitmap)
- Dinamikus tömb (dynamic array)
- Magassági mező (heightmap)
- Mátrix (2 dimenziós tömb, matrix)
- Párhuzamos tömb (parallel array)
- Ritka tömb (sparse array)
- Ritka mátrix (sparse matrix)
- Tömb (array)
|
| Listák | - Láncolt lista (linked list)
- Kétszeresen láncolt lista (doubly linked list)
- Kifejtett láncolt lista (unrolled linked list)
- Önrendező lista (self-organizing list)
- Ugrásos lista (skip list)
- VLista (VList)
- XOR láncolt lista (xor linked list)
|
| Asszociatív tömbök | - Asszociatív tömb (associative array, map)
- Hash tábla (hash table)
|
Fák
| Kategória | Specifikus típusok |
| Bináris fák | - AA-fa
- AVL-fa
- Bináris fa (binary tree)
- Bináris keresőfa (binary search tree)
- Bűnbak fa (scapegoat tree)
- Intervallum fa (interval tree)
- Önkiegyensúlyozó bináris keresőfa (self-balancing binary search tree)
- Piros-fekete fa (red-black tree)
- Súlyozott fa (weight-balanced tree)
|
| B-fák | - 2-3 fa
- 2-3-4 fa
- B fa
- B+ fa
- B*-fa
|
| Kupacok | - 2-3 kupac
- Bináris kupac (binary heap)
- Binomiális kupac (binomial heap)
- D-kupac (D-ary heap)
- Fibonacci kupac (Fibonacci heap)
- Kupac (heap)
- Párosító kupac (pairing heap)
- Treap
|
| Prefix fák (trie) | - B-trie
- Ctrie
- Radix fa
- Prefix fa (trie)
- Suffix fa
|
| Többirányú fák | - (a,b)-fa
- És-vagy fa (And-or tree)
- Exponenciális fa (Exponential tree)
- Fenwick fa
- Fúziós fa (Fusion tree)
- Háromirányú keresőfa (Ternary search tree)
- SPQR-fa
- Van Emde Boas fa
|
| Térpartícionáló fák | - Adaptív Kd-fa
- BK-fa
- Implicit Kd-fa
- Intervallum fa
- Kd-fa
- M-fa
- Min/Max Kd-fa
- Octree
- Lineáris octree
- Quadtree
- R-fa
- R+ fa
- R*-fa
- Szegmens fa
- VP-fa
- X-fa
|
Gráfok
| Kategória | Specifikus típusok |
| Gráf adatszerkezetek | |
Hashek
| Kategória | Specifikus típusok |
| Hash | - Bloom szűrő
- Elosztott hash tábla
- Hash fa
- Hash lista
- Hash tábla
- Hash trie
- Prefix hash fa
|
Összehasonlítás
Az adatstruktúrák osztályozása jellegzetes tulajdonságaik alapján:
| Szerkezet | Rendezett | Egyedi | Cellák csomópontonként |
| Zsák (multihalmaz) | nem | nem | 1 |
| Halmaz | nem | igen | 1 |
| Lista | igen | nem | 1 |
| Asszociatív tömb | nem | igen | 2 |
A rendezett nem jelenti, hogy az adatok csoportosítva vannak, csak azt, hogy megőrzik a beviteli sorrendjüket. Más struktúrák, mint például a linkelt lista és a verem nem határozható meg ilyen módon, mivel specifikus műveletek tartoznak hozzájuk.
Fordítás
- Ez a szócikk részben vagy egészben a List of data structures című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Források
- Lecture Notes -- Data Structures (Stony Brook University - Department of Computer Science) (angolul)
- Adatstruktúrák a C++ dokumentációban (angolul)
- Algoritmusok és adatszerkezetek (angolul)
- Introduction to data structures (MSDN) (angolul)
- Dictionary of Algorithms and Data Structures
|
|---|
| Típusok | Collection • Container |
|---|
| Absztrakt adattípusok | - Asszociatív tömb (associative array, map)
- Kétvégű sor (deque)
- Fa (tree)
- Gráf (graph)
- Halmaz (set)
- Hash (hash)
- Prioritásos sor (priority queue)
- Sor (queue)
- Verem (stack)
|
|---|
| Tömbök | - Bittáblázat (bitboard)
- Bittérkép (bitmap)
- Dinamikus tömb (dynamic array)
- Magassági mező (heightmap)
- Mátrix (2 dimenziós tömb, matrix)
- Párhuzamos tömb (parallel array)
- Ritka tömb (sparse array)
- Ritka mátrix (sparse matrix)
- Tömb (array)
|
|---|
| Láncolt adatszerkezetek | - Láncolt lista (linked list)
- Kétszeresen láncolt lista (doubly linked list)
- Kifejtett láncolt lista (unrolled linked list)
- Önrendező lista (self-organizing list)
- Ugrásos lista (skip list)
- VLista (VList)
- XOR láncolt lista (xor linked list)
|
|---|
| Fa adatszerkezetek | | - AA-fa
- AVL-fa
- Bináris fa (binary tree)
- Bináris keresőfa (binary search tree)
- Bűnbak fa (scapegoat tree)
- Intervallum fa (interval tree)
- Önkiegyensúlyozó bináris keresőfa (self-balancing binary search tree)
- Piros-fekete fa (red-black tree)
- Súlyozott fa (weight-balanced tree)
|
|---|
Kupacok | - 2-3 kupac
- Bináris kupac (binary heap)
- Binomiális kupac (binomial heap)
- D-kupac (D-ary heap)
- Fibonacci kupac (Fibonacci heap)
- Kupac (heap)
- Párosító kupac (pairing heap)
- Treap
|
|---|
|
|---|
| Gráf adatszerkezetek | |
|---|
| Hash | - Bloom szűrő
- Elosztott hash tábla
- Hash fa
- Hash lista
- Hash-tábla
- Hash trie
- Prefix hash fa
|
|---|
Adatszerkezetek listája |
