Dopo gli array, la seconda struttura di dati più popolare è l'elenco collegato. Una lista collegata è una struttura dati lineare, composta da una catena di nodi in cui ogni nodo contiene un valore e un puntatore al nodo successivo della catena. In questo articolo, vediamo come implementare un elenco collegato in C.
Cos'è l'elenco collegato in C?
Un elenco collegato è una struttura dati lineare. Ogni elenco collegato ha due parti, la sezione dati e la sezione indirizzo che contiene l'indirizzo dell'elemento successivo nell'elenco, chiamato nodo.
La dimensione dell'elenco collegato non è fissa e gli elementi di dati possono essere aggiunti in qualsiasi posizione nell'elenco. Lo svantaggio è che per arrivare a un nodo, dobbiamo attraversare tutto il percorso dal primo nodo al nodo di cui abbiamo bisogno. L'elenco collegato è come un array ma, a differenza di un array, non viene archiviato sequenzialmente nella memoria.
I tipi più popolari di un elenco collegato sono:
Esempio di elenco collegato
Formato: [dati, indirizzo]
Testa -> [3,1000] -> [43,1001] -> [21,1002]
Nell'esempio, il numero 43 è presente nella posizione 1000 e l'indirizzo è presente nel nodo precedente. Ecco come viene rappresentato un elenco collegato.
Funzioni di base degli elenchi collegati
Ci sono più funzioni che possono essere implementate nell'elenco collegato in C. Proviamo a capirle con l'aiuto di un programma di esempio.Innanzitutto, creiamo un elenco, lo visualizziamo, inseriamo in qualsiasi posizione, eliminiamo una posizione. Il codice seguente ti mostrerà come eseguire le operazioni sull'elenco.
#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 node {int info struct node * next} struct node * start = NULL int main () {int scelta mentre (1) {printf ('n MENU n') printf ('n 1.Crea n') printf ('n 2.Display n') printf ('n 3.Inserisci in l'inizio n ') printf (' n 4.Insert at the end n ') printf (' n 5.Insert alla posizione specificata n ') printf (' n 6.Elimina dall'inizio n ') printf (' n 7.Delete dalla fine n ') printf (' n 8.Elimina dalla posizione specificata n ') printf (' n 9.Exit n ') printf (' n ----------------- --------------------- n ') printf (' Inserisci la tua scelta: t ') scanf ('% d ', & choice) switch (choice) {case 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 create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nEnter the data value for the node: 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 (' n Gli elementi della lista sono: 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 ('nEnter the valore dei dati per il nodo: 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 ('nEnter il valore dei dati per il nodo: 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 node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEnter la posizione del nuovo nodo da inserire: t') scanf ('% d' , & pos) printf ('nInserisci il valore dei dati del nodo: 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 (' nL'elemento eliminato è:% 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 ('nL'elemento cancellato è:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > successivo! = NULL) {temp = ptr ptr = ptr-> successivo} temp-> successivo = NULL printf ('nL'elemento eliminato è:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nEnter the position of the node to be deleted : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nL'elemento cancellato è:% 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 ('nL'elemento cancellato è: % dt ', ptr-> info) free (ptr)}}}La prima parte di questo codice è creare una struttura. Viene creata una struttura di elenchi collegati in modo che possa contenere i dati e l'indirizzo quando ne abbiamo bisogno. Questo viene fatto per dare al compilatore un'idea di come dovrebbe essere il nodo.
struct node {int info struct node * next}Nella struttura, abbiamo una variabile di dati chiamata info per contenere i dati e una variabile puntatore per puntare all'indirizzo. Ci sono varie operazioni che possono essere eseguite su un elenco collegato, come:
- creare()
- Schermo()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos ()
Queste funzioni sono chiamate dalla funzione principale guidata da menu. Nella funzione principale, prendiamo l'input dell'utente in base all'operazione che l'utente desidera eseguire nel programma. L'input viene quindi inviato alla custodia dello switch e in base all'input dell'utente.
In base a quale input viene fornito, la funzione verrà chiamata. Successivamente, abbiamo diverse funzioni che devono essere risolte. Diamo un'occhiata a ciascuna di queste funzioni.
Crea funzione
Innanzitutto, c'è una funzione di creazione per creare l'elenco collegato. Questo è il modo in cui viene creato l'elenco collegato. Vediamo il codice.
void create () {struct node * temp, * ptr printf ('nEnter the data value for the node: 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}}Produzione
Innanzitutto, vengono creati due puntatori del tipo nodo, ptr e temp . Prendiamo il valore che è necessario aggiungere nell'elenco collegato dall'utente e lo memorizziamo nella parte info della variabile temp e assegniamo temp of next che è la parte dell'indirizzo a null. C'è un puntatore di inizio che tiene l'inizio dell'elenco. Quindi controlliamo l'inizio dell'elenco. Se l'inizio della lista è nullo, allora assegniamo temp al puntatore di inizio. Altrimenti, passiamo all'ultimo punto in cui sono stati aggiunti i dati.
Per questo, assegniamo a ptr il valore iniziale e traverse till ptr-> successivo = null . Quindi assegniamo ptr-> successivo l'indirizzo del temp. In modo simile, viene fornito il codice per l'inserimento all'inizio, l'inserimento alla fine e l'inserimento in una posizione specificata.
Funzione di visualizzazione
Ecco il codice per la funzione di visualizzazione.
void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nThe List elements are: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> next}}}Produzione
Nella funzione di visualizzazione, controlliamo prima se l'elenco è vuoto e restituiamo se è vuoto. Nella parte successiva, assegniamo il valore iniziale a ptr. Quindi eseguiamo un ciclo fino a quando ptr è nullo e stampiamo l'elemento dati per ogni nodo, finché ptr non è nullo, che specifica la fine della lista.
analisi del file xml in java
Elimina funzione
Ecco lo snippet di codice per eliminare un nodo dall'elenco collegato.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nEnter the position of nodo da eliminare: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nL'elemento cancellato è:% 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 l'elemento eliminato è:% dt ', ptr-> info) free (ptr)}}}Produzione
Nel processo di eliminazione, controlla prima se l'elenco è vuoto, se sì, esiste. Se non è vuoto chiede all'utente la cancellazione della posizione. Una volta che l'utente entra nella posizione, controlla se è la prima posizione, se sì la assegna ptr per iniziare e sposta il puntatore di inizio nella posizione successiva ed elimina ptr. Se la la posizione non è zero , quindi esegue un ciclo for da 0 fino alla posizione inserita dall'utente e memorizzata nel file pos variabile. C'è un'istruzione if per decidere se la posizione inserita non è presente. Se ptr è uguale a null , quindi non è presente.
Noi assegna ptr a temp nel ciclo for, e ptr quindi passa alla parte successiva. Dopo questo quando viene trovata la posizione. Facciamo in modo che la variabile temp contenga il valore di ptr-> successivo saltando così il ptr. Quindi ptr viene eliminato. Allo stesso modo, può essere fatto per l'eliminazione del primo e dell'ultimo elemento.
Elenco doppiamente collegato
Si chiama lista doppiamente collegata perché ce ne sono due puntatori , un punto al nodo successivo e altri punti al nodo precedente. Le operazioni eseguite in doppiamente concatenate sono simili a quelle di una lista concatenata singolarmente. Ecco il codice per le operazioni di base.
#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)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> previous p2 = p -> next p1 - > successivo = p -> successivo if (p2! = NULL) // se il nodo non è l'ultimo nodo p2 -> precedente = p -> precedente} else printf ('L'elemento non esiste !!! n')} void Visualizza (Lista l) {printf ('Gli elementi della lista sono ::') Posizione p = l-> successiva mentre (p! = NULL) {printf ('% d ->', p-> e) p = p- > successivo}} 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 ('ELENCO DOPPIO COLLEGATO IMPLEMENTAZIONE DI 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 (' Enter the element to be insert :: ') scanf ('% d', & x) printf ('Inserisci la posizione dell'elemento ::') scanf ('% d', & pos) for (i = 1 isuccessivo} Inserisci (x, l, p) interruzione caso 2: p = l printf ('Inserisci l'elemento da eliminare ::') scanf ('% d', & x) Elimina (x, p) interruzione caso 3: Visualizza (l) break}} while (ch<4) } Produzione
Quindi, come puoi vedere, il concetto di operazioni è abbastanza semplice. La lista doppiamente concatenata ha le stesse operazioni di quella della lista concatenata singolarmente nel linguaggio di programmazione C. L'unica differenza è che esiste un'altra variabile di indirizzo che aiuta ad attraversare meglio la lista in una lista doppiamente collegata.
Spero che tu abbia capito come eseguire le operazioni di base su una lista collegata singolarmente e doppiamente in C.
Se desideri imparare l'elenco collegato in Java, ecco un file .
Se incontri delle domande, sentiti libero di porre tutte le tue domande nella sezione commenti di 'Elenco collegato in C' e il nostro team sarà lieto di rispondere.