Filas, Pilhas e outras estruturas de dados

[Happening]

Boas marinheiros 😛

Mais um tópico que espero que me esclareça àcerca de pilhas, filas, listas ligadas...

O que gostava de saber é essencialmente a estrutura delas e como se comportam a nível de memória pois para mim é estritamente necessário saber isto para conseguir escrever o código...

Obrigado desde já!

[pmg]

A Wikipedia pode servir como uma (boa) introdução ao tema das estruturas de dados (tens lá um artigo semelhante em português, mas não está tão completo).

[Happening]

Sim é sem dúvida um bom sitio por onde começar. MAs agora que estou a implementar funções as coisas já nao são tão evidentes...

Por exemplo tenho uma função que vai apagar elementos de uma fila se esses elementos começarem por uma dada letra passada por argumento.

Eu tenho de criar apontadores ou posso trabalhar directamente na lista passada por argumento?

headers:

struct fitem
{
char *string;
struct fitem *proximo;
};
typedef struct fitem filaItem;
typedef struct
{
int capacidade;
filaItem *cabeca;
filaItem *cauda;
} fila;

função que implementei:

int fila_elimina(fila *f, char c_inicial)
{
int contador=0;
fila *pointer;
pointer=f;
if(pointer->cabeca->string[0] == c_inicial)
{
free(pointer->cabeca->string);
pointer=pointer->cabeca->proximo;
pointer->capacidade--
contador++;
}
return contador;
}

Não passa é nos testes..

[pmg]

função que implementei:

int fila_elimina(fila *f, char c_inicial)
{
int contador=0;
fila *pointer;
pointer=f;
if(pointer->cabeca->string[0] == c_inicial)
{
free(pointer->cabeca->string);
pointer=pointer->cabeca->proximo;
pointer->capacidade--
contador++;
}
return contador;
}

Não passa é nos testes..

Nesta função os tipos dos ponteiros não são os correctos.

Repara

pointer é um ponteiro para fila

mas pointer->cabeca->proximo é um ponteiro para struct fitem

Alem disso, o que acontece quando a primeira string não começar pela letra especificada?

[HappyHippyHippo]

Como é uma fila (FIFO / First-In-First-Out) presumo que so pretendas eliminar a cabeca

int fila_elimina(fila *f, char c_inicial) {
 int contador=0;

 // precisas do ponteiro para o elemento que queres eliminar
 // para não perderes a referência/ posição de memória após
 // a remoção deste da lista

 //fila *pointer;
 //pointer=f;
 fileItem * pointer = f->cabeca;

 if(f->cabeca->string[0] == c_inicial) {
// primeiro vamos remover o elemento da lista
f->cabeca=f->cabeca->proximo;

// vamos entao libertar a memoria do elemento removido
free(pointer->string);
free(pointer);

// no fim, decrementamos então o numero de elementos
// guardados na lista
pointer->capacidade--
contador++;
 }
 return contador;
}

Edited May 29, 2012 at 09:23 AM by HappyHippyHippo

[Happening]

Se não for igual à letra não remove esse elemento, ou seja continua a pesquisar na lista.

Mas no caso que apresentaste como o pointer é do tipo FilaItem ou seja já nao posso decrementar a capacidade...

Edited May 29, 2012 at 10:33 AM by Happening

[Flinger]

Se não for igual à letra não remove esse elemento, ou seja continua a pesquisar na lista

Continua a procurar? isso parte o conceito de FIFO. Uma FIFO é suposto ser como uma fila de espera. Só quem está à cabeça é que é atendido, os outros continuam à espera independentemente do problema. Não é suposto ires buscar alguém a meio da fila para ser atendido 😛

[Happening]

Sim, é suposto eliminar todos os elementos que comecem por aquela letra do parametro

[HappyHippyHippo]

nesse caso a primeira coisa é pegar em todo o texto que diz fila e apagar

segundo, necessitas de um ciclo de remoção. para isso lembra-te que para remover um elemento necessitas sempre de nunca perder as referências de memória.

isto é, para remover o elemento n, necessitas estar a apontar para o elemento n-1 para atribuires como próximo, o elemento n+1

[Happening]

Ou posso criar outra fila e vou copiando aqueles que não começam por a letra do parametro n é?

[HappyHippyHippo]

duplicação de elementos ... isso é mais ou menos a pior solução correcta

[Flinger]

Ou posso criar outra fila e vou copiando aqueles que não começam por a letra do parametro n é?

Podes, mas aí vais estar a usar memória desnecessariamente. Para tratares isso, tens de apagar todos os elementos da lista original no final. Ora isso não se justifica, podendo apenas remover os que te interessam.

Além disso, não trates a tua estrutura como uma fila. Se é suposto percorreres a estrutura toda, o que tu tens é uma lista simples. Pode-te parecer tudo o mesmo, mas a nível de conceitos são coisas completamente diferentes:

Uma lista ligada é um conjunto de nodos ligados de forma ordenada, em que cada nodo está ligado ao seguinte através de um apontador.

Um fila, ou queue, pode ser implementada usando uma lista ligada, mas onde é suposto apenas inserires no fim da lista e removeres o elemento que está à cabeça da mesma. Não é suposto removeres, nem tão pouco consultares, elementos que estão no meio da lista.

[Happening]

Esta estrutura de dados confunde-me um bocado :S

[HappyHippyHippo]

pensa num comboio

[Happening]

O que me está a deixar um pouco confuso é a utilização dos apontadores e da lista ao mesmo tempo.

Por exemplo no teu código tinhas:

f->cabeca=f->cabeca->proximo;

// vamos entao libertar a memoria do elemento removido

free(pointer->string);

free(pointer);

f->cabeca=f->cabeca->proximo eu entendo, estamos a percorrer a lista.

Mas depois não entendo o porquê de fazermos free aos pointers. Tal como dizes em comentário é libertar a memória do elemento removido mas não estou a entender bem como se processa...

[Flinger]

Tem atenção que o código do Hyppo apenas liberta o primeiro elemento da lista. Foi pensado para uma fila e não para remover elementos a meio.

Cada vez que fazes um malloc, o teu SO reserva um bloco de memória para o teu programa. Quando deixas de precisar dele, convem fazer o free desse bloco, por forma a devolver o controlo desse bloco ao SO. Se o campo string foi allocado tem de ser libertado usando o primeiro free. Depois libertas o elemento propriamente dito.

[Happening]

Já sei como se faz 🙂

Tipo se um elemento tem a letra remove-se se não tiver copio o elemento para a cauda e liberto a cabeça, e assim sucessivamente até à capacidade inicial.

É simples até mas deu que pensar 🙂

[bsccara]

Tipo se um elemento tem a letra remove-se se não tiver copio o elemento para a cauda e liberto a cabeça, e assim sucessivamente até à capacidade inicial.

Não sei o que queres fazer com isso, mas qual é o interesse de andar a passar elementos para a cauda ? Percorres a lista (chama-lhe lista ligada, para não haver confusões) e para cada elemento verificas a tal letra. Se corresponder eliminas esse elemento e continuas a percorrer a lista.

[Happening]

O problema é que se fizer isso tenho de andar a trabalhar com os apontadores pq se apago um elemento do meio o apontador de trás tem de apontar para o elemento da frente. Fazendo o que disse não temos de nos preocupar. Apenas passar o apontador para NULL cada vez que adicionamos na cauda

[bsccara]

Então imagina que procuras por uma letra que não existe em nenhum elemento. Passas o primeiro para o fim. Depois o novo primeiro para o fim. Depois... Quando é que paras ?

Vais ter de contar o número de elementos na lista para saber quando parar, ou seja vais ter de percorrer a lista de qualquer maneira.