Jump to content
renato_m

Listas duplamente ligadas

Recommended Posts

renato_m

Olá pessoal.

O problema é o seguinte, eu tenho o seguinte construtor para uma lista ordenada que o código é o seguinte:

lstM consLstMcNumber(lstM lista, musica mu)
{
     lstM aux;
     //se lista existir
     //strcmp < 0, primeira string vem primeiro
     //se a lista existir e o nó que recebi for o primeiro
     if(!lista || (strcmp(mu.trackNumber, lista -> m.trackNumber)<0))
     {
       aux = (lstM)malloc(sizeof(lstNodo));

       aux -> m = mu;
       aux -> seg = lista;

       return aux;
     }
     else
       lista -> seg = consLstMcNumber(lista -> seg , mu);
       return lista;

}

o nó da lista é o seguinte:

typedef struct sLstM
{
        musica m;
        struct sLstM *seg;
}lstNodo,*lstM;

Agora a minha dúvida é que alterações tenho que fazer para criar uma lista duplamente ligada.

O nó da lista ficará algo parecido com:

typedef struct sLstM
{
        musica m;
        struct sLstM *seg;
        struct sLstM *anterior;
}lstNodo,*lstM;

Agora não sei é que alterações fazer ao construtor...

Se me puderem ajudar agradecia.

Share this post


Link to post
Share on other sites
Localhost

Basicamente se criares um novo nó (vou chamar-lhe new) numa lista duplamente ligada tens algo como (vou chamar ao último nó da lista end):

new = malloc (...);

end->next = new;
new->ant = end;

new->next = NULL;
end = new;


here since 2009

Share this post


Link to post
Share on other sites
renato_m

Pois mas no meu caso, reaproveitar a minha função construtora de lista ordenada já não dá certo??

Por causa da primeira condição de (!lista || strcmp ...)

Share this post


Link to post
Share on other sites
Diutsu

é mais fácil (e correcto) criares mais uma função para inserir, um elemento na lista embora possas alterar o construtor para teres apenas uma função.


XX SINFO - Semana Informática

Share this post


Link to post
Share on other sites
renato_m

Como assim??

Eu tenho sempre que alterar o meu construtor, pois neste momento cria uma lista ordenada, mas simples...

Eu quero é que ela agora tambem aponte para o nó anterior...

Share this post


Link to post
Share on other sites
Diutsu

O que eu quis dizer foi que de uma perspectiva de design da aplicação é mais fácil teres uma função para inserir separada do construtor.

O construtor, geralmente cria uma estrutura vazia, e devolve um ponteiro para a estrutura

A função de inserir é que começa a guardar elementos na estrutura.

No teu caso, como uma lista vazia é um ponteiro para NULL não tens um construtor propriamente dito, tens apenas uma função de inserir novos eleementos, função à qual chamaste consLstMcNumber.

à função de inserir é passado sempre um ponteiro para o primeiro elemento da lista, que é também um ponteiro para a propria lista, e ou um novo nó a inserir ou a informação a inserir num novo nó.

As alterações que tens de fazer ao construtor é:

aplica o código que o Localhost te deu, caso a lista não seja vazia (NULL), se for null fazes apenas o malloc, inicialização das variáveis e atribuição de NULL ao prev e ao next


XX SINFO - Semana Informática

Share this post


Link to post
Share on other sites
renato_m

Olá bom dia.

Eu tive a alterar o meu construtor e fiz algo do género?

Acham que assim está a funcionar?

É que não sei como ver se tá ligada inversamente.

lstM consLstMcNumber(lstM lista, musica mu)
{
     lstM aux;
     //se lista estiver vazia
     if(!lista)
     {
       aux = (lstM)malloc(sizeof(lstNodo));

       aux -> m = mu;
       aux -> seg = lista;
       aux -> ant = NULL;
       return aux;
     }
     else
     {
       if((strcmp(mu.trackNumber, lista -> m.trackNumber)<0))
       {
       		aux = (lstM)malloc(sizeof(lstNodo));
       		
       		aux -> m = mu;
       		aux -> seg = lista;
       		aux -> ant = lista -> ant;
       		lista = aux;
       		
       		//return aux;
       }
       else
       {
       		lista -> seg = consLstMcNumber(lista -> seg , mu);
          return lista;
       }
       
       return lista;
     } 
}

Share this post


Link to post
Share on other sites
renato_m

Peço desculpa mas ao bocado enganei-me no código.

Este penso que deve funcionar, o que dizem?

Abraço

lstM consLstMcNumber(lstM lista, musica mu)
{
     lstM aux;
     //se lista estiver vazia
     if(!lista)
     {
       aux = (lstM)malloc(sizeof(lstNodo));

       aux -> m = mu;
       aux -> seg = lista;
       aux -> ant = NULL;
       return aux;
     }
     else
     {
     		//se o primeiro for maior que o segundo
     	  if((strcmp(mu.trackNumber, lista -> m.trackNumber)<0))
       {
       		aux = (lstM)malloc(sizeof(lstNodo));
       		
       		aux -> m = mu;
       		aux -> seg = lista;
       		aux -> ant = lista -> ant;
       		lista -> ant = aux;
       		lista = aux;
       		
       		//return aux;
       }
       else
       {
       		lista -> seg = consLstMcNumber(lista -> seg , mu);
          return lista;
       }
       
       return lista;
     }
}

Share this post


Link to post
Share on other sites
Diutsu

Também penso que deve funcionar (parece-me bem). Mas não sou eu que o vou testar


XX SINFO - Semana Informática

Share this post


Link to post
Share on other sites
renato_m

Olá amigos.

Tive a testar a lista com o gdb e ela não funciona quando insere no final da lista...

Pois entra logo no if(!lista) e poe-me o apontador para o anterior a NULL...

Logo perde a ligaçao com o anterior da lista.

Como posso resolver este problema?

Share this post


Link to post
Share on other sites
Diutsu

Quando fazes !lista estás à espera que lista seja null, logo colocar os apontadores para o seguinte e anterior a null está certo.

Agora falta-te é o caso em que chegas ao fim da lista, e queres inserir no fim da lista.

Basicamente é acrescentares mais um if antes no ultimo else, se o seguinte for nulll então chamas à mesma a função e quando voltares fazes a ligação com o anterior, caso o seguinte não seja null segues em frente.


XX SINFO - Semana Informática

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.