C++, liste con puntatori, circolare e con sentinella.

[pietrol83]

ciao ragazzi, ho creato una calsse (listap) che implementa le liste con i puntatori, circolari e con sentinella però è evidente che c'è un problema nel metodo inslista. in pratica quando vienne inserito nella lista il primo nodo (dopo la sentinella) ho il seguente problema: il puntatore all'elemento precedente della sentinella non punta al nuovo elemento inserito ma alla sentinella stessa, mentre il puntatore all'elemento successivo dell'elemento inserito non punta alla sentinella ma a se stesso. io non riesco a capire dove sia il problema. chi mi aiuta a capire meglio???
posto il codice della classe e il codice che ho scritto per provare se la classe è stata creata correttamente:

listap.h

#ifndef _LISTAP_H
#define _LISTAP_H

#include <iostream>

using namespace std;

typedef int tipoelem;

struct nodo
{
      nodo *precedente;
      tipoelem elemento;
      nodo *successivo;
};

typedef nodo *posizione;

class listap
{
      public:
             posizione sentinella;
             
             listap();
             void crealista();
             bool listavuota();
             posizione primolista();
             bool finelista(posizione);
             void inslista(posizione &, tipoelem);
             void canclista(posizione &);
             tipoelem leggilista(posizione);
             void scrivilista(posizione &, tipoelem);
             posizione predlista(posizione);
             posizione succlista(posizione);
};

#endif

listap.cpp

#include "listap.h"

listap::listap()
{
	crealista();
}

void listap::crealista()
{
	sentinella = (posizione)malloc(sizeof(nodo));
    tipoelem elemnullo = 0;
	sentinella->precedente = sentinella;
	sentinella->elemento = elemnullo;
	sentinella->successivo = sentinella;
}

bool listap::listavuota()
{
	return((sentinella->precedente == sentinella) && (sentinella->successivo == sentinella));
}

posizione listap::primolista()
{
    if(!listavuota())
    {
        return(sentinella->successivo);
    }
    cerr << "la lista e\' vuota\n\n";
}

bool listap::finelista(posizione p)
{
    return(p->successivo == sentinella);
}

void listap::inslista(posizione &p, tipoelem elem)
{
    posizione temp = new nodo;
    temp->elemento = elem;
    temp->precedente = p->precedente;
    temp->successivo = p;
    p->precedente->successivo = temp;
    p->precedente = temp;
    p = temp;
}

void listap::canclista(posizione &p)
{
    posizione temp = p;
    p->precedente->successivo = p->successivo;
    p->successivo->precedente = p->precedente;
    p = p->successivo;
    delete(temp);
}

tipoelem listap::leggilista(posizione p)
{
    return(p->elemento);
}

void listap::scrivilista(posizione &p, tipoelem elem)
{
    p->elemento = elem;
}

posizione listap::predlista(posizione p)
{
    return(p->precedente);
}

posizione listap::succlista(posizione p)
{
    return(p->successivo);
}

provalistap.cpp

#include <cstdlib>
#include <iostream>
#include "listap.h"

using namespace std;

int main(int argc, char *argv[])
{
    listap list;        
    
    list.inslista(list.sentinella, 1);

    cout << list.listavuota() << "\n\n";
    system("pause");
    system("cls");
    
    cout << list.succlista(list.sentinella) << "\n";
    cout << list.succlista(list.sentinella)->precedente << "  " << list.succlista(list.sentinella)->successivo << "\n\n";
    
    cout << list.sentinella << "\n";
    cout << list.sentinella->precedente << "  " << list.sentinella->successivo << "\n\n";
    system("pause");
    system("cls");
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

[pietrol83]

ragazzi qualcuno può rispondere???

[antotan]

Direi che in inslista

p = temp;

sia sbagliato.

Chiamo per comodità q = p->precendente
In pratica tu:

1. crei un nuovo elemento
2. setti il suo precendente a q e il suo successivo a p, quindi ci sono entrambi gli archi in uscita
3. setti il p->precedente = nuovoelem e setti il successivo di q in modo che sia il nuovo elemento, quindi ora ci sono gli archi in entrata.

A questo punto hai finito. Da q va in nuovoelem e da nuovoelem vai in p. Stesso a ritroso. Dunque il nodo è correttamente inserito

L'ultimo assegnamento, p = temp, fa puntare p al nuovo elemento, dunque p->succ = temp->succ e p->prec = temp->prec. Cioè ti sei scordato del nodo che era puntato da p e che ora non è puntato più da nessuno.

Ho provato a fare:

int main(int argc, char *argv[])
{
    listap list;        
    
    list.inslista(list.sentinella, 1);
	list.inslista(list.sentinella, 2);
       
    cout << list.sentinella->precedente->elemento 
        << "  " << list.sentinella->precedente->precedente->elemento << "\n\n";
       
    system("PAUSE");
    return EXIT_SUCCESS;
}

E mi stampa "2 1" quindi credo sia giusto.

[pietrol83]

grazie 1000!!!