Eliminar ultimo elemento de la lista enlazada C++

Foro de elhacker.net

Programación

Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)

Eliminar ultimo elemento de la lista enlazada C++

0 Usuarios y 1 Visitante están viendo este tema.

Páginas: [1]

Autor

Tema: Eliminar ultimo elemento de la lista enlazada C++ (Leído 5,363 veces)

nurnain

Desconectado

Mensajes: 1

Eliminar ultimo elemento de la lista enlazada C++

« en: 24 Enero 2020, 13:53 pm »

//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");

}


	En línea

Serapis

Colaborador

Desconectado

Mensajes: 3.351

Re: Eliminar ultimo elemento de la lista enlazada C++

« Respuesta #1 en: 25 Enero 2020, 17:22 pm »

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:

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:

// 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?.


« Última modificación: 25 Enero 2020, 17:32 pm por NEBIRE »	En línea

dijsktra

Desconectado

Mensajes: 110

Mr Edsger Dijsktra (Tribute to)

Re: Eliminar ultimo elemento de la lista enlazada C++

« Respuesta #2 en: 21 Marzo 2020, 01:48 am »

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

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

 
#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:

[ 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  ]
[  ]


« Última modificación: 21 Marzo 2020, 08:31 am por dijsktra »	En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)

Páginas: [1]

Ir a:

Mensajes similares
	Asunto	Iniciado por	Respuestas	Vistas	Último mensaje
	No se añade elemento nuevo en una lista enlazada Programación C/C++	NathanD	2	2,194	23 Abril 2013, 10:05 am por NathanD
	Insertar un elemento ordenadamente en una lista enlazada simple Programación C/C++	NathanD	4	26,587	27 Abril 2013, 14:25 pm por NathanD
	borrar elemento de la lista enlazada simple Programación C/C++	d91	2	3,273	9 Junio 2014, 13:44 pm por d91
	Eliminar nodo en lista enlazada: problema con el último nodo [C] Programación C/C++	Rhessus	2	5,297	20 Julio 2016, 06:08 am por Rhessus
	Borrar ultimo nodo lista simplemente enlazada Programación C/C++	robertoesimez	5	5,281	23 Marzo 2017, 07:22 am por MAFUS