Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: dacima99 en 22 Marzo 2018, 19:28 pm



Título: Se puede imprimir lista simplemente enlazada al reves
Publicado por: dacima99 en 22 Marzo 2018, 19:28 pm
Si tengo una lista simplemente enlazada dinámica, ¿puedo imprimir info desde el último nodo hasta el primero?

Código:
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



Título: Re: Se puede imprimir lista simplemente enlazada al reves
Publicado por: animanegra en 22 Marzo 2018, 20:04 pm
¿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.


Título: Re: Se puede imprimir lista simplemente enlazada al reves
Publicado por: ThunderCls en 22 Marzo 2018, 20:11 pm
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


Título: Re: Se puede imprimir lista simplemente enlazada al reves
Publicado por: Serapis en 22 Marzo 2018, 21:04 pm
Poderse, se puede... pero sin cambios es ineficiente.

aquí como:
Código:
    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.


Título: Re: Se puede imprimir lista simplemente enlazada al reves
Publicado por: MAFUS en 22 Marzo 2018, 23:25 pm
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.

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <locale.h>
  4.  
  5. typedef struct tnodo {
  6.    int numero;
  7.    struct tnodo *siguiente;
  8. } nodo;
  9.  
  10. void lista_add(nodo **raiz, int numero) {
  11.    nodo *actual = *raiz;
  12.    nodo *aux = malloc(sizeof(nodo));
  13.  
  14.    aux->numero = numero;
  15.    aux->siguiente = NULL;
  16.  
  17.    if(!actual)
  18.        *raiz = aux;
  19.    else {
  20.        while(actual->siguiente)
  21.            actual = actual->siguiente;
  22.        actual->siguiente = aux;
  23.    }
  24. }
  25.  
  26. void lista_imprimir(nodo *raiz) {
  27.    if(raiz) {
  28.        printf("%d\n", raiz->numero);
  29.        lista_imprimir(raiz->siguiente);
  30.    }
  31. }
  32.  
  33. void lista_imprimir_invertido(nodo *raiz) {
  34.    if(raiz) {
  35.        lista_imprimir_invertido(raiz->siguiente);
  36.        printf("%d\n", raiz->numero);
  37.    }
  38. }
  39.  
  40. nodo * lista_nueva() {
  41.    return NULL;
  42. };
  43.  
  44. void lista_eliminar(nodo **raiz) {
  45.    if(*raiz) {
  46.        lista_eliminar(&(*raiz)->siguiente);
  47.        free(*raiz);
  48.        *raiz = NULL;
  49.    }
  50. }
  51.  
  52. int main() {
  53.    int i;
  54.    nodo *lista = lista_nueva();
  55.  
  56.    setlocale(LC_ALL, "spanish"); // Cosas mías para que windows saque acentos.
  57.  
  58.    for(i=1; i<=10; ++i)
  59.        lista_add(&lista, i);
  60.  
  61.    puts("Lista del derecho:");
  62.    lista_imprimir(lista);
  63.  
  64.    puts("\n");
  65.  
  66.    puts("List del revés:");
  67.    lista_imprimir_invertido(lista);
  68.  
  69.    lista_eliminar(&lista);
  70. }