Estruturas de Dados: Conceitos, TADs e Implementações

Tipos de Dados e Abstratos

Tipo de Dado

Define o conjunto de valores que uma variável pode assumir e as operações sobre esses valores. Ex.: Int, Double, Char.

Tipo Abstrato de Dados (TAD)

Define o conjunto de valores e as operações sobre os valores, mas não define sua implementação. Ex.: Lista, Pilha, Fila e Árvore.

Exemplos de Tipos Abstratos de Dados (TADs)

• Lista: Conjunto de itens interligados cujas operações de inserção e remoção podem ser feitas em qualquer parte da lista.
• Pilha: Conjunto de itens interligados cujas operações de inserção e remoção só podem ser feitas no topo da pilha (LIFO - Last In, First Out).
• Fila: Conjunto de itens interligados cuja operação de inserção é feita no final da fila e a operação de remoção é feita no início da fila (FIFO - First In, First Out).
• Árvore: Conjunto de itens interligados na qual cada item tem um ou mais itens associados a ele. Uma árvore contém um nó chamado raiz que está ligado a um conjunto finito de subárvores.

Estrutura de Dados

É uma maneira particular de se implementar um Tipo Abstrato de Dados (TAD). Ex.: Sequencial, Encadeada.

Tipos de Implementação de Estruturas

• Estrutura Sequencial

  Cada item é armazenado em posições contíguas da memória. O tamanho da estrutura deve ser definido na sua criação, e qualquer item pode ser acessado diretamente.

  • Pontos Positivos: Facilidade de acesso a cada item, baixo custo para inserção no final dos itens.
  • Pontos Negativos: Alto custo para inserir ou remover itens no caso de implicar em deslocamento de outros itens. O tamanho fixo pode implicar em falta de espaço.

• Estrutura Encadeada

  Cada item é encadeado por um ponteiro que aponta para o item seguinte da estrutura, permitindo armazenamento em posições não contíguas de memória.

  • Pontos Positivos: Não há desperdício de memória, pois a memória alocada pela estrutura é aquela utilizada pelos itens. O custo é baixo para inserir e remover itens.
  • Ponto Negativo: Custo alto para acessar um determinado item, pois implica em passar por todos os itens que o precedem na estrutura.

Vetor (Array)

É uma estrutura de dados composta que pode armazenar somente valores do mesmo tipo ou objetos da mesma classe. Tem sua capacidade definida na criação.

Método que retorna a quantidade de elementos preenchidos no vetor:

public int quantidadeElementos(int[] vetor) {
    int i;
    int total = 0;
    // Nota: 'n' deve ser o tamanho lógico do vetor ou vetor.length
    for (i = 0; i < n; i++) {
        // Assumindo que 0 representa uma posição vazia
        if (vetor[i] != 0) {
            total++; // Corrigido para contar a quantidade, não somar o valor
        }
    }
    return total;
}

Método que retorna o maior valor armazenado no vetor:

public int obterMaior(int[] vetor) {
    int i;
    // Nota: Inicialização com 0 pode falhar se todos os valores forem negativos.
    int maiorValor = 0;

    // Nota: 'n' deve ser o tamanho lógico do vetor ou vetor.length
    for (i = 0; i < n; i++) {
        if (vetor[i] > maiorValor) {
            maiorValor = vetor[i];
        }
    }
    return maiorValor;
}