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.

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.

Exercícios relacionados