Estruturas Lineares: Lista, fila e pilha

Listas encadeadas

Numas lista encadeada, cada elemento aponta para o próximo, sem que estejam em posiçoes sequenciais na memória.

1. Listas encadeadas simples

Cada elemento aponta apenas para o que vem a seguir. Cada caixinha é chamada de nó ou célula e é implementada da seguinte forma:

type def struct celula{
    int dado;
    struct celula *prox;
} celula;

Implementaremos listas simplesmente encadeadas com nó cabeça;

Criação da lista

celula *cria_lista(){
    celula *le = malloc(sizeof(celula));
    le -> prox = NULL;
    return le;
}

(*le).dado = 10, é a mesma coisa que le -> dado = 10

Busca

Busca Iterativa

celula *busca(celula *le, int x){
    for(celula *ptr = le; ptr != NULL; ptr = ptr -> prox)
        if(ptr -> dado == x) return ptr;
    return NULL;
}

Fazendo alguns exercícios do MOJ, surgiu uma questão de implementar uma função de busca de forma recursiva. Dessa forma:

Busca Recursiva

celula *busca_rec(celula *le, int x){
    if (le == NULL) return NULL;
    if ( le -> prox == x) return le;

    return busca_rec(le->prox, x);
}

Inserção

void insere(celula *ptr, int x){
    celula *novo = malloc(sizeof(celula));
    novo -> dado = x;
    novo -> prox = ptr -> prox;
    ptr -> prox = novo;
} // COMPLEXIDADE: O(1)

Para inserir no começo, basta chamar insere com le. Para inserir depois de um elemento y da lista, basta chamar busca e com seu retorno, chamar insere.

Remoção

int remove(celula *ptr){
    celula *lixo = ptr -> prox;
    celula *proxNo = lixo -> prox;
    int x = lixo -> dado;
    ptr -> prox = proxNo;

    free(lixo);
    return x;
}

Para remover o primeiro elemento da lista, chama-se remove com le.

Agora para exercitar, pense:

• Como remover um elemento y?

  • Estive estudando, e o princípio é. Temos que saber a celula anterior a que queremos saber, e fazer essa anterior apontar para a que ela aponta. Dessa forma:

  ```c int removeItem(celula le, int x){ for ( celula atual = le; atual != NULL; atual = atual -> prox){ if ( atual -> prox -> dado == x){ celula *to_remove = atual -> prox;

          atual -> prox = to_remove -> prox;
  
          free(to_remove);
  
          return 1;
      }
  }
  return 0; // 0 se n econtrou
  

  } ```

• Como remover o último elemento da lista?

  • Podemos seguir do mesmo jeito, achamos o último elemento que aponta para NULL, pegamos o antecessor e apontamos para NULL; ```c int removeUltimo(celula *le){ if(le -> prox == NULL) return 0;

    for (celula *atual = le; atual != NULL; atual = atual -> prox){ if ( atual -> prox -> prox == NULL) { free(atual->prox); atual -> prox = NULL; return 1; } } return 0; } ```

Destroi lista

void destroi_lista(celula *le){
    while(le -> prox != NULL)
        remove(le);
    free(le);
} // COMPLEXIDADE: O(n)

Pilhas

São estruturas do tipo LIFO (Last-In-Fist-Out). Tem dois jeitos de fazer uma pilha, usando:

• Vetores
• Listas Encadeadas

Usando listas encadeadas é praticamente a mesma forma de implementar uma lista. Então vou implementar uma usando vetores.

Pilhas com Vetores

type def struct {
    int *dado;
    int n; // tamanho
    int topo;
}pilha

Criacao da pilha

pilha *cria_pilha(int tam){
    pilha *p = malloc(sizeof(pilha));
    p -> dado = malloc(tam * sizeof(int));
    p -> n = tam;
    p -> topo = 0;
    return p;
}

Empilha

    int empilha(pilha *p, int x){
        if(p -> topo == p -> n){
            p -> dado = realloc(p -> dado, 2 * p -> tam * sizeof(int));
            if(p -> dado == NULL) return 1; // Estouro
            p -> n *= 2;
        }
        p -> dado[p -> topo++] = x;
        return 0; // bem sucedido
    } // O(1)

Desempilha

    int desempilha(pilha *p, int *y){
        if(p -> topo == 0) return 1; //erro
        p -> topo--;
        *y = p -> dado[p -> topo];
        return 0;
    } O(1)

Destroi pilha

    void destroi_pilha(pilha *p){
        free(p->dado);
        free(p);
    }

Fila

São estruturas do tipo FIFO (First-In-First-Out). Tem dois jeitos de fazer uma fila, usando:

• Vetores
• Lista encadeada

Por meio de vetores

Vou mostrar a implementação via vetor, mas o indicado é sempre por lista encadeada para não se preocupar com redimensionamento. Utilizando o conceito de fila circular, para não ficar tão simples.

type def struct{
    int *dado;
    int s, e; // start e end
    int n; // tamanho
}

Criar fila

fila *cria_fila(int tam){
    fila *f = malloc(sizeof(fila));
    f -> dado = malloc(tam * sizeof(int));
    f -> s = f -> = 0;
    f -> n = tam;
    return f;
}

Insere na Fila

int enfileira(fila *f, int x){
    if ((f -> e+1)%f -> n == f -> s) if (redimensiona(f)) return 1;
    f -> dado[f -> e] = x;
    f -> e = (f -> e+1) % f -> n;

    return 0; // deu certo
}

Remove da Fila

int desenfileira(fila *f, int *y){
    if (f -> e == f -> s) return 1; // vazia
    *y = f -> dado[f -> s];
    f -> s = (f -> s+1) % f -> n;
    return 0; // deu certo
}