Jump to content
Sign in to follow this  
AprendizZ

Inserção de novos nós em lista dupla com sentinela!

Recommended Posts

AprendizZ

Agora "encalhei" noutra fase do problema: inserir novos nós na lista dupla com sentinela.

Neste momento tenho o programa quase terminado, só que não consigo inserir vários

números nessa lista dupla.

Se insiro um 1º novo nó, este é inserido à cabeça da lista e actualiza o apontadores (anterior

e seguinte do novo nó e do nó-sentinela). Ao testar com uma função size confirmo que a

lista tem mais um elemento.

A seguir se insiro um 2º novo nó, este é inserido sem problemas, mas o 1º novo nó desapareceu,

ficando a lista só com o último novo nó (mais o sentinela).

Já testes várias alterações, inclusive desenhos no papel, mas não encontro o problema.

Eis o código:

// definicao do tipo dlist - lista dupla --------------
typedef struct dlnode *dlist;
typedef struct dlnode {
int value;    // valor do nó
dlist prev;   // nó anterior
dlist next;   // nó seguinte
} dlist_node;

dlist sentinela;

// criar lista dupla - sentinela --------------
dlist dlist_create ()
{
sentinela = (dlist) malloc (sizeof (dlist_node));
sentinela->prev = sentinela;
sentinela->next = sentinela;
return sentinela;
}

// verifica se lista dupla vazia --------------
int dlist_empty ()
{
int e;
if (sentinela->next == sentinela)
	e = 1;
else
	e = 0;
return e;
}

// construtor de listas
dlist dlist_put_first (int x, dlist s)
{
dlist r = (dlist) malloc (sizeof (dlist_node));
if (dlist_empty() == 1)
{
	r->value = x;
	r->prev = s;
	r->next = s->next;
	r->prev->next = r;
	r->next->prev = r;
}
else
{
	r->value = x;
	r->prev = s;
	r->next = sentinela;
	sentinela->prev = r;
	s->next = r;
}
return r;
}

// tamanho da lista dupla
int dlist_size (dlist s)
{
int tamanho = 0;
while(s != sentinela)
{ 
	s = s->next;
	tamanho++;
}
return tamanho;
}

// escrever valores da lista
void dlist_write (dlist s)
{
while (s != sentinela)
{
	printf(" |%d| ",s->value);
	s = s->next;
}
printf("\n");
}
// ------------------------------------------
void testeA ()
{
int x;
dlist s;
dlist_create();
s = sentinela;
while (scanf ("%d", &x) != EOF)
{
	s = dlist_put_first (x, s);
	dlist_write (s);
	printf("     tamanho final %d vazio %d apontador %d\n\n", dlist_size(s), dlist_empty(), s);
}
}

Se alguém me puder ajudar, agradeço desde já.

Share this post


Link to post
Share on other sites
KTachyon

Está-me a parecer que tu estás a mandar imprimir e a ver o tamanho a partir do último elemento que inseriste na lista ligada, cujo ponteiro seguinte é o da sentinela.

Repara, fiz as seguintes alterações (para poder executar e para o meu processador, que é de 64-bit, logo os ponteiros são long int):

// escrever valores da lista
void dlist_write (dlist s)
{
    s = sentinela->next;
    
        while (s != sentinela)
        {
                printf(" |%d| (%ld, %ld)", s->value, (long) s, (long) sentinela);
                s = s->next;
        }
        printf(" |%d| (%ld, %ld)", s->value, (long) s, (long) sentinela);
        printf("\n");
}
// ------------------------------------------
int main()
{
        int x;
        dlist s;
        dlist_create();
        s = sentinela;
        while (scanf ("%d", &x) != EOF)
        {
                s = dlist_put_first (x, s);
                dlist_write (s);
                printf("     tamanho final %d vazio %d apontador %ld\n\n", dlist_size(s), dlist_empty(), (long) s);
        }

return 0;
}

O resultado:

1
|1| (4296016032, 4296016000) |0| (4296016000, 4296016000)
     tamanho final 1 vazio 0 apontador 4296016032

2
|1| (4296016032, 4296016000) |2| (4296016064, 4296016000) |0| (4296016000, 4296016000)
     tamanho final 1 vazio 0 apontador 4296016064

3
|1| (4296016032, 4296016000) |2| (4296016064, 4296016000) |3| (4296016096, 4296016000) |0| (4296016000, 4296016000)
     tamanho final 1 vazio 0 apontador 4296016096

Ou seja, na realidade estás a adicionar os elementos à lista. O que não estás a fazer bem é calcular o tamanho e a escrever. Tens que partir da sentinela.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
AprendizZ

Meu caro,

era isso mesmo que faltava... eu não estava a raciocinar nesse sentido.

Um grande obrigado.

(Espero num futuro próximo tb poder ajudar neste forum, é a única forma que tenha de agradecer).

Share this post


Link to post
Share on other sites
KTachyon

É para isso que o fórum existe. Para além disso, o problema colocado foi suficientemente interessante para eu me dar ao trabalho de o alterar e executar, coisa que não acontece frequentemente em muitas dúvidas do fórum. Por mim já é agradecimento suficiente :thumbsup:


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.