Bem-vindo ao décimo capítulo da Especialização em Engenharia de Sistemas com Linguagem C (C17/C23)! ⚡

Variáveis primitivas individuais armazenam apenas um dado isolado por vez. Na Engenharia de Software, quase todos os problemas práticos exigem o processamento de coleções de dados (sensores, tabelas de cotação, buffers de pacotes de rede). O Vetor Unidimensional (Array 1D) é a estrutura de dados mais elementar e eficiente da computação: um bloco 100% contíguo de memória física com acesso instantâneo em tempo constante $O(1)$.

Vetores Unidimensionais 1D, Memória RAM e Algoritmos em C

🗺️ Mapa Conceitual do Capítulo

graph TD
    A["Vetores 1D em C"] --> B["1. Layout de Memória & O(1)"]
    A --> C["2. Passagem para Funções"]
    A --> D["3. Algoritmos de Busca"]
    A --> E["4. Algoritmos de Ordenação"]

    B --> B1["Indexação base-0, Bloco Contíguo, sizeof(v)/sizeof(v[0])"]
    C --> C1["Decaimento de Ponteiro (Pointer Decay) e envio de size_t n"]
    D --> D1["Busca Linear O(N) vs Busca Binária O(log N)"]
    E --> E1["Bubble Sort O(N²) otimizado e Selection Sort O(N²)"]

📦 1. Mapeamento Físico de Memória e Acesso $O(1)$

Quando você declara um vetor como int v[5];, o compilador reserva um bloco linear e contínuo de bytes na memória Stack. Se sizeof(int) == 4 bytes e o endereço base for 0x1000:

\[\text{Endereco de } v[i] = \text{Endereco Base} + (i \times \text{sizeof}(\text{tipo}))\]
  • $v[0] \rightarrow 0x1000 + (0 \times 4) = \mathbf{0x1000}$
  • $v[1] \rightarrow 0x1000 + (1 \times 4) = \mathbf{0x1004}$
  • $v[2] \rightarrow 0x1000 + (2 \times 4) = \mathbf{0x1008}$
  • $v[3] \rightarrow 0x1000 + (3 \times 4) = \mathbf{0x100C}$
  • $v[4] \rightarrow 0x1000 + (4 \times 4) = \mathbf{0x1010}$

Como a CPU realiza apenas uma multiplicação aritmética e uma soma de registradores para calcular qualquer posição, o tempo de acesso a qualquer elemento é instantâneo e constante: $O(1)$!

Idioma de Engenharia: Contagem de Elementos

Para obter o número de elementos de um vetor estático no mesmo escopo de sua criação:

int leituras[] = {10, 20, 30, 40, 50, 60};
size_t totalElementos = sizeof(leituras) / sizeof(leituras[0]); // 24B / 4B = 6 elementos

⚠️ 2. Passagem para Funções e o Decaimento de Ponteiro (Pointer Decay)

[!CAUTION] Em C, um vetor NUNCA é passado por valor (cópia inteira). Ao passar um vetor para uma função, o nome do vetor “decai” para um ponteiro que aponta para o primeiro elemento (&v[0]). Consequentemente, sizeof(v) dentro da função retornará 8 bytes (tamanho do ponteiro em 64 bits), e não o tamanho total do vetor!

Regra de Ouro: Sempre passe explicitamente o tamanho do vetor como um parâmetro size_t:

void imprimirVetor(const int arr[], size_t tamanho) {
    for (size_t i = 0; i < tamanho; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

🔍 3. Algoritmos de Busca: Linear $O(N)$ vs Binária $O(\log N)$

1. Busca Linear ($O(N)$)

Percorre o vetor do início ao fim até encontrar o alvo. Funciona em vetores não ordenados:

int buscaLinear(const int arr[], size_t n, int chave) {
    for (size_t i = 0; i < n; i++) {
        if (arr[i] == chave) return (int)i; // Encontrado no índice i
    }
    return -1; // Não encontrado
}

2. Busca Binária ($O(\log N)$)

Exige que o vetor esteja previamente ordenado. Divide o espaço de busca pela metade a cada comparação:

int buscaBinaria(const int arr[], size_t n, int chave) {
    int inicio = 0;
    int fim = (int)n - 1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2; // Previne overflow

        if (arr[meio] == chave) {
            return meio; // Encontrado!
        } else if (arr[meio] < chave) {
            inicio = meio + 1; // Busca na metade direita
        } else {
            fim = meio - 1;    // Busca na metade esquerda
        }
    }
    return -1; // Não encontrado
}

🔄 4. Algoritmos de Ordenação Fundamentais: Bubble Sort ($O(N^2)$)

O algoritmo Bubble Sort percorre o vetor comparando pares de elementos adjacentes e trocando-os de posição caso estejam fora de ordem:

void bubbleSort(int arr[], size_t n) {
    for (size_t i = 0; i < n - 1; i++) {
        bool trocou = false;
        for (size_t j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                trocou = true;
            }
        }
        // Se nenhuma troca ocorreu nesta passagem, o vetor já está 100% ordenado!
        if (!trocou) break;
    }
}

🛡️ 5. Boas Práticas e Prevenção de Buffer Overflow (CERT C)

  1. Acesso Fora dos Limites (Out-of-Bounds): Em um vetor de tamanho N, os índices válidos vão de 0 até N - 1. Acessar arr[N] corrompe bytes adjacentes da pilha.
  2. Qualificador const em Funções de Leitura: Se a função apenas lê o vetor sem modificá-lo, declare o parâmetro como const int arr[].
  3. Inicialização com Zero: Para zerar todos os elementos de um vetor estático na declaração: int buffer[100] = {0};.

🔍 6. Diagnóstico & Resolução de Problemas (Troubleshooting)

Sintoma Observado Causa Provável Como Resolver
sizeof(arr) dentro da função retorna 8 em vez do tamanho total O vetor sofreu decaimento de ponteiro (Pointer Decay). Passe a quantidade de elementos como parâmetro adicional size_t n.
A Busca Binária entra em loop infinito ou retorna resultados errados O vetor não estava ordenado previamente ou o cálculo do meio causou overflow. Ordene o vetor antes de chamar a busca binária e use meio = inicio + (fim - inicio) / 2.
O programa trava com comportamento bizarro após preencher um vetor O loop iterou de 0 até <= N em vez de < N (Off-by-one bug / Out-of-bounds). Ajuste a condição de parada para i < N.

🏆 7. Desafio Prático de Consolidação

Enunciado do Desafio: Desenvolva um programa em C chamado radar_velocidade.c para processamento de telemetria de tráfego:

  1. Crie um vetor de números reais (double) com 8 medições de velocidade desordenadas.
  2. Implemente a função void ordenarVelocidades(double arr[], size_t n); usando Bubble Sort ou Selection Sort.
  3. Implemente a função int buscarInfracao(const double arr[], size_t n, double limite); utilizando Busca Binária para localizar se exatamente o limite regulamentar foi atingido.
  4. Exiba no terminal: o vetor original, o vetor ordenado, a velocidade mínima, a máxima e a média aritmética da via.
🔍 Ver Solução Comentada do Desafio 
#include <stdio.h>

int buscaBinaria(const int arr[], size_t n, int chave) {
    int inicio = 0;
    int fim = (int)n - 1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (arr[meio] == chave) return meio;
        if (arr[meio] < chave) inicio = meio + 1;
        else fim = meio - 1;
    }
    return -1;
}

int main(void) {
    int dados[] = {12, 24, 35, 48, 57, 69, 73, 88, 91};
    size_t n = sizeof(dados) / sizeof(dados[0]);

    int chave = 57;
    int idx = buscaBinaria(dados, n, chave);

    if (idx != -1) {
        printf("Chave %d encontrada no indice %d! ✅\n", chave, idx);
    } else {
        printf("Chave nao encontrada.\n");
    }

    return 0;
}