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.

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.

Exercícios relacionados