Desafio 1: Implemente o TAD Listas duplamente ligadas de inteiros. Deve ter as operações abaixo: (2 V):
a. Inicializar lista
a. Inicializar lista
Passo 1
Beleza, vamos lá! Você precisa implementar um Tipo Abstrato de Dados (TAD) para Listas Duplamente Ligadas de inteiros. Isso faz parte da matéria de Estruturas de Dados. Para começar, a gente vai precisar entender como uma lista duplamente ligada funciona e criar uma estrutura básica para representar essa lista no código.
Passo 2
Primeiro, vamos definir como será a estrutura de um nó na nossa lista. Em uma lista duplamente ligada, cada nó tem três partes: o valor inteiro que ele armazena, um ponteiro para o nó anterior e outro para o próximo nó. Isso permite navegar tanto para frente quanto para trás na lista.
Passo 3
Aqui está como podemos representar isso em código usando C:
typedef struct No {
int valor;
struct No* anterior;
struct No* proximo;
} No;
Nessa estrutura,
valor
guarda o número inteiro, anterior
aponta para o nó antes desse, e proximo
para o próximo nó.Passo 4
Agora, vamos criar a estrutura para a lista em si. A lista vai manter um ponteiro para o primeiro nó (cabeça) e outro para o último nó (cauda). Isso facilita operações como inserção e remoção de elementos no início e no fim da lista.
Passo 5
Segue a estrutura da lista:
typedef struct Lista {
No* cabeca;
No* cauda;
} Lista;
Inicialmente, quando a lista está vazia, tanto
cabeca
quanto cauda
serão NULL
.Passo 6
Para inicializar a lista, precisamos criar uma função que aloque memória para a lista e configure os ponteiros
cabeca
e cauda
como NULL
, indicando que a lista está vazia.Passo 7
Aqui está a função de inicialização:
Lista* inicializarLista() {
Lista* lista = (Lista*) malloc(sizeof(Lista));
lista->cabeca = NULL;
lista->cauda = NULL;
return lista;
}
Essa função usa
malloc
para reservar espaço na memória para a lista e define cabeca
e cauda
como NULL
.Resposta
Pronto! Agora você tem uma função que inicializa uma lista duplamente ligada de inteiros, pronta para ser usada nas operações seguintes.