Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: ShadowA7X en 24 Noviembre 2014, 23:59 pm



Título: Por que ésta pequeña función de invertir una lista enlazda funciona?
Publicado por: ShadowA7X en 24 Noviembre 2014, 23:59 pm
Hola chicos/as que tal? espero que estén bien. Vine nuevamente aquí porque uds siempre me sacan las dudas precisas que tengo, y debo aclarar que les estoy muy agradecido. Ahora bien necesito que por favor alguien me explique (si es posible con manzanitas o dibujitos xd) por qué ésta función de invertir lista funciona tan bien:





Código
  1.  
  2. typedef struct NODO{
  3.  
  4. char *nombre;
  5. struct NODO *sgte;
  6.  
  7. }nodo;
  8.  
  9. void invertirlista(nodo **inicio){
  10.  
  11. nodo *aux,*next;
  12.  
  13. aux=*inicio;
  14. *inicio=NULL;
  15.  
  16. while(aux!=NULL){
  17.  
  18. next=aux->sgte;
  19. aux->sgte=*inicio;
  20. *inicio=aux;
  21. aux=next;
  22.  
  23. }
  24. }


El typedef lo coloqué por si alguien siente necesario saber como fue hecha la lista (aunque verdaderamente no creo que importe para la pregunta que estoy haciendo).Sé como crear,mostrar y eliminar listas y nodos, he intentado esquematizar ésta función tan corta pero no he podido aclararle a mi cabeza como funciona. De antemano muchas gracias por su ayuda  :)



Título: Re: Por que ésta pequeña función de invertir una lista enlazda funciona?
Publicado por: avesudra en 25 Noviembre 2014, 01:01 am
Hola ShadowA7X, es un código muy limpio y la verdad bastante bueno. Te pongo un ejemplo práctico de lo que hace el algoritmo. Tenemos una lista con 4 nodos (o lista da igual como los llames):

P Q R S

Sabemos que esos nodos tienen un puntero al nodo siguiente, y esos estan tal que asi:
P -> Q , Q -> R , R -> S y S -> NULL

(entendiendo esa flechita por, "el nodo P tiene un puntero que apunta a Q")

Lo que hace esto es invertir el sentido, es decir, que P apunte a NULL, Q apunte a P , R apunte a Q y S apunte a R. (entendiendo por apuntar, que el nodo tiene un puntero que apunta a otro nodo). Realmente no modifica la lista en sí, sino a quienes apuntan sus nodos, el meollo del asunto está aqui:
Código
  1. next=aux->sgte;
  2. aux->sgte=*inicio;

Saludos.