<Direto ao Ponto 46> Estruturas de Dados - Vetores

Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )

Olá, dev!

Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Ele vai tratar de uma das principais estruturas de dados, os vetores.

Sumário

1. Introdução

2. O vetor

3. Exemplos de aplicações implementadas com vetores

4. Considerações finais

5. Referências

1 – Introdução

Eu criei a série de artigos DIRETO AO PONTO com o objetivo de apresentar, de forma simples e direta, conhecimentos básicos da programação e de computação, principalmente, para os iniciantes.

Aqui, são tratados de temas como lógica de programação, linguagens, hardware dos computadores, história da computação e assuntos relacionados à plataforma da DIO, como a escrita de artigos e os desafios de código.

Neste artigo, eu vou falar sobre os vetores e das aplicações que usam vetores na implementação.

Os vetores já eram oferecidos pelas primeiras linguagens de programação, como FORTRAN. Era uma forma de armazenar uma sequência de dados do mesmo tipo em uma mesma variável. Desta forma, era possível implementar aplicações de cadastro de um volume de dados de pessoas, objetos e outros conjuntos de itens.

Atualmente, todas as linguagens de programação modernas oferecem o tipo vetor (array), de diversas formas diferentes. Além disso, a importância dos vetores se mostra na possibilidade de eles serem usados para implementar vários tipos diferentes de estruturas de dados, como pilhas e filas, por exemplo.

Em seguida, vamos ver os vetores em detalhes.

2 – Os vetores (“arrays”)

Um vetor (ou “array”) é uma estrutura de dados muito comum em todas as linguagens de programação. Ele é usado para armazenar uma coleção de dados homogêneos, ou seja, do mesmo tipo (inteiro, float, string, etc.).

Os elementos são armazenados de forma sequencial, um após o outro, na memória, em endereços contíguos. Cada elemento pode ser acessado de forma direta, usando um índice. Nas linguagens modernas, este índice é um número inteiro, que se inicia em zero e cresce em valores positivos, incrementados de 1 em 1;

Em muitas linguagens de programação, o tamanho do vetor é definido no momento da criação e não pode ser alterado. No entanto algumas linguagens implementam o vetor de forma dinâmica, que pode crescer de tamanho.

Um vetor dinâmico é semelhante a um vetor tradicional, mas ele pode ser redimensionado automaticamente à medida que elementos são adicionados ou removidos.

Os vetores dinâmicos são amplamente usados em linguagens de programação modernas, como Python (list), Java (ArrayList) e C++ (std::vector), por exemplo.

O seu funcionamento pode ser resumido assim:

Ele começa com uma capacidade inicial definida (4 elementos). Que é alocada na memória. Quando um novo elemento é adicionado e há espaço suficiente na capacidade atual, o elemento é simplesmente inserido. Caso o vetor esteja cheio, um novo vetor é criado com o dobro da capacidade atual e os elementos existentes são copiados para o novo vetor.

Assim, o vetor cresce de acordo com a necessidade. Mesmo assim, as operações de inserção e remoção de elementos no meio do vetor ainda são custosas, por causa do deslocamento necessário dos elementos.

Os vetores são usados mais comumente para os seguintes tipos de aplicações:

 ·        Armazenamento de coleções de dados, como uma lista de itens (notas de alunos, preços de produtos etc.);

 ·        Implementação de outras estruturas de dados complexas, como listas, filas e pilhas;

 ·        Manipulação de dados, como aqueles usados em operações matemáticas ou em algoritmos de ordenação e busca;

 ·        Uso como buffer e dados em sistemas que exigem processamento de dados em lote, como processamento de imagens;

 ·        Uso em tabelas de alocação de recursos em sistemas operacionais e bancos de dados.

A simplicidade e eficiência dos vetores se devem, em grande parte, às vantagens que eles oferecem, sendo as principais:

 ·        Acesso rápido (imediato) a qualquer elemento por meio do índice, o que é muito eficiente;

 ·        Facilidade de implementação e manipulação, tornando o código mais legível e compreensível;

 ·        Permite otimização da cache de memória, por usar posições contíguas, podendo acelerar o processamento;

 ·        Ótimo desempenho em operações de leitura, escrita e iteração simples.

Mesmo com todas estas vantagens os vetores também apresentam algumas desvantagens, que podem limitar seu uso em algumas aplicações:

·        Desperdício de memória, caso o tamanho do vetor seja maior do que o necessário;

 ·        As operações de inserção ou remoção no meio do vetor são custosas, pois exigem o deslocamento dos elementos;

 ·        Em linguagens que não oferecem vetores dinâmicos, o declarado inicialmente para seu tamanho não pode ser alterado, resultando em falta de flexibilidade para determinadas utilizações;

A figura a seguir mostra uma representação de um vetor em programação. Note que o vetor tem 8 elementos e a representação da memória tem 8 valores armazenados. Na verdade, cada valor inteiro ocupa 4 bytes na memória e ele é representado em binário nela. Eu não dividi cada posição de memória em 4 bytes nem representei cada valor em binário por simplicidade didática.

As operações básicas que podem ser realizadas com um vetor são (em pseudo-código, independentemente de alguma linguagem de programação específica):

Criação (ou declaração) – nomeia a variável, informa o tipo e reserva espaço para os elementos:

int vetor[8];

Inicialização – ao declarar o vetor, já informar os elementos do vetor:

int vetor[8] = {5, 12, -3, 0, 17, -8, 6, 0};

Acesso – acessar o valor armazenado em uma posição do vetor:

temp = vetor[4]; // o valor acessado é 17 (quinto elemento do vetor)

print(vetor[0]) // imprime o valor 5 (primeiro elemento do vetor)

Atribuição – atribuir um valor para uma posição do vetor:

vetor[1] = 100; // atribui o valor 100 ao segundo elemento do vetor (que era 12)

Em geral, o processamento de um vetor em um código envolve o uso de um comando de repetição para varrer os elementos do vetor, da seguinte forma:

// Imprimindo a vetor

printf("Vetor:\n");

for (int i = 0; i < 6; i++) { // varre todos os elementos do vetor

       printf("%d ", vetor[i]); // imprime o elemento [ i ]

}

printf("]\n");

OBS: Esta forma de usar comandos de repetição para percorrer elemento por elemento de um vetor é muito custosa computacionalmente e algumas linguagens modernas (C#, R, Ruby, Haskell, Go, Swift) já oferecem outra forma mais adequada de se manipular vetores e matrizes, tratando-os como um objeto único. O Matlab já oferecia isso há anos e Python também oferece, tanto para o tipo lista (list) ou para as matrizes, por meio do módulo Numpy.

É o fatiamento (slicing), que permite usar fatias (slices) de um vetor (ou de uma matriz) apenas pela indicação de limites dos índices. Veja exemplos em Python, para listas (vetores):

# Criar um vetor (list)

vetor = [10, 20, 30, 40, 50, 60, 70, 80, 90]

A sintaxe usada no fatiamento é vetor[ início : fim ] para selecionar um subvetor. O índice de início é inclusivo e o de fim é exclusivo. Por exemplo, vetor[2:6] gera um vetor menor (fatia) que vai do elemento vetor[2] até antes de vetor[6], ou seja, até vetor[5].

Ex 1. Fatiar parte dos elementos

# Selecionar os elementos do índice 1 ao 4 (elementos das posições 1 até 3)

fatia1 = vetor[1:4]

print(fatia1) # Saída: [20, 30, 40]

Você pode omitir índices de início ou fim:

• Omitindo o início, o fatiamento começará do primeiro elemento;
• Omitindo o fim, o fatiamento irá até o último elemento.

Ex 2. Selecionar os primeiros ou os últimos elementos

# Selecionar do início até o índice 3 (elementos 0, 1, 2)

fatia2 = lista[:3]

print(fatia2) # Saída: [10, 20, 30]

# Selecionar do índice 4 até o fim

fatia3 = lista[4:]

print(fatia3) # Saída: [50, 60, 70, 80, 90]

Pode ser utilizado um terceiro argumento para definir um passo (stride), que define quantos elementos pular entre cada seleção.

Ex 3. Selecionar de 2 em 2 elementos

# Selecionar todos os elementos com passo 2 (de 2 em 2 elementos)

fatia4 = lista[::2]

print(fatia4) # Saída: [10, 30, 50, 70, 90]

O fatiamento pode usar índices negativos, que inicia, a contagem a partir do último elemento. Por exemplo, -1 refere-se ao último elemento, -2 ao penúltimo, e assim por diante.

# Selecionar o último elemento da lista

fatia5 = lista[-1]

print(fatia5) # Saída: 90

# Selecionar os últimos três elementos

fatia 6 = lista[-3:]

print(faftia6) # Saída: [70, 80, 90]

OBS: Em Python, não resulta em erro ao tentar fatiar com índices fora do intervalo válido do vetor.

3 – Exemplos de aplicações implementadas com vetores

O vetor é muito usado em várias linguagens de programação, com implementações específicas adaptadas às características de cada linguagem. Algumas das linguagens mais conhecidas implementam vetores, como C, C++, C#, Java, Javascript, Kotlin e Python.

Algumas delas implementam o vetor estático (como C), já outras implementam também o vetor dinâmico (como Java, Python, C++, C# e Javascript).

A seguir, seguem alguns programas básicos que implementam vetores, em linguagens diferentes:

Na linguagem C – Contagem de elementos positivos, negativos e zero de um vetor estático

#include <stdio.h>
 
int main() {
 int vetor[8] = {5, 12, -3, 0, 17, -8, 6, 0}; // Inicializando o vetor
 
 int positivos = 0, negativos = 0, zeros = 0;
 
 for (int i = 0; i < 8; i++) {
     if (vetor[i] > 0) {
         positivos++;
     } else if (vetor[i] < 0) {
         negativos++;
     } else {
         zeros++;
     }
 }
 
 printf("Quantidade de números positivos: %d\n", positivos);
 printf("Quantidade de números negativos: %d\n", negativos);
 printf("Quantidade de zeros: %d\n", zeros);
 
 return 0;
}

Na linguagem Python – soma sos elementos de um vetor estático

def main():
 # Inicializando o vetor com valores escolhidos
 vetor = [5, 12, 8, 3, 17, 20, 6, 10]
 
 # Calculando a soma
 soma = 0
 for elemento in vetor:
     soma += elemento
 
 print(f"Vetor: {vetor}")
 print(f"Soma dos elementos: {soma}")

Linguagem Java – cálculo da média dos elementos de um vetor estático

public class Main {
 public static void main(String[] args) {
     // Inicializando o vetor com valores escolhidos
     float[] vetor = {5.0f, 12.5f, 8.3f, 3.7f, 17.2f, 20.0f, 6.8f, 10.1f};
 
     // Calculando a soma manualmente
     float soma = 0.0f;
     for (float elemento : vetor) {
         soma += elemento;
     }
 
     // Calculando a média
     float media = soma / vetor.length;
 
     System.out.println("Vetor: " + java.util.Arrays.toString(vetor));
     System.out.println("Média dos elementos: " + media);
 }
}

4 – Considerações finais

Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Neste artigo eu tratei dos vetores, uma estrutura de dados básica e muito importante para a programação.

Desde as primeiras linguagens (FORTRAN e C), um vetor era uma estrutura de dados que armazenava elementos homogêneos (do mesmo tipo), de tamanho fixo (estática), cujos elementos eram armazenados em uma área contígua da memória. Eles eram acessados por um índice inteiro.

Atualmente, além desta forma de se implementar os vetores, existe outra que permite aumentar o tamanho do vetor caso ele já tenha preenchido as posições estabelecidas na sua declaração, o chamado vetor dinâmico.

Neste caso, embora seja um vetor, ele é um tipo diferente (Dinamic Array), sendo implementado de diversas formas nas diferentes linguagens de programação, mais com o comportamento de uma lista do que como vetor (por exemplo, list em Python). 

O vetor é uma estrutura bem simples e permite implementar outras estruturas mais complexas ou com comportamentos diferentes, como pilhas e filas.

No próximo artigo, eu vou começar tratar das cadeias de caracteres (strings), que são vetores que armazenam textos, com funções de manipulação de caracteres específicas.

5 – Referências

Praticamente todo o conteúdo deste artigo foi tirado do que eu aprendi (e me lembro) sobre o assunto desde o início da minha carreira como programador, desde os anos 80 até agora.

Para criar os códigos dos exemplos, eu consultei o ChatGPT e fiz algumas correções necessárias para sair do jeito que eu queria. Todos os códigos foram testados e rodaram sem problemas.

Para a elaboração da lista de tipos de estruturas de dados oferecidas por algumas linguagens, eu consultei as ferramentas ChatGPT e Copilot.

Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )