elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Listas doblemente enlazadas
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Listas doblemente enlazadas  (Leído 4,898 veces)
AlexWolf097

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Listas doblemente enlazadas
« en: 23 Octubre 2017, 01:13 am »

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.

Código:
#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);
}


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: Listas doblemente enlazadas
« Respuesta #1 en: 23 Octubre 2017, 17:33 pm »

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


« Última modificación: 23 Octubre 2017, 17:42 pm por NEBIRE » En línea

AlexWolf097

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Listas doblemente enlazadas
« Respuesta #2 en: 25 Octubre 2017, 23:45 pm »

Muchas gracias por los comentarios, seguire practicando para dominar este tema
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[SRC-C99] Listas doblemente enlazadas (varias funciones).
Programación C/C++
BlackZeroX 1 2,741 Último mensaje 15 Enero 2013, 07:18 am
por BlackZeroX
Manejar listas doblemente enlazadas en C desde ASM
ASM
danndres 1 2,369 Último mensaje 13 Octubre 2014, 23:26 pm
por xv0
Ayuda para crear Listas doblemente enlazadas
Programación C/C++
kur79 0 1,993 Último mensaje 25 Octubre 2014, 16:35 pm
por kur79
Ayuda! Listas Doblemente Enlazadas
Programación C/C++
mordeki_99 0 1,572 Último mensaje 30 Noviembre 2015, 00:45 am
por mordeki_99
Programa en c++ listas doblemente enlazadas
Programación C/C++
Diosa21 0 9,636 Último mensaje 29 Marzo 2017, 19:48 pm
por Diosa21
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines