Liste over datastrukturer - List of data structures
Dette er en liste over bemærkelsesværdige datastrukturer . For en bredere liste over termer, se liste over termer vedrørende algoritmer og datastrukturer . For sammenligning af driftstider for en delmængde af denne liste, se sammenligning af datastrukturer .
Datatyper
Primitive typer
- Boolsk , sand eller falsk.
- Karakter
-
Flydende tal, begrænsede præcisionstilnærmelser af reelle talværdier.
- Herunder blandt andet enkeltpræcision og dobbeltpræcision IEEE 754 floats
- Fixed-point tal
- Heltal , integrerede eller faste præcisionsværdier
- Reference (også kaldet en markør eller håndtag), en lille værdi, der henviser til et andet objekts adresse i hukommelsen, muligvis en meget større
- Opregnet type , et lille sæt unikke navngivne værdier
- Dato Tid , værdi der henviser til Dato og Tid
Sammensatte typer eller ikke-primitiv type
- Array (som et eksempel String, som er en række tegn)
- Rekord også kaldet struktur
- Forening ( mærket fagforening er en delmængde, også kaldet variant , variantrekord, diskrimineret fagforening eller usammenhængende fagforening)
Abstrakte datatyper
- Beholder
- Liste
- Tuple
- Tilknyttet array, kort
- Multimap
- Sæt
- Multiset (taske)
- Stak
- Kø (eksempel Prioritetskø )
- Dobbelt kø
- Graf (eksempelvis træ , bunke )
Nogle egenskaber ved abstrakte datatyper:
| Struktur | Bestille | Enestående |
|---|---|---|
| Liste | Ja | ingen |
| Associativ matrix | ingen | nøgler (indekser) |
| Sæt | ingen | Ja |
| Stak | Ja | ingen |
| Multimap | ingen | ingen |
| Multiset (taske) | ingen | ingen |
| Kø | Ja | ingen |
Ordre betyder, at indsættelsessekvensen tæller. Unikt betyder, at dubletter ikke er tilladt, baseret på nogle indbyggede eller alternativt brugerdefinerede regler for sammenligning af elementer.
Lineære datastrukturer
En datastruktur siges at være lineær, hvis dens elementer danner en sekvens.
Arrays
- Array
- Bit array
- Bitfelt
- Bitboard
- Bitmap
- Cirkulær buffer
- Kontrolbord
- Billede
- Dope vektor
- Dynamisk array
- Gap buffer
- Hashed array træ
- Opslagstabel
- Matrix
- Parallelt array
- Sorteret array
- Sparsom matrix
- Iliffe vektor
- Variabel længde array
Lister
- Dobbelt linket liste
- Array liste
- Linket liste
- Foreningsliste
- Selvorganiserende liste
- Spring liste over
- Afrullet linkliste
- VListe
- Conc-træ liste
- Xor linkliste
- Lynlås
- Dobbelt forbundet kantliste også kendt som halvkant
- Forskelliste
- Gratis liste
Træer
Binære træer
- AA træ
- AVL træ
- Binært søgetræ
- Binært træ
- Kartesisk træ
- Conc-træ liste
- Venstre-barn højre-søskende binært træ
- Bestil statistik træ
- Pagode
- Randomiseret binært søgetræ
- Rød -sort træ
- Reb
- Syndebodstræ
- Selvbalancerende binært søgetræ
- Spil træ
- T-træ
- Tangotræ
- Gevindet binært træ
- Øverste træ
- Treap
- WAVL træ
- Vægtbalanceret træ
B-træer
Bunker
- Bunke
- Binær bunke
- B-bunke
- Svag bunke
- Binomial bunke
- Fibonacci -bunke
- AF-bunke
- Leonardo -bunke
- 2–3 bunke
- Blød bunke
- Parringsbunke
- Venstrebunke
- Treap
- Beap
- Skæv bunke
- Ternær bunke
- D-ary bunke
- Brodal kø
Træer
I disse datastrukturer sammenligner hver træknude et stykke af nøgleværdier.
- Træ (datastruktur)
- Radix træ
- Suffix træ
- Suffix -array
- Komprimeret endelse array
- FM-indeks
- Generaliseret endelse træ
- B-træ
- Judy array
- X-hurtig trie
- Y-hurtig trie
- Merkle træ
- C træ
Multi-way træer
- Ternært træ
- K-ary træ
- Og – eller træ
- (a, b) -træ
- Link/hugget træ
- SPQR-træ
- Spaghetti stabel
- Usammensat datastruktur (datastruktur for EU-find)
- Fusionstræ
- Enfilade
- Eksponentielt træ
- Fenwick træ
- Van Emde Boas træ
- Rostræ
Rumopdelende træer
Disse er datastrukturer, der bruges til rumopdeling eller binær rumopdeling .
- Segment træ
- Intervaltræ
- Range træ
- Beholder
- Kd træ
- Implicit kd -træ
- Min/maks kd træ
- Afslappet kd -træ
- Adaptivt kd -træ
- Quadtree
- Oktree
- Lineær okter
- Z-ordre
- UB-træ
- R-træ
- R+ træ
- R* træ
- Hilbert R-træ
- X-træ
- Metrisk træ
- Dæk træ
- M-træ
- VP-træ
- BK-træ
- Afgrænsningsintervallshierarki
- Afgrænsende volumenhierarki
- BSP træ
- Undersøg hurtigt tilfældigt træ
Applikationsspecifikke træer
- Abstrakt syntaks træ
- Parsetræ
- Beslutningstræ
- Skiftende beslutningstræ
- Minimax træ
- Forventiminimax træ
- Fingertræ
- Udtrykstræ
- Log-struktureret fusionstræ
- Leksikografisk søgetræ
Hash-baserede strukturer
- Bloom filter
- Tælle -min skitse
- Distribueret hashtabel
- Dobbelt hashing
- Dynamisk perfekt hashbord
- Hash array kortlagt trie
- Hash -liste
- Hash bord
- Hashtræ
- Hash trie
- Koorde
- Præfiks hashtræ
- Rullende hash
- MinHash
- Kvotefilter
- Ctrie
Grafer
Mange graf baserede datastrukturer anvendes i datalogi og relaterede områder:
- Kurve
- Tilstødelsesliste
- Tilstødelsesmatrix
- Graf-struktureret stak
- Scenegraf
- Beslutningstræ
- Nul-undertrykt beslutningsdiagram
- And-inverter graf
- Rettet graf
- Rettet acyklisk graf
- Propositionelt styret acyklisk graf
- Multigraf
- Hypergraf
Andet
Se også
- Rent funktionel datastruktur
- Blockchain , en hashbaseret kædet datastruktur, der kan opretholde statens historie over tid
eksterne links
- Tommy Benchmarks Sammenligning af flere datastrukturer.