Gegevensstructuren en algoritmen C ++

Gegevensstructuren en algoritmen C ++ - betekent het rangschikken of organiseren van de elementen op een bepaalde manier. Als we zeggen dat we elementen moeten rangschikken, kunnen die elementen in verschillende vormen worden georganiseerd. Sokken kunnen bijvoorbeeld op verschillende manieren worden gerangschikt. Je kunt het gewoon in je kast bewaren. Of je kunt het netjes opgevouwen houden. De beste manier is om ze te vouwen en in kleur te rangschikken. Dus voor het zoeken naar een bepaald paar sokken, is het derde arrangement perfect.

Op een vergelijkbare manier om sokken te organiseren, kunnen Gegevens ook op verschillende manieren of vormen worden georganiseerd. Deze verschillende manieren om gegevens te ordenen worden gegevensstructuur genoemd. Laten we eens kijken naar een formele definitie van een gegevensstructuur en de basisprincipes van gegevensstructuren en algoritmen.

Gegevensstructuren en algoritmen C ++:

Het logische of wiskundige model van een bepaalde gegevensorganisatie.

OF

Het is een bepaalde manier om gegevens op een computer te ordenen zodat ze kunnen worden gebruikt.

Net als sokken; verschillende organisatie van lijst datastructuren en algoritmen C ++ beschikbaar is -

  1. reeks
  2. Gekoppelde lijst
  3. stack
  4. Wachtrij
  5. Boom
  6. diagram
  7. Hash-tafel
  8. Hoop
  9. archief
  10. tabellen

Deze gegevensstructuren en algoritmen C ++ zijn erg belangrijk tijdens het programmeren. Een goede programmeur legt altijd de nadruk op datastructuur in plaats van code. Elke programmeertaal werkt op verschillende datastructuren en algoritmen in C ++. Gegevensstructuren die beschikbaar zijn in C ++ zijn als volgt.

  1. reeks
  2. Gekoppelde lijst
  3. stack
  4. Wachtrij
  5. Boom
  6. diagram
  7. Hash-tafel
  8. Hoop

Laten we dit één voor één bespreken:

# 1 Array

Array is een eenvoudigste type gegevensstructuren en algoritmen C ++. De array is gedefinieerd als een opeenvolgende verzameling gegevenselementen van hetzelfde formaat. Bijvoorbeeld a0 = 12, a1 = 21, a2 = 14, a3 = 15 … We kunnen een eendimensionale array voorstellen zoals weergegeven in de afbeelding:

Waar

0, 1, 2, 3… ..n wordt subscript of index genoemd

a (1), a (2), … a (n) wordt subscriptvariabele genoemd

Het kan 1-dimensionaal, 2-dimensionaal, 3-dimensionaal enzovoort zijn, multidimensionaal.

In geheugenrij opgeslagen in aaneengesloten geheugenlocaties.

Het laagste adres komt overeen met het eerste element

Het hoogste adres komt overeen met het laatste element

We kunnen 1-D (1-Dimensional) array in C ++ als volgt declareren

dataType arrayName (arraySize);

Bijv. Int num (5);

Array initialiseren in C ++

aantal = (23, 10, 12, 3, 6);

We kunnen aangifte en initialisatie als volgt combineren in een enkele instructie.

int num = (23, 10, 12, 3, 6);

Als we de grootte van een array dynamisch willen toewijzen, moeten we de volgende nieuwe operator gebruiken

int * a = nieuwe int (grootte);

Het nadeel van de array is het invoegen en verwijderen van elementen is traag, net als in de geordende array en de opslag met een vaste grootte.

# 2 Gekoppelde lijst

Lijst verwijst naar een lineaire verzameling items. Een gekoppelde lijst is een reeks verbonden knooppunten (gegevenselement) zoals weergegeven in figuur 3. Kopknooppunt verwijst naar het eerste knooppunt van de lijst en het laatste knooppunt verwijst naar NULL aangegeven doorÆ. Omdat elke knoop ten minste bevat.

  1. Een stukje gegevens (elk type)
  2. Aanwijzer naar het volgende knooppunt in de lijst

Gekoppelde lijst wordt in het geheugen weergegeven met behulp van twee arrays. De ene array slaat informatie op die informatie wordt genoemd die moet worden opgeslagen en de andere slaat het volgende aanwijzerveld op met de naam LINK, dat een adres is van het volgende knooppunt.

Een voordeel van een gekoppelde lijst ten opzichte van een array:

Zowel een array als een gekoppelde lijst zijn representaties van een lijst met items in het geheugen. Het belangrijke verschil is de manier waarop de items aan elkaar zijn gekoppeld. De belangrijkste beperking van de reeks is het invoegen van elementen in de reeks en het verwijderen van elementen uit de geordende reeks is moeilijk omdat de restelementen moeten worden verplaatst. Het invoegen en verwijderen van elementen uit een gekoppelde lijst is heel eenvoudig.

Opmerking: word een C ++ Developer
Leer programma's ontwerpen en aanpassen voor verschillende platforms. Software-applicaties coderen, testen, debuggen en implementeren. Ontwikkel vaardigheden om te zorgen dat applicaties soepel verlopen.

Typen gekoppelde lijsten zijn:

1. Afzonderlijk gekoppelde lijst : bevat slechts één gekoppeld veld met het adres van het volgende knooppunt in de lijst en opgeslagen informatie met informatie die moet worden opgeslagen.

2. Enkele circulaire gekoppelde lijst is slechts een enkele lijst, maar het laatste knooppunt van de lijst bevat het adres van het eerste knooppunt in plaats van null. Dat is de inhoud van de kop en het volgende veld van de laatste knoop is hetzelfde.

3. De dubbel gekoppelde lijst bevat twee gekoppelde velden vorige en volgende. Een eerder gekoppeld veld dat een adres van het vorige knooppunt in de lijst bevat en het volgende gekoppelde veld bevat het adres van het volgende knooppunt in de lijst en opgeslagen informatie bevat de informatie om een ​​winkel te zijn.

4. Double Circular Linked List is een dubbel gekoppelde lijst, maar het volgende veld van het laatste knooppunt bevat het adres van het eerste knooppunt in plaats van null.

Aanbevolen cursussen

  • Cursus op VB.NET
  • Data Science Programming Training
  • Online ISTQB-cursus
  • Kali Linux-training

Implementatie van gekoppelde lijst in C ++ omvat het maken van een knooppunt, het verwijderen van een knooppunt uit de lijst, het invoegen van een nieuw gemaakt knooppunt in de lijst en het zoeken naar een knooppunt met een bepaalde sleutel.

De code voor het maken van het knooppunt wordt als volgt gegeven:

Het invoegen van een knooppunt in de lijst bestaat uit drie gevallen

1. Het invoegen van een knoop aan het begin betekent het invoegen van de nieuw gemaakte knoop als startknoop. Voor het invoegen van een knoop aan het begin, hebt u eerst een nieuwe knoop gemaakt en maakt u een nieuwe knoop naar de oude start en werkt u vervolgens de start bij naar een nieuwe knoop, zoals in onderstaande afbeelding wordt getoond:

Code voor het invoegen van een knoop aan het begin:

2. Het invoegen van een knoop aan de staart betekent het invoegen van de nieuw gemaakte knoop als de laatste knoop. Voor het invoegen van het knooppunt als staartknooppunt, moet u een nieuw knooppunt maken en het oude laatste knooppunt naar het nieuwe knooppunt wijzen en vervolgens de staart bijwerken naar het nieuwe knooppunt.

3. Het invoegen van een knooppunt op een bepaalde positie omvat het creëren van een nieuw tijdelijk knooppunt. Vervolgens moet u de invoegpositie van het nieuw gecreëerde knooppunt vinden.

Code voor het invoegen van de knoop op een gegeven positie:

Als u een knooppunt uit de lijst verwijdert, moet u een knooppunt uit een bestaande lijst verwijderen. Het verwijderen van het knooppunt uit de koppelingslijst is eenvoudig dan het invoegen van een knooppunt in de lijst. In C ++ wordt de code voor het verwijderen van het knooppunt als volgt gegeven:

Doorkruisen van een knooppunt met een bepaalde sleutel (waarde) uit een lijst, zoekt een knooppunt in de lijst waarvan de info overeenkomt met de sleutel van een gegeven knooppunt. De volgende C ++ code doorloopt een lijst. gegevensstructuren en algoritmen C ++

# 3 Stapel

Een stapel is een lijst met elementen waarin een element slechts aan één uiteinde kan worden ingevoegd of verwijderd, de bovenkant van de stapel genoemd. Overweeg het voorbeeld van een toren van Hanoi. Wanneer we hier een schijf moeten plaatsen, moeten we deze alleen vanaf de bovenkant plaatsen en op dezelfde manier wordt de schijf alleen vanaf de bovenkant verwijderd.

Stack gebruikt het LIFO-principe, wat betekent dat het in de volgorde Last in First Out werkt. Dat is het laatste element toegevoegd aan de stapel is het eerste element van verwijdering. Er zijn dus vier basisbewerkingen die op de stapel kunnen worden uitgevoerd:

  • Isempty: deze bewerking ziet of de stapel leeg is.
  • Push : met deze bewerking wordt een nieuw item aan de stapel toegevoegd.
  • Pop: met deze bewerking wordt een item verwijderd uit het laatst toegevoegde stapelitem.
  • Boven: deze bewerking retourneert het item dat het meest recent aan de stapel is toegevoegd.

De volgende afbeelding is een voorbeeld van de stapel waarbij het inbrengen in de stapel en het verwijderen uit een stapel van het artikel plaatsvindt vanaf de bovenkant van de stapel en nergens anders.

Stapel overloop

De voorwaarde die voortvloeit uit het proberen een element op een volledige stapel te duwen.

Stapel onderloop

De toestand die het gevolg is van een lege stapel proberen te maken.

Hier hebben we enkele push- en pop-bewerkingen op de stapel getoond. Stel dat de stapel eerst leeg is, dan hebben we F, A, M, R, N toegevoegd. Knal dan twee keer en druk op N, H, B, T, K, O, P.

Implementatie van Stack:

Het kan worden geïmplementeerd met behulp van een array of beide.

De volgende gegeven code laat zien hoe de stapel wordt geïmplementeerd in C ++ met Class. Hier hebben we een klasse gedefinieerd als een stapel waarin een array met de naam stick met dynamische grootte en twee hoofdfuncties push en pop is gemaakt.

Stack Overflow: When top> = size-1

Stack underflow: Wanneer top <0

Gerelateerde artikelen:-

Hier zijn enkele artikelen die gerelateerd zijn aan de datastructuren en algoritmen C ++ die u zullen helpen om meer details te krijgen over de Algorithms C ++ en de datastructuren en algoritmen die zo vriendelijk zijn om de link te volgen die hieronder wordt gegeven. als je de artikel datastructuren en algoritmen C ++ leuk vindt, geef ons dan je waardevolle commentaar.

  1. Cheatsheet voor C ++ programmeertaal
  2. Linux versus Ubuntu
  3. C ++ Interviewvragen die u moet weten
  4. Datastructuren en algoritmen Interview Vragen | Meest nuttig
  5. Het beste artikel voor algoritmen en cryptografie (voorbeelden)
  6. 8 geweldige vragen en antwoorden over het algoritme van het algoritme
  7. Verbazingwekkende gids over Kali Linux versus Ubuntu
  8. C ++ Vector vs Array: Wat zijn de beste functies

Categorie:

Software ontwikkeling