Koblet liste i C: Hvordan implementerer jeg en koblet liste i C?



bloggen hans på Linked List i C introduserer deg for Linked List datastruktur i C og hjelper deg å forstå implementering av koblet liste i detalj med eksempler.

Etter arrays er den nest mest populære datastrukturen Linked List. En koblet liste er en lineær datastruktur, laget av en kjede av noder der hver node inneholder en verdi og en peker til neste node i kjeden. I denne artikkelen, la oss se hvordan du implementerer en koblet liste i C.

Hva er koblet liste i C?

En koblet liste er en lineær datastruktur. Hver koblet liste har to deler, dataseksjonen og adresseseksjonen som inneholder adressen til det neste elementet i listen, som kalles en node.





Størrelsen på den koblede listen er ikke fast, og dataelementer kan legges til hvor som helst i listen. Ulempen er at for å komme til en node, må vi krysse hele veien fra den første noden til den noden vi trenger. Den koblede listen er som en matrise, men i motsetning til en matrise lagres den ikke sekvensielt i minnet.

De mest populære typene av en koblet liste er:



  1. Enkel lenkeliste
  2. Dobbelt lenkliste

Eksempel på koblet liste

Format: [data, adresse]

Hode -> [3,1000] -> [43,1001] -> [21,1002]



I eksemplet er tallet 43 til stede på plassering 1000 og adressen er til stede i forrige node. Slik er en koblet liste representert.

Grunnleggende funksjoner for koblede lister

Det er flere funksjoner som kan implementeres på den koblede listen i C. La oss prøve å forstå dem ved hjelp av et eksempelprogram.Først oppretter vi en liste, viser den, setter inn hvor som helst, sletter en plassering. Følgende kode vil vise deg hvordan du utfører operasjoner på listen.

#include #include void create () void display () ugyldig insert_begin () ugyldig insert_end () ugyldig insert_pos () ugyldig delete_begin () ugyldig delete_end () ugyldig delete_pos () struct node {int info struct node * neste} struct node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2. Display n') printf ('n 3. Sett inn ved begynnelsen n ') printf (' n 4. Sett inn på slutten n ') printf (' n 5. Sett inn i spesifisert posisjon n ') printf (' n 6. Slett fra begynnelsen n ') printf (' n 7. Slett fra slutten n ') printf (' n 8. Slett fra spesifisert posisjon n ') printf (' n 9. Avslutt n ') printf (' n ----------------- --------------------- n ') printf (' Skriv inn ditt valg: t ') scanf ('% d ', & valg) bryter (valg) {sak 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d opprett () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nUt minneområdet: n') exit (0) } printf ('nTast inn dataverdien for noden: t') scanf ('% d', & temp-> info) temp-> neste = NULL hvis (start == NULL) {start = temp} annet {ptr = start mens (ptr-> neste! = NULL) {ptr = ptr-> neste} ptr-> neste = temp}} ugyldig visning () {struct node * ptr hvis (start == NULL) {printf ('nListe er tom: n ') returner ellers {ptr = start printf (' nListeelementene er: n ') mens (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> neste}}} ugyldig insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nTast inn dataverdi for noden: t ') scanf ('% d ', & temp-> info) temp-> neste = NULL hvis (start == NULL) {start = temp} annet {temp-> neste = start start = temp }} ugyldig insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} s rintf ('nTast inn dataverdien for noden: t') scanf ('% d', & temp-> info) temp-> neste = NULL hvis (start == NULL) {start = temp} annet {ptr = start mens (ptr-> neste! = NULL) {ptr = ptr-> neste} ptr-> neste = temp}} ugyldig insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) hvis (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nTast inn posisjonen for den nye noden som skal settes inn: t') scanf ('% d' , & pos) printf ('nTast inn dataverdien til noden: t') scanf ('% d', & temp-> info) temp-> neste = NULL hvis (pos == 0) {temp-> neste = start start = temp} annet {for (i = 0, ptr = start-tekst hvis (ptr == NULL) {printf ('nPosisjon ikke funnet: [Håndter forsiktig] n') retur}} temp-> neste = ptr-> neste ptr -> neste = temp}} ugyldig delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nDet slettede elementet er:% dt ', ptr-> info) ledig (ptr)}} ugyldig delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } annet hvis (start-> neste == NULL) {ptr = start start = NULL printf ('nDet slettede elementet er:% dt', ptr-> info) gratis (ptr)} annet {ptr = start mens (ptr- > neste! = NULL) {temp = ptr ptr = ptr-> neste} temp-> neste = NULL printf ('nDet slettede elementet er:% dt', ptr-> info) gratis (ptr)}} ugyldig delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nListen er tom: n') exit (0)} else {printf ('n Angi posisjonen til noden som skal slettes : t ') scanf ('% d ', & pos) hvis (pos == 0) {ptr = start start = start-> neste printf (' nDet slettede elementet er:% dt ', ptr-> info) gratis (ptr )} annet {ptr = start for (i = 0 neste hvis (ptr == NULL) {printf ('nPosisjon ikke funnet: n') retur}} temp-> neste = ptr-> neste printf ('nDet slettede elementet er: % dt ', ptr-> info) gratis (ptr)}}}

Den første delen av denne koden er å lage en struktur. En koblet listestruktur opprettes slik at den kan holde dataene og adressen slik vi trenger den. Dette er gjort for å gi kompilatoren en ide om hvordan noden skal være.

struct node {int info struct node * neste}

I strukturen har vi en datavariabel kalt info for å holde data og en pekervariabel for å peke på adressen. Det er forskjellige operasjoner som kan gjøres på en koblet liste, som:

  • skape()
  • vise()
  • insert_begin ()
  • insert_end ()
  • ] insert_pos ()
  • delete_begin ()
  • delete_end ()
  • delete_pos ()

Disse funksjonene kalles av den menydrevne hovedfunksjonen. I hovedfunksjonen tar vi innspill fra brukeren basert på hvilken operasjon brukeren vil gjøre i programmet. Inngangen sendes deretter til brytervesken og basert på brukerinngang.

Basert på hvilken inngang som gis, blir funksjonen kalt. Deretter har vi forskjellige funksjoner som må løses. La oss ta en titt på hver av disse funksjonene.

Opprett funksjon

Først er det en opprettingsfunksjon for å opprette den koblede listen. Dette er den grunnleggende måten den lenkede listen opprettes på. La oss se på koden.

void create () {struct node * temp, * ptr printf ('nTast inn dataverdien for noden: t') scanf ('% d', & temp-> info) temp-> neste = NULL hvis (start == NULL ) {start = temp} annet {ptr = start mens (ptr-> neste! = NULL) {ptr = ptr-> neste} ptr-> neste = temp}}

Produksjon

Sett inn - lenket liste - Edureka

Først opprettes to pekere av typen node, ptr og temp . Vi tar verdien som er nødvendig for å bli lagt til i den koblede listen fra brukeren og lagrer den i infodelen av tempvariabelen og tildeler temp for neste som er adressedelen til null. Det er en startpeker som holder starten på listen. Så ser vi etter starten på listen. Hvis starten på listen er null, tilordner vi temp til startpekeren. Ellers krysser vi til det siste punktet der dataene er lagt til.

For dette tildeler vi ptr startverdien og krysser till ptr-> neste = null . Vi tilordner deretter ptr-> neste adressen til temp. På lignende måte er det gitt kode for å sette inn i begynnelsen, sette inn på slutten og sette inn på et spesifisert sted.

Skjermfunksjon

Her er koden for visningsfunksjon.

ugyldig visning () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('n Listelementene er: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> neste}}}

Produksjon

I skjermfunksjonen sjekker vi først om listen er tom, og returnerer hvis den er tom. I neste del tilordner vi startverdien til ptr. Vi kjører deretter en sløyfe til ptr er null og skriver ut dataelementet for hver node, til ptr er null, som spesifiserer slutten av listen.

Slett funksjon

Her er kodebiten for å slette en node fra den koblede listen.

ugyldig delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('n Listen er tom: n') exit (0)} else {printf ('n Angi posisjonen til node som skal slettes: t ') scanf ('% d ', & pos) hvis (pos == 0) {ptr = start start = start-> neste printf (' n Det slettede elementet er:% dt ', ptr-> info ) gratis (ptr)} annet {ptr = start for (i = 0 neste hvis (ptr == NULL) {printf ('nPosisjon ikke funnet: n') retur}} temp-> neste = ptr-> neste printf ('nThe slettet element er:% dt ', ptr-> info) gratis (ptr)}}}

Produksjon

I slettingsprosessen sjekker den først om listen er tom, hvis ja den eksisterer. Hvis den ikke er tom, ber den brukeren om at posisjonen skal slettes. Når brukeren kommer inn i posisjonen, sjekker den om den er første posisjon, hvis ja den tildeles ptr for å starte og flytter startpekeren til neste plassering og sletter ptr. Hvis den posisjon er ikke null , så kjører den en for-loop fra 0 helt til posen som er angitt av brukeren og lagret i pos variabel. Det er en if-uttalelse for å avgjøre om den innlagte stillingen ikke er til stede. Hvis ptr er lik null , da er den ikke til stede.

Vi tilordne ptr til temp i for-sløyfen, og ptr går deretter videre til neste del. Etter dette når stillingen er funnet. Vi lager tempvariabelen for å holde verdien på ptr-> neste dermed hopper over ptr. Deretter slettes ptr. På samme måte kan det gjøres for første og siste elementsletting.

Dobbeltkoblet liste

Det kalles den dobbeltkoblede listen fordi det er to pekere , ett punkt til neste node og andre punkter til forrige node. Operasjonene utført i dobbeltkoblet ligner på en enkeltkoblet liste. Her er koden for grunnleggende operasjoner.

java konvertere fra dobbelt til int
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position previous Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) hvis (TmpCell == NULL) printf ('Memory out of spacen') ellers {TmpCell-> e = x TmpCell-> forrige = p TmpCell-> neste = p-> neste p-> neste = TmpCell}} ugyldig Slett (int x, Liste l) {Posisjon p, p1, p2 p = Finn (x, l) hvis (p! = NULL) {p1 = p -> forrige p2 = p -> neste p1 - > neste = p -> neste hvis (p2! = NULL) // hvis noden ikke er den siste noden p2 -> forrige = p -> forrige} annet printf ('Element eksisterer ikke !!! n')} ugyldig Vis (Liste l) {printf ('Listeelementet er ::') Posisjon p = l-> neste mens (p! = NULL) {printf ('% d ->', p-> e) p = p- > neste}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('DOBBELKOBLET LISTE IMPLEMENTERING AV L IST ADTnn ') gjør {printf (' nn1. CREATEn 2. SLETT 3. DISPLAYn 4. QUITnnTast inn valget :: ') scanf ('% d ', & ch) bryter (ch) {case 1: p = l printf (' Skriv inn elementet som skal settes inn :: ') scanf ('% d', & x) printf ('Skriv inn posisjonen til elementet ::') scanf ('% d', & pos) for (i = 1 ineste} Sett inn (x, l, p) break case 2: p = l printf ('Skriv inn elementet som skal slettes ::') scanf ('% d', & x) Slett (x, p) break case 3: Display (l) bryte}} mens (kap<4) } 

Produksjon

Så som du kan se er operasjonskonseptet ganske enkelt. Den dobbeltkoblede listen har de samme operasjonene som den for enkeltkoblet liste i C-programmeringsspråk. Den eneste forskjellen er at det er en annen adressevariabel som hjelper å krysse listen bedre i en dobbeltkoblet liste.

Jeg håper du har forstått hvordan du utfører grunnleggende operasjoner på en enkelt og dobbelt koblet liste i C.

Hvis du ønsker å lære Linked List i Java, er her en .

Hvis du kommer over noen spørsmål, er du velkommen til å stille alle spørsmålene dine i kommentarfeltet i 'Koblet liste i C', og teamet vårt svarer gjerne.