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

 

 


Tema destacado: Recopilación Tutoriales y Manuales Hacking, Seguridad, Privacidad, Hardware, etc


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

Desconectado Desconectado

Mensajes: 6



Ver Perfil
estructura doblemente encadenada
« en: 14 Mayo 2011, 00:00 am »

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
  1. struct Node {
  2.            int dada;
  3.            Node *seguent;
  4.            Node *anterior;
  5.  
  6.        };
  7.        Node *a_inici;
  8.  

METODOS:
Código
  1. EstDinDE::EstDinDE()
  2. {
  3.    a_inici=NULL;
  4. }
  5.  
  6. void EstDinDE::afegirInici(int e)
  7. {
  8.    Node *p;
  9.    p=new Node();
  10.    p->dada=e;
  11.    p->seguent=a_inici;
  12.    p->anterior=NULL;
  13.    //a_inici->anterior=p;
  14.    a_inici=p;
  15. }
  16.  
  17. void EstDinDE::afegirFinal(int e)
  18. {
  19.    Node *p,*aux;
  20.    p=new Node();
  21.    aux=new Node();
  22.    bool inserit=false;
  23.  
  24.    if(a_inici==NULL){
  25.        p->dada=e;
  26.        p->seguent=a_inici;
  27.        p->anterior=NULL;
  28.        a_inici=p;
  29.    }
  30.    else {
  31.        p=a_inici;
  32.        p=p->seguent;
  33.        aux=a_inici;
  34.        while(!inserit){
  35.            if(p!=NULL){
  36.                p=p->seguent;
  37.                aux=aux->seguent;
  38.            }
  39.            else{
  40.                Node *nou;
  41.                nou=new Node();
  42.  
  43.                nou->dada=e;
  44.                nou->seguent=NULL;
  45.                nou->anterior=aux->seguent;
  46.                p->seguent=nou;
  47.  
  48.                inserit=true;
  49.            }
  50.        }
  51.    }
  52. }
  53.  
  54. void EstDinDE::esborrar(int e)
  55. {
  56.    Node *p;
  57.    p=new Node();
  58.  
  59.    bool trobat=false;
  60.  
  61.    trobat=existeix(e);
  62.  
  63.    if((p!=NULL)&&trobat)
  64.    {
  65.        if(p==a_inici)
  66.        {
  67.            a_inici=p->seguent;
  68.            if(p->seguent != NULL)
  69.                p->seguent->anterior =NULL;
  70.        }
  71.        else if  (p->seguent!= NULL)
  72.        {
  73.            p->anterior->seguent=p->seguent;
  74.            p->seguent->anterior=p->anterior;
  75.        }
  76.        else {
  77.            p->anterior->seguent=NULL;
  78.        }
  79.        delete p;
  80.    }
  81. }
  82.  
  83. bool EstDinDE::existeix(int e)
  84. {
  85.    Node *p;
  86.    bool trobat=false;
  87.    p=a_inici;
  88.  
  89.    while((p!=NULL)&&(!trobat))
  90.    {
  91.        if (p->dada==e) trobat=true;
  92.        p=p->seguent;
  93.    }
  94.    return(trobat);
  95. }
  96.  
  97. void EstDinDE::llistar()
  98. {
  99.    Node *p;
  100.    p=a_inici;
  101.  
  102.    while(p->anterior) p=p->anterior;
  103.    while(p) {
  104.         cout << p->dada <<endl;
  105.         p=p->seguent;
  106.    }
  107. }
  108.  


En línea

Ten en muy en cuenta tus objetivos!!!
Puede ser que sea lo único que te de ánimos para continuar!!
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: estructura doblemente encadenada
« Respuesta #1 en: 14 Mayo 2011, 18:51 pm »

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
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct Node {
  5.    int dada;
  6.    Node *seguent;
  7.    Node *anterior;
  8. };
  9.  
  10. Node *inici = NULL, *final = NULL;
  11.  
  12. void afegirInici(int x) {
  13.    Node *p = new Node;
  14.    p->dada = x;
  15.    p->seguent = inici;
  16.    p->anterior = NULL;
  17.    if (inici != NULL) inici->anterior = p;
  18.    swap(p, inici);
  19.    if (final == NULL) final = inici;
  20. }
  21.  
  22. void afegirFinal(int x) {
  23.    Node *p = new Node;
  24.    p->dada = x;
  25.    p->seguent = NULL;
  26.    p->anterior = final;
  27.    if (final != NULL) final->seguent = p;
  28.    swap(p, final);
  29.    if (inici == NULL) inici = final;
  30. }
  31.  
  32. bool existeix(int x) {
  33.    Node *actual = inici;
  34.    while (actual != NULL) {
  35.        if (actual->dada == x) return true;
  36.        actual = actual->seguent;
  37.    }
  38.    return false;
  39. }
  40.  
  41. //Esborra totes les ocurrencies de x a la llista
  42. void esborrar(int x) {
  43.    Node *actual = inici;
  44.    while (actual != NULL) {
  45.        if (actual->dada == x) {
  46.            if (actual->anterior != NULL) actual->anterior->seguent = actual->seguent;
  47.            else inici = actual->seguent;
  48.            if (actual->seguent != NULL) actual->seguent->anterior = actual->anterior;
  49.            else final = actual->anterior;
  50.  
  51.            Node *aux = actual->seguent;
  52.            delete actual;
  53.            actual = aux;
  54.        }
  55.        else actual = actual->seguent;
  56.    }
  57. }
  58.  
  59. void llistar() {
  60.    Node *actual = inici;
  61.    while (actual != NULL) {
  62.        cout << actual->dada;
  63.        if (actual->seguent != NULL) cout << " <-> ";
  64.        actual = actual->seguent;
  65.    }
  66.    cout << endl;
  67. }
  68.  
  69. int main() {
  70.    char c;
  71.    while (cin >> c) {
  72.        if (c == 'I') {
  73.            int x;
  74.            cin >> x;
  75.            afegirInici(x);
  76.        }
  77.        else if (c == 'F') {
  78.            int x;
  79.            cin >> x;
  80.            afegirFinal(x);
  81.        }
  82.        else if (c == 'E') {
  83.            int x;
  84.            cin >> x;
  85.            cout << (existeix(x)?"Existeix":"No existeix") << endl;
  86.        }
  87.        else if (c == 'L') llistar();
  88.        else {
  89.            int x;
  90.            cin >> x;
  91.            esborrar(x);
  92.        }
  93.    }
  94. }

Te pongo la prueba que he hecho:

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


En línea

mihina

Desconectado Desconectado

Mensajes: 6



Ver Perfil
Re: estructura doblemente encadenada
« Respuesta #2 en: 15 Mayo 2011, 18:04 pm »

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!!
En línea

Ten en muy en cuenta tus objetivos!!!
Puede ser que sea lo único que te de ánimos para continuar!!
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: estructura doblemente encadenada
« Respuesta #3 en: 15 Mayo 2011, 18:59 pm »

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

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Nesecio ayuda con las listas encadenadas y doblemente encadenasa de C#
.NET (C#, VB.NET, ASP)
alonsomzo 1 4,611 Último mensaje 18 Marzo 2009, 00:33 am
por Mr. Crowley
ayuda con esta lista encadenada simple
.NET (C#, VB.NET, ASP)
alonsomzo 0 3,139 Último mensaje 3 Abril 2009, 00:39 am
por alonsomzo
una lista circular doblemente enlazada en c sharp c#
.NET (C#, VB.NET, ASP)
neo_angel_xxx 2 8,929 Último mensaje 29 Octubre 2010, 01:48 am
por [D4N93R]
Problema con lista simplemente encadenada
Programación C/C++
BJM 3 1,982 Último mensaje 14 Diciembre 2012, 23:19 pm
por twins
Lista encadenada
Programación C/C++
pudge123 4 2,518 Último mensaje 7 Octubre 2013, 08:32 am
por eferion
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines