Escreva uma função em C++ para contar a quantidade de dados pares de uma lista simplesmente encadeada
não circular, que pode ser vazia, de acordo com o tipo no a seguir:
struct no {
int dado;
struct no *link;
};
Considere o protótipo :
int contar(no *);
Note que a função deverá receber o ponteiro para o início da lista e deverá retornar a quantidade
obtida.
Soluções para a tarefa
Resposta:
Uma lista encadeada (= linked list = lista ligada) é uma sequência de células; cada célula contém um objeto (todos os objetos são do mesmo tipo) e o endereço da célula seguinte. Neste capítulo, suporemos que os objetos armazenados nas células são do tipo int. Cada célula é um registro que pode ser definido assim:
struct reg {
int conteudo;
struct reg *prox;
};
[célula de lista encadeada]
É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:
typedef struct reg celula; // célula
Uma célula c e um ponteiro p para uma célula podem ser declarados assim:
celula c;
celula *p;
Se c é uma célula então c.conteudo é o conteúdo da célula e c.prox é o endereço da próxima célula. Se p é o endereço de uma célula, então p->conteudo é o conteúdo da célula e p->prox é o endereço da próxima célula. Se p é o endereço da última célula da lista então p->prox vale NULL .
[lista encadeada]
(A figura pode dar a falsa impressão de que as células da lista ocupam posições consecutivas na memória. Na realidade, as células estão tipicamente espalhadas pela memória de maneira imprevisível.)
Resposta:
Uma lista encadeada (= linked list = lista ligada) é uma sequência de células; cada célula contém um objeto (todos os objetos são do mesmo tipo) e o endereço da célula seguinte. Neste capítulo, suporemos que os objetos armazenados nas células são do tipo int. Cada célula é um registro que pode ser definido assim:
struct reg {
int conteudo;
struct reg *prox;
};
[célula de lista encadeada]
É conveniente tratar as células como um novo tipo-de-dados e atribuir um nome a esse novo tipo:
typedef struct reg celula; // célula
Uma célula c e um ponteiro p para uma célula podem ser declarados assim:
celula c;
celula *p;
Se c é uma célula então c.conteudo é o conteúdo da célula e c.prox é o endereço da próxima célula. Se p é o endereço de uma célula, então p->conteudo é o conteúdo da célula e p->prox é o endereço da próxima célula. Se p é o endereço da última célula da lista então p->prox vale NULL .
[lista encadeada]
(A figura pode dar a falsa impressão de que as células da lista ocupam posições consecutivas na memória. Na realidade, as células estão tipicamente espalhadas pela memória de maneira imprevisível.)
Exercícios 1
Declaração alternativa. Verifique que a declaração de células pode também ser escrita assim:
typedef struct reg celula;
struct reg {
int conteudo;
celula *prox;
};
★ Declaração alternativa. Verifique que a declaração de células pode também ser escrita assim:
typedef struct reg {
int conteudo;
struct reg *prox;
} celula;
Tamanho de célula. Compile e execute o seguinte programa:
int main (void) {
printf ("sizeof (celula) = %d\n",
sizeof (celula));
return EXIT_SUCCESS;
}
Endereço de uma lista encadeada
O endereço de uma lista encadeada é o endereço de sua primeira célula. Se le é o endereço de uma lista encadeada, convém dizer simplesmente que
le é uma lista encadeada.
(Não confunda le com 1e.) A lista está vazia (ou seja, não tem célula alguma) se e somente se le == NULL.
Listas são animais eminentemente recursivos. Para tornar isso evidente, basta fazer a seguinte observação: se le é uma lista não vazia então le->prox também é uma lista. Muitos algoritmos sobre listas encadeadas ficam mais simples quando escritos em estilo recursivo.
Exemplo. A seguinte função recursiva imprime o conteúdo de uma lista encadeada le:
void imprime (celula *le) {
if (le != NULL) {
printf ("%d\n", le->conteudo);
imprime (le->prox);
}
}
E aqui está a versão iterativa da mesma função:
void imprime (celula *le) {
celula *p;
for (p = le; p != NULL; p = p->prox)
printf ("%d\n", p->conteudo);
}
Explicação: