Skriv ut koblet liste i C ++

Når det gjelder dynamisk lagring av dataelementer, ligner koblede lister en matrise. En matrise er en lineær datastruktur som lagrer alle dataelementene, slik at vi kan overføre elementene i matrisen i en kontinuerlig operasjon. Mens dataelementer i den koblede listen ikke holdes på kontinuerlige minneplasser når de lagres. Det er utgangspunktet i den koblede listen som kalles hodet og sluttpunktet kalles halen til den koblede listen på C ++ programmeringsspråk. I en koblet liste er det noder som lagrer dataobjekter i den. Noden har to deler: Delen inneholder dataobjektet i seg selv, og den andre delen inneholder pekeren mot noden etter den. Den endelige noden til den koblede listen inneholder nullpekeren.

Vi bruker en koblet liste når vi har en rekke for å lagre dataene, fordi vi i matriser må fortelle lengden på matrisen under erklæringen om matrisen. Men i koblede lister er ikke størrelse på størrelse noe problem lenger. Lengden på den koblede listen utvides som programmet krever, men listen er begrenset av kapasiteten til minne som er tilgjengelig. Den koblede listen kan utføre flere operasjoner på C ++ språk som er: innsetting, sletting, traversal, søk og sorteringsoperasjoner. For å forstå disse operasjonene av lenklisten, la oss implementere eksemplet og forstå hvordan en lenket liste fungerer i C ++ programmeringsspråk. Vi utforsker også hvordan disse operasjonene fungerer i den koblede listen.

Eksempel:

La oss nå begynne å utvikle C ++ programmeringsspråkens lenket listeeksempel. Start kompilatoren og begynn å skrive kode for å sette eksemplet i praksis. Vi må inkludere overskriftsfilen etter å ha kjørt oversetteren for å gjøre det enkelt og enkelt å få tilgang til de innebygde metodene, klassene og andre komponentene som vi ønsker å inkludere i C ++ programmeringsspråkprogrammet.

#inkludere
#inkludere
ved hjelp av navneområdet STD;

"Iostream" -pakken er den første grunnleggende pakken i C ++ og brukes av alle programmene fordi den lar brukere gi inngangs- og visningsutgang. Den andre standardbibliotekets overskrift “stdlib.H ”gir pålitelige og effektive rutiner for tildeling av minne dynamisk til C ++ programmerere. "#" -Tegnet instruerer tolken til å hente pakkene, etterfulgt av "inkludert" nøkkelordet, og forteller det å innlemme biblioteket. Endelig er biblioteknavnet skrevet i “" -tokens. Den siste setningen, "Bruke navneområde STD," er nødvendig for å gi kontekst for koden.

Initialisere strukturen

Deretter vil vi lage strukturen til navnet “Node” slik at vi dannet noden til den koblede listen. Etter å ha opprettet noden, vil vi erklære delene av noden i strukturen. Den første delen av noden er der vi lagrer dataelementene. Så vi har erklært en variabel "info av heltallstype for å lagre dataelementene. Neste del er en pekervariabel "Follownode" som vil flytte pekeren mot neste Follownode i den koblede listen. Detaljene er som følger:

Struct Node

int info;
struct node* follownode;
;

Sette inn dataelementer i den koblede listen

Vi har laget flere funksjoner slik at vi kan sette inn dataelementene i den koblede listen som vi ønsker å lage på C ++ programmeringsspråk.

Beg_Insert () Funksjon:

Vi har laget en brukerdefinert funksjon i C ++ programmeringsspråk som er Beg_Insert () -funksjonen. Som navnet antyder, vil vi bruke denne funksjonen til å sette inn dataene i begynnelsen av den koblede listen. Funksjonen Beg_Insert () tar to argumenter som er "head_info" som er pekeren til head pekeren til den koblede listen, og det andre argumentet er "new_info" som er datoen for den nye Follownoden som skal settes inn. Deretter har funksjonen laget en "cur_node" av typen "node" ved å bruke malloc () -funksjonen. "Cur Node" blir deretter initialisert med parameteren "Ny informasjon", og dens peker er satt til den tilkoblede listenes hode. Ved hjelp av "Head Info" -referansen er den koblede listenes hode opprinnelig oppført til "Cur Node".

void Beg_Insert (Struct Node ** head_info, int new_info)

struct node* cur_node = (struct node*) malloc (sizeof (struct node)));
cur_node-> info = new_info;
cur_node-> follownode = (*head_info);
(*head_info) = cur_node;

Mid_Insert () Funksjon:

Nå har vi laget en annen funksjon for å legge inn dataelementene i midten av den likte listen som er mid_insert () -funksjonen. I mid () -funksjonen må vi ta to argumenter som er "pre_node" som er pekeren for "node" -typen, og "new_info" som er variabelen som lagrer de nye dataene i seg selv av heltallstype. Vi har brukt "hvis" -uttalelsen for å sjekke "pre_node hvis det er null eller ikke i funksjonskroppen, har vi erklært en" cur_node "og lagret" new_info "i den. Så opprettet vi en "neste" peker av "new_info" som peker mot neste node av "pre_node".

void Mid_Insert (struct Node* pre_node, int new_info)

if (pre_node == null)

cout << "The Previous Node Can't be NULL";
komme tilbake;

struct node* cur_node = (struct node*) malloc (sizeof (struct node)));
cur_node-> info = new_info;
cur_node-> follownode = pre_node-> follownode;
pre_node-> follownode = cur_node;

End_Insert () Funksjon:

Vi har opprettet denne funksjonen slik at vi kan legge inn dataelementene på slutten av den koblede listen. Vi har erklært de samme argumentene som vi har erklært i Beg_Insert () -funksjonen. Denne funksjonen sjekker først om listen er tom eller ikke. Sett den "nye informasjonen" i begynnelsen av listen og returner den hvis listen også var null. Hvis det ikke er null, vil prosedyren fortsette gjennom listen til den treffer "siste node" -noden. Den "nye informasjonen" blir deretter lagt til som "siste node" -noden på slutten av listen.

void end_insert (struct node ** head_info, int new_info)

struct node* cur_node = (struct node*) malloc (sizeof (struct node)));
struct node * last_node = * head_info;
cur_node-> info = new_info;
cur_node-> follownode = null;
if (*head_info == null)

*head_info = cur_node;
komme tilbake;

mens (last_node-> follownode != Null)

last_node = last_node-> follownode;
last_node-> follownode = cur_node;
komme tilbake;

Tar en node ut av en lenket liste

For å fjerne de nåværende nodene fra den koblede listen, har vi nå bygget en ny metode som heter Delete Node (). Den bestemmer først om selve hodeknuten har den nye_keyen som må slettes. I så fall blir hovedreferansen til Follownoden oppdatert. Ved hjelp av en sløyfe vil den lokalisere noden som inneholder New_Key som skal ødelegges. Når en node blir oppdaget, oppdaterer "pre" -noden Follownode -pekeren til noden som vil bli ødelagt slik at den kan slettes uten å bli sett. Endelig brukes gratis () -funksjonen til å frigjøre lagringen.

void Delete_node (struct Node ** head_info, int new_key)

struct node *temp_var = *head_info, *pre;
if (temp_var != Null && temp_var-> info == new_key)

*head_info = temp_var-> follownode;
gratis (temp_var);
komme tilbake;

mens (temp_var != Null && temp_var-> info != new_key)

pre = temp_var;
temp_var = temp_var-> follownode;

if (temp_var == null)

komme tilbake;

pre-> follownode = temp_var-> follownode;
gratis (temp_var);

Søk i noden i den koblede listen

Funksjonssøket () tar to argumenter, som er pekeren til "head_info" på den koblede listen og "new_key" som skal søkes. Funksjonen krysser den koblede listen og sjekker om gjeldende nodedata samsvarer med "new_key". Hvis "nåværende" nodes data samsvarer med "new_key", returnerer funksjonen sann. Hvis "gjeldende" nodes data ikke samsvarer med "new_key", beveger funksjonen seg til follownoden. Hvis den "nåværende" noden blir null, returnerer funksjonen falsk.

bool -søk (struct node ** head_info, int new_key)

struct node * current = * head_info;
mens (strøm != Null)

if (current-> info == new_key)

return True;

Current = Current-> Follownode;

return falsk;

Sortering av nodens komponenter i den koblede listen

I C ++ programmering brukes sort () -metoden for å arrangere medlemmene i den koblede listen i økende rekkefølge. For det første bestemmes det om "hodeinfo" -referansen er null. I så fall kommer vi tilbake. Etter det gjentas listen flere ganger til sløyfens oppsigelse. Kontroller om ytterligere informasjon er til stede på den "nåværende" noden, så kommer "indeks" -noden neste. I så fall utveksler vi dataene mellom de to nodene. "Indeks" -noden blir deretter overført til Follownode. Prosedyren blir deretter gjentatt frem til gjennomføringen av listen.

void sort (struct node ** head_info)

struct node *current = *head_info, *index = null;
int temp_var;
if (head_info == null)

komme tilbake;

ellers

mens (strøm != Null)

indeks = gjeldende-> follownode;
mens (indeks != Null)

if (current-> info> index-> ​​info)

temp_var = current-> info;
Current-> Info = Index-> ​​Info;
indeks-> info = temp_var;

indeks = indeks-> follownode;

Current = Current-> Follownode;

Vis noden i den koblede listen

Funksjonsdisplayet () tar en peker til hodet på den koblede listen som en parameter. Etter det går den gjennom listen og viser hver nodes informasjon. Når det kommer til fullføringen av listen, stopper den.

void display (struct node* node)

mens (node != Null)
G
cout << node->info << " ";
node = node-> follownode;

Kaller funksjonene i main () -funksjonen

Vi har skrevet Main () -funksjonen slik at vi kan begynne å skrive førerkoden til programmet i hovedkroppen (). Først initialiseres "head_val" -pekeren til null av "node" -typen. Deretter kalte vi innsatsfunksjonene som vi har opprettet globalt, og vi definerte hver funksjon av å sette inn og passerte verdien i den. For å vise den koblede listen i brukerens konsollvindu, har vi kalt en brukerdefinert skjerm () -funksjon. Ring sorteringen () slik at vi kan sette av dataene i den koblede listen. For å slette noden fra den koblede listen, har vi kalt Delete_node () -funksjonen og bestått dataelementene som vi ønsker å slette. Hvis vi ønsker å finne noe element i noden, har vi kalt Search () -funksjonen og passert elementet i den.

int main ()

struct node* head_val = null;
Beg_Insert (& head_val, 34);
Beg_Insert (& head_val, 10);
end_insert (& head_val, 48);
Mid_Insert (head_val-> follownode, 72);
cout << "*---Implementation of Linked List in C++---*" << endl;
cout << "\nThe Input Linked list is: ";
display (head_val);
sorter (& head_val);
cout << "\n\nAfter Sorting the Input List: ";
display (head_val);
cout << "\nAfter deleting an element: ";
delete_node (& head_val, 48);
display (head_val);
Beg_Insert (& head_val, 63);
Beg_Insert (& head_val, 84);
end_insert (& head_val, 11);
Mid_Insert (head_val-> follownode, 100);
cout << "\n\nThe Updated Linked list is: ";
display (head_val);
sorter (& head_val);
cout << "\nAfter Sorting the Input List: ";
display (head_val);
int find_data;
cout << "\n\nEnter the element which you want to find? ";
cin >> find_data;
if (søk (& head_val, find_data))

cout << "The element " << find_data << " is found… ";

ellers

cout << "The element " << find_data << " is not found… ";

Nedenfor vises C ++ programmeringsspråkutfallet av scenariet fra samlingen ovenfor.

Konklusjon

Den koblede listen på C ++ programmeringsspråk og skillet mellom en matrise og en lenket liste ble begge dekket i denne artikkelen. Vi har snakket om den koblede listenes forskjellige operasjoner. Vi konstruerte først et lenket listescenario, deretter konstruerte vi hver operasjon i illustrasjonen med en omfattende beskrivelse av hver linje med C ++ -kode.