Efter arrays er den næstmest populære datastruktur Linked List. En sammenkædet liste er en lineær datastruktur, der er lavet af en kæde af noder, hvor hver node indeholder en værdi og en markør til den næste node i kæden. Lad os i denne artikel se, hvordan man implementerer en linket liste i C.
Hvad er sammenkædet liste i C?
En sammenkædet liste er en lineær datastruktur. Hver sammenkædet liste har to dele, datasektionen og adresseafsnittet, der indeholder adressen på det næste element i listen, der kaldes en node.
hvordan man dybt kopierer i java
Størrelsen på den sammenkædede liste er ikke fast, og dataelementer kan tilføjes hvor som helst på listen. Ulempen er, at for at komme til en node skal vi krydse hele vejen fra den første node til den node, som vi har brug for. Den sammenkædede liste er som et array, men i modsætning til et array lagres det ikke sekventielt i hukommelsen.
De mest populære typer af en linket liste er:
Eksempel på sammenkædet liste
Format: [data, adresse]
Hoved -> [3.100] -> [43.1001] -> [21.1002]
I eksemplet er tallet 43 til stede på placering 1000, og adressen er til stede i den forrige knude. Sådan vises en sammenkædet liste.
Grundlæggende sammenkædede listefunktioner
Der er flere funktioner, der kan implementeres på den linkede liste i C. Lad os prøve at forstå dem ved hjælp af et eksempelprogram.Først opretter vi en liste, viser den, indsætter hvor som helst, sletter en placering. Den følgende kode viser dig, hvordan du udfører operationer på listen.
#include #include void create () ugyldig 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 * næste} 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. Indsæt ved begyndelsen n ') printf (' n 4. Indsæt i slutningen n ') printf (' n 5. Indsæt i specificeret position n ') printf (' n 6. Slet fra start n ') printf (' n 7. Slet fra slutningen n ') printf (' n 8. Slet fra specificeret position n ') printf (' n 9. Afslut n ') printf (' n ----------------- --------------------- n ') printf (' Indtast dit valg: t ') scanf ('% d ', & valg) switch (valg) {sag 1 : Opret () 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 create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nIndtast dataværdien for noden: t') scanf ('% d', & temp-> info) temp-> næste = NULL hvis (start == NULL) {start = temp} ellers {ptr = start mens (ptr-> næste! = NULL) {ptr = ptr-> næste} ptr-> næste = temp}} ugyldig visning () {struct node * ptr hvis (start == NULL) {printf ('nList er tom: n ') returner} ellers {ptr = start printf (' nListeelementerne er: n ') mens (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> næste}}} ugyldigt insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nIndtast dataværdi for noden: t ') scanf ('% d ', & temp-> info) temp-> næste = NULL hvis (start == NULL) {start = temp} ellers {temp-> næste = start start = temp }} ugyldigt 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 ('nIndtast dataværdien for noden: t') scanf ('% d', & temp-> info) temp-> næste = NULL hvis (start == NULL) {start = temp} ellers {ptr = start mens (ptr-> næste! = NULL) {ptr = ptr-> næste} ptr-> næste = 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 ('nIndtast positionen for den nye node, der skal indsættes: t') scanf ('% d' , & pos) printf ('nIndtast dataværdien for noden: t') scanf ('% d', & temp-> info) temp-> næste = NULL hvis (pos == 0) {temp-> næste = start start = temp} andet {for (i = 0, ptr = start-tekst, hvis (ptr == NULL) {printf ('nPosition ikke fundet: [Håndter med omhu] n') retur}} temp-> næste = ptr-> næste ptr -> næste = temp}} ugyldig delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} ellers {ptr = start start = start-> next printf (' nDet slettede element er:% dt ', ptr-> info) gratis (ptr)}} ugyldigt delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } ellers hvis (start-> næste == NULL) {ptr = start start = NULL printf ('nDet slettede element er:% dt', ptr-> info) gratis (ptr)} ellers {ptr = start mens (ptr- > næste! = NULL) {temp = ptr ptr = ptr-> næste} temp-> næste = NULL printf ('nDet slettede element 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)} ellers {printf ('n Indtast positionen for noden, der skal slettes : t ') scanf ('% d ', & pos) hvis (pos == 0) {ptr = start start = start-> næste printf (' nDet slettede element er:% dt ', ptr-> info) gratis (ptr )} andet {ptr = start for (i = 0 næste hvis (ptr == NULL) {printf ('nPosition ikke fundet: n') returnere}} temp-> næste = ptr-> næste printf ('nDet slettede element er: % dt ', ptr-> info) gratis (ptr)}}}Den første del af denne kode opretter en struktur. En linket listestruktur oprettes, så den kan indeholde data og adresse, som vi har brug for det. Dette gøres for at give compileren en idé om, hvordan noden skal være.
struct node {int info struct node * næste}I strukturen har vi en datavariabel kaldet info til at holde data og en pegevariabel til at pege på adressen. Der er forskellige handlinger, der kan udføres på en linket liste, som:
- skab()
- Skærm()
- insert_begin ()
- indsæt_end ()
- ] indsæt_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Disse funktioner kaldes af den menustyrede hovedfunktion. I hovedfunktionen tager vi input fra brugeren baseret på hvilken handling brugeren ønsker at udføre i programmet. Input sendes derefter til switch case og er baseret på bruger input.
Baseret på hvilken input der leveres, kaldes funktionen. Dernæst har vi forskellige funktioner, der skal løses. Lad os se på hver af disse funktioner.
Opret funktion
For det første er der en Opret funktion til at oprette den linkede liste. Dette er den grundlæggende måde, den linkede liste oprettes på. Lad os se på koden.
ugyldigt oprette () {struct node * temp, * ptr printf ('nIndtast dataværdien for noden: t') scanf ('% d', & temp-> info) temp-> næste = NULL hvis (start == NULL ) {start = temp} ellers {ptr = start mens (ptr-> næste! = NULL) {ptr = ptr-> næste} ptr-> næste = temp}}Produktion
For det første oprettes to markører af typen node, ptr og temp . Vi tager den værdi, der skal tilføjes i den linkede liste, fra brugeren og gemmer den i infodelen af tempvariablen og tildeler temp for den næste, der er adressedelen, til null. Der er en startmarkør, der holder starten på listen. Derefter kontrollerer vi for starten på listen. Hvis starten på listen er nul, tildeler vi temp til startmarkøren. Ellers krydser vi til det sidste punkt, hvor dataene er tilføjet.
Til dette tildeler vi ptr startværdien og krydser till ptr-> næste = null . Vi tildeler derefter ptr-> næste adressen på temp. På samme måde er der kode, der skal indsættes i begyndelsen, indsættes i slutningen og indsættes på et bestemt sted.
forskel mellem java og klasse
Displayfunktion
Her er koden til visningsfunktion.
ugyldig visning () {struct node * ptr hvis (start == NULL) {printf ('nList er tom: n') returnere} ellers {ptr = start printf ('n Listelementerne er: n') mens (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> næste}}}Produktion
I displayfunktionen kontrollerer vi først, om listen er tom, og vender tilbage, hvis den er tom. I den næste del tildeler vi startværdien til ptr. Vi kører derefter en sløjfe, indtil ptr er nul og udskriver dataelementet for hver node, indtil ptr er nul, hvilket specificerer slutningen af listen.
Slet funktion
Her er kodestykket for at slette en node fra den linkede liste.
ugyldig delete_pos () {int i, pos struct node * temp, * ptr hvis (start == NULL) {printf ('nListen er tom: n') exit (0)} ellers {printf ('nIndtast positionen for knude, der skal slettes: t ') scanf ('% d ', & pos) hvis (pos == 0) {ptr = start start = start-> næste printf (' nDet slettede element er:% dt ', ptr-> info ) gratis (ptr)} ellers {ptr = start for (i = 0 næste, hvis (ptr == NULL) {printf ('nPosition ikke fundet: n') returnere}} temp-> næste = ptr-> næste printf ('nThe slettet element er:% dt ', ptr-> info) gratis (ptr)}}}Produktion
I sletningsprocessen kontrollerer den først, om listen er tom, hvis ja, den findes. Hvis den ikke er tom, beder den brugeren om, at positionen slettes. Når brugeren kommer ind i positionen, kontrollerer den, om det er den første position, hvis ja, den tildeles ptr for at starte og flytter startmarkøren til næste placering og sletter ptr. Hvis position er ikke nul , så kører det en for-loop fra 0 hele vejen til den pos, der er indtastet af brugeren og gemt i pos variabel. Der er en if-erklæring for at afgøre, om den indtastede position ikke er til stede. Hvis ptr er lig med null , så er den ikke til stede.
Vi tildel ptr til temp i for-sløjfen, og ptr går derefter videre til næste del. Herefter når positionen er fundet. Vi laver temp-variablen til at holde værdien af ptr-> næste springer således over ptr. Derefter slettes ptr. På samme måde kan det gøres til første og sidste elementsletning.
Dobbelt sammenkædet liste
Det kaldes den dobbeltkoblede liste, fordi der er to henvisninger , et punkt til den næste node og andre punkter til den forrige node. De operationer, der udføres i dobbeltkoblet, svarer til en enkeltkædet liste. Her er koden til grundlæggende operationer.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position forrige position næste} ugyldig 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-> næste = p-> næste p-> næste = TmpCell}} ugyldig Slet (int x, Liste l) {Position p, p1, p2 p = Find (x, l) hvis (p! = NULL) {p1 = p -> forrige p2 = p -> næste p1 - > næste = p -> næste hvis (p2! = NULL) // hvis noden ikke er den sidste node p2 -> forrige = p -> forrige} ellers printf ('Element findes ikke !!! n')} ugyldig Vis (Liste l) {printf ('Listeelementet er ::') Position p = l-> næste, mens (p! = NULL) {printf ('% d ->', p-> e) p = p- > næste}} 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 ('DOUBLY LINKED LIST IMPLEMENTATION OF L IST ADTnn ') gør {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Indtast valget :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Indtast det element, der skal indsættes :: ') scanf ('% d', & x) printf ('Indtast elementets position ::') scanf ('% d', & pos) for (i = 1 inæste} Indsæt (x, l, p) break case 2: p = l printf ('Indtast det element, der skal slettes ::') scanf ('% d', & x) Slet (x, p) break case 3: Display (l) bryde}} mens (kap<4) } Produktion
hvordan fungerer casting i java
Så som du kan se, er begrebet operationer ret simpelt. Den dobbeltkoblede liste har de samme operationer som den enkeltkædede liste i C-programmeringssprog. Den eneste forskel er, at der er en anden adressevariabel, som hjælper med at krydse listen bedre på en dobbeltkoblet liste.
Jeg håber, du har forstået, hvordan man udfører grundlæggende operationer på en enkelt og dobbeltkoblet liste i C.
Hvis du ønsker at lære Linked List i Java, er her en .
Hvis du støder på nogen spørgsmål, er du velkommen til at stille alle dine spørgsmål i kommentarfeltet i 'Linked List in C', og vores team vil med glæde svare.