estructura doblemente encadenada

[mihina]

Buenas estoy haciendo una lista doblemente encadenada; entiendo su funcionamiento pero no acabo de poder plasmarlo en el codigo. Haber si me podeis aconsegar de como hacerlo.

Gracias!!.

ESTRUCTURA:

Código (cpp) [Seleccionar] Expandir


struct Node {
            int dada;
            Node *seguent;
            Node *anterior;

        };
        Node *a_inici;


METODOS:

Código (cpp) [Seleccionar] Expandir


EstDinDE::EstDinDE()
{
    a_inici=NULL;
}

void EstDinDE::afegirInici(int e)
{
    Node *p;
    p=new Node();
    p->dada=e;
    p->seguent=a_inici;
    p->anterior=NULL;
    //a_inici->anterior=p;
    a_inici=p;
}

void EstDinDE::afegirFinal(int e)
{
    Node *p,*aux;
    p=new Node();
    aux=new Node();
    bool inserit=false;

    if(a_inici==NULL){
        p->dada=e;
        p->seguent=a_inici;
        p->anterior=NULL;
        a_inici=p;
    }
    else {
        p=a_inici;
        p=p->seguent;
        aux=a_inici;
        while(!inserit){
            if(p!=NULL){
                p=p->seguent;
                aux=aux->seguent;
            }
            else{
                Node *nou;
                nou=new Node();

                nou->dada=e;
                nou->seguent=NULL;
                nou->anterior=aux->seguent;
                p->seguent=nou;

                inserit=true;
            }
        }
    }
}

void EstDinDE::esborrar(int e)
{
    Node *p;
    p=new Node();

    bool trobat=false;

    trobat=existeix(e);
   
    if((p!=NULL)&&trobat)
    {
        if(p==a_inici)
        {
            a_inici=p->seguent;
            if(p->seguent != NULL)
                p->seguent->anterior =NULL;
        }
        else if  (p->seguent!= NULL)
        {
            p->anterior->seguent=p->seguent;
            p->seguent->anterior=p->anterior;
        }
        else {
            p->anterior->seguent=NULL;
        }
        delete p;
    }
}

bool EstDinDE::existeix(int e)
{
    Node *p;
    bool trobat=false;
    p=a_inici;

    while((p!=NULL)&&(!trobat))
    {
        if (p->dada==e) trobat=true;
        p=p->seguent;
    }
    return(trobat);
}

void EstDinDE::llistar()
{
    Node *p;
    p=a_inici;

    while(p->anterior) p=p->anterior;
    while(p) {
         cout << p->dada <<endl;
         p=p->seguent;
    }
}


[ghastlyX]

Tienes varios errores en tu código.

En la función para añadir al inicio, creas un nuevo nodo que pones como inicio, pero no haces que la lista anterior apunte a él (sólo el nuevo nodo apunta a lista). Básicamente, falta la línea que tienes comentada, que supongo que lo habrás hecho porque te daba Segmentation Fault. Esto sucedería porque al principio, a_inici es NULL, de forma que haría falta un if para comprobarlo.

La función de añadir al final la veo horrible por un simple motivo. Estás guardando un puntero al inicio de la lista, pero no uno para el final. Así, si quieres añadir al algo al final, tienes que recorrer la lista entera para llegar al final y después añadir: pasas una operación que teniendo un puntero extra sería O(1) a una operación O(n), siendo n el número de elementos de la lista.

La función para mirar si está el elemento parece correcta, mientras que la de borrar no entiendo qué haces, pero no veo que recorras la lista, de forma que dudo que sea correcta.

He picado ahora cómo haría yo las funciones que implementas, no lo he probado en profundidad, pero parece que funcionan bien.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

struct Node {
    int dada;
    Node *seguent;
    Node *anterior;
};

Node *inici = NULL, *final = NULL;

void afegirInici(int x) {
    Node *p = new Node;
    p->dada = x;
    p->seguent = inici;
    p->anterior = NULL;
    if (inici != NULL) inici->anterior = p;
    swap(p, inici);
    if (final == NULL) final = inici;
}

void afegirFinal(int x) {
    Node *p = new Node;
    p->dada = x;
    p->seguent = NULL;
    p->anterior = final;
    if (final != NULL) final->seguent = p;
    swap(p, final);
    if (inici == NULL) inici = final;
}

bool existeix(int x) {
    Node *actual = inici;
    while (actual != NULL) {
        if (actual->dada == x) return true;
        actual = actual->seguent;
    }
    return false;
}

//Esborra totes les ocurrencies de x a la llista
void esborrar(int x) {
    Node *actual = inici;
    while (actual != NULL) {
        if (actual->dada == x) {
            if (actual->anterior != NULL) actual->anterior->seguent = actual->seguent;
            else inici = actual->seguent;
            if (actual->seguent != NULL) actual->seguent->anterior = actual->anterior;
            else final = actual->anterior;

            Node *aux = actual->seguent;
            delete actual;
            actual = aux;
        }
        else actual = actual->seguent;
    }
}

void llistar() {
    Node *actual = inici;
    while (actual != NULL) {
        cout << actual->dada;
        if (actual->seguent != NULL) cout << " <-> ";
        actual = actual->seguent;
    }
    cout << endl;
}

int main() {
    char c;
    while (cin >> c) {
        if (c == 'I') {
            int x;
            cin >> x;
            afegirInici(x);
        }
        else if (c == 'F') {
            int x;
            cin >> x;
            afegirFinal(x);
        }
        else if (c == 'E') {
            int x;
            cin >> x;
            cout << (existeix(x)?"Existeix":"No existeix") << endl;
        }
        else if (c == 'L') llistar();
        else {
            int x;
            cin >> x;
            esborrar(x);
        }
    }
}

Te pongo la prueba que he hecho:

Entrada:

Código [Seleccionar] Expandir

I 1 I 2 I 3
L
F 1
L
F 23
L
E 1
E 23
E 25
E 4
B 2
L
B 1
L
B 3
L
B 23
L
I 1
L
F 2
L

Salida:

Código [Seleccionar] Expandir

3 <-> 2 <-> 1
3 <-> 2 <-> 1 <-> 1
3 <-> 2 <-> 1 <-> 1 <-> 23
Existeix
Existeix
No existeix
No existeix
3 <-> 1 <-> 1 <-> 23
3 <-> 23
23

1
1 <-> 2

[mihina]

Ostia muchas gracias!!! sabia que se me escapaban cosas pero no sabia que eran ya que era la primera vez que intentaba hacer una lista doblemente encadenada.

lo que no se que es el swap(); para que sirve?

Gracias!!

[ghastlyX]

Simplemente hace un intercambio de las variables:
http://www.cplusplus.com/reference/algorithm/swap/