Meny

Introduksjon til datastrukturer i C ++

  • Hoved
  • Annen
  • Introduksjon til datastrukturer i C ++

introduction data structures c

Prøv Instrumentet Vårt For Å Eliminere Problemer

En innledende veiledning om datastrukturer i C ++.

”Datastruktur kan defineres som en organisert datainnsamling som hjelper et program til å få tilgang til data effektivt og raskt, slik at hele programmet kan fungere på en effektiv måte. “

Vi vet at i programmeringsverdenen er data sentrum og alt dreier seg om data. Vi må utføre alle dataoperasjoner, inkludert lagring, søk, sortering, organisering og tilgang til data effektivt, og bare da kan programmet vårt lykkes.

=> Se her for å utforske hele C ++ opplæringslisten.

Introduksjon til datastrukturer i C ++ (1)

Hva du vil lære:

Oversikt

Vi må finne den mest effektive måten å lagre data på som kan hjelpe oss med å bygge dynamiske løsninger. Datastruktur hjelper oss med å bygge slike løsninger.

Mens vi organiserer eller ordner data i strukturer, må vi sørge for at arrangementet representerer nesten et objekt fra den virkelige verden. For det andre bør denne ordningen være enkel nok til at alle enkelt kan få tilgang til den og behandle den når det er nødvendig.

I denne serien vil vi lære i detalj om grunnleggende så vel som en avansert datastruktur. Vi vil også lære i detalj om ulike søke- og sorteringsteknikker som kan utføres på datastrukturer.

Etter å ha lært denne opplæringsserien, bør leseren bli godt kjent med hver datastruktur og dens programmering.

La oss gå gjennom noen av begrepene vi bruker når vi arbeider med datastrukturer:

For eksempel,ta en bestemt student. En student kan ha følgende detaljer som vist på bildet.

Eksempel - Datastruktur

  • Data: Det er den grunnleggende verdien. I figuren ovenfor kan studentrullnr. Være data.
  • Gruppeartikkel: Dette er dataelementet som har mer enn ett underelement. I figuren ovenfor har Studentnavn fornavn og etternavn.
  • Ta opp: Det er en samling av dataelementer. I eksemplet ovenfor utgjør dataelementer som studentrull nr., Navn, klasse, alder, karakter osv. En post sammen.
  • Enhet: Det er en klasse av poster. I diagrammet ovenfor er studenten en enhet.
  • Attributt eller felt: Egenskaper til en enhet kalles attributter, og hvert felt representerer et attributt.
  • Fil: En fil er en samling poster. I eksemplet ovenfor kan en studentenhet ha tusenvis av poster. Dermed vil en fil inneholde alle disse postene.

Leseren bør være oppmerksom på alle disse begrepene når vi bruker dem nå og da når vi bruker forskjellige datastrukturer.

Datastrukturer er hovedbygningen i programmet, og som programmerere bør vi være forsiktige med hvilken datastruktur vi skal bruke. Den nøyaktige datastrukturen som skal brukes, er den tøffeste beslutningen å ta når det gjelder programmering.

La oss diskutere behovet for datastruktur i programmering.

Behov for datastruktur i programmering

Etter hvert som datamengden fortsetter å vokse, blir applikasjonene mer og mer komplekse, og det blir derfor vanskelig for programmereren å administrere disse dataene så vel som programvaren.

Vanligvis kan applikasjonen når som helst møte følgende hindringer:

# 1) Søke etter store mengder data: Med en stor mengde data som behandles og lagres, kan vårt program til enhver tid være pålagt å søke i bestemte data. Hvis dataene er for store og ikke er ordnet ordentlig, vil det ta mye tid å få de nødvendige dataene.

Når vi bruker datastrukturer til å lagre og organisere data, blir henting av data raskere og enklere.

# 2) Behandlingshastighet: Uorganiserte data kan føre til langsom prosesseringshastighet ettersom mye tid blir kastet bort i å hente og få tilgang til data.

Hvis vi organiserer dataene riktig i en datastruktur mens vi lagrer, vil vi ikke kaste bort tid på aktiviteter som å hente, organisere dem hver gang. I stedet kan vi konsentrere oss om prosessering av data for å produsere ønsket utdata.

# 3) Flere samtidige forespørsler: Mange applikasjoner i disse dager må sende en forespørsel til data samtidig. Disse forespørslene bør behandles effektivt for at søknadene skal kunne fungere greit.

Hvis dataene våre lagres bare tilfeldig, vil vi ikke kunne behandle alle samtidige forespørsler samtidig. Så det er en klok beslutning å ordne data i riktig datastruktur for å minimere samtidige forespørselers behandlingstid.

Datastrukturklassifisering

Datastrukturer som brukes i C ++ kan klassifiseres som følger.

Klassifisering av datastrukturer

En datastruktur er en måte å organisere dataene på. Så vi kan klassifisere datastrukturer som vist i primitive eller standard datastrukturer og ikke-primitive eller brukerdefinerte datastrukturer.

Vi har sett alle datatypene som støttes i C ++. Ettersom dette også er en måte å organisere data på, sier vi at det er en standard datastruktur.

De andre datastrukturene er ikke-primitive, og brukeren må definere dem før de brukes i et program. Disse brukerdefinerte datastrukturene klassifiseres videre i lineære og ikke-lineære datastrukturer.

Lineær datastruktur

Lineære datastrukturer har alle elementene ordnet på en lineær eller sekvensiell måte. Hvert element i en lineær datastruktur har en forgjenger (forrige element) og en etterfølger (neste element)

Lineære datastrukturer er videre delt inn i statiske og dynamiske datastrukturer. Statiske datastrukturer har vanligvis en fast størrelse, og når størrelsen er erklært på kompileringstidspunktet, kan den ikke endres. Dynamiske datastrukturer kan endre størrelsen dynamisk og imøtekomme seg selv.

Det mest populære eksemplet på lineær statisk datastruktur er en matrise.

Array

En matrise er en sekvensiell samling av elementer av samme type. Hvert element i matrisen kan nås ved å bruke sin posisjon i matrisen som kalles en indeks eller et abonnement på matrisen. Navnet på matrisen peker mot det første elementet i matrisen.

array

Ovennevnte er en matrise ‘a’ av n elementer. Elementene er nummerert fra 0 til n-1. Størrelsen på matrisen (i dette tilfellet) kalles også dimensjonen til matrisen. Som vist i figuren ovenfor, peker navnet på matrisen på det første elementet i matrisen.

Matrisen er den enkleste datastrukturen og er effektiv ettersom elementer er tilgjengelige via abonnement direkte. Hvis vi vil ha tilgang til det tredje elementet i matrisen, må vi bare si a (2).

Men det er vanskelig å legge til eller slette matriseelementene. Derfor bruker vi matriser bare i enkle applikasjoner eller i applikasjoner der det ikke er nødvendig å legge til / slette elementer.

Populære lineære dynamiske datastrukturer er koblet til liste, stabel og kø.

Koblet liste

En koblet liste er en samling noder. Hver node inneholder dataelementet og en peker til neste node. Noder kan legges til og slettes dynamisk. En koblet liste kan være en enkelt koblet liste der hver node bare har en peker til neste element. For det siste elementet er neste peker satt til null.

I den dobbeltkoblede listen har hver node to pekere en til forrige node og den andre til neste node. For den første noden er den forrige pekeren null, og for den siste noden er den neste pekeren null.

Koblet liste

Som vist i figuren ovenfor, kalles begynnelsen på listen hodet mens slutten på den koblede listen kalles halen. Som vist ovenfor har hver node en peker til neste element. Vi kan enkelt legge til eller slette elementer ved å endre pekeren til neste node.

Stable

Stack er en lineær datastruktur der elementene bare kan legges til eller fjernes fra den ene enden, kjent som 'Top' of the stack. På denne måten viser stack LIFO (Last In, First Out) minnetilgang.

Stable

Som vist ovenfor blir elementer i stabelen alltid lagt til i den ene enden og fjernet fra samme ende. Dette kalles 'toppen' av bunken. Når et element er lagt til, skyves det nedover stabelen, og toppen av stabelen økes med en posisjon.

Tilsvarende, når et element fjernes, blir toppen av bunken redusert. Når en bunke er tom, er toppen av bunken satt til -1. Det er to hovedoperasjoner 'Push' og 'Pop' som utføres på bunken.

Kø

Køen er enda en lineær datastruktur der elementene blir lagt til i den ene enden kalt 'bak' og slettet fra en annen ende kalt 'front'. Køen viser FIFO (First In, First Out) typen minnetilgangsmetodikk.

Kø

Ovenstående diagram viser en kø med bak- og frontender. Når køen er tom sammenfaller pekerne bak og foran hverandre.

Ikke-lineær datastruktur

I ikke-lineære datastrukturer er ikke data ordnet sekvensielt, i stedet er de ordnet på en ikke-lineær måte. Elementer er koblet til hverandre i et ikke-lineært arrangement.

Ikke-lineære datastrukturer er trær og grafer.

forskjell mellom alfa- og betatesting

Trær

Trær er ikke-lineære datanettverk på flere nivåer som har et hierarkisk forhold mellom elementene. Elementer av treet kalles noder.

Noden øverst kalles roten til treet. Roten kan ha en eller flere underordnede noder. De påfølgende nodene kan også ha en eller flere underordnede noder. Nodene som ikke har barn noder kalles bladnoder.

Trær

I diagrammet ovenfor har vi vist et tre med 6 noder. Ut av disse tre nodene er bladnodene, en øverste node er roten og de andre er barnenoder. Avhengig av antall noder, noder til barn osv. Eller forholdet mellom noder, har vi forskjellige trær.

Grafer

Grafen er et sett med noder som kalles hjørner koblet til hverandre ved hjelp av koblingene som kalles Kanter . Grafer kan ha en syklus inne i den, dvs. det samme toppunktet kan være et utgangspunkt i tillegg til sluttpunktet til en bestemt bane. Trær kan aldri ha en syklus.

Grafer

Ovenstående diagram er en ikke-rettet graf. Vi kan også ha rettet grafer der vi representerer kantene ved hjelp av rettet pil.

Operasjoner på datastruktur

Alle datastrukturene utfører forskjellige operasjoner på elementene.

Disse er felles for alle datastrukturer og er oppført som følger:

  • Søker: Denne operasjonen utføres for å søke etter et bestemt element eller en nøkkel. De vanligste søkealgoritmene er sekvensielt / lineært søk og binært søk.
  • Sortering: Sorteringsoperasjon innebærer å ordne elementene i en datastruktur i en bestemt rekkefølge, enten stigende eller synkende. Det er forskjellige sorteringsalgoritmer som er tilgjengelige for datastrukturer. Mest populære blant dem er Quicksort, Selection sort, Merge sort, etc.
  • Innsetting: Innsettingsoperasjon handler om å legge til et element i datastrukturen. Dette er den viktigste operasjonen, og som et resultat av tillegg av et element endres arrangementet, og vi må passe på at datastrukturen forblir intakt.
  • Sletting: Slettingsoperasjon fjerner et element fra datastrukturen. De samme vilkårene som skal vurderes for innsetting skal også oppfylles i tilfelle slettingsoperasjonen.
  • Traversering: Vi sier at vi krysser en datastruktur når vi besøker hvert eneste element i strukturen. Traversering er nødvendig for å utføre bestemte spesifikke operasjoner på datastrukturen.

I de påfølgende emnene vil vi først lære de forskjellige søke- og sorteringsteknikkene som skal utføres på datastrukturer.

Fordeler med datastruktur

  • Abstraksjon: Datastrukturer implementeres ofte som abstrakte datatyper. Brukerne får bare tilgang til det ytre grensesnittet uten å bekymre seg for den underliggende implementeringen. Dermed gir datastrukturen et abstraksjonslag.
  • Effektivitet: Riktig organisering av data resulterer i effektiv tilgang til data og derved gjør programmer mer effektive. For det andre kan vi velge riktig datastruktur avhengig av våre krav.
  • Gjenbrukbarhet: Vi kan gjenbruke datastrukturene vi har designet. De kan også samles i et bibliotek og distribueres til klienten.

Konklusjon

Med dette avslutter vi denne veiledningen om introduksjon til datastrukturer. Vi har introdusert hver av datastrukturene i korte trekk i denne opplæringen.

I de påfølgende veiledningene vil vi utforske mer om datastrukturer sammen med de forskjellige søke- og sorteringsteknikkene.

=> Klikk her for den absolutte C ++ treningsserien.

Anbefalt lesing

^