Eliminar ultimo elemento de la lista enlazada C++

[nurnain]

//Hola!! Necesito ayuda con este enunciado pues la verdad no se como lograr eliminar el ultimo elemento de la lista espero que me puedan ayudar , si me pueden decir que debo hacer o me podrían elaborar el código seria genial.

//Borrar ultimo elemento de la Lista enlazada en c++



#include <stdlib.h>
#include <stdio.h>
#define nuevo_nodo (struct nodo *)malloc(sizeof(struct nodo))
struct nodo {
   int info; struct nodo *sig;
} *c, *p, *q;
int mostrar_nodo(struct nodo *s) {
   printf("%d",s->info); return 0;
}
int mostrar_lista(struct nodo *r){
   printf("{ "); mostrar_nodo(r);
   while (r->sig!=NULL){
   printf(", "); mostrar_nodo(r->p); r=r ->sig;
   }
   
   printf(" }"); return 0;
}
int main() {         c = nuevo_nodo;
   c->info=36;      p=nuevo_nodo;   c->sig=p;
   p->info=18;      q=nuevo_nodo;   p->sig=q;
   q->info=45;      p=nuevo_nodo;   q->sig=p;
   p->info=123;   q=nuevo_nodo;   p->sig=q;
   q->info=9;      p=nuevo_nodo;   q->sig=p;
   p->info=54;                  p->sig=NULL;
   
   printf("\n\n   "); mostrar_lista(c);



system ("pause");

}

[Serapis]

La eliminación del último nodo, suele ser la eliminación más sencilla (detrás de eliminar el último cuando además es el único).

Piensa en forma manual e imagina que fuera una cadena (si, con eslabones metálicos), cada vez que quieras quitar un eslabón piensa cuantas manos necesitas para agarrar la parte que interesa... considera todos los pasos que hay que hacer y el orden correcto de los mismos.

Para eliminar un nodo en cualquier posición, debes posicionarte en la posición previa, para establecer su nodo siguiente a nulo... si además está intermedio (antes establecer la referencia siguiente de él a nulo), se requiere tener acceso al siguiente a eliminar... para luego poder volver a conectar la 'cadena rota' (ha quedado rota por culpa de él) por el nodo eliminado...

En la lista enlazada, hay que pensar además si está doble o simplemente enlazada. El caso más sencillo es empezar con listas simplemente enlazadas, que e slo que se asume mirando tu código...

* Nota: Aquí se supone a Raiz como un nodo oculto, que no contabiliza en la lista, cuando no conviene que sea el caso, puede considerarse como nulo y entenderse raiz.siguiente como el nodo raiz.
* Nota: Que si no se mantiene una cuenta de los nodos que existen en la lista, cambia ligeramente, pués no hay forma de saber a priori si un nodo es el último, salvo llegando a él desde la raíz, o un 'nodo actual', es decir un sobrecoste en eficiencia a causa del recorrido, que siempre deberá hacerse y que por tanto es desconocido.

Código [Seleccionar] Expandir

funcion EliminarNodo(x)
   Si numNodos = 0 salir   // la lista está vacía...

   Si (x = numNodos) //equivale a eliminar el último
       Si (x = 0)  // además es el único
              raiz.Siguiente = nulo
       sino
           p = raiz
           n = p.siguiente
           Hacer  mientras (n.siguiente <> Nulo)
               p = n
               n = n.siguiente      
           repetir
           n = nulo
           p.siguiente = nulo
       fin si
   Sino   // en estos casos, al eliminar uno exige conectar los que vienen detrás con el previo.
       Si (x = 0) // elimina el primero, pero hay más detrás
           Si numNodos = 1
               raiz.siguiente = nulo  // lista vacía
           SiNo
               n = raiz.siguiente
               raiz.siguiente = n.siguiente  // el nodo en raíz será el que antes era el 2º.
               n.siguiente = nulo // eliminar la referencia a la que apunta el que se pretende eliminar
               n = nulo   // se elimina el que antes era el 1º
           fin si    
       sino
           y = 0
           n = raiz.siguiente
           hacer mientras (y < x)
                y +=1
                p = n   // mantener el previo (agarrar con una 'mano' el eslabón previo al que se desea eliminar)
                n = n.siguiente
           siguiente
           //(a estas alturas) sabemos que no es el último, por eso esto no
dará error
           n = n.siguiente  // agarrar con 'otra mano' al eslabón siguiente al que se quiere eliminar
           p.siguiente.siguiente = nulo  // eliminar el enlace del eliminado al siguiente
           p.siguiente = nulo // eliminar el deseado
           p.siguiente = n  // atar la cadena por los dos eslabones sueltos
       fin si
   fin si

   numNodos -= 1 //la cuenta hay que actualizarla adecuadamente siempre que se eliminen o añadan nodos.
fin funcion

* Nota: Que se puede optimizar, pero es más sencillo entender cuando no hay 'abreviaciones y omisiones por optimización', cuando el código es canónico, es más fácil seguir los pasos dados...

* Nota: Que aunque la función elimina por índicie, si se precisa puede ocultarse (dicha función, haciéndola privada) y crearse exprofeso funciones para eliminar el último nodo, etc...

Código [Seleccionar] Expandir


// Como se ve, simplemente se llama al último, por el índice que tiene.
funcion EliminarUltimo
   EliminarNodo(numNodos-1)
Fin Funcion

Funcion EliminarPrimero
   EliminarNodo(0)
Fin Funcion

...


* Nota: También como la simple adicción a la lista de un valor que mantenga la 'cantidad' total de nodos (aquí llamada numNodos), simplifica bastante las cosas y mantener actualizado dicho valor no es complicado.
Cuando:
--- Se crea la lista: numNodos = 0
--- Se añade un nodo: numNodos += 1
--- Se elimina un nodo: numNodos -= 1
--- Se vacía/elimina toda la lista: numNodos = 0
Igualmente resulta útil por tanto proveer una propiedad de lectura de la cantidad de nodos...

* Nota: Por último que también suele ser muy útil disponer de un nodo 'Actual' (comporta nodo e índice 'NodoActual' e 'IndiceActual'), que facilita el acceso, así si el que se quiere eliminar está antes del actual se accede desde raíz, si está después del actual, a través del actual... lo mismo al añadir cuando puede elegirse una posición arbitraria. Actual es aún más útil cuando la lista es doblemente enlazada, pues ya hay 4 puntos entre los que elegir iniciar el acceso (desde el primero --->, desde el actual <---, desde el actual --->, desde el último <---- ). Por lo mismo, que la 'cantidad' de nodos, se hace publico como propiedad de lectura, en tal caso también interesa tener público 'Actual', que en este caso puede además ser también de escritura. Así el acceso a un nodo de la lista es más eficiente (casi siempre) al coste de añadir código extra para mantener con vigencia el nodo actual y su índice (dicho índice puede variar según la posición que tenga cuando se añadan o eliminen nodos anteriores a dicha posición. El coste más caro de eliminar o añadir es cuando se elimina precisamente el actual, pero se contrarresta con el coste de acceso al mismo, que es tal caso es 0, por ser conocido...

Para pasarlo a código, te tocará leerlo y entenderlo... algo de esfuerzo por tu parte tendrás que poner, ¿no?.

[dijsktra]

Brevemente, amigo.
Las estructuras de datos, en tu caso una lista simplemente enlazda, solo exiten para emular algun tipo asbtracto de datos (pilas, colas, dobles colas ... e incluso listas como tipo abstracto, no como estructura de datos en si).


EDIT: No se hacer en C++. Te proporcion en C


Para tu caso he elegio la emulación parcial de una doble cola. Faltan unas operaciones, como push_front, pop_front , que por espacio omito. practica tu.

TE podra serviar para lo que quieres.


La operacion por la que estas interesado es

Código (c) [Seleccionar] Expandir


typedef struct _node
{
 int info;
 struct _node *next;
} *node;

typedef struct _deque
{
 node first;
 node last;
}deque;


void pop_back(deque *dq)
{
 assert(dq->last != NULL);
 node prev,act;
 for(prev=NULL,act=dq->first;act!=dq->last;act=act->next)
   prev=act;
 dq->last = prev;
 if (prev) prev->next=NULL;
 else dq->first=dq->last=NULL;
 free(act);
}



Y aqui una exhibicion del programa ejecutable

Código (c) [Seleccionar] Expandir



#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct _node
{
 int info;
 struct _node *next;
} *node;

typedef struct _deque
{
 node first;
 node last;
}deque;


int print(const deque *dq){
 printf("[ ");
 node p;
 for(p=dq->first;p!=NULL ; p=p->next)
   printf("%d ",p->info);
 printf(" ]");
 printf("\n");
 return 0;
}

void create(deque *dq)
{
 dq->first = dq->last = NULL ;
 return;
}

void push_back(deque *dq,int info)
{
 node n;
 if ((n = (node)malloc(sizeof(struct _node)))==NULL)
   {
     perror("malloc");
     exit(-1);
   }
 n->info = info;
 n->next = NULL;
 node prev;
 
 if (dq->last) dq->last->next = n ;
 dq->last= n;
 if (!dq->first) dq->first=dq->last;
 return;
}



int top(const deque *dq)
{
 assert(dq->last != NULL);
 return dq->last->info;
}

void pop_back(deque *dq)
{
 assert(dq->last != NULL);
 node prev,act;
 for(prev=NULL,act=dq->first;act!=dq->last;act=act->next)
   prev=act;
 dq->last = prev;
 if (prev) prev->next=NULL;
 else dq->first=dq->last=NULL;
 free(act);
}


int empty(const deque *dq)
{
 return dq->first == NULL;
}

void destroy(deque *dq)
{
 node p,aux;
 for(p=dq->first ;p;p=aux)
   {
     aux=p->next;
     free(p);
   }
 return ;
}

int main(int argc, char *args[] )
{
 int N=10;
 deque dq;
 create(&dq);
 for(int n=0;n<N;n++)
   push_back(&dq,n);
 for( ; !empty(&dq); pop_back(&dq)) print(&dq);
 print(&dq);
 destroy(&dq);
 return 0;

}



Y una preuba de ejecucion

Código [Seleccionar] Expandir


[ 0 1 2 3 4 5 6 7 8 9  ]
[ 0 1 2 3 4 5 6 7 8  ]
[ 0 1 2 3 4 5 6 7  ]
[ 0 1 2 3 4 5 6  ]
[ 0 1 2 3 4 5  ]
[ 0 1 2 3 4  ]
[ 0 1 2 3  ]
[ 0 1 2  ]
[ 0 1  ]
[ 0  ]
[  ]