Revise as aulas 43 a 44 com uma folha de consulta, seis questões de leitura de código e uma lista de erros frequentes.
| Estrutura | Característica | Uso típico |
|---|---|---|
| arrays | Acesso direto por índice | Dados de tamanho fixo |
| Lista encadeada | Inserção e remoção eficientes | Dados com tamanho variável |
| Pilha | Último a entrar, primeiro a sair (LIFO) | Chamadas de funções e desfazer |
| Fila | Primeiro a entrar, primeiro a sair (FIFO) | Espera por atendimento e BFS |
struct Node { int value; struct Node *next; // Ponteiro para o próximo nó }; // No último nó, next é NULL
// Pilha (LIFO): push / pop push(1); push(2); push(3); pop(); // → 3 (último inserido) // Fila (FIFO): enqueue / dequeue enqueue(1); enqueue(2); enqueue(3); dequeue(); // → 1 (primeiro inserido)
| Nome | Estratégia | Complexidade |
|---|---|---|
| Bolha | Compara e troca vizinhos | O(N²) |
| Seleção | Move o menor valor para o início | O(N²) |
| Inserção | Insere na posição correta da parte ordenada | O(N²) |
| Método | Pré-requisito | Complexidade |
|---|---|---|
| busca linear | Nenhuma | O(N) |
| busca binária | Dados ordenadossão necessários | O(log N) |
// Após os push, o que um único pop retorna? push(10); push(20); push(30); int v = pop(); printf("%d\n", v);
enqueue(10); enqueue(20); enqueue(30); int v = dequeue(); printf("%d\n", v);
int a[] = {5, 2, 8, 1, 9}; // N=5 for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1 - i; j++) { if (a[j] > a[j+1]) /* swap */; } }
4+3+2+1 = 10. Com N=5, a fórmula N(N-1)/2 também fornece 10. Esse crescimento é quadrático: O(N²).// Procure um item em 1024 dados ordenados // Aproximadamente quantas comparações no pior caso?
2¹⁰ = 1024. Sua complexidade é O(log N), menor que a busca linear. Ela exige dados ordenados.struct Node *cur = head; while (cur->next != NULL) { cur = cur->next; } // Para qual nó cur aponta agora?
cur->next != NULL. Quando next é NULL, cur ainda aponta para o último nó, cujo próximo é NULL. Se a condição fosse cur != NULL, ele só terminaria quando cur fosse NULL.int a[] = {5, 2, 8, 1, 9}; // Após uma passagem (encontrar o mínimo e trocá-lo com o primeiro)?
push/pop usa LIFO;enqueue/dequeue usa FIFO.Lembre pelo exemplo(pilha de pratos e fila do caixa).
free para os nósfree é necessário para evitar Vazamento de memória. Guarde next em outra variável antes de liberar o nó atual.
j < N - 1 - i e j >= 1 : errar o limite por uma posição pode causar Acesso fora dos limites.
a = b; b = a; faz ambas receberem o valor original de b.int t = a; a = b; b = t; realiza a troca por meio de uma variável temporária.
next ainda não estiver claro
Memória dinâmicaPara alocar e liberar nós dinamicamente
Folha de consulta rápidaRevise complexidade e estruturas de dados em uma página