Considere a lista duplamente 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 numa lista ordenada. O resultado deve ser uma lista ordenada.
d) 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).
e) Intercale duas listas encadeadas ordenadas. A lista resultante tem que estar ordenada. Sua função deve ter complexidade linear.
f) Calcule a função de complexidade de tempo da função do item anterior. Conclua com a notação assintótica da complexidade calculada.
a) Criar um novo nó, dado uma chave.
b) Imprimir os números contidos numa lista.
c) Inserir um nó criado numa lista ordenada. O resultado deve ser uma lista ordenada.
d) 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).
e) Intercale duas listas encadeadas ordenadas. A lista resultante tem que estar ordenada. Sua função deve ter complexidade linear.
f) Calcule a função de complexidade de tempo da função do item anterior. Conclua com a notação assintótica da complexidade calculada.
Passo 1
Beleza, vamos dar uma olhada no que a questão tá pedindo. A gente precisa trabalhar com uma lista simplesmente encadeada de números inteiros. Isso faz parte da matéria de Estruturas de Dados. Vamos precisar entender como declarar uma estrutura de nó, criar e manipular essa lista com as funções que a questão pede: criar nós, imprimir a lista, inserir nós de forma ordenada, remover duplicatas, intercalar duas listas e calcular a complexidade de tempo dessa interlação.
Passo 2
Primeiro, vamos declarar a estrutura de um nó para uma lista simplesmente encadeada de números inteiros. Cada nó vai ter uma chave (o número inteiro) e um ponteiro para o próximo nó.
typedef struct No {
int chave;
struct No* proximo;
} No;
Aqui,
typedef
cria um apelido para a estrutura, facilitando o uso depois. O int chave
armazena o valor do nó, e struct No* proximo
aponta para o próximo nó na lista.Passo 3
Agora, vamos implementar a função a) para criar um novo nó dado uma chave. Essa função vai alocar memória para um novo nó, atribuir o valor da chave e apontar o próximo para
NULL
.No* criarNo(int chave) {
No* novoNo = (No*)malloc(sizeof(No));
if (novoNo == NULL) {
printf("Erro ao alocar memória.\n");
exit(1);
}
novoNo->chave = chave;
novoNo->proximo = NULL;
return novoNo;
}
Explicando: usamos
malloc
para reservar espaço na memória. Se a alocação falhar, exibimos uma mensagem de erro. Atribuímos a chave passada e inicializamos o ponteiro proximo
como NULL
porque, nesse momento, o nó não aponta para nenhum outro.Passo 4
Vamos para a função b), que é imprimir os números contidos na lista. A gente vai percorrer a lista do início até o final, imprimindo cada chave encontrada.
void imprimirLista(No* cabeca) {
No* atual = cabeca;
while (atual != NULL) {
printf("%d ", atual->chave);
atual = atual->proximo;
}
printf("\n");
}
Aqui, começamos com o nó cabeça e usamos um ponteiro
atual
para percorrer a lista. Enquanto atual
não for NULL
, imprimimos a chave e avançamos para o próximo nó.Passo 5
Agora, vamos implementar a função c): inserir um nó criado numa lista ordenada, mantendo a lista ordenada. A ideia é encontrar a posição correta para inserir o novo nó de forma que a ordem seja mantida.
void inserirOrdenado(No** cabeca, int chave) {
No* novoNo = criarNo(chave);
// Se a lista estiver vazia ou o novo nó deve ser o primeiro
if (*cabeca == NULL || (*cabeca)->chave >= chave) {
novoNo->proximo = *cabeca;
*cabeca = novoNo;
return;
}
// Procurar a posição de inserção
No* atual = *cabeca;
while (atual->proximo != NULL && atual->proximo->chave < chave) {
atual = atual->proximo;
}
novoNo->proximo = atual->proximo;
atual->proximo = novoNo;
}
Explicação: Recebemos um ponteiro para o
cabeca
(por referência). Se a lista estiver vazia ou o novo nó tiver uma chave menor que a cabeça, inserimos no início. Caso contrário, percorremos a lista até encontrar o local certo onde a chave do próximo nó é maior ou igual à chave que queremos inserir. Inserimos o novo nó nesse ponto.Passo 6
Vamos para a função d): remover todos os nós da lista que possuem informações duplicadas, deixando apenas uma ocorrência de cada número. Para isso, vamos percorrer a lista e eliminar os nós que têm chaves repetidas.
void removerDuplicados(No* cabeca) {
if (cabeca == NULL) return;
No* atual = cabeca;
while (atual->proximo != NULL) {
if (atual->chave == atual->proximo->chave) {
No* temp = atual->proximo;
atual->proximo = atual->proximo->proximo;
free(temp);
} else {
atual = atual->proximo;
}
}
}
Explicação: Começamos com o nó cabeça. Enquanto houver um próximo nó, comparamos a chave do nó atual com a do próximo. Se forem iguais, removemos o próximo nó ajustando os ponteiros e liberando a memória. Se não, avançamos para o próximo nó.
Passo 7
Agora, vamos implementar a função e): intercalar duas listas encadeadas ordenadas de forma que a lista resultante também esteja ordenada, com complexidade linear. Isso significa que vamos comparar os elementos das duas listas e construir uma nova lista ordenada sem precisar realizar buscas adicionais.
No* intercalarListas(No* lista1, No* lista2) {
No dummy;
No* tail = &dummy;
dummy.proximo = NULL;
while (lista1 != NULL && lista2 != NULL) {
if (lista1->chave <= lista2->chave) {
tail->proximo = lista1;
lista1 = lista1->proximo;
} else {
tail->proximo = lista2;
lista2 = lista2->proximo;
}
tail = tail->proximo;
}
// Anexar o que sobrar
if (lista1 != NULL) {
tail->proximo = lista1;
} else {
tail->proximo = lista2;
}
return dummy.proximo;
}
Explicação: Usamos um nó fictício
dummy
para facilitar a manipulação dos ponteiros. Enquanto ambas as listas tiverem nós, comparamos as chaves e anexamos o menor nó à lista resultante. Depois que uma das listas terminar, anexamos o restante da outra lista. Essa abordagem garante que a complexidade seja linear, $ O(n + m) $, onde $ n $ e $ m $ são os tamanhos das duas listas.Passo 8
Finalmente, vamos para a função f): calcular a complexidade de tempo da função de intercalar duas listas ordenadas e concluir com a notação assintótica.
Como vimos na implementação da função de intercalação, percorremos cada nó das duas listas uma única vez, comparando pares de elementos. Isso significa que, se a primeira lista tem $ n $ elementos e a segunda tem $ m $ elementos, a complexidade de tempo é proporcional a $ n + m $.
Portanto, a complexidade assintótica da função é $ \mathcal{O}(n + m) $.
Resposta
Implementamos todas as funções pedidas para manipular listas simplesmente encadeadas de números inteiros, garantindo operações como criação, inserção ordenada, remoção de duplicatas e intercalação eficiente. A função de intercalação possui complexidade de tempo linear, $ \mathcal{O}(n + m) $, atendendo aos requisitos da questão.