Dually linked lists do not print well

1

I am studying data structure in c ++, but I get to the moment where my list is not being printed correctly, in the first option, which is "Insert ()", only the first element of my list is printed, and in the second option that is "Fine ()" only the third element is printed correctly.

I would greatly appreciate your help if you could guide me to find my 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);
}
    
asked by Alex 22.10.2017 в 23:11
source

3 answers

1

You are doing wrong filling the list, apply these quick corrections that I did:

for both cases, temp is declared in this way

pNodo temp = new struct Nodo ;

-To the method Insert this:

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

-For the Final method this:

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

    }
    else
    {
        temp=lista;
        while(temp -> sig != NULL)
        {
            temp = temp -> sig;
        }
        q -> sig = NULL;
        q -> ant = temp;
        temp -> sig = q;
    }

That's all, what happened was that you always assigned the data to "list" so you only had 3 numbers at most in the linked list.

    
answered by 23.10.2017 / 03:44
source
2

Apart from the corrections mentioned by eferion , there are other things you should keep in mind.

In C ++, struct is not part of the type.

In the C language, it is necessary to prepend struct before the name of a structure, because struct is part of the data type, but in C ++ this is not the case, therefore you can change your aliases to:

typedef Nodo *Tlista; // Sin anteponer 'struct'.
typedef Nodo *pNodo;  // Sin anteponer 'struct'.

Although I personally prefer this notation:

using Tlista = Nodo *;
using pNodo = Nodo *;

You confuse nodes with lists.

Do not you really find it odd that the list alias and the node alias are the same ? You are defining that a list ( Tlista ) is a pointer to node and a pointer to node ( pNodo ) is a pointer to node.

In other words: you are saying that a step is a ladder, or that a ladder and a step are interchangeable ... which makes no sense.

Create a List object.

To avoid the problem of the previous point, create a Lista object in which to add the methods that you have left now loose:

struct Lista
{
    void Imprimir() const;
    void Insertar();
    void Final();

private:
    struct Nodo
    {
        int dato;
        Nodo *sig = nullptr;
        Nodo *ant = nullptr;
    };

    Nodo *raiz = nullptr;
};

If you notice, the methods do not receive a node as a parameter, since the nodes with which the list will work are already contained in the object itself ( Lista::raiz ). I'm also using the null pointer literal ( nullptr ) since it is more appropriate and safe than the macro NULL and the node is a nested object within the list since there is no need to expose it outside the list.

Insertar and Final .

It is not clear to me that they do those functions, I think they are to grow the list on the right (lengthening Nodo::sig ) or on the left (lengthening Nodo::ant ), let's see your algorithms:

In Insertar .

You link all the nodes to the initial node, so you never create a list.

q -> sig = lista;
q -> ant = lista -> ant;
lista -> ant = q;

After inserting three data, your memory structure looks like this:

The next one of each node that you insert always points to the initial node, if it was a list each node will be linked only once. On the other hand it is clearly seen why when printing, only the initial node is printed: because the next one of the initial node is always null.

In Final .

You also link to the initial node, but in a more rare way:

    q -> sig = lista -> sig;
    lista -> sig = q;
    q -> ant = lista;

After inserting three data, your memory structure looks like this:

Therefore inserting from the data does not keep the order of insertion because you do not link correctly.

Conclusion

You should check your insertion algorithms. I advise you to draw some schemes like the ones that I give as an example to see what you are doing.

    
answered by 23.10.2017 в 08:14
1

C ++ is not C. In C ++, data structures (commonly called classes, although you use struct ) differ from those you have seen when learning C in which they have, among other things, builders (functions that allow you to initialize data structures automatically).

The normal thing when creating an object is that its pointers are initialized automatically to avoid detours :

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

  // Constructor por defecto
  Nodo()
    : sig(nullptr), ant(nullptr) // C++11 en adelante
    : sig(NULL), ant(NULL)       // C++03 y anteriores
  { }

  // Constructor para asignar el dato
  Nodo(int dato)
    : dato(dato), sig(nullptr), ant(nullptr)
  { }
};

On the other hand, in C ++ it is not necessary to use struct every two times three ... the language is, in that aspect, a bit more readable than C:

// sintaxis C
typedef struct Nodo *Tlista;
pNodo temp = new struct Nodo; // nota que en C habría que usar malloc

// sintaxis C++
typedef Nodo* TLista;
pNodo temp = new Nodo;    // Se invoca el constructor por defecto
pNodo temp = new Nodo(5); // Se invoca el segundo constructor

Well, if we take a look at the function Insertar :

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);
}  

We see that the else does something weird: You add an element before lista and then print from lista ... you are ignoring the item you just added. Assuming you have implemented the default constructor the code should look like this:

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

    cout << "Introduce el dato: ";
        cin >> q->dato;

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

    lista = q;

    Imprimir(lista);
}

Note that the pointer lista always is updated. It is necessary since it is assumed that always the nodes will be added to the top of the list.

On the other hand, the function Final also has its problems:

else
{
    q -> sig = lista -> sig;
    lista -> sig = q;
    q -> ant = lista;
}

Here the code is adding the new node in the second position, not in the last one. In addition, it does not do so well since the one that happens to be the third node has ant to node lista (you have not updated it).

What you have to do is locate the last node in the list and add the new node behind it. This is easily achieved with a while :

    Nodo* ultimo = lista;
    while( ultimo->sig ) ultimo = ultimo->sig;

That is, the last node will be the one that has no more nodes behind it.

Once this node is located, it will only be necessary (if the default constructor has been implemented) to update two pointers.

else
{
    Nodo* ultimo = lista;
    while( ultimo->sig ) ultimo = ultimo->sig;

    ultimo->sig = q;
    q->ant = ultimo;
}

By the way, do not forget to release the memory before leaving the program ... you should not lose good habits:

while( lista )
{
  Nodo* temp = lista;
  lista = lista->sig;
  delete temp;
}

Ah yes, for compatibility, to import cin and cout I suggest using:

#include <iostream>

Instead of

#include <bits/stdc++.h> 

The first is referred to as a standard library (unlike the second). You will save a whole source of errors when testing the code in other systems (such as the class pc when teaching your exercise, for example)

    
answered by 23.10.2017 в 07:34