Sorter koblet liste C ++

Koblet liste

En koblet liste er en slags datastruktur. Elementene inne i den koblede listen er koblet sammen ved å bruke pekere. Det er en samling noder. En node inneholder to deler. Den ene inkluderer dataene, og den andre delen består av pekeren. Denne pekeren brukes til å lagre minneadressen til nodeelementet ved siden av den i den koblede listen. Fordelen med den koblede listen over en matrise er at den har en dynamisk størrelse.

Representasjon av en lenket liste

Den første noden på den koblede listen kalles fremover. Verdien er null i tilfelle av en tom matrise. I C ++ bruker vi en struktur for å representere en node.

Dette er en enkel C ++ -kode for Linked List Creation. Vi har opprettet en klasse der den offentlige delen, en datavariabel av heltallstype, er opprettet med en pekertypevariabel 'neste' som vil lagre adressen til noden.

Tre noder er opprettet inne i hovedprogrammet, med den øverste første noden erklært som 'Head' -noden. Alle tre-poengene til disse nodene er tomme, så de er erklært som null til å begynne med. Etter å ha gjort dette, blir alle tre nodene tildelt i en haug. 'head' sekund, og tredje er tildelt med den nye noden.

Nå vil vi tilordne data, og data kan være en hvilken som helst tilfeldig verdi. Først vil vi tilordne data i den første noden.

Head-> data = 1;

Denne demonstrasjonen av data som tilordner viser at den første nodens datadel vil inneholde data i den. Etter å ha tilordnet data, vil vi koble den første noden med den andre

Head-> neste = sekund;

Vi kobler den 'neste' pekerdelen med den andre noden for å koble to noder. Vi vil tilordne data lagret i datadelen av den første noden. Mens den 'neste' delen vil inneholde minneadressen til noden som er til stede etter den. Tilsvarende vil vi nå tildele data til den andre noden, og den andre noden vil være koblet til den tredje noden. Legg nå til data i den tredje noden. Ettersom vi bare har laget tre noder, er det ingen annen node, så neste del av den tredje pekeren vil bli erklært som null; Dette indikerer at den koblede listen blir avsluttet.

Tredje-> neste = null;

Eksempel

Sorter koblet liste

Her har vi erklært en struktur som representerer en node med en enkelt koblet liste. Som beskrevet ovenfor tas konseptet med koblet listedeklarasjon, datavariabelen og pekervariablene i strukturen. I likhet med den "neste" pekerdelen som lagrer adressen, har vi også erklært ytterligere to pekertypevariabler: Nodehode og nodehale. Disse begge er opprinnelig erklært som null.

Når innsettingsnoden tar for seg å sette inn dataknute i den koblede listen, vil vi bruke en funksjon av å legge til en node. Dataene vil også tilordne denne noden. Så parameteren til denne funksjonen vil inneholde data som et argument. Før innsetting vil noden bli opprettet med minnetildeling ved å bruke en Malloc () -funksjon. Datadelen av den nye noden vil bli tildelt med de beståtte dataene.

NewNode-> data = data;

Og på samme måte blir den neste delen tildelt som null, da det ikke er noen sammenheng mellom denne noden med noen annen. Ettersom hode- og halevariabler er erklært å hjelpe til med innsettingssortering. Nå vil vi bruke dem her. For det første, ved å bruke en if-ests-uttalelse, vil vi sjekke om hodet er null, som vi har erklært som null ovenfor, noe som betyr at hele listen er tom. Derfor er hodet tomt, så hodet og halevariablene vil peke på den nyopprettede noden. Ellers, i den andre delen, hvis listen ikke er tom, antar vi at mens vi oppretter listen har vi også lagt inn data, vil den nye noden i dette tilfellet bli lagt til på siste sted.

Hale-> neste = newNode;

Og nå vil denne nye noden fungere som en ny historie.

Hale = newNode;

For ytterligere tillegg fortsetter den samme prosessen, men vi må sortere den koblede listen. Så vi har lagt til en enkelt node som fungerer som en temp -node for å lagre data i den midlertidig.

Etter å ha lagt til den nye noden, vil vi bruke en funksjon til å sortere/ ordne listen. Ettersom sorteringen ikke er nevnt her, vil listen som standard bli sortert i stigende rekkefølge.

Når vi kommer tilbake mot eksemplet, peker en annen strømpeker mot hodet, som vi erklærte ovenfor. Dette brukes til å sortere listeelementene. En annen pekertypevariabel vil bli brukt her og deretter erklært som null. Ytterligere bruk vil være i programmet senere.

Her vil vi bruke en sjekk for å identifisere om Head Pointer er i nullposisjonen og deretter tilbake til hovedprogrammet. Ellers vil vi bruke logikk her som vil følge en stund loop. Indekspekeren vil peke på neste del av den gjeldende noden. Inne i at mens Loop brukes en annen mens Loop brukes, og dette vil også vare til den nåværende noden ikke er null. Her vil vi bruke en IF-uttalelse for å sjekke om dataene i den gjeldende noden er større enn dataene i indeksens node, så byttes dataene mellom dem.

Temp -variabelen vil spille en viktig rolle her i databytte. Først overføres gjeldende nodedata til temp, og deretter er den gjeldende noden nå tom. Denne noden vil bli tildelt verdien av indeksdata. Og på slutten tildeles den tomme indeksnoden av dataene som er til stede i temp -variabelen.

Utenfor IF-uttalelsen økes også indeksnoden med den nye verdien av en indeks. Tilsvarende, utenfor While Loop, tildeles også den nåværende noden av den nye verdien.

Deretter har vi brukt en skjermfunksjon her for å vise verdien av alle nodene. Den nåværende pekeren vil peke mot hodet. I et annet tilfelle viser en stundsløyfe alle verdiene til den gjeldende noden ikke er null.

Vurder nå hovedprogrammet, funksjonen til AddNode () kalles med verdiene for å legge til nye verdier inne i listen. Da vil visningsfunksjonen vise alle de angitte verdiene før sortering. Kall deretter sorteringsfunksjonen (). Og så igjen, ring displayfunksjonen for å vise hele listen.

Lagre kodefilen og kjør den deretter i Ubuntu -terminalen ved hjelp av en G ++ -kompilator.

$ g ++ -o filfil.c

$./fil

Fra den resulterende verdien kan du observere at verdiene er ordnet i stigende rekkefølge da de ble lagt inn tilfeldig i den koblede listen.

Konklusjon

'Sort Linked List C ++' inneholder beskrivelsen av den grunnleggende kunnskapen om den koblede listen og dens skapelse. En prøvekode er nok til å demonstrere nodeopprettelsen og arbeidet med alle nodene i den koblede listen. Elementene inne i den koblede listen er ordnet i stigende rekkefølge ved hjelp av en detaljert prosess ved å legge til nye noder og deretter sortere gjennom en temp -variabel. Forklaring med koden gjøres for å hjelpe brukeren.