Considere a lista simplesmente encadeada para os itens a seguir. Declare uma estrutura de uma lista simplesmente encadeada de números inteiros e implemente as seguintes funções:
a) Criar um novo nó, dado uma chave;
b) Imprimir os números contidos numa lista;
c) Inserir um nó criado no início de uma lista;
d) Inserir um nó criado no final de uma lista;
e) Remover todos os nós da lista que possuem informações duplicadas (deixe apenas uma ocorrência de cada número e dar free nos nós com valores repetidos);
f) Imprime o total de ocorrências de um número em uma lista;
g) Multiplica todos os números da lista por 10;
h) Imprime na tela se uma dada lista está ordenada ou não.
i) Intercale duas listas encadeadas ordenadas. A lista resultante tem que estar ordenada. Sua função deve ter complexidade linear.
j) Calcule a complexidade da função do item anterior.
a) Criar um novo nó, dado uma chave;
b) Imprimir os números contidos numa lista;
c) Inserir um nó criado no início de uma lista;
d) Inserir um nó criado no final de uma lista;
e) Remover todos os nós da lista que possuem informações duplicadas (deixe apenas uma ocorrência de cada número e dar free nos nós com valores repetidos);
f) Imprime o total de ocorrências de um número em uma lista;
g) Multiplica todos os números da lista por 10;
h) Imprime na tela se uma dada lista está ordenada ou não.
i) Intercale duas listas encadeadas ordenadas. A lista resultante tem que estar ordenada. Sua função deve ter complexidade linear.
j) Calcule a complexidade da função do item anterior.
Passo 1
Beleza! Vamos resolver esse exercício juntos. O que a gente tem aqui é um trabalho com listas simplesmente encadeadas em programação, que são estruturas de dados usadas para armazenar sequências de elementos. A gente vai precisar entender como declarar essa estrutura, além de implementar várias funções para manipular a lista, como criar nós, imprimir elementos, inserir no início ou no fim, remover duplicados, contar ocorrências, multiplicar valores, verificar se está ordenada, e intercalar duas listas ordenadas. Vamos passo a passo!
Passo 2
Primeiro, vamos declarar a estrutura de uma lista simplesmente encadeada para armazenar números inteiros. Em C, por exemplo, isso é feito usando
struct
. Cada nó da lista vai ter um valor
e um ponteiro para o próximo nó. Aqui está como fica:typedef struct No {
int valor;
struct No* proximo;
} No;
Explicando:
typedef
cria um novo tipo chamado No
. Cada No
tem um inteiro valor
e um ponteiro proximo
que aponta para o próximo nó na lista. Se proximo
for NULL
, significa que é o último nó da lista.Passo 3
Agora, vamos para a função a): Criar um novo nó, dado uma chave. Essa função vai alocar memória para um novo nó, atribuir o valor passado e definir o próximo como
NULL
.No* criarNo(int chave) {
No* novo = (No*)malloc(sizeof(No));
if (novo == NULL) {
printf("Erro ao alocar memória.\n");
exit(1);
}
novo->valor = chave;
novo->proximo = NULL;
return novo;
}
Explicação: Usamos
malloc
para alocar memória. Verificamos se a alocação foi bem-sucedida. Depois, atribuímos o valor e inicializamos o ponteiro proximo
como NULL
.Passo 4
Vamos para a função b): Imprimir os números contidos numa lista. Essa função vai percorrer cada nó da lista e imprimir seu valor.
void imprimirLista(No* cabeca) {
No* atual = cabeca;
while (atual != NULL) {
printf("%d -> ", atual->valor);
atual = atual->proximo;
}
printf("NULL\n");
}
Explicação: Começamos com o
cabeca
(início da lista) e percorremos cada nó até chegar em NULL
, imprimindo os valores.Passo 5
Agora, função c): Inserir um nó criado no início de uma lista. Aqui, a gente ajusta o ponteiro do novo nó para apontar para o antigo primeiro nó e depois atualiza a cabeça da lista.
void inserirNoInicio(No** cabeca, No* novo) {
novo->proximo = *cabeca;
*cabeca = novo;
}
Explicação: Recebemos um ponteiro para o
cabeca
(usando No**
para modificar o ponteiro original). O novo nó aponta para o antigo primeiro nó, e então atualizamos a cabeça para ser o novo nó.Passo 6
Seguimos para a função d): Inserir um nó criado no final de uma lista. Aqui, a gente percorre a lista até o último nó e ajusta seu ponteiro para o novo nó.
void inserirNoFinal(No** cabeca, No* novo) {
if (*cabeca == NULL) {
*cabeca = novo;
return;
}
No* atual = *cabeca;
while (atual->proximo != NULL) {
atual = atual->proximo;
}
atual->proximo = novo;
}
Explicação: Se a lista estiver vazia (
cabeca
é NULL
), o novo nó se torna a cabeça. Caso contrário, percorremos até o final e inserimos o novo nó.Passo 7
Vamos para a função e): Remover todos os nós da lista que possuem informações duplicadas. A ideia é manter apenas uma ocorrência de cada número.
void removerDuplicados(No* cabeca) {
No* atual = cabeca;
while (atual != NULL && atual->proximo != NULL) {
No* runner = atual;
while (runner->proximo != NULL) {
if (runner->proximo->valor == atual->valor) {
No* temp = runner->proximo;
runner->proximo = runner->proximo->proximo;
free(temp);
} else {
runner = runner->proximo;
}
}
atual = atual->proximo;
}
}
Explicação: Usamos dois ponteiros:
atual
para percorrer cada nó e runner
para verificar duplicados à frente. Se encontrar um duplicado, remove aquele nó e libera a memória com free
.Passo 8
Agora, função f): Imprime o total de ocorrências de um número em uma lista. Vamos contar quantas vezes um número específico aparece.
int contarOcorrencias(No* cabeca, int numero) {
int contador = 0;
No* atual = cabeca;
while (atual != NULL) {
if (atual->valor == numero) {
contador++;
}
atual = atual->proximo;
}
return contador;
}
Explicação: Inicializamos um contador e percorremos a lista, incrementando quando encontramos o número buscado. No final, retornamos a contagem.
Passo 9
Seguimos para a função g): Multiplica todos os números da lista por 10. Aqui, apenas atualizamos o valor de cada nó.
void multiplicarPorDez(No* cabeca) {
No* atual = cabeca;
while (atual != NULL) {
atual->valor *= 10;
atual = atual->proximo;
}
}
Explicação: Percorremos cada nó e multiplicamos o valor por 10 diretamente.
Passo 10
Vamos para a função h): Imprime na tela se uma dada lista está ordenada ou não. A gente verifica se cada elemento é menor ou igual ao próximo.
int estaOrdenada(No* cabeca) {
if (cabeca == NULL || cabeca->proximo == NULL) {
return 1; // Lista vazia ou com um elemento está ordenada
}
No* atual = cabeca;
while (atual->proximo != NULL) {
if (atual->valor > atual->proximo->valor) {
return 0; // Não está ordenada
}
atual = atual->proximo;
}
return 1; // Está ordenada
}
Explicação: Se a lista tiver 0 ou 1 elemento, está ordenada. Caso contrário, percorremos e verificamos se cada elemento é menor ou igual ao próximo. Se encontrar algum que não segue a ordem, retorna que não está ordenada.
Passo 11
Chegamos à função i): Intercale duas listas encadeadas ordenadas. A ideia é mesclar duas listas em uma nova lista, mantendo a ordem, com complexidade linear.
No* intercalarListas(No* lista1, No* lista2) {
No dummy;
No* tail = &dummy;
dummy.proximo = NULL;
while (lista1 != NULL && lista2 != NULL) {
if (lista1->valor <= lista2->valor) {
tail->proximo = lista1;
lista1 = lista1->proximo;
} else {
tail->proximo = lista2;
lista2 = lista2->proximo;
}
tail = tail->proximo;
}
if (lista1 != NULL) {
tail->proximo = lista1;
} else {
tail->proximo = lista2;
}
return dummy.proximo;
}
Explicação: Usamos um nó
dummy
para facilitar a construção da lista intercalada. Comparamos os valores das duas listas e adicionamos o menor à nova lista, avançando na lista correspondente. Continuamos até que uma das listas termine, e então adicionamos o restante da outra lista. Isso garante que a nova lista esteja ordenada e faz tudo em tempo linear.Passo 12
Finalmente, a função j): Calcule a complexidade da função do item anterior. A complexidade da função
intercalarListas
é O(n), onde n é o total de elementos das duas listas. Isso porque percorremos cada elemento exatamente uma vez.Resposta
Finalizamos a implementação das funções para manipular listas simplesmente encadeadas de números inteiros. A complexidade da função de intercalar duas listas ordenadas é O(n), garantindo eficiência na operação.