Se puede imprimir lista simplemente enlazada al reves

Iniciado por dacima99, 22 Marzo 2018, 19:28 PM

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

dacima99

Si tengo una lista simplemente enlazada dinámica, ¿puedo imprimir info desde el último nodo hasta el primero?


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

typedef struct{
Node *firstnode;
int size;
}List;


¿Supongo que si que es posible, no?
Es decir, supongamos que creamos una función donde pasamos la lista por referencia, luego guardamos en un array de punteros todos los nodos de la lista. Después simplemente hemos de imprimir el array al inrevés y listo. Entonces no es necesario que el nodo tenga un puntero a previous o  la estructura List tenga un puntero a el último estado.

Si no estoy en lo correcto agradecería que me corrigieran.

Muchas gracias,

:D


animanegra

¿Y de cuantos punteros haces el array?
Si te vas a pasear por el array para primero contar el numero de punteros, reservar la memoria del array y despues volver a recorrerlo para meter los punteros en el array para poder despues recorrer el array al reves, igual date un paseo por la lista enlazada cambiando los punteros siguiente y cambialos por los anteriores y lo recorres en sentido inverso.
Osea, mayormente, hazte una funcion que sea invierte punteros. y despues recorres el array invertido con tu funcion normal de imprimir.
No se si me explico.

42
No contesto mensajes por privado, si tienes alguna pregunta, consulta o petición plantéala en el foro para que se aproveche toda la comunidad.

ThunderCls

#2
Si tuvieras un puntero al siguiente nodo y otro al anterior ya no seria una lista "simplemente enlazada" sino "doblemente enlazada"  :xD
Una idea es crearte una funcion que trabaje con tu lista y cambie el sentido de los punteros (los punteros del nodo siguiente por el anterior):

1->2->3->4->5->NULL

quedaria como:

NULL<-1<-2<-3<-4<-5

una posible logica seria:

// antes de modificar curr->next
next = curr->next;

// cambias el sentido del puntero
curr->next = prev;

prev = curr;
curr = next;

Saludos
-[ "...I can only show you the door. You're the one that has to walk through it." – Morpheus (The Matrix) ]-
http://reversec0de.wordpress.com
https://github.com/ThunderCls/

Serapis

Poderse, se puede... pero sin cambios es ineficiente.

aquí como:

    entero k = lista.Count-1
    nodo n

    bucle mientras (k>0)   
        n = nodoRaiz
        bucle desde 0 hasta k
            n = n.siguiente   
        fin bucle

        imprimir n.valor
        k -=1
    fin bucle

Suongamos que la lista tiene 6 elementos (0-5)
Fíjate, que primero debe llegar hasta el 5, para imprimirlo.
luego hasta el 4 y lo imprime
luego hasta el 3 y lo imprime
luego hasta el 2 y lo imprime
...
Cada nodo se visita entre 1 y n veces, en promedio cada nodo se visita: veces = ((n+1)\2)
Cuando una lista doblemente enlazada, o simplemente enlazada pero hacia abajo (esto es, al añadir nodos, se añaden en raíz, en vez de al final), basta con visitar cada nodo 1 sola vez.

MAFUS

Pues sí, todo depende del orden en que le indiques que pase al siguiente elemento y escriba lo que hay guardado en el nodo.

Algo así. Fíjate en lista_imprimir y lista_imprimir_invertido.


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

typedef struct tnodo {
    int numero;
    struct tnodo *siguiente;
} nodo;

void lista_add(nodo **raiz, int numero) {
    nodo *actual = *raiz;
    nodo *aux = malloc(sizeof(nodo));

    aux->numero = numero;
    aux->siguiente = NULL;

    if(!actual)
        *raiz = aux;
    else {
        while(actual->siguiente)
            actual = actual->siguiente;
        actual->siguiente = aux;
    }
}

void lista_imprimir(nodo *raiz) {
    if(raiz) {
        printf("%d\n", raiz->numero);
        lista_imprimir(raiz->siguiente);
    }
}

void lista_imprimir_invertido(nodo *raiz) {
    if(raiz) {
        lista_imprimir_invertido(raiz->siguiente);
        printf("%d\n", raiz->numero);
    }
}

nodo * lista_nueva() {
    return NULL;
};

void lista_eliminar(nodo **raiz) {
    if(*raiz) {
        lista_eliminar(&(*raiz)->siguiente);
        free(*raiz);
        *raiz = NULL;
    }
}

int main() {
    int i;
    nodo *lista = lista_nueva();

    setlocale(LC_ALL, "spanish"); // Cosas mías para que windows saque acentos.

    for(i=1; i<=10; ++i)
        lista_add(&lista, i);

    puts("Lista del derecho:");
    lista_imprimir(lista);

    puts("\n");

    puts("List del revés:");
    lista_imprimir_invertido(lista);

    lista_eliminar(&lista);
}