Considere as estruturas seguintes:
typedef struct no{
int ch;
struct no *prox, *ant;
}No;
typedef struct lista {
No *inicio, *fim;
} Lista;
Implemente funções que:
a) Cria uma lista vazia.
b) Insere no início da lista.
c) Insere no final da lista.
d) Remove uma dada chave da lista.
e) Recebe duas listas, L1 e L2, e duas chaves, c1 e c2. Busca c1 na lista L1, busca c2 em L2. Caso as duas chaves existam nas respectivas listas, realiza a troca das chaves entre as listas. Ou seja, retira os nós que contém c1 e c2 de L1 e L2, respectivamente. Insere c1 em L2 na posição onde estava c2. Insere c2 em L1 na posição onde estava c1. 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

Então, temos um exercício de programação em C que trabalha com listas duplamente ligadas. As estruturas usadas são No (nó) e Lista. O conteúdo envolve criação e manipulação de listas, como inserir e remover elementos. Para resolver, vamos precisar entender como funcionam as listas duplamente ligadas e como implementar as funções solicitadas passo a passo.

Passo 2

a) Cria uma lista vazia.
Para criar uma lista vazia, precisamos inicializar uma estrutura Lista onde os ponteiros para o início e o fim são NULL, indicando que não há elementos na lista.
Lista* criaLista() {
    Lista* lista = (Lista*) malloc(sizeof(Lista));
    lista->inicio = NULL;
    lista->fim = NULL;
    return lista;
}

Passo 3

b) Insere no início da lista.
Para inserir um elemento no início, criamos um novo nó com a chave desejada. Se a lista estiver vazia, esse nó será tanto o início quanto o fim. Caso contrário, ligamos o novo nó ao antigo início e atualizamos o ponteiro do início.
void insereInicio(Lista* lista, int chave) {
    No* novo = (No*) malloc(sizeof(No));
    novo->ch = chave;
    novo->prox = lista->inicio;
    novo->ant = NULL;
    if (lista->inicio != NULL) {
        lista->inicio->ant = novo;
    } else {
        lista->fim = novo;
    }
    lista->inicio = novo;
}

Passo 4

c) Insere no final da lista.
Para inserir no final, criamos um novo nó. Se a lista estiver vazia, esse nó é o início e o fim. Se não, ligamos o novo nó ao fim atual e atualizamos o ponteiro do fim.
void insereFinal(Lista* lista, int chave) {
    No* novo = (No*) malloc(sizeof(No));
    novo->ch = chave;
    novo->prox = NULL;
    novo->ant = lista->fim;
    if (lista->fim != NULL) {
        lista->fim->prox = novo;
    } else {
        lista->inicio = novo;
    }
    lista->fim = novo;
}

Passo 5

d) Remove uma dada chave da lista.
Para remover um nó com uma chave específica, precisamos primeiro encontrá-lo. Percorremos a lista até encontrar o nó. Depois, atualizamos os ponteiros dos nós anteriores e posteriores para excluir o nó encontrado da lista, liberando sua memória.
void removeChave(Lista* lista, int chave) {
    No* atual = lista->inicio;
    while (atual != NULL && atual->ch != chave) {
        atual = atual->prox;
    }
    if (atual == NULL) {
        return; // Chave não encontrada
    }
    if (atual->ant != NULL) {
        atual->ant->prox = atual->prox;
    } else {
        lista->inicio = atual->prox;
    }
    if (atual->prox != NULL) {
        atual->prox->ant = atual->ant;
    } else {
        lista->fim = atual->ant;
    }
    free(atual);
}

Passo 6

e) Troca de chaves entre duas listas.
Vamos criar uma função que recebe duas listas L1 e L2, e duas chaves c1 e c2. Primeiro, buscamos c1 em L1 e c2 em L2. Se ambas existirem, removemos os nós correspondentes e inserimos as chaves na posição onde estavam na outra lista.
void trocaChaves(Lista* L1, Lista* L2, int c1, int c2) {
    No* nodo1 = L1->inicio;
    while (nodo1 != NULL && nodo1->ch != c1) {
        nodo1 = nodo1->prox;
    }
    No* nodo2 = L2->inicio;
    while (nodo2 != NULL && nodo2->ch != c2) {
        nodo2 = nodo2->prox;
    }
    if (nodo1 != NULL && nodo2 != NULL) {
        // Remover os nós
        if (nodo1->ant != NULL) {
            nodo1->ant->prox = nodo1->prox;
        } else {
            L1->inicio = nodo1->prox;
        }
        if (nodo1->prox != NULL) {
            nodo1->prox->ant = nodo1->ant;
        } else {
            L1->fim = nodo1->ant;
        }
        if (nodo2->ant != NULL) {
            nodo2->ant->prox = nodo2->prox;
        } else {
            L2->inicio = nodo2->prox;
        }
        if (nodo2->prox != NULL) {
            nodo2->prox->ant = nodo2->ant;
        } else {
            L2->fim = nodo2->ant;
        }
        // Trocar as chaves
        int temp = nodo1->ch;
        nodo1->ch = nodo2->ch;
        nodo2->ch = temp;
        // Reinserir os nós nas posições originais
        // Inserir nodo1 em L2
        if (nodo2->ant != NULL) {
            nodo2->ant->prox = nodo1;
            nodo1->ant = nodo2->ant;
        } else {
            L2->inicio = nodo1;
            nodo1->ant = NULL;
        }
        nodo1->prox = nodo2->prox;
        if (nodo2->prox != NULL) {
            nodo2->prox->ant = nodo1;
        } else {
            L2->fim = nodo1;
        }
        // Inserir nodo2 em L1
        if (nodo1->ant != NULL) {
            nodo1->ant->prox = nodo2;
            nodo2->ant = nodo1->ant;
        } else {
            L1->inicio = nodo2;
            nodo2->ant = NULL;
        }
        nodo2->prox = nodo1->prox;
        if (nodo1->prox != NULL) {
            nodo1->prox->ant = nodo2;
        } else {
            L1->fim = nodo2;
        }
    }
}

Passo 7

f) Calcula a função de complexidade de tempo da função do item anterior.
Analisando a função trocaChaves, vemos que ela percorre ambas as listas uma vez para encontrar os nós com as chaves c1 e c2. Cada percorre é proporcional ao tamanho das listas, digamos n e m. As operações de remoção e inserção são constantes após encontrar os nós. Portanto, a complexidade de tempo é linear em relação ao tamanho das listas.
Notação assintótica: O(n + m)

Resposta

Finalizamos a implementação das funções para manipulação de listas duplamente ligadas e determinamos que a complexidade da função de troca de chaves é O(n + m).

Exercícios relacionados