C: Prática: Vetores e Funções
Por mais técnicas que você aprenda, são apenas teoria até entrar no ringue. Este capítulo integra vetores, funções e ponteiros através de quatro projetos práticos para testar suas habilidades reais.
1. Projeto 1: Bubble Sort
Bubble sort é o algoritmo de ordenação mais básico. A ideia é percorrer repetidamente o vetor, comparando elementos adjacentes e trocando-os se estiverem na ordem errada, até que nenhuma troca ocorra. Cada passagem "borbulha" o maior valor atual para o final.
(1) Passos do algoritmo
- Comece pelo primeiro elemento e compare cada par de elementos adjacentes
- Se o elemento à esquerda é maior que o da direita, troque-os
- Após uma passagem, o maior valor está na posição correta
- Repita para a porção restante até estar totalmente ordenado
(2) Implementação
#include <stdio.h>
void bubble_sort(int *arr, int len) {
int i, j;
int swapped;
for (i = 0; i < len - 1; i++) {
swapped = 0;
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break;
}
}
void print_array(const int *arr, int len) {
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void) {
int data[] = {64, 34, 25, 12, 22, 11, 90};
int len = sizeof(data) / sizeof(data[0]);
printf("Before: ");
print_array(data, len);
bubble_sort(data, len);
printf("After: ");
print_array(data, len);
return 0;
}
ext Before: 64 34 25 12 22 11 90 After: 11 12 22 25 34 64 90
A otimização com flag swapped: se nenhuma troca ocorrer durante uma passagem, o vetor já está ordenado e o algoritmo termina antecipadamente. No melhor caso (já ordenado), a complexidade de tempo cai para O(n).
qsort em projetos reais.
▶ Exemplo
Ordene notas em ordem decrescente usando bubble sort:
#include <stdio.h>
void sort_desc(int *arr, int len) {
int i, j, swapped;
for (i = 0; i < len - 1; i++) {
swapped = 0;
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break;
}
}
int main(void) {
int scores[] = {85, 92, 78, 95, 88};
int len = sizeof(scores) / sizeof(scores[0]);
int i;
sort_desc(scores, len);
printf("Ranking: ");
for (i = 0; i < len; i++) {
printf("%d ", scores[i]);
}
printf("\n");
return 0;
}
ext Ranking: 95 92 88 85 78
Para ordem decrescente, basta mudar a comparação de > para <.
2. Projeto 2: Busca Binária
Busca binária localiza eficientemente um valor alvo em um vetor ordenado dividindo o intervalo de busca pela metade a cada passo.
(1) Passos do algoritmo
- Defina o intervalo de busca como
[low, high] - Calcule a posição do meio:
mid = (low + high) / 2 - Se
rr[mid]é igual ao alvo, foi encontrado - Se
rr[mid]é menor que o alvo, busque na metade direita - Se
rr[mid]é maior que o alvo, busque na metade esquerda - Se o intervalo se reduz a vazio sem encontrar, o alvo não existe
(2) Implementação
#include <stdio.h>
int binary_search(const int *arr, int len, int target) {
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main(void) {
int data[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 78};
int len = sizeof(data) / sizeof(data[0]);
int targets[] = {23, 7, 78, 1};
int num = sizeof(targets) / sizeof(targets[0]);
int i;
for (i = 0; i < num; i++) {
int pos = binary_search(data, len, targets[i]);
if (pos >= 0) {
printf("%d found at index %d\n", targets[i], pos);
} else {
printf("%d not found\n", targets[i]);
}
}
return 0;
}
ext 23 found at index 5 7 not found 78 found at index 9 1 not found
low + (high - low) / 2 em vez de (low + high) / 2 para evitar estouro de inteiros. Este é um detalhe clássico de busca binária.
A complexidade de tempo é O(log n); 1 bilhão de elementos exige no máximo 30 comparações.
▶ Exemplo
Encontre a posição do primeiro elemento maior ou igual ao alvo (busca de limite inferior):
#include <stdio.h>
int lower_bound(const int *arr, int len, int target) {
int low = 0;
int high = len;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int main(void) {
int data[] = {1, 3, 3, 5, 7, 7, 7, 9, 11};
int len = sizeof(data) / sizeof(data[0]);
int pos = lower_bound(data, len, 7);
printf("First >= 7 at index %d, value=%d\n", pos, data[pos]);
return 0;
}
ext First >= 7 at index 4, value=7
Busca de limite inferior é extremamente comum em programação competitiva e na STL.
3. Projeto 3: Inversão de Strings
Troque os caracteres da frente e de trás de uma string, ex.: "hello" torna-se "olleh". Use a técnica de dois ponteiros para operação in-place, sem vetor extra.
(1) Implementação
#include <stdio.h>
#include <string.h>
void str_reverse(char *s) {
char *left = s;
char *right = s + strlen(s) - 1;
while (left < right) {
char temp = *left;
*left = *right;
*right = temp;
left++;
right--;
}
}
int main(void) {
char s1[] = "Hello World";
char s2[] = "ABCDE";
char s3[] = "racecar";
str_reverse(s1);
str_reverse(s2);
str_reverse(s3);
printf("%s\n", s1);
printf("%s\n", s2);
printf("%s\n", s3);
return 0;
}
ext dlroW olleH EDCBA racecar
Nota: você deve usar um vetor de caracteres (modificável), não um ponteiro para um literal de string.
▶ Exemplo
Verifique se uma string é um palíndromo (ignorando caracteres não alfanuméricos, sem distinguir maiúsculas/minúsculas):
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int is_palindrome(const char *s) {
const char *left = s;
const char *right = s + strlen(s) - 1;
while (left < right) {
while (left < right && !isalnum((unsigned char)*left)) left++;
while (left < right && !isalnum((unsigned char)*right)) right--;
if (tolower((unsigned char)*left) != tolower((unsigned char)*right)) {
return 0;
}
left++;
right--;
}
return 1;
}
int main(void) {
printf("%d\n", is_palindrome("racecar"));
printf("%d\n", is_palindrome("hello"));
printf("%d\n", is_palindrome("A man a plan a canal Panama"));
return 0;
}
ext 1 0 1
4. Projeto 4: Análise de Frequência de Caracteres
Conte quantas vezes cada caractere aparece em uma string — uma operação fundamental de análise de texto.
(1) Implementação
#include <stdio.h>
#include <string.h>
void char_freq(const char *s, int *freq, int size) {
int i;
for (i = 0; i < size; i++) freq[i] = 0;
while (*s != '\0') {
unsigned char ch = (unsigned char)*s;
if (ch < (unsigned)size) freq[ch]++;
s++;
}
}
int main(void) {
char text[] = "Hello World!";
int freq[256] = {0};
int i;
char_freq(text, freq, 256);
for (i = 32; i < 127; i++) {
if (freq[i] > 0) printf("'%c': %d ", i, freq[i]);
}
printf("\n");
return 0;
}
ext ' ': 1 '!': 1 'H': 1 'W': 1 'd': 1 'e': 1 'l': 3 'o': 2 'r': 1
Usando valores ASCII como índices do vetor, uma única passagem completa a contagem. 256 posições cobrem todos os caracteres de 8 bits.
▶ Exemplo
Conte frequências de letras e encontre a letra mais frequente:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
void letter_freq(const char *s, int *freq) {
int i;
for (i = 0; i < 26; i++) freq[i] = 0;
while (*s != '\0') {
if (isalpha((unsigned char)*s)) {
freq[tolower((unsigned char)*s) - 'a']++;
}
s++;
}
}
char find_max(const int *freq, int size) {
int max_idx = 0;
int i;
for (i = 1; i < size; i++) {
if (freq[i] > freq[max_idx]) max_idx = i;
}
return 'a' + max_idx;
}
int main(void) {
const char *text = "The quick brown fox jumps over the lazy dog";
int freq[26];
letter_freq(text, freq);
char max_ch = find_max(freq, 26);
printf("Most frequent letter: %c (%d times)\n", max_ch, freq[max_ch - 'a']);
return 0;
}
ext Most frequent letter: o (4 times)
❓ Perguntas Frequentes
P: Qual é melhor, bubble sort ou selection sort? R: Ambos têm complexidade de tempo O(n^2), mas bubble sort tem uma otimização de término antecipado com O(n) no melhor caso. A diferença prática é pequena; nenhum dos dois é adequado para grandes conjuntos de dados.
P: Quais são os pré-requisitos para busca binária? R: O vetor deve estar ordenado e suportar acesso aleatório. Listas encadeadas não podem usar busca binária porque você não pode acessar o elemento do meio em O(1).
P: Existe uma função de biblioteca para inversão de strings? R: A biblioteca padrão C não tem uma função de inversão direta. C++ tem
std::reverseem<algorithm>; em C, você deve implementá-la.
P: Por que usar um vetor de 256 elementos para contagem de frequência? R: unsigned char varia de 0 a 255, totalizando 256 valores. Usando o valor ASCII do caractere como índice, 256 posições cobrem todos os caracteres possíveis, e uma única passagem completa a contagem.
📖 Resumo
- Bubble sort ordena trocando elementos adjacentes; a flag swapped permite término antecipado
- Busca binária requer um vetor ordenado; eficiência O(log n) supera amplamente a busca linear
- A técnica de dois ponteiros inverte strings in-place com complexidade de espaço O(1)
- Análise de frequência de caracteres usa valores ASCII como índices de vetor, completando em uma passagem
- Estes projetos demonstram as três habilidades centrais: armazenamento em vetores, encapsulamento em funções e manipulação com ponteiros
📝 Exercícios
- Aprimore bubble sort: implemente uma função que pode ordenar tanto em ordem crescente quanto decrescente, controlada por um parâmetro de ponteiro de função.
- Implemente uma versão recursiva de busca binária:
int bin_search_rec(const int *arr, int low, int high, int target). - Escreva um analisador de frequência de caracteres aprimorado: leia uma linha de entrada do usuário, depois exiba os 3 caracteres mais frequentes e suas contagens.
