După tablouri, a doua structură de date cea mai populară este Linked List. O listă legată este o structură de date liniară, formată dintr-un lanț de noduri în care fiecare nod conține o valoare și un pointer către următorul nod din lanț. În acest articol, să vedem cum să implementăm o listă legată în C.
Ce este Linked List în C?
O listă legată este o structură de date liniară. Fiecare listă legată are două părți, secțiunea de date și secțiunea de adrese care deține adresa elementului următor din listă, care se numește nod.
Dimensiunea listei conectate nu este fixă, iar elementele de date pot fi adăugate în orice locație din listă. Dezavantajul este că pentru a ajunge la un nod, trebuie să parcurgem tot drumul de la primul nod la nodul de care avem nevoie. Lista legată este ca un tablou, dar spre deosebire de un tablou, nu este stocată secvențial în memorie.
Cele mai populare tipuri de liste legate sunt:
Exemplu de Listă legată
Format: [date, adresă]
Cap -> [3,1000] -> [43,1001] -> [21,1002]
În exemplu, numărul 43 este prezent la locația 1000, iar adresa este prezentă în nodul anterior. Acesta este modul în care este reprezentată o listă legată.
Funcții de bază legate de listă
Există mai multe funcții care pot fi implementate pe lista legată în C. Să încercăm să le înțelegem cu ajutorul unui exemplu de program.Mai întâi, creăm o listă, o afișăm, o inserăm în orice locație, ștergem o locație. Următorul cod vă va arăta cum să efectuați operațiuni pe listă.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct nod {int info struct node * next} struct node * start = NULL int main () {int choice while (1) {printf ('n MENU n') printf ('n 1. Creați n') printf ('n 2. Afișați n') printf ('n 3. Introduceți la începutul n ') printf (' n 4. Introduceți la sfârșitul n ') printf (' n 5. Introduceți la poziția specificată n ') printf (' n 6. Ștergeți de la începutul n ') printf (' n 7. Ștergeți de la sfârșitul n ') printf (' n 8. Ștergeți din poziția specificată n ') printf (' n 9. Exit n ') printf (' n ----------------- --------------------- n ') printf (' Introduceți alegerea: t ') scanf ('% d ', & alegere) comutator (alegere) {caz 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 implicit: printf ('n Alegere greșită: 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 ('nIntroduceți valoarea datelor pentru nod: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n ') return} else {ptr = start printf (' nElementele listei sunt: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nIntroduceți valoarea datelor pentru nod: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nIntroduceți valoarea datelor pentru nod: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct nod)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nIntroduceți poziția pentru noul nod de inserat: t') scanf ('% d' , & pos) printf ('nIntroduceți valoarea datelor nodului: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Handle with care] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nElementul șters este:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nElementul șters este:% dt', ptr-> info) gratuit (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nElementul șters este:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLista este goală: n') exit (0)} else {printf ('nIntroduceți poziția nodului care trebuie șters : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nElementul șters este:% dt ', ptr-> info) gratuit (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nElementul șters este: % dt ', ptr-> info) gratuit (ptr)}}}Prima parte a acestui cod este crearea unei structuri. O structură de listă legată este creată astfel încât să poată păstra datele și adresa după cum avem nevoie. Acest lucru este făcut pentru a oferi compilatorului o idee despre cum ar trebui să fie nodul.
nod nod {int info nod nod * următor}În structură, avem o variabilă de date numită info pentru a păstra date și o variabilă de pointer pentru a indica adresa. Există diverse operații care pot fi efectuate pe o listă legată, cum ar fi:
- crea()
- afişa()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Aceste funcții sunt apelate de funcția principală bazată pe meniu. În funcția principală, preluăm date de la utilizator în funcție de ce operație dorește să facă utilizatorul în program. Intrarea este apoi trimisă în cazul comutatorului și pe baza intrării utilizatorului.
Pe baza intrării furnizate se va apela funcția. Apoi, avem diferite funcții care trebuie rezolvate. Să aruncăm o privire la fiecare dintre aceste funcții.
Creați funcția
În primul rând, există o funcție de creare pentru a crea lista legată. Acesta este modul de bază în care este creată lista legată. Să ne uităm la cod.
mongodb creează utilizator pentru baza de date
void create () {struct node * temp, * ptr printf ('nIntroduceți valoarea datelor pentru nod: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Ieșire
În primul rând, sunt create două indicii de acest tip nod, ptr și temp . Luăm de la utilizator valoarea necesară pentru a fi adăugată în lista legată și o stocăm în partea de informații a variabilei temp și atribuim temperatura de la următoarea, care este partea de adresă nulă Există un indicator de pornire care menține începutul listei. Apoi verificăm începutul listei. Dacă începutul listei este nul, atunci atribuim temp cursorului de pornire. În caz contrar, parcurgem ultimul punct în care au fost adăugate datele.
Pentru aceasta, atribuim ptr valoarea de pornire și traversăm până ptr-> next = nul . Apoi atribuim ptr-> următor adresa temp. În mod similar, există codul dat pentru inserarea la început, inserarea la sfârșit și inserarea într-o locație specificată.
Funcția de afișare
Iată codul pentru funcția de afișare.
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nElementele din Listă sunt: n') în timp ce (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> next}}}Ieșire
În funcția de afișare, verificăm mai întâi dacă lista este goală și revenim dacă este goală. În partea următoare, atribuim valoarea de pornire ptr. Apoi rulăm o buclă până când ptr este nul și imprimăm elementul de date pentru fiecare nod, până când ptr este nul, care specifică sfârșitul listei.
Funcția de ștergere
Iată fragmentul de cod pentru a șterge un nod din lista conectată.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLista este goală: n') exit (0)} else {printf ('nIntroduceți poziția nod de șters: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nElementul șters este:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe elementul șters este:% dt ', ptr-> info) gratuit (ptr)}}}Ieșire
În procesul de ștergere, verifică mai întâi dacă lista este goală, dacă da există. Dacă nu este gol, îi solicită utilizatorului ștergerea poziției. Odată ce utilizatorul intră în poziție, verifică dacă este prima poziție, dacă da atribuie ptr pentru a porni și muta indicatorul de start la următoarea locație și șterge ptr. Dacă poziția nu este zero , apoi rulează o buclă for de la 0 până la poziția introdusă de utilizator și stocată în poz variabil. Există o declarație if pentru a decide dacă poziția introdusă nu este prezentă. Dacă ptr este egal cu nul , atunci nu este prezent.
Noi atribuiți ptr la temp în bucla for și ptr trece apoi la partea următoare. După aceasta când se găsește poziția. Facem variabila temp pentru a menține valoarea lui ptr-> următor sărind astfel ptr. Apoi ptr este șters. În mod similar, se poate face pentru ștergerea primului și ultimului element.
Lista dublă legată
Se numește lista dublu legată, deoarece există două indicii , un punct către nodul următor și alte puncte către nodul anterior. Operațiunile efectuate în legătură dublă sunt similare cu cele ale unei liste conectate individual. Iată codul pentru operațiuni de bază.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position anterior Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') altceva {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Șterge (int x, Lista l) {Poziția p, p1, p2 p = Găsiți (x, l) dacă (p! = NULL) {p1 = p -> precedent p2 = p -> următor p1 - > următor = p -> următor dacă (p2! = NULL) // dacă nodul nu este ultimul nod p2 -> precedent = p -> anterior} else printf ('Elementul nu există !!! n')} void Afișare (Listă l) {printf („Elementul listei este ::”) Poziție p = l-> următoare în timp ce (p! = NULL) {printf („% d ->”, p-> e) p = p- > next}} 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 ('IMPLEMENTAREA LISTEI DUBLU LEGATE DE L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnEnter the choice :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Introduceți elementul de inserat :: ') scanf ('% d', & x) printf ('Introduceți poziția elementului ::') scanf ('% d', & pos) pentru (i = 1 iurmător} Insert (x, l, p) break case 2: p = l printf ('Introduceți elementul de șters ::') scanf ('% d', & x) Delete (x, p) break case 3: Display (l) pauză}} în timp ce (cap<4) } Ieșire
Deci, după cum puteți vedea, conceptul de operații este destul de simplu. Lista dublă legată are aceleași operații ca cea a listei legate individual în limbajul de programare C. Singura diferență este că există o altă variabilă de adresă care ajută la traversarea mai bună a listei într-o listă dublu legată.
Sper că ați înțeles cum să efectuați operațiuni de bază pe o listă legată individual și dublu în C.
eșuează rapid vs eșuează în siguranță
Dacă doriți să aflați Lista conectată în Java, iată un .
Dacă întâmpinați orice întrebare, nu ezitați să vă adresați toate întrebările în secțiunea de comentarii din „Listă legată în C”, iar echipa noastră va răspunde cu plăcere.