Listas doblemente enlazadas

Iniciado por AlexWolf097, 23 Octubre 2017, 01:13 AM

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

AlexWolf097

estoy estudiando estructura de datos en c++, pero llegue al momento en donde no se esta imprimiendo de forma correcta mi lista, en la primera opcion, que es "Insertar()" se imprime solo el primer elemento de mi lista, y en la segunda opcion que es "Fina()" solo se imprime correctamente hasta el tercer elemento.

Agradeceria mucho su ayuda si me pudieran orientar para encontrar mi error.

#include <bits/stdc++.h>
using namespace std;

struct Nodo
{
    int dato;
    Nodo *sig;
    Nodo *ant;
};

typedef struct Nodo *Tlista;
typedef struct Nodo *pNodo;

Tlista lista = NULL;

void Imprimir(Tlista);
void Insertar(Tlista &);
void Final(Tlista &);

int main()
{
    int opc;
    while(1)
    {
        cout << "L I S T A S  D O B L E S" << endl
             << "1) Insertar al incio" << endl
             << "2) Insertar al final" << endl
             << "10) Salir" << endl
             << "Seleccione Opcion: ";
        do
        {
            cin >> opc;
        }while(opc < 1 && opc > 10);

        switch(opc)
        {
        case 1:
            Insertar(lista);
        break;

        case 2:
            Final(lista);
        break;

        case 10:
            exit(0);
        break;

        default:
            cout << "Opcion Invalida" << endl;
            system("pause");
            system("cls");
        break;
        }
    }
}

void Imprimir(Tlista lista)
{
    pNodo q = lista;

    while(q != NULL)
    {
        cout << q -> dato << " ";
        q = q -> sig;
    }

    cout << endl;
    system("pause");
    system("cls");
}

void Insertar(Tlista &lista)
{
    pNodo q = new struct Nodo ;
    int x;

    cout << "Introduce el dato: ";
        cin >> x;

    q -> dato = x;

    if(lista == NULL)
    {
        lista = q;
        q -> sig = NULL;
        q -> ant = NULL;
    }
    else
    {
        q -> sig = lista;
        q -> ant = lista -> ant;
        lista -> ant = q;
    }

    Imprimir(lista);
}

void Final(Tlista &lista)
{
    pNodo q = new struct Nodo ;
    int x;

    cout << "Introduce el dato: ";
        cin >> x;

    q -> dato = x;

    if(lista == NULL)
    {
        lista = q;
        q -> sig = NULL;
        q -> ant = NULL;
    }
    else
    {
        q -> sig = lista -> sig;
        lista -> sig = q;
        q -> ant = lista;
    }

    Imprimir(lista);
}

Serapis

#1
Cuando señalas insertar (al inicio o al final), no debieras imprimir la lista, eso haría inecesario en el menú, la opción imprimir... (que yo añadiría esa opción al menú) bien que mientras diseñas si tengas activa esa línea para ir verificando que las operaciones se realizan correctamente...
entonces lo pondrías tras la llamada en el menú, antes del  Break...

El nombre de 'Final', no es para nada ilustrativo de su funcionalidad. Insertar, siempre es añadir delante de algún item, OK, pero al final puedes llamarlo simplemente Añadir... sin más expecificaciones, al añadir, siempre se añade al final.

Por último, no veo que lleves la cuenta de la cantidad de ítems en la lista... es más eficiente preguntar que 'Si Items=0', que 'Si Lista es null', y añadir al comienzo puede indicarse con un 0 y añadir al final con -1, y Añadir en cualquier otra posición (insertar), con cualquier otro valor entre 1 e ítems -2
Un control de la cuenta de nodos en la lista, aunque no es imprescindible, si es más que aconsejable, simplifica la lógica y funcionalidad de la misma a cambio de algo de código extra.



Y ahora yendo a tus dudas:
- Tu función 'Final' no está bien implementada... Trato de explicarte con un sencillo ejemplo, sea una lista con varios elementos, consideremos estos 3:  Marte -> Jueves -> domingo
vemos que domingo.anterior = jueves
y vemos que Jueves.siguiente = domingo
Ahora insertemos un elemento en medio, por ejemplo viernes.
Las operaciones a realizar serán 4, verás:

viernes.siguiente = domingo
domingo.anterior = viernes
Viernes.anterior = jueves
Jueves.siguiente = viernes

Es decir se necesita apuntar desde el nuevo elemento a los extremos donde se inserta, y se necesita apuntar desde los extremos donde se inserta al nuevo elemento. Siempre son 4 asignaciones (si está en medio)
Si el nodo a añadir es un extremo, solo necesita 2 asignaciones (si la lista doblemente enlazada no es circular)...




Modifico tu código a pseudocódigo para hacerlo más legible:
Esta función está bien, salvo la redundancia de establecer nulos, donde ya los hay y no llevar cuenta de ítems que tiene la lista.

   if (lista = Nulo)
       lista = q  //OK
       q.sig = Nulo  //Innecesario
       q.ant = Nulo  //Innecesario
   else
       q.sig = lista //OK
       q.ant = lista.ant; //Innecesario
       lista.ant = q //OK
    }
¿No cuentas los items que lleva la lista.... por qué?


Así tu función externa podría ser:

Funcion Añadir(dato, posicion)
  nodo n

  n.Dato = dato
  // o bien como en tu caso operas por consola, desde aquí solicitas la entrada del dato, 1 solo sitio para las 3 funciones internas (y retiras el parámetro dato de la funcion)

  Si (posicion=0) ó (Items=0) luego
      AñadirAlComienzo(n)
  PeroSi (posicion menor que 0) ó (posicion mayor o igual que Items-1) luego
      AñadirAlFinal(n)
  Sino
      Insertar(n, posicion)
  Fin si
  actual =n
Fin funcion

Y tus funciones internas serían ahora: AñadirAlFinal, AñadirAlComienzo, Insertar

Fíjate que ahora insertar exigirá localizar el ítem en la posición pedida. al caso actual es una buena estrategia, porque recordando su posición, puede partirse desde 0 hasta actual desde actual hasta 0, desde actual hasta último, desde último hasta actual, según quede más cerca de un nodo u otro de los 3 implicados: primero, actual ó último...

Reviso tu función 'Final' (Añadir):
Simplifico tu código hacia pseudocódigo, más sencillo de ver así...

funcion Final
   ...
   if(lista = Nulo)
       lista = q
       q.sig = Nulo //Innecesario
       q.ant = Nulo  //Innecesario
   else
       //3 líneas 3 errores...
       q.sig = lista.sig  //Innecesario, asignar nulo al final de la lista no es preciso, el nodo recién creado ya tiene su .siguiente en nulo. Pero además es un error.
       lista.sig = q  //NO lista.sig apunta al segundo nodo, no al último.
       q.ant = lista //NO, le estás diciendo que el anterior a este nodo es el primer nodo.
   }
¿Igual que la otra, no llevas cuenta de los ítems, por qué?
Fin funcion


Esta función te falla... porque
Una lista, basta que tenga el nodo 'inicial, pero si tienes una lista doblemente enlazada, debieras mantener referencia al primer y último elemento.
Cuando apuntas a lista (tu nodo lista), estás apuntando al primero nodo en ella, entonces lista.siguiente apunta al siguiente nodo en la lista, es decir al segundo nodo, no al último. Será el último solo si la lista tiene 2 ítems...
Entonces tu función Final, está insertando nodos incorrectamente... usa nombre días o de meses y haz las asignaciones en papel para ver como va quedando concada inserción, para entender el problema.



La implementación debe mantener referencia al primer y último nodo, y deja de llamar lista al primer nodo, porque eso te 'nubla la vista'.

Aquí una sencilla implementación con referencias al primero, último y actual nodos, además lleva la cuenta de ítems...
Estos son los miembros en la clase, debajo los métodos...

nodo Primero   //primer nodo de la lista.
nodo Ultimo     // Ultimo nodo de la lista.
nodo Actual     // Nodo actual, también podría ser el primero y el último

entero ixActual  // indice que ocupa el nodo en la lista.
entero Items   // Cantidad de nodos que contiene la lista actualmente.


Función externa para añadir nodos...
Con cada añadido, se hace actual al nodo añadido, y se conserva su posición.

Funcion Añadir(Posicion)
   nodo n
   entero dato

   dato = PedirDatoAlUsuario

   Si (Items=0) luego
       CrearLista(n)
       ixActual=0
   Sino
       Si (posicion=0) luego
           AñadirAlComienzo(n)
           ixActual=0
       PeroSi ((posicion < 0) ó (posicion >(Items-2))) luego
           AñadirAlFinal(n)
           ixActual= items
       Sino
          Insertar(n, posicion)
          ixActual= posicion
       Fin si
   Fin Si
   actual = n
   Items +=1
Fin Funcion


Añade el primer nodo a la lista.

funcion CrearLista (nodo n)
   primero = n
   ultimo = n  // vuando solo hay 1 nodo en la lista, es el primero y también el último.
Fin funcion


Añade un nodo al comienzo de la lista.

Funcion AñadirAlComienzo(nodo n)
   n.siguiente = primero
   primero.anterior = n
   primero = n
   Si (items=1) luego
       ultimo.anterior = n //el primero
   fin si
Fin funcion


Añade un nodo al final de la lista.

Funcion AñadirAlFinal(nodo n)
   n.anterior = ultimo
   ultimo.siguiente = n
   ultimo = n
   Si (items = 1) luego
       primero.siguiente = n // el ultimo
   Fin si
Fin si


Insertar un nodo en posiciones distintas del último y el primero.

Funcion Insertar(nodo n, entero posicion)
   nodo busca

   busca = BuscarNodo(posicion)

   n.anterior = busca.anterior
   n.siguiente = busca
   busca.anterior.siguiente = n
   busca.anterior = n    
Fin funcion


Busca desde el primero hasta hallar el nodo en la posición pedida.

nodo = funcion BuscarNodo(entero posicion)
   nodo n
   entero k

   n= primero
   mientras (k < posicion)
       n = n.siguiente
       k +=1
   repetir
   devolver n
Fin funcion


Búsqueda optimizada, basada en el actual... para una lista con pocos elementos no se nota, cuanto más crece la lista, más útil resulta...

nodo = funcion BuscarNodo(entero posicion)
   nodo n
   entero k, s

   Si (posicion <= ixactual) luego //está entre el primero e ixactual
       Si ((posicion-ixactaul) < (ixActual /2)) luego //si está más cerca de ixActual que de 0...
           n = ixactual  
           k = ixactaul
           s = -1
       Sino
           n = primero
           k = 0
           s = 1
       fin si
   Sino //está entre ixactual y el último
       k = (items-ixActual)
       Si ((k/2) => (k - (posicion-ixactaual))) luego // si está más cerca de ixActual que del final
           n = ixactual  
           k = ixactaul
           s = 1
       Sino
           n = ultimo
           k = Items-1
           s = -1
       fin si        
   Fin si
   
   Si (s = 1) luego //busca hacia arriba (itera sobre siguiente
       mientras (k < posicion)  // <> es distintode
           n = n.siguiente
           k +=1
       repetir
   Sino  //busca hacia abajo (itera sobre anterior)
       mientras (k>posicion)
           n = n.anterior
           k -=1
       repetir
   devolver n
Fin funcion


Dejo a tu cargo Imprimir(DesdePosicion, HastaPosicion), con valores Imprimir(0,-1) debería imprimir toda la lista.

AlexWolf097

Muchas gracias por los comentarios, seguire practicando para dominar este tema