Vad är en datastruktur?

En datastruktur är en metod för att organisera en uppsättning data. Strukturen definieras av hur data lagras och hur operationer, såsom datatillgång, infogning och radering, utförs på den lagrade datan. Datastrukturer är viktiga verktyg för programmerare, eftersom varje struktur har en uppsättning fördelar som gör det användbart för att lösa vissa typer av problem.

arrayer

Allmän uppfattning

En matris används för att lagra ett fast antal dataelement av samma datatyp. Ett enda minne är avsatt för att lagra hela matrisen. Arrayens dataelement lagras sedan sammanhängande inom det angivna blocket.

Konceptuellt är en matris bäst tänkt som en samling av objekt som är relaterade på något sätt. Till exempel en matris som lagrar nummer som representerar värdet på korten i din hand när du spelar poker. Matriser är den mest använda datastrukturen och ingår som sådan direkt i de flesta programmeringsspråk.

Ett exempel array, kallad siffror, som lagrar fem heltal. Lagrade data är färgade blått.

initiering

Liksom alla andra variabler bör matriser initieras innan de används i programmet. C ++ tillhandahåller olika metoder för att initialisera en matris. Varje arrayelement kan ställas in manuellt genom att slinga över varje arrayindex. Alternativt kan en initialiseringslista användas för att initialisera hela matrisen i en enda rad. Olika varianter av syntaxen för initialiseringslista är tillåtna, som visas i koden nedan. En tom lista kommer att initialisera matrisen för att innehålla nollor eller specifika värden för varje element kan anges.

 // Förklaring utan initialisering int test1 [4]; // test1 = [fyra okända värden] // Ställa in varje värde manuellt för (int i {0}; i <4; i ++) {test1 [i] = i + 1; } // test1 = [1, 2, 3, 4] // Använda en initialiseringslista int test2 [4] {}; // test2 = [0, 0, 0, 0] int test3 [4] {1, 2, 3, 4}; // test3 = [1, 2, 3, 4] int test4 [4] {1}; // test4 = [1, 0, 0, 0] int test5 [] {1, 2, 3, 4}; // test5 = [1, 2, 3, 4] 

Åtkomst till data

Arrayelement nås genom att begära ett arrayindex. I C ++ görs detta via abonnentoperatören, syntaxen är: "Array_name [int index]". Matriser är nollindexerade, det betyder att det första elementet ges indexet 0, det andra elementet ges indexet 1 och upp till det sista elementet ges ett index lika med 1 mindre än matrisens storlek.

Eftersom matrisens data lagras sammanhängande är det enkelt för datorn att hitta det begärda dataelementet. Arrayvariabeln lagrar matrisens startminneadress. Detta kan sedan flyttas framåt med det begärda indexet multiplicerat med storleken på den datatyp som är lagrad i arrayen och nå startadressen för det begärda elementet. Att lagra matrisen som ett minnesblock gör det också möjligt för datorn att implementera slumpmässig åtkomst av enskilda element, detta är en snabb operation, skalning som O (1)

Insättning och radering

Att infoga ett nytt element eller ta bort ett aktuellt arrayelement är inte möjligt på grund av att begränsningen i matrisen är en fast storlek. En ny matris (större eller mindre av ett element) måste skapas och relevanta element kopieras över från den gamla matrisen. Detta gör operationerna ineffektiva och bäst hanteras genom att använda en dynamisk datastruktur istället för att använda en matris.

Vidarebefordra matriser till en funktion

I C ++ passerar standardmetoden för att skicka parametrar till funktioner efter värde. Du kan då förvänta dig att genom att passera en matris skapas en kopia av hela matrisen. Detta är inte fallet, istället passas adressen för det första matriselementet efter värde. Det sägs att matrisen sönderfaller till en pekare (det kan till och med uttryckligen skickas som en pekare). Den förfallna pekaren vet inte längre att den är avsedd att peka på en matris och all information rörande matrisstorleken går förlorad. Det är därför du ser de flesta funktioner som också tar en separat variabel för matrisstorlek. Man måste också vara försiktig eftersom en icke-konstant pekare tillåter modifiering av matrisvariabler från funktionen.

En matris kan också skickas som referens men matrisstorleken måste anges. Detta kommer att skicka adressen till det första elementet med referens men det behåller fortfarande informationen som pekaren pekar på en matris. På grund av behovet av att ange matrisstorlek används denna metod sällan. I C ++ 11 introducerades en standardbiblioteksklass för att hantera frågan om pekarförfall.

Skriva ut en matris

 #include // Passera matrisadress efter värde (implicit pointer) ogiltig Skriv ut1 (const int arr [], int storlek) {std :: cout << "["; för (int i {0}; i <storlek; i ++) {std :: cout << arr [i]; if (i <storlek - 1) {std :: cout << ", "; }} std :: cout << "]"; } // Passera matrisadress efter värde (tydlig pekare) ogiltig Print2 (const int * arr, int storlek) {std :: cout << "["; för (int i {0}; i <storlek; i ++) {std :: cout << arr [i]; if (i <storlek - 1) {std :: cout << ", "; }} std :: cout << "]"; } // Passera matrisadress efter referens (storlek måste anges) void Print3 (const int (& arr) [5]) {// storlek på array bevaras och kan användas int storlek {sizeof (arr) / sizeof (arr [ 0])}; std :: cout << "["; för (int i {0}; i <storlek; i ++) {std :: cout << arr [i]; if (i <storlek - 1) {std :: cout << ", "; }} std :: cout << "]"; } int main () {int-nummer [5] {1, 2, 3, 4, 5}; Print1 (nummer); Print2 (nummer); Print3 (nummer); retur 0; } 

Flerdimensionella matriser

Multidimensionella matriser är matriser vars element också är matriser. Detta gör att allt komplexare strukturer skapas, men 2D-arrayer är de vanligaste. Vid åtkomst till en flerdimensionell matris utvärderas abonnentoperatörerna från vänster till höger.

En vanlig användning av en 2D-grupp är att representera en matris. 2D-arrayen kan tänkas vara en lagring av en samling rader (eller kolumner). Var och en av dessa rader är en 1D-serie med siffror.

Ett exempel på 2D-matris med heltal, som kan användas för att representera en 3x5-matris. Den valda visuella layouten visar tydligt hur den är analog med en matris. Datoren skulle dock lagra siffrorna som ett enda sammanhängande block av minne.

Initierar en 3x3 identitetsmatris

 const int storlek {3}; int identitet [storlek] [storlek]; för (int i {0}; i <storlek; i ++) {för (int j {0}; j <storlek; j ++) {if (i == j) {identitet [i] [j] = 1; } annat {identitet [i] [j] = 0; }}} 

Fördelar och nackdelar

+ Arrays är den mest effektiva datastrukturen för lagring av data. Endast data lagras och inget extra minne slösas bort.

+ Slumpmässig åtkomst ger snabb åtkomst till enskilda dataelement.

+ Multidimensionella matriser är användbara för att representera komplexa strukturer.

- Storleken på matrisen måste anges vid kompileringstidpunkten (innan programmet körs).

- Matrisstorleken är fast och kan inte ändras i storlek under körning. Detta kan leda till att matriser används som är stora, för att ge utrymme för potentiella nya element men slösa minne på tomma element.

användningsområden

Matriser är allestädes när det gäller programmering och kan användas för nästan alla problem. Men nyckeln till att använda datastrukturer är att välja den struktur vars egenskaper bäst passar problemet. Några exempel för matriser är:

  • För att lagra föremål placerade på brädet i ett spel. Kortet kommer alltid att ha en fast storlek och snabb åtkomst till ett specifikt kortutrymme kan behövas för att modifiera data lagrade där. Till exempel klickar användaren på ett tomt kortutrymme och matriselementet som representerar det måste ändras från tomt till fullt.
  • För att lagra en konstant värdetabell. Matriser är det bästa alternativet att lagra en konstant uppsättning värden som kommer att letas upp av programmet. Till exempel en matris med alfabetiska tecken, som tillåter konvertering av ett nummer till ett tecken genom att använda det som ett arrayindex.
  • Som diskuterats tidigare kan 2D-matriser lagra matriser.

Dynamiska matriser

C ++ STL (standardmallbibliotek) innehåller en implementering av en dynamisk matris, känd som en vektor. Vektorklassen tar bort kravet på en fast storlek genom att inkludera metoder för att ta bort befintliga element och lägga till nya element. Ett mycket enkelt kodexempel ingår nedan för att demonstrera dessa funktioner.

 #include #include int main () {std :: vektorfrukter {"äpple", "banan", "blåbär", "gurka"}; // frukter = ["äpple", "banan", "blåbär", "gurka"] frukter.pop_back (); // frukter = ["äpple", "banan", "blåbär"] fruits.push_back ("kiwi"); // frukter = ["äpple", "banan", "blåbär", "kiwi"] return 0; } 

Testa din kunskap

visa frågesportstatistik

Alternativa datastrukturer

  • Länkade listor
  • Staplar och köer
  • träd