Menu

Inleiding tot gegevensstructuren in C ++

introduction data structures c

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Een inleidende zelfstudie over gegevensstructuren in C ++.

“Datastructuur kan worden gedefinieerd als een georganiseerde verzameling gegevens die een programma helpt om efficiënt en snel toegang te krijgen tot gegevens, zodat het hele programma op een efficiënte manier kan functioneren.​

We weten dat in de programmeerwereld data het centrum is en dat alles om data draait. We moeten alle gegevensbewerkingen, inclusief het opslaan, zoeken, sorteren, organiseren en openen van gegevens, efficiënt uitvoeren en alleen dan kan ons programma slagen.

​ Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.

Inleiding tot datastructuren in C ++ (1)

Wat je leert:

Overzicht

We moeten de meest efficiënte manier vinden om gegevens op te slaan die ons kan helpen dynamische oplossingen te bouwen. Datastructuur helpt ons bij het bouwen van dergelijke oplossingen.

Bij het ordenen of ordenen van gegevens in structuren, moeten we ervoor zorgen dat de opstelling een bijna realistisch object vertegenwoordigt. Ten tweede moet deze regeling eenvoudig genoeg zijn, zodat iedereen er gemakkelijk toegang toe heeft en deze op elk gewenst moment kan verwerken.

In deze serie zullen we in detail leren over zowel een basis als een geavanceerde datastructuur. We zullen ook uitgebreid leren over verschillende zoek- en sorteertechnieken die op datastructuren kunnen worden uitgevoerd.

Na het leren van deze tutorialserie, moet de lezer vertrouwd raken met elke datastructuur en de programmering ervan.

Laten we enkele termen doornemen die we gebruiken bij het omgaan met datastructuren:

Bijvoorbeeld,neem een ​​bepaalde student. Een student kan de volgende details hebben, zoals afgebeeld.

Voorbeeld - gegevensstructuur

  • Gegevens: Het is de elementaire waarde. In de bovenstaande afbeelding kan leerlingrolnummer gegevens zijn.
  • Groepsitem: Dit is het gegevensitem met meer dan één subitem. In de bovenstaande afbeelding heeft Student_name Voornaam en Achternaam.
  • Vermelding: Het is een verzameling gegevensitems. In het bovenstaande voorbeeld vormen gegevensitems zoals studentrolnummer, naam, klas, leeftijd, cijfer, enz. Samen een record.
  • Entiteit: Het is een klasse records. In het bovenstaande diagram is de student een entiteit.
  • Kenmerk of veld: Eigenschappen van een entiteit worden attributen genoemd en elk veld vertegenwoordigt een attribuut.
  • Het dossier: Een bestand is een verzameling records. In het bovenstaande voorbeeld kan een studententiteit duizenden records hebben. Een bestand zal dus al deze records bevatten.

De lezer dient zich bewust te zijn van al deze termen, aangezien we ze zo nu en dan gebruiken bij het gebruik van verschillende datastructuren.

Datastructuren zijn de belangrijkste bouwstenen van het programma en als programmeurs moeten we voorzichtig zijn met welke datastructuur we moeten gebruiken. De exacte datastructuur die moet worden gebruikt, is de moeilijkste beslissing die moet worden genomen als het gaat om programmeren.

Laten we de behoefte aan datastructuur in Programmeren bespreken.

Behoefte aan gegevensstructuur bij programmeren

Naarmate de hoeveelheid gegevens blijft groeien, worden de toepassingen steeds complexer, waardoor het moeilijk wordt voor de programmeur om zowel deze gegevens als de software te beheren.

Doorgaans kan de toepassing op elk moment met de volgende hindernissen worden geconfronteerd:

# 1) Grote hoeveelheden gegevens zoeken: Omdat er een grote hoeveelheid gegevens wordt verwerkt en opgeslagen, kan ons programma op elk moment nodig zijn om bepaalde gegevens te doorzoeken. Als de gegevens te groot en niet goed georganiseerd zijn, zal het veel tijd kosten om de vereiste gegevens te verkrijgen.

Wanneer we datastructuren gebruiken om gegevens op te slaan en te ordenen, wordt het ophalen van gegevens sneller en gemakkelijker.

# 2) Verwerkingssnelheid: Ongeorganiseerde gegevens kunnen resulteren in een lage verwerkingssnelheid, aangezien er veel tijd wordt verspild aan het ophalen en openen van gegevens.

Als we de data tijdens het opslaan goed ordenen in een datastructuur, dan verspillen we geen tijd aan activiteiten als ophalen en elke keer weer organiseren. In plaats daarvan kunnen we ons concentreren op de verwerking van gegevens om de gewenste output te produceren.

# 3) Meerdere gelijktijdige verzoeken: Veel applicaties moeten tegenwoordig gelijktijdig gegevens opvragen. Deze verzoeken moeten efficiënt worden verwerkt om de toepassingen soepel te laten verlopen.

Als onze gegevens willekeurig worden opgeslagen, kunnen we niet alle gelijktijdige verzoeken tegelijkertijd verwerken. Het is dus een verstandige beslissing om gegevens in een juiste gegevensstructuur te rangschikken om de doorlooptijd van gelijktijdige verzoeken te minimaliseren.

Classificatie van gegevensstructuur

Datastructuren die in C ++ worden gebruikt, kunnen als volgt worden geclassificeerd.

Classificatie van datastructuren

Een datastructuur is een manier om de data te ordenen. We kunnen dus datastructuren classificeren zoals getoond in primitieve of standaard datastructuren en niet-primitieve of door de gebruiker gedefinieerde datastructuren.

We hebben alle gegevenstypen gezien die worden ondersteund in C ++. Omdat dit ook een manier is om gegevens te ordenen, zeggen we dat het een standaard gegevensstructuur is.

De andere datastructuren zijn niet primitief en de gebruiker moet ze definiëren voordat ze in een programma kunnen worden gebruikt. Deze door de gebruiker gedefinieerde datastructuren worden verder geclassificeerd in lineaire en niet-lineaire datastructuren.

Lineaire gegevensstructuur

Bij lineaire datastructuren zijn al hun elementen lineair of sequentieel gerangschikt. Elk element in een lineaire datastructuur heeft een voorganger (vorig element) en een opvolger (volgend element)

Lineaire datastructuren worden verder onderverdeeld in statische en dynamische datastructuren. Statische datastructuren hebben meestal een vaste grootte en zodra hun grootte is aangegeven tijdens het compileren, kan deze niet worden gewijzigd. Dynamische datastructuren kunnen dynamisch van grootte veranderen en zichzelf aanpassen.

Het meest populaire voorbeeld van lineaire statische gegevensstructuur is een array.

Array

Een array is een opeenvolgende verzameling elementen van hetzelfde type. Elk element van de array is toegankelijk via zijn positie in de array, een index of subscript van de array genoemd. De naam van de array verwijst naar het eerste element in de array.

array

Het bovenstaande is een array ‘a’ van n elementen. De elementen zijn genummerd van 0 tot n-1. De grootte van de array (in dit geval n) wordt ook wel de dimensie van de array genoemd. Zoals weergegeven in de bovenstaande afbeelding, verwijst de naam van de array naar het eerste element van de array.

De array is de eenvoudigste datastructuur en is efficiënt omdat elementen rechtstreeks toegankelijk zijn via subscripts. Als we toegang willen krijgen tot het derde element in de array, hoeven we alleen maar een (2) te zeggen.

Maar het toevoegen of verwijderen van de array-elementen is moeilijk. Daarom gebruiken we arrays alleen in eenvoudige toepassingen of in toepassingen waar toevoeging / verwijdering van elementen niet vereist is.

Populaire lineaire dynamische gegevensstructuren zijn gekoppelde lijst, stapel en wachtrij.

Gekoppelde lijst

Een gekoppelde lijst is een verzameling knooppunten. Elk knooppunt bevat het data-element en een pointer naar het volgende knooppunt. Knooppunten kunnen dynamisch worden toegevoegd en verwijderd. Een gekoppelde lijst kan een enkelvoudig gekoppelde lijst zijn waarin elk knooppunt alleen een verwijzing naar het volgende element heeft. Voor het laatste element wordt de volgende pointer op nul gezet.

In de dubbelgekoppelde lijst heeft elk knooppunt twee verwijzingen: één naar het vorige knooppunt en de tweede naar het volgende knooppunt. Voor het eerste knooppunt is de vorige aanwijzer nul en voor het laatste knooppunt is de volgende aanwijzer nul.

Gekoppelde lijst

Zoals te zien is in de bovenstaande afbeelding, wordt het begin van de lijst de kop genoemd en het einde van de gekoppelde lijst de staart. Zoals hierboven weergegeven, heeft elk knooppunt een aanwijzer naar het volgende element. We kunnen eenvoudig elementen toevoegen of verwijderen door de aanwijzer naar het volgende knooppunt te verplaatsen.

Stapel

Stack is een lineaire datastructuur waarin de elementen alleen kunnen worden toegevoegd of verwijderd vanaf één uiteinde dat bekend staat als 'Top' van de stapel. Op deze manier vertoont stack LIFO-type geheugentoegang (Last In, First Out).

Stapel

Zoals hierboven getoond, worden elementen in de stapel altijd aan één uiteinde toegevoegd en ook aan hetzelfde uiteinde verwijderd. Dit wordt de 'bovenkant' van de stapel genoemd. Wanneer een element wordt toegevoegd, wordt het langs de stapel naar beneden geduwd en wordt de bovenkant van de stapel met één positie verhoogd.

Evenzo, wanneer een element wordt verwijderd, wordt de bovenkant van de stapel verlaagd. Als een stapel leeg is, wordt de bovenkant van de stapel ingesteld op -1. Er zijn twee hoofdbewerkingen 'Push' en 'Pop' die worden uitgevoerd op de stapel.

Wachtrij

De wachtrij is nog een andere lineaire datastructuur waarin de elementen worden toegevoegd aan het ene uiteinde genaamd 'achterkant' en verwijderd aan het andere uiteinde genaamd 'voorkant'. Wachtrij toont FIFO (First In, First Out) het type geheugentoegangsmethode.

Wachtrij

Het bovenstaande diagram toont een wachtrij met voor- en achterkant. Als de wachtrij leeg is, vallen de achter- en voorwijzer met elkaar samen.

Niet-lineaire gegevensstructuur

In niet-lineaire gegevensstructuren worden de gegevens niet opeenvolgend gerangschikt, maar op een niet-lineaire manier. Elementen zijn met elkaar verbonden in een niet-lineaire opstelling.

Niet-lineaire datastructuren zijn bomen en grafieken.

interviewvragen en antwoorden voor bedrijfsanalisten voor het domein van de bank

Bomen

Bomen zijn niet-lineaire datastructuren op meerdere niveaus met een hiërarchische relatie tussen de elementen. Elementen van de boom worden knooppunten genoemd.

Het knooppunt bovenaan wordt de wortel van de boom genoemd. De root kan een of meer onderliggende knooppunten hebben. De volgende knooppunten kunnen ook een of meer onderliggende knooppunten hebben. De knooppunten die geen onderliggende knooppunten hebben, worden bladknooppunten genoemd.

Bomen

In het bovenstaande diagram hebben we een boom met 6 knooppunten getoond. Van deze drie knooppunten zijn de bladknooppunten, een bovenste knooppunt is de wortel en de andere zijn onderliggende knooppunten. Afhankelijk van het aantal knooppunten, onderliggende knooppunten, etc. of de relatie tussen de knooppunten, hebben we verschillende soorten bomen.

Grafieken

De grafiek is een reeks knooppunten genaamd hoekpunten met elkaar verbonden door middel van de zogenaamde links Randen ​Grafieken kunnen een cyclus bevatten, d.w.z. hetzelfde hoekpunt kan zowel een beginpunt als het eindpunt van een bepaald pad zijn. Bomen kunnen nooit een cyclus hebben.

Grafieken

Het bovenstaande diagram is een ongerichte grafiek. We kunnen ook gerichte grafieken hebben waarbij we de randen weergeven met gerichte pijlen.

Bewerkingen op gegevensstructuur

Alle datastructuren voeren verschillende bewerkingen uit op de elementen ervan.

Deze zijn gemeenschappelijk voor alle datastructuren en worden als volgt weergegeven:

  • Zoeken: Deze bewerking wordt uitgevoerd om te zoeken naar een bepaald element of een sleutel. De meest voorkomende zoekalgoritmen zijn sequentieel / lineair zoeken en binair zoeken.
  • Sorteren: Bij het sorteren worden de elementen in een gegevensstructuur in een bepaalde volgorde oplopend of aflopend gerangschikt. Er zijn verschillende sorteeralgoritmen beschikbaar voor datastructuren. De meest populaire zijn Quicksort, Selectie sorteren, Samenvoegen sorteren, etc.
  • Invoeging: Invoegbewerking behandelt het toevoegen van een element aan de gegevensstructuur. Dit is de belangrijkste operatie en als gevolg van het toevoegen van een element verandert de indeling en moeten we ervoor zorgen dat de datastructuur intact blijft.
  • Schrapping: Een verwijderingsoperatie verwijdert een element uit de datastructuur. Dezelfde voorwaarden die in aanmerking moeten worden genomen voor het invoegen, moeten ook worden vervuld in het geval van het verwijderen.
  • Doorkruisen: We zeggen dat we een datastructuur doorkruisen wanneer we elk element in de structuur bezoeken. Oversteken is vereist om bepaalde specifieke bewerkingen op de datastructuur uit te voeren.

In onze volgende onderwerpen leren we eerst de verschillende zoek- en sorteertechnieken die op datastructuren kunnen worden uitgevoerd.

Voordelen van gegevensstructuur

  • Abstractie: Datastructuren worden vaak geïmplementeerd als abstracte datatypes. De gebruikers hebben alleen toegang tot de buitenste interface zonder zich zorgen te hoeven maken over de onderliggende implementatie. Datastructuur zorgt dus voor een abstractielaag.
  • Efficiëntie: Een juiste organisatie van gegevens resulteert in een efficiënte toegang tot gegevens, waardoor programma's efficiënter worden. Ten tweede kunnen we de juiste gegevensstructuur selecteren, afhankelijk van onze vereisten.
  • Herbruikbaarheid: We kunnen de datastructuren die we hebben ontworpen hergebruiken. Ze kunnen ook in een bibliotheek worden gecompileerd en naar de klant worden gedistribueerd.

Gevolgtrekking

Hiermee sluiten we deze tutorial over introductie in datastructuren af. In deze tutorial hebben we elk van de datastructuren in het kort geïntroduceerd.

In onze volgende tutorials zullen we meer onderzoeken over datastructuren en de verschillende zoek- en sorteertechnieken.

​ Klik hier voor de Absolute C ++ trainingsserie.

Aanbevolen literatuur

^