Datastruktur

Från Wikipedia, den fria encyklopedin
Hoppa till navigation Hoppa till sökning

Inom datavetenskap och mjukvaruteknik är en datastruktur ett objekt som används för att lagra och organisera data . Det är en struktur eftersom data är ordnade och länkade på ett specifikt sätt för att möjliggöra effektiv åtkomst till den och dess hantering.

Datastrukturer kännetecknas inte bara av de data de innehåller, utan framför allt av operationerna på denna data som möjliggör och implementerar åtkomst och hantering.

Förklaring

Specifikationen ( definitionen ) av datastrukturer utförs i allmänhet genom en exakt beskrivning ( specifikation ) av datahanteringen och de åtgärder som krävs för detta. Denna specifika specifikation definierar det allmänna beteendet för operationerna och abstraherar därmed från den specifika implementeringen av datastrukturen.

Om fokus övervägas till det konkreta genomförandet av operationerna används ofta en abstrakt datatyp istället för termen datastruktur. Övergången från datastrukturen till en abstrakt datatyp är inte klart definierad, utan beror enbart på perspektivet. Med tanke på de ofta förändrade minneskraven för många datastrukturer talar vi också om dynamiska datatyper som tekniskt är baserade på dynamisk minneshantering .

Förutom sin grundform har de flesta datastrukturer många specialiseringar som specifikt har specificerats för att fullgöra en viss uppgift. Exempelvis är B-träd, som en specialisering av träddatastrukturen, särskilt väl lämpade för databasimplementeringar .

Med många algoritmer beror resurskraven, dvs. både erforderlig körtid och lagringsutrymme, på användningen av lämpliga datastrukturer.

Grundläggande datastrukturer

Följande datastrukturer har vanligtvis utvecklats och optimerats för klassisk imperativ programmering . Andra programmeringsparadigm, såsom funktionell programmering, kan mycket väl kräva olika datastrukturer.

spela in

Datauppsättningar (även kallade 'tuples' eller engelska poster ) är de enklaste datastrukturerna. De innehåller vanligtvis värden som innehåller andra värden i ett fast antal och sekvens. Dataposter identifieras vanligtvis med ett eller flera av de element de innehåller, ofta kallade ett datafält .

(Data) -fält (även array)

Fältet ( även kallat array ) är den enklaste datastrukturen som används. Flera variabler av samma grund den datatyp sparas här. Åtkomst till de enskilda elementen är möjlig via ett index. Ur teknisk synvinkel motsvarar detta värdet som läggs till startadressen för gruppen i minnet för att erhålla objektets adress. De enda operationer som krävs är indexerad lagring och indexerad läsning , som direkt kan komma åt alla element i matrisen. I det endimensionella fallet kallas matrisen ofta som en vektor och i det tvådimensionella fallet som en tabell eller matris . Arrays är ingalunda begränsade till endast två dimensioner, men kan användas i valfritt antal dimensioner. På grund av deras enkelhet och grundläggande betydelse erbjuder de allra flesta programmeringsspråk en konkret implementering av denna datastruktur som en sammansatt datatypmatris i det grundläggande språkområdet.

Tilldelningstabell

Tilldelningstabellen (även associerande array eller nyckel-värde-par) är ett speciellt fall där lagrade data inte nås via ett numeriskt index, utan via en nyckel . Ett möjligt sätt att implementera en associativ array är med hashtabellen .

folkmassan

Ett annat specialfall är beloppet. Här kan du inte komma åt specifika värden med hjälp av ett index eller en nyckel. Det är oordning. Det motsvarar en tilldelningstabell med nycklar som bara kan visas en gång, men utan värden.

(Kedjelista

Den (länkade) listan är en datastruktur för dynamisk lagring av valfritt antal objekt. Varje listelement i en länkad lista innehåller som en specialfunktion en referens till nästa element, varigenom objektens totalitet blir en kedja av objekt. Den verksamhet som tillhör en lista är relativt ospecificerad. De används ofta i mer komplexa datastrukturer och deras element nås vanligtvis direkt istället för via operationer av effektivitetsskäl. Listorna som erbjuds i programbibliotek är vanligtvis mycket mer komplexa när det gäller deras underliggande datastruktur och representerar ofta inga riktiga listor alls, utan framstår som omvärlden som sådana. Listor är alltid linjära strukturer. Om föregångare och efterföljare är länkade åt två håll talar man om en dubbel länkad lista.

I en kö (engelska engelska kö) kan vara valfritt antal objekt som ska lagras, men de lagrade objekten kan bara läsas igen endast i samma ordning som de lagrades. Detta motsvarar FIFO -principen. För definitionen och därmed specifikationen för kön är det irrelevant vilka objekt som lagras i den. Åtgärderna tillhör åtminstone en kö

  • enqueue för att sätta ett objekt i kön och
  • dequeue för att läsa objektet som sparats först och ta bort det från kön.

En kö implementeras vanligtvis som en länkad lista, men den kan också använda en array internt; i detta fall är antalet element begränsat.

Stack minne

I ett stackminne ( engelsk stack) kan lagras objekt från valfritt antal, men de lagrade objekten kan läsas igen, bara i omvänd ordning. Detta motsvarar LIFO -principen. För definitionen och därmed specifikationen för stapeln är det irrelevant vilka objekt som lagras i den. Åtminstone operationerna tillhör en stapel

  • tryck för att lägga ett föremål på bunten och
  • pop för att läsa det senast sparade objektet igen och ta bort det från bunten.
  • ( toppa eller kika för att läsa toppobjektet utan att ta bort det)

Den översta operation är inte obligatoriskt, men ofta genomförs för att ersätta pop / push, eftersom det ofta är intressant att "test" takelementet. En stapel implementeras vanligtvis som en lista, men den kan också vara en vektor.

Deque

Deque (dubbelsidig kö) är en datastruktur som liknar kön eller stackminnet. Den kombinerar egenskaperna hos båda datastrukturerna. Skillnaden är att data kan läsas, infogas eller tas bort i båda ändarna.

Prioritetskö

En specialisering av kön är prioritetskön, som också kallas prioritetskön . Kallas Prioritetskö . Detta avviker från FIFO -principen. Genom att utföra enqueue -operationen, även kallad insert -operationen i det här fallet, sorterar objektet i prioritetskön enligt en given prioritet som varje objekt bär. Tömningsoperationen returnerar alltid objektet med högsta prioritet. Prioritetsköer implementeras mestadels med högar .

Graf

Som en datastruktur gör en graf det möjligt att övervinna länkens enkelriktning. Operationerna här är också att infoga , ta bort och hitta ett objekt. De mest kända representationerna av grafer i datorn är adjacensmatrisen , incidensmatrisen och adjacenslistan . Plana grafer kan mappas med hjälp av en halvkantig datastruktur.

träd

Träd är speciella former av grafer i grafteorin . Vanligtvis används endast ut-träd som datastruktur. Från roten kan flera objekt av samma typ länkas med varandra, så att den linjära strukturen i listan bryts upp och en gren sker. Eftersom träd är en av de mest använda datastrukturerna inom datavetenskap finns det många specialiseringar.

I binära träd, till exempel, är antalet barn högst två, och i höjdbalanserade träd gäller det också att höjden på vänster och höger delträd vid varje nod inte skiljer sig för mycket.

När det gäller ordnade träd, särskilt sökträd , lagras elementen i trädstrukturen på ett ordnat sätt så att element snabbt kan hittas i trädet. En ytterligare åtskillnad görs här mellan binära sökträd med AVL -träd (inklusive Fibonacci -träd ) som en balanserad version och B -träd samt en variant, B * -träden . Specialiseringar av B-träd är återigen 2-3-4-träd , som ofta implementeras som rödsvarta träd .

Geometriska trädstrukturer som R-trädet och dess varianter sorteras inte, utan "kapslas". Här söks endast de subtrees som överlappar med det begärda området.

Träd är flerdimensionella i sin struktur, men sammankopplingen av föremålen är ofta enkelriktad. Sammankopplingen av de lagrade föremålen börjar vid roten av trädet och därifrån i riktningen mot trädets noder.

Högen

Högen kombinerar datastrukturen för ett träd med operationerna i en prioritetskö. Förutom de minimalt nödvändiga operationerna som infoga , ta bort och extrahera Min , har högen också andra operationer som sammanfoga eller ändra nyckel . Beroende på prioritetsordningen i prioritetskön används en minhög eller en maxhög. Ytterligare specialiseringar av högen är den binära högen , binomialhögen och Fibonacci -högen . Högar byggs mestadels med hjälp av träd.

Treap

Treap kombinerar egenskaperna hos träd ( "träd" ) och högar.

Hashbord

Hashtabellen eller hashtabellen är en speciell indexstruktur där minnespositionen kan beräknas direkt. Hashtabeller konkurrerar med trädstrukturer, som till skillnad från hashtabeller kan reproducera alla indexvärden i en ordning, men kräver större administrativ ansträngning för att tillhandahålla indexet. När man använder en hashtabell för att söka igenom datamängder talar man också om hashmetoden . En distribuerad hashtabell kan användas för mycket stora mängder data.

Datalagrings lagrings- och datoransträngning

kirurgi Array Dynamisk
Array
Länkade
lista
Mer balanserad
träd
Hashbord
Infogning / radering
i början
Ej tillgängligt Θ ( n ) Θ (1) Θ ( logga n ) Θ ( 1 ) till Θ ( n ) [1]
Infogning / radering
i slutet
Ej tillgängligt Θ (1) Θ (1) [2]
Infogning / radering
i mitten
Ej tillgängligt Θ ( n ) sök +
Θ (1) [3]
söka Θ ( n ) Θ ( n ) Θ ( n ) Θ ( logga n ) Θ ( 1 ) till Θ ( n )
Ytterligare lagringsutrymme
motsatt array
0 0, Θ ( n ) [4] Θ ( n ) Θ ( n ) Θ ( n )
Tillgång till valfritt / slumpmässigt objekt Θ (1) Θ (1) Θ ( n ) Θ ( n ) Θ ( n )

Se även

litteratur

  • Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed: Grunderna i datastrukturer i C. International Thomson Publishing, Bonn 1994, ISBN 3-929821-00-1 .
  • Chris Okasaki: Rent funktionella datastrukturer . Cambridge University Press, Cambridge 1999, ISBN 0-521-66350-4
  • Thomas Ottmann, Peter Widmayer: Algoritmer och datastrukturer . 4: e upplagan. Spectrum Academic Publishing House, Heidelberg 2002, ISBN 3-8274-1029-0 .
  • Hanan Samet: Grunden för flerdimensionella och metriska datastrukturer. Elsevier, Amsterdam 2006, ISBN 0-12-369446-9
  • Niklaus Wirth : Algoritmer och datastrukturer i Pascal . 5: e upplagan. Teubner, Stuttgart 2000, ISBN 3-519-22250-7
  • Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders: Algoritmer och datastrukturer . Ed.: Springer. Springer, Berlin Heidelberg 2014, ISBN 978-3-642-05471-6 .

Individuella bevis

  1. ^ Dan Schmidt Perl Journal 1999: Building a Better Hash
  2. Antar att den länkade listan kommer ihåg en pekare för datapunktens slutposition, annars måste listans slut först bestämmas med den tid som krävs Θ ( n ).
  3. Gerald Kruse. CS 240 Föreläsningsanteckningar @ 1 @ 2 Mall: Toter Link / www.juniata.edu ( sidan är inte längre tillgänglig , sök i webbarkiv ) Info: Länken markerades automatiskt som defekt. Kontrollera länken enligt instruktionerna och ta sedan bort detta meddelande. : Länkade listor Plus: Komplexitet-avvägningar @ 1 @ 2 Mall: Toter Link / www.juniata.edu ( sidan är inte längre tillgänglig , sök i webbarkiv ) Info: Länken markerades automatiskt som defekt. Kontrollera länken enligt instruktionerna och ta sedan bort detta meddelande. . Juniata College. Våren 2008.
  4. Antar att en buffert är reserverad för expansioner.