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,
e
, e duas chaves,
e
. Busca
na lista
, busca
em
. 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
e
de
e
, respectivamente. Insere
em
na posição onde estava
. Insere
em
na posição onde estava
. 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.
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,
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:
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 é
.