Listas Lineares Ligadas (ou Encadeadas) + Implementação Dinâmicas

Código da aula:

// Aula do dia 14/09 - Quinta-feira
// Listas Ligadas Dinâmicas
#include <malloc.h>
# include <stdbool.h>

typedef struct estrutura {
    int chave;
    int info;
    struct estrutura *prox;
} NO;

typedef struct {
    NO* inicio;
} LISTA;

// BUSCA
NO* busca(LISTA *l, int ch, NO* *ant){ // busca ....... &ant (ficaria assim a implementação)
    *ant = NULL;
    NO* p = l->inicio;
    while (p){
        if(p->chave = ch) return p;
        if(p->chave > ch) return NULL; // Só funciona em uma lista ordenada por chave
        *ant = p;
        p = p->prox;
    }
    return NULL; // Isso é caso não funcione em nenhum dos casos acima
}

// TODO: Colocar lado a lado (busca diâmica e Busca sequencial)
// TODO: Por que ' NO* *ant)';
// Eu posso modificar ele - NO* *ant (Eu posso fazer o que precisar com isso)

// EXCLUSÃO
bool excluir(LISTA *l, int ch){
    NO* ant;
    NO* atual = busca(l, ch, &ant);
    if (atual == NULL) return false; // Ou if (!atual)
    if (ant) ant->prox = atual->prox; // se existe um anterior
    else l->inicio = atual->prox; // Caso seja o primeiro item e não haja algo antes
    // Depois preciso fazer o free (liberar o espaço);
    free(atual);
    return true;
}

// INSERÇÃO (ela insere na ordem);
bool inserir(LISTA *l, int ch){
    NO* ant;
    NO* atual = busca(l, ch, &ant);
    if(atual) return false; // Já existe
    NO* novo = (NO*) malloc(sizeof(NO)); // Aqui o NO sem asteriscos é a estrutura, o tipo!
    novo->chave = ch;
    // Agora preciso tratar os casos de inserção
    // Caso haja um anterior

    // Agora verifico se a lista está vazia (se não existe início) e já aplico os dois casos
    if(ant) {
        novo->prox = ant->prox;
        ant->prox = novo;
    }
    else{
        novo->prox = l->inicio; // Lista vazia é quando o iníccio é null
        l->inicio = novo;
    }   
    return true; 
}

// (1) MOVER Ch para frente da lista (versão 1);
// (2) MOVER P para frente da lista (versão 2);

// (Versão 1);
void moverChParaInicio(LISTA *l, int ch){ // Aqui é um caso especial
    NO* ant;
    if(l->inicio && l->inicio->chave == ch) return; // Passo 1: preciso mover?
    NO* p = busca(l, ch, &ant); // Passo 2: Busca
    if(ant) ant->prox = p->prox;  // Passo 3: Recortar o elemento
    else l->inicio = p->prox;
    // Agora movo para o início da lista
    p->prox = l->inicio; // Passo 4: Colocar no início
    l->inicio = p;
}

// Obs: A (versão 2) ele fez na lousa mas não consegui anotar

// Destruir a lista
void destruir(LISTA* l){
    NO* p = l->inicio;
    while(p){
        NO* aux = p->prox;
        free(p);
        p = aux;
    }
    l->inicio = NULL;
}

// Seja uma lista que aceita chaves repetidas, sem ordem;
// Problema: eliminar todas ocorrências de uma chave ch

Listas Ligadas (Implementação Dinâmica) | Univesp

Código da aula A cada elemento novo a gente aloca memória e quando não usamos mais a gente libera ela. A lista é ligada porque cada elemento aponta pra seu próximo. Antes a implementação era estática, ou seja, envolvia a criação de um arranjo;

Implementação Dinâmica

Alocaremos e desalocaremos a memória para os elementos sob demanda Vantagens: Não precisamos gastar memória que não estamos usando e não precisamos gerenciar uma lista de elementos disponíveis.

Precisaremos de um ponteiro chamado início que irá dizer em qual endereço de memória está o início da lista;
Cada elemento terá um endereço de memória do próximo (não será mais um arranjo);

Modelagem

#include <stdio.h>
#include <malloc.h>

typedef int bool;
typedef int TIPOCHAVE;

typedef struct {
    TIPOCHAVE chave;
    // outros campos..
} REGISTRO;

typedef struct aux{
    REGISTRO reg;
    struct aux* prox;
} ELEMENTO;

typedef ELEMENTO* PONT;

typedef struct {
    PONT inicio;
} LISTA;

Inicializar:

2023-09-25_16h42_35

Retornar a número de elementos

2023-09-25_16h43_29

int tamanho(LISTA* l){
    PONT end = l->inicio;
    int tam = 0;
    while(end != NULL){
        tam++;
        end = end->prox;
    }
    return tam;
}

Exibir/Impressão

2023-09-25_16h47_58

void exibirLista(LISTA* l){
    PONT end = l->inicio;
    printf("Lista: \" ");
        printf("%i ", end->reg.chave);
        end = end->prox;
    printf("\"\"n");
}

Buscar por um elemento na estrutura

2023-09-25_16h51_23

// Buscar por um elemento na estrutura 
// (1) Sem estar ordenanda:
PONT buscaSequencial(LISTA* l, TIPOCHAVE ch){
    PONT pos = l->inicio;
    while(pos != NULL){
        if (pos->reg.chave == ch) return pos;
        pos = pos->prox;
    }
    return NULL;
}

// (2) Lista ordenada pelos valores das cahves dos registros (Ordenada)
PONT buscaSeqOrd(LISTA* l, TIPOCHAVE ch){
    PONT pos = l->inicio;
    while(pos != NULL && pos->reg.chave < ch) pos = pos->prox;
    if (pos != NULL & pos->reg.chave == ch) return pos;
    return NULL;
}

Inserir elementos na estrutura

2023-09-25_17h00_19 2023-09-25_17h01_47

Precisaremos de uma função auxiliar!

Exemplo de código:

2023-09-25_17h04_16

Obs: ou seja, eu retorno um valor e salvo também outro valor num espaço de memória que vem como parâmetro.;

Voltando...

2023-09-25_17h07_06

// Inserir elementos na estrutura

// (1) Função auxiliar que vai verificar se o elemento que quero inserir já existe:
PONT buscaSequencialEx(LISTA* l, TIPOCHAVE ch, PONT* ant){
    *ant = NULL;
    PONT atual = l->inicio;
    while((atual != NULL) && (atual->reg.chave<ch)){
        *ant = atual;
        atual = atual->prox;
    }
    if((atual != NULL) && (atual->reg.chave == ch)) return atual;
    return NULL;
    // IMPORTANTE: Independente se encontrar ou não, a variável ant terá o endereço do elemento anterior ao que deve ser inserido
}

// (2) Insersão ordenada:
bool inserirElemListaOrd(LISTA* l, REGISTRO reg){
    TIPOCHAVE ch = reg.chave;
    PONT ant, i;
    i = buscaSequencialEx(l, ch, &ant);
    if(i != NULL) return false; // Ou seja, já existe
    i = (PONT) malloc(sizeof(ELEMENTO)); // Senão ele aloca memória para esse elemento
    i->reg = reg;
    if(ant == NULL){ // Caso seja o primeiro
        i->prox = l->inicio;
        l->inicio = i;
    } else{ // Caso não saja o primeiro
        i->prox = ant->prox;
        ant->prox = i;
    }
    return true;
}

Exclusão de um elemento

2023-09-25_17h21_17


// Exclusão de um elemento
bool excluirElmLista(LISTA* l, TIPOCHAVE ch){
    PONT ant, i;
    i = buscaSequencialEx(l,ch,&ant);
    if (i == NULL) return false;
    if (ant == NULL) l->inicio = i->prox; // Caso seja o primeiro
    else ant->prox = i->prox; // Caso não seja o primeiro
    free(i); // Libero o i
}

Reinicialização da lista

// Reinicialização da lista
// Precisamos liberar/excluir todos os elementos dentro da lista (não basta só dizer que início é NULL)
void reinicializarLista(LISTA* l){
    PONT end = l->inicio;
    // Eu preciso de uma auxiliar porque preciso saber quem é o próximo elemento. Ela se chama apagar
    while (end != NULL){
        PONT apagar = end; // Essa é a variável auxiliar
        end = end->prox;
        free(apagar);
    }
    l->inicio = NULL;
}

JayCesar / USP_AED1_EXER