Samling (programmering)
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 28 augusti 2018; kontroller kräver
9 redigeringar .
En samling i programmering är ett programobjekt som på ett eller annat sätt innehåller en uppsättning värden av en eller olika typer, och låter dig komma åt dessa värden.
En samling gör att värden kan skrivas till och hämtas. Syftet med en samling är att fungera som ett förråd av objekt och ge tillgång till dem. Vanligtvis används samlingar för att lagra grupper av objekt av samma typ som är föremål för stereotyper. Olika metoder kan användas för att komma åt ett visst element i en samling, beroende på dess logiska organisation. En implementering KAN tillåta att enskilda operationer utförs på samlingar som helhet. Närvaron av operationer på samlingar kan i många fall förenkla programmeringen avsevärt.
Samlingar och behållare
En samling eller behållare grupperar ihop ett variabelt (eventuellt noll) antal dataelement som har något gemensamt värde för att lösa ett problem. De opereras på något sätt. Vanligtvis är dataelementen av samma typ, eller (på språk som stöder nedärvning ) kommer typerna att härledas från någon vanlig förfadertyp. En samling är ett koncept som tillämpas på abstrakta datatyper och föreskriver inte en specifik implementering genom en viss datastruktur, även om det ofta finns ett väletablerat val. Behållare i typteorin är abstraktioner som gör att samlingar av olika strukturer, såsom listor och träd , kan representeras på något enhetligt sätt. En ( unär ) behållare definieras av index S och en familj av typer vid positioner P indexerade med S: en funktion från indextyper till elementtyp ges. Behållare kan ses som kanoniska klasser för samlingar av olika typer. Listor indexeras genom naturliga tal (inklusive noll ). Listor har ett maximalt index. För träd kan trädets struktur uttryckas i termer av index utan specifik information om innehållet i noderna. Index av strukturelement i minnet är isomorfa till vägar från trädets rot till dess noder .
Klassificering
Enligt allmänna egenskaper
- En samling kan ha en konstant eller dynamiskt föränderlig storlek. I det första fallet kan endast ett strikt definierat antal objekt skrivas till samlingen, i det andra tillåter samlingen placering av så många objekt som behövs (naturligtvis inom de gränser som anges av tekniska begränsningar). I de flesta fall, när man talar om en samling, menar de en dynamisk samling, det vill säga en samling av det andra slaget, även om till exempel en vanlig statisk array också är en samling.
- En samling kan bara lagra objekt av samma typ eller olika typer. I det andra fallet talar man om en heterogen samling.
Enligt organisationens logik
Beroende på hur tillgången till insamlingsdata är logiskt organiserad, särskiljs följande huvudtyper:
- Vektor - elementen i samlingen är beställda, var och en har sitt eget nummer, kallat index , genom vilket det kan nås när som helst. Som regel fungerar successiva heltal eller värden som gjuts till dem som index. Ett element i en vektor nås med hjälp av vektornamnet och indexvärdet. När du lägger till ett nytt element läggs det till antingen i slutet av vektorn eller till positionen med det givna indexet. Att ta bort ett element från en vektor resulterar i ett tomt element.
- Matris - Elementen har två ordnade index, som vart och ett är ett heltal eller ett värde som kan konverteras till ett heltal. För att komma åt ett element måste du ange namnet på matrisen och båda indexen. Ett nytt element kan bara läggas till vid en position med ett givet indexpar. Radering lämnar ett tomt element.
- En flerdimensionell array är en logisk utveckling av idén om en vektor och en matris till ett större (i allmänhet godtyckligt) antal index.
- Lista - elementen i samlingen är ordnade, elementen har inga identifierare. Lista är en samling med sekventiell åtkomst. När som helst är det första elementet i samlingen tillgängligt (vanligtvis är det sista elementet också tillgängligt). Från valfritt element i samlingen kan du komma åt nästa i ordning, så att du sekventiellt kan ta dig från det första elementet i listan till vilket som helst. En implementering är möjlig som tillåter en omvänd passning (till föregående element från ett känt). Det nya elementet kan läggas till i början eller slutet av listan. När ett element tas bort från början av listan blir nästa element det första elementet, när det tas bort från slutet - det föregående, från mitten - blir det föregående och efterföljande elementet det föregående respektive efterföljande elementet för Övrig.
- En stack är en samling som implementerar lagringsprincipen LIFO (sist in, först ut). Endast ett element är alltid tillgängligt på stacken - det som lades till sist. Ett nytt element kan läggas till i stacken, det blir det nuvarande. Det aktuella elementet kan alltid tas bort ("tas") från stacken, varefter elementet som lades till omedelbart innan det blir tillgängligt.
- En kö är en samling som implementerar lagringsprincipen FIFO (först in, först ut). Endast ett element är alltid tillgängligt i kön - det som lades till det allra första av de tillgängliga. När ett nytt element läggs till kommer det in i kön. Det aktuella elementet kan tas bort - då blir det element som läggs till först av de återstående det aktuella.
- En associativ array (ordbok) är en oordnad samling som lagrar nyckel-värdepar. Element nås med nyckel. Värden av olika typer kan användas som nyckel, den enda begränsningen är att nyckeltypen måste tillåta jämförelse för jämlikhet. Vilket par som helst kan tas bort när som helst. Endast ett par (med en specifik nyckel) kan läggas till. Ett förbud mot kopiering av nycklar i en samling kan komma att införas. Om det inte finns någon sådan begränsning kan antingen det n:te hittade värdet (där n antingen är konstant eller bestäms av frågeformuläret) eller alla värden med denna nyckel returneras när du kommer åt en dubblettnyckel.
- En uppsättning är en oordnad samling som lagrar en uppsättning unika värden och stödjer operationerna för att lägga till, ta bort och definiera en händelse för dem. I allmänhet stöds operationer som liknar matematiska mängdoperationer för mängder: union, skärningspunkt, symmetrisk mängdskillnad och asymmetrisk mängdskillnad .
- En multiset är en oordnad samling, som liknar en uppsättning, men som tillåter samlingen att ha två eller flera identiska värden samtidigt.
Genom implementering
På implementeringsnivå kan en samling vara en av följande datastrukturer:
Operationer på samlingar
Beroende på den booleska typen av samlingen och på implementeringen kan olika operationer på samlingar i allmänhet stödjas. I alla fall kan operationer endast utföras på par av samlingar av samma typ (och, om samlingarna inte är heterogena, med samma typ av element). Följande operationer kan också stödjas:
- För alla typer av samlingar - förbund. Resultatet av en sådan operation är en samling av samma typ som operanderna, som innehåller alla element som finns i operanderna.
- För vektorer och matriser som innehåller numeriska värden - typiska matematiska operationer på objekt med samma namn: addition, subtraktion, multiplikation, transponering.
- För vektorer, extrahera ett antal index. Resultatet av en sådan operation kommer att vara en vektor av samma typ, som endast innehåller de element av originalet som faller inom ett visst specificerat område.
- För vektorer och listor, sortering.
- För uppsättningar, union, skärningspunkt, skillnad och symmetrisk skillnad.
Anmärkningsvärda implementeringar
- Glib är ett bibliotek som implementerar de flesta samlingar under GNU LGPL -licensen.
- STL är en implementering i form av ett mallbibliotek för C++.
Se även
Anteckningar
Länkar