Llista enllaçada en C: com implementar una llista enllaçada en C?



el seu bloc sobre Llista enllaçada en C us presenta l'estructura de dades de Llista enllaçada en C i us ajuda a entendre la implementació de la llista enllaçada amb detall amb exemples.

Després de matrius, la segona estructura de dades més popular és Linked List. Una llista enllaçada és una estructura de dades lineal, formada per una cadena de nodes en què cada node conté un valor i un punter al següent node de la cadena. En aquest article, vegem com implementar una llista enllaçada a C.

Què és la llista enllaçada en C?

Una llista enllaçada és una estructura de dades lineal. Cada llista enllaçada té dues parts, la secció de dades i la secció d’adreça que conté l’adreça del següent element de la llista, que s’anomena node.





La mida de la llista enllaçada no és fixa i es poden afegir elements de dades a qualsevol ubicació de la llista. El desavantatge és que per arribar a un node, hem de recórrer tot el camí des del primer node fins al node que necessitem. La llista enllaçada és com una matriu, però a diferència d’una matriu, no s’emmagatzema de manera seqüencial a la memòria.

Els tipus més populars d’una llista enllaçada són:



  1. Llista d'enllaços individualment
  2. Llista d'enllaços dobles

Exemple de llista enllaçada

Format: [dades, adreça]

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



A l'exemple, el número 43 es troba a la ubicació 1000 i l'adreça es troba al node anterior. Així es representa una llista enllaçada.

Funcions bàsiques de la llista enllaçada

Hi ha diverses funcions que es poden implementar a la llista enllaçada de C. Intentem comprendre-les amb l’ajut d’un programa d’exemple.En primer lloc, creem una llista, la mostrem, la inserim en qualsevol ubicació, la suprimim. El següent codi us mostrarà com realitzar operacions a la llista.

#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 choice while (1) {printf ('n MENU n') printf ('n 1. Crea n') printf ('n 2. Mostra n') printf ('n 3. Insereix a el principi n ') printf (' n 4. Insereix al final n ') printf (' n 5. Insereix a la posició especificada n ') printf (' n 6. Suprimeix del principi n ') printf (' n 7. Suprimeix des del final n ') printf (' n 8. Esborra de la posició especificada n ') printf (' n 9. Surt n ') printf (' n ----------------- --------------------- n ') printf (' Introduïu la vostra elecció: t ') scanf ('% d ', & elecció) commutador (elecció) {cas 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 Elecció incorrecta: 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 ('nIntroduïu el valor de les dades del 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 (' nEls elements de la llista són: 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 ('nIntroduïu el valor de dades per al node: 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àg rintf ('nIntroduïu el valor de les dades del 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 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 ('nIntroduïu la posició per inserir el nou node: t') scanf ('% d') , & pos) printf ('nIntroduïu el valor de les dades del node: 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 ('nPosició no trobada: [Manejar amb cura] n') tornar}} 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'element suprimit és:% dt ', ptr-> info) lliure (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'element suprimit és:% dt', ptr-> info) lliure (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nL'element suprimit és:% dt', ptr-> info) lliure (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLa llista és buida: n') exit (0)} else {printf ('nIntroduïu la posició del node a suprimir : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nL'element suprimit és:% dt ', ptr-> info) lliure (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nL'element suprimit és: % dt ', ptr-> info) gratis (ptr)}}}

La primera part d’aquest codi és crear una estructura. Es crea una estructura de llistes enllaçades perquè pugui contenir les dades i l'adreça segons les necessitem. Això es fa per donar al compilador una idea de com ha de ser el node.

struct node {int info struct node * next}

A l’estructura, tenim una variable de dades anomenada info per contenir dades i una variable de punter per apuntar a l’adreça. Hi ha diverses operacions que es poden fer en una llista enllaçada, com ara:

  • crear()
  • display ()
  • insert_begin ()
  • insert_end ()
  • ] insert_pos ()
  • delete_begin ()
  • delete_end ()
  • delete_pos ()

Aquestes funcions són anomenades per la funció principal basada en el menú. A la funció principal, prenem l'entrada de l'usuari en funció de l'operació que l'usuari vol fer al programa. A continuació, l’entrada s’envia al cas de commutació i es basa en l’entrada de l’usuari.

Segons quina entrada es proporciona, es cridarà la funció. A continuació, tenim diferents funcions que cal resoldre. Vegem cadascuna d’aquestes funcions.

Funció de creació

En primer lloc, hi ha una funció de creació per crear la llista enllaçada. Aquesta és la manera bàsica de crear la llista enllaçada. Ens permet veure el codi.

sas programació introducció conceptes bàsics
void create () {struct node * temp, * ptr printf ('nEnter the value data 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}}

Sortida

Insereix - Llista enllaçada - Edureka

En primer lloc, es creen dos indicadors del tipus node, ptr i temp . Prenem de l’usuari el valor que cal afegir a la llista enllaçada i l’emmagatzemem a la part d’informació de la variable temp i assignem la temperatura de la següent que és la part d’adreça a nul·la. Hi ha un punter d’inici que manté l’inici de la llista. A continuació, comprovem l’inici de la llista. Si l’inici de la llista és nul, assignem temp al punter d’inici. En cas contrari, anem fins a l'últim punt on s'han afegit les dades.

Per a això, assignem ptr el valor inicial i travessa fins ptr-> següent = nul . A continuació, assignem ptr-> següent l'adreça de la temp. De manera similar, es dóna un codi per inserir-lo al principi, inserir-lo al final i inserir-lo en una ubicació especificada.

Funció de visualització

Aquí teniu el codi per a la funció de visualització.

void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nEls elements de la llista són: n') mentre (ptr! = NULL) {printf ('% dt', ptr-> informació) ptr = ptr-> següent}}}

Sortida

A la funció de visualització, primer comprovem si la llista està buida i retornem si està buida. A la part següent, assignem el valor inicial a ptr. A continuació, executem un bucle fins que ptr és nul i imprimim l'element de dades per a cada node, fins que ptr sigui nul, que especifica el final de la llista.

Funció Suprimeix

Aquí teniu el fragment de codi per suprimir un node de la llista enllaçada.

void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLa llista és buida: n') exit (0)} else {printf ('nIntroduïu la posició del node a suprimir: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nL'element suprimit és:% dt ', ptr-> info ) gratuït (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosició no trobada: n') return}} temp-> next = ptr-> next printf ('nLa l'element suprimit és:% dt ', ptr-> info) lliure (ptr)}}}

Sortida

En el procés de supressió, primer comprova si la llista està buida, si sí, existeix. Si no està buit, demana a l'usuari que esborri la posició. Un cop l'usuari entra a la posició, comprova si és la primera posició, en cas afirmatiu que assigna ptr per iniciar i mou el punter d'inici a la següent ubicació i elimina ptr. Si el la posició no és zero , llavors executa un bucle for des de 0 fins a la posició introduïda per l'usuari i emmagatzemada al fitxer pos variable. Hi ha una declaració if per decidir si la posició introduïda no és present. Si ptr és igual a nul , llavors no és present.

Nosaltres assignar ptr a temp al bucle for i ptr passa a la part següent. Després d'això, quan es troba la posició. Fem la variable temp per mantenir el valor de ptr-> següent saltant-se així el ptr. A continuació, se suprimeix ptr. De la mateixa manera, es pot fer per a l'eliminació del primer i l'últim element.

Llista doblement enllaçada

Es diu la llista doblement enllaçada perquè n’hi ha dues indicadors , un punt al següent node i altres punts al node anterior. Les operacions realitzades en doblement enllaçades són similars a les d'una llista enllaçada individualment. Aquí teniu el codi per a les operacions bàsiques.

#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Posició anterior Posició següent} void Insereix (int x, Llista l, Posició p) {Posició 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 Suprimeix (int x, Llista l) {Posició p, p1, p2 p = Cerca (x, l) si (p! = NUL) {p1 = p -> anterior p2 = p -> següent p1 - > següent = p -> següent si (p2! = NULL) // si el node no és l'últim node p2 -> anterior = p -> anterior} else printf ('L'element no existeix !!! n')} void Mostra (Llista l) {printf ('Els elements de la llista són ::') Posició p = l-> següent mentre (p! = NUL) {printf ('% d ->', p-> e) p = p- > següent}} int main () {int x, pos, ch, i Llista l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> anterior = NULL l-> next = NULL Llista p = l printf ('IMPLANTACIÓ DE LISTA DOBLE ENLLAÇADA IST ADTnn ') fer {printf (' nn1. CREAR 2. ESBORRAR 3. VISUALITZAR 4. QUITnn Introduïu l'opció :: ') scanf ('% d ', & ch) commutador (ch) {cas 1: p = l printf (' Introduïu l'element a inserir :: ') scanf ('% d', & x) printf ('Introduïu la posició de l'element ::') scanf ('% d', & pos) per a (i = 1 isegüent} Insereix (x, l, p) cas de ruptura 2: p = l printf ('Introduïu l'element que s'ha de suprimir ::') scanf ('% d', & x) Suprimeix (x, p) cas de trencament 3: Mostra (l) trencar}} mentre que (cap<4) } 

Sortida

Per tant, com podeu veure, el concepte d’operacions és bastant senzill. La llista doblement enllaçada té les mateixes operacions que la llista enllaçada individualment en llenguatge de programació C. L'única diferència és que hi ha una altra variable d'adreça que ajuda a recórrer millor la llista en una llista doblement enllaçada.

Espero que hagueu entès com realitzar operacions bàsiques en una llista doblement enllaçada a C.

el millor ide de Java per Linux

Si voleu aprendre Llista enllaçada a Java, aquí teniu un .

Si teniu cap pregunta, no dubteu a fer-vos totes les vostres preguntes a la secció de comentaris de 'Llista enllaçada en C' i el nostre equip estarà encantat de respondre-us.