Jump to content
AprendizZ

Lista duplamente ligadas com sentinela.

Recommended Posts

AprendizZ

Caros amigos. Se já sou aprendiz nestas coisas de C ainda mais sou no que diz

respeito a listas.

Preciso de fazer uma função com uma lista duplamente ligada, mas com sentinela.

Alguém me pode ajudar a esclarecer o que é uma sentinela, nestas listas, e como

se implementam.

Já pesquisei pela Internet, mas acho que o que é português (portugal-a-programar)

é bom.

Muito obrigado.

Share this post


Link to post
Share on other sites
tsrodrigues

sentinela? nunca ouvi falar. Será que te estás a referir a um iterador?

Share this post


Link to post
Share on other sites
Diutsu

Uma sentinela é um elemento extra, que não guarda dados, apenas a informação para o primeiro e ultimo elemento da lista (e outra informação sobre a lista que queiras).

Basicamente em vez de teres uma coisa assim:

     ___       ___       ___       ___
<-- |D1 | <-- |D2 | <-- |D3 | <-- |D4 |
    |___| --> |___| --> |___| --> |___|  -->


Tens


              _____
             |Lst  |
    /--------|_____|--------------\
    |                             |
    V___       ___       ___      V___
<-- |D1 | <-- |D2 | <-- |D3 | <-- |D4 |
    |___| --> |___| --> |___| --> |___|  -->


E agora apenas manipulas o Lst.


XX SINFO - Semana Informática

Share this post


Link to post
Share on other sites
AprendizZ

Estou a precisar de funções que:

criem uma lista dupla vazia (mas só com a sentinela/iterador...). Já fiz o seguinte:

dlist dlist_create (dlist lis)
{
dlist r = (dlist) malloc (sizeof (dlist_node));
r->next = lis;
r->prev = lis;
return r;
}

... mas não sei se está bem.

outra função que verifique que esta lista tá vazia:

int dlist_empty (dlist lis)
{
return (lis->next == lis->prev);
}

e outra para inserir valor à cabeça desta lista:

dlist dlist_put_first (int x, dlist lis)
{
dlist r = (dlist) malloc (sizeof (dlist_node));
r->value = x;
r->next = lis;
r->prev = lis;
return r;
}

Numa lista simples corre bem, mas dupla com sentinela...

Os esquemas têm ajudado, mas não totalmente.

Obrigado.

Share this post


Link to post
Share on other sites
falk0n

int dlist_empty (dlist lis)
{
        return (lis->next == lis->prev);
}

se é duplamente ligada e se tiver dois elementos o prev e o next apontam para o mesmo sitio :) e não é NULL

Cuidado com isto

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

×
×
  • 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.